Algoritmo de Lamport

La panadería de Lamport es un algoritmo basado en el sistema de turno existente en las panaderías y otros negocios.
 Consiste en darle a cada cliente un numero, el cual determina el orden de atención del vendedor y permitirles realizar su pedido, después de lo cual se le libera, pudiendo este comprar nuevamente solo si obtiene un numero nuevo.
 Llevado a programación, el Servidor entrega un numero a cada hilo que desea acceder a este y les atiende de uno en uno por orden de llegada. Una vez que toca le toca su turno, el proceso ingresa a su etapa  critica y después de realizada esta, el servidor le libera y atiende al siguiente proceso.

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.

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

  }