En tecnología informática , la memoria transaccional de software ( STM ) es un mecanismo de control de concurrencia similar al mecanismo de transacción de base de datos para controlar el acceso a la memoria compartida en computación paralela . Es una alternativa para la sincronización basada en bloqueo . Una transacción en este contexto es una pieza de código que lee y escribe en la memoria compartida (compartida). La lectura y la escritura ocurren lógicamente en un solo punto en el tiempo, y los estados intermedios son invisibles para otras transacciones (resultantes). La idea de brindar transacciones con soporte de hardware se originó en 1986 en el trabajo y patente de Tom Knight . [1] La idea fue publicitada por Maurice Herlihy y Eliot Moss . [2] En 1995, Nir Shavit y Dan Toytu extendieron esta idea a la memoria transaccional de software (STM). STM todavía está en el centro de una intensa investigación; su apoyo a las implementaciones prácticas está aumentando.
A diferencia de los métodos de bloqueo utilizados en la mayoría de las aplicaciones multiproceso modernas, STM es muy optimista: un subproceso completa los cambios en la memoria compartida sin tener en cuenta lo que están haciendo otros subprocesos y registra las lecturas y escrituras en el registro. En lugar de usar el escritor para verificar si tiene un efecto negativo en otras operaciones en curso, la responsabilidad se transfiere al lector, que, después de completar una transacción completa, verifica si otros subprocesos han realizado cambios simultáneos en la memoria a la que se accedió en el pasado. . Esta última operación, que verifica los cambios en las transacciones y que, si la verificación tiene éxito, permanece sin cambios, se denomina confirmación. La transacción puede cancelarse en cualquier momento, como resultado de lo cual se cancelarán todos los cambios recientes. Si no se puede confirmar una transacción debido a conflictos de cambio, se aborta y se vuelve a intentar desde el principio hasta que se completa con éxito.
La ventaja de este enfoque optimista se ve reforzada por el paralelismo: ningún subproceso necesita esperar para acceder a un recurso, y diferentes subprocesos pueden modificar de manera simultánea y segura partes inconexas de la estructura de datos que estarían protegidas por el mismo bloqueo.
Sin embargo, en la práctica, los sistemas STM pierden rendimiento frente a sistemas de granularidad fina basados en bloqueos en una pequeña cantidad de procesadores (de 1 a 4 dependiendo de la aplicación). Esto se debe principalmente a la sobrecarga de mantener el registro y el tiempo dedicado a las transacciones. Pero incluso en este caso, el rendimiento difiere en no más de 2 veces. [3] Los partidarios de STM creen que tales pérdidas están justificadas por las ventajas conceptuales de STM.
Teóricamente, la complejidad de tiempo y espacio de ejecutar n transacciones paralelas es O (n) en el peor de los casos . El costo real depende de la implementación (puede cancelar la transacción antes de tiempo para evitar gastos generales), pero siempre habrá casos, aunque raros, en los que los algoritmos de bloqueo tendrán una mayor complejidad de tiempo que la memoria transaccional del software.
Además de los beneficios de rendimiento, STM simplifica en gran medida la comprensión conceptual de los programas de subprocesos múltiples y ayuda en su mantenimiento al trabajar sin problemas con las abstracciones de alto nivel existentes, como objetos y módulos.
La programación de cerraduras contiene una serie de problemas conocidos que a menudo surgen en la práctica:
Por el contrario, el concepto de memoria transaccional es mucho más simple, porque cada transacción puede considerarse individualmente, como un cálculo de un solo subproceso. Los interbloqueos se evitan por completo o los resuelve un administrador de transacciones externo; el programador apenas necesita preocuparse por esto. La inversión de prioridad aún puede ser un problema, pero las transacciones de alta prioridad pueden anular las transacciones de baja prioridad en conflicto que aún no se han comprometido.
Por otro lado, la necesidad de abortar transacciones fallidas también impone restricciones en su comportamiento: no pueden realizar ninguna operación que no se pueda deshacer, incluida la mayoría de las operaciones de E/S. Tales limitaciones generalmente se superan en la práctica mediante la creación de búferes que ponen en cola operaciones irreversibles y las ejecutan algún tiempo después fuera de cualquier transacción. En Haskell, esta restricción la impone el sistema de tipos en tiempo de compilación.
En 2005, Tim Harris, Simon Marlow, Simon Peyton-Jones y Maurice Herlihy describieron un sistema STM integrado en Haskell que implementa el paralelismo. Este sistema permite combinar operaciones atómicas arbitrarias en operaciones atómicas más grandes, un concepto útil que no es posible con la programación de bloqueo. Según los autores:
“Quizás el inconveniente más fundamental es que los programas de bloqueo no pueden vincularse: es posible que los fragmentos correctos no funcionen cuando se vinculan. Considere, por ejemplo, una tabla hash con inserciones y eliminaciones seguras para subprocesos. Ahora supongamos que queremos eliminar un elemento de la tabla t1 e insertarlo en la tabla t2, pero el estado intermedio (en el que ninguna tabla contiene ese elemento) no debería ser visible para otros subprocesos. Hasta que el diseñador de la tabla hash determine esta necesidad, simplemente no hay forma de satisfacer este requisito. En general, cada operación correcta (inserciones, eliminaciones) no se puede combinar en operaciones correctas más grandes.
— (Tim Harris et al., "Operación de acceso a la memoria componible", Sección 2. Antecedentes, p.2)Con STM, este problema se resuelve de manera simple: la simple combinación de dos operaciones en una transacción convierte una operación componible en atómica. El único obstáculo es que no está claro para la persona que llama, que no conoce los detalles de implementación de los métodos de enlace, cuándo debe intentar volver a intentar la transacción si no ocurre. En respuesta a esto, los autores han propuesto un comando de reintento que utiliza el registro de transacciones (archivo de registro) generado por la transacción fallida para determinar la parte de la memoria que lee. Luego, automáticamente inicia la transacción nuevamente cuando cambia una de estas ubicaciones de memoria. Esto se basa en la lógica de que una transacción no se comportará de manera diferente hasta que al menos uno de esos valores haya cambiado.
Los autores también propusieron un mecanismo para construir alternativas (la función orElse). Inicia una transacción y si la transacción se vuelve a intentar, inicia una segunda. Si ocurre lo mismo con el segundo, el mecanismo vuelve a poner en marcha a ambos hasta que se produce un cambio significativo. Esta función, comparable a la función select() estándar de la red POSIX, permite que la persona que llama espere cualquiera de una serie de eventos al mismo tiempo. También simplifica la programación de la interfaz, por ejemplo, proporcionando un mecanismo de conversión simple entre operaciones de bloqueo y no bloqueo.
Este esquema fue implementado en el compilador GHC de Haskell .
La simplicidad conceptual de los sistemas STM permite al programador trabajar fácilmente con ellos usando una sintaxis relativamente simple del lenguaje. En su libro An Auxiliary Language for Lightweight Transactions, 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 solo un "bloque atómico", una pieza de código que se ejecuta secuencialmente en un solo punto en el tiempo:
// Insertar atómicamente un nodo en una lista doblemente enlazada atómico { nuevoNodo->anterior = nodo; nuevoNodo->siguiente = nodo->siguiente; nodo->siguiente->anterior = nuevoNodo; nodo->siguiente = nuevoNodo; }Cuando se llega al final del bloque, la transacción se compromete, si es posible, de lo contrario, se termina y se repite. Las regiones críticas condicionales también permiten una condición de persistencia, lo que permite que una transacción espere hasta que su trabajo entre en vigor.
atómico (tamaño de la cola > 0) { eliminar elemento de la cola y usarlo }Si la condición falla, el administrador de transacciones esperará hasta que ocurra otra que afecte la condición antes de volver a intentarlo. Esta comunicación flexible entre productores y consumidores mejora la modularidad sobre una señalización clara entre hilos. Composable Memory Access va más allá con su comando de reintento (ver arriba), que puede abortar la transacción en cualquier momento y esperar hasta que haya algún cambio en el valor leído previamente por la operación antes de volver a intentarlo. Ejemplo:
atómico { if (tamaño de la cola > 0) { eliminar elemento de la cola y usarlo } más { rever } }Esta capacidad de reintentar dinámicamente al final de una transacción simplifica el modelo de programación y abre nuevas posibilidades.
Un problema es el comportamiento de las excepciones cuando se propagan fuera de las transacciones. En "Una operación de acceso a memoria componible", los autores decidieron que esto debería abortar la transacción, ya que las excepciones suelen indicar errores inesperados en Haskell (con concurrencia), pero que esta excepción puede almacenar la información proporcionada y leerla durante la transacción para los fines de diagnósticos. Destacan que otras decisiones de diseño también son razonables bajo otros parámetros.
STM se puede implementar como un algoritmo bloqueable y sin bloqueo. Hay dos tipos de bloqueo.
El esquema de ejecución de transacciones, llamado "Transactional Locking-2" e implementado por Dice, Shalev y Shavit, utiliza el tiempo global. Cada transacción comienza leyendo el valor de tiempo actual y lo almacena para su lectura. Luego, en cada lectura y escritura, la versión del área de memoria especificada se compara con la versión de lectura y, si es mayor, la transacción se cancela. Esto asegura que el código se ejecute en la copia apropiada de la memoria. Durante la confirmación, todas las regiones de lectura se bloquean y los valores de la versión dada de todas las regiones de memoria de escritura y lectura se vuelven a verificar. Finalmente, se incrementa el tiempo global, los nuevos valores de la entrada de registro se vuelven a escribir en la memoria con la nueva versión del tiempo.
Un método cada vez más popular para gestionar conflictos transaccionales en la memoria transaccional , especialmente en STM, es el orden en el que(CO). Se utiliza para lograr un pedido sin bloqueo (es decir, sin bloqueo en transacciones en conflicto y solo bloqueo en el compromiso de transacción) reordenando transacciones (p. ej., Ramadan et al. 2009 y Zhang et al. 2006). Ordenar es la base para el estado correcto de la memoria transaccional (cuando se realizan transacciones paralelas). Ya se han publicado docenas de artículos y patentes sobre STM utilizando el "orden de ejecución".
"Zhang et al., 2006" es una patente estadounidense titulada "Transaction Order Software and Conflict Management" (que hace referencia a Order Order US Patent 5.701.480). Aquí hay extractos:
"Se están desarrollando varias tecnologías y métodos para aplicar el orden de ejecución en un sistema de memoria transaccional de software. El sistema de memoria transaccional del programa está equipado con una función para que un orden de ejecución predefinido sea aplicable a muchas operaciones. El orden de confirmación predefinido se utiliza en tiempo de ejecución para establecer el orden en el que realizar transacciones en el sistema de memoria transaccional del software. El proceso de gestión de conflictos se invoca cuando conflicto entre la primera y la segunda transacción. El orden predefinido de compromiso se utiliza en el proceso de gestión de conflictos, para determinar qué transacción debe ganar el conflicto y debe continuar".Con orden de compromiso, la propiedad deseada de ordenar se logra al comprometer transacciones solo en orden cronológico consistente con el orden de precedencia (según lo determinado por el orden cronológico de operaciones en conflictos)
SRTM ha sido implementado (de diferente calidad y estabilidad) en varios lenguajes de programación. Como: