自旋锁 CLH和CMS

浅浅的花香味﹌ 2022-11-30 04:23 174阅读 0赞

### 文章目录 ###

*  前言
 *  什么是自旋锁？
 *  自旋锁种类

# 前言 #

在`JAVA` 中`concurrent`包中大多数`API`借助`AQS`完成，而`AQS`核心又在于`CLH`自旋锁上。

# 什么是自旋锁？ #

线程无法获取锁时会进行阻塞休眠，但很多时候我们只需要稍微等一会即可得到锁资源，在这种情况我们会让程序做无意义的循环。  
如下代码：

public class Main {
        
        static AtomicBoolean isLock = new AtomicBoolean();
        public static void main(String[] args) {
        
            //主线程得到锁
            isLock.compareAndSet(false, true);
            
            new Thread(new Runnable() {
        
                @Override
                public void run() {
        
                    //自旋得到锁位置
                    while (!isLock.compareAndSet(false, true)) {
        
                        //没有得到锁继续尝试
                        continue;
                    }
                }
            }).start()；
            //主线程释放锁
            isLock.compareAndSet(true, false);
        }
    }

上述代码主线程得到锁之后会立马释放，而如果子线程采用得不到就休眠等候唤醒，相对于自旋来说上下文切换成本更大。

# 自旋锁种类 #

**(1)单一共享变量类型：**

上一节自旋锁是最常见的形式，但是效率也是最差的。因为在线程数众多的情况下对共享变量读写可见性需要付出额外的代价。

public class Main {
        
        static AtomicBoolean isLock = new AtomicBoolean();
        public static void main(String[] args) {
        
            //主线程得到锁
            isLock.compareAndSet(false, true);
            Runnable runnable = new Runnable() {
        
                @Override
                public void run() {
        
                    //自旋得到锁位置
                    while (!isLock.compareAndSet(false, true)) {
        
                        //没有得到锁继续尝试
                        continue;
                    }
                }
            };
            for (int i = 0; i < 20; i++) {
        
                //多个线程对同一变量自旋
                new Thread(runnable).start();
            }
           
            //主线程释放锁
            isLock.compareAndSet(true, false);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmYW5taW5neWlx_size_16_color_FFFFFF_t_70_pic_center]  
随着线程数量的增加自旋锁的代价会逐步上升。

**(2)CLH类型自旋锁**

为了弥补单一共享变量问题，`Craig，Landin and Hagersten`这几位大佬提出新的新解决方案。  
每个线程视为一个`Node`,然后全部将其链接成一个链表，每个`Node`自旋前驱节点是否释放了锁，从而避免了多线程全部自旋同一变量的问题。

代码摘抄之[CLH lock 原理及JAVA实现][CLH lock _JAVA]

public interface Lock {
        
        void lock();
     
        void unlock();
    }
     
    public class QNode {
        
        volatile boolean locked;
    }
     
     
    import java.util.concurrent.atomic.AtomicReference;
     
    public class CLHLock implements Lock {
        
        // 尾巴，是所有线程共有的一个。所有线程进来后，把自己设置为tail
        private final AtomicReference<QNode> tail;
        // 前驱节点，每个线程独有一个。
        private final ThreadLocal<QNode> myPred;
        // 当前节点，表示自己，每个线程独有一个。
        private final ThreadLocal<QNode> myNode;
     
        public CLHLock() {
        
            this.tail = new AtomicReference<QNode>(new QNode());
            this.myNode = new ThreadLocal<QNode>() {
        
                protected QNode initialValue() {
        
                    return new QNode();
                }
            };
            this.myPred = new ThreadLocal<QNode>();
        }
     
        @Override
        public void lock() {
        
            // 获取当前线程的代表节点
            QNode node = myNode.get();
            // 将自己的状态设置为true表示获取锁。
            node.locked = true;
            // 将自己放在队列的尾巴，并且返回以前的值。第一次进将获取构造函数中的那个new QNode
            QNode pred = tail.getAndSet(node);
            // 把旧的节点放入前驱节点。
            myPred.set(pred);
            // 判断前驱节点的状态，然后走掉。
            while (pred.locked) {
        
            }
        }
     
        @Override
        public void unlock() {
        
            // unlock. 获取自己的node。把自己的locked设置为false。
            QNode node = myNode.get();
            node.locked = false;
            myNode.set(myPred.get());
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmYW5taW5neWlx_size_16_color_FFFFFF_t_70_pic_center 1]  
上述代码相对 **(1)单一共享变量类型** 来说减轻了大量的变量同步操作，但是需要额外的内存空间。  
但是他也并非完美无缺的，`NUMA`架构下每个`CPU`都有一块自己内存掌控区，也就是每个线程拥有自身内存区域，如果其他线程访问另一线程也需要付出额外的代价。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmYW5taW5neWlx_size_16_color_FFFFFF_t_70_pic_center 2]  
上图转自[Loks][]

**(2)CMS类型自旋锁**  
每个线程构建成一个链表，`CMS`自旋锁中每个线程子自旋本地线程变量，当持有线程锁线程释放时，修改后任线程变量标识。

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
    public class MCSLock {
        
        public static class MCSNode {
        
            volatile MCSNode next;
            volatile boolean isWaiting = true; // 默认是在等待锁
        }
        volatile MCSNode queue;// 指向最后一个申请锁的MCSNode
        private static final AtomicReferenceFieldUpdater<MCSLock, MCSNode> UPDATER = AtomicReferenceFieldUpdater
                .newUpdater(MCSLock.class, MCSNode.class, "queue");
    
        public void lock(MCSNode currentThread) {
        
            MCSNode predecessor = UPDATER.getAndSet(this, currentThread);// step 1
            if (predecessor != null) {
        
                predecessor.next = currentThread;// step 2
                while (currentThread.isWaiting) {
        // step 3
                }
            } else {
         // 只有一个线程在使用锁，没有前驱来通知它，所以得自己标记自己已获得锁
                currentThread.isWaiting = false;
            }
        }
    
        public void unlock(MCSNode currentThread) {
        
            if (currentThread.isWaiting) {
        // 锁拥有者进行释放锁才有意义
                return;
            }
    
            if (currentThread.next == null) {
        // 检查是否有人排在自己后面
                if (UPDATER.compareAndSet(this, currentThread, null)) {
        // step 4
                    // compareAndSet返回true表示确实没有人排在自己后面
                    return;
                } else {
        
                    // 突然有人排在自己后面了，可能还不知道是谁，下面是等待后续者
                    // 这里之所以要忙等是因为：step 1执行完后，step 2可能还没执行完
                    while (currentThread.next == null) {
         // step 5
                    }
                }
            }
            currentThread.next.isWaiting = false;
            currentThread.next = null;// for GC
        }
    }

`CMS`比`CLH`更优秀为何`AQS`选择了`CLH`,在Doug Lea在其论文中做了描绘  
`因为CLH锁可以更容易地去实现“取消（cancellation）”和“超时”功能`。  
另外笔者认为`AQS`在尝试得不到锁后进行阻塞等候唤醒，而不是不断的尝试。

[CLH lock 原理及JAVA实现][CLH lock _JAVA]  
[The java.util.concurrent Synchronizer Framework ][The java.util.concurrent Synchronizer Framework]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmYW5taW5neWlx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/f611b59723ec4b7aac5c1bf40b8eba40.png
[CLH lock _JAVA]: https://www.cnblogs.com/shoshana-kong/p/10831502.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmYW5taW5neWlx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/f15961839cf2498f9ec02cbef8243866.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmYW5taW5neWlx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/bcf9662650c140148515f64a40f47353.png
[Loks]: https://classes.engineering.wustl.edu/cse539/web/lectures/locks.pdf
[The java.util.concurrent Synchronizer Framework]: http://ifeve.com/aqs/