Practice Exam

Question 1

A lock that uses busy waiting is called a spin lock. What is the meaning of the term busy
waiting? Can busy waiting be avoided altogether? Explain your answer.

Answer 1

Busy waiting means that a process is waiting for a condition to be satisfied in a tight loop
without relinquish the processor.
Alternatively, a process could wait by relinquishing the processor, and block on a condition
and wait to be awakened at some appropriate time in the future.
Busy waiting can be avoided but incurs the overhead associated with putting a process to
sleep and having to wake it up when the appropriate program state is reached.

Question 2

Consider the following Petersons solution for mutual exclusion.
flag[ME] = TRUE;/* declare interest /
turn = ME; / for race condition /
while ((flag[1-ME]==TRUE) && (turn == ME)) ;
CS();
flag[ME] = FALSE; / release */
Non_CS();
Is the Peterson’s solution susceptible to the busy waiting problem? Explain your answer with
respect to the code above.

Answer 2

Yes, the following code results in busy waiting:
while ((flag[1-ME]==TRUE) && (turn == ME))

Question 3

Consider the following solution to the Dining Philosopher’s problem:
while (TRUE) { /* philosopher i loop */
UP(chopstick[i]);
UP(chopstick[i+1 mod N]);
eat();
DOWN(chopstick[i]);
DOWN(chopstick[i+1 mod N]);
think();
}
Question 3a:
Explain why deadlocks occur in the solution above.

Answer 3

Every philosopher runs in lock-step. First everyone picks up their chopstick[i]. Then
everyone tries to get chopstick[i+1 mod N], but that’s someone else’s
chopstick[i], which is in use.

Question 4

For the solution to the Dining Philosopher’s problem described above in the introduction to
Question 3, briefly explain, in words, a modification to the above solution such that
deadlocks are prevented without sacrificing concurrency.
This question is worth 3 points

Answer 4

Feedback:
Your solution must state that one or more philosophers look for forks in the opposite order
from the rest.

Question 5

Question 3c
One solution to the Dining Philosopher’s Problem that avoids deadlocks and achieve
fairness is the use of a “token-ring solution”, in which each philosopher eats in a round robin
fashion, whereby a philosopher eats, and then releases its chopsticks to its adjacent
philosopher in the clockwise (or counter-clockwise direction).
Name the main disadvantage of this token-ring solution to the Dining Philosopher’s
problem.
This question is worth 2 points.

Answer 5

Lack of concurrency, since only one philosopher can eat at any time.

Question 6

Consider the following precedence constraints that must be satisfied for the execution of
processes P1, P2, P3, P4 and P5:
● P1 can start any time.
● P2 can start after P1 completes.
● P4 can start after P2 completes.
● P3 can start after P1 completes.
● P5 can start after P3 completes.
Note: if two processes pi and pj have no precedence constraints with respect to each other,
either one of them can run first. In addition, on a multi-processor, pi and pj are allowed to run
simultaneously.
Using a minimal number of counting semaphores (all initialized to 0) and minimal number of
semaphore operations, explain how these precedence constraints can be enforced without
restricting simultaneous execution stated above. Deadlocks should not occur in your
solution.
P1 P2 P3 P4 P5
P1 code (a) P(S1) (c) P(S3)
V(S1) P2 code P3 code P4 code P5 code
V(S1) V(S2) (b)
Question 4a:
What is the value of part (a) in the table above? Select the best answer.
a. P(S1)
b. P(S2)
c. V(S1)
d. V(S2)
This question is worth 2 points.

Answer 6

Solution: P(S1)

Question 7

Using the same setup as Question 4 described above, what is the value of part (b)? Select
the best answer.
The table from Question 4 is reproduced here:
P1 P2 P3 P4 P5
P1 code (a) P(S1) (c) P(S3)
V(S1) P2 code P3 code P4 code P5 code
V(S1) V(S2) (b)
a. P(S2)
b. P(S3)
c. V(S2)
d. V(S3)
This question is worth 2 points.

Answer 7

Solution: V(S3)

Question 8

Using the same setup as Question 4 described above, what is the value of part (c)? Select
the best answer.
The table from Question 4 is reproduced here:
P1 P2 P3 P4 P5
P1 code (a) P(S1) (c) P(S3)
V(S1) P2 code P3 code P4 code P5 code
V(S1) V(S2) (b)
a. P(S2)
b. P(S3)
c. V(S2)
d. V(S3)
This question is worth 2 points.

Answer 8

Solution: P(S2)