Optimizing a FIFO, Scalable Spin Lock
Using Consistent Memory
This paper presents a FIFO
queue-based spin lock that
(1) uses only one atomic swap
operation;
(2) is scalable as it requires
a constant amount of communication; (3) runs without
a coherent cache support; and (4) provides a
timing guarantee required for real-time applications.
The algorithm is optimal in terms of the number of atomic
operations required to solve a scalable mutual exclusion
problem in NUMA architectures, improving on Craig's
spin lock that uses four atomic swap operations.
It minimizes the number of atomic operations
by replacing them with non-atomic read and write operations.
This optimization can benefit greatly from modern multiprocessors
where non-atomic memory operations are much more optimized
than atomic operations.
The algorithm runs correctly
in various weakly consistent memories, providing
a potentially significant speed-up over the algorithms
with more atomic operations.
PS COPY