based locks. The more basic locking mechanisms have lower uncontended latency than the advanced locking mechanisms. Advantages One 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. A ticket lock algorithm also prevents the thundering herd problem occurring since only one thread at a time tries to enter the critical section. Storage is not necessarily a problem as all threads spin on one variable, unlike array-based queueing locks (ABQL) who have threads spin on individual elements of an array. Disadvantages One disadvantage is that there is a higher uncontended latency due to the extra instructions required to read and test the value that all threads are spinning on before a lock is released. Another major disadvantage of a ticket lock is that it is non-scalable. Research indicated that as processors are added to a Ticket Lock system, performance appears to decay exponentially. Another problem comes from releasing a lock. All threads are spinning on one variable, so when the lock is released there are Ө(p) invalidations (as well as Ө(p) acquisitions). This is because all threads must reload their block into the cache and perform a test to determine their admittance to the critical section. History The ticket lock was introduced by Mellor-Crummey and Scott in 1991. This algorithm was introduced into the Linux kernel in 2008 due to its advantages, but was omitted in paravirtualized environments where it had disadvantages. , work is in progress to enable the use of ticket locks in paravirtualization. As of March 2015 this type of locking scheme has been reemployed by Red Hat Enterprise Linux in their system. Related work Lamport's bakery algorithm uses a similar concept of a "ticket" or "counter" but does not make the use of atomic hardware operations. It was designed for fault tolerance rather than performance. Rather than all processors continuously examining the release counter, the bakery lock spins on examining the tickets of its peers. 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. See also fetch-and-add, another atomic instruction that can be used in place of fetch-and-increment to implement a ticket lock References Concurrency control algorithms