《Operating System Concepts》中临界区问题：退出区进程能否影响临界区调度决策？

Great question—this cuts right to the tradeoffs between fairness, efficiency, and correctness in critical section synchronization, a core topic in Operating System Concepts. The short answer: Yes, and many classic synchronization mechanisms are explicitly designed this way—though there are simpler (but less ideal) approaches where this doesn’t happen.

Why Allow This Influence? #

The critical section problem has three non-negotiable requirements: mutual exclusion, progress, and bounded waiting. Let’s tie this design choice to those rules:

• Bounded waiting: If the exiting process can explicitly wake or select the next process, we guarantee no process gets stuck waiting forever (no starvation). This directly enforces the bounded waiting condition.
• Efficiency: Instead of making all waiting processes waste CPU cycles polling the lock (busy waiting), the exiting process knows the critical section is free and can immediately trigger the next process to run. This cuts down on unnecessary overhead.

Examples from Classic Mechanisms #

Let’s look at how this plays out in the book’s key examples:

1. Peterson’s Algorithm #

In Peterson’s solution, the exiting process sets the turn variable to the other process’s ID. This is a direct, explicit choice: the exiting process is telling the system exactly which process gets to enter next. No ambiguity, no luck—just a clear handoff.

2. Queue-Based Semaphores (Dijkstra’s Implementation) #

When a process calls signal() (the exit operation for semaphores), it pulls the first process from the semaphore’s waiting queue and wakes it up. Here, the exiting process’s action directly determines which process enters the critical section next—strictly following a FIFO order, which ensures fairness.

3. Monitors with Condition Variables #

When a process exits the monitor and calls signal() on a condition variable, it wakes one of the processes waiting on that condition (most implementations pick the first in line). Again, the exiting process is actively influencing the next process’s selection, rather than leaving it to random polling.

When Would We Not Allow This Influence? #

The main case is simple spin locks (like those using test-and-set). Here, the exiting process just sets the lock variable to "available" and walks away. All waiting processes are stuck in a loop, checking the lock repeatedly. The first one to see the lock free grabs it—this is entirely dependent on scheduling luck or priority, not any choice by the exiting process.

The problem with this approach? It violates bounded waiting (a process could theoretically wait forever) and wastes CPU cycles on busy waiting. It’s simple, but not ideal for most real-world systems.

The Key Tradeoff #

Allowing the exiting process to influence the next selection is about balancing fairness and efficiency:

• Fairness: By using a queue or explicit turn-taking, we ensure every process gets a shot at the critical section, no starvation.
• Efficiency: We eliminate the overhead of busy waiting, letting the system transition smoothly from one critical section execution to the next.

Skipping this influence might make the implementation simpler, but it comes at the cost of fairness and wasted resources.

内容的提问来源于stack exchange，提问作者Ahmad Naseem