¿Qué es "linealizabilidad"?

Question

¿Alguien puede ayudarme a entender qué es Linearizability? Necesito una explicación que sea simple y fácil de entender. Estoy leyendo The Art of Multiprocessor Programming por Maruice Herilihy y Nir Shavit y estoy tratando de entender el Capítulo 3 sobre Objetos concurrentes.

Entiendo que un método es Lineizable si tiene un punto donde parece "tener efecto" instantáneamente desde el punto de vista de los otros hilos. Eso tiene sentido, pero también se dice que Linearizability es en realidad una propiedad del historial de ejecución. ¿Qué significa que un historial de ejecución sea linealizable, por qué me importa y cómo se relaciona con un método u objeto linealizable?

¡Gracias!

Answer 1

Un objeto solo se considera linealizable si

(a) cada uno de sus métodos es atómica. Imagínelos como métodos sincronizados de Java, pero más abajo.

(b) no puede haber como máximo una operación pendiente de un hilo/procesador determinado.

(c) las operaciones deben tener efecto antes de que regresen. No es aceptable que el objeto los ponga en cola para realizarlos perezosamente.

Ahora, (a) se puede aflojar mucho más. La linealizabilidad requiere que el efecto de esa operación sea atómico. Por lo tanto, una operación de adición en una lista vinculada sin bloqueo tendrá un punto en su ejecución (un "punto de linealización") antes de que ese elemento no se agregue, y después de lo cual el elemento está definitivamente adentro. Esto es mejor que obtener bloqueos , porque los bloqueos pueden bloquearse indefinidamente.

Ahora, cuando varios hilos llaman simultáneamente a un objeto linealizable, el objeto se comporta como si los métodos se llamaran en una secuencia lineal (debido al requisito de atomicidad); dos llamadas superpuestas podrían hacerse lineales en algún orden arbitrario.

Y debido a que se ven obligados a tener algún efecto durante la invocación del método (las pilas deben presionar/abrir, los conjuntos deben agregar/eliminar etc.), el objeto puede razonarse con métodos de especificación secuencial bien conocidos (pre y condiciones de publicación, etc.).

Mientras estamos en ello, la diferencia entre linearizabilidad y consistencia secuencial es que la última no requiere (c). Para un almacén de datos secuencialmente consistente, un método no tiene que tener un efecto de inmediato. En otras palabras, una invocación a un método es simplemente una solicitud de acción, pero no la acción en sí misma. En un objeto linealizable, una invocación de método es una llamada a la acción. Un objeto linealizable es secuencialmente consistente, pero no al revés.

Answer 2

Quizás una confusión entre Linearizability versus Serializability.

De this article (P. Bailis):

instrucción atómica es una garantía acerca de las operaciones individuales sobre objetos individuales [...] instrucción atómica para la lectura y escritura es sinónimo del término “consistencia atómica” y es la “C” o "consistencia", en la prueba de Gilbert y Lynch del Teorema CAP.

Serializabilidad es una garantía sobre transacciones, o grupos de una o más operaciones sobre uno o más objetos.Garantiza que la ejecución de un conjunto de transacciones (generalmente con operaciones de lectura y escritura) sobre múltiples elementos es equivalente a una ejecución en serie (ordenamiento total) de las transacciones [...] La serialización es el "yo" tradicional, o aislamiento, en ACID.

Answer 3

Bueno, creo que puedo responder esta pregunta de manera concisa.

Cuando vamos a decir si un objeto simultáneo es correcto, siempre tratamos de encontrar la manera de extender el orden parcial a un orden total.

podemos reconocer si un objeto secuencial es correcto mucho más fácilmente.

Primero, pongamos el objeto concurrente a un lado. Lo discutiremos más tarde. Ahora consideremos un historial secuencial H_S, un historial secuencial es una secuencia de eventos (es decir, Invocaciones y Respuestas) de la cual cada Invocación es seguida instantáneamente por su Respuesta correspondiente. (De acuerdo, "instantáneamente" podría confundirse, considere la ejecución de un programa de un único subproceso, por supuesto, hay un intervalo entre cada invocación y su respuesta, pero los métodos se ejecutan uno por uno. Por lo tanto, "instantáneamente" significa que ningún otro invocación/respuesta puede pegarse en un par de Invoke_i ~ Response_i)

el H_S puede parece:

H_S : I1 R1 I2 R2 I3 R3 ... In Rn 
(Ii means the i-th Invoke, and Ri means the i-th Response) 

será muy fácil de razonar acerca de la exactitud de la historia H_S, beca usar allí no es concurrencia, lo que tenemos que hacer es verificar si la ejecución funciona tan bien como lo esperamos (cumplir con las condiciones de la especificación secuencial). En otras palabras, es un legel historial secuencial.

Ok, la realidad es que estamos trabajando con un programa concurrente. Por ejemplo, ejecutamos dos hilos A y B en nuestro programa. Cada vez que ejecutamos el programa, obtendremos un historial de H_C (History_Concurrent) de la expulsión. Necesitamos considerar una llamada a método como Ii ~ Ri como en H_S. Por supuesto, debe haber muchas superposiciones entre llamadas de método llamadas por el subproceso A y el subproceso B. Pero cada evento (es decir, Invocaciones y Respuestas) tiene su orden en tiempo real. Por lo que los invoca y respuesta de todos los métodos llamados por A y B se pueden asignar a un orden secuencial, el orden puede verse como:

H_C : IA1 IB1 RA1 RB1 IB2 IA2 RB2 RA2 

El orden parece estar confundido, es justo el tipo de los acontecimientos de cada método llama:

thread A:   IA1----------RA1    IA2-----------RA2 
thread B:   |  IB1---|---RB1 IB2----|----RB2  | 
        |  | | |  |  |  |  | 
        |  | | |  |  |  |  | 
real-time order: IA1  IB1 RA1 RB1 IB2 IA2 RB2  RA2 
       ------------------------------------------------------>time 

Y tenemos el H_C. Entonces, ¿cómo podríamos verificar si la ejecución de H_C es correcta? Podemos reordenar la H_C a un H_RO siguiendo la regla:

REGLA:Si un método llamado m1 m2 precede a otro, entonces el mosto m1 m2 precede en la secuencia reordenada. (Significa que si Ri está delante de Ij en el H_C, debe garantizar que Ri todavía está delante de Ij en la secuencia reordenada, i y j no tienen sus órdenes, también podemos usar a, b, c ...) Decimos que H_C es equivalente a H_RO (history_reorder) bajo dicha regla.

El H_RO tendrá 2 propiedades:

1. Se respeta el orden del programa.
2. Conserva el comportamiento en tiempo real.

Reordenar la H_C sin violar la regla anterior, podemos obtener algunas historias secuenciales (que son equivalentes a H_C), por ejemplo:

H_S1: IA1 RA1 IB1 RB1 IB2 RB2 IA2 RA2 
H_S2: IB1 RB1 IA1 RA1 IB2 RB2 IA2 RA2 
H_S3: IB1 RB1 IA1 RA1 IA2 RA2 IB2 RB2 
H_S4: IA1 RA1 IB1 RB1 IA2 RA2 IB2 RB2 

Sin embargo, no podemos obtener una H_S5:

H_S5: IA1 RA1 IA2 RA2 IB1 RB1 IB2 RB2 

porque IB1 ~ RB1 precede por completo a IA2 ~ RA2 en el H_C, no se puede reordenar.

Ahora, con estas historias secuenciales, ¿cómo podríamos confirmar si nuestra ejecución historia H_C es correcta? (Resalto la historia H_C, significa que nosotros sólo se preocupan por la corrección de la historia H_C ahora en lugar de la corrección de el programa concurrente)

la respuesta es sencilla, si al menos una de las historias secuenciales es correcta (una historia legal secuencial cumple con las condiciones de la especificación secuencial), entonces la historia H_C es linealizable, nos llaman el H_S legal linealización del H_C. Y H_C es una ejecución correcta. En otras palabras, es una ejecución legal que esperábamos. Si tiene experiencia en programación simultánea, debe haber escrito dicho programa que a veces parece bastante bien, pero a veces puede ser totalmente erróneo.

Ahora hemos sabido lo que es un historia linealizable de la ejecución de un programa concurrente. Entonces, ¿qué pasa con el programa concurrente en sí?

---

La idea básica detrás de instrucción atómica es que cada historia concurrente es equivalente, en el sentido siguiente, a una cierta historia secuencial. [El arte de la programación de multiprocesador 3.6.1: instrucción atómica] ("siguiente sentido" es la regla de reordenación he hablado más arriba)

Ok, la referencia puede ser un poco confuso. Significa que, si cada historia concurrente tiene una linealización (historia secuencial legal equivalente a ella), el programa concurrente cumple las condiciones de linealidad.

Ahora, hemos entendido lo que es Linearizability. Si decimos que nuestro programa concurrente es linealizable, en otras palabras, tiene la propiedad de linealidad. Significa que cada vez que lo ejecutamos, la historia es linealizable (el historial es lo que esperamos).

Por lo tanto es obvio que instrucción atómica es un de seguridad (corrección) propiedad.

---

Sin embargo, el método de la reordenación de todas las historias concurrentes a la historia secuencial para juzgar si un programa es linealizable sólo es posible en prinple. En la práctica, nos enfrentamos a miles de llamadas a métodos llamadas por subprocesos de dos dígitos.No podemos reordenar todas las historias de ellos. Ni siquiera podemos enumerar todas las historias concurrentes de un programa de trival.

La manera habitual de mostrar que una implementación de objeto concurrente es linealizable es identificar para cada método de un punto donde el efecto método TAKS linealización. [El Arte de Programar multiprocesador 3.5.1: puntos de linealización]

vamos a discutir sobre la cuestión en las condiciones de "objeto concurrente". Es sustancialmente igual que arriba. Una implementación de un objeto simultáneo tiene algunos métodos para acceder a los datos del objeto simultáneo. Y los multihilos compartirán un objeto concurrente. Por lo tanto, cuando acceden al objeto al mismo tiempo llamando a los métodos del objeto, el implementador del objeto concurrente debe garantizar la corrección de las llamadas al método simultáneo.

Identificará para cada método un punto de linealización. Lo más importante es comprender el significado del punto de linealización. La afirmación de "donde el método hace efecto" es realmente difícil de entender. Tengo algunos ejemplos:

primer lugar, vamos a ver un caso incorrecto:

//int i = 0; i is a global shared variable. 
int inc_counter() { 
    int j = i++; 
    return j; 
} 

Es bastante fácil de detectar el error. Podemos traducir i ++ en:

#Pseudo-asm-code 
Load register, address of i 
Add register, 1 
Store register, address of i 

De modo que dos hilos pueden ejecutar uno "i ++;" concurrentemente y el resultado de i parece ser aumentado solo una vez. pudimos conseguir una H_C tales:

thread A:   IA1----------RA1(1)     IA2------------RA2(3) 
thread B:   |  IB1---|------RB1(1) IB2----|----RB2(2) | 
        |  | |  |  |  |  |  | 
        |  | |  |  |  |  |  | 
real-time order: IA1  IB1 RA1(1) RB1(1) IB2 IA2 RB2(2) RA2(3) 
       ---------------------------------------------------------->time 

Lo que intenta reordenar el orden de tiempo real, no se debe encontrar una historia secuencial Legel que equivale a H_C.

Nos debe reescribir el programa:

//int i = 0; i is a global shared variable. 
int inc_counter(){ 
    //do some unrelated work, for example, play a popular song. 
    lock(&lock); 
    i++; 
    int j = i; 
    unlock(&lock); 
    //do some unrelated work, for example, fetch a web page and print it to the screen. 
    return j; 
} 

bien, ¿cuál es el punto de linealización inc_counter()? La respuesta es toda la sección crítica. Porque cuando muchos hilos llaman repetidamente a inc_counter(), la sección crítica se ejecutará atómicamente. Y puede garantizar la exactitud del método. La respuesta del método es el valor incrementado de i global. Considere la H_C como:

thread A:   IA1----------RA1(2)     IA2-----------RA2(4) 
thread B:   |  IB1---|-------RB1(1) IB2--|----RB2(3) | 
        |  | |  |   | |  |  | 
        |  | |  |   | |  |  | 
real-time order: IA1  IB1 RA1(2) RB1(1)  IB2 IA2 RB2(3) RA2(4) 

Obviamente, la historia secuencial equivalente es legal:

IB1 RB1(1) IA1 RA1(2) IB2 RB2(3) IA2 RA2(4) //a legal sequential history 

Tenemos reordenar la IB1 ~ ~ RB1 y IA1 RA1, porque se solapaban en el orden tiempo real , se pueden reordenar ambiguamente. En el caso de H_C, podemos razonar que la sección crítica de IB1 ~ RB1 se ingresa primero.

El ejemplo es demasiado simple. Vamos a considerar otro:

//top is the tio 
void push(T val) { 
    while (1) { 
     Node * new_element = allocte(val); 
     Node * next = top->next; 
     new_element->next = next; 
     if (CAS(&top->next, next, new_element)) { //Linearization point1 
      //CAS success! 
      //ok, we can do some other work, such as go shopping. 
      return; 
     } 
     //CAS fail! retry! 
    } 
} 

T pop() { 
    while (1) { 
     Node * next = top->next; 
     Node * nextnext = next->next; 
     if (CAS(&top->next, next, nextnext)) { //Linearization point2 
      //CAS succeed! 
      //ok, let me take a rest. 
      return next->value; 
     } 
     //CAS fail! retry! 
    } 
} 

Es un algoritmo de pila sin bloqueo lleno de errores! pero no cuides los detalles. Solo quiero mostrar el punto de linealización de push() y pop().Los he mostrado en los comentarios. Considere que muchos hilos llaman repetidamente a push() y pop(), se ordenarán en el paso CAS. Y otros pasos parecen no tener importancia porque cualquiera que sea que se ejecuten simultáneamente, el efecto final que tomarán en la pila (precisamente la variable superior) se debe al orden del paso CAS (punto de linealización). Si podemos asegurarnos de que el punto de linealización realmente funciona, entonces la pila concurrente es correcta. La imagen del H_C es demasiado larga, pero podemos confirmar que debe haber un equivalente secuencial legal a H_C.

---

Entonces, si está implementando un objeto simultáneo, ¿cómo decir la exactitud de su programa? Debe identificar cada método de puntos de linealización y pensar cuidadosamente (o incluso probar) que siempre tendrán las invariantes del objeto concurrente. Entonces, el orden parcial de todas las llamadas a métodos se puede extender a, al menos, un orden total legal (historial secuencial de eventos) que cumpla con la especificación secuencial del objeto concurrente.

Entonces puede decir que su objeto simultáneo es el correcto.