a) Alice, Bob, and Carol go to a Chinese restaurant at a busy time of the day. T
ID: 3829627 • Letter: A
Question
a) Alice, Bob, and Carol go to a Chinese restaurant at a busy time of the day. The waiter apologetically explains that the restaurant can provide only two pairs of chopsticks (for a total of four chopsticks) to be shared among the three people. Alice proposes that all four chopsticks be placed in an empty glass at the center of the table and that each diner should obey the following protocol:
while (!had_enough_to_eat()) {
acquire_one_chopstick(); /* May block. */
acquire_one_chopstick(); /* May block. */
eat();
release_one_chopstick(); /* Does not block. */
release_one_chopstick(); /* Does not block. */
}
Can this dining plan lead to deadlock? Explain your answer.
b) Suppose now that instead of three diners there will be an arbitrary number, D. Furthermore, each diner may require a different number of chopsticks to eat. For example, it is possible that one of the diners is an octopus, who for some reason refuses to begin eating before acquiring eight chopsticks. The second parameter of this scenario is C, the number of chopsticks that would simultaneously satisfy the needs of all diners at the table. For example, Alice, Bob, Carol, and one octopus would result in C = 14. Each diner’s eating protocol will be as displayed below:
int s;
int num_sticks = my_chopstick_requirement();
while (!had_enough_to_eat()) {
for (s = 0; s < num_sticks; ++s) {
acquire_one_chopstick(); /* May block. */
}
eat();
for (s = 0; s < num_sticks; ++s) {
release_one_chopstick(); /* Does not block. */
}
}
What is the smallest number of chopsticks (in terms of D and C) needed to ensure that deadlock cannot occur? Explain your answer.
I found answers in this link: https://web.stanford.edu/~ouster/cgi-bin/cs140-winter16/downloads/Final%20(Winter%202012)%20Solution.pdf
The answer for question a is no. Deadlock cannot occur because there are enough chopsticks to guarantee that at least one of the 3 diners will be able to get the 2 chopsticks that he/she needs. Once that diner finishes, he/she will release their chopsticks for someone else to use, so eventually everyone finishes.
The answer for question b is C – D + 1. This guarantees that every diner can get all but one of the chopsticks it needs (C – D), with one additional chopstick to guarantee that at least one diner gets all of the chopsticks it needs. The D wants to eat and people need chopsticks with C.
But I cannot understand the question b answer, is there anyone can help me to understand it? Thanks!
Explanation / Answer
I will try to explain by an example,
Suppose there were three persons X, Y and Z, so here D=3 and their requirement for number of choopsticks are 3, 5, 4 respectively, so here C=12.
So when can a dead lock occur, only when all of the people are waiting to get another chopstick. suppose if we put 9 chopsticks, can a deadlock occur ? yes with X holding 2, Y holding 4 and Z holding 3 chopsticks and all the 3 waiting for another. What if we add one more chopstick there, then anyone would pick this chopstick and finish their eating so no deadlock.
The thing here is, when every diner is holding the chopsticks one less than the number they require, if we have an additional chopstick then any one diner can fulfill his requirement and so can prevent deadlock.
Now the calculation:
if the requirements for D diners are c1,c2,.....cD respectively, then we have c1+c2+ ....+cD = C.
The total number of chopsticks for every diner to get one less than what they require is (c1-1)+(c2-1)+....(cD-1) = C-D
so the answer is C-D+1(one more than that)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.