Semaphores, Mutexes and Monitors: short notes (Operating Systems)

Revision mode

Introduction

Peterson's algorithm and TestAndSet loops solve mutual exclusion, but they are awkward to use and they busy-wait. Operating systems offer higher-level tools instead. A semaphore, introduced by Dijkstra, is an integer with two atomic operations that can both protect critical sections and order events between processes. A mutex lock is the special case built only for mutual exclusion, with an owner. A monitor is a language construct that bundles shared data with the procedures that use it and guarantees that only one process is active inside at a time, with condition variables for waiting.

Analysing a synchronization scheme means tracing these operations: what values a semaphore takes, which processes block, what outputs are possible, whether a deadlock can occur. The exact semantics needed to trace them correctly follow.

Prerequisites

The Critical-Section Problem and Software/Hardware Solutions: the three requirements, race conditions, busy waiting and atomic instructions.

Core concepts

Semaphore operations

A semaphore $S$ holds an integer and is accessed only through two atomic operations (the names vary by book):

Name used here	Other names	Effect
`wait(S)`	P, down, `sem_wait`	Decrement; if the value does not allow it, the caller waits
`signal(S)`	V, up, post, `sem_post`	Increment; if processes are waiting, wake one

Busy-waiting definition (the classical one):

Text

wait(S):    while S <= 0 do nothing
            S <- S - 1
signal(S):  S <- S + 1

Here the test and the decrement together are atomic, and $S$ never goes below 0.

Blocking definition (how kernels implement it):

Text

wait(S):    S.value <- S.value - 1
            if S.value < 0 then
                add this process to S.list
                block()
signal(S):  S.value <- S.value + 1
            if S.value <= 0 then
                remove a process P from S.list
                wakeup(P)

Reading a negative value. In the blocking definition, a negative value $-k$ means exactly $k$ processes are waiting in the list. A value $v \ge 0$ means $v$ more wait calls can succeed without blocking. The two definitions allow the same sets of outcomes; only the bookkeeping differs.

Final value after many operations. If a semaphore starts at $s_0$ and, by the end, $p$ wait and $v$ signal operations have completed, the value is $s_0 - p + v$ , whatever the order (in the blocking definition this holds once every blocked process has been woken).

Semaphore value and waiting list over six operations — Figure 1. A semaphore initialized to 1: P1, P2 and P3 each call wait, then each calls signal in the same order; the value goes 0, -1, -2, -1, 0, 1 and the waiting list holds P2, then P2 and P3, then P3, then nobody.

Kinds of semaphore and lock

Tool	Values	Owner?	Typical use
Counting semaphore	Any integer $\ge 0$ (or negative in the blocking form)	No	Pools of $n$ identical resources; counting items
Binary semaphore	0 or 1 available permits; blocking implementations may use negative internal values for waiters	No	Mutual exclusion; one-shot signalling
Mutex lock	Locked or unlocked	Yes: only the locker may unlock	Mutual exclusion only
Spinlock	Locked or unlocked	Usually	Short critical sections on multiprocessors

Binary semaphore versus mutex. A binary semaphore can be signalled by a process that never waited on it, which makes it usable for ordering ("tell B that A has finished"). A mutex has ownership: unlocking a mutex you do not hold is an error. Many systems add priority inheritance to mutexes for the same reason.

Counting semaphores do not give mutual exclusion. A semaphore initialized to $k > 1$ lets $k$ processes in at once. Wrapping x = x + 1 in wait(S) and signal(S) with $S = 2$ and three threads still loses updates.

Three patterns

Text

Mutual exclusion          Ordering: A before B        Resource pool of n
mutex <- 1                S <- 0                      pool <- n
wait(mutex)               process 1: A; signal(S)     wait(pool)
  critical section        process 2: wait(S); B       use one resource
signal(mutex)                                         signal(pool)

Initial value is the key to the pattern: 1 for mutual exclusion, 0 for "wait until somebody signals", $n$ for $n$ identical resources.

Misuse

signal(mutex) ... wait(mutex) (swapped): several processes enter together.
wait(mutex) ... wait(mutex): the process blocks itself forever (a non-recursive lock).
Omitting wait in one process: that process ignores the protocol and races.
Two semaphores taken in opposite orders by two processes: deadlock is possible (see "Worked examples").

Monitors and condition variables

A monitor is an abstract data type whose procedures are executed under mutual exclusion automatically: the compiler inserts the lock. Inside, a process may need to wait for a condition (for example "buffer not empty"); for that the monitor provides condition variables with two operations:

x.wait(): release the monitor and block on x.
x.signal(): wake one process blocked on x; if none is waiting, nothing happens.

Condition variable versus semaphore. A semaphore's signal is remembered (the value goes up) even if nobody is waiting. A condition variable's signal with no waiter is lost. An unconditional condition wait used as an event token can miss an earlier signal. Correct condition-variable code uses a mutex-protected predicate and waits in a while loop; it need not hang after an early signal.

Who runs after a signal? When P signals Q inside the monitor, only one of them may continue:

Semantics	After `x.signal()`	Consequence
Signal and wait (Hoare)	Q runs at once; P waits	Q may assume the condition holds
Signal and continue (Mesa)	P continues; Q runs later, when the monitor is free	The condition may be false again by then: Q must recheck with `while`, not `if`

POSIX condition variables (pthread_cond_wait, used with a mutex) follow signal-and-continue, and can even wake spuriously, so the waiting code is always

pthread_mutex_lock(&m);
while (count == 0)                 /* while, not if */
    pthread_cond_wait(&not_empty, &m);
/* remove an item */
pthread_mutex_unlock(&m);

Related material. A monitor can be implemented with semaphores: one semaphore mutex (initial 1) for entry, and for each condition variable a semaphore (initial 0) plus a count of its waiters. Conversely a semaphore can be built from a monitor. So the tools are equally powerful; they differ in how easy they make correct code.

Worked examples

Tracing values and the waiting list

The semaphore of Figure 1 starts at 1. The six operations give:

Operation	Value after	Waiting list
P1 wait	0	empty (P1 enters)
P2 wait	-1	P2
P3 wait	-2	P2, P3
P1 signal	-1	P3 (P2 woken)
P2 signal	0	empty (P3 woken)
P3 signal	1	empty

At every point, a negative value equals minus the number of waiting processes.

Counting operations

A counting semaphore starts at 10. Twelve wait and nine signal operations complete in some order. The final value is $10 - 12 + 9 = 7$ , and no process is left blocked.

Possible outputs

With $S = T = 0$ :

Text

X:  print "A"; signal(S); wait(T); print "C"
Y:  wait(S); print "B"; signal(T); print "D"

B cannot precede A (Y waits for S), and C cannot precede B (X waits for T, which Y signals after printing B). After signal(T), both C and D are free. The only outputs are ABCD and ABDC, and no interleaving deadlocks.

Lost updates with the wrong initial value

Three threads each run wait(S); x = x + 1; signal(S) with x = 0 and the increment done as a load and a store.

With $S = 1$ : the final value is always 3.
With $S = 2$ : the final value can be 1, 2 or 3. One way to get 1: A and B both load 0; B stores 1 and signals; C enters, loads 1, stores 2; A finally stores 1.
With two threads, $S = 1$ , and one thread omitting wait and signal, the counter can end at 1 or 2.

Mixed increments under a counting semaphore

$x = 0$ and $S = 2$ . Processes W and X each run wait(S); x = x + 1; signal(S); processes Y and Z each run wait(S); x = x - 2; signal(S). Each update is a load followed by a store. What values can $x$ end with?

With $S = 2$ , two processes can be between wait and signal at once, so two updates can overlap and the later store can overwrite the earlier one. Searching by hand is error-prone, so enumerate every interleaving of the 16 steps (4 processes, each wait, load, store, signal). The reachable final values are exactly

x \in \{-4, -3, -2, -1, 0, 1, 2\}.

The maximum 2 is reached when both decrements are overwritten: Y loads 0 and W loads 0; Y stores $-2$ and signals; Z enters, loads $-2$ ; W stores 1 (Y's update lost) and signals; X enters, loads 1; Z stores $-4$ and signals; X stores 2 (Z's update lost). The minimum $-4$ loses both increments symmetrically. With $S = 1$ the semaphore is a mutex, every update is serialized, and the only result is $1 + 1 - 2 - 2 = -2$ .

A strict alternation puzzle

$S = 1$ and $T = 0$ :

Text

P:  repeat 3 times: wait(S); print "0"; signal(T)
Q:  repeat 3 times: wait(T); print "1"; signal(S)

P can print only after a signal(S) and Q only after a signal(T). The semaphores pass a single token back and forth, so the only output is 010101. If $S$ starts at 2 instead, P may run one round ahead: the outputs are exactly 001011, 001101, 010011 and 010101, never three 0s in a row and never a 1 before the first 0. In general, the number of 0s printed minus the number of 1s printed always lies between 0 and the initial value of $S$ .

Deadlock from lock order

$S = Q = 1$ . P0 runs wait(S); wait(Q); ...; signal(Q); signal(S) and P1 runs wait(Q); wait(S); ...; signal(S); signal(Q). If P0 takes S and P1 takes Q, each blocks on the other's semaphore forever. If both take S first and then Q, no interleaving deadlocks. Ordering all locks globally is the standard prevention method, discussed in Deadlock.

Important properties and observations

wait and signal must themselves be atomic; kernels implement them with interrupt disabling (uniprocessor) or spinlocks (multiprocessor). The busy waiting moves into these short operations instead of disappearing.
A semaphore says nothing about which waiter is woken; a FIFO list gives bounded waiting, an arbitrary choice may starve a process.
Deadlock and starvation are possible with correct semaphore code if the order of waits is wrong or the wake-up policy is unfair.
Monitors prevent forgetting the lock but not deadlock between monitors or misuse of conditions.

Common misconceptions.

"A semaphore's value is the number of waiting processes." Only its negative part is, and only in the blocking definition.
"Binary semaphore and mutex are the same." A mutex has an owner.
"x.signal() increments something." A condition variable has no value.

GATE examination perspective

Final value questions. $s_0 - p + v$ for completed operations; check that the given order is possible at all (the busy-waiting form never goes below 0).
Possible outputs and orderings. Build the precedence constraints from each signal to the wait it releases; enumerate the remaining freedom.
Initial values. 1 for mutual exclusion, 0 for ordering, $n$ for pools; check the initial value first; a wrong one breaks an otherwise correct scheme.
Deadlock with semaphores. Two processes acquiring two semaphores in opposite orders can deadlock.
Mutex versus binary semaphore; semaphore versus condition variable. Ownership, and remembered versus lost signals.
Mesa semantics. Waiting must be in a while loop.

Summary

Sources

A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10th ed., Wiley: Chapter 6 (6.5 Mutex Locks, 6.6 Semaphores, 6.7 Monitors, 6.8 Liveness).
A. S. Tanenbaum, H. Bos, Modern Operating Systems, 4th ed., Pearson: Sections 2.3.4 Sleep and Wakeup, 2.3.5 Semaphores, 2.3.6 Mutexes, 2.3.7 Monitors.

Introduction

Prerequisites

Core concepts

Semaphore operations

Kinds of semaphore and lock

Three patterns

Misuse

Monitors and condition variables

Worked examples

Tracing values and the waiting list

Counting operations

Possible outputs

Lost updates with the wrong initial value

Mixed increments under a counting semaphore

A strict alternation puzzle

Deadlock from lock order

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps