Threads: Starving Philosopher

From: William Kempf (sirwillard_at_[hidden])
Date: 2000-08-24 17:05:42

I've been looking at the site that Greg provided, 
http://www.cs.ukc.ac.uk/projects/ofa/java-threads/0.html.  The "Wot, 
no chickens?" example was quite interesting, and out of curiosity I 
ran it through my Win32 implementation of the current Boost models.  
The code can be found below.

Unfortunately, but not surprisingly since the page claims the fault 
is in the FIFO ordering queue, the test code starved my philosopher!  
This example just further shows how traditional threading techniques 
are error prone and difficult to use safely.  The monitor pattern 
didn't help at all here, and in fact the above site claims the 
pattern is the cause of the problem.

The site piqued my interest in CSP.  This is a concurrent programming 
technique/mathematical model that I've not heard of until today.  I'd 
be very interested in learning more about it, and it sounds like it's 
something that should be discussed here.  Is anyone familiar with 
books on the subject (preferably books for mere mortals... the heady 
stuff loses me until I've gotten used to the concepts)?  Is anyone 
aware of any C or (preferably) C++ implementations of CSP?  I've 
found a reference that says that the University of Twente has C/C++ 
libraries in addition to the Java libraries available at 
http://www.rt.el.utwente.nl/javapp, but there's no reference to the 
C/C++ libraries that I can find there.

Bill Kempf

["Wot, no chickens?" for Win32... Phil0 starves to death!]

#include "mutex.h"
#include "condition.h"
#include <iostream>
#include <time.h>

class canteen
{
public:
        canteen() : m_chickens(0) { }

        void get(int id)
        {
                boost::mutex::lock lock(m_mutex);
                while (m_chickens == 0)
                {
                        std::cout << "(" << clock() << ") Phil" << id 
<<
                                ": wot, no chickens?  I'll WAIT ..." 
<< std::endl;
                        m_condition.wait(m_mutex);
                }
                std::cout << "(" << clock() << ") Phil" << id <<
                        ": those chickens look good ... one 
please ..." << std::endl;
                m_chickens--;
        }
        void put(int value)
        {
                boost::mutex::lock lock(m_mutex);
                std::cout << "(" << clock() <<
                        ") Chef: ouch ... make room ... this dish is 
very hot ..." << std::endl;
                Sleep(3000);
                m_chickens += value;
                std::cout << "(" << clock() <<
                        ") Chef: more chickens ... " << m_chickens <<
                        " now available ... NOTIFYING ..." << 
std::endl;
                m_condition.notify_all();
        }

private:
        boost::mutex m_mutex;
        boost::condition m_condition;
        int m_chickens;
};

canteen g_canteen;

unsigned __stdcall chef(void*)
{
        const int chickens = 4;
        std::cout << "(" << clock() << ") Chef: starting ..." << 
std::endl;
        for (;;)
        {
                std::cout << "(" << clock() << ") Chef: cooking ..." 
<< std::endl;
                Sleep(2000);
                std::cout << "(" << clock() << ") Chef: " << chickens
                        << " chickens, ready-to-go ..." << std::endl;
                g_canteen.put(chickens);
        }
        return 0;
}

unsigned __stdcall phil(void* parm)
{
        int id = (int)parm;
        std::cout << "(" << clock() << ") Phil" << id << ": 
starting ..." << std::endl;
        for (;;)
        {
                if (id > 0)
                        Sleep(3000);
                std::cout << "(" << clock() << ") Phil" << id
                        << ": gotta eat ..." << std::endl;
                g_canteen.get(id);
                std::cout << "(" << clock() << ") Phil" << id
                        << ": mmm ... that's good ..." << std::endl;
        }
        return 0;
}

void test_starving_philosopher()
{
        unsigned addr;
        HANDLE hThreads[6];
        hThreads[0] = (HANDLE)_beginthreadex(0, 0, chef, 0, 0, &addr);
        hThreads[1] = (HANDLE)_beginthreadex(0, 0, phil, 0, 0, &addr);
        hThreads[2] = (HANDLE)_beginthreadex(0, 0, phil, (void*)1, 0, 
&addr);
        hThreads[3] = (HANDLE)_beginthreadex(0, 0, phil, (void*)2, 0, 
&addr);
        hThreads[4] = (HANDLE)_beginthreadex(0, 0, phil, (void*)3, 0, 
&addr);
        hThreads[5] = (HANDLE)_beginthreadex(0, 0, phil, (void*)4, 0, 
&addr);
        WaitForMultipleObjects(6, hThreads, TRUE, INFINITE);
}