Click here to Skip to main content
Click here to Skip to main content

Solving Starvation in Dining Philosopher Problem: Using Inverse Semaphore

, 2 Jun 2008
Rate this:
Please Sign up or sign in to vote.
Multithreaded GUI solution for starvation in Dining Philosopher problem

Introduction

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.

Problem Definition

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.

Demo Screen

Solution

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.

CInverseSemaphore Class Diagram

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 semaphore. 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.

Logic

There are five threads, one for each philosopher and a Monitor thread.
In the CInverseSemaphore object (invsema) is a global variable, hence will be initialized first. The count is set to 2.

Entry Criteria

Each philosopher waits on an event, and this event is set by the Monitor thread.
The Monitor thread acts as a scheduler, which schedules the next set of philosophers to start eating.

//Entry Criteria
dwEvent =WaitForSingleObject(hndEvent[4],INFINITE);

Exit Criteria

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….

// Exit Criteria
EnterCriticalSection(&cs);
{
    sp[1] = 1;
    sp[0] = 1;

    invsema.UnGuard();
}
LeaveCriticalSection(&cs);

Once the event object is signalled in the Monitor thread, which by the way happens only when two threads (or Philosophers) call the UnGuard function.

Monitor Thread

The monitor thread waits on the InverseSempahore event which gets set as mentioned above in the exit criteria.

// Monitor waiting on the event found in inverse semaphore class
dwEvent = WaitForSingleObject(invsema.GetHandle(),INFINITE);

The invsema.GetHandle() function returns the event handle for the monitor to wait on.

Conclusion

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.

History

  • 2nd June, 2008: Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Bharath NS
Software Developer (Senior) IBM
India India
No Biography provided

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Mobile
Web01 | 2.8.140821.2 | Last Updated 2 Jun 2008
Article Copyright 2008 by Bharath NS
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid