Implement a Binary Semaphore in Rust

Concurrency is a fundamental aspect of modern software development, enabling programs to perform multiple tasks simultaneously. Managing shared resources efficiently and preventing race conditions are critical challenges in concurrent programming. This challenge asks you to implement a binary semaphore in Rust, a synchronization primitive that can be used to control access to a shared resource by a limited number of threads.

Problem Description

Your task is to implement a BinarySemaphore struct in Rust that mimics the behavior of a traditional binary semaphore. A binary semaphore can be thought of as a mutex that can be "locked" and "unlocked" by multiple threads, but only allows one thread to hold the lock at a time. If a thread attempts to acquire the semaphore when it's already held, it will block until another thread releases it.

Key Requirements

1. BinarySemaphore struct: Create a struct named BinarySemaphore.
2. new() constructor: Implement a public associated function new(initial_count: usize) which creates a new semaphore. The initial_count should typically be 1 for a binary semaphore, indicating that the resource is initially available.
3. acquire() method: Implement a public method acquire() that attempts to decrement the semaphore's count.
   • If the count is greater than 0, decrement it and return immediately.
   • If the count is 0, the calling thread must block until the semaphore is available (i.e., until release() is called). Once available, decrement the count and return.
4. release() method: Implement a public method release() that increments the semaphore's count. If there are threads currently blocked on acquire(), one of them should be unblocked.
5. Thread Safety: The BinarySemaphore must be thread-safe. Multiple threads should be able to call acquire() and release() concurrently without causing data races or deadlocks.

Expected Behavior

When multiple threads access a shared resource protected by your BinarySemaphore:

• Threads will call acquire() to try and gain access.
• Only one thread can successfully acquire() the semaphore at a time if its initial count was 1.
• Other threads attempting to acquire() will wait.
• When a thread finishes with the resource, it will call release(), making the semaphore available for another waiting thread.

Important Edge Cases

• Initial count of 0: What happens if new(0) is called? The first acquire() should immediately block.
• Rapid Acquire/Release: Consider scenarios where threads acquire and release the semaphore in rapid succession.
• Many waiting threads: Ensure fair behavior when a large number of threads are blocked waiting to acquire the semaphore.

Examples

Example 1: A simple scenario with two threads.

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

// Assume BinarySemaphore implementation is available

let semaphore = Arc::new(BinarySemaphore::new(1)); // Initially available
let mut handles = vec![];

for i in 0..2 {
    let semaphore_clone = Arc::clone(&semaphore);
    let handle = thread::spawn(move || {
        println!("Thread {} attempting to acquire semaphore...", i);
        semaphore_clone.acquire();
        println!("Thread {} acquired semaphore. Working...", i);
        thread::sleep(Duration::from_millis(100)); // Simulate work
        println!("Thread {} releasing semaphore.", i);
        semaphore_clone.release();
    });
    handles.push(handle);
}

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

Expected Output (order may vary for the "acquired" and "releasing" lines):

Thread 0 attempting to acquire semaphore...
Thread 0 acquired semaphore. Working...
Thread 1 attempting to acquire semaphore...
Thread 0 releasing semaphore.
Thread 1 acquired semaphore. Working...
Thread 1 releasing semaphore.

Explanation: Thread 0 acquires the semaphore first. Thread 1 attempts to acquire it but blocks. Once Thread 0 releases it, Thread 1 acquires it, does its work, and then releases it.

Example 2: Demonstrating blocking behavior with initial_count = 0.

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

// Assume BinarySemaphore implementation is available

let semaphore = Arc::new(BinarySemaphore::new(0)); // Initially unavailable
let mut handles = vec![];

// Thread that will acquire and release
let semaphore_clone_holder = Arc::clone(&semaphore);
let holder_handle = thread::spawn(move || {
    println!("Holder thread: Waiting for 500ms before releasing...");
    thread::sleep(Duration::from_millis(500));
    println!("Holder thread: Releasing semaphore.");
    semaphore_clone_holder.release();
});
handles.push(holder_handle);

// Threads that will try to acquire
for i in 0..3 {
    let semaphore_clone_waiter = Arc::clone(&semaphore);
    let handle = thread::spawn(move || {
        println!("Waiter thread {} attempting to acquire semaphore...", i);
        semaphore_clone_waiter.acquire();
        println!("Waiter thread {} acquired semaphore.", i);
        // No release here to keep it simple, but in a real scenario, it would release
    });
    handles.push(handle);
}

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

Expected Output (order may vary for the "attempting" and "acquired" lines):

Waiter thread 0 attempting to acquire semaphore...
Waiter thread 1 attempting to acquire semaphore...
Waiter thread 2 attempting to acquire semaphore...
Holder thread: Waiting for 500ms before releasing...
Holder thread: Releasing semaphore.
Waiter thread X acquired semaphore. // One of the waiter threads will acquire
Waiter thread Y acquired semaphore. // Another waiter thread if semaphore was re-released
Waiter thread Z acquired semaphore. // If more releases happened

Explanation: All waiter threads will initially block because the semaphore count is 0. The holder thread waits for 500ms and then releases the semaphore. This allows one of the waiting threads to acquire it. If more releases occurred, other waiting threads would eventually acquire it. The exact order of which waiter thread acquires it first depends on OS scheduling.

Constraints

• The BinarySemaphore must be implemented using only standard library concurrency primitives (std::sync, std::thread). You should not use external crates.
• The acquire() and release() methods should not panic under normal operation (e.g., no out-of-bounds access or invalid states).
• The implementation should aim for reasonable efficiency, avoiding busy-waiting where possible.

Notes

• Consider using std::sync::Mutex and std::sync::Condvar to manage the internal state of the semaphore and to signal waiting threads.
• Think about how to represent the semaphore's count and how to protect it from concurrent access.
• When a thread calls acquire() and finds the count is 0, it needs to wait. Condvar::wait() is designed for this purpose.
• When a thread calls release() and there are waiting threads, it needs to notify one of them. Condvar::notify_one() is suitable here.
• Be mindful of the MutexGuard returned by Mutex::lock(). It ensures that the lock is released when it goes out of scope, which is crucial for preventing deadlocks.
• The problem specifies a "binary" semaphore, implying an initial count of 1. However, your new() function should accept initial_count to be more general, and the logic for acquire/release should correctly handle any non-negative usize count. The focus for testing and understanding is on the binary use case.