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

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); 

的一个问题，我可以看到的是，如果一个哲学家是吃，毗邻他有人试图抢一双筷子，他将不能够得到一个完整的一对，因此每个人都将被冻结，直到目前的食客完成。我在这里一切正常吗？

我将不胜感激任何反馈！

真诚， REDZONE

Answer 1

我想自己找出尽可能多地。

您是否阅读过有关这些维基百科的文章？你有从那里的具体问题？我很高兴你想为自己工作，但这是一个糟糕的计划。了解什么是洞察力。维基百科经常不会挑剔你，但给你一个基础。

的一个问题，我可以看到的是，如果一个哲学家是吃，毗邻他有人试图抢一双筷子，他将不能够得到一个完整的对，因此每个人都将被冻结直到现在的食客完成。我在这里一切正常吗？

你是在正确的轨道上，是的。请注意，有可能两个人同时进食，但没有更多。诀窍就是在你拿起它后，如果你不能得到第二个，就放下你持有的几滴蜱。

（在有点儿一个C的混合动力和伪代码）：

所有伪趋于℃的混合;）

Answer 2

餐哲学家是由锁定顺序解决的经典死锁问题（我相信这是在你的书中，尝试代码很好，但它是很好的基础第一）

1. 每个筷子订购一个（不同）的数字。
2. 哲学家必须能够拿起较低编号的筷子，然后拿起较高数量的筷子。
3. 一旦您获得降低编号的筷子，即使您无法立即获得编号较高的筷子，您仍可以坚持。
4. 一个（也许是两个）哲学家总是能够吃东西，并最终完成，让另一个（或两个）吃。

 

     1 o 2 

     o  o 

     4 o 3 

您可以将相同的逻辑来最僵局的问题。这类问题的关键不在于如何对解决方案进行编码，而是为了识别它解释的问题（死锁，资源匮乏）以及解决方案，然后将解决方案应用于此类型的其他更一般化问题（在锁A，B和C，如何确保在尝试获取多个锁的线程之间没有死锁（筷子是锁的隐喻，哲学家是线程或进程的隐喻））。