“A Solution: Breaking the Dependency” improves upon the “Broken Solution”.
The Dining
Philosophers problem is a classic concurrency or synchronization problem in
Operating Systems. E. Dijkstra posed and solved this problem in 1965. In this
problem, there are 5 philosophers around a dining table and 5 forks available
for eating. The life of the philosophers consists of alternative period of
eating and thinking, and eating needs two forks (left and right). When
philosopher gets hungry, he/she tries to acquire two forks, eats for a while, and
then puts down the forks and continues to think.
The broken
solution is that when the philosopher is hungry, he/she picks up the left fork first
and waits for right fork, when gets it eats for a while and put both forks back
to the table (Arpaci-Dusseau &
Arpaci-Dusseau, 2014). The problem with this solution, because of which
it is called “broken”, is that if all philosophers pick up the forks to their
left and wait for the ones on the right, nobody will get to eat (as all forks
are already acquired) leading to a deadlock. This phenomenon can be said to be
“Circular Wait”.
The solution
“Breaking the Dependency” improves upon it by changing the way the forks are
acquired by one philosopher. More specifically, Philosopher 4 (or any other
philosopher) can be made to pick up the right fork first, instead of the one on
the left (Arpaci-Dusseau &
Arpaci-Dusseau, 2014).
void
getforks() {
if
(p == 4) {
sem_wait(forks[right(p)]);
sem_wait(forks[left(p)]);
}
else {
sem_wait(forks[left(p)]);
sem_wait(forks[right(p)]);
}
}
This will
avoid the deadlock because it will break the “Circular Wait” situation. At
least one philosopher will then be able to eat even if all are trying to
acquire forks for eating.
An alternate
solution to break the dependency would be to test (using a function) if both
right and left forks are free, before acquiring them (Tanenbaum, 2007). And
this also improves upon the broken solution.
void test(p)
{ /* p: philosopher number, from 0 to
N−1 */
if
(state[p] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=
EATING){
state[p] = EATING;
sem_post(forks[left(p)]);
sem_post(forks[right(p)]);
}
}
References:
Arpaci-Dusseau, R., & Arpaci-Dusseau, A. (2014).Semaphore,
Operating systems: Three easy pieces. Madison: Arpaci-Dusseau. Retrieved
from http://pages.cs.wisc.edu/~remzi/OSTEP/
Tanenbaum, A. S. (2007),
Modern operating systems. (2nd ed., pp. 173-176). Prentice Hall
PTR.
No comments:
Post a Comment
Was this post helpful? Ask any questions you have, I will try to answer them for you.