Thread: Dining Philosopher question

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    17

    Question 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?
    Last edited by jalex39; 03-11-2009 at 09:56 AM. Reason: I need to add the file but its to big so I will type the code

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    up(&mutex) should block anyone else who is trying to use that mutex.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    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 [...]"
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  5. #5
    Registered User
    Join Date
    Mar 2008
    Posts
    17

    The code is this-

    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!!

  6. #6
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Man i hate my OS class, that ........ is more challenging than C, we do it in BACI, damn that language n concurrency :S
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  7. #7
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    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.

    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
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  8. #8
    Registered User
    Join Date
    Mar 2008
    Posts
    17
    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.

  9. #9
    Registered User
    Join Date
    Mar 2009
    Posts
    2
    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.

  10. #10
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by Snafuist View Post
    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
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  11. #11
    Registered User
    Join Date
    Mar 2009
    Posts
    2
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Alice....
    By Lurker in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 06-20-2005, 02:51 PM
  2. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  3. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  4. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 01:47 AM