Threads, locks, and deadlocks in Rust

A very compelling feature of the Rust language is compile-time protection against data races.  This makes it much easier to write correct threaded programs that share mutable state.  The following program illustrates how this works. The program runs eight parallel simulations of a coin-flipping experiment.

extern crate rand;
use std::thread;
use std::sync::{Arc, Mutex};

fn main() {
    let total_flips = Arc::new(Mutex::new(0));
    let completed = Arc::new(Mutex::new(0));
    let runs = 8;
    let target_flips = 10;

    for _ in 0..runs {
        let total_flips = total_flips.clone();
        let completed = completed.clone();
        thread::spawn(move || {
            simulate(target_flips, total_flips);
            let mut completed = completed.lock().unwrap();
            *completed += 1;
        });
    }

    loop {
        let completed = completed.lock().unwrap();
        if *completed == runs {
            let total_flips = total_flips.lock().unwrap();
            println!("Final average: {}", *total_flips / *completed);
            break;
        }
    }
}

fn simulate(target_flips: u64, total_flips: Arc<Mutex<u64>>) {
    let mut consecutive = 0;
    let mut iterations = 0;
    while consecutive < target_flips {
        iterations += 1;
        if rand::random() {
            consecutive += 1;
        } else {
            consecutive = 0;
        }
    }
    println!("iterations: {}", iterations);
    let mut total_flips = total_flips.lock().unwrap();
    *total_flips += iterations;
}

The main() function creates two mutable variables that can be shared among threads. One represents the total flips across all experiments. The other represents the total number of experiments that have completed. They are Arc (atomic reference counted pointers) objects that each contain a Mutex (lockable resource).

As each thread is created, it needs its own reference to these shared variables. To create a new shared reference, we need to clone() each variable. This clone is then moved into the thread as it is created, so that the thread is now the owner of the cloned reference.

To access the shared variables, a thread must acquire a lock. The thread blocks if the lock is already held by another thread. A thread releases a lock it holds when the locked variable goes out of scope. The total_flips variable is locked within the simulate() function, while the completed variable is locked after that function completes. The main thread also locks completed periodically as it checks for completion.

The program works fine as written above. But it would be easy to make a mistake that leads to a deadlock. Consider the following variation.

extern crate rand;
use std::thread;
use std::sync::{Arc, Mutex};

fn main() {
    let total_flips = Arc::new(Mutex::new(0));
    let completed = Arc::new(Mutex::new(0));
    let runs = 8;
    let target_flips = 10;

    for _ in 0..runs {
        let total_flips = total_flips.clone();
        let completed = completed.clone();
        thread::spawn(move || {
            simulate(target_flips, total_flips);
            let mut completed = completed.lock().unwrap();
            *completed += 1;
        });
    }
    
    let completed = completed.lock().unwrap();
    while *completed < runs {}
    let total_flips = total_flips.lock().unwrap();
    println!("Final average: {}", *total_flips / *completed);
}

fn simulate(target_flips: u64, total_flips: Arc<Mutex<u64>>) {
    let mut consecutive = 0;
    let mut iterations = 0;
    while consecutive < target_flips {
        iterations += 1;
        if rand::random() {
            consecutive += 1;
        } else {
            consecutive = 0;
        }
    }
    println!("iterations: {}", iterations);
    let mut total_flips = total_flips.lock().unwrap();
    *total_flips += iterations;
}

In this variation, the main thread retains ownership of the lock on completed. This causes all of the simulating threads to block. Unfortunately, the simulating threads cannot update completed because they are blocked. In the meantime, the main thread is waiting for the simulating threads to complete! This is an example of a deadlock. Although Rust prevents lots of concurrency problems, it can't prevent all of them! When writing multithreaded Rust code, it is always essential to retain locks for the smallest possible scope in order to avoid deadlocks.

I'd like to point out that there are alternatives to locks available in Rust. One intriguing option involves using lock-free data structures. I'd like to explore that library in more depth when time permits.