Pointer Walk

Mutex, Semaphore, Channel

Six primitives, sorted by how many threads may pass at once, and which one to reach for.

ConcurrencyIntermediate10 min read

Sharing safely

When several threads use the same data at the same time, things go wrong in ways that are hard to see. See Race Conditions. The tools for preventing that are called synchronization primitives.

There are a handful, and their names are intimidating. One question sorts most of them:

How many threads may pass at once?

MutexInteractive
Primitive

Waiting in line

T1 · readerT2 · readerT3 · writerT4 · readerT5 · readerT6 · writer

Inside

Done

Start. One thread inside at a time. Six threads arrive wanting the same shared data. Each needs 2 ticks with it.

Ticks
0
Inside now
0
Most inside at once
0

Mutex: one at a time

A mutex (short for mutual exclusion) is the simplest. It is a lock with one key.

  1. A thread locks the mutex before touching the shared data

    If it is free, the thread goes straight in.

  2. Any other thread that tries to lock it must wait

    It is paused until the mutex is free.

  3. The first thread unlocks when it has finished

    One waiting thread is let in.

MutexInteractive

Waiting in line

T1 · readerT2 · readerT3 · writerT4 · readerT5 · readerT6 · writer

Inside

Done

Start. One thread inside at a time. Six threads arrive wanting the same shared data. Each needs 2 ticks with it.

Ticks
0
Inside now
0
Most inside at once
0

Six threads, strictly one after another. Safe, and slow if the protected section is long.

python
import threading

lock = threading.Lock()

def add_to_total(amount):
    global total
    with lock:                 # locks here, unlocks at the end of the block
        total = total + amount

Use a mutex when a piece of data must never be touched by two threads at once. It is the default choice.

Semaphore: N at a time

A semaphore is a counter of permits. It starts at some number N.

  • To enter, a thread takes a permit. If none are left, it waits.
  • When it leaves, it hands the permit back.

So at most N threads are inside together.

Semaphore (3 permits)Interactive

Waiting in line

T1 · readerT2 · readerT3 · writerT4 · readerT5 · readerT6 · writer

Inside

Done

Start. Up to three threads inside at a time. Six threads arrive wanting the same shared data. Each needs 2 ticks with it.

Ticks
0
Inside now
0
Most inside at once
0

A semaphore does not make shared data safe: three threads are in there at once. Its job is different. It limits how many do something at the same time.

Example

What semaphores are for

A database allows 10 connections. A semaphore with 10 permits stops an eleventh thread from trying.

You need to download 500 files but only want 5 downloads in flight. A semaphore with 5 permits.

A semaphore with one permit behaves much like a mutex.

Read-write lock: many readers or one writer

Reading shared data does not change it, so any number of threads can read together without harm. Problems only arise when someone writes. A read-write lock uses that.

  • Any number of readers may hold it together.
  • A writer must have it alone: no readers, no other writers.
Read-write lockInteractive

Waiting in line

T1 · readerT2 · readerT3 · writerT4 · readerT5 · readerT6 · writer

Inside

Done

Start. Any number of readers together, or one writer alone. Six threads arrive wanting the same shared data. Each needs 2 ticks with it.

Ticks
0
Inside now
0
Most inside at once
0

Readers went in side by side. Each writer went in alone. The total time is well under the mutex's, with the same safety.

Use it for data that is read far more often than it changes, such as settings or a cache. If writes are frequent, a plain mutex is simpler and often just as fast.

The other three

These do not fit the "how many at once" picture as neatly, but you will meet them.

Atomic operation: one indivisible step

Some small operations, such as adding one to a number or swapping a value, can be done by the processor as a single step that cannot be interrupted. No lock, no waiting.

java
AtomicInteger counter = new AtomicInteger();
counter.incrementAndGet();      // safe from any number of threads

It is the fastest option, and only works for simple single-value updates.

Condition variable: wait until something is true

Sometimes a thread has nothing to do until another thread changes something: "wait until the queue is not empty". A condition variable lets a thread sleep, without using any CPU, until another thread signals that things have changed. It is always used together with a mutex.

Channel: hand the data over

All of the above let threads share memory carefully. A channel avoids sharing altogether. It is a pipe: one thread puts a value in, another takes it out. Only one thread has the value at any time, so there is nothing to lock.

go
jobs := make(chan Job)

go func() { jobs <- job }()     // one side sends
next := <-jobs                  // the other receives

The saying that goes with it: do not communicate by sharing memory. Share memory by communicating.

All six, sorted

PrimitiveHow many pass at onceUse it for
Mutex1Protecting shared data
Read-write lockMany readers, or 1 writerData that is mostly read
SemaphoreUp to NLimiting use of a scarce resource
Atomic operationEveryone, each in one indivisible stepCounters and flags
Condition variableNobody, until signalledWaiting for a change
Channel1 holds each itemPassing work between threads

Which one?

  1. Can you avoid sharing?

    Give each thread its own data, or pass data through a channel. No sharing means nothing to protect.

  2. Is it a single counter or flag?

    Use an atomic operation.

  3. Otherwise, start with a mutex

    Keep the locked section as short as possible.

  4. Reach for the others when you have their specific need

    Mostly reads: read-write lock. A limit on simultaneous use: semaphore. Waiting for a condition: condition variable.

Key takeaways

  • Synchronization primitives control how threads access shared things.
  • A mutex lets one thread in at a time. It is the default for protecting shared data.
  • A semaphore lets up to N in. It limits simultaneous use and does not by itself protect data.
  • A read-write lock lets many readers in together, or one writer alone.
  • Atomic operations, condition variables and channels cover single-value updates, waiting, and passing data without sharing.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    8 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress