Overview

In this lecture, we discuss deadlock and condition variables.

Full notes on synchronization

Review

Synchronization objects are for coordination

Advanced CS 61 Bank operations

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

Deadlock theory

Deadlock diagram

Lock ordering

Lock ordering solution

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

Idea: wait and notify_all

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

Condition variables

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

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;
            }
        }
    }
}