Deadlock Avoidance

Make the threads acquire locks in the same order
- Relies on the programmer
Lock multiple mutexes in a single operation
- Thread A locks mut1 and mut2
- Thread B cannot lock mut2 or mut1 during this operation
- A much better solution
C++ provides library features for this

`std::scoped_lock`

C++17 has std::scored_lock
Very similar to std::lock_guard
- Except it can lock more than one mutex at the same time std::scoped_lock scope_lck(mut1, mut2...);
The mutexes are locked in the order given in the constructor call
- In the destructor, the mutexes are unlocked in the reverse order
This avoids the possibility of deadlock with multiple mutexes


#include <iostream>
#include <mutex>
#include <thread>

using namespace std::literals;

std::mutex mut1;
std::mutex mut2;

void funcA() {
  std::cout << "Thread A trying to lock mutexes 1 and 2...\n";
  std::scoped_lock scoped_lck(mut1, mut2);
  std::cout << "Thread A has locked mutexes 1 and 2\n";
  std::this_thread::sleep_for(50ms);
  std::cout << "Thread A releasing mutexes 1 and 2...\n";
}

void funcB() {
  std::cout << "Thread B trying to lock mutexes 2 and 1...\n";
  std::scoped_lock scoped_lck(mut2, mut1);
  std::cout << "Thread B has locked mutexes 2 and 1\n";
  std::this_thread::sleep_for(50ms);
  std::cout << "Thread B releasing mutexes 2 and 1...\n";
}

int main() {
  std::thread thrA(funcA);
  std::thread thrB(funcB);

  thrA.join();
  thrB.join();
}

`std::scoped_lock` Caveat

scoped_lock can be used with a single mutex std::scoped_lock scoped_lck(mut);
It is easy to accidentally omit the argument std::scoped_lock scoped_lck;
This will compile and run, but not actually perform any locking
- May cause an unexpected data race

Deadlock Avoidance before C++17

Use the std::lock function
- It can lock multiple mutexes in a single operation
```
// Lock two mutexes
std::lock(mut1, mut2);
```

Adopting Locks

std::unique_lock can "adopt" the locks

Pass the std::adopt_lock option to its constructor
Then std::unique_lock object now owns the lock

void funcA() {
  std::cout << "Thread A trying to lock mutexes 1 and 2...\n";
  std::lock(mut1, mut2);

  // Each lock is adopted by a unique_lock object
  std::unique_lock<std::mutex> uniq_lk1(mut1, std::adopt_lock);
  std::unique_lock<std::mutex> uniq_lk2(mut2, std::adopr_lock);
  std::cout << "Thread A has adopted the locks\n";

  std::this_thread::sleep_for(50ms);
  std::cout << "Thread A releasing mutexes 1 and 2...\n";
}

Deferring Locks

Alternatively, we can "defer" the locking
- Pass the std::defer_lock option to the constructor
- Then lock the mutexes later

void funcA()
  // Each unique_lock object is associated with a mutex
  std::unique_lock<std::mutex> uniq_lk1(mut1, std::defer_lock);
  std::unique_lock<std::mutex> uniq_lk2(mut2, std::defer_lock);

  std::cout << "Thread A trying to lock mutexes 1 and 2...\n";
  std::lock(uniq_lk1, uniq_lk2);
  std::cout << "Thread A trying has locked mutexes 1 and 2...\n";

  std::this_thread::sleep_for(50ms);
  std::cout << "Thread A releasing mutexes 1 and 2...\n";

`std::try_lock()`

Also locks multiple mutexes in a single operation
Returns immediately if it cannot obtain all the locks
- On failure, it returns the index of the object that failed to lock (0 for the first argument, etc)
On success, it returns -1

void funcA() {
  std::unique_lock<std::mutex> uniq_lk1(mut1, std::defer_lock);
  std::unique_lock<std::mutex> uniq_lk2(mut2, std::defer_lock);
  
  std::cout << "Thread A trying to lock mutexes 1 and 2...\n";
  
  auto idx = std::try_lock(uniq_lk1, uniq_lk2);
  if (idx != -1) {
    std::cout << "try_lock failed on mutex with index " << idx << '\n';
  } else {
    std::cout << "Thread A has locked mutexes 1 and 2\n";
    std::this_thread::sleep_for(50ms);
    std::cout << "Thread A releasing mutexes 1 and 2...\n";  
  }
}

Hierarchical Mutex

Sometimes this approach is not suitable
- It is not feasible to acquire multiple locks simultaneaously
A common technique is to impose an ordering
A thread cannot lock a mutex unless it has already locked a mutex with a lower status
- ID number
- Alphabetical name
The Williams book has a hierarchical_mutex that implements this

Deadlock Avoidance Guidelines

Avoid waiting for a thread while holding a lock
- The other thread may need the lock to proceed
Try to avoid waiting for other threads
- The other thread may be waiting for your thread
Try to avoid nested locks
- If your thread already holds a lock, do not acquire another one
- If you need multiple locks, acquire them in a single operation
Avoid calling functions within a critical section
- Unless you are certain the function does not try to lock

Debugging Grimoire