0

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:

  1. 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?
  2. 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.

1
  • 1
    Where did your assumption about the "critical sections of application programs" come from? I think it's just referring to the busy wait it already admitted is in the mutex operations, since mutexes are used to protect critical sections of code (here, operations on the semaphore variable and wait queue) – Useless Nov 9 '20 at 12:53
1

You're misinterpreting the text you quoted. The critical sections it is talking about are ones mentioned in the previous paragraph:

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.

  1. In "moved busy waiting from the entry section to the critical sections of application programs", assume "the application program" is:

    No, don't assume that, it's wrong. You already know where the critical section is, you mentioned it yourself:

  2. In "we have limited busy waiting to the critical sections of the wait() and signal() operations"

    That is (those are) the critical section. There's no need to introduce a hypothetical extra critical section that isn't in the text.

    • what are "the critical sections of the wait() and signal() operations"?

      What do you understand by "critical section"? What parts of the wait() and signal() operations need to be protected from concurrent access?

    • 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?)

      You already quoted the book as saying that mutexes (as defined at this stage of the book) use busy wait. Mutexes are presumably how the book expects you to protect the critical code sections from concurrent access. I don't know what the book has said about critical sections (please don't quote any more of it), but this is fairly clear even from Wikipedia

In summary:

  • The critical section is the code that mutates or accesses the semaphore data structure itself
  • This critical section of the code must be protected by a mutex
  • The mutex itself has a busy wait (according to the text, at this stage in the book)
  • This busy wait is executing in the application context (ie, in userspace)
3
  • Mutexes usually “just” protect a resource, and are often locked / unlocked within less than a microsecond. Semaphores can wait for ages until they are signalled. – gnasher729 Nov 11 '20 at 7:01
  • Yep, and in this case the resource is the semaphore state (the counter and the waitlist). It might have been clearer if the book didn't mix up critical sections with mutexes at all. – Useless Nov 11 '20 at 17:10
  • I have some doubts about this part as well. As I understand, we're trying to develop a mechanism to protect critical sections of our application programs. A semaphore is such a tool which limits the number of concurrent accesses to critical sections. Now, a semaphore itself has a critical section(the semaphore value and condition check) which must be performed atomically. For this we use mutex locks which use busy wait for blocking. My doubt is, at what point did the busy wait move from wait() and signal() calls to the critical section of application programs? – Jamāl Dec 6 '20 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.