Peluquería FIFO en sincronización de Procesos

Descripción general:
en la sincronización de procesos, existe un problema de Sleeping Barber, como se explica aquí. Pero en la solución anterior, no hay garantía de que los clientes sean atendidos en el orden en que llegan a la barbería, es decir, no hay garantía de que los clientes entren de manera FIFO (primero en entrar, primero en salir). En la solución discutida anteriormente.

• Pueden llegar hasta n clientes, luego señalar al cliente y esperar a que el barbero esté inactivo o despierto.
• Una vez que el peluquero está ocioso o despierto, cualquiera de los clientes puede proceder.

Requisito previo:
problema del peluquero durmiente en la sincronización de procesos

Planteamiento del problema: 
Queremos una solución en la que los clientes sean atendidos por orden de llegada al interior de la tienda.

Solución:
para mantener el orden de los clientes, debemos implementar una estructura de datos, conocida como Queue, que sigue el principio First-in First-out. En lugar de utilizar un solo semáforo para los clientes, se utilizará una lista de semáforos. De ahora en adelante, referiremos a un cliente como un hilo. Entonces, para los subprocesos, se usará una lista de semáforos, nombrada como una cola. La intuición detrás de este enfoque es que:

1. A medida que cada hilo ingresa a la barbería, crea un hilo y lo pone en la cola. 
2. En lugar de esperar a que el peluquero esté inactivo, cada subproceso espera en su propio semáforo.
3. Cada vez que un peluquero está ocioso o despierto, quita el hilo de la cola y le indica que proceda a la silla.

Nota:
el barbero debe obtener el mutex para acceder a la cola . Por lo tanto, el mutex usará algún semáforo para controlar el acceso del subproceso a la cola y el peluquero procesa la cola.

Algoritmo para el problema FIFO Barbershop:

Semaphore customer = 0;
Semaphore mutex = 1;
Semaphore barberDone = 0;
Semaphore customerDone = 0;
customer = 0;
Queue queue;

/* Number of chairs available */
n = 4

Customer
{
/* Protects the seat, to mark the present customer */
    Semaphore self = 0;
    
    mutex.wait();
    
    if(customer == n){
    mutex.signal();
          
/* Invoke the barber */
    customer += 1;          
            
/* Adds the thread inside the queue */
    queue.push(self);
    
    mutex.signal();
    customer.signal();
    self.wait();
    
/* gets the hair cut */
    customerDone.signal();
    barberDone.wait();
    
/* Decrements the number of thread by one */
    mutex . wait ();
    customers -= 1;
    mutex . signal ();
}


Barber{
/* To store the current thread*/
    Semaphore curr;
    
    customer.wait();
    mutex.wait();
    
/* Gets the current thread*/
    curr = queue.pop();
    mutex.signal();
    
    curr.signal();
    
    /* gets the hair cut */
    customerDone.waitl();
    barberDone.signal();

}

Nota:
self y curr no son más que semáforos que se refieren al hilo actual.