Problema del barbiere addormentato (con più barbieri)

6

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

    
posta user2018675 02.10.2013 - 05:03
fonte

1 risposta

2

Con un barbiere, hai solo bisogno di una coda di messaggi (la sala d'attesa). I semafori sono incorporati in esso.

Con più barbieri, la coordinazione mira a:

  • impedendo a diversi barbieri di tagliare i capelli dello stesso cliente.

  • impedendo di avere un solo barbiere occupato mentre gli altri dormono tutto il giorno.

risposta data 02.10.2013 - 09:29
fonte

Leggi altre domande sui tag