A semaphore is a synchronization variable used to control access to shared resources and coordinate the order of concurrent processes or threads. The two basic operations are wait() and signal(). wait() requests or consumes permission; signal() releases permission or wakes a waiting process. A binary semaphore can protect one critical section, while a counting semaphore can represent several identical resources. Semaphores can be implemented using blocking queues so waiting processes do not waste CPU time. Test-and-set is different: it is an atomic hardware instruction often used to build low-level locks. This chapter teaches all of these ideas through simple resource-permit examples, solved traces and synchronization patterns.
Why Do We Need a Semaphore?
Suppose two processes want to update the same shared variable. If both enter the sensitive code at the same time, one update can overwrite the other.
Process P1
Reads shared counter and prepares an update.
RESOURCE
Process P2
Reads and updates the same counter at nearly the same time.
This is the same race-condition problem studied in Critical Section & Mutual Exclusion in OS.
A semaphore gives the operating system a controlled way to say “you may enter,” “you must wait,” or “a resource has become available.”
Semaphore Meaning With a Simple Permit Example
The easiest way to understand a semaphore is to imagine a box of permits.
If the semaphore value is 3, up to three resource units are available. Every successful wait() takes one permit. Every signal() returns one permit.
What Does wait() Do?
wait(S)
wait() tries to acquire permission from semaphore S.
signal(S)
signal() returns permission to semaphore S and may wake a waiting process.
Textbooks also use other names:
The exact pseudocode can differ between textbooks and operating systems, but the idea is always permission acquisition and release.
How Is a Semaphore Used Around a Critical Section?
For mutual exclusion, the semaphore is commonly initialized to 1. That single permit ensures only one process enters the protected section at a time.
What Is a Binary Semaphore?
Binary Semaphore
A binary semaphore represents two logical states: permission available or permission unavailable.
Typical use: mutual exclusion or simple event synchronization.
Counting Semaphore
A counting semaphore represents multiple available units of a resource.
Typical use: controlling access to a pool of identical resources.
A binary semaphore is often initialized to 1 when used for mutual exclusion.
What Is a Counting Semaphore?
A counting semaphore is used when more than one identical resource instance is available.
Imagine a lab with three printers. At most three print jobs can use a printer at the same time.
If all three permits are taken, the next process must wait until one process executes signal().
Binary Semaphore Example Step by Step
Suppose:
This is semaphore-based mutual exclusion.
Counting Semaphore Example Step by Step
Suppose a system has three identical database connections available:
What Happens When Semaphore Permission Is Not Available?
A practical semaphore can place the process into a waiting queue instead of letting it waste CPU time.
With a blocking semaphore, a waiting process can sleep instead of repeatedly checking the semaphore value. When another process signals, one waiting process can become ready again.
Busy-Wait Semaphore vs Blocking Semaphore
| Point | Busy Waiting | Blocking |
|---|---|---|
| Waiting behavior | Repeatedly checks condition | Process sleeps/waits in a queue |
| CPU usage while waiting | Consumes CPU cycles | Much lower while blocked |
| Useful when | Expected wait is extremely short | Wait may be longer |
| Typical form | Spinlock-like behavior | Semaphore/mutex with scheduler support |
This distinction matters because semaphore theory is about synchronization, while the exact waiting mechanism is an implementation choice.
How Can Semaphores Control Execution Order?
Semaphores can do more than keep two processes out of the same critical section. They can also enforce “this must happen before that.”
Suppose P2 must not start Step B until P1 finishes Step A.
This is synchronization by ordering: semaphore value 0 is useful when one process must wait for an event from another process.
Semaphore vs Mutex
| Point | Semaphore | Mutex |
|---|---|---|
| Main idea | Permit/counter for synchronization | Ownership-based mutual exclusion lock |
| Values | Binary or counting | Locked or unlocked |
| Resource count | Can represent multiple resources | Usually protects one critical section/resource |
| Ordering use | Can coordinate event order | Mainly protects exclusive ownership |
| Ownership concept | Not always ownership-based in textbook semaphore use | Usually the owner is expected to unlock it |
Students often say “binary semaphore and mutex are exactly the same.” They can solve similar mutual-exclusion problems, but their semantics and ownership rules can differ.
What Is Test-and-Set?
Test-and-set is an atomic hardware instruction that reads a lock value and changes it in one indivisible operation.
It is not a semaphore operation. Instead, it is a low-level building block that can be used to implement spinlocks or protect short critical sections.
Semaphore
A higher-level synchronization primitive with wait/signal semantics and often scheduler-supported blocking.
Test-and-Set
A hardware atomic instruction commonly used to build a lock.
Why Must wait() and signal() Be Atomic?
If two processes could change the semaphore value at the same time without protection, the semaphore itself would have a race condition.
The internal update of a semaphore must be performed atomically so two processes cannot corrupt its value or waiting queue.
Operating systems can use hardware atomic operations, interrupt control in limited kernel situations, internal locks or other protected mechanisms to implement semaphore operations safely.
Semaphore Permit Simulator
This simulator starts with three permits. Use wait() to take a permit and signal() to return one.
Available permits
Event log
The simulator stops decreasing at zero because there is no permit left to acquire. In a real blocking semaphore, another process would wait until signal() makes permission available again.
Common Semaphore Mistakes
Can Semaphores Cause Deadlock?
Yes. Semaphores are tools; incorrect use can create deadlock.
Suppose two processes need semaphores A and B:
P1
wait(A) -> wait(B)
P2
wait(B) -> wait(A)
If P1 holds A while P2 holds B, both can wait forever for the other semaphore.
Where Are Semaphores Used?
How to Choose the Initial Semaphore Value
| Situation | Common Initial Value | Why |
|---|---|---|
| One critical section permit | 1 | Only one process should enter at a time |
| Three identical resources | 3 | Three processes may acquire one resource each |
| P2 must wait for event from P1 | 0 | P2 blocks until P1 signals |
| N identical resource units | N | Semaphore count represents free units |
How to Write Semaphores in Semester Exams
Definition
Define semaphore and write the names of wait() and signal().
Types + operations
Explain binary and counting semaphores with wait/signal and one resource example.
Complete answer
Add mutual exclusion, blocking queue, busy waiting, event ordering, test-and-set difference, solved trace and deadlock warning.
Fast memory trick
Wait takes permission · Signal returns permissionPractice Questions With Answers
1. What is a semaphore in OS?
A semaphore is a synchronization variable used to control access to shared resources and coordinate concurrent processes or threads.
2. What does wait() do?
wait() tries to acquire permission from the semaphore. If permission is unavailable, the process waits according to the semaphore implementation.
3. What does signal() do?
signal() releases permission to the semaphore and may allow a waiting process to continue.
4. What is a binary semaphore?
A binary semaphore represents two logical states and is commonly used for mutual exclusion or simple event synchronization.
5. What is a counting semaphore?
A counting semaphore tracks multiple available units of a resource.
6. Why can a semaphore start at 0?
Starting at 0 is useful when a process must wait until another process signals that an event has occurred.
7. What is test-and-set?
Test-and-set is an atomic hardware instruction used to read and change a lock value in one indivisible operation.
8. Is test-and-set the same as a semaphore?
No. Test-and-set is a low-level atomic instruction, while a semaphore is a higher-level synchronization primitive.
9. Can semaphores cause deadlock?
Yes. Incorrect semaphore ordering or missing signal operations can cause deadlock.
10. What is the difference between mutex and semaphore?
A mutex is mainly an ownership-based mutual-exclusion lock, while a semaphore is a counter/permit synchronization primitive that can also coordinate multiple resources or execution order.
Semaphore Concept Map
Frequently Asked Questions
What is semaphore in OS in simple words?
A semaphore is a synchronization counter or permission mechanism used to control access to shared resources and coordinate processes or threads.
What is the difference between wait() and signal()?
wait() requests or consumes semaphore permission, while signal() releases permission and may allow a waiting process to continue.
What is the difference between binary and counting semaphore?
A binary semaphore represents two logical states, while a counting semaphore tracks multiple available resource units.
Why is semaphore operation atomic?
Semaphore operations must be atomic so concurrent processes cannot corrupt the semaphore value or its waiting queue.
Is test-and-set a semaphore?
No. Test-and-set is an atomic hardware instruction commonly used to build locks, while a semaphore is a higher-level synchronization primitive.
Can semaphore solve process synchronization?
Yes. Semaphores can provide mutual exclusion, control access to multiple resources and enforce execution ordering between processes or threads.
Next Chapter: Producer-Consumer Problem
Now apply semaphores to a real synchronization problem
The next topic should be Producer-Consumer Problem in OS: Semaphore Solution With Simple Examples. There you will use three important semaphore ideas together: a mutex for the buffer, an empty-slot counter and a full-slot counter.
You can also revise Process Concept & Concurrency before moving to the solved Producer-Consumer execution.
