自旋锁实现理解
锁类型
可重入锁：基于线程维度，递归锁定、再一层一层释放。
可中断锁：等待锁期间可以被中断。
公平锁：等待时间最长的锁优先被给到。
读写锁：读写分离，一个读锁，一个写锁，提高并发。
自旋锁：自旋是一种"原地忙等"策略，线程未获得锁则原地等待，不去睡眠，直到锁被释放，即不放弃CPU时间片，避免线程进入阻塞状态的开销（线程的阻塞挂起处理器需要切换上下文）。注意：自旋一般会设定一个过期时间，防止长时间自旋导致CPU时间片被长时间占用。自旋是等待他人，不能等待自己，若递归过程中原地打转嵌套等待自己，就会进入死锁。适合：耗时较少的逻辑中，对共享数据的保护，每个线程持有的自旋锁的时间较短。
优点：等待的线程发现自旋锁被其他线程持有的时候，不必挂起自己，而是原地稍微等一会儿，直到锁被释放。所以，避免了线程切换带来的开销。
缺点：等待自旋锁的线程一直占有CPU，如果长时间得不到自旋锁或者释放自旋锁，会导致CPU的浪费。另外，自旋锁可能导致死锁。
互斥锁：线程未获得锁则去睡眠。
一种自旋锁的简单实现
- SpinLock
package lockTest;
import java.util.concurrent.atomic.AtomicReference;
/**
* 它是为实现保护共享资源而提出一种锁机制。其实，自旋锁与互斥锁比较类似，它们都是为了解决对某项资源的互斥使用。无论是互斥锁，还是自旋锁，在任何时刻，最多只能有一个保持者，也就说，在任何时刻最多只能有一个执行单元获得锁。
* 但是两者在调度机制上略有不同。对于互斥锁，如果资源已经被占用，资源申请者只能进入睡眠状态。但是自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元保持，调用者就一直循环在那里看是否该自旋锁的保持者已经释放了锁，"自旋"一词就是因此而得名。
*/
public class SpinLock {
/**
* AtomicReference 原理：
* unsafe获取偏移量 + 基址 定位到真实内存地址，cas操作保证原子性，volatile 修饰 value 保证可见性和有序性。
* 类似版本号概念解 ABA 问题。
* 自旋 失败重试 保障操作执行成功。
*
* holderWithSpinLock 为 持有自旋锁的线程对象。
*
* 无 static 保障每个操作的原子性，最终结果是100。（局部原子，并发）
* 有 static 保障过程的串行化，从1加到100，每次获取锁、解开锁，最终得到100。（整体原子，串行）
*/
private final AtomicReference<Thread> holderWithSpinLock = new AtomicReference<>();
// private static final AtomicReference<Thread> holderWithSpinLock = new AtomicReference<>();
public AtomicReference<Thread> getHolderWithSpinLock() {
return holderWithSpinLock;
}
/**
* 不需要 volatile 修饰，因为不存在并发修改。是描述一个线程的自旋次数。
* 可重入锁，计数重入次数。
**/
private int count = 0;
public void lock(){
// 当前线程
Thread curThread = Thread.currentThread();
System.out.println("curThread: "+ curThread + " start try enter lock with rotate.");
// 如果是当前线程已经持有锁，则自旋次数加一。
if(holderWithSpinLock.get() == curThread){
System.out.println("curThread: "+ curThread + " is self rotate. count is: " + count);
count++;
return;
}
// 自旋 等待锁资源
while(!holderWithSpinLock.compareAndSet(null, curThread)){
System.out.println("curThread: "+ curThread + " is rotate.");
}
System.out.println("curThread: "+ curThread + " get lock success.");
}
public void unlock(){
Thread curThread = Thread.currentThread();
if(holderWithSpinLock.get() == curThread){
if(count > 0){
count--;
System.out.println("curThread: "+ curThread + " is self unlock. count is: " + count);
}else{
holderWithSpinLock.set(null);
}
}
System.out.println("curThread: "+ curThread + " enter unlock.");
// holderWithSpinLock.compareAndSet(curThread, null);
System.out.println("curThread: "+ curThread + " complete unlock.");
}
}
- SpinTask
package lockTest;
public class SpinTask implements Runnable{
public static int count;
private SpinLock spinLock;
public SpinTask(SpinLock spinLock){
this.spinLock = spinLock;
}
@Override
public void run(){
this.spinLock.lock();
count++;
System.out.println("------------currentThread------------ : "+ Thread.currentThread() + " count : "+ count);
this.spinLock.unlock();
}
}
- SpinLockTest
package lockTest;
public class SpinLockTest {
private static final int TASK_NUM = 100;
public static void main(String[] args) throws InterruptedException{
// 应该是一把锁，让所有线程去竞争 共享临界区的资源。
SpinTask spinTask = new SpinTask(new SpinLock());
for(int i = 0; i<TASK_NUM; i++){
Thread thread = new Thread(spinTask);
thread.start();
}
Thread.sleep(5000);
System.out.println(SpinTask.count);
}
}
- 小结：
- CAS操作需要硬件的配合；
- 保证各个CPU的缓存（L1、L2、L3、跨CPU Socket、主存）的数据一致性，通讯开销很大，在多处理器系统上更严重；
- 没法保证公平性，不保证等待进程/线程按照FIFO顺序获得锁。
TicketLock实现
public class TicketLock implements Lock {
// 正在服务号码全局记录（正在游玩体验）
private AtomicInteger serviceNum = new AtomicInteger(0);
// 预售服务号码全局记录（预先排队领号）FIFO，保障公平，公平锁。
private AtomicInteger ticketNum = new AtomicInteger(0);
// 每个线程独有的变量，变量分身思想，互不影响。
private final ThreadLocal<Integer> myNum = new ThreadLocal<>();
@Override
public void lock() {
// 当有新的线程获取锁资源后，相当于模拟其排队的过程，预先排队领号。
myNum.set(ticketNum.getAndIncrement());
// 每个线程都会自旋去校验，当前正在服务号码是不是我的票号，如果排队取号好了，就获得锁资源。
while (serviceNum.get() != myNum.get()) {
}
}
@Override
public void unlock() {
// 释放锁的时候，看当前服务的号码应该顺延。
serviceNum.compareAndSet(myNum.get(), myNum.get() + 1);
// 然后票号码已经使用过，无效了，所以销毁。
myNum.remove();
}
}
小结：serviceNum与ticketNum是全局的服务执行号码与预售排队号码的模拟，每个线程持有的票myNum是利用ThreadLocal进行模拟的（每个线程独有）。（解决了公平问题，FIFO。）
缺点是：在多处理器系统上，每个进程/线程占用的处理器都在读写同一个变量serviceNum ，每次读写操作都必须在多个处理器缓存之间进行缓存同步，这会导致繁重的系统总线和内存的流量，大大降低系统整体的性能。
CLHLock
CLH的发明人是：Craig，Landin and Hagersten。是一种基于链表的
可扩展、高性能、公平的自旋锁，申请线程只在本地变量上自旋，它不断轮询前驱的状态，如果发现前驱释放了锁就结束自旋。CLH队列中的结点QNode中含有一个locked字段，该字段若为true表示该线程需要获取锁，且不释放锁，为false表示线程释放了锁。结点之间是通过隐形的链表相连，之所以叫
隐形的链表是因为这些结点之间没有明显的next指针，而是通过preNode所指向的结点的变化情况来影响myNode的行为。CLHLock上还有一个尾指针，始终指向队列的最后一个结点。（后继监控前驱，尾巴才是起点）CLHLock的类图如下所示：
步骤演示：
- 当一个线程需要获取锁时，会创建一个新的QNode，将其中的locked设置为true表示需要获取锁。（locked标记位表示当前有特别的需求）
- 然后线程对tail域调用getAndSet方法，使自己成为队列的尾部，同时获取一个指向其前趋的引用preNode。（
尾巴才是起点，preNode目的是监控前驱节点的资源。FIFO，后一个等前一个。） - 当一个线程需要释放锁时，将当前结点的locked域设置为false，同时回收前趋结点。（断掉myPred）
public class CLHLock implements Lock {
/**
* 锁等待队列的尾部。
* 每次都是在尾部进行追加，尾巴才是起点。
*/
private AtomicReference<QNode> tail;
/**
* 指向前屈，目的是监控前驱节点的资源。FIFO，后一个等前一个。
*/
private ThreadLocal<QNode> preNode;
/**
* 当前节点。
*/
private ThreadLocal<QNode> myNode;
public CLHLock() {
tail = new AtomicReference<>(null);
myNode = ThreadLocal.withInitial(QNode::new);
preNode = ThreadLocal.withInitial(() -> null);
}
@Override
public void lock() {
QNode qnode = myNode.get();
//设置自己的状态为locked=true表示需要获取锁
qnode.locked = true;
//链表的尾部设置为本线程的qNode，并将之前的尾部设置为当前线程的preNode，尾部追加的方式。
QNode pre = tail.getAndSet(qnode);
preNode.set(pre);
if(pre != null) {
//当前线程在前驱节点的locked字段上旋转，直到前驱节点释放锁资源。监控前驱的锁状态，也就是监控前驱的资源是否被释放。
while (pre.locked) {
}
}
}
@Override
public void unlock() {
QNode qnode = myNode.get();
//释放锁操作时将自己的locked设置为false，可以使得自己的后继节点可以结束自旋。
qnode.locked = false;
//回收自己这个节点，从虚拟队列中删除。
//将当前节点引用置为自己的preNode，那么下一个节点的preNode就变为了当前节点的preNode，这样就将当前节点移出了队列
//也就是通过将当前节点的自我移除的方式，让其后继节点前移。
myNode.set(preNode.get());
}
private class QNode {
/**
* true表示该线程需要获取锁，且不释放锁。
* false表示线程释放了锁，且不需要锁。
*/
private volatile boolean locked = false;
}
}
优缺点：
优点：
优点是空间复杂度低（如果有n个线程，L个锁，每个线程每次只获取一个锁，那么需要的存储空间是O（L+n），n个线程有n个myNode，L个锁有L个tail），CLH的一种变体被应用在了JAVA并发框架中。
缺点：
唯一的缺点是在
NUMA系统结构下性能很差，在这种系统结构下，每个线程有自己的内存，如果前趋结点的内存位置比较远，自旋判断前趋结点的locked域，性能将大打折扣，但是在SMP系统结构下该法还是非常有效的。一种解决NUMA系统结构的思路是MCS队列锁。
备注：将当前节点引用置为自己的preNode，那么下一个节点的preNode就变为了当前节点的preNode，这样就将当前节点移出了队列。（当前节点自释放过程）
MCSLock
MCS 来自于其发明人名字的首字母： John Mellor-Crummey和Michael Scott。是一种基于链表的
可扩展、高性能、公平的自旋锁，申请线程只在本地变量上自旋，直接前驱负责通知其结束自旋，从而极大地减少了不必要的处理器缓存同步的次数，降低了总线和内存的开销。public class MCSLock implements Lock { private AtomicReference<QNode> tail; private ThreadLocal<QNode> myNode; public MCSLock() { tail = new AtomicReference<>(null); myNode = ThreadLocal.withInitial(QNode::new); } @Override public void lock() { QNode qnode = myNode.get(); QNode preNode = tail.getAndSet(qnode); if (preNode != null) { qnode.locked = false; preNode.next = qnode; //wait until predecessor gives up the lock while (!qnode.locked) { } } qnode.locked = true; } @Override public void unlock() { QNode qnode = myNode.get(); if (qnode.next == null) { //后面没有等待线程的情况 if (tail.compareAndSet(qnode, null)) { //真的没有等待线程，则直接返回，不需要通知 return; } // wait until predecessor fills in its next field // 突然有人排在自己后面了，可能还不知道是谁，下面是等待后续者 while (qnode.next == null) { } } //后面有等待线程，则通知后面的线程 qnode.next.locked = true; qnode.next = null; } private class QNode { /** * 是否被qNode所属线程锁定 */ private volatile boolean locked = false; /** * 与CLHLock相比，多了这个真正的next */ private volatile QNode next = null; } }
CLH锁与MCS锁的比较
- CLH锁是轮询前驱节点（主动查看自己需要的资源有没有被当前使用占有者释放），缺点就是可能前驱节点的locked域在内存中距离比较远，轮询查看很费力。CLH中，下一个资源使用者，负责监听资源是否被释放。
- MCS是在本地属性变量上自旋，MCSNode直接持有后继节点，MCS锁释放需要改变后继节点的属性。MCS中，当前资源的使用者负责转交当前的资源给下一个使用者。
Reference
- https://www.cnblogs.com/aspirant/p/6930436.html（JAVA锁机制-可重入锁，可中断锁，公平锁，读写锁，自旋锁）
- https://www.jianshu.com/p/824b2e4f1eed（几种自旋锁的java实现）
- https://www.cnblogs.com/code-duck/p/13588021.html（实现自旋锁）
- https://blog.csdn.net/ustc_dylan/article/details/45667227（NUMA体系结构详解）
- https://blog.csdn.net/weixin_33772645/article/details/92430207（什么是SMP系统）
版权声明：本文为GZHarryAnonymous原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。