Il Problema del barbiere addormentato è un classico problema di sincronizzazione di cui molti di voi potrebbero avere familiarità o almeno averne sentito parlare.
Si basa sulla premessa che un barbiere (un thread) dorme quando non ci sono clienti (ogni cliente è un thread) nella sala d'attesa (che è un semaforo). Se c'è qualcuno, si taglia i capelli (a simboleggiare qualche lavorazione) e il cliente se ne va. Se, quindi, non c'è nessuno nella sala d'attesa, il barbiere va a dormire. Quando arriva un altro cliente, deve quindi svegliare il barbiere.
Ne ho fatto un'implementazione usando la seguente idea di base (pseudo-codice, usando solo sem_wait
e sem_post
1 per una lettura fluida)
Semaphore Customers = 0;
Semaphore Barber = 0;
Mutex accessSeats = 1;
int NumberOfFreeSeats = N;
Barber {
while(1) {
sem_wait(Customers) // waits for a customer (sleeps)
sem_wait(accessSeats) // mutex to protect the number of available seats
NumberOfFreeSeats++ // a chair gets free
sem_post(Barber) // bring customer for haircut
sem_post(accessSeats) // release the mutex on the chair
// barber is cutting hair
}
}
Customer {
while(1) {
sem_wait(accessSeats) // protects seats so only 1 thread tries to sit in a chair if that's the case
if(NumberOfFreeSeats > 0) {
NumberOfFreeSeats-- // sitting down
sem_post(Customers) // notify the barber
sem_post(accessSeats) // release the lock
sem_wait(Barber) // wait in the waiting room if barber is busy
// customer is having hair cut
} else {
sem_post(accessSeats) // release the lock
// customer leaves
}
}
}
Tuttavia, ora che implementerò questo problema con più barbieri, la mia testa si è bloccata. Sono andato su Wikipedia per vedere se potevo trovare qualcosa al riguardo, ma l'unica cosa che ho trovato era questa
A multiple sleeping barbers problem has the additional complexity of coordinating several barbers among the waiting customers.
e non sono riuscito a capirlo da solo. In tal caso avrei questa complessità? Di diversi barbieri che vanno nella sala d'attesa per vedere se c'è qualcuno lì e quindi che prende (più di un barbiere) un solo cliente? Avrei bisogno di un semaforo extra qui?
1 sem_wait () blocca il semaforo. sem_post () lo sblocca