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 , cuyo objetivo es mejorar la seguridad en el uso de recursos compartidos entre múltiples subprocesos mediante la exclusión mutua .
En informática , es común 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 simultáneos entren en secciones críticas de código al mismo tiempo para eliminar el riesgo de corrupción de datos.
Algoritmo
Analogía
Lamport imaginó una panadería con una máquina de numeración en su entrada para que cada cliente reciba un número único. Los números aumentan en uno a medida que los clientes ingresan a la tienda. Un contador global muestra el número del cliente al que se atiende actualmente. 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 aumenta 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 a partir de una variable global.
Debido a las limitaciones de la arquitectura de la computadora, algunas partes de la analogía de Lamport necesitan una ligera modificación. Es posible que más de un hilo obtenga el mismo número n cuando lo soliciten; esto no se puede evitar. Por lo tanto, se supone que el identificador de hilo i también es una prioridad. Un valor más bajo de i significa una prioridad más alta y los subprocesos con una prioridad más alta ingresarán primero a la sección crítica .
Sección crítica
La sección crítica es aquella parte del código que requiere acceso exclusivo a los recursos y 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, tiene que comprobar si ahora es su turno para hacerlo. Debería comprobar el número n de todos los demás subprocesos para asegurarse de que tenga el más pequeño. En caso de que otro hilo tenga el mismo número, el hilo con la i más pequeña entrará primero en la sección crítica.
En pseudocódigo esta comparación entre los hilos una y b se puede escribir en la forma:
(n a , i a ) <(n b , i b ) // n a - el número de cliente para el hilo a , i a - el número de hilo para el hilo a
que es equivalente a:
(n ab ) o ((n a == n b ) y (i a b ))
Una vez que el hilo finaliza su trabajo crítico, 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 un cálculo específico de subprocesos 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.
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 cuando falla, inmediatamente pasa a su sección no crítica y se detiene. Entonces puede haber un período en el que la lectura de su memoria dé valores arbitrarios. Eventualmente, cualquier lectura de su memoria debe dar un valor de cero.
Ejemplos de código
Pseudocódigo
En este ejemplo, todos los subprocesos ejecutan la misma función "principal", Thread . En aplicaciones reales, diferentes subprocesos a menudo tienen diferentes funciones "principales".
Tenga en cuenta que, como en el papel original, el hilo se comprueba antes de entrar en 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 = { falso }; Número : matriz [ 1 .. NUM_THREADS ] de entero = { 0 }; bloquear ( 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 ++ ) { // Espere hasta que el hilo j reciba su número: while ( Ingresando [ j ]) { / * nada * / } // Espere 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: while (( Número [ j ] ! = 0 ) && (( Número [ j ], j ) < ( Número [ i ], i ))) { / * nada * / } } } desbloquear ( entero i ) { Número [ i ] = 0 ; } Subproceso ( entero i ) { while ( verdadero ) { bloqueo ( i ); // La sección crítica va aquí ... desbloquear ( i ); // sección no crítica ... } }
Cada hilo solo escribe su propio almacenamiento, solo se comparten las lecturas. Es notable que este algoritmo no se construya sobre alguna operación "atómica" de nivel inferior, por ejemplo, comparar e intercambiar . La prueba original muestra que para 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.
Es posible que la necesidad de la variable Entering no sea obvia, ya que no hay un "bloqueo" entre las líneas 7 a 13. Sin embargo, suponga que la variable se eliminó y dos procesos calcularon lo mismo Number[i]
. Si el proceso de mayor prioridad se adelantó antes de la configuración Number[i]
, el proceso de baja prioridad verá que el otro proceso tiene un número cero y entra en la sección crítica; más tarde, el proceso de alta prioridad ignorará igual Number[i]
para los procesos de menor prioridad y también ingresará a la sección crítica. Como resultado, dos procesos pueden ingresar a 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; procesar i nunca se verá un número igual a cero para un proceso j que se va a recoger el mismo número que i .
Al implementar el pseudocódigo en un sistema de proceso único o bajo multitarea cooperativa , es mejor reemplazar las secciones de "no hacer nada" con un código que notifique al sistema operativo que cambie inmediatamente al siguiente hilo. Este primitivo a menudo se conoce como yield
.
El algoritmo de panadería de Lamport asume un modelo de memoria de consistencia secuencial. Pocos idiomas o procesadores multinúcleo, si es que hay alguno, implementan un modelo de memoria de este tipo. Por lo tanto, la implementación correcta del algoritmo generalmente requiere la inserción de vallas para inhibir el reordenamiento. [1]
Código PlusCal
Declaramos que N es el número de procesos y asumimos que N es un número natural.
N CONSTANTEASUME N \ en Nat
Definimos P como el conjunto {1, 2, ..., N} de procesos.
P == 1..N
Las variables num y flag se declaran como globales.
--algorithm AtomicBakery {variable num = [i \ in P | -> 0], flag = [i \ in P | -> FALSE];
Lo siguiente define LL(j, i)
como verdadero sif << 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 [j] / \ j = }
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 declaración con 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 se puede ejecutar solo cuando el valor de expr es (x \in S) { body }
VERDADERO .
proceso (p \ in P) variables no leídas \ en SUBSET P, max \ in Nat, nxt \ en P;{p1: while (VERDADERO) { no leído: = P \ {self}; máx: = 0; bandera [yo]: = VERDADERO;p2: while (no leído # {}) { with (i \ in unread) {unread: = unread \ {i}; if (num [i]> max) {max: = num [i]; } } };p3: num [self]: = max + 1;p4: bandera [yo]: = FALSO; no leído: = P \ {self};p5: while (no leído # {}) { con (i \ en no leído) {nxt: = i; }; aguardar ~ bandera [nxt];p6: espera \ / num [nxt] = 0 \ / LL (uno mismo, nxt); no leído: = no leído \ {nxt}; };cs: saltar; \ * la sección crítica;p7: num [yo]: = 0; }}}
Código Java
Usamos 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. Bajo el modelo de memoria de Java, esto asegura que las escrituras sean inmediatamente visibles para todos los subprocesos.
AtomicIntegerArray ticket = new AtomicIntegerArray ( hilos ); // ticket para subprocesos en línea, n - número de subprocesos// Java inicializa cada elemento de 'ticket' a 0 AtomicIntegerArray ingresando = new AtomicIntegerArray ( hilos ); // 1 cuando el hilo entra en línea// Java inicializa cada elemento de 'ingresar' a 0 public void lock ( int pid ) // ID de hilo{ entrando . conjunto ( pid , 1 ); int max = 0 ; para ( int i = 0 ; i < hilos ; i ++ ) { int current = ticket . obtener ( i ); si ( actual > max ) { max = corriente ; } } billete . conjunto ( pid , 1 + max ); entrando . conjunto ( pid , 0 ); para ( int i = 0 ; i < ticket . length (); ++ i ) { si ( yo ! = pid ) { while ( ingresando . get ( i ) == 1 ) { Thread . rendimiento (); } // espera mientras otro hilo elige un ticket while ( ticket . get ( i ) ! = 0 && ( ticket . get ( i ) < ticket . get ( pid ) || ( ticket . get ( i ) == ticket . get ( pid ) && i < pid ))) { Hilo . rendimiento (); } } } // La sección crítica va aquí ...} desbloqueo vacío público ( int pid ) { billete . conjunto ( pid , 0 );}
Ver también
Referencias
- ^ Chinmay Narayan, Shibashis Guha, S. Arun-Kumar Inferir vallas en un programa concurrente con prueba de corrección de SC
- Papel original
- En su página de publicaciones , Lamport ha agregado algunos comentarios sobre el algoritmo.
enlaces externos
- Variación de Wallace del algoritmo de panadería que supera las limitaciones del lenguaje Javascript. Archivado desde el original el 6 de mayo de 2018.
- Algoritmo de panadería de Lamport
- Otra implementación de JavaScript de a.in.the.k