Counting Semaphores in Operating Systems
A binary semaphore works great when there is only one instance of a resource to protect. But what happens when you have, say, three printers or five database connections, and multiple processes need to use them at the same time? That is where counting semaphores come in.
A counting semaphore keeps track of how many instances of a resource are currently available. The value is not limited to 0 and 1 like a binary semaphore. It can go up to however many instances you have. Every time a process grabs one, the count drops. Every time a process lets one go, the count rises. When it hits zero, the next process that asks gets blocked until something is released.
The Two Operations
The logic behind wait and signal is the same as with binary semaphores, just with a wider range of values.
wait(S)
Wait decrements the count. If the result goes below zero, the process blocks and waits for a resource to free up.
wait(S) {
S = S - 1;
if (S < 0)
block(); // No resources left, process goes to sleep
}signal(S)
Signal increments the count. If there are any processes sitting in the waiting queue, one of them gets unblocked.
signal(S) {
S = S + 1;
if (S <= 0)
unblock(); // Wake up one process from the waiting queue
}Walking Through an Example
Say you have 3 instances of a resource and 4 processes all wanting to use one. The semaphore starts at 3.
Initial: S = 3 (3 resource instances available)
P1 calls wait() -> S = 2 -> P1 gets access
P2 calls wait() -> S = 1 -> P2 gets access
P3 calls wait() -> S = 0 -> P3 gets access
P4 calls wait() -> S = -1 -> P4 BLOCKS (no resources left, queued)
... P1 finishes its work ...
P1 calls signal() -> S = 0 -> P4 gets unblocked and enters
... P2, P3, P4 finish ...
All signal() -> S = 3 -> All resources free againImplementation in C++
#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <chrono>
#include <vector>
class CountingSemaphore {
private:
int count;
std::mutex mtx;
std::condition_variable cv;
public:
CountingSemaphore(int initial_count) : count(initial_count) {
std::cout << "Semaphore initialized with count: " << count << std::endl;
}
void wait() {
std::unique_lock<std::mutex> lock(mtx);
cv.wait(lock, [this]() { return count > 0; });
count--;
std::cout << "Resource acquired. Available: " << count << std::endl;
}
void signal() {
std::unique_lock<std::mutex> lock(mtx);
count++;
std::cout << "Resource released. Available: " << count << std::endl;
cv.notify_one();
}
int getCount() { return count; }
};
CountingSemaphore sem(3); // 3 instances available
void process(int id) {
std::cout << "Process " << id << " requesting a resource." << std::endl;
sem.wait(); // Acquire one instance
// --- Using the resource ---
std::cout << "Process " << id << " is using the resource." << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(1000));
std::cout << "Process " << id << " finished." << std::endl;
sem.signal(); // Release the instance
}
int main() {
std::vector<std::thread> processes;
for (int i = 1; i <= 4; i++) {
processes.push_back(std::thread(process, i));
std::this_thread::sleep_for(std::chrono::milliseconds(100));
}
for (auto& p : processes) {
p.join();
}
std::cout << "All processes completed." << std::endl;
std::cout << "Final count: " << sem.getCount() << std::endl;
return 0;
}Output:
Semaphore initialized with count: 3
Process 1 requesting a resource.
Resource acquired. Available: 2
Process 1 is using the resource.
Process 2 requesting a resource.
Resource acquired. Available: 1
Process 2 is using the resource.
Process 3 requesting a resource.
Resource acquired. Available: 0
Process 3 is using the resource.
Process 4 requesting a resource.
// Process 4 blocks here since count is 0
Process 1 finished.
Resource released. Available: 1
Resource acquired. Available: 0
Process 4 is using the resource.
Process 2 finished.
Resource released. Available: 1
Process 3 finished.
Resource released. Available: 2
Process 4 finished.
Resource released. Available: 3
All processes completed.
Final count: 3Processes 1, 2, and 3 all get in since there are three available instances. Process 4 has to wait until one of them finishes and signals. Once that happens, P4 gets through. By the end, all four are done and the count is back to 3 where it started.
Counting vs Binary Semaphore
| Aspect | Binary Semaphore | Counting Semaphore |
|---|---|---|
| Value range | Only 0 or 1 | 0 to N |
| Use case | Single resource instance | Multiple resource instances |
| Blocks when | Value is 0 | Value is 0 (all instances taken) |
| Operations | wait() and signal() | wait() and signal() |
| Example scenario | One printer, one file | Thread pool, database connections |
Real-World Use Cases
- Database Connection Pools: A web server might have 20 database connections. Initialize the semaphore to 20. Each request grabs one, uses it, and returns it. If all 20 are in use, new requests wait.
- Thread Pools: A task scheduler with 8 worker threads uses a counting semaphore initialized to 8. Tasks are assigned to available threads, and when all are busy, new tasks queue up.
- Parking Lots: A garage with 50 spots uses a semaphore initialized to 50. Each car entering decrements it, each car leaving increments it. When it hits 0, the gate shows "Full."
- Bounded Buffers: In the classic producer-consumer problem, two counting semaphores track the number of empty slots and filled slots in a shared buffer.
The counting semaphore is the right tool when you have a pool of identical resources and need to track how many are still free. It handles the bookkeeping automatically through the count, so you do not have to manage individual locks for each resource instance. As long as there is at least one available, processes can get through. The moment the pool empties, everyone else waits their turn until someone gives one back.
Counting Semaphore Trace
Question 1 of 1Test your ability to track semaphore values through a sequence of operations.