Ticket lock

A ticket lock is a form of lockless inter-thread synchronization.

Overview

Conventionally, inter-thread synchronization is achieved by using synchronization entities provided by the operating system, such as events, semaphores and mutexes.

For example, a thread will create a mutex and in the act of creation, "claim" the mutex. A mutex can have only one owner at any time. Other threads, when they come to the point where their behaviour must be synchronized, will attempt to "claim" the mutex; if they cannot, because another thread already owns the mutex, they automatically sleep until the thread which currently owns the mutex gives it up. Then one of the currently sleeping threads will automatically be awoken and given ownership of the mutex.

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 serialised code. If they are not the same, then another thread must already be in the serialised code and this thread must busy-wait or yield. When a thread has comes to leave the serialised code, it atomically increments the dequeue ticket, thus permitting the next waiting thread to enter the serialised code.

This approach is heavyweight (high-overhead, code intensive), in that such entities have a significant impact upon the performance of the operating system, since the operating system has to switch into a special mode when dealing with operations upon synchronization entities to ensure they provide synchronized behaviour.

A further drawback is that if the thread which owns the mutex fails, the entire application halts. (This type of problem applies to all synchronization entities).

Lockless locking

Lockless locking achieves inter-thread synchronization without the use of operating system provided sychronization entities.

Generally, two techniques are involved.

The first technique is the use of a special set of instructions which are guaranteed atomic by the CPU. This generally centers on an instrument known as Compare-and-swap. This instruction compares two variables and if they are the same, replaces one of the variable's values with a third value.

For example;

compare_and_swap ( destination, exchange, comparand );

Here the destination and comparand are compared. If they are identical, the value in exchange is placed in destination.

This first technique provides the vital inter-thread atomicity of operation. It would otherwise be impossible to perform any lockless locking, since on systems with multiple processors, even operations such as a simple assignment (let a = b) could be half-way through occurring while other operations occur on other processors; the software trying to sychronize across processors could never be sure that any operation had reached a sane state permitting it to be used in some way.

The second technique is to busy-wait or yield when it is clear that the current thread cannot be permitted to continue processing. This provides the vital ability to defer the processing done by a thread when such processing would violate the operations which are being serialised between threads.

External links