发布于 由admin

Java的CLH Lock：基于队列实现公平锁的链表节点结构与操作

Java CLH Lock：基于队列实现公平锁的链表节点结构与操作

大家好，今天我们来深入探讨一种经典的自旋锁——CLH Lock。它以其基于队列实现的公平性著称，在并发编程领域有着重要的地位。我们将从CLH Lock的基本原理入手，逐步分析其链表节点结构，以及相关的操作实现，并通过代码示例加深理解。

1. CLH Lock 的基本原理

CLH Lock 是一种基于链表结构的自旋锁，由 Craig、Landin 和 Hagersten 三位学者分别独立提出，因此得名 CLH Lock。它通过维护一个FIFO队列来保证锁的公平性，即先请求锁的线程先获得锁。

CLH Lock 的核心思想是：每个线程在尝试获取锁时，都在队列的末尾添加一个节点（Node）。每个节点代表一个线程，并且包含一个 locked 状态，表示该线程是否持有锁。线程通过检查其前驱节点的 locked 状态来判断是否可以获得锁。如果前驱节点已经释放锁（locked 为 false），则当前线程就可以获得锁，并将其自身节点的 locked 状态设置为 false，表示自己已经释放锁，可以允许后继节点获取锁。

这种基于队列的机制确保了锁的公平性，因为线程总是按照它们加入队列的顺序来获得锁。

2. CLH Lock 的链表节点结构

CLH Lock 的链表节点结构非常简单，通常只需要一个 locked 状态和一个指向后继节点的指针（隐式存在）。在 Java 中，我们可以使用 AtomicBoolean 来实现 locked 状态，保证其原子性。

import java.util.concurrent.atomic.AtomicBoolean;

public class CLHNode {
    volatile AtomicBoolean locked = new AtomicBoolean(true);
}
  • locked (AtomicBoolean): 这是一个原子布尔变量，用于指示该节点对应的线程是否持有锁。true 表示线程正在等待或持有锁，false 表示线程已经释放锁。使用 AtomicBoolean 可以保证在多线程环境下的可见性和原子性。
  • 后继节点 (隐式): CLH Lock 的链表结构并非显式地维护 next 指针。线程通过 tail 变量来原子性地获取队列的尾部节点，从而隐式地连接到链表中。

3. CLH Lock 的队列维护

CLH Lock 的队列维护主要依靠一个 tail 指针，它指向队列的尾部节点。当一个线程想要获取锁时，它会创建一个新的节点，并将 tail 指针原子性地指向该节点。这个过程使用了 compareAndSet 操作，确保只有一个线程能够成功地将 tail 指针指向新的节点。

import java.util.concurrent.atomic.AtomicReference;

public class CLHLock {
    private final AtomicReference<CLHNode> tail;
    private final ThreadLocal<CLHNode> myNode;
    private final ThreadLocal<CLHNode> myPred;

    public CLHLock() {
        tail = new AtomicReference<>(new CLHNode()); // 初始化 tail 指向一个空的 CLHNode
        myNode = ThreadLocal.withInitial(CLHNode::new); // 每个线程独有的 CLHNode
        myPred = new ThreadLocal<>();
    }

    public void lock() {
        CLHNode node = myNode.get();
        CLHNode pred = tail.getAndSet(node);
        myPred.set(pred);
        while (pred.locked.get()) {
            // 自旋等待前驱节点释放锁
        }
    }

    public void unlock() {
        CLHNode node = myNode.get();
        node.locked.set(false);
        myNode.set(myPred.get()); // 重置 myNode，下次lock时可以复用该node
    }
}

让我们分解这段代码：

  • tail (AtomicReference): 这是一个原子引用，指向队列的尾部节点。
  • myNode (ThreadLocal): 这是一个 ThreadLocal 变量，每个线程都拥有一个独立的 CLHNode 实例。每个线程获取锁时都会复用自己的node，避免频繁创建对象。
  • myPred (ThreadLocal): 这是一个 ThreadLocal 变量，保存当前节点的前驱节点。

4. CLH Lock 的加锁操作

加锁操作的核心逻辑如下：

  1. 获取线程的私有节点 myNode。
  2. 将 tail 指针指向 myNode，并获取原来的 tail 指针 (前驱节点 pred)。 这一步使用 tail.getAndSet(node) 原子操作，确保只有一个线程能够成功更新 tail 指针。
  3. 将前驱节点 pred 保存在 myPred 变量中，方便解锁时使用。
  4. 自旋等待前驱节点释放锁 (pred.locked.get())。 线程会不断检查前驱节点的 locked 状态，直到前驱节点释放锁。
public void lock() {
    CLHNode node = myNode.get();
    CLHNode pred = tail.getAndSet(node);
    myPred.set(pred);
    while (pred.locked.get()) {
        // 自旋等待前驱节点释放锁
    }
}

代码示例解释：

  • CLHNode node = myNode.get();: 从线程本地变量 myNode 中获取当前线程的 CLH 节点。这是每个线程预先分配好的节点，避免了在每次加锁时都创建新节点的开销。
  • CLHNode pred = tail.getAndSet(node);: 这是关键的一步。它使用 AtomicReference 的 getAndSet 方法原子性地完成两件事：
    • 获取当前 tail 指针指向的节点（即前驱节点），并将其赋值给 pred。
    • 将 tail 指针更新为当前线程的节点 node。
      这个操作保证了线程按照请求锁的顺序加入队列。
  • myPred.set(pred);: 将前驱节点 pred 存储到线程本地变量 myPred 中。解锁时需要用到前驱节点。
  • while (pred.locked.get()) { ... }: 这是一个自旋等待循环。线程会不断检查前驱节点 pred 的 locked 状态。只要 pred.locked.get() 返回 true，就表示前驱节点还没有释放锁，当前线程就必须继续等待。

5. CLH Lock 的解锁操作

解锁操作也比较简单：

  1. 将当前节点的 locked 状态设置为 false，表示释放锁。
  2. 将 myNode 设置为 myPred，下次lock时可以复用该node
public void unlock() {
    CLHNode node = myNode.get();
    node.locked.set(false);
    myNode.set(myPred.get()); // 重置 myNode，下次lock时可以复用该node
}

代码示例解释：

  • CLHNode node = myNode.get();: 从线程本地变量 myNode 中获取当前线程的 CLH 节点。
  • node.locked.set(false);: 将当前节点的 locked 状态设置为 false，表示线程已经释放了锁。这一步操作会使得后继节点能够退出自旋等待循环，并获得锁。
  • myNode.set(myPred.get());: 重置 myNode 为前驱节点，以便下次 lock 操作时可以复用该节点，减少对象创建的开销。

6. CLH Lock 的公平性分析

CLH Lock 通过维护一个 FIFO 队列来保证锁的公平性。每个线程在尝试获取锁时，都会加入到队列的末尾。线程只有在其前驱节点释放锁之后才能获得锁。这种机制确保了线程按照它们加入队列的顺序来获得锁，从而避免了饥饿现象。

7. CLH Lock 的优势与劣势

优势：

  • 公平性： CLH Lock 是一种公平锁，可以避免线程饥饿。
  • 自旋等待： 避免了线程的上下文切换，提高了性能。
  • 简单性： CLH Lock 的实现相对简单，易于理解和维护。

劣势：

  • 自旋等待： 如果锁的竞争非常激烈，线程可能会长时间自旋等待，消耗 CPU 资源。
  • NUMA 问题： 在 NUMA (Non-Uniform Memory Access) 架构下，如果线程访问的是远程内存上的 locked 变量，可能会导致性能下降。 每个线程的节点实际上是由上一个持有锁的线程写入的，因此在NUMA架构下可能会引起性能问题。

8. CLH Lock 的应用场景

CLH Lock 适用于以下场景：

  • 需要保证锁的公平性。
  • 锁的持有时间比较短。
  • 锁的竞争不是特别激烈。

9. CLH Lock 的变体：MCS Lock

MCS Lock 是另一种基于队列的自旋锁，也具有公平性。它与 CLH Lock 的主要区别在于：

  • 节点结构： MCS Lock 的节点包含一个指向后继节点的显式指针。
  • 解锁方式： MCS Lock 的解锁操作需要修改后继节点的 locked 状态，而不是自身节点的 locked 状态。

虽然实现细节不同，但 MCS Lock 的基本原理与 CLH Lock 类似，都是通过维护一个 FIFO 队列来保证锁的公平性。

10. CLH Lock 代码示例 (完整可运行)

import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicReference;

public class CLHLock {
    private final AtomicReference<CLHNode> tail;
    private final ThreadLocal<CLHNode> myNode;
    private final ThreadLocal<CLHNode> myPred;

    public CLHLock() {
        tail = new AtomicReference<>(new CLHNode()); // 初始化 tail 指向一个空的 CLHNode
        myNode = ThreadLocal.withInitial(CLHNode::new); // 每个线程独有的 CLHNode
        myPred = new ThreadLocal<>();
    }

    public void lock() {
        CLHNode node = myNode.get();
        node.locked.set(true); // 避免在 unlock 之前，其他线程提前 lock 成功。
        CLHNode pred = tail.getAndSet(node);
        myPred.set(pred);
        while (pred.locked.get()) {
            // 自旋等待前驱节点释放锁
        }
    }

    public void unlock() {
        CLHNode node = myNode.get();
        node.locked.set(false);
        myNode.set(myPred.get()); // 重置 myNode，下次lock时可以复用该node
    }

    static class CLHNode {
        volatile AtomicBoolean locked = new AtomicBoolean(false); // 初始化为false，表示初始状态下没有线程持有锁
    }

    public static void main(String[] args) throws InterruptedException {
        CLHLock lock = new CLHLock();
        int numThreads = 5;
        Thread[] threads = new Thread[numThreads];

        for (int i = 0; i < numThreads; i++) {
            int threadId = i;
            threads[i] = new Thread(() -> {
                lock.lock();
                try {
                    System.out.println("Thread " + threadId + " acquired the lock.");
                    Thread.sleep(100); // 模拟临界区操作
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    System.out.println("Thread " + threadId + " releasing the lock.");
                    lock.unlock();
                }
            });
            threads[i].start();
        }

        for (int i = 0; i < numThreads; i++) {
            threads[i].join();
        }

        System.out.println("All threads finished.");
    }
}

代码运行结果示例：

Thread 0 acquired the lock.
Thread 0 releasing the lock.
Thread 1 acquired the lock.
Thread 1 releasing the lock.
Thread 2 acquired the lock.
Thread 2 releasing the lock.
Thread 3 acquired the lock.
Thread 3 releasing the lock.
Thread 4 acquired the lock.
Thread 4 releasing the lock.
All threads finished.

这个示例展示了如何使用 CLH Lock 来保护临界区，并保证线程按照请求锁的顺序获得锁。 请注意，ThreadLocal 确保每个线程都有自己独立的 CLHNode 实例，避免了线程之间的干扰。

11. CLH Lock 的性能优化

虽然 CLH Lock 具有公平性，但在高并发场景下，自旋等待可能会导致 CPU 资源的浪费。为了提高 CLH Lock 的性能，可以考虑以下优化策略：

  • 自旋等待时间限制： 可以设置一个自旋等待时间上限，如果超过该时间仍未获得锁，则线程放弃自旋，进入阻塞状态。
  • 自适应自旋： 可以根据锁的竞争情况动态调整自旋等待的时间。如果锁的竞争激烈，则缩短自旋等待时间；如果锁的竞争不激烈，则延长自旋等待时间。
  • 结合其他锁机制： 可以将 CLH Lock 与其他锁机制（如互斥锁）结合使用。例如，可以先尝试使用 CLH Lock 获取锁，如果获取失败，则进入互斥锁的等待队列。

12. 表格总结CLH Lock 的特点

特性 描述
公平性 CLH Lock 是一种公平锁，按照 FIFO 队列顺序授予锁，避免线程饥饿。
基于队列 CLH Lock 基于链表队列实现，每个线程对应一个节点，节点通过 locked 状态标识是否持有锁。
自旋等待 线程通过自旋等待前驱节点释放锁，避免线程上下文切换的开销。
NUMA敏感 在 NUMA 架构下，由于线程访问的是远程内存上的 locked 变量，可能会导致性能下降。
适用场景 适用于需要保证锁的公平性、锁的持有时间比较短、锁的竞争不是特别激烈的场景。
代码复杂度 相对简单，易于理解和实现。
线程本地变量 使用 ThreadLocal 存储每个线程的节点信息，避免线程间的干扰，并且可以复用节点，减少对象创建开销。

理解CLH Lock 的核心逻辑

CLH Lock 通过维护一个隐式的 FIFO 队列来实现公平锁。 每个线程拥有一个节点，通过自旋等待其前驱节点的释放来获得锁。这种机制避免了线程饥饿，但自旋等待可能消耗 CPU 资源。

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注