Algoritmo de la panadería de Lamport

El algoritmo de panadería de Lamport es un algoritmo informático ideado por el científico informático Leslie Lamport , como parte de su extenso estudio sobre la corrección formal de los sistemas concurrentes , cuyo objetivo es mejorar la seguridad en el uso de recursos compartidos entre múltiples hilos mediante la exclusión mutua .

En informática , es común que varios hilos accedan simultáneamente a los mismos recursos. La corrupción de datos puede ocurrir si dos o más hilos intentan escribir en la misma ubicación de memoria , o si un hilo lee una ubicación de memoria antes de que otro haya terminado de escribir en ella. El algoritmo de Lamport es uno de los muchos algoritmos de exclusión mutua diseñados para evitar que hilos concurrentes accedan simultáneamente a secciones críticas del código y así eliminar el riesgo de corrupción de datos.

Algoritmo

Analogía

Lamport imaginó una panadería con una máquina numeradora en la entrada, de modo que a cada cliente se le asignara un número único. Los números aumentaban de uno en uno a medida que los clientes entraban a la tienda. Un contador global mostraba el número del cliente que estaba siendo atendido. Los demás clientes debían esperar en una cola hasta que el panadero terminara de atender al cliente actual y se mostrara el siguiente número. Cuando el cliente terminaba de comprar y su número había sido desechado, el dependiente incrementaba el número, permitiendo que el siguiente cliente fuera atendido. Ese cliente debía sacar otro número de la máquina numeradora para volver a comprar.

Según la analogía, los "clientes" son hilos, identificados por la letra i , obtenidos de una variable global .

Es posible que más de un hilo obtenga el mismo número n al solicitarlo; esto es inevitable (sin resolver primero el problema de exclusión mutua, que es el objetivo del algoritmo). Por lo tanto, se asume que el identificador del hilo i también tiene prioridad. Un valor menor de i indica una mayor prioridad, y los hilos con mayor prioridad accederán primero a la sección crítica . Esto equivale a asignar el número de ticket al cliente más antiguo que lo solicite.

Sección crítica

La sección crítica es aquella parte del código que requiere acceso exclusivo a los recursos y que solo puede ser ejecutada por un hilo a la vez. Siguiendo la analogía de la panadería, es cuando el cliente realiza la transacción con el panadero que los demás deben esperar.

Cuando un hilo quiere entrar en la sección crítica, debe comprobar si le corresponde hacerlo. Para ello, debe verificar el número n de todos los demás hilos para asegurarse de tener el menor. En caso de que otro hilo tenga el mismo número, el hilo con el menor valor de i entrará primero en la sección crítica.

En pseudocódigo, esta comparación entre los hilos a y b se puede escribir de la siguiente forma:

// Sea n _a - el número de cliente para el hilo a , y // i _a - el número de hilo para el hilo a , entonces (n _a , i _a ) < (n _b , i _b )

lo cual es equivalente a:

(n _a < n _b ) o ((n _a == n _b ) y (i _a < i _b ))

Una vez que el hilo finaliza su tarea crítica, se deshace de su número y entra en la sección no crítica .

Sección no crítica

La sección no crítica es la parte del código que no necesita acceso exclusivo. Representa cálculos específicos de un hilo que no interfieren con los recursos ni la ejecución de otros hilos.

Esta parte es análoga a las acciones que se realizan después de ir de compras, como guardar el cambio en la cartera.

Implementación del algoritmo

Definiciones

En el artículo original de Lamport, la variable de entrada se conoce como elección , y se aplican las siguientes condiciones:

Las palabras que eligen [i] y el número [i] están en la memoria del proceso i, y son inicialmente cero.
El rango de valores del número [i] es ilimitado.
Un proceso puede fallar en cualquier momento. Suponemos que, al fallar, pasa inmediatamente a su sección no crítica y se detiene. Posteriormente, puede haber un período durante el cual la lectura de su memoria arroje valores arbitrarios. Finalmente, cualquier lectura de su memoria debe dar como resultado un valor de cero.

Ejemplos de código

Pseudocódigo

En este ejemplo, todos los hilos ejecutan la misma función principal, Thread . En aplicaciones reales, los distintos hilos suelen tener funciones principales diferentes.

Cabe destacar que, al igual que en el artículo original, el hilo se autoevalúa antes de entrar en la sección crítica. Dado que las condiciones del bucle se evaluarán como falsas , esto no provoca mucha demora.

// Declaración y valores iniciales de las variables globalesEntrando : array [ 1. . NUM_THREADS ] de bool = { false };Número : matriz [ 1. . NUM_THREADS ] de entero = { 0 };bloquear ( entero i ) {Ingresando [ i ] = verdadero ;Número [ i ] = 1 + max ( Número [ 1 ], ..., Número [ NUM_THREADS ]);Ingresando [ i ] = falso ;para ( entero j = 1 ; j <= NUM_THREADS ; j ++ ) {// Esperar hasta que el hilo j reciba su número:mientras ( Entrando [ j ]) { /* nada */ }// Esperar hasta que todos los hilos con números más pequeños o con el mismo// número, pero con mayor prioridad, terminan su trabajo:mientras (( Número [ j ] != 0 ) && (( Número [ j ], j ) < ( Número [ i ], i ))) { /* nada */ }}}desbloquear ( entero i ) {Número [ i ] = 0 ;}Hilo ( entero i ) {mientras ( verdadero ) {bloquear ( i );// La sección crítica va aquí...desbloquear ( i );// sección no crítica...}}

Cada hilo solo escribe en su propio almacenamiento; solo se comparten las lecturas. Es notable que este algoritmo no se base en alguna operación atómica de nivel inferior, como por ejemplo, comparar e intercambiar . La demostración original muestra que, para lecturas y escrituras superpuestas en la misma celda de almacenamiento, solo la escritura debe ser correcta. La operación de lectura puede devolver un número arbitrario. Por lo tanto, este algoritmo puede utilizarse para implementar la exclusión mutua en memoria que carece de primitivas de sincronización, como por ejemplo, un disco SCSI simple compartido entre dos ordenadores.

La necesidad de la variable Entering puede no ser obvia ya que no hay ningún "bloqueo" alrededor de las líneas 7 a 13. Sin embargo, supongamos que la variable se eliminó y dos procesos calcularon el mismo Number[i]. Si el proceso de mayor prioridad fue interrumpido antes de establecer Number[i], el proceso de baja prioridad verá que el otro proceso tiene un número de cero y entra en la sección crítica; más tarde, el proceso de alta prioridad ignorará la igualdad Number[i]para los procesos de menor prioridad y también entra en la sección crítica. Como resultado, dos procesos pueden entrar en la sección crítica al mismo tiempo. El algoritmo de la panadería usa la variable Entering para hacer que la asignación en la línea 6 parezca atómica; el proceso i nunca verá un número igual a cero para un proceso j que va a elegir el mismo número que i .

Al implementar el pseudocódigo en un sistema de un solo proceso o bajo multitarea cooperativa , es mejor reemplazar las secciones que "no hacen nada" con código que notifique al sistema operativo que cambie inmediatamente al siguiente hilo. Esta primitiva se suele denominar yield.

El algoritmo de panadería de Lamport presupone un modelo de memoria de consistencia secuencial . Pocos lenguajes modernos o procesadores multinúcleo implementan un modelo de memoria de este tipo. Por lo tanto, la implementación correcta del algoritmo generalmente requiere la inserción de barreras para evitar la reordenación. ^{[ 1 ]}

Código PlusCal

Declaramos que N es el número de procesos y asumimos que N es un número natural .

CONSTANTE N SUPONGAMOS que N \in Nat

Definimos P como el conjunto {1, 2, ... , N} de procesos.

P == 1..N

Las variables num y flag se declaran como globales.

--algoritmo AtomicBakery { variable num = [i \in P |-> 0], flag = [i \in P |-> FALSE];

Lo siguiente se define LL(j, i)como verdadero si y solo si <<num[j], j>> es menor o igual que <<num[i], i>> en el orden lexicográfico habitual .

define { LL(j, i) == \/ num[j] < num[i] \/ /\ num[i] = num[j] /\ j =< i }

Para cada elemento en P hay un proceso con variables locales unread, max y nxt. Los pasos entre etiquetas consecutivas p1, ..., p7, cs se consideran atómicos. La instrucción establece id a un elemento elegido de forma no determinista del conjunto S y luego ejecuta body. Un paso que contiene la instrucción await expr solo se puede ejecutar cuando el valor de expr es TRUE .(x \in S) { body }

proceso (p ∈ P) variables no leídas en el subconjunto P, máximo en Nat, nxt \in P; { p1: mientras (VERDADERO) { no leído := P \ {self} ; máximo := 0; flag[self] := VERDADERO; p2: mientras (sin leer # {}) { con (i \in no leído) { no leído := no leído \ {i}; if (num[i] > max) { max := num[i]; } } }; p3: num[self] := max + 1; p4: flag[self] := FALSE; no leído := P \ {self} ; p5: mientras (sin leer # {}) { con (i \in no leído) { nxt := i ; }; esperar ~ flag[nxt]; p6: esperar \/ num[nxt] = 0 \/ LL(self, nxt) ; no leído := no leído \ {nxt}; } ; cs: omitir ; \* la sección crítica; p7: num[self] := 0; }} }

Código Java

Utilizamos la clase AtomicIntegerArray no por sus operaciones atómicas integradas, sino porque sus métodos get y set funcionan como lecturas y escrituras volátiles. Según el modelo de memoria de Java, esto garantiza que las escrituras sean visibles de inmediato para todos los subprocesos.

AtomicIntegerArray ticket = new AtomicIntegerArray ( threads ); // ticket para los hilos en la línea, n - número de hilos// Java inicializa cada elemento de 'ticket' a 0.AtomicIntegerArray entrando = new AtomicIntegerArray ( hilos ); // 1 cuando el hilo entra en la línea// Java inicializa cada elemento de 'entering' a 0.public void lock ( int pid ) // ID del hilo{entrando . set ( pid , 1 );entero máximo = 0 ;para ( int i = 0 ; i < threads ; i ++ ){int actual = ticket.get ( i ) ;si ( actual > máximo ){máximo = actual ;}}ticket.set ( pid , 1 + max ) ;entrando . set ( pid , 0 );para ( int i = 0 ; i < ticket . length (); ++ i ){si ( i != pid ){while ( entrando.get ( i ) == 1 ) { Thread.yield ( ); } // esperar mientras otro hilo elige un ticketmientras ( ticket . get ( i ) != 0 && ( ticket . get ( i ) < ticket . get ( pid ) ||( ticket . get ( i ) == ticket . get ( pid ) && i < pid ))){ Hilo.yield ( ) ; }}}// La sección crítica va aquí...}público void desbloquear ( int pid ){ticket.set ( pid , 0 ) ;}