Threads and Locks

The previous lesson showed that when the set of types is closed at compile time, the cost of polymorphism moves to compiling: a function call pays nothing at run time, but a separate body is produced for every type that is instantiated. This lesson measures a case where the payment goes somewhere else: the locks added to protect shared data once work is split across several threads. The question the course measures stays the same here: where does a mechanism move the cost? The answer falls under the kind wait. This measure does not count actual waiting; it counts the points where a thread may be forced to wait. No time is printed, because time depends on the machine and the load at that moment, while the number of points can be read from the code.

One distinction first. In M10/K03, the question “how many times did it run” made the count the measurement itself. Here the count is only a tool of evidence: the lesson does not answer “how many times was the lock acquired” but the kind that count points to, which is wait. The question of M08/K04, “which thread runs the step”, is also not asked in this lesson; what is measured is not which thread does what, but how many synchronization points there are.

Starting and Joining a Thread

std::thread starts running the function it is given on a separate thread at the moment it is constructed. Before the object is destroyed it must either be waited for with join() or released with detach(); an object destroyed with neither done terminates the program. For this reason every example calls join(), and results are read only after join() returns: join() guarantees that everything the thread wrote is visible to the caller.

If two threads write shared data with no protection at all, the behavior of the program is undefined: this is called a data race. Four threads each incrementing an unprotected counter ten thousand times does not guarantee that the result will be forty thousand; it guarantees no result at all. We do not run undefined behavior; we run only its defined counterpart and explain in prose why it is needed.

jthread: A Thread That Joins Itself

std::jthread arrives with C++20 and removes the most common mistake with std::thread. If the thread has not yet been joined, its destructor first sends a stop request and then calls join(); even if a return or an exception intervenes, the thread is finished before the scope is left. A std::thread destroyed without being joined, on the other hand, terminates the program. The difference is less about convenience than about safety: a forgotten join() is no longer a crash.

The second difference is that a jthread carries a stop request. If the function takes a std::stop_token parameter, it can leave its loop when request_stop() is called from the outside. Because when the request is seen depends on timing, we do not run that; we use only the joining behavior at the end of the scope. The subject of the measurement is not how the thread is started, but how it protects shared data once started.

Lock and lock_guard

The defined counterpart is to put the shared data behind a mutex. Once a std::mutex is locked, no other thread can acquire it until it is released; a thread that cannot acquire it waits. std::lock_guard acquires the lock when it is constructed and releases it when it is destroyed; because it ties the release to the end of the scope, neither a return nor an exception can leave the lock held.

The header below defines the shared counter and two ways of incrementing it. acquired is the second field, which counts how many times the lock was acquired; it is touched only while the lock is held. The first way acquires the lock on every increment. We will explain the second shortly.

// lock_measure.hpp — shared counter and two ways of incrementing
#pragma once
#include <mutex>

struct LockedCounter {
    std::mutex lock_m;
    long value = 0;
    long acquired = 0;
};

inline void increment_every_time(LockedCounter& c, int times) {
    for (int i = 0; i < times; ++i) {
        std::lock_guard<std::mutex> guard(c.lock_m);
        ++c.value;
        ++c.acquired;
    }
}

inline void increment_local(LockedCounter& c, int times) {
    long local = 0;
    for (int i = 0; i < times; ++i) ++local;
    std::lock_guard<std::mutex> guard(c.lock_m);
    c.value += local;
    ++c.acquired;
}

Several Locks and scoped_lock

One lock protects one variable. An operation that changes two objects at once must acquire the locks of both. If two threads acquire these locks in opposite order, each waits for the lock the other holds and neither can make progress: this is called deadlock. The common root of deadlock is locks being acquired in an inconsistent order.

There are two ways out. The first is to fix a single order across all the code; for example, always acquiring locks from the smaller account number to the larger. This works but takes discipline: the order is only a rule, and every new function that is written must obey it. The second is std::scoped_lock: it acquires several locks in one step, in an order that prevents deadlock; the standard requires a deadlock-avoidance algorithm for this. The order in which you write the locks no longer matters.

// account.hpp — operations that take two and three locks at once
#pragma once
#include <mutex>

struct Account {
    std::mutex lock_m;
    long balance = 0;
};

inline void transfer(Account& source, Account& target, long amount) {
    std::scoped_lock both(source.lock_m, target.lock_m);
    source.balance -= amount;
    target.balance += amount;
}

inline long total_balance(Account& a, Account& b, Account& c) {
    std::scoped_lock three(a.lock_m, b.lock_m, c.lock_m);
    return a.balance + b.balance + c.balance;
}

Even if transfer(a, b, 1) and transfer(b, a, 1) are called at the same time, no deadlock occurs. Had we written a.lock_m.lock() followed by b.lock_m.lock() by hand, deadlock would have been possible whenever two calls acquired them in opposite order; we do not run that, because the result may leave the program hanging. total_balance takes three locks at once: transfers hold only two locks, so a reader of the total never lands in the middle of any transfer.

Condition Variable and unique_lock

Sometimes a thread needs more than to protect shared data: it needs to wait for something to happen. std::condition_variable exists for this: the waiting thread releases the lock and sleeps, and wakes when another thread makes the condition true and gives notice. So that the waiting side can release the lock it holds, std::lock_guard is not enough; a std::unique_lock, which can be released and reacquired, is needed. unique_lock does everything lock_guard does and, on top of that, allows unlock() and lock() to be called; the price is a small piece of extra state.

// handoff.hpp — a one-time wake-up with a condition variable
#pragma once
#include <condition_variable>
#include <mutex>

struct Handoff {
    std::mutex lock_m;
    std::condition_variable wake;
    bool ready = false;
    int value = 0;
};

inline void prepare(Handoff& h, int v) {
    {
        std::lock_guard<std::mutex> guard(h.lock_m);
        h.value = v;
        h.ready = true;
    }
    h.wake.notify_one();
}

inline int await_value(Handoff& h) {
    std::unique_lock<std::mutex> locked(h.lock_m);
    h.wake.wait(locked, [&h] { return h.ready; });
    return h.value;
}

wait takes the condition as a predicate and checks it while the lock is held; the wake-up notice may have come for nothing, or the condition may have become true before it came, so the condition is retested on every wake-up. The flag and the value are written and read only under the lock.

Producer and Consumer

When a stream of values is carried instead of a single value, the same mechanism turns into a queue. The producer puts values in the queue and gives notice; the consumer takes values while the queue is full and sleeps while it is empty. When the work is done, the producer raises a done flag, because the consumer has no other answer to the question “the queue is empty, but will more values come”.

After the consumer takes a value from the queue, it releases the lock, does the work without the lock, and reacquires it. This is where unique_lock differs from lock_guard: the lock is held only for as long as shared data is being touched, and processing a value does not shut the queue to others.

// work_queue.hpp — producer/consumer queue
#pragma once
#include <condition_variable>
#include <mutex>
#include <queue>

struct WorkQueue {
    std::mutex lock_m;
    std::condition_variable wake;
    std::queue<int> items;
    bool done = false;
};

inline void produce(WorkQueue& q, int count) {
    for (int i = 0; i < count; ++i) {
        {
            std::lock_guard<std::mutex> guard(q.lock_m);
            q.items.push(i);
        }
        q.wake.notify_one();
    }
    {
        std::lock_guard<std::mutex> guard(q.lock_m);
        q.done = true;
    }
    q.wake.notify_one();
}

inline long consume(WorkQueue& q, int& received) {
    long total = 0;
    std::unique_lock<std::mutex> locked(q.lock_m);
    for (;;) {
        q.wake.wait(locked, [&q] { return !q.items.empty() || q.done; });
        if (q.items.empty()) break;
        int v = q.items.front();
        q.items.pop();
        locked.unlock();
        total += v;
        ++received;
        locked.lock();
    }
    return total;
}

How many times the consumer woke and how many times it waited depends on the schedule and is not printed. What is printed is two numbers that do not depend on the schedule: how many values were received, and the sum of the values.

Measurement: How Many Times Was the Lock Acquired

Now we run the two ways of incrementing with four threads, each making ten thousand increments. transfer, Handoff and WorkQueue also run in the same program; each result is printed only after join() returns, so the output does not depend on the order of the threads.

// lock_measurement.cpp — lock acquisition count and supporting checks
#include <functional>
#include <iostream>
#include <thread>
#include <vector>

#include "account.hpp"
#include "handoff.hpp"
#include "lock_measure.hpp"
#include "work_queue.hpp"

namespace {

void four_threads(LockedCounter& c, void (*work)(LockedCounter&, int)) {
    std::vector<std::thread> workers;
    for (int i = 0; i < 4; ++i) workers.emplace_back(work, std::ref(c), 10000);
    for (auto& worker : workers) worker.join();
}

}  // namespace

int main() {
    LockedCounter every_time;
    four_threads(every_time, increment_every_time);
    std::cout << "locked counter wait acquired=" << every_time.acquired
              << " value=" << every_time.value << "\n";

    LockedCounter local;
    four_threads(local, increment_local);
    std::cout << "local total wait acquired=" << local.acquired
              << " value=" << local.value << "\n";

    Account a, b;
    a.balance = 1000;
    b.balance = 1000;
    {
        std::thread forward([&] { for (int i = 0; i < 500; ++i) transfer(a, b, 1); });
        std::thread backward([&] { for (int i = 0; i < 500; ++i) transfer(b, a, 1); });
        forward.join();
        backward.join();
    }
    std::cout << "two-way transfer wait total=" << a.balance + b.balance << "\n";

    Account x, y, z;
    x.balance = y.balance = z.balance = 1000;
    int violations = 0;
    {
        std::thread t1([&] { for (int i = 0; i < 300; ++i) transfer(x, y, 1); });
        std::thread t2([&] { for (int i = 0; i < 300; ++i) transfer(y, z, 1); });
        std::thread t3([&] { for (int i = 0; i < 300; ++i) transfer(z, x, 1); });
        std::thread checker([&] {
            for (int i = 0; i < 200; ++i)
                if (total_balance(x, y, z) != 3000) ++violations;
        });
        t1.join();
        t2.join();
        t3.join();
        checker.join();
    }
    std::cout << "three-account ring wait total=" << total_balance(x, y, z)
              << " violations=" << violations << "\n";

    Handoff handoff;
    int received = 0;
    {
        std::jthread consumer([&] { received = await_value(handoff); });
        prepare(handoff, 42);
    }
    std::cout << "condition variable wait received=" << received << "\n";

    WorkQueue queue;
    int received_items = 0;
    long item_total = 0;
    {
        std::jthread consumer([&] { item_total = consume(queue, received_items); });
        produce(queue, 1000);
    }
    std::cout << "producer consumer wait received=" << received_items
              << " total=" << item_total << "\n";
    return 0;
}

locked counter wait acquired=40000 value=40000
local total wait acquired=4 value=40000
two-way transfer wait total=2000
three-account ring wait total=3000 violations=0
condition variable wait received=42
producer consumer wait received=1000 total=499500

CP1. The first line shows that the four threads acquired the lock on each of the forty thousand increments: acquired=40000, value=40000. Each acquisition is a point where a thread may be forced to wait for a lock held by another thread; the lesson measures the number of these points, not how many times waiting actually happened. The result value=40000 is defined because every increment was made under the lock; this correctness is the guarantee the lock gives.

CP2. The total=2000 on the third line shows that the transfers made in opposite order in the two directions left neither a deadlock nor a loss, thanks to std::scoped_lock: the sum of the two balances did not change. The order in which we wrote the locks did not matter here; transfer(a, b, …) and transfer(b, a, …) asked for the same two locks in opposite order.

CP3. The fourth line tests a ring of three locks: while three threads transferred from x to y, from y to z and from z to x, a fourth thread took all three locks at once two hundred times and read the total. The total showed 3000 every time and violations=0 came out. The reader never landed in the middle of a transfer, because no transfer changed a balance while holding only one of the two locks.

CP4. On the fifth line the waiting thread woke when prepare was called and received the value 42. std::jthread performed join() at the end of the scope, so received was written before it was read. At what moment the wake-up happened was not printed; only what was received was printed.

CP5. The last line shows that the consumer received all one thousand values and that the total is 499500, which is the sum of the numbers from zero to nine hundred ninety-nine. No value was lost and none was received twice. The done flag made sure that the consumer did not leave while the producer had not finished even if the queue emptied, and that it did not stay stuck waiting once the producer had finished and the queue was empty.

CP6. The two std::jthread objects on the fifth and sixth lines were also finished without a hand-written join(): the destructor joined as the scope closed. This is the only basis for the result being readable; without join(), or a destructor that calls it, received and item_total could have been read while the thread was still writing.

The Bounding Measurement

The mechanism this lesson measured is protecting shared data with a lock, and the second line reduces its cost. increment_local makes the ten thousand increments in each thread in its own local total, acquires the lock only once at the end, and adds the total to the shared counter. The result is the same, value=40000; but the synchronization points fell from forty thousand to four: acquired=4. The synchronization points were reduced ten thousand times over, and correctness was kept.

The lesson drawn from this is that the cost comes not from the lock itself but from how many times it is acquired. The same std::mutex was acquired forty thousand times in one way of writing and four times in another. The limit of this is as follows: a local total works only where the work can be split into parts and combined at the end. If every step must see the shared state, that is, if the result of one thread entered the next step of another, the lock is acquired at every step and the count does not fall. In that case the way to reduce the cost is not to let go of the lock but to divide the shared state; we will see this in the next two lessons as memory ordering and data layout.

Summary

• The mechanism this lesson measured moves the cost to the kind wait: a lock increases the number of points where a thread may be forced to wait; the measure is the number of these points, not the actual waiting time.
• A std::thread is waited for with join() once constructed; everything the thread wrote is read only after join() returns. std::jthread does the same work in its destructor.
• Writing shared data without protection is a data race and its behavior is undefined; std::mutex with std::lock_guard ends the race and releases the lock at the end of the scope.
• std::scoped_lock acquires several locks in an order that does not lead to deadlock; no ordering discipline is needed.
• std::condition_variable is for waiting on a condition and requires std::unique_lock; the condition is retested on every wake-up. Because unique_lock can release and reacquire the lock, it allows the work in a producer/consumer queue to be done without the lock.
• locked counter acquired the lock forty thousand times and local total four times, with the same result: the cost is determined not by the lock but by how many times it is acquired.

Next Step

A lock says whose hands a piece of data is in, and it makes what one thread wrote under the lock visible to whoever acquires the lock next; but it does not say which ordering is really needed for visibility, or how many synchronization points that ordering costs. The next lesson opens the memory model: with the question of how many synchronization points a memory order asks for, we will measure std::atomic and the release and acquire relation.