Skip to content
/ mcs-lock Public

MCS Queue Lock maintains a linked-list for threads waiting to enter critical section, and is suitable for cache-less NUMA architectures.

License

Notifications You must be signed in to change notification settings

javaf/mcs-lock

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

13 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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.

references

About

MCS Queue Lock maintains a linked-list for threads waiting to enter critical section, and is suitable for cache-less NUMA architectures.

Topics

Resources

License

Stars

Watchers

Forks

Languages