Building Thread-Safe Primitives in Rust

Concurrency is a fundamental aspect of modern software development, enabling applications to perform multiple tasks simultaneously and improve responsiveness. Rust provides robust tools for managing concurrent operations safely, but understanding the underlying mechanisms of synchronization primitives is crucial for building reliable and efficient multi-threaded applications. This challenge asks you to implement common synchronization primitives from scratch, deepening your understanding of Rust's concurrency model.

Problem Description

Your task is to implement two fundamental synchronization primitives in Rust: a Mutex and a Semaphore. These primitives are essential for controlling access to shared resources in a multi-threaded environment, preventing race conditions and ensuring data integrity.

You will need to implement:

1. A Basic Mutex (MyMutex):

   • This mutex should allow only one thread to acquire a lock at a time.
   • It should wrap a piece of data and provide methods to acquire and release the lock, allowing mutable access to the wrapped data while locked.
   • The mutex should be thread-safe, meaning it can be shared and used across multiple threads.
   • When a thread attempts to acquire a lock that is already held, it should block until the lock is released.

2. A Basic Semaphore (MySemaphore):

   • This semaphore should manage a counter representing available permits.
   • It should provide methods to acquire a permit (decrementing the counter and blocking if no permits are available) and release a permit (incrementing the counter and potentially waking up a blocked thread).
   • The semaphore should be initialized with a specific number of permits.
   • It must be thread-safe.

Key Requirements:

• Thread Safety: Your implementations must be safe to use across multiple threads. This implies careful handling of shared state and synchronization.
• Blocking Behavior: Threads attempting to acquire a lock or permit when none are available should block.
• Correctness: The primitives should behave according to their standard definitions, ensuring mutual exclusion for the mutex and controlled resource access for the semaphore.
• No External Crates (for core logic): While you can use standard library types like std::thread, std::sync::Arc, std::sync::atomic, and std::sync::Condvar, your core mutex and semaphore logic should not rely on existing std::sync::Mutex or std::sync::Semaphore implementations.

Expected Behavior:

• A MyMutex should allow a thread to lock() and get a guard. When the guard goes out of scope, the mutex should be unlock()ed. If multiple threads try to lock() simultaneously, only one should succeed, and the others should wait.
• A MySemaphore initialized with N permits should allow up to N threads to acquire() successfully. Subsequent acquire() calls should block until a release() occurs.

Edge Cases to Consider:

• Multiple threads contending for the same lock/semaphore.
• Releasing a lock/permit when no thread is holding it (though this might be an invalid operation depending on API design, consider its implications).
• A thread holding a lock/permit and then panicking (this is a more advanced consideration for robustness, but for this challenge, assume normal operation).

Examples

Example 1: MyMutex - Basic Usage

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

// Assume MyMutex is implemented and imported
// let mutex = Arc::new(MyMutex::new(0));
// let mut handles = vec![];

// for _ in 0..5 {
//     let mutex = Arc::clone(&mutex);
//     let handle = thread::spawn(move || {
//         let mut num = mutex.lock(); // Acquire lock
//         *num += 1;
//         println!("Incremented to: {}", *num);
//         thread::sleep(Duration::from_millis(10));
//         // Lock is automatically released when `num` (the guard) goes out of scope
//     });
//     handles.push(handle);
// }

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

// // After all threads finish, the final value should reflect all increments.
// // If the mutex works correctly, the final value should be 5.
// // println!("Final value: {}", *mutex.lock());

Expected Output (order may vary due to thread scheduling):

Incremented to: 1
Incremented to: 2
Incremented to: 3
Incremented to: 4
Incremented to: 5
Final value: 5

Explanation: Each of the 5 threads attempts to acquire the mutex. Only one thread can hold the lock at a time. Each thread increments the shared counter and prints the value. Because the increments happen serially (due to the mutex), the final value is predictably 5.

Example 2: MySemaphore - Resource Pool Simulation

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

// Assume MySemaphore is implemented and imported
// let semaphore = Arc::new(MySemaphore::new(2)); // Allow 2 concurrent users
// let mut handles = vec![];

// for i in 0..5 {
//     let semaphore = Arc::clone(&semaphore);
//     let handle = thread::spawn(move || {
//         println!("Thread {} waiting to acquire permit...", i);
//         semaphore.acquire(); // Block until a permit is available
//         println!("Thread {} acquired permit. Working...", i);
//         thread::sleep(Duration::from_secs(1)); // Simulate work
//         println!("Thread {} releasing permit.", i);
//         semaphore.release(); // Release the permit
//     });
//     handles.push(handle);
// }

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

Expected Output (order may vary, but observe the concurrency limit):

Thread 0 waiting to acquire permit...
Thread 0 acquired permit. Working...
Thread 1 waiting to acquire permit...
Thread 1 acquired permit. Working...
Thread 2 waiting to acquire permit...
Thread 3 waiting to acquire permit...
Thread 4 waiting to acquire permit...
Thread 0 releasing permit.
Thread 2 acquired permit. Working...
Thread 1 releasing permit.
Thread 3 acquired permit. Working...
Thread 2 releasing permit.
Thread 4 acquired permit. Working...
Thread 3 releasing permit.
Thread 4 releasing permit.

Explanation: The semaphore is initialized with 2 permits. Threads 0 and 1 acquire permits immediately and start "working". Threads 2, 3, and 4 block. Once thread 0 finishes and releases its permit, one of the waiting threads (e.g., thread 2) can acquire it. This continues until all threads have had a chance to acquire and release a permit.

Example 3: MyMutex - Contention and Fairness (Conceptual)

This example illustrates the concept, actual output order will vary.

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

// Assume MyMutex is implemented and imported
// let mutex = Arc::new(MyMutex::new(0));
// let mut handles = vec![];

// // Spawn a thread that holds the lock for a while
// let mutex_clone1 = Arc::clone(&mutex);
// let h1 = thread::spawn(move || {
//     let mut guard = mutex_clone1.lock();
//     println!("Thread 1 acquired lock.");
//     *guard = 100;
//     thread::sleep(Duration::from_millis(500));
//     println!("Thread 1 releasing lock.");
// });
// handles.push(h1);

// // Spawn other threads that will contend for the lock
// for i in 2..5 {
//     let mutex_clone = Arc::clone(&mutex);
//     let handle = thread::spawn(move || {
//         println!("Thread {} waiting for lock...", i);
//         let mut guard = mutex_clone.lock();
//         println!("Thread {} acquired lock. Value: {}", i, *guard);
//         *guard += 1;
//         thread::sleep(Duration::from_millis(50));
//         println!("Thread {} releasing lock.", i);
//     });
//     handles.push(handle);
// }

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

Expected Behavior (illustrative order):

Thread 1 acquired lock.
Thread 2 waiting for lock...
Thread 3 waiting for lock...
Thread 4 waiting for lock...
Thread 1 releasing lock.
Thread 2 acquired lock. Value: 100
Thread 2 releasing lock.
Thread 3 acquired lock. Value: 101
Thread 3 releasing lock.
Thread 4 acquired lock. Value: 102
Thread 4 releasing lock.

Explanation: Thread 1 acquires the lock first and holds it for a significant duration. During this time, other threads (2, 3, 4) attempting to acquire the lock will block. Once Thread 1 releases the lock, one of the waiting threads will acquire it, perform its operation, and release it, allowing another waiting thread to proceed.

Constraints

• Language: Rust
• Target Platform: Standard Rust installation (no special hardware or OS features required).
• Performance: While not strictly timed, your implementations should avoid busy-waiting loops for blocking behavior. Use appropriate synchronization primitives like std::sync::Condvar for efficient blocking.
• Data Types: MyMutex should be generic over the type T it protects. MySemaphore should be an integer type, e.g., u32.

Notes

• std::sync::Arc: You will likely need Arc to share your mutex and semaphore instances across multiple threads.
• std::sync::atomic: For managing the internal state of your primitives (like lock flags or semaphore counts) in a thread-safe manner without resorting to other locks.
• std::sync::Condvar: This is your primary tool for signaling between threads. When a thread needs to wait (e.g., for a lock to be released or a semaphore permit to become available), it should use a Condvar to block efficiently. When the condition is met (e.g., lock released, permit available), another thread will notify the Condvar to wake up a waiting thread.
• Mutex Guard: For MyMutex, consider implementing a "lock guard" struct that automatically unlocks the mutex when it's dropped (RAII pattern). This is idiomatic Rust and helps prevent deadlocks caused by forgotten unlocks.
• Poisoning (Advanced Consideration): Real-world mutexes often have a "poisoning" mechanism that indicates if a thread panicked while holding the lock. This is a more advanced feature and not strictly required for this challenge, but worth considering for robustness.
• Fairness: The simplest implementations of Condvar might not guarantee fairness (i.e., the order in which threads are woken up might not be strictly FIFO). For this challenge, basic correctness is the priority.