Ticket lock

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computer science, a ticket lock is a locking algorithm that is a type of spinlock which uses "tickets" to control which thread of execution is allowed to enter a critical section.

Overview[edit]

A ticket lock works as follows; there are two integer values which begin at 0. The first value is the queue ticket, the second is the dequeue ticket.

When a thread arrives, it atomically obtains and then increments the queue ticket. It then atomically compares its ticket's value (before the increment) with the dequeue ticket's value. If they are the same, the thread is permitted to enter the critical section. If they are not the same, then another thread must already be in the critical section and this thread must busy wait or yield. When a thread leaves the critical section controlled by the lock, it atomically increments the dequeue ticket. This permits the next waiting thread to enter the critical section.

Advantages[edit]

The advantage of a ticket lock over other spinlock algorithms is that it is fair. The waiting threads are processed in a first-in first-out basis as the dequeue ticket integer increases, thus preventing starvation. It also prevents the thundering herd problem occurring since only one thread at a time tries to enter the critical section. The Linux kernel implementation can have lower latency than the simpler test-and-set or exchange based spinlock algorithms on modern machines.[citation needed]

This algorithm was introduced into the Linux kernel in 2008 due to its advantages,[1] but was omitted in paravirtualized environments where it had disadvantages.[2] As of July 2010, work is in progress to enable the use of ticket locks in paravirtualization.[3][4]

Related work[edit]

  • Lamport's bakery algorithm also uses atomic operations (loads and stores) to ensure that the ticket numbers are unique, but requires O(n) space and time, whereas the ticket lock is O(1) and uses an atomic increment operation.
  • Queue-based spin locks guarantee fairness by maintaining a queue of waiters and by granting the lock to the first waiter during an unlock operation.[5]

See also[edit]

fetch-and-add, an instruction that can be used to implement a ticket lock

References[edit]

  1. ^ Jonathan Corbet, Ticket spinlocks, Linux Weekly News, February 6, 2008. Retrieved 23. July, 2010.
  2. ^ Jeremy Fitzhardinge, paravirt: introduce a "lock-byte" spinlock implementation, Linux kernel, July 7, 2008
  3. ^ x86/spinlocks: replace pv spinlocks with pv ticketlocks
  4. ^ Revert "Merge branch 'xen/pvticketlock' into xen/next"
  5. ^ Michael L. Scott and William N. Scherer III. Scalable Queue-Based Spin Locks with Timeout. Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, pp. 44-52, 2001.