Question

Which of the following is a solution to the "Critical Section Problem" that satisfies mutual exclusion, progress, and bounded waiting?

• A. Peterson’s Solution
• B. Test-and-Set Lock (hardware-only)
• C. Busy Waiting
• D. Shared Memory without synchronization

Hint:

Peterson's solution is the "Gold Standard" for theoretical software synchronization, although it is limited to two processes and relies on the assumption that load/store operations are atomic.

Answer 1

The Correct Option is A

Concept:
The Critical Section Problem involves designing a protocol that processes can use to cooperate safely when sharing data. A valid solution must satisfy three requirements:
• Mutual Exclusion: If process $P_i$ is in its critical section, no other process can be in theirs.
• Progress: If no process is in the critical section and someone wants in, only those not in their remainder section can participate in the decision, and this decision cannot be postponed indefinitely.
• Bounded Waiting: There is a limit on the number of times other processes can enter the critical section after a process has made a request.

Step 1: Analyzing Peterson's Solution.
Peterson's solution is a classic software-based solution for two processes ($P_0$ and $P_1$). It uses two shared variables:
• int turn; (Indicates whose turn it is to enter)
• boolean flag[2]; (Indicates if a process is ready to enter) A process $P_i$ sets flag[i] = true and sets turn = j (giving the other process a chance). It enters the critical section only if flag[j] == false or turn == i.

Step 2: Verification of the conditions.

• Mutual Exclusion: Both cannot enter because turn can only be 0 or 1 at any given moment.
• Progress: The turn variable ensures that if someone wants to enter, a decision is made immediately based on who set the variable last.
• Bounded Waiting: Since a process sets turn to the other process upon entry, the waiting process will get to enter after at most one entry by the other process.

Step 3: Comparison with other options.
Hardware locks like "Test-and-Set" provide mutual exclusion but do not inherently guarantee bounded waiting without extra logic. "Busy Waiting" is a symptom/mechanism, not a complete solution, and "Shared Memory without synchronization" leads to race conditions.