Semaphores and mutexes

Semaphores and mutexes

The semaphore

In computing terms, a semaphore is a mechanism that can be used to coordinate between two or more processes. The semaphore consists of a counter and two operations, P (wait) and V (signal). The parts in bold must be atomic with respect to other processes.

    P(s, i) {
      while (1) {
        if (s>=i) {
          s-=i;
          break;
        }
      }
    }

    V(s, i) {
      s+=i;
    }

The initial value of the counter is the number of objects that are available. For example, a uart driver might use semaphores to communicate between an interrupt handler and a process that interprets the character stream. For incoming characters, the interrupt handler puts an incoming character into a circular buffer and signals the semaphore. The interpreter process waits for a character then processes it. In this case, the initial value of the semaphore is 0 (no characters available).

As shown, the P operation is a busy-waiting operation. In practice, an operating system usually implements a mechanism for removing waiting processes from the scheduler until the condition s>=i becomes true. The waiting processes are placed in a queue, which could be in FIFO order or ordered by the priority of the waiting processes.

In either case, a process that is waiting for a larger number of objects could prevent processes that request a smaller number from running, even though the objects are available. On the other hand, if the queue were ordered by the size of the request (smallest first), a process that waits for a larger number of objects could be permanently blocked.

In Xinu, the wait() and signal() functions use a fixed value of 1 for i. This conveniently sidesteps the multiple objects problem.

The semaphore as a mutual exclusion mechanism

A semaphore with an initial value of 1 can be used as a mutual exclusion mechanism (mutex). Unlike the uart example above, a single process waits for the semaphore, performs some computation that needs exclusivity, then signals the same semaphore. After the wait, the process is said to "occupy" the semaphore, and the signal operation releases it.

To be continued ...