Dinning-philosphers problem, solution using counting semaphore and fair scheduling

Hi All,

This query is not about linux kernel in any way, but rather is a very primitive question on scheduling and resource management principles, using the dinning-philosphers analogy. I assume, most of the people here would have faced such situation and hence thought of discussing this in this forum. Also, i think, learning such basic principle will help me understand the scheduling algorithms.

I also assume that every computer science student would have come across this classical problem of dinning philosphers problem[1], proposed by Dijkstra. I came across it long back but i never took it seriously, Now I have revisited this same topic and was wondering if using a counting semaphore with completely fair scheduling will solve both of the deadlock and starvation situations.

Going back to the classical case, lets assume that we still have just 5 philosphers gathered over weekend at some food joint, sitting in a round-table. The table has again just 5 forks laid out around their plates(please see the diagram in the link[1] below) and to eat that sphagetti, both forks are needed. These guys either talk or eat, nothing else(nobody's going anywhere). To avoid potential deadlock situation(considering each one took one left fork at the same time) and to avoid starvation(a slow philospher never gets a chance to eat, because he is so lazy, picking up the fork) and to improve efficiency(let 2 philosphers eat simultaneously), why not use a counting semaphore instead of binary semaphore. Also, to avoid starvation, lets use a round-robin scheduling. As, there is no point accessing one fork at a time, so, each fork will be paired and acquistion of a semaphore, entitles one to get a pair of forks.

The psuedo code is mentioned below:

int nforks; //total number of forks, 5 here Semaphore sem; //controls, who gets to eat
int num_philosphers; //total number of philosphers, 5 here
cfq_t queue; // some kind of waitqueue, At any moment, there will be

		// 3 elements(philosphers) in the queue

add_tail(queue); //add at the end
remove_head(queue); //remove from the front

if ((nfoks & 0x01) == 0x01)

	sem = (nforks -1) / 2;
else
	sem = (nforks) / 2;

// P(sem) returns 0, if a pair of forks were acquired, else some number // P(sem) and V(sem) has same classical concept philospher(i)

{
	philosphies();
	if (hungry) {
		if (P(sem) != 0) {
			add_tail(queue);
		} else {
			takeup_fork();
			eat();
			put_down_fork();
			V(sem);    	    // release the pair of forks
			remove_head(queue); // remove the philospher from
				            // the front
			add_tail(queue); // add myself on the queue, add
					 // at the tail of the queue
		}
	} else {
		remove_head(queue);
		add_tail(queue);
	} 
}

scheduler()

{
	int i;
	for (i = 0; i < num_philosphers; i++) 
		philospher(i);

}

Please share you thoughts, help me learn.

[1] http://en.wikipedia.org/wiki/Dining_philosophers_problem

Thanks much,
Kumar

the standard solution is to simply order the resources and require
everyone to request resources in that order. problem solved. don't make this into a bigger issue than it really is.

rday

========================================================================
Robert P. J. Day                                 Ottawa, Ontario, CANADA
                        http://crashcourse.ca

Twitter:                                       http://twitter.com/rpjday
LinkedIn:                               http://ca.linkedin.com/in/rpjday
========================================================================

Thank you for giving me some directions.