12,298,463 members (48,627 online)
Article
Add your own
alternative version

36.4K views
1.3K downloads
7 bookmarked
Posted

# Solving Starvation in Dining Philosopher Problem: Using Inverse Semaphore

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

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

• 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)

## About the Author

 Software Developer (Senior) IBM India
No Biography provided

## Comments and Discussions

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