CLH Queue Lock maintains a linked-list for threads waiting to enter critical section (CS).
Each thread that wants to enter CS raises its hand, joins at the end of the queue, and waits for the thread infront of it to lower its hand (indicating that he has finishes his CS). Then it enters its CS.
Once the thread is done with CS, it lowers its hand and moves to take the place of the thread standing infront of it. To ensure that there is always a thread infront of another, the queue is initialized with a dummy node. Atomic instructions are used when updating the shared queue.
As each thread waits (spins) on its predecessor's hand status "locked" field only, cache invalidate only occurs due to the predecessor. Also, this does not require the knowledge of number of threads before hand. This also provides first- come-first-served fairness. The CLHLock is due to Travis Craig, Erik Hagersten, and Anders Landin.
Course: Concurrent Data Structures, Monsoon 2020
Taught by: Prof. Govindarajulu Regeti
lock():
1. When thread wants to access critical
section, it raises its hand "locked" and
stands at the end of the queue (FIFO).
2. If thread standing infront has his hand
raised "locked", it waits for him to be
done with CS.unlock():
1. When a thread is done with its critical
section, it drops down its hand "locked".
2. It then takes the place of the thread
standing infront of it.(To ensure that there is always a thread
infront of another, the queue is
initialized with a dummy node.)See CLHLock.java for code, Main.java for test, and repl.it for output.