Six philosophers with six chopsticks
The dining table has 6 people with 6 chopsticks (may use different people and chopsticks number). Six people sit around a table with a single chop stick between each two adjacent people. A single bowl is placed in front of each of them. Two chopsticks (on his left and right) must be in hand in order to eat noodle. After he eats a bit of rice, he puts the chop sticks down for some time and thinks for another amount of time. He repeats this process over and over again. As can be seen, there are only six chop sticks. Deadlock is obviously possible in this case. For instance, each of them grabs a chopstick on his right. But, he cannot eat as there is no longer any chopstick to his left. So, each diner waits for a left chopstick that may never arrive.
Starvation Issue
Imagine that two diners are quick thinkers and quick eaters. They think faster
and get hungry faster. Assume that, they are sitting down in the opposite chairs
as shown below.
Because they are so fast, it is possible that they can lock their chopsticks and eat. After finish eating and before their neighbors can lock the chopsticks and eat, they start again and lock the chopsticks and eat. In this case, the other four diners, even though they have been sitting for a long time, they have no chance to eat. This is called a starvation. Note that it is not a deadlock because there is no circular waiting, and everyone has a chance to eat. Starvation happens when some thread gets deferred forever and violates the idea of fairness which each thread gets a turn to make progress. This just a simple example of starvation because you can find more complicated thinking-eating sequence that also can generates starvation.
The Six philosophers with Semaphore Program Example
The following solution to the problem using semaphore is based on the principle that, six chop sticks can only be used by three people, restricting only maximum three people that can attempt to eat at any one time.
Create a new empty Win32 console application project. Give a suitable project name and change the project location if needed.
Then, add the source file and give it a suitable name.
Next, add the following source code.
// Solution to 6 diners with 6 chopsticks problem using semaphores
#include <windows.h>
#include <stdio.h>
#include <wchar.h>
#include <assert.h>
#define Diners 6
// Global variables
// handle to see who attempts to eat
HANDLE hSemEat=NULL;
// binary semaphores for each chop stick
HANDLE hSemChopSticks[Diners];
// Handle to Philosophers
HANDLE hDiners[Diners];
// tell philosophers to stop
BOOL bStopDiners[Diners];
//////////Thread Code /////////
// Id from 0 to Diners-1
void DinerNum(int Id)
{
// Can discard the limit for forever eating & thinking i.e. for(;;)
for(;;)
{
wprintf(L Diner #%d - Thinking, not enough chopsticks...\n, Id);
if(bStopDiners[Id] == TRUE)
{
ExitThread(0);
}
// Wait till turn to eat/signaled
WaitForSingleObject(hSemEat,INFINITE);
// Pick chopsticks
WaitForSingleObject(hSemChopSticks[Id],INFINITE);
WaitForSingleObject(hSemChopSticks[(Id+1)%Diners],INFINITE);
wprintf(L Diner #%d - Eating with two chopsticks...\n, Id);
// Put down chopsticks
ReleaseSemaphore(hSemChopSticks[(Id+1)%Diners],1,NULL);
ReleaseSemaphore(hSemChopSticks[Id],1,NULL);
// Release the right to eat
ReleaseSemaphore(hSemEat,1,NULL);
}
}
//////////// Create the diners /////////////
void CreateDiners(void)
{
int i;
for(i=0;i<Diners;++i)
{
DWORD dwThreadID;
// set flag off for stopping
bStopDiners[i]=FALSE;
hDiners[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)DinerNum,(LPVOID)i,0,&dwThreadID);
assert(hDiners[i]!=NULL);
}
}
////////////CreateSemaphores//////////
void CreateSemaphores(void)
{
int i;
// create eating semaphore
// Initial and max are set to 3
hSemEat = CreateSemaphore(NULL,Diners/2,Diners/2,NULL);
assert(hSemEat!=NULL);
for(i=0;i<Diners;++i)
{
hSemChopSticks[i]=CreateSemaphore(NULL,1,1,NULL);
assert(hSemChopSticks[i]!=NULL);
}
}
///////////////////
void AttemptToStop(void)
{
int i;
wprintf(L\n=====Attempting to stop all threads=========\n\n);
for(i=0;i<Diners;++i)
{
bStopDiners[i]=TRUE;
}
// wait for all threads to finish
WaitForMultipleObjects(Diners,(CONST HANDLE *)hDiners,TRUE,INFINITE);
}
/////////Close All Handles//////////
void CloseAllHandles(void)
{
int i;
for(i=0;i<Diners;++i)
{
CloseHandle(hDiners[i]);
CloseHandle(hSemChopSticks[i]);
}
CloseHandle(hSemEat);
}
///// Main //////////
int wmain(void)
{
CreateSemaphores();
CreateDiners();
AttemptToStop();
CloseAllHandles();
ExitProcess(0);
return 0;
}
Build and run the project. The following screenshot is a sample output.