Implementing a Basic Mutex in Rust

Concurrency is a fundamental aspect of modern software development. When multiple threads access shared mutable data, it can lead to race conditions, where the final outcome depends on the unpredictable timing of thread execution. A Mutex (Mutual Exclusion) is a synchronization primitive that prevents this by ensuring that only one thread can access a shared resource at a time. This challenge involves building a simplified Mutex from scratch in Rust to understand its core principles.

Problem Description

Your task is to implement a basic Mutex in Rust that can protect a shared piece of data. This Mutex should allow only one thread to hold a lock on the data at any given time. If a thread attempts to acquire the lock while it's already held, the thread should block until the lock is released.

Key Requirements:

1. Mutex<T> Struct: Define a generic struct Mutex<T> that holds the data T it will protect.
2. lock() Method: Implement a lock() method on Mutex<T>. This method should:
   • Attempt to acquire the lock.
   • If the lock is available, acquire it and return a guard.
   • If the lock is already held, the calling thread must block until the lock becomes available.
3. MutexGuard<'a, T> Struct: Implement a MutexGuard<'a, T> struct. This guard should:
   • Hold a reference to the protected data T.
   • Implement Deref and DerefMut to allow mutable access to the protected data.
   • When the MutexGuard goes out of scope (is dropped), it must automatically release the lock.
4. Thread Safety: The implementation must be thread-safe.

Expected Behavior:

When multiple threads try to access the data protected by the Mutex, only one thread should be able to modify the data at a time. Other threads attempting to access it will wait.

Edge Cases:

• Deadlocks: While a full deadlock detection mechanism is beyond the scope of this basic implementation, be mindful of how your locking and unlocking logic might contribute to deadlocks in more complex scenarios.
• Multiple threads waiting: Ensure that when a lock is released, one of the waiting threads correctly acquires it.

Examples

Example 1: Basic Usage

use std::sync::Arc;
use std::thread;

// Assume you have implemented Mutex<T> and MutexGuard<'a, T> here

fn main() {
    let counter = Arc::new(Mutex::new(0));
    let mut handles = vec![];

    for _ in 0..10 {
        let counter = Arc::clone(&counter);
        let handle = thread::spawn(move || {
            let mut num = counter.lock(); // Acquire the lock
            *num += 1; // Mutate the shared data
        });
        handles.push(handle);
    }

    for handle in handles {
        handle.join().unwrap();
    }

    println!("Result: {}", *counter.lock());
}

Expected Output:

Result: 10

Explanation:

Ten threads each attempt to increment a shared counter. Without a Mutex, this would likely result in a value less than 10 due to race conditions. With the implemented Mutex, each thread successfully acquires the lock, increments the counter, and then releases the lock, ensuring the final value is 10.

Example 2: Demonstrating Blocking

use std::sync::Arc;
use std::thread;
use std::time::Duration;

// Assume you have implemented Mutex<T> and MutexGuard<'a, T> here

fn main() {
    let data = Arc::new(Mutex::new(String::from("Initial")));
    let mut handles = vec![];

    // Thread 1 locks and holds for a bit
    let data1 = Arc::clone(&data);
    let handle1 = thread::spawn(move || {
        let mut s = data1.lock();
        s.push_str(" (locked by thread 1)");
        println!("Thread 1: Acquired lock and modified.");
        thread::sleep(Duration::from_millis(100)); // Hold lock
        println!("Thread 1: Releasing lock.");
    });
    handles.push(handle1);

    // Give Thread 1 a moment to acquire the lock
    thread::sleep(Duration::from_millis(10));

    // Thread 2 tries to acquire the lock while Thread 1 holds it
    let data2 = Arc::clone(&data);
    let handle2 = thread::spawn(move || {
        println!("Thread 2: Attempting to acquire lock...");
        let mut s = data2.lock(); // This should block
        println!("Thread 2: Acquired lock.");
        s.push_str(" (modified by thread 2)");
    });
    handles.push(handle2);

    for handle in handles {
        handle.join().unwrap();
    }

    println!("Final data: {}", *data.lock());
}

Expected Output (order of "Acquired lock" messages may vary slightly, but Thread 2's acquisition will be after Thread 1's release):

Thread 1: Acquired lock and modified.
Thread 1: Releasing lock.
Thread 2: Attempting to acquire lock...
Thread 2: Acquired lock.
Final data: Initial (locked by thread 1) (modified by thread 2)

Explanation:

Thread 1 acquires the lock, modifies the string, and holds the lock for a short duration. Thread 2 attempts to acquire the lock while Thread 1 still holds it, causing Thread 2 to block. Once Thread 1 releases the lock, Thread 2 acquires it and modifies the string. The final output reflects modifications from both threads in the correct sequence.

Constraints

• Your Mutex<T> implementation should be able to hold any data type T that is Send and 'static.
• The underlying synchronization mechanism used for blocking and waking threads should be efficient and idiomatic for Rust concurrency. You can use primitives from std::sync or std::sync::atomic as needed, but the core locking logic should be your implementation.
• The lock() method should not panic if called on a Mutex that has already been poisoned (i.e., a thread holding the lock panicked). For this basic implementation, you can choose to either propagate the panic or return a valid MutexGuard (though propagating is more typical for a robust Mutex). Let's aim for propagating the panic for this exercise.

Notes

• Consider how to represent the "locked" state and how threads will wait and be notified.
• The MutexGuard's Drop implementation is crucial for ensuring the lock is always released, even if errors occur within the critical section.
• You will likely need to use Arc to share the Mutex across threads, as Mutex itself is not Copy.
• Think about how to signal between threads when the lock is available. std::sync::Condvar might be a useful tool here, or you could explore other lower-level primitives if you're feeling adventurous (though Condvar is generally the idiomatic choice for this pattern).
• For the blocking mechanism, consider how to atomically check the lock state and put the thread to sleep if it's not available.