En programación concurrente , una operación (o conjunto de operaciones) es linealizable si consta de una lista ordenada de eventos de invocación y respuesta , que puede ampliarse agregando eventos de respuesta tales como:
Informalmente, esto significa que la lista de eventos no modificada es linealizable si y sólo 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 solo objeto, puede surgir una situación en la que mientras un proceso accede al objeto, otro proceso cambia su contenido. Hacer un sistema 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 fuerte condición de corrección, que limita qué salidas son posibles cuando varios procesos acceden a un objeto al mismo tiempo. Es una propiedad de seguridad que garantiza que las operaciones no se completen de forma inesperada o impredecible. Si un sistema es linealizable, permite al programador razonar sobre el sistema. [2]
La linealizabilidad fue introducida por primera vez como un modelo de consistencia por Herlihy y Wing en 1987. Abarcaba definiciones más restrictivas de atómico, como "una operación atómica es aquella que no puede ser (o no es) interrumpida por operaciones concurrentes", que generalmente son vagas al respecto. cuando se considera que una operación comienza y termina.
Un objeto atómico puede entenderse inmediata y completamente a partir de su definición secuencial, como un conjunto de operaciones ejecutadas en paralelo que siempre parecen ocurrir una tras otra; no pueden surgir inconsistencias. Específicamente, la linealización garantiza que las invariantes de un sistema sean observadas y preservadas por todas las operaciones: si todas las operaciones preservan individualmente una invariante, el sistema en su conjunto lo hará.
Un sistema concurrente consta de una colección de procesos que se comunican a través de estructuras u objetos de datos compartidos. La linealización es importante en estos sistemas concurrentes donde múltiples procesos pueden acceder a los objetos al mismo tiempo y un programador debe poder razonar sobre los resultados esperados. Una ejecución de un sistema concurrente da como resultado un historial , una secuencia ordenada de operaciones completadas.
Una historia es una secuencia de invocaciones y respuestas realizadas a un objeto por un conjunto de hilos o procesos. Se puede considerar una invocación 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 hilos, A y B, intentan agarrar un candado y retroceden si ya está tomado. Esto se modelaría como si ambos subprocesos invocaran la operación de bloqueo y luego ambos subprocesos recibieran una respuesta, uno exitoso y el otro 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 tienen lugar instantáneamente. Debería ser trivial razonar sobre una historia secuencial, ya que no tiene una concurrencia real; el ejemplo anterior no fue secuencial y, por lo tanto, es difícil razonar sobre él. Aquí es donde entra en juego la linealización.
Una historia es linealizable si existe un orden lineal de las operaciones completadas tal que:
En otras palabras:
(Tenga en cuenta que los dos primeros puntos aquí coinciden con la serialización : las operaciones parecen ocurrir en algún orden. Es el último punto que es exclusivo de la linealización y, por lo tanto, es la principal contribución de Herlihy y Wing) .
Veamos dos formas de reordenar el ejemplo de bloqueo anterior.
Reordenar la invocación de B debajo de la respuesta de A produce una historia secuencial. Es fácil razonar sobre esto, ya que ahora todas las operaciones ocurren en un orden obvio. Desafortunadamente, no coincide con la definición secuencial del objeto (no coincide con la semántica del programa): A debería haber obtenido con éxito el bloqueo y B debería haber abortado posteriormente.
Esta es otra historia secuencial correcta. ¡También es una linealización! Tenga en cuenta que la definición de linealización solo impide que se reordenen las respuestas que preceden a las invocaciones; dado que la historia original no tuvo respuestas antes de las invocaciones, podemos reordenarla como queramos. Por tanto, la historia original es realmente linealizable.
Un objeto (a diferencia de una historia) es linealizable si todas las historias válidas de su uso pueden ser linealizadas. Tenga en cuenta que esta es una afirmación mucho más difícil de probar.
Considere la siguiente historia, nuevamente de dos objetos que interactúan con una cerradura:
Esta historia no es válida porque hay un punto en el que tanto A como B mantienen el candado; además, no se puede reordenar según un historial secuencial válido sin violar la regla de ordenamiento. Por tanto, no es linealizable. Sin embargo, bajo serialización, la operación de desbloqueo de B se puede mover antes del bloqueo original de A, que es un historial válido (asumiendo que el objeto comienza el historial en un estado bloqueado):
Esta reordenación es sensata siempre que no exista un medio alternativo de comunicación entre A y B. La linealización es mejor cuando se consideran objetos individuales por separado, ya que las restricciones de reordenación garantizan que múltiples objetos linealizables, considerados en su conjunto, sigan siendo linealizables.
Esta definición de linealización es equivalente a lo siguiente:
Esta alternativa suele ser mucho más fácil de probar. También es mucho más fácil razonar como usuario, en gran parte debido a su intuición. Esta propiedad de ocurrir de forma instantánea o indivisible lleva 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 en comparación e intercambio es el punto de linealización de la primera (y única) actualización exitosa de comparación e intercambio. Se puede considerar que el contador construido mediante bloqueo se linealiza en cualquier momento mientras se mantienen los bloqueos, ya que cualquier operación potencialmente conflictiva queda excluida de la ejecución durante ese período.
Los procesadores tienen instrucciones que se pueden utilizar para implementar algoritmos de bloqueo y sin bloqueo y sin espera . La capacidad de inhibir temporalmente las interrupciones , asegurando que el proceso actualmente en ejecución no pueda cambiar de contexto , también es suficiente en un monoprocesador . Estas instrucciones son utilizadas directamente por compiladores y escritores de sistemas operativos, pero también se resumen y exponen como códigos de bytes y funciones de biblioteca en lenguajes de nivel superior:
La mayoría de los procesadores incluyen operaciones de almacenamiento que no son atómicas con respecto a la memoria. Estos incluyen almacenes de varias palabras y operaciones de cadenas. Si ocurre 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á cambiando. 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 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 canalización 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 proporcionan sig_atomic_tlecturas y escrituras 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 características de hardware o métodos más complejos para implementar las operaciones; un ejemplo es libatómico de GCC.
El conjunto de instrucciones ARM proporciona LDREXinstrucciones STREXque 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 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 LDXRinstrucciones STXRpara tamaños de bytes, 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 . Estrictamente, entonces se puede permitir cuidadosamente que las operaciones independientes se superpongan a sus secciones críticas, siempre que esto no viole la linealización. Este enfoque debe equilibrar el costo de un gran número de cerraduras con los beneficios de un mayor paralelismo.
Otro enfoque, favorecido por los investigadores (pero aún no ampliamente utilizado 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 código secuencial que debe ejecutarse 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 al interactuar con bases de datos; por ejemplo, cuando se utiliza Spring Framework , anotar un método con @Transactional garantizará que todas las interacciones de la base de datos adjunta se produzcan en una sola transacción de base de datos . La memoria transaccional va un paso más allá y garantiza que todas las interacciones de la memoria se produzcan de forma atómica. Al igual que con las transacciones de bases de datos, surgen problemas con respecto a la composición de las transacciones, especialmente las transacciones de bases 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:
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 múltiples procesos. Muchos sistemas comunes utilizan contadores para realizar un seguimiento del número de veces que ha ocurrido un evento.
Múltiples procesos pueden acceder al objeto contador y tiene dos operaciones disponibles.
Intentaremos implementar este objeto contador utilizando registros compartidos .
Nuestro primer intento, que veremos no linealizable, tiene la siguiente implementación utilizando un registro compartido entre los procesos.
La implementación ingenua y no atómica:
Incremento:
Leer:
Leer registro R
Esta implementación simple no es linealizable, como lo demuestra el siguiente ejemplo.
Imagine que se están ejecutando dos procesos que acceden al único objeto de contador inicializado para tener el valor 0:
El segundo proceso finaliza su ejecución y el primer proceso continúa ejecutándose desde donde lo dejó:
En el ejemplo anterior, dos procesos invocaron un comando de incremento, sin embargo, el valor del objeto solo aumentó de 0 a 1, en lugar de 2 como debería haberlo hecho. Una de las operaciones de incremento se perdió debido a que el sistema no era linealizable.
El ejemplo anterior muestra la necesidad de pensar detenidamente en 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:
Leer:
Esta implementación resuelve el problema con nuestra implementación original. En este sistema las operaciones incrementales se linealizan en el paso de escritura. El punto de linealización de una operación incremental 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 cuando el valor devuelto por la lectura es igual a la suma de todos los valores almacenados en cada registro R i.
Éste 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 en realidad puede implementarse como dos lecturas secuenciales de dos ubicaciones 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 cambia 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 el que se ejecutan los procesos puede cambiar los resultados, lo que hace que dicho error sea difícil de detectar, reproducir y depurar .
La mayoría de los sistemas proporcionan una instrucción atómica de comparación e intercambio 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 arreglar el algoritmo del contador no atómico de la siguiente manera:
Dado que la comparación e intercambio ocurre (o parece ocurrir) instantáneamente, si otro proceso actualiza la ubicación mientras estamos en progreso, se garantiza que la comparación e intercambio fallará.
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 arreglar el algoritmo del contador no atómico de la siguiente manera:
Usar buscar e incrementar siempre es mejor (requiere menos referencias de memoria) para algunos algoritmos, como el que se muestra aquí, que comparar e intercambiar, [6] a pesar de que Herlihy demostró anteriormente que comparar e intercambiar es mejor para ciertos otros algoritmos que no se pueden implementar en absoluto usando solo buscar e incrementar. 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 una u otra. [6]
Otro enfoque es convertir el algoritmo ingenuo en una sección crítica , evitando que otros subprocesos la interrumpan, mediante un bloqueo . Una vez más arreglando el algoritmo del contador no atómico:
Esta estrategia funciona como se esperaba; el bloqueo evita que otros subprocesos actualicen el valor hasta que se libere. Sin embargo, en comparación con el uso directo de operaciones atómicas, puede sufrir una sobrecarga significativa debido a la contención de bloqueos. Por lo tanto, para mejorar el rendimiento del programa, puede ser una buena idea reemplazar secciones críticas simples con operaciones atómicas para sincronización sin bloqueo (como acabamos de hacer para el contador con comparar e intercambiar y buscar e incrementar), en lugar de al revés, pero desafortunadamente no se garantiza una mejora significativa y los algoritmos sin bloqueo pueden volverse demasiado complicados para que valga la pena el esfuerzo.
{{cite book}}: |journal=ignorado ( ayuda )