Semaphores

A lock answers one question: is this thing free, yes or no?

But the browser has a different problem. It allows 3 simultaneous connections. Not one. Not unlimited. Three.

A lock cannot express that. It counts to one.

Why & what

A semaphore is a counter with two rules. The count is how many of the resource are still available right now.

• wait(S) — if the count is greater than 0, subtract 1 and continue. If it is 0, go to sleep until someone signals. Also written P or down.
• signal(S) — add 1 back. If a thread is sleeping on this semaphore, wake one of them. Also written V or up.

Both operations are atomic, built on the hardware instruction from Topic 4.3. The semaphore is a layer on top of a lock, not a replacement for one.

Two kinds.

• A counting semaphore ranges from 0 up to N. It guards N identical things — 3 network connections, 4 buffer slots, 10 database handles.
• A binary semaphore is 0 or 1. It behaves like a lock.

Following the browser's connection limit. The semaphore starts at 3.

• First thread calls wait → count 2, it connects.
• Second thread → count 1, it connects.
• Third thread → count 0, it connects.
• Fourth thread calls wait → count is 0, so it sleeps.
• The first thread finishes and calls signal → count would go to 1, but a thread is sleeping, so that thread is woken instead and takes the permit.

The count is not bookkeeping. It is literally how many permits are left.

Signalling between threads. There is a second use that surprises people. A semaphore starting at 0 is not guarding anything — it is a way for one thread to tell another that something has happened. Thread A calls wait(S) and sleeps immediately. Thread B does its work and calls signal(S) to wake A. That turns a semaphore into an ordering tool, and it is the whole trick behind the next topic.

How it works

1. Choose the initial value. It is the number of the resource available at the start. Three connections means start at 3. A lock means start at 1. A signal means start at 0.
2. Every thread calls wait before using the resource. If none is free it sleeps, using no CPU.
3. It uses the resource while holding its permit.
4. It calls signal when finished. The permit returns to the pool, or goes straight to a sleeping thread.
5. The count never goes below zero. If you see a negative count in a textbook, that variant is using the magnitude to mean "how many threads are asleep here".

Common confusion

"Semaphores prevent race conditions automatically." Only if every thread uses them correctly. A semaphore is still a convention, exactly like a lock. Forget one wait and the protection is gone.

"A binary semaphore is a mutex." Almost, and interviewers press on the almost. The difference is ownership: any thread can signal a binary semaphore, but only the owner can unlock a mutex. That makes a mutex safer for mutual exclusion and a binary semaphore usable for signalling between threads.

"wait means the thread spins." It usually means the opposite. A semaphore's wait puts the thread into the Waiting state and it uses no CPU until it is signalled.

Interview angle

"What is a semaphore?" An integer counter with two atomic operations, where the count is the number of available instances of a resource. Then give a concrete counting example — 3 connections is better than an abstract N.

"Counting versus binary?" Range and purpose: 0-to-N for N identical resources, 0-or-1 for mutual exclusion.

"Can a semaphore be used for something other than mutual exclusion?" Yes, and this is where good candidates separate themselves. A semaphore starting at 0 is a signal that orders two threads. The next topic is built entirely on that idea.