CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 4 of 7 · 2 min read

Counting

Think of it this way. A library has three copies of a popular textbook. The librarian does not track who has which copy. The number of copies on the shelf is enough: a reader takes one if the number is above zero, and waits if it is zero. A semaphore initialised to the number of copies is exactly this. The analogy stops in one place: a library tracks borrowers, but a semaphore does not know which thread holds a unit.

In plain words: A counting semaphore has an initial value n above 1. The value is the number of units of a resource that are free: database connections, buffer slots, licences. wait takes a unit (or waits for one), and post returns it.

A test: eight jobs each hold one of three slots for 100 ms. A semaphore starts at 3.

8 jobs of 100 ms on 3 slots: 0.30 s, at most 3 at once

The 8 jobs run in waves of 3, 3 and 2, three waves of 100 ms, so 0.30 s. The program also counted how many were inside at once (under a mutex), and the maximum was 3, never 4. At the end, the value of the semaphore was back at 3.

This is the same wave arithmetic as the pool of Level 2, page 7, and the semaphore is the tool that bounds the number of threads in a region. Without it, all eight jobs would run at once, and the shared resource would be overloaded.

A note on fairness: POSIX does not say which waiter wakes first, so a semaphore is not strictly first-in, first-out, and a thread can be overtaken.

Counting semaphore

A counting semaphore is a semaphore whose initial value is the number of identical units of a resource that are available, so that wait claims a unit, sleeping if none is free, and post returns one.

Example: a semaphore initialised to 3 admits at most 3 threads into a region at the same time.

Check yourself: 1. What is the value of the semaphore when two of three slots are in use? 2. How long do 7 jobs of 100 ms take on 3 slots? 3. What does the semaphore not know about the units?