Wait Queues

To implement synchronization, processes sometimes need to wait until a resource or lock becomes available. For performance reason, we can not allow the process to just execute an empty loop (Busy wait). Thus, an additional responability that the OS must take on is to manage waiting queues, so that processes or threads can wait without using the CPU and be retrieved from the wait queue as soon as the resource that they are waiting for becomes available. This functionality is provided by the resource manager. See Process Resource Allocation.

In the algorithms discussed below, when WAIT() is executed, we mean that the process or thread is put in a queue and later retrieved when the tread issues a SIGNAL().

4.2.2. Possible Synchronization Solutions

Important

• Software solution
• Disable interrupts
• . . . Something new, with hardware support . . .

4.2.2.1. Software Solution

As we observed (Synchronization Requirements), simple user code lock implementations do not work. However, as is noted in many texts, there are some software algorithms (Dekker’s, Peterson’s and Bakery) that in some situation may be useful to provide synchronization solutions. These algorithms could be useful in virtual threading environments such as Java, Python, Perl, or Pthreads where the programming environment has some control over the scheduling of threads. However, there are restrictions on the usability of these algorithms as a general purpose synchronization framework.

1. Dekker’s and Peterson’s algorithms only work for two threads.
2. The bakery algorithm requires that we know the number of threads before execution.
3. They contain DoNothing() instructions as a waiting mechanism. It might be difficult to implement this to behave like the wait queues that the operating system provides.

4.2.2.2. Disable Interrupts

To execute the critical section:

disableInterrupts();
/* --------------- */
  Critical Section
/* --------------- */
enableInterrupts();

• This block interrupts for the whole computer
• Interrupts could be disabled arbitrarily long
• Do you trust ALL programmers this much?

How about operating system provided software locks using disabled interrupts?:

void get_lock(locked) {
    disableInterrupts();
    while( locked ) {
        enableInterrupts();
        WAIT();
        disableInterrupts();
    }
    locked = True
    enableInterrupts();
}

void release_lock(locked) {
    disableInterrupts();
    locked = False
    enableInterrupts();
    SIGNAL()
}

---

Is This Good Enough?

• Interrupts not disabled during whole critical section.

• Mostly easy for programmers:

  shared boolean lock;
  
  ...
  
  acquire_lock(lock);
  /* --------------- */
    Critical Section
  /* --------------- */
  release_lock(lock);
  

• What if programmers release a lock they don’t own? This could be solved with careful programming, but adds complexity.

• Remember: This blocks interrupts for processes using the CPU.

• For shared memory, multiprocessor system – interrupts for other CPU’s are not blocked.

• There might be a better solution.

4.2.2.3. Dijkstra’s Semaphore

• Proposed in 1965 by Edseger Dijkstra

• Conceptual OS mechanism, with no specific implementation defined (could be enter()/exit())

• Basis of all contemporary OS synchronization mechanisms

• A simple hardware based solution

• A semaphore, s, is a nonnegative integer variable that can only be changed or tested by these two indivisible functions:

  V(s): [s = s + 1]

  P(s): [while(s == 0) {WAIT()}; s = s - 1]

• V and P are the first letters of Dutch words. P (probern – to test) is used for acquiring the lock. V (verhogen – to increment) is used for releasing the lock.

• The square brackets [ ] here mean that the actions between the brackets is to be autonomous (not interruptible).

• The initial value of s determines how many simultaneous threads may hold the semaphore lock. Set s to 1 for a simple lock, called a binary lock or binary semaphore. Some problems allow for s to be larger than 1.