Hints (not answers) on correctness of my sleeping barber and dining philosopher algorithms?

Question

I'm in an operating systems course. We have an exam in two weeks, and I suspect that the dining philosopher and sleeping barber problems (semaphore versions) are in there. Now, if I wanted to, I could just crack open the textbook and have the answers spoonfed to me, but I would rather actually learn them on my own. I've spent some time working through the problems and I think I'm getting close, but... I'm not sure. I don't want to just be told exactly what's wrong with my solutions, but I would like hints. I want to figure out as much as possible by myself.

So, sleeping barber... In the solution I've worked out I have three binary semaphores: 'w' for the waiting room, 'c' for the barber's chair, and 'x' for exit. The barber can take care of one customer at a time, when done checks the waiting room for other customers, and if there are none, sleeps, right? This is what I have worked out for the barber process's code (in kinda a hybrid of C and pseudocode):

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

I think this is right but I'm not sure. I feel like the customer who just came in should be handled by the code in the while(customersWaiting > 0) loop, but I can't figure out how to arrange the semaphores to make that work.

The customer, if I understand it, must check to see if the chair is occupied. If it is, he must see if it is the barber in it. If it is, me wakes him up, otherwise he sits in the waiting room. If the waiting room is full, he leaves, right? Anyway, here's the code I've worked out for the customer process:

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

I'm not sure if I'm on the right track here or not... the problem I see is that, when there are no customers, the barber goes to sleep but, he might not be all the way asleep when a new customer arrives, and so the customer will go to the waiting room and wait for him forever. I've thought of a couple possible ways to solve this...I could have a flag that the barber sets right before he sleeps (using a semaphore to access it), and then the new customer could check that, and sit in a tight loop until the barber is all the way asleep, then wake him up... but that's not exactly the best solution, is it? I'm so unsure about this... Any hints? Again I don't want the answer straight up, I want hints.

Now the dining philosophers problem... I'm significantly more confident about this one, but I still want to double check. In wthe solution I've worked out, I have a binary semaphore 'g' for grabbing a pair of chopsticks, a counting semaphore 'a' for the number of philosophers that may start eating, and one binary semaphore c[0..n-1] for each chopstick. Basically, half the philosophers (rounded down, of course) may eat at any one time, right? (rounded down, of course) So in my solution, the philsopher after his thinking is done tries to grab a pair of chopsticks chopstick, but only if less than half the philosophers are eating and no one else is trying to grab a chopstick. I've coded the philosopher's code like this:

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

The one problem I can see is that, if a philosopher is eating and someone adjacent to him tries to grab a pair of chopsticks, he won't be able to get a full pair and therefore everyone will be frozen until the current eater finishes. Am I on the right track at all here?

I would greatly appreciate any feedback!

Sincerely, RedZone

Answer 1

Dining philosophers is a classical deadlock problem solved by lock ordering (I am sure that this is in your book, trying out code is nice, but it is nice to have the foundations first)

1. Every chopstick is ordered with a (different) number.
2. A philosopher must be able to pick up the lower numbered chopstick before picking up the higher number chopstick.
3. Once you have the lowered numbered chopstick, you can hold on to it even if you cannot get the higher numbered one right away.
4. One (maybe two) philosopher will always be able to eat, and will eventually finish, allowing another one (or two) to eat.

      1  o  2

      o     o

      4  o  3

You can apply the same logic to most deadlock problems. The point to this type of problem is not how to code a solution, but to recognize the problem it illustrates (deadlock, resource starvation), the solution, and then apply the solution to other more generalized problems of this type (in a program with locks A, B and C, how to ensure that there is no deadlock between threads trying to acquire multiple locks (where chopsticks are a metaphor for locks and philosophers are a metaphor for threads or processes)).

Answer 2

I want to figure out as much as possible by myself.

Have you read the wikipedia articles on each of these? Do you have specific questions from there? I'm glad you want to work them out for yourself, but that's a bad plan. See what insight exists. Wikipedia doesn't often spoonfeed you, but gives you a foundation.

The one problem I can see is that, if a philosopher is eating and someone adjacent to him tries to grab a pair of chopsticks, he won't be able to get a full pair and therefore everyone will be frozen until the current eater finishes. Am I on the right track at all here?

You're on the right track, yes. Note that it's possible for two people to eat at the same time, but no more. The trick is after you pick it up, if you can't get the second one, put down the one that you are holding for a few ticks.

(in kinda a hybrid of C and pseudocode):

all pseudocode tends to be a hybrid of C ;)