Dining Philosopher question

I am going to put this algorithm (attachment) in my code and however this code supposbly works and but it seems to me you could have a race condition if two adjacent philosophers try to aquire forks at the same time. in the take forks function if both philosophers execute the
up(&mutex) then try to iniate the down(&s[i]), I can't see what is going to prevent them from blocking each other. Does anyone understand this and would not mind assisting how its going to allow one to get forks and keep the other waiting to get them?

up(&mutex) should block anyone else who is trying to use that mutex.

--
Mats

I thot that's what a mutex is/does -- allows you to lock in/out variable access?

It would have been more interesting if you had to explain someone ending up with a rusty spoon :)

Although you didn't post the code, I suppose you are talking about the example code from the Chapter "The Dining Philosophers Problem" in "Modern Operating Systems" by Andrew S. Tanenbaum. In my edition (2nd), this is chapter 2.4.1, figure 2-33.

The philosophers can't block each other in take_forks(), because only one philosopher may call up(&mutex) at a time in the first place: if there's a philosopher in the critical region, he already issued a down(&mutex), so every other philosopher will block at the same call. Furthermore, the down(&s[i]) only affects philosopher i (he will block). There's no philosopher j != i who may call down(&s[i]), but there must be a philosopher j=i-1 or j=i+1 who calls up(&s[i]). Hence, philosopher i will resume as soon as the offending philosopher puts down his forks.

Either way, you should read the accompanying text and the chapter before that one called "Interprocess Communication", which explains the semantics of up(), down(), mutexes, semaphores etc.

Greets,
Philip

PS: for those of you who haven't got the book at hand, there's a funny bit right at the beginning of this chapter: "The life of a philosopher consists of alternate periods of eating and thinking. (This is something of an abstraction, even for philosophers [...]"

Code:

---


# define N  5
# define LEFT (i+N-1)%N
# define RIGHT (i+1)%N
# define THINKING  0
# define  HUNGRY  1
# define  EATING  2
typede int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N];
   

void philosopher(int i)
{
while (TRUE) {
    think ();
    take_forks(i);
    eat();
    put_forks(i);
}
}

void take_fork(int i)
{
    down(&mutex);
    state[i] = HUNGRY;
    test(i);
    up(&mutex);
    down(&s[i]);
}

void put_forks(i)
{
    down(&mutex);
    state[i] = THINKING;
    test(LEFT);
    test(RIGHT);
    up(&mutex);
}

void test(i)
{
    if (state[i] ==HUNGRY && state[LEFT] != EATING && state[RIGHT] !  =EATING {
    state[i] = EATING;
    up(&s[i];
}
}

I'm sorry for not posting the code originally at first I thought I did!!

---

Man i hate my OS class, that ........ is more challenging than C, we do it in BACI, damn that language n concurrency :S

Quote:

---

I'm sorry for not posting the code originally at first I thought I did!!

---

Yep, this looks like the example code from the book I mentioned.

Quote:

---

Man i hate my OS class, that ........ is more challenging than C, we do it in BACI, damn that language n concurrency :S

---

I just read the stuff on the BACI homepage. To me, it looks pretty simple, which is supported by the fact that their compiler is named "C--". The language is reduced to a very small subset of C/C++ and features all important concepts to get a grip on concurrent programming, such as semaphores, monitors, creating concurrent processes/threads. If you don't have to actually write code in C--, enjoy this quote from an exercise sheet of my own OS class several years ago: "If you don't understand C code, consider it to be pseudocode".

If you still hope that this might turn out useful eventually: "A Computer is a state machine. Threads are for people who can't program state machines." (Alan Cox)

Just kidding,
Philip

If no one one is eating initially and they both excute the function take_ forks the first one will run test and see that neither person to his left or right meets the test so he will change his state to eating and then up (&s[i]); and if the second at the same time runs it will get the same result but you are saying that because of down(&mutex) will prevent one from entering because mutex will be at 0 and by definition will block the other- but once the 1st hits up(&mutex) it will allow the second in and they will be at down(&s[i]);
Maybe I'm confused on what the down s[i] and up s[i] is going to do.

Quote:

---

The philosophers can't block each other in take_forks(), because only one philosopher may call up(&mutex) at a time in the first place: if there's a philosopher in the critical region, he already issued a down(&mutex),

---

The first philospher will release the critical area once he issues a down(&mutex) allowing the second to get in and possibly compete with the 1st for forks.

Quote:

---

Originally Posted by Snafuist

Yep, this looks like the example code from the book I mentioned.



I just read the stuff on the BACI homepage. To me, it looks pretty simple, which is supported by the fact that their compiler is named "C--". The language is reduced to a very small subset of C/C++ and features all important concepts to get a grip on concurrent programming, such as semaphores, monitors, creating concurrent processes/threads. If you don't have to actually write code in C--, enjoy this quote from an exercise sheet of my own OS class several years ago: "If you don't understand C code, consider it to be pseudocode".

If you still hope that this might turn out useful eventually: "A Computer is a state machine. Threads are for people who can't program state machines." (Alan Cox)

Just kidding,
Philip

---

Haha, no man i get your point. Me personally is my problem is understanding the whole deal with semaphores and monitors, that's my problem. I enjoyed C while i took intro to it, and another class. But this Operating System, simply not made for me :)

Thats what i believe i guess lol

Matus, what the hell you talking about-- are you on drugs. Anyways, this is what should happen when the 1st semaphore does a dow &mutex and goes to test he would be hungry and no one to his left or right are eating so he will up his state of hungry to eating. The second will get blocked due to the fact the the 1st will be eating (either left or right) so he will do a down si to thinking and be in a loop until the 1st is done.