This is an implementation of futex-based user space blocking synchronization. In this lock implementation, one first tries atomic operations (Compare-And-Swap) to test if one can get the lock immediately. If it fails, it calls futex() which makes it (probably) sleep. Later, it is waken up when the lock holder releases the lock by calling futex() with FUTEX_WAKE operation flag. Even after waking up, it checks if the lock variable represents that lock is "not-held-state" and retries futex() if it does not. This prevents sprious wakeup from negating the correctness of the synchronization.
To test the correctness of our implementation, we conducted a experiment where we create N_THREADS threads and each thread
- calls lock() method
- increases the global variable
- calls unlock() method
- repeats [1-3] N_INC times.
Then checks if (N_THREADS * N_INC) is equal to the value of the global variable. In addition to the futex-lock, we also conduct the same test using dummy lock, simple Compare-And-Swap lock and pthread_mutex_lock. The experiment showed that every lock except dummy lock guarantees correct synchronization.
We run tests to investigate the performace of the futex-lock. In all tests, threads acquire the lock and perform simple global variable increment.
In our futex lock, we try atomic operations (CAS) for the lock variable before we call futex(). We vary the number of CAS and evaluate the lock performance to investigate how the futex-lock's performance behavior is affected by the number of CAS before blocking.
We evaluate and compare the performance of following synchronizaiton primitives.
- dummy-lock (which is simply a no-op)
- CAS-lock
- pthread_mutex_lock
- futex-lock
Correctness is checked for each lock.
./install.sh or
./debug_install.sh (for enabling -g compile option)build/futex_backoff_test/futex_backoff_test
build/locks_test/locks_test <# of threads>
build/corr_check/corr_checkWe will humbly welcome your contributions!
Distributed under the MIT License.