Spin lock
Implement a spin lock: a mutual-exclusion lock that waits by spinning on an atomic flag in user space instead of sleeping in the kernel.
lock() returns once the calling thread holds the lock. try_lock() takes the lock only if it is free right now, and returns whether it did. unlock() releases it, and is only ever called by the holder.
Build it from atomics. No std::mutex, pthread_mutex_t, std::sync::Mutex, or any other OS-backed lock. The driver sends many threads through a critical section that increments a plain, non-atomic counter, so getting the atomic operation right is not enough: the memory ordering has to make each holder's writes visible to the next.
Spinning burns CPU, and the holder can be preempted while everyone else spins. The tests run more threads than there are CPUs, so a lock that never backs off or yields will run out of time.
Constraints
- 1 ≤ threads ≤ 8
- threads × iterations ≤ 400,000
- The program gets 2 CPUs; CPU time is summed across all threads
- CPU time
- 4000 ms
- Memory
- 256 MB
- CPUs
- 2
Examples
1 1000
try_lock 101 counter 1000 overlaps none
4 20000
try_lock 101 counter 80000 overlaps none
ThreadSanitizer check
Once a C++ solution passes the tests, it's rebuilt with ThreadSanitizer and run again on this input. It catches data races, including ones a missing memory ordering hides on x86. Any report fails the submission, even when the output is right.
4 2000How your code is tested
Your code is compiled together with this driver, which reads each test's input from stdin and prints what it observed. Hidden tests use the same driver with different inputs.
// Reads "<threads> <iterations>" and checks try_lock semantics, then
// mutual exclusion and visibility under contention.
int main() {
int threads = 0, iterations = 0;
std::cin >> threads >> iterations;
SpinLock lock;
bool first = lock.try_lock(); // free: must succeed
bool second = lock.try_lock(); // held: must fail
lock.unlock();
bool third = lock.try_lock(); // free again
lock.unlock();
std::cout << "try_lock " << first << second << third << "\n";
long long counter = 0; // deliberately not atomic: the lock protects it
std::atomic<int> inside{0};
std::atomic<bool> overlapped{false};
std::vector<std::thread> workers;
for (int t = 0; t < threads; ++t) {
workers.emplace_back([&] {
for (int i = 0; i < iterations; ++i) {
lock.lock();
if (inside.fetch_add(1, std::memory_order_relaxed) != 0) {
overlapped.store(true, std::memory_order_relaxed);
}
++counter;
inside.fetch_sub(1, std::memory_order_relaxed);
lock.unlock();
}
});
}
for (auto& w : workers) w.join();
std::cout << "counter " << counter << "\n";
std::cout << "overlaps " << (overlapped.load() ? "yes" : "none") << "\n";
}
// Reads "<threads> <iterations>" and checks try_lock semantics, then
// mutual exclusion and visibility under contention.
struct KataCounter(std::cell::UnsafeCell<u64>);
// Deliberately unsynchronized: only the lock under test protects it.
unsafe impl Sync for KataCounter {}
fn main() {
use std::io::Read;
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
let mut input = String::new();
std::io::stdin().read_to_string(&mut input).unwrap();
let mut nums = input.split_whitespace().map(|x| x.parse::<usize>().unwrap());
let (threads, iterations) = (nums.next().unwrap(), nums.next().unwrap());
let lock = Arc::new(SpinLock::new());
let first = lock.try_lock();
let second = lock.try_lock();
lock.unlock();
let third = lock.try_lock();
lock.unlock();
println!("try_lock {}{}{}", first as u8, second as u8, third as u8);
let counter = Arc::new(KataCounter(std::cell::UnsafeCell::new(0)));
let inside = Arc::new(AtomicUsize::new(0));
let overlapped = Arc::new(AtomicBool::new(false));
let workers: Vec<_> = (0..threads)
.map(|_| {
let (lock, counter) = (Arc::clone(&lock), Arc::clone(&counter));
let (inside, overlapped) = (Arc::clone(&inside), Arc::clone(&overlapped));
std::thread::spawn(move || {
for _ in 0..iterations {
lock.lock();
if inside.fetch_add(1, Ordering::Relaxed) != 0 {
overlapped.store(true, Ordering::Relaxed);
}
unsafe { *counter.0.get() += 1 };
inside.fetch_sub(1, Ordering::Relaxed);
lock.unlock();
}
})
})
.collect();
for w in workers {
w.join().unwrap();
}
println!("counter {}", unsafe { *counter.0.get() });
println!("overlaps {}", if overlapped.load(Ordering::Relaxed) { "yes" } else { "none" });
}