CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 3 of 7 · 2 min read

Binary semaphore

In plain words: A single changing room has a token on a hook. Whoever takes the token enters, and returns the token on leaving. This is the key-and-toolbox of page 3, as a counter. The analogy stops in one place: a token can be handed back by a friend, while a mutex must be unlocked by its holder.

A semaphore that starts at 1 and is used with wait before the critical section and post after it is a binary semaphore (its value is only 0 or 1 when used correctly). It gives mutual exclusion: the first thread takes the value to 0 and enters, any other sleeps, and the post lets the next one in.

sem_t lock;
sem_init(&lock, 0, 1);          /* value 1: free; the middle 0 means shared between threads */

sem_wait(&lock);                /* like mutex lock   */
counter++;
sem_post(&lock);                /* like mutex unlock */

A binary semaphore and a mutex look alike. The differences matter:

Mutex Binary semaphore
Owner The thread that locked it must unlock it Any thread may post
Purpose Mutual exclusion Exclusion, and also signalling
Error checking Types detect misuse (page 3) None: a stray post raises the value above 1
Priority inheritance Available (PTHREAD_PRIO_INHERIT) Not available
Recursion Possible with the recursive type A second wait by the owner blocks for ever

The absence of an owner is a freedom and a danger. An extra sem_post turns the binary semaphore into a counting one with value 2, and two threads then enter together, silently. For plain exclusion, a mutex is the safer tool, since misuse is detected and priority inheritance is available. Use a semaphore when its other powers (counting and signalling, below) are needed.

Binary semaphore

A binary semaphore is a semaphore used with the values 0 and 1 only, initialised to 1, so that wait and post around a critical section give mutual exclusion, but which, unlike a mutex, has no owner.

Example: sem_wait takes the value from 1 to 0 and admits one thread; the next sem_wait sleeps until a sem_post brings the value back to 1.

Check yourself: 1. What initial value makes a semaphore a lock? 2. What goes wrong if a thread posts twice by mistake? 3. Why is a mutex safer for plain exclusion?