Home Download Register Become an Affiliate Contact
Examples Submenu
Dining Philosophers
Up
Oven
Calculator
Mad Minutes Test
Text Messenger
Two Communicating Objects
Dining Philosophers

 
 






Dining Philosophers


This example implements a solution to the classic Dijkstra's Dining Philosophers problem (DPP). It also illustrates instantiating of active objects from a template (class) and working with timers.

Below is the DPP description from Samek, M. Practical Statecharts in C++ (p. 191):

DPP illustrates basic challenges of multithreading. Several (originally 5) philosophers are gathered around a table with a big plate of spaghetti in the middle. The spaghetti is so slippery that a philosopher needs two forks to eat it. Between each philosopher is a fork. The life of a philosopher consists of alternate periods of thinking and eating. When a philosopher wants to eat, he tries to acquire forks. If successful in acquiring two forks, he eats for a while, then puts down the forks and continues to think. The key question is : Can you write a program for each philosopher that never gets stuck?

The problem is actually about resource allocation and its main pitfalls: race conditions, deadlock and starvation. An attempt to prevent them can cause more subtle problems assosiated with fairness and suboptimal system utilization.

Start this VI and it will create as many philosopher objects as there are elements in
Philosophers, Thinking Time, and Eating Time Arrays. The number of elements in these arrays needs to be the same, of course. The Is Hungry? and Forks in Use arrays will be scaled automatically.

The philosopher's individual VI windows will open on top of each other, so you have to drag them and place around your screen to see the whole picture. You can change philosopher's individual eating and thinking times from the initial values defined in the main VI.

Please note that this solution, though free of concurrency hazards, does not provide fairness! Increase, say, eating time of one philosopher and you will see how neighbors of that selfish bastard start piling up their hungry time. Fairness can be added by introducing a Forks Taken Away event sent from Table to Philosopher and keeping track of hungry and eating times for each philosopher in the Table/Butler Object. Then some criterion of fairness has to be chosen and implemented in the Table object to decide when to take away forks (preempt processes) and to whom they should be given.
 


      Back  
Universal HSM Template | LabHSM Editor | Getting Started | Tutorials | Included Examples | Links/References
2004-2005 H View Labs, Inc. All rights reserved.