bringing practical lock-free synchronization to 64-bit applications
Many lock-free data structures in the literature exploit techniques that are possible only because state-of-the-art 64-bit processors are still running 32-bit operating systems and applications. As software catches up to hardware, "64-bit-clean" lock-free data structures, which cannot use such techniques, are needed.We present several 64-bit-clean lock-free implementations: load-linked/store-conditional variables of arbitrary size, a FIFO queue, and a freelist. In addition to being portable to 64-bit software, our implementations also improve on previous ones in that they are space-adaptive and do not require knowledge of the number of threads that will access them.
practical lock-free synchronization applications data structures exploit processor operating system software hardware use implementation variability size queues freelists portability space-adaptive knowledge thread access memory management population-oblivious load-linked/store-conditional (ll/sc) 64-bit architectures art nonblocking synchronization compare-and-swap (cas) 64-bit-clean software multiprocessors adapt space