Algoritmo de la panadería de
Lamport
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.
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 obtienen un número de turno (único) y lo utilizan
para que el dependiente les vaya atendiendo en orden de llegada. El cliente
obtiene su número de turno usando una cinta de papel que ofrece boletos con
números consecutivos.
El dependiente sólo puede atender
a una persona al mismo tiempo, lo que concuerda con el uso de un recurso de
forma exclusiva: el recurso es el dependiente y la sección crítica de un cliente es lo que realiza mientras es
atendido.
El sistema mantiene un número (variable global) que refleja el número de turno del
cliente que se está atendiendo en el instante actual. Los clientes deben
esperar en una cola hasta que llega su turno. Una vez que se acaba con un
cliente, la variable global se incrementa en uno y el cliente que tenga un
boleto con ese número pasa a ser atendido. Cuando termina una compra, el
cliente se desprende de su boleto y se dedica a realizar cualquier otra
actividad libremente (guardar el dinero en la billetera, retirarse, etc.), ya
que no se encuentra más en su sección crítica. Si más tarde quiere volver a
comprar, tendrá que obtener un nuevo número.
En el modelo algorítmico que se
propone, cada cliente es un hilo, identificado con un número único i.
Los hilos se deben coordinar para decidir en cada momento qué hilo tiene
derecho a ejecutar su código de sección crítica.
En la vida real, el sistema de
los boletos funciona perfectamente, pero en un sistema informático la obtención
del boleto es problemática: varios hilos pueden obtener el mismo número de
turno. En el algoritmo de Lamport se permite que varios hilos obtengan el mismo
número. En este caso, se aplica un algoritmo de desempate, que garantiza
que sólo un hilo entra en sección crítica. El desempate se realiza así: si dos
o más hilos tienen el mismo número de turno, tiene más prioridad el hilo que
tenga el identificador con un número más bajo. Como no puede haber dos hilos
con el mismo identificador, nunca se da el caso de que dos hilos evalúen al
mismo tiempo que tienen derecho a ejecutar su sección crítica.
Entrada en sección crítica
Cuando un hilo quiere entrar en
su sección crítica, primero obtiene su número de turno, que calcula como el
máximo de los turnos de los otros hilos, más uno. (Si varios hilos realizan el
cálculo al mismo tiempo, puede ocurrir que dos o más hilos obtengan el mismo
turno).
Antes de entrar en sección
crítica, el hilo debe asegurarse de que tiene el número de turno más bajo. En
caso de empate, decidirá el identificador de hilo más bajo.
Cuando el hilo abandona la
sección crítica, pone su número de turno a un valor especial que indique su no
intención de entrar en sección crítica (en este algoritmo, se usa el valor
cero).
Implementación
Este es el pseudocódigo del
algoritmo de la panadería.
Operador de comparación
Para simplificar la escritura del
algoritmo, se utiliza esta notación en las comparaciones entre las prioridades
de los hilos:
(a, b) < (c, d)
que es equivalente a:
(a < c) o ((a == c) y (b < d))
Pseudocódigo
N es el número de hilos que hay en el sistema.
Para conocer los números de turno
se utiliza un vector de enteros. número[i] es el turno correspondiente al hilo i.
Si número[i] = 0 significa que el hilo i no está interesado en entrar en
sección crítica.
/* Variables globales */
Número: vector [1..N] de enteros = {todos a 0};
Eligiendo: vector [1..N] de booleanos = {todos a
falso};
/* Código del hilo i */
Hilo(i) {
loop {
/* Calcula el número de turno
*/
Eligiendo[i] = cierto;
Número[i] = 1 + max(Número[1],...,
Número[N]);
Eligiendo[i] = falso;
/* Compara con todos los hilos
*/
for j in 1..N {
/* Si el hilo j está
calculando su número, espera a que termine */
while ( Eligiendo[j] ) {
/* nada */ }
/* Si el hilo j tiene más prioridad,
espera a que ponga su número a cero */
/* j tiene más prioridad si
su número de turno es más bajo que el de i,
*/
/* o bien si es el mismo número y además j es
menor que i */
while ( (Número[j] != 0)
&& ((Número[j], j) < (Número[i], i)) ) { /* nada */ }
}
/* Sección crítica */
...
/* Fin de sección crítica */
Número[i] = 0;
/* Código restante */
}
}
