关于我的睡眠理发师和就餐哲学家算法的正确性的提示（不是答案）？

Question

我正在上操作系统课程。两周后我们有一次考试，我怀疑那里有哲学家就餐和理发师睡觉的问题（信号量版本）。现在，如果我愿意，我可以打开教科书并得到答案，但我宁愿自己实际学习它们。我花了一些时间来解决这些问题，我想我已经接近解决问题了，但是......我不确定。我不想只是被告知我的解决方案到底有什么问题，但我想要提示。我想尽可能地自己弄清楚。

所以，睡觉的理发师...在我制定的解决方案中，我有三个二进制信号量：“w”表示候诊室，“c”表示理发师的椅子，“x”表示出口。理发师一次可以照顾一名顾客，完成后检查等候室是否有其他顾客，如果没有，就睡觉，对吗？这是我为理发师流程的代码（有点 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

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

现在哲学家就餐问题……我对这个问题更有信心了，但我仍然想仔细检查一下。在我制定的解决方案中，我有一个用于抓住一双筷子的二进制信号量“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

哲学家就餐是一个通过锁排序解决的经典死锁问题（我确信这在你的书中，尝试代码很好，但最好先有基础）

1. 每根筷子都用一个（不同的）数字排序。
2. 哲学家必须能够在拿起编号较大的筷子之前拿起编号较小的筷子。
3. 一旦你拿到了编号较低的筷子，即使你不能立即拿到编号较高的那根筷子，你也可以握住它。
4. 一位（也许两位）哲学家总是能够吃饭，并且最终会吃完，让另一位（或两位）哲学家吃饭。

      1  o  2

      o     o

      4  o  3

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

Answer 2

我想自己尽可能多地弄清楚。

您读过关于这些的维基百科文章吗？您有具体问题吗？我很高兴你想自己解决这些问题，但这是一个糟糕的计划。看看存在什么洞察力。维基百科并不经常给你灌输，而是给你一个基础。

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

是的，你走在正确的道路上。注意，两个人可以同时吃饭，但不能多吃。诀窍是，在你拿起它之后，如果你拿不到第二个，就把你拿着的那个放下几格。

（有点 C 和伪代码的混合）：

所有伪代码往往都是 C 的混合；）