GATE 2013

OPERATING SYSTEM QUESTION AND ANSWERS

1 What is a critical section?
Answer: A section of code that only one process at a time can be executing.


2 What is the critical-section problem?
Answer: To design an algorithm that allows at most one process into the critical section
at a time, without deadlock.

3 Why have critical sections of programs, as defined by authors?
Answer: To allow no more than one process in at a time.

4 List the constraints Dijkstra placed on solutions to the critical-section problem.
Answer:
a. Simultaneous execution is equivalent to sequential execution in unknown order.
b. Speeds of the processes are independent of each other.
c. A process in noncritical section can’t prevent other processes fromentering the critical
section.
d. Selection of admitting one process into critical section can’t be indefinitely postponed.

5 What three requirements must a solution to the critical-section problem satisfy?
Answer: Mutual exclusion, progress, bounded waiting.

6 What variable is common between the two processes in algorithm 1?
Answer: turn. Note that i and j are not variables.

7 What is wrong with algorithm 1?
Answer: Since algorithm 1 requires strict alternation of processes in the execution of the
critical section it does not satisfy the progress requirement.

8 What variable(s) is/are common between the two processes in algorithm 2?
Answer: A two-element boolean flag array.

9 What is wrong with algorithm 2? How do you prove it?
Answer: Violates the progress requirement (see page 168).

10 What variables are used in algorithm 3, which are common to both processes?
Answer: A two-element boolean array flag and turn.

11 What does execute “atomically” mean?
Answer: Executed as a group, with no context switches possible until all of the statements
in the group are completed.

12 Define the wait-(postpone) operation, wait(S).
Answer: While semaphore is nonpositive, wait; when semaphore becomes positive, subtract
one and exit.

13 Define the wakeup operation signal(S).
Answer: Add 1 to the semaphore.

14 Suppose we want to execute the statements S1, S2, and S3 in sequence, but that S2 has to be
executed exclusively for one process at a time. Write the code needed using semaphores.
Answer: Assume Q = 1 initially. S1; wait(Q); S2; signal(Q); S3