memoria transaccional de software

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 la 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 ú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 extendieron esta idea a la memoria transaccional exclusivamente de software (STM). ^{[ 3 ]} Desde 2005, STM ha sido el foco de una intensa investigación ^{[ 4 ]} y el apoyo a las implementaciones prácticas está creciendo.

A diferencia de las técnicas de bloqueo utilizadas en la mayoría de las aplicaciones multihilo modernas, STM suele ser muy optimista : un hilo completa las modificaciones en la memoria compartida sin tener en cuenta lo que otros hilos puedan estar haciendo, registrando cada lectura y escritura que realiza en un registro. En lugar de que la responsabilidad recaiga en el escritor para asegurarse de no afectar negativamente a otras operaciones en curso, recae en el lector, quien, tras completar una transacción completa, verifica que otros hilos no hayan realizado cambios concurrentes en la memoria a la que accedió anteriormente. 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 denomina confirmación . Una transacción también puede abortarse 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 conflictivos, normalmente se aborta y se vuelve a ejecutar desde el principio hasta que se complete con éxito.

La ventaja 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 disminución del rendimiento en comparación con los sistemas basados ​​en bloqueos de grano fino en un número reducido 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 las 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 se justifica por los beneficios conceptuales de STM.

Teóricamente, la complejidad espacial y temporal en el peor de los casos para n transacciones concurrentes es O ( n ). Las necesidades reales dependen de los detalles de la 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 ventajas en cuanto al rendimiento, STM simplifica enormemente la comprensión conceptual de los programas multihilo y contribuye 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 presenta una serie de problemas bien conocidos que surgen con frecuencia en la práctica:

• El bloqueo requiere pensar en operaciones superpuestas y operaciones parciales en secciones de código distantes y aparentemente no relacionadas, una tarea muy difícil y propensa a errores.
• El bloqueo exige que los programadores adopten una política de bloqueo para evitar interbloqueos , bloqueos permanentes y otros fallos que impidan el progreso. Estas políticas suelen aplicarse de forma informal y son falibles, y cuando surgen estos problemas, resultan insidiosamente difíciles de reproducir y depurar.
• El bloqueo puede provocar una inversión de prioridad , un fenómeno en el que un hilo de alta prioridad se ve obligado a esperar a que un hilo de baja prioridad tenga acceso exclusivo a un recurso que necesita.

En cambio, el concepto de transacción de memoria es mucho más sencillo, ya que cada transacción puede considerarse de forma aislada como un cálculo de un solo hilo. El interbloqueo y el bloqueo permanente se evitan por completo o son gestionados por un gestor de transacciones externo; el programador apenas tiene que preocuparse por ello. La inversión de prioridad aún puede ser un problema, pero las transacciones de alta prioridad pueden abortar las 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 podría reintentarse. 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 creando búferes que ponen en cola las operaciones irreversibles y las ejecutan después de que la transacción tenga éxito. En Haskell , este límite se impone en tiempo de compilación por el sistema de tipos .

En 2005, Tim Harris, Simon Marlow , Simon Peyton Jones y Maurice Herlihy describieron un sistema STM basado en Concurrent Haskell que permite componer operaciones atómicas arbitrarias en operaciones atómicas más grandes, un concepto útil imposible con la programación basada en bloqueos. Citando a los autores:

Quizás la objeción más fundamental [...] es que los programas basados ​​en bloqueos no se componen : los fragmentos correctos pueden fallar al combinarse. Por ejemplo, consideremos una tabla hash con operaciones de inserción y eliminación seguras para subprocesos. Supongamos ahora que queremos eliminar un elemento A de la tabla t1 e insertarlo en la tabla t2; pero el estado intermedio (en el que ninguna de las tablas 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 encapsulando dos operaciones en una transacción, la operación combinada se vuelve atómica. El único inconveniente es que, para quien realiza la llamada, que desconoce los detalles de implementación de los métodos componentes, no está claro cuándo debe intentar ejecutar la transacción nuevamente 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 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 modifique al menos uno de estos valores.

Los autores también propusieron un mecanismo para la composición de alternativas , la orElsefunción. Esta ejecuta una transacción y, si esta realiza un reintento , ejecuta una segunda. Si ambas reintentan, las vuelve a intentar en cuanto se produce un cambio relevante. Esta funcionalidad, comparable a características como la llamada de red POSIX (Portable Operating System Interface ) select(), permite al emisor esperar simultáneamente a cualquiera de varios eventos. Además, simplifica las interfaces de programación, por ejemplo, al proporcionar un mecanismo sencillo para convertir entre operaciones bloqueantes y no bloqueantes.

Este esquema se ha implementado en el compilador Haskell de Glasgow .

La simplicidad conceptual de las STM permite que el programador las comprenda utilizando una sintaxis de lenguaje relativamente sencilla . En su artículo "Language Support for Lightweight Transactions" (Soporte de lenguaje para transacciones ligeras), 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, se trata de un "bloque atómico", un bloque de código que ocurre lógicamente en un único instante.

// Inserta un nodo en una lista doblemente enlazada de forma atómica { nuevoNodo->prev = nodo; nuevoNodo->siguiente = nodo->siguiente; nodo->siguiente->anterior = nuevoNodo; nodo->siguiente = nuevoNodo; }

Al llegar al final del bloque, la transacción se confirma si es posible; de ​​lo contrario, se cancela y se vuelve a intentar. (Este es solo 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).

Las CCR también permiten una condición de guarda , que permite que una transacción espere hasta que tenga trabajo que hacer:

atómico (tamaño de cola > 0) { eliminar el elemento de la cola y usarlo }

Si la condición no se cumple, el gestor de transacciones esperará hasta que otra transacción haya realizado una confirmación que afecte a 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 hilos. Las "Transacciones de Memoria Componibles" ^{[ 6 ]} fueron un paso más allá con su comando de reintento (mencionado 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 (tamaño de la cola > 0) { eliminar el elemento de la cola y usarlo } demás { rever } }

Esta capacidad de reintentar dinámicamente en una etapa avanzada de la transacción simplifica el modelo de programación y abre nuevas posibilidades.

Un problema radica en 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 conservar información asignada y leída durante la transacción con fines de diagnóstico. Destacan que otras decisiones de diseño podrían ser razonables en otros contextos.

STM puede implementarse 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 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 confirmación de transacciones 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 específica se compara con la versión de lectura; si es mayor, la transacción se aborta. Esto garantiza que el código se ejecute sobre una instantánea consistente de la memoria. Durante la confirmación, todas las ubicaciones de escritura se bloquean y se vuelven a comprobar 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 escriben en la memoria y se les asigna la nueva versión del reloj.

Un problema al implementar memoria transaccional de software con lectura optimista es que una transacción incompleta puede leer un estado inconsistente (es decir, leer una mezcla de valores antiguos y nuevos escritos por otra transacción). Dicha transacción está condenada a abortar si 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" provoque que una transacción desencadene una condición excepcional fatal, como un fallo de segmentación , o incluso que entre en un bucle infinito, como en el siguiente ejemplo artificial de la Figura 4 de "Soporte de lenguaje para transacciones ligeras":

Si inicialmente x = y , ninguna de las transacciones anteriores altera 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ía un bucle infinito. La estrategia habitual para solucionar esto consiste en 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 que no finalizan correctamente y abortarlas de forma limpia; otro enfoque es el esquema de bloqueo transaccional .

• Haskell GHC ^{[ 8 ]}
• C++ cpp_stm_free ^{[ 9 ]}
• Referencias de Clojure , ^{[ 10 ]} portadas a node-stm ^{[ 11 ]}
• Go Kashmir ^{[ 12 ]}
• Rust async-stm ^{[ 13 ]}
• Scala ZIO ^{[ 14 ]}
• OCaml Kcas ^{[ 15 ]}
• Kotlin arrow-fx-stm ^{[ 16 ]}