Algoritmo de panadería de Lamport

El algoritmo de panadería de Lamport es un algoritmo informático ideado por el 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 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 concurrentes 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 numeradora en la 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 está atendiendo actualmente. Todos los demás clientes deben esperar en 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, permitiendo atender al siguiente cliente. Ese cliente debe sacar otro número de la máquina numeradora para poder volver a comprar.

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 ligeras modificaciones. Es posible que más de un hilo obtenga el mismo número n cuando lo solicite; 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 del hilo i también es una prioridad. Un valor más bajo de i significa una prioridad más alta y los subprocesos con mayor prioridad ingresarán primero a la sección crítica.

Sección crítica

La sección crítica es la 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 comercia con el panadero cuando los demás deben esperar.

Cuando un hilo quiere entrar en la sección crítica, tiene que comprobar si ahora es su turno de hacerlo. Debería verificar el número n de cada dos 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 el i más pequeño ingresará primero a la sección crítica.

En pseudocódigo, esta comparación entre los subprocesos a y b se puede escribir en la forma:

// Let na - el número de cliente para el hilo a, y
/ ia - el número de hilo para hilo aEntonces

(na, ia)b, ib)

que equivale a:

(na Identificadob(n)a ==b) y (ia ib)

Una vez que el hilo finaliza su trabajo crítico, se deshace de su número y ingresa a 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 algún cálculo específico de un subproceso que no interfiere con la ejecución de otros subprocesos. recursos y ejecución.

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 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] está sin límites.
• Un proceso puede fallar en cualquier momento. Asumimos que cuando falla, inmediatamente va a su sección no crítica y se detiene. Entonces puede haber un período cuando la lectura de su memoria da 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 el mismo comando "principal" función, Hilo. En aplicaciones reales, diferentes subprocesos suelen tener diferentes hilos "principales" funciones.

Tenga en cuenta que, como en el artículo original, el hilo se controla antes de entrar en la sección crítica. Dado que las condiciones del bucle se evaluarán como false, esto no causa mucho retraso.

 // declaración y valores iniciales de variables globales Entrando: array [1..NUM_THREADS] de bool = {}falso}; Número: array [1..NUM_THREADS] de entero = {}0}; Cerradura()entero i) {} Entrando[i] = verdadero; Número[i] = 1 + max()Número[1] ... Número[NUM_THREADS]); Entrando[i] = falso; para ()entero j = 1; j . NUM_THREADS; j++) {} // Espera hasta que el hilo j reciba su número: mientras ()Entrando[j]) {} * Nada */ } // Espera hasta todos los hilos con números más pequeños o con los mismos // número, pero con mayor prioridad, termine su trabajo: mientras (()Número[j] ! 0) " (()Número[j] j) c) ()Número[i] i)) {} * Nada */ } } }  Desbloquear()entero i) {} Número[i] = 0; } Thread()entero i) {} mientras ()verdadero) {} Cerradura()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 esté construido sobre algún algoritmo "atómico" de nivel inferior. operación, p.e. 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. 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 existe un 'bloqueo' alrededor de las líneas 7 a 13. Sin embargo, supongamos que la variable se eliminó y dos procesos calcularon el mismo Número[i]. Si el proceso de mayor prioridad fue adelantado antes de configurar Number[i], el proceso de baja prioridad verá que el otro proceso tiene un número de cero y entrará en la sección crítica; Más tarde, el proceso de alta prioridad ignorará el Número[i] igual 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 utiliza 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 seleccionará el mismo número que i.

Al implementar el pseudocódigo en un sistema de proceso único o en una multitarea cooperativa, es mejor reemplazar la opción "no hacer nada" por la de "no hacer nada". secciones con código que notifica al sistema operativo que cambie inmediatamente al siguiente hilo. Esta primitiva a menudo se denomina rendimiento.

El algoritmo de panadería de Lamport asume un modelo de memoria de consistencia secuencial. Pocos lenguajes o procesadores multinúcleo, si es que hay alguno, implementan dicho modelo de memoria. Por lo tanto, la implementación correcta del algoritmo generalmente requiere insertar barreras para inhibir el reordenamiento.

Código PlusCal

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

CONSTANT N
ASSUME 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.

--algorithm AtomicBakery {
variable num = [i in P ← 0], flag = [i in P Ø- FALSE];

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

definir { LL(j, i) == / num[j]
/ / num[i] = num[j]
♪ ♪ ♪ ♪♪
}

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

proceso (p in P)
variables unread in SUBSET P,
max in Nat,
nxt in P;
{}
p1: mientras (TRUE) {
sin leer:= P  {self};
max:= 0;
flag[self]:= TRUE;
p2: mientras (sin leer) {}
con (i in unread) { unread:= unread {};
si (num[i] не max) { max:= num[i]; }
}
};
p3: num[self]:= max + 1;
p4: flag[self]:= FALSE;
sin leer:= P  {self};
p5: mientras (sin leer) {}
con (i in unread) { nxt:= i; };
await ~ flag[nxt];
p6: espera / num[nxt] = 0
/ LL(self, nxt);
noread:= unread  {nxt};
};
cs: saltar; * la sección crítica;
p7: num[self]:= 0;
}
}

Código Java

Utilizamos la clase AtomicIntegerArray no por su construcción en operaciones atómicas, sino porque sus métodos get y set funcionan como lecturas y escritos volátiles. Bajo el modelo de memoria Java esto asegura que los escritos sean inmediatamente visibles a todos los hilos.

AtomicIntegerArray Ticket = nuevo AtomicIntegerArray()hilos); // ticket para hilos en línea, n - número de hilos// Java inicializa cada elemento de 'ticket' a 0 AtomicIntegerArray entrando = nuevo AtomicIntegerArray()hilos); // 1 cuando el hilo entra en línea// Java inicializa cada elemento de 'entrada' a 0 público vacío Cerradura()int pid) // ID de hilo{} entrando.set()pid, 1); int max = 0; para ()int i = 0; i c) hilos; i++) {} int corriente = Ticket.#()i); si ()corriente ■ max) {} max = corriente; } } Ticket.set()pid, 1 + max);  entrando.set()pid, 0); para ()int i = 0; i c) Ticket.longitud(); ++i) {} si ()i ! pid) {} mientras ()entrando.#()i) == 1) {} Thread.rendimiento(); } // espera mientras que otro hilo elige un ticket mientras ()Ticket.#()i) ! 0 " () Ticket.#()i) c) Ticket.#()pid) Silencio ()Ticket.#()i) == Ticket.#()pid) " i c) pid)) {} Thread.rendimiento(); } } } // La sección crítica va aquí...}público vacío Desbloquear()int pid){} Ticket.set()pid, 0);}