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 largo estudio sobre la corrección formal de los sistemas concurrentes , que pretende mejorar la seguridad en el uso de recursos compartidos entre múltiples hilos mediante exclusión mutua .
En informática , es habitual que varios subprocesos accedan simultáneamente a los mismos recursos. La corrupción de datos puede ocurrir si dos o más subprocesos intentan escribir en la misma ubicación de memoria , o si un subproceso lee una ubicación de memoria antes de que otro haya terminado de escribir en ella. El algoritmo de panadería de Lamport es uno de los muchos algoritmos de exclusión mutua diseñados para evitar que subprocesos concurrentes ingresen a secciones críticas del código al mismo tiempo para eliminar el riesgo de corrupción de datos.
Lamport imaginó una panadería con una máquina de numeración en la entrada, de modo que cada cliente recibe un número único. Los números aumentan de uno en uno a medida que los clientes entran en la tienda. Un contador global muestra el número del cliente que está siendo atendido en ese momento. Todos los demás clientes deben esperar en una cola hasta que el panadero termine de atender al cliente actual y se muestre el siguiente número. Cuando el cliente termina de comprar y se deshace de su número, el empleado incrementa el número, lo que permite atender al siguiente cliente. Ese cliente debe sacar otro número de la máquina de numeración para poder comprar nuevamente.
Según la analogía, los "clientes" son hilos, identificados por la letra i , obtenidos de una variable global.
Debido a las limitaciones de la arquitectura informática, algunas partes de la analogía de Lamport necesitan una ligera modificación. Es posible que más de un subproceso obtenga el mismo número n cuando lo soliciten; esto no se puede evitar (sin resolver primero el problema de exclusión mutua, que es el objetivo del algoritmo). Por lo tanto, se supone que el identificador de subproceso i también es una prioridad. Un valor menor de i significa una prioridad más alta y los subprocesos con mayor prioridad ingresarán primero a la sección crítica .
La sección crítica es la parte del código que requiere acceso exclusivo a los recursos y que solo puede ser ejecutada por un hilo a la vez. En la analogía de la panadería, es cuando el cliente negocia con el panadero que los demás deben esperar.
Cuando un hilo quiere entrar en la sección crítica, debe comprobar si ahora es su turno para hacerlo. Debe comprobar el número n de todos los demás hilos para asegurarse de que tiene el más pequeño. En caso de que otro hilo tenga el mismo número, el hilo con el i más pequeño entrará primero en la sección crítica.
En pseudocódigo, esta comparación entre los hilos a y b se puede escribir en la 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 )
que es equivalente a:
(n a < n b ) o ((n a == n b ) y (i a < i b ))
Una vez que el hilo termina su trabajo crítico, se deshace de su número y entra en la sección no crítica .
La sección no crítica es la parte del código que no necesita acceso exclusivo. Representa algún cálculo específico del subproceso que no interfiere con los recursos y la ejecución de otros subprocesos.
Esta parte es análoga a las acciones que ocurren después de comprar, como devolver el cambio a la billetera.
En el artículo original de Lamport, la variable entrante se conoce como choosing y se aplican las siguientes condiciones:
En este ejemplo, todos los subprocesos ejecutan la misma función "principal", Thread . En aplicaciones reales, los distintos subprocesos suelen tener distintas funciones "principales".
Tenga en cuenta que, como en el artículo original, el hilo se verifica a sí mismo antes de ingresar a la sección crítica. Dado que las condiciones del bucle se evaluarán como falsas , esto no causa mucho retraso.
// declaración y valores iniciales de variables globales Ingresando : matriz [ 1. . NUM_THREADS ] de bool = { false }; Número : matriz [ 1. . NUM_THREADS ] de entero = { 0 }; bloqueo ( entero i ) { Ingresando [ i ] = verdadero ; Número [ i ] = 1 + máx ( 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 ( Ingresando [ j ]) { /* nada */ } // Esperar hasta que todos los hilos con números menores o con el mismo // numero, 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 ) { cerradura ( 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 esté construido sobre alguna operación "atómica" de nivel inferior, por ejemplo, comparar e intercambiar . La prueba original muestra que para las lecturas y escrituras superpuestas en la misma celda de almacenamiento, solo la escritura debe ser correcta. [ aclaración necesaria ] La operación de lectura puede devolver un número arbitrario. Por lo tanto, este algoritmo se puede utilizar para implementar la exclusión mutua en la memoria que carece de primitivas de sincronización, por ejemplo, un disco SCSI simple compartido entre dos computadoras.
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 fue eliminada 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á equal 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 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 en un sistema multitarea cooperativo , es mejor reemplazar las secciones de "no hacer nada" con código que notifique al sistema operativo que cambie inmediatamente al siguiente hilo. Esta primitiva se conoce a menudo como yield.
El algoritmo de panadería de Lamport asume un modelo de memoria de consistencia secuencial. Pocos lenguajes o procesadores multinúcleo implementan un modelo de memoria de este tipo, por lo que la implementación correcta del algoritmo normalmente requiere insertar barreras para inhibir la reordenación. [1]
Declaramos que N es el número de procesos y asumimos que N es un número natural.
N CONSTANTEASUMIR N \in NatDefinimos P como el conjunto {1, 2, ..., N} de procesos.
P == 1..NLas variables num y flag se declaran como globales.
--algoritmo AtomicBakery {variable num = [i \in P |-> 0], bandera = [i \in P |-> FALSO];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 .
definir { LL(j, i) == \/ num[j] < num[i] \/ /\ num[i] = num[j] /\ j =< yo }Para cada elemento de P hay un proceso con las variables locales unread, max y nxt. Los pasos entre las etiquetas consecutivas p1, ..., p7, cs se consideran atómicos. La instrucción con establece id en un elemento elegido de forma no determinista del conjunto S y luego ejecuta body. Un paso que contiene la instrucción await expr se puede ejecutar solo cuando el valor de expr es TRUE .(x \in S) { body }
proceso (p \en P) variables no leídas \en SUBCONJUNTO P, máximo \en Nat, nxt \en P;{p1: mientras (VERDADERO) { no leído := P \ {self} ; máx := 0; bandera[self] := VERDADERO;p2: mientras (no leído # {}) { con (i \in no leído) { no leído := no leído \ {i}; si (num[i] > máx) { máx := num[i]; } } };p3: num[self] := máx + 1;p4: bandera[self] := FALSO; no leído := P \ {self} ;p5: mientras (no leído # {}) { con (i \in no leído) { nxt := i ; }; esperar ~ bandera[nxt];p6: espera \/ num[nxt] = 0 \/ LL(yo mismo, nxt) ; no leído := no leído \ {nxt}; } ;cs: omitir; \* la sección crítica;p7: num[auto] := 0; }}}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. En el modelo de memoria de Java, esto garantiza que las escrituras sean visibles inmediatamente para todos los subprocesos.
AtomicIntegerArray ticket = new AtomicIntegerArray ( threads ); // ticket para los hilos en línea, n - número de hilos // Java inicializa cada elemento de 'ticket' a 0 AtomicIntegerArray ingresando = new AtomicIntegerArray ( threads ); // 1 cuando el hilo ingresa en la línea // Java inicializa cada elemento de 'entering' a 0 bloqueo de vacío público ( int pid ) // ID del hilo { ingresando .set ( pid , 1 ) ; int máximo = 0 ; para ( int i = 0 ; i < hilos ; i ++ ) { int actual = ticket . get ( i ); si ( actual > máx ) { máx = actual ; } } ticket .set ( pid , 1 + max ) ; ingresando .set ( pid , 0 ) ; para ( int i = 0 ; i < ticket . length (); ++ i ) { si ( i != pid ) { mientras ( ingresando . get ( i ) == 1 ) { Hilo . yield (); } // esperar mientras otro hilo selecciona un ticket mientras ( 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í...}desbloqueo público vacío ( int pid ) { billete .set ( pid , 0 ) ; }