Gyanrush
Start freeOpen Gyanrush
Start freeOpen Gyanrush
  1. LPU MCA Semester 1
  2. CAP366
  3. Unit 5

CAP366 · Unit 5: Process synchronization

The critical section problem

12 practice questions · in the MTE and ETE syllabus

Practise this topicPractise this topic

Key points

  • Three requirements: mutual exclusion, progress, bounded waiting
  • Peterson: flag array + turn variable
  • Strict alternation violates progress
  • Test-then-set without atomicity violates mutual exclusion

A solution must satisfy three requirements:

  1. Mutual exclusion: at most one process in its critical section.
  2. Progress: if no process is in its critical section, only the processes wanting entry take part in choosing the next one, and the choice cannot be postponed indefinitely.
  3. Bounded waiting: a limit on how often others may enter after a process has requested entry.

Peterson's solution (two processes): flag[i] = true; turn = j; while (flag[j] && turn == j); ... flag[i] = false. If both set their flags, the last write to turn decides: that process waits, the other enters.

AttemptFails
Strict alternation (turn only)Progress
Plain lock flag (test then set)Mutual exclusion

A non-preemptive kernel is free of kernel race conditions on one CPU.

Exam pitfall: hardware atomic instructions and semaphores are tools to build solutions, not requirements.

Try two questions

Question 1 · Tier 1, Recall

Mutual exclusion means:

  1. Every process must enter its critical section once
  2. The compiler keeps critical sections short so conflicts cannot arise
  3. Processes are admitted to the critical section in FIFO order
  4. At most one process can be in its critical section at a time
Show the answer

D. It prevents conflicting simultaneous updates of shared data.

Question 2 · Tier 3, Apply

Peterson's solution: each Pi sets flag[i] = true, then turn = j, then waits while (flag[j] && turn == j). P0 sets flag[0] and turn = 1; then P1 sets flag[1] and turn = 0. Who enters the critical section first?

  1. P0 enters and P1 waits
  2. Neither enters (deadlock)
  3. P1 enters and P0 waits
  4. Both enter at the same time
Show the answer

A. turn ends as 0, so P0's loop condition (flag[1] && turn == 1) is false and it enters. P1's condition (flag[0] && turn == 0) is true so it waits. Both cannot enter, which is what the turn variable guarantees.