12,816,401 members (27,982 online)
Article
alternative version

#### Stats

37.6K views
7 bookmarked
Posted 2 Jun 2008

# Solving Starvation in Dining Philosopher Problem: Using Inverse Semaphore

, 2 Jun 2008 CPOL
 Rate this:
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.

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

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

## Share

 Software Developer (Senior) IBM India
No Biography provided

## You may also be interested in...

 Pro Pro