睡觉理发师算法(有多个理发师)

Question

该睡理发问题是一个经典的同步问题,很多人可能很熟悉,或者至少听说过.

它基于这样一个前提:当等候室(信号量)中没有客户(每个客户都是线程)时,理发师(线程)会睡觉.如果有人,他会削减他的头发(象征着一些处理)并且顾客离开.如果,等候室里没有人,那么理发师会去睡觉.当另一位顾客到达时,他必须叫醒理发师.

---

我使用以下基本思想实现了这一点

_{(虽然实际代码是在C,但为了解决问题,我编写了下面的伪代码而没有太多关心语法,只使用sem_wait和sem_post¹来更顺畅地阅读)}

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

但是,现在我将与多个理发师一起实施这个问题,我的头脑卡住了.我去维基百科看看我是否能找到一些关于它的东西,但我发现的唯一的东西就是这个

多个睡眠理发师问题具有在等待的顾客中协调几个理发师的额外复杂性.

而我自己也想不通².

我的代码需要做哪些更改？我在哪里需要额外的信号量？

¹ _{sem_wait()锁定信号量.sem_post()解锁它}
² _{免责声明:虽然我已经在programmers.stackexchange中问过这个问题,但我没有达到预期的答案,我的问题仍然存在.}

Answer 1

编写的代码将管理任意数量的理发师，而无需任何额外的信号量。只需为店里的每个理发师启动一个 Barber 线程即可。{}

维基百科评论中提到的问题是这样的：仅仅因为你有 M 个理发师处于“理发师正在理发”状态，M 个顾客处于“顾客正在理发”状态，就不能保证某些理发师不会尝试理发。理发超过一位顾客，或者某些顾客没有几位理发师在理发。

换句话说，一旦允许适当数量的顾客进入剪发室，理发师和顾客如何配对？你不能再说“理发师正在理发”和“顾客正在理发”；你必须说“理发师正在给顾客C剪头发”和“顾客正在理发师B剪头发”。

// Assumptions about the meaning of 'haircut':
// each thread has a unique PID
// each thread can get its own PID via system.info.PID
// a barber uses a customer's PID to cut that custmer's hair
// a customer uses a barber's PID to get his hair cut by that barber
// Assumptions about the operating environment:
// a semaphore releases threads in the order that they were queued

Semaphore Customers = 0;
Semaphore Barbers = 0;
Mutex AccessSeats = 1;
int NumberOfFreeSeats = N;
int SeatPocket[N];  // (or 'PID SeatPocket[N];' if PID is a data type)
int SitHereNext = 0;
int ServeMeNext = 0;

// main program must start a copy of this thread for each barber in the shop
Barber {
    int mynext, C;
    while(1) {
        sem_wait(Barbers);  // join queue of sleeping barbers
        sem_wait(AccessSeats);  // mutex to protect seat changes
        ServeMeNext = (ServeMeNext++) mod N;  // select next customer
        mynext = ServeMeNext;
        C = SeatPocket[mynext];  // get selected customer's PID
        SeatPocket[mynext] = system.info.PID;  // leave own PID for customer
        sem_post(AccessSeats);  // release the seat change mutex
        sem_post(Customers);  // wake up selected customer
        //
        // barber is cutting hair of customer 'C'
        //
    }
}

// main program must start a copy of this thread at random intervals
// to represent the arrival of a continual stream of customers
Customer {
    int myseat, B;
    sem_wait(AccessSeats);  // mutex to protect seat changes
    if(NumberOfFreeSeats > 0) {
        NumberOfFreeSeats--;  // sit down in one of the seats
        SitHereNext = (SitHereNext++) mod N;
        myseat = SitHereNext;
        SeatPocket[myseat] = system.info.PID;
        sem_post(AccessSeats);  // release the seat change mutex
        sem_post(Barbers);  // wake up one barber
        sem_wait(Customers);  // join queue of sleeping customers
        sem_wait(AccessSeats);  // mutex to protect seat changes
        B = SeatPocket[myseat];  // barber replaced my PID with his own
        NumberOfFreeSeats++;  // stand up
        sem_post(AccessSeats);  // release the seat change mutex
        //
        // customer is having hair cut by barber 'B'
        //
    } else {
        sem_post(AccessSeats);  // release the seat change mutex
        // customer leaves without haircut
    }
    system.thread.exit;  // (or signal main program to kill this thread)
}