Chapter 6, Problem 18 Operating Systems: Internals and Design Principles Systems

Question

Chapter 6, Problem 18

Operating Systems: Internals and Design Principles Systems, 7th Edition (Textbook Solutions)

Author: William Stallings

______________

Suppose that there are two types of philosphers. One type always picks up his left fork first (a "lefty"), and the other type always picks up his right fork first (a "righty"). The behavior of a left is defined in Figure 6.12. The behavior of a righty is as follows:

begin

repeat

think;

wait (fork[(i+1) mod 5]);

wait (fork[i]);

eat;

signal (fork[i]);

signal (fork[(i+1) mod 5]);

forever

end;

Prove the following:

a. Any seating arrangement of lefties and righties with at least one of each avoids deadlock.

b. Any seating arrangement of lefties and righties with at least one of each prevents starvation.

Figure 6.12

------------------------

/*program dining philopsheres*/

semaphore fork [5] = {1};

int i;

void philosopher (int i){

while(true){

think();

wait( fork [i]);

wait( fork [(i+1) mod 5]);

eat();

signal (fork [(i+1) mod 5]);

signal (fork[i]);

}

}

void main(){

parbegin (philosopher (0), philosopher (1), philosopher (2), philosopher (3), philosopher (4));

}

-----------------------

Explanation / Answer

a. To avoid the deadlock the circular wait must be prevented by the arrangement. The seating arrangement having the minimum of one lefties and righties avoids the deadlock because at least one of thenm has different behaviour, this prevents the circular wait because one of them holds nothing atleast at a time. This condition is because the ones with different behavior will select from the right first which is the left fork of the adjacent philosopher,hence if all the lefties philosophers pick the left fork, the one with dissimilar behavior will not select any fork as he cannot access his right fork.

b. Assume that in the dining pattern Lj never eats , and if Lj does not holds fork, then Lj's left neighbour Li holds the right fork and not completes its eating , Hence Li is holding right fork and will not allow its left fork to finish , therefore Li will suffer from starvation. Then if Li's left neighbour righty will hold right fork, and by moving to the left side it is observed that philosophers righties are starving . but since Lj is lefty , it holds one fork , it waits for its right neighbour Lk who never finishes his meal and thus Lk also starves. Now moving this argument rightward it is found that philosophers starving are lefties . It is a contradiction and hence starvation is precluded.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.