Operating System Concepts discusses two implementations of a semaphore, by busy waiting in Section 5.5 and by blocking the current process in Section 5.6:
Section 5.5
A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait() and signal(). The wait() operation was originally termed P (from the Dutch proberen, “to test”); signal() was originally called V (from verhogen, “to increment”). The definition of wait() is as follows:
wait(S) { while (S <= 0) ; // busy wait S--; }The definition of signal() is as follows:
signal(S) { S++; }Section 5.6
Recall that the implementation of mutex locks discussed in Section 5.5 suffers from busy waiting. The definitions of the wait() and signal() semaphore operations just described present the same problem. To overcome the need for busy waiting, we can modify the definition of the wait() and signal() operations as follows: When a process executes the wait() operation and finds that the semaphore value is not positive, it must wait. However, rather than engaging in busy waiting, the process can block itself. The block operation places a process into a waiting queue associated with the semaphore, and the state of the process is switched to the waiting state. Then control is transferred to the CPU scheduler, which selects another process to execute.
To implement semaphores under this definition, we define a semaphore as follows:
typedef struct { int value; struct process *list; } semaphore;Each semaphore has an integer value and a list of processes list. When a process must wait on a semaphore, it is added to the list of processes. A signal() operation removes one process from the list of waiting processes and awakens that process.
Now, the wait() semaphore operation can be defined as
wait(semaphore *S) { S->value--; if (S->value < 0) { add this process to S->list; block(); } }and the signal() semaphore operation can be defined as
signal(semaphore *S) { S->value++; if (S->value <= 0) { remove a process P from S->list; wakeup(P); } }The block() operation suspends the process that invokes it. The wakeup(P) operation resumes the execution of a blocked process P. These two operations are provided by the operating system as basic system calls.
It is critical that semaphore operations be executed atomically. We must guarantee that no two processes can execute wait() and signal() operations on the same semaphore at the same time. This is a critical-section problem;
It is important to admit that we have not completely eliminated busy waiting with this definition of the wait() and signal() operations. Rather, we have moved busy waiting from the entry section to the critical sections of application programs. Furthermore, we have limited busy waiting to the critical sections of the wait() and signal() operations, and these sections are short (if properly coded, they should be no more than about ten instructions). Thus, the critical section is almost never occupied, and busy waiting occurs rarely, and then for only a short time.
Questions about the last paragraph:
In "moved busy waiting from the entry section to the critical sections of application programs", assume "the application program" is:
do { wait(S) // entry section <critical section> signal(S) // exit section <remainder section> } while (true);- where is the busy waiting in "the critical sections of application programs" that is moved from the entry section?
In "we have limited busy waiting to the critical sections of the wait() and signal() operations",
what are "the critical sections of the wait() and signal() operations"? Are they the entire function bodies of wait() and signal()? (I guess so, because the two functions must be atomic, mentioned in the paragraph before the last.)
Where is "busy waiting" which is limited to the critical sections of the wait() and signal() operations? (There is no loop inside wait() and signal(), so I guess no busy waiting in them?)
Thanks.
