  The classic ticket lock consists of ticket and grant fields. Arriving threads
atomically fetch-and-increment ticket and then wait for grant to become equal
to the value returned by the fetch-and-increment primitive, at which point the
thread holds the lock. The corresponding unlock operation simply increments
grant. This simple design has short code paths and fast handover (transfer of
ownership) under light contention, but may suffer degraded scalability under
high contention when multiple threads busy wait on the grant field -- so-called
global spinning. We propose a variation on ticket locks where long-term waiting
threads wait on locations in a waiting array instead of busy waiting on the
grant field. The single waiting array is shared among all locks. Short-term
waiting is accomplished in the usual manner on the grant field. The resulting
algorithm, TWA, improves on ticket locks by limiting the number of threads
spinning on the grant field at any given time, reducing the number of remote
caches requiring invalidation from the store that releases the lock. In turn,
this accelerates handover, and since the lock is held throughout the handover
operation, scalability improves. Under light or no contention, TWA yields
performance comparable to the classic ticket lock, avoiding the complexity and
extra accesses incurred by MCS locks in the handover path, but providing
performance above or beyond that of MCS at high contention.
