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

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

Quote:

---

Originally Posted by Salem

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

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.

Quote:

---

Originally Posted by Salem

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 )

Quote:

---

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 ?

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

---

Quote:

---

Originally Posted by oogabooga

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.

Quote:

---

[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

---

Quote:

---

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.

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;

---

Or "(n + 1) % nump".

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

gg

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

---

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

Multithreading in C++0x part 7: Locking multiple mutexes without deadlock | Just Software Solutions - Custom Software Development and Website Development in West Cornwall, UK
You would use std::try_lock in this case.

In log(), just use a std::lock_guard.

Line 58: You could randomize this as well.

gg