Algoritmo de la panadería de Lamport
De Wikipedia, la enciclopedia libre
El algoritmo de la panadería de Lamport es un algoritmo de computación creado por el científico en computación Dr Leslie Lamport, para implementar la exclusión mutua de N procesos o hilos de ejecución.
Tabla de contenidos |
[editar] Algoritmo
El algoritmo de la panadería toma su nombre de la costumbre de las panaderías y tiendas en general, donde las personas al entrar al local extraen un número (único) y lo utilizan para ser atendidos en orden por el empleado del mostrador. Sólo una persona puede ser atendida a la vez, que concuerda con el uso de un recurso (en este caso el empleado) de forma exclusiva (la sección crítica de un cliente es lo que realiza en el lapso de tiempo que transcurre mientras es atendido). Un número (variable global) es mantenido y refleja el número de cliente que está siendo atendido en ese instante. Los clientes deben esperar en una cola mientras el cliente actual es atendido. Una vez terminada la atención la variable global es incrementada en una unidad y el cliente con ese número pasa a ser atendido. Cuando termina una compra, el cliente tira el número y puede hacer lo que quiera (guardar la plata en la billetera, retirarse, etc., ya que no se encuentra más en su sección crítica) salvo comprar nuevamente, para lo que tiene que sacar otro número.
Los clientes, en computación, serán threads identificados por un número i, siempre mayor o igual a cualquier número sacado anteriormente.
Debido a limitaciones en la arquitectura del computador, algunas partes de la analogía deben ser revisadas para su implementación. Es posible que más de un thread obtenga el mismo número: esto no puede ser evitado. Por lo tanto, se utiliza el número de thread, i, como un identificador de prioridad. Cuando más bajo es este número mayor la prioridad, lo que significa que podrá entrar en su sección crítica antes (podrá ser atendido por el panadero).
Cuando un thread quiere entrar en su sección crítica, debe asegurarse de tener el mismo número del que muestra la variable global. Además debe tener la máxima prioridad entre los posibles threads que poseen mismo número. En este último caso, entrará en su sección crítica el thread con menor i. En pseudocódigo la comparación se ve de esta forma:
(a, b) < (c, d) que es análogo a (a < c) o ((a == c) y (b < d)), siendo (x, y) tal que x es el número extraído e y el identificador de thread i.
[editar] Implementación
En pseudocódigo, una implementación del algoritmo de la panadería es la siguiente, donde N es el número de threads:
/* declaración e inicialización de las variables globales */
Número: arreglo [1..N] de enteros = {0};
Eligiendo: arreglo [1..N] de booleanos = {falso};
Thread(i) {
while (cierto) {
Eligiendo[i] = cierto;
Número[i] = 1 + max(Número[1], ..., Número[N]);
Eligiendo[i] = falso;
for (j = 1; j <= N; j++) { /* Para todos los threads */
while (Eligiendo[j] != falso) {
/* Esperar hasta que el thread j reciba su Número */
}
while ((Número[j] != 0) && ((Número[j], j) < (Número[i], i))) {
/* esperar que terminen los threads con menor Número o
con el mismo Número, pero con mayor prioridad */
}
}
/* sección crítica */
Número[i] = 0;
/ resto */
}
}
