(turn) CLH queue lock

The original:


CLH lock is Craig, Landin, and Hagersten (CLH) locks, CLH lock is a spin lock, can ensure no hunger, provide fairness first come first service.

The CLH lock is a scalable, high performance, fairness and spin lock based on the list, the application thread spin only on a local variable, it constantly polling the precursor state, if it is found that the pre release lock end spin.


SMP(Symmetric Multi-Processor), Symmetric multi processor architecture, referring to multiple CPU symmetry in the server, the time required for each CPU to access the same memory address. Its main characteristic is shared, include CPU, memory, I/O share. The advantage of the SMP is to ensure memory consistency, the disadvantage is that these shared resources may become a performance bottleneck, with the increase in the number of CPU, each CPU must have access to the same memory resources, likely to cause memory access conflict, may cause the CPU waste of resources. PC machine used to belong to this.
NUMA(Non-Uniform Memory Access)Non uniform memory access, CPU is divided into CPU blocks, each CPU module is composed of a plurality of CPU, and have independent local memory, I/O slot, the modules are mutually accessible through Internet access local memory module, the speed will be much higher than the access remote memory (the other nodes in the system speed, memory) this is consistent with non origin memory access NUMA. NUMA advantage is that it can effectively solve the problem extends the original SMP system, due to the shortcomings of remote memory access latency than local memory, so when CPU increases, the system performance can not increase linearly.

CLH algorithm

CLH queue of nodes in QNode contains a locked field, the field if the true indicates that the thread needs to acquire the lock, and does not release the lock, false represents a thread releases the lock. Nodes are connected through contact list, is called a contact list because there is no obvious next pointer changes between these nodes, but through myPred by pointing to the node to influence the behavior of the myNode. CLHLock also has a tail pointer, the last node always point to the queue. The CLHLock class diagram as follows:

When a thread needs to acquire the lock time, Will create a new QNode, The locked is set to true expressed the need to acquire the lock, Then call the getAndSet method on the tail thread, Make oneself become the queue tail, At the same time to obtain a pointer to its predecessor cited myPred, then the thread in the locked field precursor node rotation, Release the lock until the predecessor node. When a thread needs to release the lock, the locked domain for the current node is set to false, at the same time, recovery of precursor node. As shown below, the thread A need to acquire the lock, the myNode domain of true, some tail pointing to the thread of A nodes, then the thread B is added to the thread behind A, tail refers to the B thread node. Then the thread A and B in the myPred domain of its rotation, locked field of a myPred node it into the false, it can acquire the lock sweep line. Obvious thread A locked domain for false myPred, the thread A access to the lock.

The CLH code is as follows, which uses the ThreadLocal class, binding QNode to each thread, also used the AtomicReference, the tail pointer modification is called getAndSet (it) operation, it can guarantee the atomically update object reference.
[java] view plaincopy  

  1. public class CLHLock implements Lock {  
  2.     AtomicReference<QNode> tail = new AtomicReference<QNode>(new QNode());  
  3.     ThreadLocal<QNode> myPred;  
  4.     ThreadLocal<QNode> myNode;  
  6.     public CLHLock() {  
  7.         tail = new AtomicReference<QNode>(new QNode());  
  8.         myNode = new ThreadLocal<QNode>() {  
  9.             protected QNode initialValue() {  
  10.                 return new QNode();  
  11.             }  
  12.         };  
  13.         myPred = new ThreadLocal<QNode>() {  
  14.             protected QNode initialValue() {  
  15.                 return null;  
  16.             }  
  17.         };  
  18.     }  
  20.     @Override  
  21.     public void lock() {  
  22.         QNode qnode = myNode.get();  
  23.         qnode.locked = true;  
  24.         QNode pred = tail.getAndSet(qnode);  
  25.         myPred.set(pred);  
  26.         while (pred.locked) {  
  27.         }  
  28.     }  
  30.     @Override  
  31.     public void unlock() {  
  32.         QNode qnode = myNode.get();  
  33.         qnode.locked = false;  
  34.         myNode.set(myPred.get());  
  35.     }  
  36. }     

As you can see from the code of lock method in a while loop, which is a locked domain in waiting for the predecessor node to the false, this is a process of spin waiting. The unlock method is very simple, only needs to be your locked domain can be set to false.

The advantages and disadvantages of CLH

Advantages of CLH queue lock is low space complexity (if n threads, L locks, each thread only gets a lock, the storage space required is O (L+n), n thread with n myNode, L locks L tail), a variant of CLH is application of JAVA in the patients with frame. The only drawback is the poor performance of the NUMA system, in this system, each thread has its own memory, if the predecessor node memory location is far away, the locked domain spin judgment predecessor node, the performance will be greatly reduced, but the method in SMP system is very effective. A solution of NUMA system structure is the idea of the MCS queue lock.

Reference material:

A Hierarchical CLH Queue Lock

Thread lock series(1): CLH Lock

The Art of Multiprocessor Programming

Posted by Heidi at August 21, 2014 - 7:59 PM