Dining philosopher problem
A. First Edition
I am practicing with multi-thread.
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?
กก
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".
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