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
_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
