Tidex: a mutual exclusion lock

Abstract

Several basic mutual exclusion lock algorithms are known, with one of the simplest being the Ticket Lock. We present a new mutual exclusion lock with properties similar to the Ticket Lock but using atomic_exchange() instead of atomic_fetch_add() that can be more efficient on systems without a native instruction for atomic_fetch_add(), or in which the native instruction for atomic_exchange() is faster than the one for atomic_fetch_add(). Similarly to the Ticket Lock, our lock has small memory foot print, is extremely simple, respects FIFO order, and provides starvation freedom in architectures that implement atomic_exchange() as a single instruction, like x86.