multithreading - 关于我 sleep 的理发师和用餐的哲学家算法正确性的提示(不是答案)？

Question

我正在学习操作系统类(class)。两周后我们有考试，我怀疑里面有用餐哲学家和 sleep 理发师问题(信号量版本)。现在，如果我愿意，我可以打开教科书，然后用勺子把答案塞给我，但我宁愿自己去学。我花了一些时间来解决这些问题，我想我已经接近了，但是……我不确定。我不想只是被告知我的解决方案到底出了什么问题，但我想要提示。我想尽可能自己弄清楚。

所以， sleep 的理发师...在我制定的解决方案中，我有三个二进制信号量:'w' 代表等候室，'c' 代表理发师的椅子，'x' 代表导出。理发师一次可以照顾一个顾客，等完了再去候诊室里找其他顾客，如果没有就 sleep ，对吧？这是我为 barber 进程的代码(有点像 C 和伪代码的混合体)制定的:

while(true)
{
    P(w);    //Guarantees an entering customer can't check the waiting room before the barber.
    P(c);
    P(x);    //A customer being serviced can't leave until barber is done servicing him.
    while( customersWaiting > 0 )  
    {
        V(c);    //Allow a waiting room customer to sit in barber's chair.
        V(w);    //Allow another customer to enter the waiting room
        service customer
        V(x);    //Allow customer to leave
        P(w);    //Lock waiting room so barber can check it.
    }   
    //No customers
    V(w);   //Allow next entering customer to check waiting room.
    sleep
    V(c);   //Allows new customer service.
    service customer
    V(x);    //Allow customer to leave.
}

我认为这是正确的，但我不确定。我觉得刚进来的客户应该由 while(customersWaiting > 0) 循环中的代码处理，但我不知道如何安排信号量来完成这项工作。

顾客，如果我理解的话，必须检查一下椅子是否有人。如果是，他必须看看是不是里面的理发师。如果是，我叫醒他，否则他就坐在候诊室里。如果等候室满了，他就离开，对吧？无论如何，这是我为客户流程制定的代码:

P(w);    //Guarantees neither barber nor other customers can check waiting room.
if (chair is occupied)  //Could you write this as if(c), or would you create a separate flag?
{    
    if (barber is sleeping)
    {
        wakeup barber
        V(w);    //Now the waiting room can be checked by someone else.
        P(c);    //Sit in barber's chair
        P(x);    //Attempt to exit shop
    }
}
else
{
    if (customersWaiting < amountOfChairs)
    {
        customersWaiting++;
        V(w);    //Now the waiting room can be checked by someone else.
        P(c);    //Sit in barber's chair, when it's available that is.
        P(x);    //Attempt to exit shop
        customersWaiting--;
    }
}
exit shop

我不确定我是否在正确的轨道上......我看到的问题是，当没有顾客时，理发师会去 sleep ，但他可能不会一直睡着当有新顾客到来时，顾客就会去等候室永远等他。我想到了几种可能的方法来解决这个问题......我可以让理发师在他 sleep 前设置一个标志(使用信号量访问它)，然后新客户可以检查它，然后坐在紧密循环，直到理发师完全睡着，然后把他叫醒……但这并不是最好的解决办法，不是吗？我对此不确定......有什么提示吗？同样，我不想要直截了当的答案，我想要提示。

现在哲学家就餐问题......我对这个问题更有信心了，但我仍然想仔细检查一下。在我已经制定的解决方案中，我有一个二进制信号量“g”用于捕获一双筷子，一个计数信号量“a”用于可能开始进食的哲学家数量，以及一个二进制信号量 c[0..n -1] 每根筷子。基本上，一半的哲学家(当然是四舍五入)可能会在任何时候吃东西，对吧？ (当然四舍五入)所以在我的解决方案中，哲学家在他的思考完成后试图拿起一双筷子筷子，但前提是只有不到一半的哲学家在吃饭并且没有其他人试图拿起筷子。我把哲学家的代码编码成这样:

while(true)
{
    think
    P(g);    //Above all, no one else can try to grab a chopstick at the same time as someone else.
    P(a);    //Decrement the amount of philosophers that may start eating.
    P(c[left chopstick's number]);
    take left chopstick
    P(c[right chopstick's number]);
    take right chopstick
    V(g);    //Now someone else may attempt to grab a pair.
    eat
    V(c[left chopstick's number]);
    replace left chopstick
    V(c[right chopstick's number]);
    replace right chopstick
    V(a);

我能看到的一个问题是，如果一个哲学家正在吃饭，而他旁边的人试图拿起一双筷子，他将无法得到一双完整的筷子，因此每个人都会被卡住，直到当前吃完了。我走在正确的轨道上了吗？

如果有任何反馈，我将不胜感激!

真诚的，红区

Answer 1

Dining philosophers 是一个通过锁顺序解决的经典死锁问题(我相信这在你的书中，尝试代码很好，但最好先有基础)

1. 每根筷子都有一个(不同的)编号。
2. 哲学家必须先拿起编号较小的筷子，然后才能拿起编号较大的筷子。
3. 拿到编号较小的筷子后，即使您不能立即拿到编号较高的筷子，也可以坚持使用它。
4. 一个(也许两个)哲学家总是能够吃东西，并最终吃完，让另一个(或两个)哲学家吃饭。

      1  o  2      o     o      4  o  3

您可以对大多数死锁问题应用相同的逻辑。这类问题的重点不是如何编写解决方案，而是识别它说明的问题(死锁、资源匮乏)、解决方案，然后将解决方案应用于此类其他更普遍的问题(在具有锁A、B、C，如何保证在尝试获取多个锁的线程之间不会出现死锁(其中筷子是锁的比喻，哲学家是线程或进程的比喻)。