Synchronization 3: Lock ordering and condition variables

Overview

In this lecture, we discuss deadlock and condition variables.

Full notes on synchronization

Review

• Atomic operations
  • Foundation of synchronization
• Mutual exclusion
  • At most one thread can be in a critical section of code at a time
  • Infer need for mutual exclusion from shared state
  • Enforce mutual exclusion using std::mutex/std::unique_lock
• Lock granularity
  • Coarse grained: Few mutexes, lots of state per mutex
  • Fine grained: Many mutexes, little state per mutex

Synchronization objects are for coordination

• Many of the objects we study have interesting contents
  • What’s the value of this integer?
  • What values are stored in this vector or list?
• Synchronization objects like std::mutex are interesting only as coordination points for threads
  • For example, std::mutex helps enforce mutual exclusion
• This means that synchronization objects cannot be copied
  • Threads coordinate on a specific object, not the object’s value

Advanced CS 61 Bank operations

• deposit(amt)
  • Add amt to account balance
• try_withdraw(amt)
  • If account balance is less than amt, return false
  • Otherwise, deduct amt from balance and return true
• try_transfer(amt, account& partner)
  • If account balance is less than amt, return false
  • Otherwise, deduct amt from this account balance, add amt to partner’s balance, and return true
• withdraw(amt)
  • Block until balance ≥ amt, then withdraw amt and return

try_transfer: Fine-grained locking

class account {
    long bal;
    std::mutex am;

    void deposit(long amt) {
        std::unique_lock guard(am);
        bal += amt;
    }

    bool try_withdraw(long amt) {
        std::unique_lock guard(am);
        if (bal < amt) {
            return false;
        }
        bal -= amt;
        return true;
    }

    bool try_transfer(long amt, account& partner) {
        std::unique_lock guard(am);
        std::unique_lock guard2(partner.am);
        if (bal < amt) {
            return false;
        }
        bal -= amt;
        partner.bal += amt;
        return true;
    }
};

Deadlock

• a.try_transfer(1, b) and b.try_transfer(1, a) can deadlock
• One or more threads that block forever
  • Each thread has exclusive access to a resource
  • Each thread wants exclusive access to a resource that some other thread owns

Deadlock theory

• Deadlock requires four properties
  1. Mutual exclusion
  2. Hold and wait
  3. No preemption
  4. Circular wait

Lock ordering

• Assign a total order to all system mutexes
• Always acquire the mutexes in the same order
• Why does this solve deadlock?

Lock ordering solution

• How can you order mutexes?
• std::scoped_lock

withdraw: Spinning vs. blocking

class account {
    long bal;
    std::mutex am;

    void deposit(long amt) {
        std::unique_lock guard(am);
        bal += amt;
    }

    bool try_withdraw(long amt) {
        std::unique_lock guard(am);
        if (bal < amt) {
            return false;
        }
        bal -= amt;
        return true;
    }

    void withdraw(long amt) {
        while (!try_withdraw(amt)) {
            // do nothing
        }
    }
};

Waiting for a change

• std::mutex lets a thread block while waiting for access (mutual exclusion)
• But withdraw wants to wait for a condition
  • Some change in the state of the world

Idea: wait and notify_all

• Motivated by signal handlers
• wait(): Block this thread until another thread calls notify_all()
• notify_all(): Wake up all threads blocked in wait()
• Why this interface?
  • Captures the essential behavior of waiting for a change
  • As simple as possible
  • …Or is it?

Using wait and notify_all

class account { …
    void deposit(long amt) {
        std::unique_lock guard(am);
        bal += amt;
        notify_all();
    }

    void withdraw(long amt) {
        while (!try_withdraw(amt)) {
            wait();
        }
    }
};

Sleep–wakeup race

• wait and notify_all have an inherent race condition
  • notify_all only wakes up threads that are waiting
  • But a thread must not wait until it releases all mutexes!
  • This means that one thread can change the state of the world just before a different thread waits
  • And the notify_all will be a lost wakeup
• Ideas?

Condition variables

• Condition variable synchronization objects implement wait and notify_all
• But they integrate mutual exclusion and so avoid sleep–wakeup races and lost wakeups
• std::condition_variable_any cv
• cv.wait(m)
  • m is a locked lock (std::mutex, std::unique_lock)
  • wait atomically releases the lock and registers interest in notify_all
  • It re-locks m before returning

Using condition variables

class account {
    std::mutex am;
    std::condition_variable_any cv;

    void deposit(long amt) {
        std::unique_lock guard(am);
        bal += amt;
        cv.notify_all();
    }

    void withdraw(long amt) {
        std::unique_lock guard(am);
        while (bal < amt) {
            cv.wait(guard);
        }
        bal -= amt;
    }
};

Compare–exchange

• Atomic data types offer atomic read–modify–write operations like increment (++, fetch_add)
• But they also offer a general read–modify–write operation that subsumes the others
• a.compare_exchange_strong(expected, desired)
  • If a == expected, set a = desired and return true
  • Otherwise, set expected = a and return false
  • In one atomic step
  • lock cmpxchg instruction in x86-64

Compare–exchange bank

class account {
    std::atomic<long> bal;

    void deposit(long amt) {
        bal += amt;
    }

    bool try_withdraw(long amt) {
        long tbal = bal;
        while (true) {
            if (tbal < amt) {
                return false;
            }
            if (bal.compare_exchange_strong(tbal, tbal - amt)) {
                return true;
            }
        }
    }
}