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 */
      }
  }

Véase también

• Algoritmo de Dekker
• Algoritmo de Peterson

Enlaces externos

• Página web de Leslie Lamport