In a
Non-Uniform Memory Architecture (NUMA) system it is important to have a lock implementation that guarantees some level of
fairness of lock acquisition. The ticket lock is an implementation of
spinlock that adds this desired attribute. The following pseudocode shows the operations for initializing the lock, acquiring the lock, and releasing the lock. A call to TicketLock::acquire() would precede the critical section of the code and ticketLock_release would follow it. Each processor will keep track of its turn via the value of each processor's myTicket. Yan Solihin's pseudocode can be represented as in the following: import java.util.concurrent.atomic.AtomicInteger; class TicketLock { private AtomicInteger nowServing = 0; private AtomicInteger nextTicket = 0; public TicketLock() { this.nowServing = 0; this.nextTicket = 0; } public void acquire() { int myTicket = nextTicket.getAndIncrement(1); while (*nowServing != myTicket) { // Do nothing... } } public void release() { nowServing.incrementAndGet(); } } Following along with the pseudocode above we can see that each time a processor tries to acquire a lock with TicketLock::acquire(), the
fetch-and-add algorithm is called, returning the current value of nextTicket into the thread-private myTicket and incrementing the shared nextTicket. It is important to note that the fetch and increment is done atomically, thereby not allowing any other concurrent attempts at access. Once myTicket has been received, each thread will spin in the
while loop while nowServing isn't equal to its myTicket. Once nowServing becomes equal to a given thread's myTicket they are allowed to return from TicketLock::acquire() and enter the critical section of code. After the critical section of the code, the thread performs TicketLock::release() which increments nowServing. This allows the thread with the next sequential myTicket to exit from TicketLock::acquire() and enter the critical section. Since the myTicket values are acquired in the order of thread arrival at the lock, subsequent acquisition of the lock is guaranteed to also be in this same order. Thus, fairness of lock acquisition is ensured, enforcing a FIFO ordering. 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. Following along with the "Action" column, the outcome based on the above pseudocode can be observed. For each row, the variable values shown are those
after the indicated action(s) have completed. The key point to note from the example is that the initial attempts by all four processors to acquire the lock results in only the first to arrive actually getting the lock. All subsequent attempts, while the first still holds the lock, serves to form the queue of processors waiting their turn in the critical section. This is followed by each getting the lock in turn, allowing the next in line to acquire it as the previous holder leaves. Also note that another processor can arrive at any time during the sequence of lock acquire/releases by other processors, and simply waits its turn. The first step, prior to use of the lock, is initialization of all lock variables (Row 1). Having nextTicket and nowServing initialized to 0 ensures that the first thread that attempts to get the lock will get ticket 0, thus acquiring the lock due to its ticket matching nowServing. So when P1 tries to acquire the lock it immediately succeeds and nextTicket is incremented to 1 (Row 2). When P3 tries to acquire the lock it gets 1 for its myTicket, next ticket is incremented to 2, and it must wait since nowServing is still 0 (Row 3). Next, when P2 attempts to acquire the lock it gets 2 for its myTicket, nextTicket is incremented to 3, and it must also wait due to nowServing still being 0 (Row 4). P1 now releases the lock by incrementing nowServing to 1, thus allowing P3 to acquire it due its myTicket value of 1 (Row 5). Now P3 releases the lock, incrementing nowServing to 2, allowing P2 to acquire it (Row 6). While P2 has the lock, P4 attempts to acquire it, gets a myTicket value of 3, increments nextTicket to 4, and must wait since nowServing is still 2 (Row 7). When P2 releases the lock, it increments nowServing to 3, allowing P4 to get it (Row 8). Finally, P4 releases the lock, incrementing nowServing to 4 (Row 9). No currently waiting threads have this ticket number, so the next thread to arrive will get 4 for its ticket and immediately acquire the lock. ==Comparison of locks==