In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, a ticket lock is a locking algorithm

Lock (computer science)

In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...

 that is a type of spinlock

Spinlock

In software engineering, a spinlock is a lock where the thread simply waits in a loop repeatedly checking until the lock becomes available. Since the thread remains active but isn't performing a useful task, the use of such a lock is a kind of busy waiting...

 which uses "tickets" to control which thread

Thread (computer science)

In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...

 of execution is allowed to enter a critical section

Critical section

In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...

.

Overview

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 with the dequeue ticket. 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

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

Resource starvation

In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task....

. It also prevents the thundering herd problem

Thundering herd problem

The thundering herd problem occurs when a large number of processes waiting for an event are awoken when that event occurs, but only one process is able to proceed at a time. After the processes wake up, they all demand the resource and a decision must be made as to which process can continue...

 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

Test-and-set

In computer science, the test-and-set instruction is an instruction used to write to a memory location and return its old value as a single atomic operation. If multiple processes may access the same memory, and if a process is currently performing a test-and-set, no other process may begin...

 or exchange

Compare-and-swap

In computer science, the compare-and-swap CPU instruction is a special instruction that atomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value...

 based spinlock algorithms on modern machines.

This algorithm was introduced into the Linux kernel

Linux kernel

The Linux kernel is an operating system kernel used by the Linux family of Unix-like operating systems. It is one of the most prominent examples of free and open source software....

 in 2008 due to its advantages, but was omitted in paravirtualized

Paravirtualization

In computing, paravirtualization is a virtualization technique that presents a software interface to virtual machines that is similar but not identical to that of the underlying hardware....

 environments where it had disadvantages. , work is in progress to enable the use of ticket locks in paravirtualization.

Compare

• Lamport's Bakery algorithm
  Lamport's bakery algorithm
  Lamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion....
  
   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.