Concurrency

Transfer Without Deadlock

Difficulty

Asked at Squarepoint Capital, Chicago Trading Company

Read the problem, hints and solution here. The editor needs a bigger screen: open this page on a laptop to write and run your code.

This problem is only available to subscribers.

Language: C++23transfer

#include <atomic>
#include <cstddef>
#include <mutex>
#include <thread>
#include <vector>

// ...
// ...
// ...
// ...
// ...
class Account {
public:
    explicit Account(long long opening) : balance_(opening) {}

    long long balance() const {
        std::lock_guard<std::mutex> hold(mu_);
        return balance_;
    }

    std::mutex& mutex() const { return mu_; }

    // ...
    long long& raw_balance() { return balance_; }

private:
    mutable std::mutex mu_;
    long long balance_ = 0;
};

// ...
// ...
// ...
// ...
// ...
// ...
bool transfer(Account& from, Account& to, long long amount) {
    std::lock_guard<std::mutex> hold_from(from.mutex());
    std::lock_guard<std::mutex> hold_to(to.mutex());
    from.raw_balance() -= amount;
    if (from.raw_balance() < 0) return false;
    to.raw_balance() += amount;
    return true;
}

// ...
// ...
// ...
inline long long joint_total(Account& x, Account& y) {
    if (&x == &y) return x.balance();
    std::scoped_lock hold(x.mutex(), y.mutex());
    return x.raw_balance() + y.raw_balance();
}

Unlock to runUpgrade

Unlock the problem to run it against the tests.

Transfer Without Deadlock

xxxxxxxx

xxxxxxxxxxx