Dining philosopher is a very old and well known problem first devised by Edgar Dijkstra.This problem is an example for concurrency in computing. More information on the problem itself can be found at Wikipedia. There is also an excellent article by Dr. Sai on the same Web site.
There are many solutions to the dining philosopher problem, but it happens that some of the solutions have a problem that is called Starvation.
Let us define it; starvation happens when a particular philosopher is not getting a chance to eat at regular intervals, there could be a scenario that one of the philosophers might overeat eventually leading to starvation of another philosopher, even though this addresses the deadlock issue. A similar thing is happening in the article written by Dr.Sai.
The solution presented here in this article uses what is called Inverse Semaphore.
Semaphore is a synchronization object, which is signalled when the count is greater than zero and non-signalled when the count is zero.
There could be scenarios when you want the opposite, as in this case where we are trying to solve the dining philosophers’ problem.
I have a class called
CInverseSemaphore which implements the Inverse
Semaphore and works satisfactorily for this problem.
As the class diagram of the Inverse
Semaphore class shows, we are using a
Critical_Section and an
Event, both of which are initialized by the constructor and relinquished in the destructor.
The constructor is used to initialize the maximum count (
m_MaxCount) of the
UnGuard function is used to decrement the count similar to
ReleaseSemaphore, but with the difference that once the count reaches zero the
Event is signalled, and the
WaitForSingleObject gets signalled which waits on the
Event handle which is returned by the
GetHandle function of the class.
There are five threads, one for each philosopher and a
CInverseSemaphore object (
invsema) is a global variable, hence will be initialized first. The count is set to
Each philosopher waits on an
event, and this
event is set by the
Monitor thread acts as a scheduler, which schedules the next set of philosophers to start eating.
The philosopher thread relinquishes the spoons that it is holding and calls the
UnGuard function which sets the
event object, which is used by the
Monitor thread. The code below tells the same story….
sp = 1;
sp = 1;
event object is signalled in the
Monitor thread, which by the way happens only when two threads (or Philosophers) call the
monitor thread waits on the
InverseSempahore event which gets set as mentioned above in the exit criteria.
dwEvent = WaitForSingleObject(invsema.GetHandle(),INFINITE);
invsema.GetHandle() function returns the
event handle for the
monitor to wait on.
This brings us to the end of the article. Hope you find it useful. Do let me know your comments / thoughts / suggestions which can be used to update this article.
- 2nd June, 2008: Initial post