Ticket lock

This is the method that many bakeries and delis use to serve customers in the order that they arrive, without making them stand in a line.

It adds the benefit of fairness of lock acquisition and works as follows; there are two integer values which begin at 0.

The atomicity of this operation is required to prevent two threads from simultaneously being able to obtain the same ticket number.

When a thread leaves the critical section controlled by the lock, it atomically increments the dequeue ticket.

This permits the next waiting thread, the one with the next sequential ticket number, to enter the critical section.

A simple example will now be presented to show how a thread could be excessively delayed due to a lack of fairness in lock acquisition.

Now further assume the physical arrangement of the three processors, P1, P2, and P3, results in a non-uniform memory access time to the location of the shared lock variable.

How this situation leads to thread starvation in the absence of a fairness guarantee is shown in the following illustration of the execution of the above pseudocode by these three processors.

Once P2 finishes the critical section and issues an unlock, both P1 and P3 simultaneously attempt to acquire it once again (Time 6).

Not all locks have mechanisms that ensure any level of fairness, leaving the potential for situations similar to that illustrated above.

[1]Following along with the pseudocode above we can see that each time a processor tries to acquire a lock with ticketLock_acquire(), fetch_and_inc is called, returning the current value of next_ticket into the thread private my_ticket and incrementing the shared next_ticket.

The following table shows an example of ticket lock in action in a system with four processors (P1, P2, P3, P4) competing for access to the critical section.

All subsequent attempts, while the first still holds the lock, serves to form the queue of processors waiting their turn in 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.

[3] This algorithm was introduced into the Linux kernel in 2008 due to its advantages,[5] but was omitted in paravirtualized environments where it had disadvantages.

[7] As of March 2015 this type of locking scheme has been reemployed by Red Hat Enterprise Linux in their system.