Building Basic Synchronization Primitives in Rust

Rust's standard library provides powerful synchronization primitives, but understanding how they work at a lower level is crucial for writing efficient and correct concurrent code. This challenge asks you to implement simplified versions of a mutex and a condition variable, giving you a deeper insight into the mechanics of thread synchronization. Successfully completing this challenge will solidify your understanding of shared mutable state and how to manage it safely in a concurrent environment.

Problem Description

You are tasked with implementing two fundamental synchronization primitives: a Mutex and a Condvar. These primitives are essential for managing access to shared mutable data in a concurrent setting, preventing race conditions and ensuring data integrity.

Mutex: The Mutex (Mutual Exclusion) should provide exclusive access to a protected resource. Only one thread can hold the lock at a time. Other threads attempting to acquire the lock will block until the lock is released.

Condvar: The Condvar (Condition Variable) allows threads to wait for a specific condition to become true. Threads can wait on a Condvar while releasing the associated Mutex. When another thread changes the condition and notifies the Condvar, waiting threads are awakened and can re-acquire the Mutex to check the condition again.

Key Requirements:

• Mutex:
  • lock(): Acquires the lock. Blocks if the lock is already held.
  • unlock(): Releases the lock. Must be called by the thread that holds the lock.
  • is_locked(): Returns true if the lock is currently held, false otherwise.
• Condvar:
  • wait(mutex: &Mutex): Atomically releases the Mutex and waits for a notification. Must be called while holding the Mutex. Reacquires the Mutex upon awakening.
  • notify_one(): Awakens one waiting thread.
  • notify_all(): Awakens all waiting threads.

Expected Behavior:

• Threads should block correctly when attempting to acquire a locked Mutex.
• wait() should atomically release the Mutex and suspend the thread.
• notify_one() and notify_all() should correctly wake up waiting threads.
• The Mutex should be reacquired by the thread after wait() returns.
• Error handling: While not strictly required for this simplified implementation, consider how you might handle errors like attempting to unlock a Mutex that isn't held.

Edge Cases to Consider:

• Spurious wakeups: Condition variables can sometimes wake up threads even when no notification has been sent. Your wait() implementation should handle this by reacquiring the mutex and rechecking the condition.
• Multiple threads waiting: Ensure that notify_one() and notify_all() correctly wake up the appropriate threads.
• Nested waits: While not required, consider how your implementation would behave if a thread attempts to call wait() while already waiting on the Condvar.

Examples

Example 1: Mutex Basic Locking

Input: Two threads, both attempting to lock a Mutex.
Output: Only one thread successfully acquires the lock at a time. The other thread blocks until the lock is released.
Explanation: Demonstrates the exclusive access provided by the Mutex.

Example 2: Condvar Wait and Notify

Input:
Thread 1: Holds a Mutex, calls wait() on a Condvar.
Thread 2: Holds the same Mutex, changes a condition, calls notify_one() on the Condvar.
Output: Thread 1 is awakened and reacquires the Mutex.
Explanation: Shows the basic functionality of waiting on a condition and being notified.

Example 3: Multiple Waiters

Input:
Three threads, all waiting on a Condvar.
Thread 4: Holds the Mutex, calls notify_all() on the Condvar.
Output: All three waiting threads are awakened.
Explanation: Demonstrates the behavior of notify_all().

Constraints

• No external crates: You are not allowed to use external crates like std::sync. You must implement the primitives from scratch using only the standard library.
• Atomicity: The atomic release and reacquisition of the mutex within Condvar::wait is critical. Use std::sync::atomic::Ordering::Release and std::sync::atomic::Ordering::Acquire for this.
• Performance: While not the primary focus, avoid unnecessary overhead. Reasonable performance is expected.
• Safety: The code must be memory-safe and free from data races.

Notes

• Start by implementing the Mutex first, as it's a building block for the Condvar.
• Consider using an AtomicBool to track whether the mutex is locked.
• The Condvar's waiting mechanism will likely involve a queue or similar data structure to manage waiting threads. You can use a Vec for simplicity, but be mindful of potential performance implications with large numbers of waiting threads.
• Spurious wakeups are a common issue with condition variables. Always recheck the condition after being awakened.
• Think carefully about the order of operations in Condvar::wait() to ensure atomicity. The mutex release and thread suspension must happen as a single, indivisible operation.
• This is a simplified implementation. Production-quality synchronization primitives are significantly more complex and optimized. The goal here is to understand the core concepts.