En informática , la memoria transaccional de software ( STM ) es un mecanismo de control de concurrencia análogo a las transacciones de bases de datos para controlar el acceso a la memoria compartida en computación concurrente . Es una alternativa a la sincronización basada en bloqueos . STM es una estrategia implementada en software, más que como un componente de hardware. Una transacción en este contexto ocurre cuando un fragmento de código ejecuta una serie de lecturas y escrituras en la memoria compartida. Estas lecturas y escrituras ocurren lógicamente en un único instante en el tiempo; Los estados intermedios no son visibles para otras transacciones (exitosas). La idea de proporcionar soporte de hardware para transacciones se originó en un artículo de 1986 de Tom Knight . [1] La idea fue popularizada por Maurice Herlihy y J. Eliot B. Moss . [2] En 1995, Nir Shavit y Dan Touitou ampliaron esta idea a la memoria transaccional sólo de software (STM). [3] Desde 2005, STM ha sido el foco de una intensa investigación [4] y el apoyo a implementaciones prácticas está creciendo.
A diferencia de las técnicas de bloqueo utilizadas en la mayoría de las aplicaciones multiproceso modernas, STM suele ser muy optimista : un subproceso completa modificaciones en la memoria compartida sin tener en cuenta lo que otros subprocesos podrían estar haciendo, registrando cada lectura y escritura que realiza en un registro. En lugar de asignar la responsabilidad al escritor para asegurarse de que no afecte negativamente a otras operaciones en progreso, se le asigna al lector, quien después de completar una transacción completa verifica que otros subprocesos no hayan realizado cambios simultáneamente en la memoria a la que accedió en el proceso. pasado. Esta operación final, en la que los cambios de una transacción se validan y, si la validación es exitosa, se vuelven permanentes, se llama confirmación . Una transacción también puede cancelarse en cualquier momento, lo que provoca que todos sus cambios anteriores se reviertan o se deshagan. Si una transacción no se puede confirmar debido a cambios contradictorios, normalmente se cancela y se vuelve a ejecutar desde el principio hasta que se realiza correctamente.
El beneficio de este enfoque optimista es una mayor concurrencia: ningún subproceso necesita esperar para acceder a un recurso, y diferentes subprocesos pueden modificar de forma segura y simultánea partes separadas de una estructura de datos que normalmente estarían protegidas bajo el mismo bloqueo.
Sin embargo, en la práctica, los sistemas STM también sufren un impacto en el rendimiento en comparación con los sistemas basados en bloqueos de grano fino en una pequeña cantidad de procesadores (de 1 a 4 dependiendo de la aplicación). Esto se debe principalmente a los gastos generales asociados con el mantenimiento del registro y el tiempo dedicado a realizar transacciones. Incluso en este caso, el rendimiento no suele ser peor que el doble de lento. [5] Los defensores de STM creen que esta penalización está justificada por los beneficios conceptuales de STM. [ cita necesaria ]
Teóricamente, el peor caso de complejidad espacial y temporal de n transacciones concurrentes es O ( n ). Las necesidades reales dependen de los detalles de implementación (se pueden hacer que las transacciones fallen lo suficientemente pronto como para evitar gastos generales), pero también habrá casos, aunque raros, en los que los algoritmos basados en bloqueos tengan una mejor complejidad temporal que la memoria transaccional de software.
Además de sus beneficios de rendimiento, [ cita necesaria ] STM simplifica enormemente la comprensión conceptual de los programas multiproceso y ayuda a que los programas sean más fáciles de mantener al trabajar en armonía con abstracciones de alto nivel existentes, como objetos y módulos. La programación basada en bloqueos tiene una serie de problemas bien conocidos que surgen con frecuencia en la práctica:
Por el contrario, el concepto de transacción de memoria es mucho más simple, porque cada transacción puede verse de forma aislada como un cálculo de un solo subproceso. Los interbloqueos y los bloqueos activos se evitan por completo o son manejados por un administrador de transacciones externo; el programador apenas necesita preocuparse por ello. La inversión de prioridad aún puede ser un problema, pero las transacciones de alta prioridad pueden cancelar transacciones conflictivas de menor prioridad que aún no se han comprometido.
Sin embargo, la necesidad de abortar transacciones fallidas también impone límites al comportamiento de las transacciones: no pueden realizar ninguna operación que no pueda deshacerse, incluida la mayoría de las entradas/salidas (E/S). Estos límites normalmente se superan en la práctica creando buffers que ponen en cola las operaciones irreversibles y las realizan en un momento posterior fuera de cualquier transacción. En Haskell , este límite lo aplica el sistema de tipos de datos en tiempo de compilación .
En 2005, Tim Harris, Simon Marlow , Simon Peyton Jones y Maurice Herlihy describieron un sistema STM construido sobre Haskell concurrente que permite que operaciones atómicas arbitrarias se compongan en operaciones atómicas más grandes, un concepto útil imposible con la programación basada en bloqueos. Para citar a los autores:
Quizás la objeción más fundamental [...] es que los programas basados en bloqueos no componen : los fragmentos correctos pueden fallar cuando se combinan. Por ejemplo, considere una tabla hash con operaciones de inserción y eliminación seguras para subprocesos. Ahora supongamos que queremos eliminar un elemento A de la tabla t1 e insertarlo en la tabla t2; pero el estado intermedio (en el que ninguna tabla contiene el elemento) no debe ser visible para otros subprocesos. A menos que el implementador de la tabla hash anticipe esta necesidad, simplemente no hay manera de satisfacer este requisito. [...] En resumen, las operaciones que son individualmente correctas (insertar, eliminar) no se pueden componer en operaciones correctas más grandes.
—Tim Harris et al., "Transacciones de memoria componibles", Sección 2: Antecedentes, página 2 [6]
Con STM, este problema es fácil de resolver: simplemente envolver dos operaciones en una transacción hace que la operación combinada sea atómica. El único punto conflictivo es que no está claro para la persona que llama, que desconoce los detalles de implementación de los métodos componentes, cuándo debe intentar volver a ejecutar la transacción si falla. En respuesta, los autores propusieron un retrycomando que utiliza el registro de transacciones generado por la transacción fallida para determinar qué celdas de memoria lee y reintenta automáticamente la transacción cuando se modifica una de estas celdas, basándose en la lógica de que la transacción no se comportará de manera diferente. hasta que se cambie al menos uno de esos valores.
Los autores también propusieron un mecanismo para la composición de alternativas , la orElsefunción. Ejecuta una transacción y, si esa transacción realiza un reintento , ejecuta una segunda. Si ambos lo vuelven a intentar, los vuelve a intentar tan pronto como se realiza un cambio relevante. [ se necesita aclaración ] Esta función, comparable a funciones como la llamada de red de la interfaz del sistema operativo portátil ( POSIX ) select(), permite a la persona que llama esperar en cualquiera de varios eventos simultáneamente. También simplifica las interfaces de programación, por ejemplo, proporcionando un mecanismo simple para convertir entre operaciones de bloqueo y sin bloqueo.
Este esquema se ha implementado en el compilador Haskell de Glasgow .
La simplicidad conceptual de los STM permite exponerlos al programador utilizando una sintaxis de lenguaje relativamente simple . "Language Support for Lightweight Transactions" de Tim Harris y Keir Fraser propusieron la idea de utilizar la región crítica condicional (CCR) clásica para representar transacciones. En su forma más simple, esto es simplemente un "bloque atómico", un bloque de código que lógicamente ocurre en un solo instante:
// Inserta un nodo en una lista doblemente enlazada atómicamente atómico { nuevoNodo->prev = nodo; nuevoNodo->siguiente = nodo->siguiente; nodo->siguiente->anterior = nuevoNodo; nodo->siguiente = nuevoNodo; }Cuando se llega al final del bloque, la transacción se confirma, si es posible, o se aborta y se vuelve a intentar. (Esto es simplemente un ejemplo conceptual, no un código correcto. Por ejemplo, se comporta incorrectamente si el nodo se elimina de la lista durante la transacción).
Los CCR también permiten una condición de guardia , que permite que una transacción espere hasta que tenga trabajo que hacer:
atómico (tamaño de cola > 0) { eliminar elemento de la cola y usarlo }Si la condición no se cumple, el administrador de transacciones esperará hasta que otra transacción haya realizado una confirmación que afecte la condición antes de volver a intentarlo. Este acoplamiento flexible entre productores y consumidores mejora la modularidad en comparación con la señalización explícita entre subprocesos. "Transacciones de memoria componible" [6] llevó esto un paso más allá con su comando de reintento (analizado anteriormente), que puede, en cualquier momento, cancelar la transacción y esperar hasta que algún valor leído previamente por la transacción se modifique antes de volver a intentarlo. Por ejemplo:
atómico { si (tamaño de cola > 0) { eliminar elemento de la cola y usarlo } demás { rever } }Esta capacidad de reintentar dinámicamente al final de la transacción simplifica el modelo de programación y abre nuevas posibilidades.
Un problema es cómo se comportan las excepciones cuando se propagan fuera de las transacciones. En "Transacciones de memoria componible", [6] los autores decidieron que esto debería abortar la transacción, ya que las excepciones normalmente indican errores inesperados en Haskell concurrente, pero que la excepción podría retener información asignada y leída durante la transacción con fines de diagnóstico. Destacan que otras decisiones de diseño pueden ser razonables en otros entornos.
STM se puede implementar como un algoritmo sin bloqueo o puede utilizar bloqueo. [7] Hay dos tipos de esquemas de bloqueo: En el bloqueo en tiempo de encuentro (Ennals, Saha y Harris), las escrituras en la memoria se realizan adquiriendo primero temporalmente un bloqueo para una ubicación determinada, escribiendo el valor directamente y registrándolo en el deshacer registro. El bloqueo en el momento de la confirmación bloquea las ubicaciones de la memoria solo durante la fase de confirmación.
Un esquema de tiempo de confirmación denominado "Bloqueo transaccional II" implementado por Dice, Shalev y Shavit utiliza un reloj de versión global. Cada transacción comienza leyendo el valor actual del reloj y almacenándolo como versión de lectura. Luego, en cada lectura o escritura, la versión de la ubicación de memoria particular se compara con la versión de lectura; y, si es mayor, se aborta la transacción. Esto garantiza que el código se ejecute en una instantánea consistente de la memoria. Durante la confirmación, todas las ubicaciones de escritura se bloquean y se vuelven a verificar los números de versión de todas las ubicaciones de lectura y escritura. Finalmente, se incrementa el reloj de la versión global, los nuevos valores de escritura del registro se vuelven a escribir en la memoria y se sellan con la nueva versión del reloj.
Un problema con la implementación de memoria transaccional de software con lectura optimista es que es posible que una transacción incompleta lea un estado inconsistente (es decir, lea una mezcla de valores antiguos y nuevos escritos por otra transacción). Una transacción de este tipo está condenada a abortar si alguna vez intenta comprometerse, por lo que esto no viola la condición de coherencia impuesta por el sistema transaccional, pero es posible que este estado inconsistente "temporal" haga que una transacción desencadene una condición excepcional fatal como como un error de segmentación o incluso entrar en un bucle sin fin, como en el siguiente ejemplo ideado de la Figura 4 de "Soporte de lenguaje para transacciones ligeras":
Siempre que x = y inicialmente, ninguna de las transacciones anteriores altere esta invariante, pero es posible que la transacción A lea x después de que la transacción B la actualice, pero lea y antes de que la transacción B la actualice, lo que provocará que entre en un bucle infinito. La estrategia habitual para solucionar este problema es interceptar cualquier excepción fatal y abortar cualquier transacción que no sea válida.
Una forma de abordar estos problemas es detectar transacciones que ejecutan operaciones ilegales o no las terminan y abortan limpiamente; Otro enfoque es el esquema de bloqueo transaccional.