自学内容网 自学内容网
自学内容网 > 正文

CLH介绍

🕗 发布于 2024-10-19 16:29 java  开发语言  

在并发编程中，锁是一种常用的保证线程安全的方法。Java 中常用的锁主要有两类，一种是 Synchronized 修饰的锁，被称为 Java 内置锁或监视器锁。另一种就是在 J2SE 1.5版本之后的 java.util.concurrent包（下称JUC包）中的各类同步器，包括 ReentrantLock（可重入锁），ReentrantReadWriteLock（可重入读写锁），Semaphore（信号量），CountDownLatch 等。这些同步器都是基于 AbstractQueuedSynchronizer（下称 AQS）这个简单的框架来构建的，而 AQS 类的核心数据结构是一种名为 Craig, Landin, and Hagersten locks（下称 CLH 锁）的变体。

CLH 锁是对自旋锁的一种改良

自旋锁

自旋锁是互斥锁的一种实现，Java 实现如下方所示

public class SpinLock {

    private AtomicReference<Thread> owner = new AtomicReference<Thread>();

    public void lock() {
        Thread currentThread = Thread.currentThread();
        // 如果锁未被占用，则设置当前线程为锁的拥有者
        while (!owner.compareAndSet(null, currentThread)) {
        }
    }

    public void unlock() {
        Thread currentThread = Thread.currentThread();
        // 只有锁的拥有者才能释放锁
        owner.compareAndSet(currentThread, null);
    }
}

获取锁时，线程会对一个原子变量循环执行 compareAndSet 方法，直到该方法返回成功时即为成功获取锁。compareAndSet 方法底层是通用 compare-and-swap （下称 CAS）实现的。该操作是原子操作。原子性保证了根据最新信息计算出新值，如果与此同时值已由另一个线程更新，则写入将失败。因此，这段代码可以实现互斥锁的功能

自旋锁实现简单，同时避免了操作系统进程调度和线程上下文切换的开销，但他有两个缺点：

  • 第一个是锁饥饿问题。在锁竞争激烈的情况下，可能存在一个线程一直被其他线程”插队“而一直获取不到锁的情况。

  • 第二是性能问题。在实际的多处理上运行的自旋锁在锁竞争激烈时性能较差。

自旋锁的性能和理想情况相距甚远。这是因为自旋锁锁状态中心化，在竞争激烈的情况下，锁状态变更会导致多个 CPU 的高速缓存的频繁同步，从而拖慢 CPU 效率

因此自旋锁适用于锁竞争不激烈、锁持有时间短的场景

CLH原理

CLH 锁是对自旋锁的一种改进，有效的解决了以上的两个缺点。首先它将线程组织成一个队列，保证先请求的线程先获得锁，避免了饥饿问题。其次锁状态去中心化，让每个线程在不同的状态变量中自旋，这样当一个线程释放它的锁时，只能使其后续线程的高速缓存失效，缩小了影响范围，从而减少了 CPU 的开销。

CLH 锁数据结构很简单，类似一个链表队列，所有请求获取锁的线程会排列在链表队列中，自旋访问队列中前一个节点的状态。当一个节点释放锁时，只有它的后一个节点才可以得到锁。CLH 锁本身有一个队尾指针 Tail，它是一个原子变量，指向队列最末端的 CLH 节点。

每一个 CLH 节点有两个属性：所代表的线程和标识是否持有锁的状态变量。当一个线程要获取锁时，它会对 Tail 进行一个 getAndSet 的原子操作。该操作会返回 Tail 当前指向的节点，也就是当前队尾节点，然后使 Tail 指向这个线程对应的 CLH 节点，成为新的队尾节点。入队成功后，该线程会轮询上一个队尾节点的状态变量，当上一个节点释放锁后，它将得到这个锁。

CLH 锁 Java 实现

public class CLHLock {


    private static class CLHNode {
        // 锁状态：默认为false，表示线程没有获取到锁；true表示线程获取到锁
        volatile boolean locked = false;
    }

    private final AtomicReference<CLHNode> tailNode;

    private final ThreadLocal<CLHNode> preNode;

    private final ThreadLocal<CLHNode> curNode;


    public CLHLock() {
        // 初始化前继节点，注意此时前继节点没有存储CLHNode对象，存储的是null
        // 在加锁时，会将 tailNode 赋值给 preNode
        this.preNode = new ThreadLocal<>();
        this.curNode = ThreadLocal.withInitial(CLHNode::new);
        this.tailNode = new AtomicReference<>(new CLHNode());
    }

    public void lock() {
        CLHNode currNode = curNode.get();
        currNode.locked = true;

        // 当前节点赋值给尾节点, 就尾节点变为当前节点的前节点
        CLHNode oldTail = tailNode.getAndSet(currNode);
        preNode.set(oldTail);

        // 循环监控前节点
        while (oldTail.locked) {
            try {
                TimeUnit.MILLISECONDS.sleep(10);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            System.out.println(Thread.currentThread().getName() + "未获取到锁");
        }
        System.out.println(Thread.currentThread().getName() + "获取到锁了");
    }

    public void unlock() {
        CLHNode currNode = curNode.get();
        currNode.locked = false;
        System.out.println(Thread.currentThread().getName() + "释放锁了");

        // 防止当前节点重新执行lock()导致死锁
        curNode.set(new CLHNode());

//        curNode.set(preNode.get());
    }
}

    private static int count = 0;

    public static void main(String[] args) throws InterruptedException {

        CLHLock lock = new CLHLock();

        for (int i = 0; i < 100; i++) {
            new Thread(() -> {
                lock.lock();
                count++;
                lock.unlock();
            }).start();
        }

        TimeUnit.SECONDS.sleep(2);
        System.out.println("count: " + count);
    }

加锁流程分析

假如有这么一个场景：有四个并发线程同时启动执行lock操作，假如四个线程的实际执行顺序为：threadA<--threadB<--threadC<--threadD

第一步，线程A过来，执行了lock操作，获得了锁，此时locked状态为true

第二步，线程B过来，执行了lock操作，由于线程A还未释放锁，此时自旋等待，locked状态也为true

第三步，线程C过来，执行了lock操作，由于线程B处于自旋等待，此时线程C也自旋等待（因此CLH锁是公平锁），locked状态也为true

第四步，线程D过来，执行了lock操作，由于线程C处于自旋等待，此时线程D也自旋等待，locked状态也为true

这就是多个线程并发加锁的一个过程图解，当前线程只要判断前一线程的locked状态如果是true，那么则说明前一线程要么拿到了锁，要么也处于自旋等待状态，所以自己也要自旋等待。而尾指针tailNode总是指向最后一个线程的CLHNode节点

释放锁流程

假如这四个线程加锁后，线程A开始释放锁，此时线程B获取到锁，结束自旋等待，然后线程C和线程D仍然自旋等待

以此类推，线程B释放锁的过程也跟上图类似，这里不再赘述。

CLH 优缺点分析

CLH 锁作为自旋锁的改进，有以下几个优点：

  1. 性能优异，获取和释放锁开销小。CLH 的锁状态不再是单一的原子变量，而是分散在每个节点的状态中，降低了自旋锁在竞争激烈时频繁同步的开销。在释放锁的开销也因为不需要使用 CAS 指令而降低了。

  2. 公平锁。先入队的线程会先得到锁。

  3. 实现简单，易于理解。

  4. 扩展性强。下面会提到 AQS 如何扩展 CLH 锁实现了 j.u.c 包下各类丰富的同步器。

当然，它也有两个缺点：第一是因为有自旋操作，当锁持有时间长时会带来较大的 CPU 开销。第二是基本的 CLH 锁功能单一，不改造不能支持复杂的功能。

死锁

在 unlock() 中有如下代码

curNode.set(new CLHNode());

若没有这两句代码，若同个线程加锁释放锁后，然后再次执行加锁操作，可能会发生死锁

出现的根本原因应该是tailNode和curNode的引用一致，当修改tailNode的值为true时，curNode也会被改为true

第一种情况：

A线程拿到锁，B线程正在等待。A线程执行完unlock()后（locked = false），（在B线程 while循环中发现A线程释放锁之前）此时A线程再次加锁，会把 locked 改为 true，此时B线程在循环中看到A线程还是没有释放锁

第二种情况：

有且只有A线程。A线程执行完unlock()后（locked = false），A线程再次加锁，这样 tail 和 cur 都是同一个引用，且tail 在加锁是把 locked 改为 true

https://zhuanlan.zhihu.com/p/197840259

Java AQS 核心数据结构-CLH 锁


原文地址：https://blog.csdn.net/weixin_46058921/article/details/142988009

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024