信号量两种wait()实现辨析：哪种正确？先检查还是先减数值？

Great question—this is such a common sticking point when diving into semaphores, and it all comes down to what kind of semaphore you're working with. Both implementations are "correct," but they serve entirely different use cases, and the order of checking vs. decrementing is tied directly to their design goals.

1. The Busy-Wait (Integer Semaphore) Implementation #

First, let's break down the busy-wait version:

wait(S) {
    while (S <= 0) ; // Busy-wait loop
    S--;
}

This is the classic integer semaphore design, used in early systems or scenarios where you can't afford to block a process (like certain kernel-level critical sections where context switching isn't safe).

• It checks the semaphore value first: the process spins in a loop, wasting CPU cycles until S becomes positive (meaning a resource is available). Only then does it decrement S to claim the resource.
• The big downside here is busy-waiting: the process holds the CPU while doing nothing useful, which is inefficient for most user-space or general-purpose OS scenarios.

2. The Blocking (Record Semaphore) Implementation #

The second version is the modern, blocking record semaphore, which is what you'll almost always see in modern operating systems:

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add this process to S->list;
        block();
    }
}

This design prioritizes CPU efficiency by avoiding busy-waiting. Here's why the order is reversed:

• First, we decrement S->value to "reserve" a resource. This is a key part of the semaphore's semantic: S->value represents the number of available resources. When you call wait(), you're requesting one, so you immediately subtract 1.
• If the result is negative, that means there were no available resources left (we just "overdrew" the resource pool). The absolute value of S->value now tells you how many processes are waiting in the queue. We add the current process to the semaphore's wait list and block it (voluntarily give up the CPU so other processes can run).
• If the result is non-negative, we successfully claimed a resource, and the process continues executing.

Key Questions Answered #

Which implementation is correct? #

Both are correct for their intended use cases:

• Use the busy-wait version only when blocking is impossible (e.g., in interrupt handlers or minimal kernel code where context switching isn't allowed).
• Use the blocking version for almost all other scenarios—it's far more efficient and aligns with how modern OSes manage process scheduling.

Should I check first or decrement first? #

Again, it depends on the semaphore type:

• For integer (busy-wait) semaphores: You must check first. If you decremented first, you'd make S negative even when no resources are available, and the busy-wait loop would never exit correctly (since other processes incrementing S would only bring it back to 0, not positive).
• For record (blocking) semaphores: You must decrement first. This step is essential to the resource reservation logic—without it, you can't accurately track how many processes are waiting for resources.

A critical note for both implementations: The entire wait() operation must be atomic. If multiple processes execute wait() at the same time, you'll get race conditions (e.g., two processes checking S>0 simultaneously and both decrementing S when only one resource is available). OSes enforce atomicity via hardware support (like test-and-set instructions) or kernel-level locks.

内容的提问来源于stack exchange，提问作者Mohammad Mehdi Sarfejoo