linealizabilidad
En la 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 ( devoluciones de llamada ), que puede extenderse agregando eventos de respuesta tales que:
De manera informal, esto significa que la lista de eventos sin modificar es linealizable si y solo si sus invocaciones fueran 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 linealizabilidad es una fuerte condición de corrección, que restringe qué salidas son posibles cuando múltiples procesos acceden a un objeto al mismo tiempo. Es una propiedad de seguridad que garantiza que las operaciones no se completen de manera inesperada o impredecible. Si un sistema es linealizable, permite a un programador razonar sobre el sistema. [2]
Herlihy y Wing introdujeron por primera vez la linealizabilidad como un modelo de consistencia 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 acerca de 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 paralelas que siempre parecen ocurrir una después de la otra; no pueden surgir inconsistencias. Específicamente, la linealizabilidad 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 como un todo 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 linealizabilidad es importante en estos sistemas simultáneos donde múltiples 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.
