资讯专栏INFORMATION COLUMN

克雷格.兰丁&hagersten (CLH Lock)

roundstones / 3278人阅读

摘要:是独占式锁的一种,并且是不可重入的锁,这篇文章是对锁源代码分析的预热篇

CLH Lock摘要

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.

CLH锁是自旋锁的一种,对它的研究是因为AQS源代码中使用了CLH锁的一个变种,为了更好的理解AQS中使用锁的思想,所以决定先好好理解CLH锁

Java代码实现
public class ClhSpinLock implements Lock{
    private final ThreadLocal prev;
    private final ThreadLocal node;
    private final AtomicReference tail = new AtomicReference(new Node());

    public ClhSpinLock() {
        this.node = new ThreadLocal() {
            protected Node initialValue() {
                return new Node();
            }
        };

        this.prev = new ThreadLocal() {
            protected Node initialValue() {
                return null;
            }
        };
    }

    /**
     * 1.初始状态 tail指向一个node(head)节点 
     * +------+ 
     * | head | <---- tail 
     * +------+
     * 
     * 2.lock-thread加入等待队列: tail指向新的Node,同时Prev指向tail之前指向的节点
     * +----------+
     * | Thread-A |
     * | := Node  | <---- tail
     * | := Prev  | -----> +------+
     * +----------+        | head |
     *                     +------+ 
     * 
     *             +----------+            +----------+
     *             | Thread-B |            | Thread-A |
     * tail ---->  | := Node  |     -->    | := Node  | 
     *             | := Prev  | ----|      | := Prev  | ----->  +------+
     *             +----------+            +----------+         | head |
     *                                                          +------+ 
     * 3.寻找当前node的prev-node然后开始自旋
     * 
     */
    public void lock() {
        final Node node = this.node.get();
        node.locked = true;
        Node pred = this.tail.getAndSet(node);
        this.prev.set(pred);
        // 自旋
        while (pred.locked);
    }

    public void unlock() {
        final Node node = this.node.get();
        node.locked = false;
        this.node.set(this.prev.get());
    }

    @Override
    public void lockInterruptibly() throws InterruptedException {
        // TODO Auto-generated method stub
        
    }

    @Override
    public boolean tryLock() {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public Condition newCondition() {
        // TODO Auto-generated method stub
        return null;
    }
    
    private static class Node {
        private volatile boolean locked;
    }
}

简单的看一下CLH的算法定义

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.

基于list,线程仅在一个局部变量上自旋,它不断轮询前一个节点状态,如果发现前一个节点释放锁结束.

所以在java中使用了ThreadLocal作为具体实现,AtomicReference为了消除多个线程并发对tail引用Node的影响,核心方法lock()中分为3个步骤去实现

初始状态 tail指向一个node(head)节点

private final AtomicReference tail = new AtomicReference(new Node());

thread加入等待队列: tail指向新的Node,同时Prev指向tail之前指向的节点,在java代码中使用了getAndSet即CAS操作使用

Node pred = this.tail.getAndSet(node);
this.prev.set(pred);

寻找当前线程对应的node的前驱node然后开始自旋前驱node的status判断是否可以获取lock

while (pred.locked);

同理unlock()方法,获取当前线程的node,设置lock status,将当前node指向前驱node(这样操作tail指向的就是前驱node等同于出队操作).至此CLH Lock的过程就结束了

测试ClhSpinLock
public class LockTest {
    static int count = 0;
    
    public static void testLock(Lock lock) {
        try {
            lock.lock();
            for (int i = 0; i < 10000000; i++) ++count;
        } finally {
            lock.unlock();
        }
    }
    
    public static void main(String[] args) throws InterruptedException, BrokenBarrierException {
        final ClhSpinLock clh = new ClhSpinLock();
        final CyclicBarrier cb = new CyclicBarrier(10, new Runnable() {
            @Override
            public void run() {
                System.out.println(count);
            }
        });
        
        for (int i = 0; i < 10; i++) {
            new Thread(new Runnable() {
                @Override
                public void run() {
                    testLock(clh);
                    // 这段代码是非lock比较使用
//                    for (int i = 0; i < 10000000; i++)
//                        count++;
                    try {
                        cb.await();
                    } catch (InterruptedException | BrokenBarrierException e) {
                        e.printStackTrace();
                    }
                }
            }).start();
        }
    }
}

测试代码使用了CyclicBarrier辅助当所有子线程完成后输出static变量count的值
结果发现输出的值和预期一样,CLH Lock完成了独占式锁的功能

小结

CLH Lock是一种比较简单的自旋锁算法之一,因为锁的CAS操作涉及到了硬件的锁定(锁总线或者是锁内存)所以性能和CPU架构也密不可分,该兴趣的同学可以继续深入研究包括MCS锁等。CLH Lock是独占式锁的一种,并且是不可重入的锁,这篇文章是对AQS锁源代码分析的预热篇

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/66114.html

相关文章

  • Java多线程进阶(六)—— J.U.C之locks框架:AQS综述(1)

    摘要:在时,引入了包,该包中的大多数同步器都是基于来构建的。框架提供了一套通用的机制来管理同步状态阻塞唤醒线程管理等待队列。指针用于在结点线程被取消时,让当前结点的前驱直接指向当前结点的后驱完成出队动作。 showImg(https://segmentfault.com/img/remote/1460000016012438); 本文首发于一世流云的专栏:https://segmentfau...

    cocopeak 评论0 收藏0
  • J.U.C|condition分析

    摘要:造成当前线程在接到信号被中断或到达指定最后期限之前一直处于等待状态。该线程从等待方法返回前必须获得与相关的锁。如果线程已经获取了锁,则将唤醒条件队列的首节点。 一、写在前面 在前几篇我们聊了 AQS、CLH、ReentrantLock、ReentrantReadWriteLock等的原理以及其源码解读,具体参见专栏 《非学无以广才》 这章我们一起聊聊显示的Condition 对象。 ...

    Sourcelink 评论0 收藏0
  • J.U.C|一文搞懂AQS

    摘要:接着线程过来通过方式获取锁,获取锁的过程就是通过操作变量将其值从变为。线程加锁成功后还有一步重要的操作,就是将设置成为自己。线程屁颠屁颠的就去等待区小憩一会去了。 一、写在前面 这篇文章,我们聊一聊Java并发中的核武器, AQS底层实现。 不管是工作三四年、还是五六年的在工作或者面试中涉及到并发的是时候总是绕不过AQS这个词。 首先,确实还有很多人连AQS是什么都不知道,甚至有的竟...

    tommego 评论0 收藏0
  • 源码分析JDK8之AbstractQueuedSynchronizer

    摘要:与之相关的方法有三个原子性地修改都是类型,可见我们可以进行,来定义的获取与释放从而实现我们自定义的同步器。 前言 源码分析我认为主要有两个作用:满足好奇心,我想每一个有追求的人都不会满足于仅仅做一个API Caller实现功能就好,我们也想知道它到底是怎么实现的;借鉴与升华,当我们明白了一个类的设计原理,在一定的情境下我们可以借鉴其设计哲学,甚至针对我们自己特殊的业务场景对其进行改良与...

    魏宪会 评论0 收藏0
  • 源码分析JDK8之AbstractQueuedSynchronizer

    摘要:与之相关的方法有三个原子性地修改都是类型,可见我们可以进行,来定义的获取与释放从而实现我们自定义的同步器。 前言 源码分析我认为主要有两个作用:满足好奇心,我想每一个有追求的人都不会满足于仅仅做一个API Caller实现功能就好,我们也想知道它到底是怎么实现的;借鉴与升华,当我们明白了一个类的设计原理,在一定的情境下我们可以借鉴其设计哲学,甚至针对我们自己特殊的业务场景对其进行改良与...

    sunny5541 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<