Definition of the semaphore type

A semaphore S is a compound data type with two fields, S.V of type non-negative integer, and S.L of type set of processes. We are using the familiar dotted notation of records and structures from programming languages. A semaphore S must be initialized with a value \( k > 0 \) for S.V and with the empty set \( \emptyset \) for the S.L:

There are two atomic operations defined on a semaphore S (where p denotes the process that is executing the statement):

wait(S)

if S.V > 0
  S.V <- S.V -1
else
  S.L <- S.L U p
  p.state <- blocked

If the value of the integer component is nonzero, decrement its value (and the process p can continue its execution); otherwise it is zero process p is added to the set component and the state of p becomes blocked. We say that p is blocked on the semaphore S.

signal(S)

if S.L = ø
  S.V <- S.V + 1
else
  let q be an arbitrary element of S.L
  S.L <- S.L - {q}
  q.state <- ready

If S.L is empty, increment the value of the integer component; otherwise S.L is nonempty unblock q, an arbitrary element of the set of processes blocked on S.L. The state of process p does not change.

A semaphore whose integer component can take arbitrary non-negative values is called a general semaphore. A semaphore whose integer component takes only the values 0 and 1 is called a binary semaphore. A binary semaphore is initialized with (0, ø) or (1, ø). The wait(S) instruction is unchanged, but signal(S) is now defined by:

if S.v = 1
  // undefined
else if S.L = ø
  S.V <- 1
else // (as above)
  let q be an arbitrary element of S.L
  S.L <- S.L - {q}
  q.state <- ready

A binary semaphore is sometimes called a mutex. This term is used in pthreads and in java.util.concurrent.

Once we have become familiar with semaphores, there will be no need to explicitly write the set of blocked processes S.L.