Skip to content
/ clh-lock Public

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

License

Notifications You must be signed in to change notification settings

javaf/clh-lock

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

10 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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.

references

About

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

Topics

Resources

License

Stars

Watchers

Forks

Languages