Array Based Queuing Locks Explained

Array-Based Queuing Lock (ABQL) is an advanced lock algorithm that ensures that threads spin on unique memory locations thus ensuring fairness of lock acquisition coupled with improved scalability.

Overview

Synchronization is a major issue in the designing and programming of shared memory^[1] multiprocessors. The common problem with lock implementations is the high network contention due to the processors spinning on a shared synchronization flag or memory location. Thus the scalability of the lock is reduced significantly in terms of the number of contending processors.

The Array Based Queuing Lock is an extension to the ticket lock algorithm which ensures that, on a lock release, only one processor attempts to acquire the lock, decreasing the number of cache misses. This effect can be achieved by having all the processors spin on unique memory locations.^[2] One analogy used to explain the lock mechanism is the relay race where the athlete passes on the baton to the next athlete in the queue, which ensures that only one athlete acquires the baton at a time.

ABQL also guarantees fairness in lock acquisition by using a first in, first out (FIFO) queue-based mechanism. Additionally, the amount of invalidation is significantly less than ticket-based lock implementations since only one processor incurs a cache miss on a lock release.

Implementation

The foremost requirement of the implementation of array based queuing lock is to ensure that all the threads spin on unique memory locations. This is achieved with an array of length equal to the number of threads which are in contention for the lock. The elements of the array are all initialized to 0 except the first element which is takes the value 1, thus ensuring successful lock acquisition by the first thread in the queue. On a lock release, the hold is passed to the next thread in queue by setting the next element of the array to 1. The requests are granted to the threads in FIFO ordering.

Pseudo Code example is listed below.ABQL_init(int *next_ticket, int *can_serve)

ABQL_acquire(int *next_ticket, int *can_serve)

ABQL_release (int *can_serve)

To implement ABQL in the pseudo code above, 3 variables are introduced namely can_serve, next_ticket and my_ticket. The roles of each are described below:

can_serve array represents the unique memory locations that the threads waiting in the queue for the lock acquisitions spin on.
next_ticket represents the next available ticket number that is assigned to a new thread.
my_ticket represents the ticket thread of each unique thread in the queue.

In the initialization method (ABQL_init), the variable next_ticket is initialized to 0. All the elements of the can_serve array except the first element are initialized to 0. Initialization of the first element in the array can_serve to 1, ensures successful lock acquisition by the first thread in the queue.

The acquire method uses an atomic operation fetch_and_inc to fetch the next available ticket number (afterwards the ticket number is incremented by 1) that the new thread will use to spin on. The threads in the queue spin on their locations until the value of my_ticket is set to 1 by the previous thread. On acquiring the lock the thread enters the critical section of the code.

On release of a lock by a thread, the control is passed to the next thread by setting the next element in the array can_serve to 1. The next thread which was waiting to acquire the lock can now do so successfully.

The working of ABQL can be depicted in the table below by assuming 4 processors contending to enter the critical section with the assumption that a thread enters the critical section only once.

Execution Steps		can_serve				Comments
initially	0	[1, 0, 0, 0]	0	0	0	initial value of all variables is 0
P1: fetch_and_inc	1	[1, 0, 0, 0]	0	0	0	P1 attempts and successfully acquires the lock
P2: fetch_and_inc	2	[1, 0, 0, 0]	1	0	0	P2 attempts to acquire the lock
P3: fetch_and_inc	3	[1, 0, 0, 0]	1	2	0	P3 attempts to acquire the lock
P4: fetch_and_inc	4	[1, 0, 0, 0]	1	2	3	P4 attempts to acquire the lock
P1: can_serve[1] = 1;can_serve[0] = 0	4	[0, 1, 0, 0]	1	2	3	P1 releases the lock and P2 successfully acquires the lock
P2: can_serve[2] = 1;can_serve[1] = 0	4	[0, 0, 1, 0]	1	2	3	P2 releases the lock and P3 successfully acquires the lock
P3: can_serve[3] = 1;can_serve[2] = 0	4	[0, 0, 0, 1]	1	2	3	P3 releases the lock and P4 successfully acquires the lock
P4: can_serve[3] = 0	4	[0, 0, 0, 0]	1	2	3	P4 releases the lock

Performance metrics

The following performance criteria can be used to analyse the lock implementations:

Uncontended lock-acquisition latency - It is defined as the time taken by a thread to acquire a lock when there is no contention between threads. Due to relatively more number of instructions being executed as opposed to other lock implementations, the uncontented lock acquisition latency for ABQL is high.
Traffic - It is defined as number of bus transactions generated which is dependent on the number of threads in contention for the lock. On a lock release, only 1 cache block is invalidated thus resulting in a single cache miss. This results in much less bus traffic.
Fairness - It ensures that all processors waiting to acquire the lock are able to do so in the order in which their requests are issued. Due to the threads waiting in a queue to acquire a lock with each thread spinning on an individual memory location, fairness is ensured.
Storage - The amount of memory required for the processing of the lock mechanism. The storage requirement scales with the number of threads due to the increase in the size of the array can_serve.

Advantages

ABQL offers improved scalability as each lock release and acquisition triggers only one cache miss resulting in only one cache block suffering from a cache miss to reload the block.
Fairness of lock acquisitions is ensured due to the use of a queue which ensures that the threads acquire the lock in the order in which their requests are issued.

Disadvantages

ABQL should not be used with threads that can be suspended (sleep or context switch) as any thread not immediately ready to acquire the lock will increase the latency of all those behind it waiting for the lock.
Each lock requires an array with a number of entries equal to the number of processors, resulting in linear space complexity. This is generally wasteful as it is rare that all processors would contend for the same lock simultaneously.

References

Web site: Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.
Web site: Anderson . James H. . James H. Anderson (computer scientist) . Kim . Yong-Jik . Herman . Ted . Shared-memory Mutual Exclusion: Major Research Trends Since 1986∗ . January 2003 . First Published in June 2001.