MCS Queue Lock maintains a linked-list for threads waiting to enter critical section (CS).
Each thread that wants to enter CS joins at the end of the queue, and waits for the thread infront of it to finish its CS. So, it locks itself and asks the thread infront of it, to unlock it when he's done. Atomics instructions are used when updating the shared queue. Corner cases are also takes care of.
As each thread waits (spins) on its own "locked" field, this type of lock is suitable for cache-less NUMA architectures. The MCSLock is due to John Mellor-Crummey and Michael Scott.
Course: Concurrent Data Structures, Monsoon 2020
Taught by: Prof. Govindarajulu Regeti
lock():
1. When thread wants to access critical
section, it stands at the end of the
queue (FIFO).
2a. If there is no one in queue, it goes head
with its critical section.
2b. Otherwise, it locks itself and asks the
thread infront of it to unlock it when its
done with CS.unlock():
1. When a thread is done with its critical
section, it needs to unlock any thread
standing behind it.
2a. If there is a thread standing behind,
then it unlocks him.
2b. Otherwise it tries to mark queue as empty.
If no one is joining, it leaves.
2c. If there is a thread trying to join the
queue, it waits until he is done, and then
unlocks him, and leaves.See MCSLock.java for code, Main.java for test, and repl.it for output.