使用 Java 示例介绍无锁数据结构

admin管理员组

文章数量:1441141

使用 Java 示例介绍无锁数据结构

1. 简介

在本教程中，我们将了解什么是非阻塞数据结构，以及为什么它们是基于锁的并发数据结构的重要替代方案。

首先，我们将介绍一些术语，例如无障碍、无锁定和无等待。

其次，我们将研究非阻塞算法的基本构建块，如CAS（compare-and-swap）。

第三，我们将研究在Java中实现无锁队列，最后，我们将概述如何实现无等待的方法。

2. 锁定与饥饿

首先，让我们看一下阻塞线程和饥饿线程之间的区别。

在上图中，线程 2 获取了数据结构上的锁。当线程 1 也尝试获取锁时，它需要等到线程 2 释放锁;在获得锁定之前，它不会继续。如果我们在线程 2 保持锁定时挂起它，线程 1 将不得不永远等待。

下图说明了线程匮乏：

在这里，线程 2 访问数据结构，但不获取锁。线程 1 尝试同时访问数据结构，检测并发访问，并立即返回，通知线程它无法完成（红色）操作。然后，线程 1 将重试，直到成功完成操作（绿色）。

这种方法的优点是我们不需要锁。但是，可能发生的情况是，如果线程 2（或其他线程）以高频率访问数据结构，则线程 1 需要大量尝试才能最终成功。我们称之为饥饿。

稍后我们将看到比较和交换操作如何实现非阻塞访问。

3. 非阻塞数据结构的类型

我们可以区分三个级别的非阻塞数据结构。

3.1. 无障碍

无障碍是非阻塞数据结构中最弱的形式。在这里，我们只要求在所有其他线程都挂起时保证线程继续。

更准确地说，如果所有其他线程都挂起，线程不会继续匮乏。从这个意义上讲，这与使用锁不同，如果线程正在等待锁并且持有锁的线程被挂起，则等待线程将永远等待。

3.2. 无锁

数据结构在任何时候至少有一个线程可以继续时提供锁定自由。所有其他线程可能都在匮乏。与无障碍的区别在于，即使没有线程挂起，也至少有一个非饥饿线程。

3.3. 免等待

如果数据结构是无锁的，并且保证每个线程在有限数量的步骤后继续，也就是说，线程不会因“不合理地大量”的步骤而匮乏，则该结构是无等待的。

3.4. 小结

让我们用图形表示来总结这些定义：

图像的第一部分显示了障碍自由，因为只要我们暂停其他线程（底部黄色），线程 1（顶部线程）就可以继续（绿色箭头）。

中间部分显示自由锁定。至少线程 1 可以前进，而其他线程 1 可能正在挨饿（红色箭头）。

最后一部分显示等待自由。在这里，我们保证线程 1 在一段时间的饥饿（红色箭头）后可以继续（绿色箭头）。

4. 非阻塞基元

在本节中，我们将介绍三个基本操作，它们帮助我们在数据结构上构建无锁操作。

4.1. 比较和交换

用于避免锁定的基本操作之一是比较和交换 （CAS） 操作。

比较和交换的想法是，只有当变量仍然具有与我们从主内存中获取变量值时相同的值时，它才会更新。CAS 是一个原子操作，这意味着一起获取和更新是一个操作：

在这里，两个线程都从主内存中获取值 3。线程 2 成功（绿色）并将变量更新为 8。由于线程 1 的第一个 CAS 期望的值仍为 3，因此 CAS 失败（红色）。因此，线程 1 再次获取该值，第二个 CAS 成功。

这里重要的是，CAS 不会获取数据结构上的锁，但如果更新成功，则返回true，否则返回false。

以下代码片段概述了 CAS 的工作原理：

代码语言：javascript代码运行次数：0运行复制

volatile int value;

boolean cas(int expectedValue, int newValue) {
    if(value == expectedValue) {
        value = newValue;
        return true;
    }
    return false;
}Copy

我们仅在新值仍具有预期值时才使用新值更新该值，否则，它将返回false。以下代码片段显示了如何调用 CAS：

代码语言：javascript代码运行次数：0运行复制

void testCas() {
    int v = value;
    int x = v + 1;

    while(!cas(v, x)) {
        v = value;
        x = v + 1;
    }
}Copy

我们尝试更新我们的值，直到 CAS 操作成功，即返回true。

但是，线程可能会陷入饥饿状态。如果其他线程同时对同一变量执行 CAS，则可能会发生这种情况，因此特定线程的操作永远不会成功（或者需要不合理的时间才能成功）。尽管如此，如果比较和交换失败，我们知道另一个线程已经成功，因此我们也确保全局进度，这是锁自由所必需的。

需要注意的是，硬件应支持比较和交换，以使其成为真正的原子操作，而无需使用锁定。

Java在类sun.misc.Unsafe中提供了比较和交换的实现。但是，在大多数情况下，我们不应该直接使用这个类，而应该使用Atomic 变量。

此外，比较和交换并不能防止A-B-A问题。我们将在下一节中介绍这一点。

4.2. load-link/store-condition

比较和交换的替代方法是加载-链接/存储-条件(load-link/store-condition)。让我们首先重新审视比较和交换。正如我们之前看到的，CAS 仅在主内存中的值仍然是我们预期的值时才更新该值。

但是，如果值已更改，并且同时已更改回其先前的值，则 CAS 也会成功。

下图说明了这种情况：

线程 1 和线程 2 都读取变量的值，即 3。然后线程 2 执行 CAS，成功将变量设置为 8。然后，线程 2 执行 CAS 将变量设置回 3，这也成功了。最后，线程 1 执行 CAS，期望值为 3，并且也成功，即使我们的变量的值在两者之间修改了两次。

这被称为A-B-A问题。当然，根据用例的不同，这种行为可能不是问题。但是，其他人可能不希望这样做。Java 提供了使用AtomicStampedReference类的load-link/store-condition实现。

4.3. 获取和添加

另一种选择是获取并添加。此操作将主内存中的变量递增给定值。同样，重要的一点是操作以原子方式发生，这意味着没有其他线程可以干扰。

Java在其原子类中提供了fetch-and-add的实现。例如AtomicInteger.incrementAndGet（），它递增值并返回新值;和AtomicInteger.getAndIncrement（），它返回旧值，然后递增该值。

5. 从多个线程访问链接队列

为了更好地理解两个（或多个）线程同时访问队列的问题，让我们看一下链接队列和两个线程尝试同时添加元素。

我们将看到的队列是一个双链接的FIFO队列，我们在最后一个元素（L）之后添加新元素，变量尾部指向最后一个元素：

要添加新元素，线程需要执行三个步骤：1） 创建新元素（N 和 M），指向下一个元素的指针设置为null;2）使对前一个元素的引用指向L，对L的下一个元素的引用分别指向N（M）。3）尾点分别为N（M）：

如果两个线程同时执行这些步骤，会出现什么问题？如果上图中的步骤按 ABCD 或 ACBD 的顺序执行，则 L 和尾部将指向 M.N 将与队列保持断开连接。

如果步骤按 ACDB 顺序执行，tail将指向 N，而 L 将指向 M，这将导致队列不一致：

当然，解决此问题的一种方法是让一个线程获取队列上的锁。我们将在下一章中看到的解决方案将使用我们之前看到的 CAS 操作，在无锁操作的帮助下解决问题。

6. Java 中的非阻塞队列

让我们看一下 Java 中的基本无锁队列。首先，让我们看一下类成员和构造函数：

代码语言：javascript代码运行次数：0运行复制

public class NonBlockingQueue<T> {

    private final AtomicReference<Node<T>> head, tail;
    private final AtomicInteger size;

    public NonBlockingQueue() {
        head = new AtomicReference<>(null);
        tail = new AtomicReference<>(null);
        size = new AtomicInteger();
        size.set(0);
    }
}Copy

重要的部分是将头和尾引用声明为AtomicReference_s，这确保了对这些引用的任何更新都是原子操作。Java 中的此数据类型实现了必要的比较和交换_操作。

接下来，让我们看一下 Node 类的实现：

代码语言：javascript代码运行次数：0运行复制

private class Node<T> {
    private volatile T value;
    private volatile Node<T> next;
    private volatile Node<T> previous;

    public Node(T value) {
        this.value = value;
        this.next = null;
    }

    // getters and setters 
}Copy

在这里，重要的部分是对上一个和下一个节点的引用声明为易失性。这确保了我们始终在主内存中更新这些引用（因此对所有线程都直接可见）。实际节点值也是如此。

6.1. 无锁添加

我们的无锁添加操作将确保我们在尾部添加新元素，并且不会与队列断开连接，即使多个线程想要同时添加新元素：

代码语言：javascript代码运行次数：0运行复制

public void add(T element) {
    if (element == null) {
        throw new NullPointerException();
    }

    Node<T> node = new Node<>(element);
    Node<T> currentTail;
    do {
        currentTail = tail.get();
        node.setPrevious(currentTail);
    } while(!tailpareAndSet(currentTail, node));

    if(node.previous != null) {
        node.previous.next = node;
    }

    headpareAndSet(null, node); // for inserting the first element
    size.incrementAndGet();
}Copy

要注意的重要部分是突出显示的线条。我们尝试将新节点添加到队列中，直到 CAS 操作成功更新尾部，该尾部必须仍然是我们附加新节点的尾部。

6.2. 无锁获取

与添加操作类似，无锁 get 操作将确保我们返回最后一个元素并将尾巴移动到当前位置：

代码语言：javascript代码运行次数：0运行复制

public T get() {
    if(head.get() == null) {
        throw new NoSuchElementException();
    }

    Node<T> currentHead;
    Node<T> nextNode;
    do {
        currentHead = head.get();
        nextNode = currentHead.getNext();
    } while(!headpareAndSet(currentHead, nextNode));

    size.decrementAndGet();
    return currentHead.getValue();
}Copy

同样，要注意的重要部分是突出显示的线条。CAS 操作确保我们仅在同时没有删除其他节点时才移动当前头。

Java已经提供了一个非阻塞队列的实现，ConcurrentLinkedQueue。这是本文中描述的 M. Michael 和 L. Scott 的无锁队列的实现。这里一个有趣的旁注是，Java 文档指出它是一个免等待队列，它实际上是无锁的。Java 8 文档正确地调用了无锁实现。

7. 免候队列

正如我们所看到的，上面的实现是无锁的，但是，不是无等待的。add和get方法中的while循环可能会循环很长时间（或者，尽管不太可能，但永远循环），如果有许多线程访问我们的队列。

我们如何实现等待自由？一般来说，免等待算法的实现非常棘手。我们向感兴趣的读者推荐这篇论文，其中详细描述了免等待队列。在本文中，让我们看一下如何处理队列的无等待实现的基本思想。

免等待队列要求每个线程都有保证的进度（在有限数量的步骤之后）。换句话说，我们的 add 和 get 方法中的while循环必须在一定数量的步骤后成功。

为了实现这一点，我们为每个线程分配一个帮助程序线程。如果该帮助程序线程成功将一个元素添加到队列中，它将帮助另一个线程在插入另一个元素之前插入其元素。

由于帮助程序线程本身有一个帮助程序，并且在整个线程列表中，每个线程都有一个帮助程序，我们可以保证线程在每个线程完成一次插入后最晚成功插入。下图说明了这个想法：

当然，当我们可以动态添加或删除线程时，事情会变得更加复杂。

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2023-02-22，如有侵权请联系 cloudcommunity@tencent 删除前往查看线程java数据结构队列教程

本文标签： 使用 Java 示例介绍无锁数据结构