Solving Starvation in Dining Philosopher Problem: Using Inverse Semaphore

• Download demo project - 8.62 KB
• Download source - 22.17 KB

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.

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.

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

• 2^nd June, 2008: Initial post