A semaphore is a non-negative atomic counter. Introduced by Dijkstra, who was ‘fearful of asynchrony’. A semaphore is a type of synchronization primitive for threads like locks.
Semaphores, unlike mutexes, use a progressive incremented counter, kind of like in reference counting. Technically, locks can be considered a type of semaphore with only two values (i.e., binary), 0 and 1.
Analogy
I like this analogy on Wikipedia:
Suppose a physical library has ten identical study rooms, to be used by one student at a time. Students must request a room from the front desk. If no rooms are free, students wait at the desk until someone relinquishes a room. When a student has finished using a room, the student must return to the desk and indicate that the room is free.
In the simplest implementation, the clerk at the front desk knows only the number of free rooms available. This requires that all of the students use their room while they have signed up for it and return it when they are done. When a student requests a room, the clerk decreases this number. When a student releases a room, the clerk increases this number. The room can be used as long as desired and rooms cannot be booked in advance.
In this scenario, the front desk count-holder represents a counting semaphore, the rooms are the resource, and the students represent processes/threads. The value of the semaphore in this scenario is initially 10, with all rooms empty. When a student requests a room, they are granted access, and the value of the semaphore is changed to 9. After the next student comes, it drops to 8, then 7, and so on. If someone requests a room and the current value of the semaphore is 0, they are forced to wait until a room is freed (when the count is increased from 0). If one of the rooms was released, but there are several students waiting, any method can be used to select the one who will occupy the room (like FIFO or random selection). And of course, a student must inform the clerk about releasing their room only after leaving it.
Operations
Semaphores generally have the two following operations:
- P(s) or wait(s)
- Tries to reduce s
- Atomic: if s == 0, blocks until s > 0 then decrements s
- V(s) or signal(s)
- increases s
- atomic : increases s and unblocks waiting threads if necessary
Attempting to make the counter negative blocks the calling thread, forcing it to wait for another thread to increment the counter first.
Semaphores do not have an operation to read the counter value, only to change it.
Implementation
Like many other synchronization primitives, semaphores require the use of atomic operations to function properly.
During the term, you will have access to the uthreads library, which is a simplified user-level thread library specifically made for CPSC 213, and you can see the full implementation of all synchronization primitives there.
The general idea is the following:
void signal(thread_sem sem){
sem->value += 1; //increment semaphore by one (atomically)
thread_t waiting_thread = thread_dequeue(sem->waiting); // attempt to dequeu a waiting thread
if(waiting_thread){ //if there was a waiting thread
thread_unblock(waiting_thread); // unblock it
}
}
void wait(thread_sem sem){
sem->value -= 1; //decrement semaphore by one (atomically)
if(sem->value <= 0){ // if the counter reaches zero
thread_queue(sem->waiting, thread_self()); //queue the current thread into the waiting queue
//and block it
}
}Deadlock, Livelock, Starvation, Re-entrant mutex for recursive calls, Waiter graphs Avoiding deadlocks
Andrew D. Birell.
Implementing conditions with semaphores
Semaphores provide an elegant solution to critical sections and wait-signal races