Linealizabilidad

Este artículo duplica el alcance de otros artículos , específicamente serialización y atomicidad (sistemas de bases de datos) . Analice este tema y ayude a introducir un estilo de resumen en el artículo. ( Noviembre de 2018 )

En la programación concurrente , una operación (o conjunto de operaciones) es linealizable si consiste en una lista ordenada de eventos de invocación y respuesta , que puede ampliarse agregando eventos de respuesta tales que:

1. La lista extendida se puede reexpresar como un historial secuencial (es serializable ).
2. Esa historia secuencial es un subconjunto de la lista original no ampliada.

De manera informal, esto significa que la lista de eventos no modificados es linealizable si y solo si sus invocaciones fueron serializables, pero algunas de las respuestas del programa serial aún no han regresado. ^[1]

En un sistema concurrente, los procesos pueden acceder a un objeto compartido al mismo tiempo. Debido a que varios procesos acceden a un único objeto, puede surgir una situación en la que, mientras un proceso accede al objeto, otro proceso cambia su contenido. Hacer que un sistema sea linealizable es una solución a este problema. En un sistema linealizable, aunque las operaciones se superponen en un objeto compartido, cada operación parece tener lugar instantáneamente. La linealización es una condición de corrección fuerte, que restringe qué resultados son posibles cuando varios procesos acceden a un objeto simultáneamente. Es una propiedad de seguridad que garantiza que las operaciones no se completen de forma inesperada o impredecible. Si un sistema es linealizable, permite a un programador razonar sobre el sistema. ^[2]

La linealizabilidad fue introducida por primera vez como un modelo de consistencia por Herlihy y Wing en 1987. Incluía definiciones más restrictivas de atómico, como "una operación atómica es una que no puede ser (o no es) interrumpida por operaciones concurrentes", que suelen ser vagas en cuanto a cuándo se considera que una operación comienza y termina.

Un objeto atómico puede ser comprendido de manera inmediata y completa a partir de su definición secuencial, como un conjunto de operaciones que se ejecutan en paralelo y que siempre parecen ocurrir una después de la otra; no pueden surgir inconsistencias. En concreto, la linealización garantiza que las invariantes de un sistema sean observadas y preservadas por todas las operaciones: si todas las operaciones individualmente preservan una invariante, el sistema en su conjunto lo hará.

Un sistema concurrente consiste en una colección de procesos que se comunican a través de estructuras de datos u objetos compartidos. La linealización es importante en estos sistemas concurrentes en los que varios procesos pueden acceder a los objetos al mismo tiempo y un programador debe poder razonar sobre los resultados esperados. La ejecución de un sistema concurrente da como resultado un historial , una secuencia ordenada de operaciones completadas.

Un historial es una secuencia de invocaciones y respuestas que un conjunto de subprocesos o procesos realiza de un objeto. Una invocación puede considerarse como el inicio de una operación y la respuesta como el final señalado de esa operación. Cada invocación de una función tendrá una respuesta posterior. Esto se puede utilizar para modelar cualquier uso de un objeto. Supongamos, por ejemplo, que dos subprocesos, A y B, intentan capturar un bloqueo y retroceden si ya lo han capturado. Esto se modelaría como que ambos subprocesos invocan la operación de bloqueo y luego ambos subprocesos reciben una respuesta, una exitosa y otra no.

Una historia secuencial es aquella en la que todas las invocaciones tienen respuestas inmediatas; es decir, se considera que la invocación y la respuesta se producen instantáneamente. Una historia secuencial debería ser trivial de razonar, ya que no tiene una concurrencia real; el ejemplo anterior no era secuencial y, por lo tanto, es difícil de razonar. Aquí es donde entra en juego la linealización.

Una historia es linealizable si existe un orden lineal de las operaciones completadas tal que:${\estilo de visualización \sigma}$

1. Para cada operación completada en , la operación devuelve el mismo resultado en la ejecución que el que devolvería si cada operación se completara una por una en orden .${\estilo de visualización \sigma}$${\estilo de visualización \sigma}$
2. Si una operación op ₁ se completa (obtiene una respuesta) antes de que op ₂ comience (invoque), entonces op ₁ precede a op ₂ en . ^[1]${\estilo de visualización \sigma}$

En otras palabras:

• Sus invocaciones y respuestas pueden reordenarse para producir una historia secuencial;
• que la historia secuencial es correcta según la definición secuencial del objeto;
• Si una respuesta precedió a una invocación en el historial original, aún debe precederla en el reordenamiento secuencial.

Obsérvese que los dos primeros puntos coinciden con la serialización : las operaciones parecen suceder en cierto orden. El último punto es exclusivo de la linealización y, por lo tanto, la principal contribución de Herlihy y Wing. ^[1]

Considere dos formas de reordenar el ejemplo de bloqueo anterior.

Reordenar la invocación de B debajo de la respuesta de A produce un historial secuencial. Es fácil razonar sobre esto, ya que ahora todas las operaciones ocurren en un orden obvio. Sin embargo, no coincide con la definición secuencial del objeto (no coincide con la semántica del programa): A debería haber obtenido el bloqueo con éxito y B debería haber abortado posteriormente.

Esta es otra historia secuencial correcta. También es una linealización ya que coincide con la definición secuencial. Nótese que la definición de linealizabilidad solo impide que se reordenen las respuestas que preceden a las invocaciones; dado que la historia original no tenía respuestas antes de las invocaciones, se pueden reordenar. Por lo tanto, la historia original es, de hecho, linealizable.

Un objeto (a diferencia de una historia) es linealizable si todas las historias válidas de su uso pueden linealizarse. Esta es una afirmación mucho más difícil de demostrar.

Consideremos la siguiente historia, nuevamente de dos objetos interactuando con una cerradura:

Este historial no es válido porque hay un punto en el que tanto A como B mantienen el bloqueo; además, no se puede reordenar a un historial secuencial válido sin violar la regla de ordenación. Por lo tanto, no es linealizable. Sin embargo, en virtud de la serialización, la operación de desbloqueo de B se puede mover antes del bloqueo original de A, que es un historial válido (suponiendo que el objeto comienza el historial en un estado bloqueado):

Este reordenamiento tiene sentido siempre que no haya medios alternativos de comunicación entre A y B. La linealización es mejor cuando se consideran objetos individuales por separado, ya que las restricciones de reordenamiento garantizan que múltiples objetos linealizables sean, considerados como un todo, aún linealizables.

Esta definición de linealizabilidad es equivalente a la siguiente:

• Todas las llamadas de función tienen un punto de linealización en algún instante entre su invocación y su respuesta.
• Todas las funciones parecen ocurrir instantáneamente en su punto de linealización, comportándose según lo especificado por la definición secuencial.

Esta alternativa suele ser mucho más fácil de demostrar. También es mucho más fácil razonar sobre ella como usuario, en gran medida debido a su intuición. Esta propiedad de ocurrir instantáneamente o indivisiblemente conduce al uso del término atómico como alternativa al más largo "linealizable". ^[1]

En los ejemplos siguientes, el punto de linealización del contador creado con la función de comparación e intercambio es el punto de linealización de la primera (y única) actualización de comparación e intercambio exitosa. Se puede considerar que el contador creado con bloqueos se linealiza en cualquier momento mientras se mantienen los bloqueos, ya que se excluye la ejecución de cualquier operación potencialmente conflictiva durante ese período.

Los procesadores tienen instrucciones que se pueden usar para implementar algoritmos de bloqueo , bloqueo libre y espera libre . La capacidad de inhibir temporalmente las interrupciones , asegurando que el proceso que se está ejecutando actualmente no pueda cambiar de contexto , también es suficiente en un monoprocesador . Estas instrucciones son utilizadas directamente por los escritores de compiladores y sistemas operativos, pero también se abstraen y se exponen como códigos de bytes y funciones de biblioteca en lenguajes de nivel superior:

• lectura-escritura atómica;
• intercambio atómico (la instrucción RDLK en algunos mainframes Burroughs y la instrucción XCHG x86 );
• prueba y configuración ;
• buscar y agregar ;
• comparar e intercambiar ;
• enlace de carga/almacenamiento condicional .

La mayoría de los procesadores incluyen operaciones de almacenamiento que no son atómicas con respecto a la memoria. Entre ellas se incluyen operaciones de almacenamiento de múltiples palabras y operaciones de cadenas. Si se produce una interrupción de alta prioridad cuando se completa una parte del almacenamiento, la operación debe completarse cuando se devuelve el nivel de interrupción. La rutina que procesa la interrupción no debe modificar la memoria que se está modificando. Es importante tener esto en cuenta al escribir rutinas de interrupción.

Cuando hay varias instrucciones que deben completarse sin interrupción, se utiliza una instrucción de CPU que deshabilita temporalmente las interrupciones. Esto debe limitarse a solo unas pocas instrucciones y las interrupciones deben volver a habilitarse para evitar un tiempo de respuesta inaceptable a las interrupciones o incluso la pérdida de interrupciones. Este mecanismo no es suficiente en un entorno multiprocesador, ya que cada CPU puede interferir con el proceso independientemente de si se producen interrupciones o no. Además, en presencia de una secuencia de instrucciones , las operaciones ininterrumpidas presentan un riesgo de seguridad, ya que potencialmente pueden encadenarse en un bucle infinito para crear un ataque de denegación de servicio , como en el error de coma de Cyrix .

El estándar C y SUSv3 permiten sig_atomic_trealizar operaciones de lectura y escritura atómicas simples; no se garantiza que el incremento o la disminución sean atómicos. ^[3] Hay operaciones atómicas más complejas disponibles en C11 , que proporciona stdatomic.h. Los compiladores utilizan las características del hardware o métodos más complejos para implementar las operaciones; un ejemplo es libatomic de GCC.

El conjunto de instrucciones ARM proporciona LDREXy STREXinstrucciones que se pueden utilizar para implementar el acceso a la memoria atómica mediante el uso de monitores exclusivos implementados en el procesador para rastrear los accesos a la memoria para una dirección específica. ^[4] Sin embargo, si se produce un cambio de contexto entre las llamadas a LDREXy STREX, la documentación indica que STREXfallará, lo que indica que se debe volver a intentar la operación. En el caso de la arquitectura ARMv8-A de 64 bits, proporciona LDXRy STXRinstrucciones para el tamaño de byte, media palabra, palabra y doble palabra. ^[5]

La forma más sencilla de lograr la linealización es ejecutar grupos de operaciones primitivas en una sección crítica . En sentido estricto, se puede permitir que las operaciones independientes se superpongan cuidadosamente a sus secciones críticas, siempre que esto no viole la linealización. Este enfoque debe equilibrar el costo de una gran cantidad de bloqueos con los beneficios de un mayor paralelismo.

Otro enfoque, preferido por los investigadores (pero que aún no se utiliza ampliamente en la industria del software), es diseñar un objeto linealizable utilizando las primitivas atómicas nativas proporcionadas por el hardware. Esto tiene el potencial de maximizar el paralelismo disponible y minimizar los costos de sincronización, pero requiere pruebas matemáticas que demuestren que los objetos se comportan correctamente.

Un híbrido prometedor de estos dos es proporcionar una abstracción de memoria transaccional . Al igual que con las secciones críticas, el usuario marca el código secuencial que se debe ejecutar de forma aislada de otros subprocesos. Luego, la implementación garantiza que el código se ejecute de forma atómica. Este estilo de abstracción es común cuando se interactúa con bases de datos; por ejemplo, al usar Spring Framework , anotar un método con @Transactional garantizará que todas las interacciones de base de datos incluidas ocurran en una sola transacción de base de datos . La memoria transaccional va un paso más allá, al garantizar que todas las interacciones de memoria ocurran de forma atómica. Al igual que con las transacciones de base de datos, surgen problemas con respecto a la composición de las transacciones, especialmente las transacciones de base de datos y en memoria.

Un tema común al diseñar objetos linealizables es proporcionar una interfaz de todo o nada: o una operación tiene éxito por completo o falla y no hace nada. ( Las bases de datos ACID se refieren a este principio como atomicidad ). Si la operación falla (generalmente debido a operaciones concurrentes), el usuario debe volver a intentarlo, generalmente realizando una operación diferente. Por ejemplo:

• La comparación e intercambio escribe un nuevo valor en una ubicación solo si el contenido de esta coincide con un valor anterior proporcionado. Esto se utiliza comúnmente en una secuencia CAS de lectura y modificación: el usuario lee la ubicación, calcula un nuevo valor para escribir y lo escribe con un CAS (comparación e intercambio); si el valor cambia simultáneamente, el CAS fallará y el usuario lo intentará nuevamente.
• Load-link/store-conditional codifica este patrón de forma más directa: el usuario lee la ubicación con load-link, calcula un nuevo valor para escribir y lo escribe con store-conditional; si el valor ha cambiado simultáneamente, el SC (store-conditional) fallará y el usuario intentará nuevamente.
• En una transacción de base de datos , si la transacción no se puede completar debido a una operación concurrente (por ejemplo, en un bloqueo ), la transacción se cancelará y el usuario deberá intentarlo nuevamente.

Para demostrar el poder y la necesidad de la linealización, consideraremos un contador simple que diferentes procesos pueden incrementar.

Nos gustaría implementar un objeto contador al que puedan acceder varios procesos. Muchos sistemas comunes utilizan contadores para realizar un seguimiento de la cantidad de veces que se produjo un evento.

El objeto contador puede ser accedido por múltiples procesos y tiene dos operaciones disponibles.

1. Incremento: agrega 1 al valor almacenado en el contador y devuelve un acuse de recibo.
2. Leer: devuelve el valor actual almacenado en el contador sin cambiarlo.

Intentaremos implementar este objeto contador utilizando registros compartidos .

Nuestro primer intento que veremos que no es linealizable tiene la siguiente implementación utilizando un registro compartido entre los procesos.

La implementación ingenua y no atómica:

Incremento:

1. Leer el valor en el registro R
2. Añade uno al valor
3. Escribe el nuevo valor nuevamente en el registro R

Leer:

Leer registro R

Esta simple implementación no es linealizable, como lo demuestra el siguiente ejemplo.

Imagine que dos procesos se están ejecutando y acceden al objeto contador único inicializado con el valor 0:

1. El primer proceso lee el valor en el registro como 0.
2. El primer proceso agrega uno al valor, el valor del contador debe ser 1, pero antes de que haya terminado de escribir el nuevo valor en el registro, puede suspenderse, mientras tanto el segundo proceso se está ejecutando:
3. El segundo proceso lee el valor en el registro, que todavía es igual a 0;
4. El segundo proceso añade uno al valor;
5. El segundo proceso escribe el nuevo valor en el registro, el registro ahora tiene el valor 1.

El segundo proceso finaliza su ejecución y el primer proceso continúa desde donde lo dejó:

1. El primer proceso escribe 1 en el registro, sin saber que el otro proceso ya ha actualizado el valor en el registro a 1.

En el ejemplo anterior, dos procesos invocaron un comando de incremento, pero el valor del objeto solo aumentó de 0 a 1, en lugar de 2, como debería haber sido. Una de las operaciones de incremento se perdió debido a que el sistema no era linealizable.

El ejemplo anterior muestra la necesidad de pensar cuidadosamente las implementaciones de estructuras de datos y cómo la linealización puede tener un efecto en la corrección del sistema.

Para implementar un objeto contador linealizable o atómico, modificaremos nuestra implementación anterior para que cada proceso P i use su propio registro R i

Cada proceso incrementa y lee según el siguiente algoritmo:

Incremento:

1. Leer el valor en el registro R i .
2. Añade uno al valor.
3. Escribe el nuevo valor nuevamente en R i

Leer:

1. Leer los registros R 1, R 2, ... R n .
2. Devuelve la suma de todos los registros.

Esta implementación resuelve el problema de nuestra implementación original. En este sistema, las operaciones de incremento se linealizan en el paso de escritura. El punto de linealización de una operación de incremento es cuando esa operación escribe el nuevo valor en su registro R i. Las operaciones de lectura se linealizan hasta un punto en el sistema en el que el valor devuelto por la lectura es igual a la suma de todos los valores almacenados en cada registro R i.

Este es un ejemplo trivial. En un sistema real, las operaciones pueden ser más complejas y los errores introducidos extremadamente sutiles. Por ejemplo, la lectura de un valor de 64 bits de la memoria puede implementarse en realidad como dos lecturas secuenciales de dos posiciones de memoria de 32 bits . Si un proceso solo ha leído los primeros 32 bits y antes de leer los segundos 32 bits se modifica el valor en la memoria, no tendrá ni el valor original ni el nuevo valor, sino un valor mezclado.

Además, el orden específico en que se ejecutan los procesos puede cambiar los resultados, lo que hace que un error de este tipo sea difícil de detectar, reproducir y depurar .

La mayoría de los sistemas proporcionan una instrucción de comparación e intercambio atómico que lee desde una ubicación de memoria, compara el valor con uno "esperado" proporcionado por el usuario y escribe un valor "nuevo" si los dos coinciden, indicando si la actualización se realizó correctamente. Podemos usar esto para corregir el algoritmo de contador no atómico de la siguiente manera:

1. Leer el valor en la ubicación de la memoria;
2. añadir uno al valor;
3. use comparar e intercambiar para volver a escribir el valor incrementado;
4. Vuelva a intentarlo si el valor leído mediante la comparación e intercambio no coincide con el valor que leímos originalmente.

Dado que la comparación y el intercambio ocurren (o parecen ocurrir) instantáneamente, si otro proceso actualiza la ubicación mientras estamos en progreso, se garantiza que la comparación y el intercambio fallarán.

Muchos sistemas proporcionan una instrucción atómica de búsqueda e incremento que lee desde una ubicación de memoria, escribe incondicionalmente un nuevo valor (el valor anterior más uno) y devuelve el valor anterior. Podemos usar esto para corregir el algoritmo de contador no atómico de la siguiente manera:

1. Utilice fetch-and-increment para leer el valor antiguo y volver a escribir el valor incrementado.

El uso de búsqueda e incremento siempre es mejor (requiere menos referencias de memoria) para algunos algoritmos (como el que se muestra aquí) que comparar e intercambiar, ^[6] aunque Herlihy demostró anteriormente que comparar e intercambiar es mejor para ciertos otros algoritmos que no se pueden implementar en absoluto utilizando solo búsqueda e incremento. Por lo tanto, los diseños de CPU con búsqueda e incremento y comparación e intercambio (o instrucciones equivalentes) pueden ser una mejor opción que aquellos con solo uno o el otro. ^[6]

Otro enfoque es convertir el algoritmo ingenuo en una sección crítica , evitando que otros subprocesos lo interrumpan, mediante un bloqueo . Una vez más, se corrige el algoritmo de contador no atómico:

1. Adquirir un bloqueo, excluyendo que otros subprocesos ejecuten la sección crítica (pasos 2 a 4) al mismo tiempo;
2. leer el valor en la ubicación de la memoria;
3. añadir uno al valor;
4. escribe el valor incrementado nuevamente en la ubicación de memoria;
5. liberar el bloqueo.

Esta estrategia funciona como se espera; el bloqueo evita que otros subprocesos actualicen el valor hasta que se libere. Sin embargo, cuando se compara con el uso directo de operaciones atómicas, puede sufrir una sobrecarga significativa debido a la contención del bloqueo. Para mejorar el rendimiento del programa, puede ser una buena idea reemplazar secciones críticas simples con operaciones atómicas para una sincronización sin bloqueo (como acabamos de hacer para el contador con comparación e intercambio y búsqueda e incremento), en lugar de lo contrario, pero desafortunadamente no se garantiza una mejora significativa y los algoritmos sin bloqueo pueden volverse fácilmente demasiado complicados para que valga la pena el esfuerzo.

• Transacción atómica
• Modelo de consistencia
• ÁCIDO
• Lectura-copia-actualización (RCU)
• Leer-modificar-escribir
• Hora de verificación hasta hora de uso

• Herlihy, Maurice P.; Wing, Jeannette M. (1987). "Axiomas para objetos concurrentes". Actas del 14º simposio ACM SIGACT-SIGPLAN sobre Principios de lenguajes de programación - POPL '87. págs. 13–26. doi :10.1145/41625.41627. ISBN 978-0-89791-215-0.S2CID16017451  .​
• Herlihy, Maurice P. (1990). Una metodología para implementar estructuras de datos altamente concurrentes . Vol. 25. págs. 197–206. CiteSeerX  10.1.1.186.6400 . doi :10.1145/99164.99185. ISBN . 978-0-89791-350-8. {{cite book}}: |journal=ignorado ( ayuda )
• Herlihy, Maurice P.; Wing, Jeannette M. (1990). "Linearizabilidad: una condición de corrección para objetos concurrentes". ACM Transactions on Programming Languages ​​and Systems . 12 (3): 463–492. CiteSeerX  10.1.1.142.5315 . doi :10.1145/78969.78972. S2CID  228785.
• Aphyr. "Modelos de consistencia fuerte". aphyr.com . Aphyr . Consultado el 13 de abril de 2018 .