Semaphores

A semaphore is a nonnegative integer together with two operators that manipulate it atomically, which are:

  • “Down” or “P”: wait for the value to become positive, then decrement it.
  • “Up” or “V”: increment the value (and wake up one waiting thread, if any).

A semaphore initialized to 0 may be used to wait for an event that will happen exactly once. For example, suppose thread A starts another thread B and wants to wait for B to signal that some activity is complete. A can create a semaphore initialized to 0, pass it to B as it starts it, and then "down" the semaphore. When B finishes its activity, it "ups" the semaphore. This works regardless of whether A "downs" the semaphore or B "ups" it first.

A semaphore initialized to 1 is typically used for controlling access to a resource. Before a block of code starts using the resource, it "downs" the semaphore, then after it is done with the resource it "ups" the resource. In such a case a lock, described below, may be more appropriate.

Semaphores can also be initialized to 0 or values larger than 1.

You may also want to read through the Study Guide related to Semaphores for more information.

PintOS’ semaphore type and operations are declared in threads/synch.h.

struct semaphore

Represents a semaphore.

void sema_init (struct semaphore *sema, unsigned value)

Initializes sema as a new semaphore with the given initial value.

void sema_down (struct semaphore *sema)

Executes the "down" or "P" operation on sema, waiting for its value to become positive and then decrementing it by one.

bool sema_try_down (struct semaphore *sema)

Tries to execute the "down" or "P" operation on sema, without waiting. Returns true if sema was successfully decremented, or false if it was already zero and thus could not be decremented without waiting. Calling this function in a tight loop wastes CPU time, so use sema_down or find a different approach instead.

void sema_up (struct semaphore *sema)

Executes the "up" or "V" operation on sema, incrementing its value. If any threads are waiting on sema, wakes one of them up.

Unlike most synchronization primitives, sema_up may be called inside an external interrupt handler.

Semaphores are internally built out of disabling interrupt and thread blocking and unblocking (thread_block and thread_unblock). Each semaphore maintains a list of waiting threads, using the linked list implementation in lib/kernel/list.c.