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.
Pintos’ semaphore type and operations are declared in
Represents a semaphore.
void sema_init (struct semaphore *sema, unsigned value)
semaas a new semaphore with the given initial
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
semawas 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_downor 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_upmay be called inside an external interrupt handler.
Semaphores are internally built out of disabling interrupt and thread blocking and unblocking (
thread_unblock). Each semaphore maintains a list of waiting threads, using the linked list implementation in