CFGReader

Dining philosopher problem

    A. First Edition

    I am practicing with multi-thread.

    B.The problem

    Five philosophers are sitting around a table, each with one chopstick on table. They keep thinking and eat rice

    when they feel hungry. When they want to eat, they have to pick up the chopstick in front of him and another

    one from either left or right of him. However, there exists a potential dead-lock problem such that when all of

    them are hungry and try to pick up chopstick and wait for the one from left of them. How to solve this classic

    synchronization problem?

กก

C.The idea of program
กก

    Each philosopher must have three states to represent him to be "thinking, eating, hungry". And each of them has

    a semaphore. Besides that there is a shared mutex to allow only one of them update the state of him in an atomic

    manner. The algorithm is given in Dr. Sinha's slides and I translate them into C++ with little modifications.

    1. When picking chopstick, philosopher must enter an atomic block to change his state to "hungry" state which

    differs him from "thinking" and "eating" state. Then he must test to see if NOT both left and right of him is

    in "eating" states which means that he is guaranteed to pick up one more chopstick from either side. And signal

    his semaphore after the test successful.

    2. He then must wait for semaphore because it is possible that some other philosopher might already have been

    waiting for that chopstick. If this is the case, he must wait for either of left or right side is released.

    3. When a philosopher finished eating, it is his duty to notify both left and right hand side of him, if they

    are in waiting state----"hungry".

    D.The major functions

    E.Further improvement

    One of big problem is synchronization with "std cout". You see, my thread is messed up when they use "cout" for

    display. I guess the reason is that I/O is extremely slow and context switch between threads is not synchronized

    with output. So, I have to store all result in an array called "log". And display it only after threads terminate.

    F.File listing

    1. main.cpp (main)

    กก

    กก

    file name: main.h

    #include <iostream>
    #include <windows.h>

    using namespace std;

    const int mainIndex=100;
    const int PhiNumber=5;
    int counter=50;
    int log[500];
    int logIndex=0;

    #define LEFT(i) ((i-1)%PhiNumber)
    #define RIGHT(i) ((i+1)%PhiNumber)

    enum State
    {THINKING, EATING, HUNGERY};
    char* stateStr[3]= {"THINKING", "EATING", "HUNGERY"};

    HANDLE phis[PhiNumber];
    HANDLE sems[PhiNumber];
    HANDLE mutex;
    HANDLE display;
    State states[PhiNumber];
    int index[PhiNumber];

    void initialize();

    DWORD WINAPI run(void* param);

    void think(int i);
    void eat(int i);
    void pickFork(int i);
    void putFork(int i);
    void test(int i);

    int main()
    {
    	initialize();
    	while (counter>0)
    	{
    		Sleep(0);

    		WaitForSingleObject(display, INFINITE);
    		//log[logIndex++]=mainIndex;
    		for (int i=0; i<PhiNumber; i++)
    		{
    			log[logIndex++]=states[i];
    		}
    		ReleaseMutex(display);

    		/*
    		WaitForSingleObject(display, INFINITE);
    		cout<<"now the philosphors are in \n";
    		for (int i=0; i<PhiNumber; i++)
    		{
    			cout<<stateStr[states[i]]<<",";
    		}
    		cout<<"\n";
    		ReleaseMutex(display);
    		Sleep(0);
    		*/
    	}
    	for (int i=0; i<PhiNumber; i++)
    	{
    		CloseHandle(sems[i]);
    		CloseHandle(phis[i]);
    	}
    	i=0;
    	cout<<"now it is what main observes\n";
    	while (i<logIndex)
    	{
    		cout<<"mainthread observes that\n";
    		for (int j=0; j<PhiNumber; j++)
    		{
    			cout<<"philosophor "<<j<<" is "<<stateStr[log[i++]]<<endl;
    		}
    		/*
    		cout<<"philosophor "<<log[i];
    		i++;
    		cout<<" says he is "<<stateStr[log[i]]<<endl;
    		i++;
    		*/
    		//cout<<"philosophor "<<log[i++]<<" says he is "<<stateStr[log[i++]]<<endl;
    		/*
    		if (log[i]!=mainIndex)
    		{
    			cout<<"philosophor "<<log[i++]<<" says he is "<<stateStr[log[i++]]<<endl;
    		}
    		else
    		{
    			cout<<"mainthread observes that\n";
    			for (int j=0; j<PhiNumber; j++)
    			{
    				cout<<"philosophor "<<j<<" is "<<stateStr[log[++i]]<<endl;
    			}
    		}
    		*/
    	}

    	return 0;
    }

    void initialize()
    {
    	for (int i=0; i<PhiNumber; i++)
    	{
    		index[i]=i;
    		sems[i]=CreateSemaphore(NULL, 0, PhiNumber-1, NULL);
    		phis[i]=CreateThread(NULL, 0, run, index+i, 0, NULL);
    		display=CreateMutex(NULL, false, NULL);
    		states[i]=THINKING;
    	}
    	mutex=CreateMutex(NULL, false, NULL);
    }

    DWORD WINAPI run(void* param)
    {
    	while (counter>0)
    	{
    		think(*((int*)(param)));
    		pickFork(*((int*)(param)));
    		eat(*((int*)(param)));
    		putFork(*((int*)(param)));
    		counter--;
    	}
    	return *((int*)(param));
    }

    void test(int i)
    {
    	if (states[i]==HUNGERY&&states[LEFT(i)]!=EATING&&states[RIGHT(i)]!=EATING)
    	{
    		states[i]=EATING;
    		ReleaseSemaphore(sems[i], 1, NULL);
    	}
    }

    void pickFork(int i)
    {
    	WaitForSingleObject(mutex, INFINITE);
    	states[i]=HUNGERY;
    	test(i);
    	ReleaseMutex(mutex);
    	WaitForSingleObject(sems[i], INFINITE);
    }

    void putFork(int i)
    {
    	WaitForSingleObject(mutex, INFINITE);

    	states[i]=THINKING;
    	test(LEFT(i));
    	test(RIGHT(i));

    	ReleaseMutex(mutex);
    }

    void think(int i)
    {
    	/*
    	WaitForSingleObject(display, INFINITE);
    	cout<<"philosopher "<<i<<" is thinking ...\n";
    	ReleaseMutex(display);
    	*/
    	/*
    	WaitForSingleObject(display, INFINITE);
    	log[logIndex++]=i;
    	log[logIndex++]=states[i];
    	ReleaseMutex(display);
    	*/
    	Sleep(0);
    }

    void eat(int i)
    {
    	/*
    	WaitForSingleObject(display, INFINITE);
    	cout<<"philosopher "<<i<<" is eating ...\n";
    	ReleaseMutex(display);
    	*/
    	/*
    	WaitForSingleObject(display, INFINITE);
    	log[logIndex++]=i;
    	log[logIndex++]=states[i];
    	ReleaseMutex(display);
    	*/
    	Sleep(0);
    }

    The input is something like following:

    Here is the result:

now it is what main observes
mainthread observes that
philosophor 0 is THINKING
philosophor 1 is THINKING
philosophor 2 is THINKING
philosophor 3 is THINKING
philosophor 4 is THINKING
mainthread observes that
philosophor 0 is EATING
philosophor 1 is HUNGERY
philosophor 2 is EATING
philosophor 3 is HUNGERY
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is THINKING
philosophor 1 is EATING
philosophor 2 is THINKING
philosophor 3 is EATING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is EATING
philosophor 1 is THINKING
philosophor 2 is EATING
philosophor 3 is THINKING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is THINKING
philosophor 1 is EATING
philosophor 2 is THINKING
philosophor 3 is EATING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is EATING
philosophor 1 is THINKING
philosophor 2 is EATING
philosophor 3 is THINKING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is THINKING
philosophor 1 is EATING
philosophor 2 is THINKING
philosophor 3 is EATING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is EATING
philosophor 1 is THINKING
philosophor 2 is EATING
philosophor 3 is THINKING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is THINKING
philosophor 1 is EATING
philosophor 2 is THINKING
philosophor 3 is EATING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is EATING
philosophor 1 is THINKING
philosophor 2 is EATING
philosophor 3 is THINKING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is THINKING
philosophor 1 is EATING
philosophor 2 is THINKING
philosophor 3 is EATING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is EATING
philosophor 1 is THINKING
philosophor 2 is EATING
philosophor 3 is THINKING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is THINKING
philosophor 1 is EATING
philosophor 2 is THINKING
philosophor 3 is EATING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is EATING
philosophor 1 is THINKING
philosophor 2 is EATING
philosophor 3 is THINKING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is THINKING
philosophor 1 is EATING
philosophor 2 is THINKING
philosophor 3 is EATING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is EATING
philosophor 1 is THINKING
philosophor 2 is EATING
philosophor 3 is THINKING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is THINKING
philosophor 1 is EATING
philosophor 2 is THINKING
philosophor 3 is EATING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is EATING
philosophor 1 is THINKING
philosophor 2 is EATING
philosophor 3 is THINKING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is THINKING
philosophor 1 is EATING
philosophor 2 is THINKING
philosophor 3 is EATING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is EATING
philosophor 1 is THINKING
philosophor 2 is EATING
philosophor 3 is THINKING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is THINKING
philosophor 1 is EATING
philosophor 2 is THINKING
philosophor 3 is EATING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is EATING
philosophor 1 is THINKING
philosophor 2 is EATING
philosophor 3 is THINKING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is THINKING
philosophor 1 is EATING
philosophor 2 is THINKING
philosophor 3 is EATING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is EATING
philosophor 1 is THINKING
philosophor 2 is EATING
philosophor 3 is THINKING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is THINKING
philosophor 1 is EATING
philosophor 2 is THINKING
philosophor 3 is EATING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is EATING
philosophor 1 is THINKING
philosophor 2 is EATING
philosophor 3 is THINKING
philosophor 4 is HUNGERY
mainthread observes that
philosophor 0 is THINKING
philosophor 1 is EATING
philosophor 2 is THINKING
philosophor 3 is EATING
philosophor 4 is HUNGERY
Press any key to continue