基于自旋的CLH锁
什么是CLH锁
CLH锁满足一下几个特点
- CLH锁是利用链表实现的无界队列，公平的(FIFO队列)，自旋锁。
- 线程在局部变量上自旋，不断轮询前置节点的状态，如果发现前置节点已经释放了锁，则结束自旋获取锁。
- AQS(AbstractQueuedSynchronizer)源码中使用的是CLH锁的一个变种。
CLH算法
CLH算法的数据结构及实现
数据结构
CLHLock内部有两个ThreadLocal变量，一个指向自己的节点(myNode)，另一个指向前一节点(myPred)。(链表)一个原子引用变量(AtomicReference)指向队列的队尾。
CLH锁的基本数据结构如下图所示:
CLH获取和释放锁过程
- 创建一个QNode节点，设置当前节点为true，表示尝试获取锁。
- 将tail指向自己，表示自己为当前队列的末尾(tail是原子性的，可以保证并发安全),获取前置节点locked字段的引用。
- 在前置节点的locked字段上自旋，直到获取锁。
- 当前线程释放锁时，将locked设置为false，将自身节点指向前置节点(相当于出队操作)
1. 初始状态 tail指向一个node(head)节点
+------+
| head | <---- tail
+------+
2. lock-thread加入等待队列: tail指向新的Node，同时Prev指向tail之前指向的节点
+----------+
| Thread-A |
| := Node | <---- tail
| := Prev | -----> +------+
+----------+ | head |
+------+
tail一直指向链表的最后一个Node元素。
+----------+ +----------+
| Thread-B | | Thread-A |
tail ----> | := Node | |---->| := Node | +------+
| := Prev | -----| | := Prev | -----> | head |
+----------+ +----------+ +------+
3. 当前线程在自己的Prev Node(即链表的上一个节点)上自旋。
Java代码实现
CLH Lock是独占式锁的一种，并且是不可重入的锁。下面是CLH Lock的Java实现。
package com.xzy.lock;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
public class CLHLock implements Lock {
private AtomicReference<QNode> tail = new AtomicReference<>(new QNode());
private ThreadLocal<QNode> myPred;
private ThreadLocal<QNode> myNode;
public CLHLock() {
tail = new AtomicReference<>(new QNode());
myNode = ThreadLocal.withInitial(QNode::new);
myPred = ThreadLocal.withInitial(() -> null);
}
@Override
public void lock() {
QNode qNode = myNode.get();
qNode.lock = true;
QNode pred = tail.getAndSet(qNode);
myPred.set(pred);
while (pred.lock) ;
}
@Override
public void lockInterruptibly() throws InterruptedException {
}
@Override
public boolean tryLock() {
return false;
}
@Override
public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
return false;
}
@Override
public void unlock() {
QNode qnode = myNode.get();
qnode.lock = false;
myNode.set(myPred.get());
}
@Override
public Condition newCondition() {
return null;
}
class QNode {
volatile boolean lock;
}
}
测试CLH Lock
package com.xzy.lock;
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.locks.Lock;
public class CLHLockTest {
static int count = 0;
public static void main(String[] args) throws InterruptedException {
final CyclicBarrier cb = new CyclicBarrier(10, new Runnable() {
@Override
public void run() {
System.out.println(count);
}
});
CLHLock clhLock = new CLHLock();
for (int i = 0; i < 10; i++) {
new Thread(new Runnable() {
@Override
public void run() {
testLock(clhLock);
try {
cb.await();
} catch (InterruptedException | BrokenBarrierException e) {
e.printStackTrace();
}
}
}).start();
}
}
public static void testLock(Lock lock) {
System.out.println(Thread.currentThread().getName() + ": ready to lock");
try {
lock.lock();
for (int i = 0; i < 100000; i++) ++count;
} finally {
System.out.println(Thread.currentThread().getName() + ": unlocked");
lock.unlock();
}
}
}
输出结果:
Thread-0: ready to lock
Thread-0: locked
Thread-1: ready to lock
Thread-0: unlocked
Thread-1: locked
Thread-2: ready to lock
Thread-3: ready to lock
Thread-1: unlocked
Thread-2: locked
Thread-4: ready to lock
Thread-2: unlocked
Thread-3: locked
Thread-5: ready to lock
Thread-3: unlocked
Thread-4: locked
Thread-4: unlocked
Thread-5: locked
Thread-6: ready to lock
Thread-5: unlocked
Thread-6: locked
Thread-7: ready to lock
Thread-6: unlocked
Thread-7: locked
Thread-8: ready to lock
Thread-7: unlocked
Thread-8: locked
Thread-8: unlocked
Thread-9: ready to lock
Thread-9: locked
Thread-9: unlocked
1000000
总结
- 关于可重入锁和不可重入锁:
- 可重入锁指可重复可递归调用的锁，并且不发生死锁。典型代表:ReentrantLock、synchronized
- 不可重入锁:与可重入锁相反。自旋锁一般都是不可重入锁。CLH就是不可重入锁。
- 由于锁对象是释放锁以后，没有指针引用，所以当前线程结束后，会被自动gc回收。
- CLH的队列是隐式的，无解的。