of fairness in lock acquisition in certain circumstances. Not all locks have mechanisms that ensure any level of fairness, leaving the potential for situations similar to that illustrated above. See the Comparison of locks section below for examples of locks that don't implement any fairness guarantees. Implementation of ticket lock 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 my_ticket. Yan Solihin's pseudocode example is listed in the diagram below.ticketLock_init(int *next_ticket, int *now_serving) { *now_serving = *next_ticket = 0; } ticketLock_acquire(int *next_ticket, int *now_serving) { my_ticket = fetch_and_inc(next_ticket); while (*now_serving != my_ticket) {} } ticketLock_release(int *now_serving) { ++*now_serving; } 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. It is important to note that the fetch and increment is done atomically, thereby not allowing any other concurrent attempts at access. Once my_ticket has been received, each thread will spin in the while loop while now_serving isn't equal to its my_ticket. Once now_serving becomes equal to a given thread's my_ticket 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 now_serving. This allows the thread with the next sequential my_ticket to exit from ticketLock_acquire() and enter the critical section. Since the my_ticket 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