Thread: Dining Philosophers...with threads.

  1. #1
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657

    Dining Philosophers...with threads.

    I just came accross this problem..and thought I'd try my own solution.
    Basically each of them thinks and eats for a random amount of time.
    One eats only when both chops are available, otherwise they put it down. The choice about which chopstick to pick up first is random.
    So far, It has been running for 20 mins without stopping (deadlock..?) .
    That makes me reasonable sure that it 'works'.

    See any bug ? ..or find a case in which it stops working ?

    Code:
    #include <iostream>
    #include <thread>
    #include <mutex>
    #include <array>
    #include <random>
    #include <chrono>
    #include <vector>
    
    const int nump=5;
    class Philosopher
    {
    public:
        Philosopher(int n_):n(n_)
        {
            chops.first = n;
            chops.second = (n<4)?n+1:0;
            randgen.seed(n);
        };
        void operator()(std::array<std::mutex,nump>& locks)
        {
            while(true)
            {
                std::chrono::milliseconds sleep_time (randgen()%10000),eat_time(randgen()%10000);
                log("Thinking");
                std::this_thread::sleep_for(sleep_time);
                
                bool hungry=true;
                int first,second;
                while(hungry)
                {
                    int choice =randgen()%2;
                    first =chops.first;
                    second = chops.second;
                    if(choice)
                        std::swap(first,second);
    
                    if(locks[first].try_lock())
                        if(locks[second].try_lock())
                            {
                                log("Eating");
                                std::this_thread::sleep_for(eat_time);
                                hungry=false;
                            }
                        else locks[first].unlock();
                    std::this_thread::sleep_for(std::chrono::milliseconds(1));
                }
                locks[first].unlock();
                locks[second].unlock();
                
            }
    
        }
        void log(const std::string& data)
        {
            while(!cout_lock.try_lock())std::this_thread::sleep_for(std::chrono::milliseconds(1));
            std::cout<<"Philosopher "<<n<<" "<<data<<std::endl;
            cout_lock.unlock();
        }
    private:
        int n;
        std::pair<int,int> chops;
        std::mt19937 randgen;
        static std::mutex cout_lock;
    };
    std::mutex Philosopher::cout_lock;
    int main()
    {
        std::array<std::mutex,nump> chops;
        std::vector<std::thread> threads;
        for(int i=0;i<nump;++i)
            threads.push_back
            (
                std::thread
                (
                    Philosopher(i),
                    std::ref(chops)
                )
            );
        for(auto& t:threads)
            t.join();
        return 0;
    }
    Removing the 1 milisecond sleep time when a try_lock fails, seems to speed up everything !

    [EDIT: Strangely, this fails when the number of Philosophers is 2. The second one does not ever get the chance to eat.
    The frequency seems to be well distributed when the number is higher, though.]
    Last edited by manasij7479; 07-30-2012 at 09:58 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > chops.second = (n<4)?n+1:0;
    Well 4 should be nump, otherwise the code is broken if you change the number of philosophers from 5 (to 2 say).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by Salem View Post
    > chops.second = (n<4)?n+1:0;
    Well 4 should be nump, otherwise the code is broken if you change the number of philosophers from 5 (to 2 say).
    Can't believe I missed that !
    (The problem spec I read mentioned 5, and I forgot to change this when I generalized it !)
    Unfortunately, the problem with 2 members (where the 2nd gets nothing to eat remains.)

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Question 13.18
    It might be worth checking your random function.
    Some crude algorithms can be rather less random in the LSB.

    Also, sleeping for 1ms (when the OS timeslice may be say 20ms) might not be doing what you expect.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by Salem View Post
    Question 13.18
    It might be worth checking your random function.
    Some crude algorithms can be rather less random in the LSB.
    I used the standard implementation of the mersenne twister.
    Would that problem be solved by
    Code:
    bool choice =randgen()%100 < 50 ;
    ?
    (If yes, the problem for 2 members is elsewhere )
    Also, sleeping for 1ms (when the OS timeslice may be say 20ms) might not be doing what you expect.
    How do I query it, in a POSIX system ?

  6. #6
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    It's possible it has something to do with how you're seeding the RNG. Try this:
    Code:
    randgen.seed((n+1) * static_cast<unsigned int>(std::time(0)));
    For the coin-flip (0 or 1) random value, if you know the maximum value of randgen() you could do this:
    Code:
    if (randgen() < (MAX_RANDGEN_VALUE+1)/2)
    For the sleep and eat times, you might try:
    Code:
    (randgen() % 10 + 1) * 100; // from 100 to 1000 in 100ms intervals
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  7. #7
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by oogabooga View Post
    It's possible it has something to do with how you're seeding the RNG. Try this:
    Code:
    randgen.seed((n+1) * static_cast<unsigned int>(std::time(0)));
    That seems to have made the frequency distribution more 'even' as recorded by a modified log function.
    But for 2 people, it remains one sided.
    [manasij7479@manasijd ~]$ g++ a.cpp -std=c++11 -lpthread
    [manasij7479@manasijd ~]$ ./a.out
    Philosopher 0 Thinking
    Philosopher 1 Thinking
    Philosopher 0 Eating
    Philosopher 0 Thinking
    Philosopher 0 Eating
    Philosopher 0 Thinking
    Philosopher 0 Eating
    Philosopher 0 Thinking
    Philosopher 0 Eating
    Philosopher 0 Thinking
    Philosopher 0 Eating
    Philosopher 0 Thinking
    Philosopher 0 Eating
    Philosopher 0 Thinking
    Philosopher 0 Eating
    Philosopher 0 Thinking
    Philosopher 0 Eating
    Philosopher 0 Thinking
    Philosopher 0 Eating
    Philosopher 0 Thinking
    Philosopher 0 Eating
    Philosopher 0 Thinking
    ^C


    For the coin-flip (0 or 1) random value, if you know the maximum value of randgen() you could do this:
    Code:
    if (randgen() < (MAX_RANDGEN_VALUE+1)/2)
    Did so, with the max() member function.
    Last edited by manasij7479; 07-30-2012 at 12:30 PM.

  8. #8
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Just to make sure. Did change this line like so (i.e., nump-1, not just nump).
    Code:
    chops.second = (n < nump - 1) ? n + 1 : 0;
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  9. #9
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    Or "(n + 1) % nump".

    Re-post the current state of the code for another code review.

    gg

  10. #10
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Code:
    #include <iostream>
    #include <thread>
    #include <mutex>
    #include <array>
    #include <random>
    #include <chrono>
    #include <vector>
    #include <ctime>
    const int NumP=5;
    
    class Philosopher
    {
    public:
        Philosopher(int n_,int health_=200):n(n_),health(health_)
        {
            chops.first = n;
            chops.second = (n + 1) % NumP;
            
            randgen.seed((n+1)* static_cast<unsigned int>(std::time(nullptr)));
    
            for(int i=0;i<NumP;++i)
            {
                logtab[i]=[]
                    (int n){std::string temp;while(n--)temp+="\t\t\t";return temp;}
                        (i);//3 tabs for a coloumn in the log output, change as required for your terminal
            }    
    
        };
        void operator()(std::array<std::mutex,NumP>& locks)
        {
            while(true)
            {
                std::chrono::milliseconds sleep_time ((randgen()%10+1)*100),eat_time((randgen()%10+1)*100);
                log("Thinking");
                std::this_thread::sleep_for(sleep_time);
                
                bool hungry=true;
                int temp_health=health;
                
                int first,second;
                while(hungry)
                {
                    bool choice =randgen() < (randgen.max()+1)/2 ; 
                    first =chops.first;
                    second = chops.second;
                    if(choice)//The order of choice becomes random
                        std::swap(first,second);
    
                    if(locks[first].try_lock())
                        if(locks[second].try_lock())
                            {
                                log("Eating");
                                std::this_thread::sleep_for(eat_time);
                                hungry=false;
                                break;
                            }
                        else locks[first].unlock();//Putting the first one down too
                    std::this_thread::sleep_for(std::chrono::milliseconds(20));//Try again
                    temp_health--;
                    if(!temp_health)
                    {
                        log("Leaving");//Becasue of lack of food in the seminar!
                        return;
                    }
                }
                locks[first].unlock();
                locks[second].unlock();
    
            }
    
        }
        void log(const std::string& fooing)
        {
            while(!cout_lock.try_lock())
                std::this_thread::sleep_for(std::chrono::milliseconds(20));
                    
            std::cout<<logtab[n]<<"Philosopher "<<n<<" "<<fooing<<std::endl;
            cout_lock.unlock();
        }
    private:
        int n;//'Roll' no. of the philosophers!
        std::pair<int,int> chops; // ^--- chops 
        std::mt19937 randgen;//Typedef of the Mersenne Twister engine with some weird looking parameters
        int health;//Each philosopher tries to eat health no. of times and then gets annoyed and leaves.
        
        std::array<std::string,NumP> logtab;
        static std::mutex cout_lock;
    };
    std::mutex Philosopher::cout_lock;
    
    int main()
    {
        std::array<std::mutex,NumP> chops;
        std::vector<std::thread> threads;
        for(int i=0;i<NumP;++i)
            threads.push_back
            (
                std::thread
                (
                    Philosopher(i),
                    std::ref(chops)
                )
            );
        for(auto& t:threads)
            t.join();
        return 0;
    }

  11. #11
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    O_o

    Why aren't you using `std::lock'? (You can lock multiple `mutex' objects at the "same time" with one expression.)

    Was it removed while I wasn't paying attention?

    Soma

  12. #12

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. The Diening Philosophers with POSIX Threads
    By MaSSaSLaYeR in forum C Programming
    Replies: 13
    Last Post: 03-21-2012, 02:27 PM
  2. Threads , how? Portable Threads Library?
    By adderly in forum C++ Programming
    Replies: 3
    Last Post: 12-15-2011, 07:54 AM
  3. Dining Philosopher question
    By jalex39 in forum C Programming
    Replies: 10
    Last Post: 03-13-2009, 07:13 PM
  4. a point of threads to create multiple threads
    By v3dant in forum C Programming
    Replies: 3
    Last Post: 10-06-2004, 09:48 AM
  5. The "Psychedelic mushroon philosophers, armageddon, and singularity" thread
    By Scourfish in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 07-19-2002, 05:25 AM