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, en lugar de 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 solo 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 extendieron esta idea a la memoria transaccional solo de software (STM). [3] Desde 2005, STM ha sido el foco de una intensa investigación [4] y el apoyo para 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 hilo completa modificaciones en la memoria compartida sin tener en cuenta lo que otros hilos puedan estar haciendo, registrando cada lectura y escritura que está realizando en un registro. En lugar de colocar la responsabilidad en el escritor para asegurarse de que no afecte negativamente a otras operaciones en curso, se coloca en el lector, quien después de completar una transacción entera verifica que otros hilos no hayan realizado cambios concurrentes en la memoria a la que accedió en el pasado. Esta operación final, en la que se validan los cambios de una transacción y, si la validación es exitosa, se hacen permanentes, se llama confirmación . Una transacción también puede abortar en cualquier momento, lo que hace que todos sus cambios anteriores se reviertan o deshagan. Si una transacción no se puede confirmar debido a cambios conflictivos, generalmente se aborta y se vuelve a ejecutar desde el principio hasta que tenga éxito.
El beneficio de este enfoque optimista es una mayor concurrencia: ningún hilo necesita esperar para acceder a un recurso, y diferentes hilos pueden modificar de forma segura y simultánea partes disjuntas 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 una pérdida de rendimiento en comparación con los sistemas basados en bloqueos de grano fino en un número pequeño de procesadores (de 1 a 4 según la aplicación). Esto se debe principalmente a la sobrecarga asociada con el mantenimiento del registro y el tiempo empleado en confirmar transacciones. Incluso en este caso, el rendimiento no suele ser más del doble de lento. [5] Los defensores de STM creen que esta penalización está justificada por los beneficios conceptuales de STM. [ cita requerida ]
En teoría, la complejidad espacial y temporal en el peor de los casos de n transacciones concurrentes es O ( n ). Las necesidades reales dependen de los detalles de implementación (se puede hacer que las transacciones fallen lo suficientemente pronto para evitar la sobrecarga), pero también habrá casos, aunque raros, en los que los algoritmos basados en bloqueos tengan una mejor complejidad temporal que la memoria transaccional del software.
Además de sus beneficios en el rendimiento, [ cita requerida ] 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:
En cambio, el concepto de transacción de memoria es mucho más simple, porque cada transacción puede considerarse aislada como un cálculo de un solo subproceso. Los bloqueos mutuos y los bloqueos activos se evitan por completo o se gestionan mediante un administrador de transacciones externo; el programador no tiene por qué preocuparse por ello. La inversión de prioridades todavía puede ser un problema, pero las transacciones de alta prioridad pueden abortar transacciones conflictivas de menor prioridad que aún no se hayan confirmado.
Sin embargo, la necesidad de reintentar y abortar transacciones limita su comportamiento. Cualquier operación realizada dentro de una transacción debe ser idempotente ya que una transacción puede ser reintentada. Además, si una operación tiene efectos secundarios que deben deshacerse si la transacción se aborta, entonces debe incluirse una operación de reversión correspondiente. Esto hace que muchas operaciones de entrada/salida (E/S) sean difíciles o imposibles de realizar dentro de las transacciones. Estos límites generalmente se superan en la práctica mediante la creación de búferes que ponen en cola las operaciones irreversibles y las realizan después de que la transacción tenga éxito. En Haskell , este límite se aplica en tiempo de compilación por el tipo de datos system .
En 2005, Tim Harris, Simon Marlow , Simon Peyton Jones y Maurice Herlihy describieron un sistema STM basado en Concurrent Haskell que permite que operaciones atómicas arbitrarias se compongan en operaciones atómicas más grandes, un concepto útil que es imposible con la programación basada en bloqueos. Para citar a los autores:
Tal vez la objeción más fundamental [...] es que los programas basados en bloqueos no se 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 suponga 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 forma 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., "Composable Memory Transactions", Sección 2: Antecedentes, pág. 2 [6]
Con STM, este problema es fácil de resolver: simplemente envolviendo dos operaciones en una transacción se hace que la operación combinada sea atómica. El único punto conflictivo es que no está claro para el llamador, que no conoce los detalles de implementación de los métodos del componente, 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 leyó y vuelve a intentar 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 vuelve a intentarlo , ejecuta una segunda. Si ambas transacciones vuelven a intentarlo, las vuelve a intentar tan pronto como se realiza un cambio relevante. [ Aclaración necesaria ] Esta facilidad, comparable a características como la llamada de red de la Interfaz de sistema operativo portátil ( POSIX ) select(), permite al llamador esperar en cualquiera de varios eventos simultáneamente. También simplifica las interfaces de programación, por ejemplo, al proporcionar un mecanismo simple para convertir entre operaciones bloqueantes y no bloqueantes.
Este esquema se ha implementado en el compilador Glasgow Haskell .
La simplicidad conceptual de los STM permite que se expongan al programador mediante una sintaxis de lenguaje relativamente simple . En "Language Support for Lightweight Transactions" de Tim Harris y Keir Fraser se propuso la idea de utilizar la región crítica condicional (CCR) clásica para representar transacciones. En su forma más simple, se trata simplemente de un "bloque atómico", un bloque de código que ocurre lógicamente en un único instante:
// Insertar un nodo en una lista doblemente enlazada atómicamente atómica { 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, de lo contrario, se cancela y se vuelve a intentar. (Esto es simplemente un ejemplo conceptual, no un código correcto. Por ejemplo, se comporta incorrectamente si se elimina un nodo de la lista durante la transacción).
Los CCR también permiten una condición de protección , que permite que una transacción espere hasta que tenga trabajo que realizar:
atómico (queueSize > 0) { eliminar elemento de la cola y usarlo }Si no se cumple la condición, 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. "Composable Memory Transactions" [6] llevó esto un paso más allá con su comando retry (discutido anteriormente), que puede, en cualquier momento, abortar la transacción y esperar hasta que se modifique algún valor leído previamente por la transacción antes de volver a intentarlo. Por ejemplo:
atómico { si (queueSize > 0) { eliminar elemento de la cola y usarlo } demás { rever } }Esta capacidad de reintentar dinámicamente en etapas tardías 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 "Composable Memory Transactions", [6] los autores decidieron que esto debería abortar la transacción, ya que las excepciones normalmente indican errores inesperados en Concurrent Haskell, pero que la excepción podría retener información asignada y leída durante la transacción para fines de diagnóstico. Destacan que otras decisiones de diseño pueden ser razonables en otras configuraciones.
STM se puede implementar como un algoritmo sin bloqueos o puede utilizar bloqueos. [7] Hay dos tipos de esquemas de bloqueo: en el bloqueo en tiempo de encuentro (Ennals, Saha y Harris), las escrituras en memoria se realizan adquiriendo primero temporalmente un bloqueo para una ubicación determinada, escribiendo el valor directamente y registrándolo en el registro de deshacer. El bloqueo en tiempo de confirmación bloquea las ubicaciones de 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 la versión de lectura. Luego, en cada lectura o escritura, la versión de la ubicación de memoria en particular se compara con la versión de lectura; y, si es mayor, la transacción se cancela. Esto garantiza que el código se ejecute en una instantánea consistente de la memoria. Durante la confirmación, se bloquean todas las ubicaciones de escritura 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 versión global, los nuevos valores de escritura del registro se vuelven a escribir en la memoria y se marcan con la nueva versión del reloj.
Un problema con la implementación de la memoria transaccional de software con lectura optimista es que es posible que una transacción incompleta lea un estado inconsistente (es decir, que 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 confirmarse, por lo que esto no viola la condición de consistencia impuesta por el sistema transaccional, pero es posible que este estado inconsistente "temporal" haga que una transacción active una condición excepcional fatal, como un error de segmentación, o incluso entre en un bucle sin fin, como en el siguiente ejemplo artificial de la Figura 4 de "Soporte de lenguaje para transacciones livianas":
Si x = y inicialmente, ninguna de las transacciones anteriores altera este 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ía que entrara en un bucle infinito. La estrategia habitual para lidiar con esto es interceptar cualquier excepción fatal y abortar cualquier transacción que no sea válida.
Una forma de abordar estos problemas es detectar las transacciones que ejecutan operaciones ilegales o no logran finalizarlas y abortarlas limpiamente; otro enfoque es el esquema de bloqueo transaccional.