Deadlocks and Race Conditions

While Safe Rust guarantees at compile time that data races (unsynchronized memory corruption) cannot occur, concurrent programs can still experience deadlocks (threads waiting on one another in a permanent cycle) and logical race conditions (incorrect results caused by non-deterministic lock or message ordering).

How Deadlocks Occur (Coffman Conditions and AB-BA Lock Ordering)

A deadlock occurs when a cycle of threads each holds a lock that the next thread in the cycle is waiting to acquire:

Classic AB-BA Deadlock:

  Thread 1                                  Thread 2
  --------                                  --------
  1. Locks `Account A`                      1. Locks `Account B`
  2. Tries to lock `Account B` (Blocks!)    2. Tries to lock `Account A` (Blocks!)
              \                                         /
               +---> Both threads wait forever! <------+

Another common single-lock deadlock is same-thread re-locking: because std::sync::Mutex<T> is not re-entrant, calling mutex.lock() a second time on the same thread while an earlier MutexGuard is still in scope deadlocks the thread immediately.

Preventing AB-BA Deadlocks with Deterministic Lock Ordering

Whenever an operation must acquire two locks (account_a and account_b), always lock them in a consistent global order—such as sorting by unique account ID or memory address—so all threads acquire the lower-ID lock first and the higher-ID lock second, making a wait cycle impossible:

use std::cmp::Ordering;
use std::sync::Mutex;
use std::thread;

struct Account {
    id: u64,
    balance: Mutex<i64>,
}

fn transfer(from: &Account, to: &Account, amount: i64) {
    // 1. Guard against self-transfer (which would try to lock the same Mutex twice!):
    if from.id == to.id {
        return;
    }

    // 2. Always lock the account with the SMALLER `id` first to prevent AB-BA deadlock:
    let (mut from_guard, mut to_guard) = match from.id.cmp(&to.id) {
        Ordering::Less => {
            let g1 = from.balance.lock().unwrap();
            let g2 = to.balance.lock().unwrap();
            (g1, g2)
        }
        Ordering::Greater => {
            let g2 = to.balance.lock().unwrap();
            let g1 = from.balance.lock().unwrap();
            (g1, g2)
        }
        Ordering::Equal => unreachable!(),
    };

    *from_guard -= amount;
    *to_guard += amount;
}

fn main() {
    let acct_1 = Account {
        id: 1,
        balance: Mutex::new(1000),
    };
    let acct_2 = Account {
        id: 2,
        balance: Mutex::new(1000),
    };

    // Concurrent transfers in opposite directions (`1 -> 2` and `2 -> 1`)
    // never deadlock because both threads lock `acct_1` before `acct_2`:
    thread::scope(|s| {
        s.spawn(|| {
            for _ in 0..100 {
                transfer(&acct_1, &acct_2, 5);
            }
        });
        s.spawn(|| {
            for _ in 0..100 {
                transfer(&acct_2, &acct_1, 3);
            }
        });
    });

    println!(
        "final balances -> acct_1: {}, acct_2: {}",
        *acct_1.balance.lock().unwrap(),
        *acct_2.balance.lock().unwrap()
    );
}

final balances -> acct_1: 800, acct_2: 1200

Preventing Check-Then-Act Logical Race Conditions (TOCTOU)

A Time-of-Check to Time-of-Use (TOCTOU) logical race condition happens when a thread locks a mutex to check a condition (if *balance.lock().unwrap() >= 100), drops the guard, and then locks the mutex a second time to deduct the amount (*balance.lock().unwrap() -= 100). In the window between the two locks, another thread can drain the balance below zero!

Buggy TOCTOU Pattern (Two Separate Lock Scopes):
  if *acct.lock().unwrap() >= 100 {     // <-- Lock acquired & released!
      // Another thread modifies `acct` here!
      *acct.lock().unwrap() -= 100;     // <-- Second lock sees stale state!
  }

Race-Free Atomic Transaction Pattern (Single Lock Guard):
  let mut guard = acct.lock().unwrap(); // <-- Single lock held across check AND update!
  if *guard >= 100 {
      *guard -= 100;
  }

Summary of Concurrency Hazard Prevention