无锁算法

Introduction to nonblocking algorithms

当多个线程访问一个变量时,所有线程都要使用同步,否则发发生很不好的结果。Java语言中的最主要的同步方式是使用synchronized关键字,它保证了互斥访问和可见性。正确的使用synchronized可以得到线程安全的程序,但是锁可能太重了,尤其是对很短的代码段而言。

Going Atomic中,我们了解了原子类变量,它提供的原子性的 读-改-写 操作,可以在无锁的条件下安全的更新变量。原子类变量和volatile相似,但是它可以被原子性的修改,可以作为实现无锁并发算法的基础。

一个非阻塞的计数器

代码1中的Counter类是线程安全的,但是锁的使用可能会引起开发者的不满,因为那会增加性能成本。锁是需要的,因为递增其实是三步操作:读变量,加1,写变量。(getValue操作同样需要同步,以保证读到的是最新值。简单的忽略加锁是不好的策略)

当多个线程同时申请一个锁,只有其中一个会获得锁,其他的阻塞。JVM通常以暂停线程的方式实现阻塞,然后在锁可用的时候重新调度线程。涉及到的上下文切换会导致非常明显的延迟,相比于递增操作本身的几个指令。

1
2
3
4
5
6
7
8
9
10
11
12
public final class {
private long value = 0;
public synchronized long getValue() {
return value;
}
public synchronized long increment() {
return ++value;
}
}

代码2中的NonblockingCounter展示了一个最简单非阻塞算法:使用AtomicInteger类的CAS方法实现的计数器。compareAndSet方法的语义是:更新变量的值,但是如果有其他线程在我上次查看之后修改过变量,则不要更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 代码2 使用CAS实现的非阻塞计数器
public class NonblockingCounter {
private AtomicInteger value;
public int getValue() {
return value.get();
}
public int increment() {
int v;
do {
v = value.get();
}
while (!value.compareAndSet(v, v + 1));
return v + 1;
}
}

原子变量类被称为atomic,是因为它们提供了更新粒度的原子更新操作,针对数字和对象引用,也因为它们是构建非阻塞算法的原语。非阻塞算法已经被研究了20几年了,但直到Java5.0才成为可能。现代处理器为原子更新共享变量,提供了特别的指令,可以检测到其他线程的干扰。compareAndSet()用的是这些特性而不是同步锁。

非阻塞算法相比于基于锁的算法,有几个性能优势。它使用硬件原语实现更细粒度(单个内存地址)的同步而不像JVM锁代码路径,获取锁失败的线程可以立即重新尝试而不是被暂停。细粒度减小了竞争的程度,无需重新调度的retry减少了竞争的成本。即便CAS会失败一定次数,这种方法仍然很可能比暂停再调度方式快。

NonblockingCounter是一个简单的例子,但是展示了所有非阻塞算法的基本特性,即某些步骤是伺机执行的,它知道如果CAS操作没有成功就必须重试。非阻塞算法是乐观的,因为它假设没有其他线程干扰或者说干扰很弱。如果真的检测到了干扰,它们会重试。在计数器的例子中,伺机执行的操作是递增,它读一个变量,加1,并期望这个过程中变量没有被修改。如果CAS失败了,它必须重新获取值,加1。

非阻塞栈

下面来看一个不那么简单的例子ConcurrentStackpush()pop()方法的结构和前面的increment()很像,特别是在提交更改时都会检查预先假设是否仍然成立。push()方法先观察顶部元素,构造新元素,然后如果顶部元素没有被修改,插入新元素。如果CAS失败了,意味着有其他线程修改了栈,所以线程必须重试CAS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 代码3
public class ConcurrentStack<E> {
    AtomicReference<Node<E>> head = new AtomicReference<Node<E>>();
 
    public void push(E item) {
        Node<E> newHead = new Node<E>(item);
        Node<E> oldHead;
        do {
            oldHead = head.get();
            newHead.next = oldHead;
        } while (!head.compareAndSet(oldHead, newHead));
    }
 
    public E pop() {
        Node<E> oldHead;
        Node<E> newHead;
        do {
            oldHead = head.get();
            if (oldHead == null)
                return null;
            newHead = oldHead.next;
        } while (!head.compareAndSet(oldHead,newHead));
        return oldHead.item;
    }
 
    static class Node<E> {
        final E item;
        Node<E> next;
 
        public Node(E item) { this.item = item; }
    }
}

性能考量

在中轻度竞争情况下,无阻塞算法可能会远胜于阻塞版本,因为CAS操作大多都能在第一次尝试就成功,即便失败重试也不会涉及到线程暂停和重调度的成本,只是多几次循环。无竞争的CAS操作是比无竞争锁获取的成本更低的,竞争的CAS操作造成的延迟比竞争的锁获取更短。

在高度竞争情况下,许多线程同时操作同一个内存位置,基于锁的算法开始显示出优势。它们可以提供更好的吞吐量,因为阻塞的线程会停止申请锁,进入等待状态,避免了持续的竞争。然而,高级别的竞争很少见,因为大多数时候线程会交替执行本地计算和竞争访问,其他线程是有机会访问到共享数据的。(如果竞争程度很高,请检查你的程序。) Going atomic中的图可能会造成误会,因为程序是在不切实际的竞争程度下运行的,让人觉得好像线程少时,锁也是更好的选择。

一个非阻塞链表

目前看的两个例子—计数器和栈—都是非常简单的非阻塞算法,只要你理解了把CAS操作放在循环里就可以实现它们。对于更复杂的数据结果,非阻塞算法也更复杂,因为修改一个链表、树或者哈希表会涉及到更新多个指针。CAS支持原子性的更新单个指针,但两个就不行了,我们需要找到一种更新多个变量的方式,要保证不会使得数据结构变成不一致的状态。

插入一个元素到链接的结尾涉及到更新两个指针:总是指向最后一个元素的尾指针;之前最后元素的next指针。因为两个指针都要更新,需要两个CAS操作。用两个单独的CAS操作更新引入了两个问题:第一个成功第二个失败意味着什么?两次CAS之间存在其他变量的操作会怎样?

构建非阻塞算法的技巧是确保数据结构始终处在一致的状态,即便是在一个线程修改开始和修改完成中间,还要确保其他线程可以判断前面的线程完成了更新还是正在更新,以及计算出需要做什么操作以弥补前面线程的工作。如果一个线程发现有未完成的更新,它应该可以替代前面的线程完成剩下的工作,再继续自己的操作。当前面的线程回来尝试自己继续完成更新,它会意识到不需要了然后直接返回,因为CAS会检测到有来自帮助线程的干扰(这里是积极的干扰)。

这种 “帮助邻居” 的需求是必要的,这样才能数据结构可以应对某个线程的失败。如果一个线程开始操作的时候,发现数据结构是中间状态,它如果选择等待那个线程完成的话,可能会永远等下去。甚至是在没有线程失败的情况下,这种策略也是很低效的,因为会有上下文切换,或者等待它自己的时间片到期。

代码4展示了一个Michael-Scott非阻塞队列算法的插入操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 代码4
public class LinkedQueue <E> {
    private static class Node <E> {
        final E item;
        final AtomicReference<Node<E>> next;
 
        Node(E item, Node<E> next) {
            this.item = item;
            this.next = new AtomicReference<Node<E>>(next);
        }
    }
 
    private AtomicReference<Node<E>> head
        = new AtomicReference<Node<E>>(new Node<E>(null, null));
    private AtomicReference<Node<E>> tail = head;
 
    public boolean put(E item) {
        Node<E> newNode = new Node<E>(item, null);
        while (true) {
            Node<E> curTail = tail.get();
            Node<E> residue = curTail.next.get();
            if (curTail == tail.get()) {
                if (residue == null) /* A */ {
                    if (curTail.next.compareAndSet(null, newNode)) /* C */ {
                        tail.compareAndSet(curTail, newNode) /* D */ ;
                        return true;
                    }
                } else {
                    tail.compareAndSet(curTail, residue) /* B */;
                }
            }
        }
    }
}

和其他形式的实现一样,空队列是一个哑节点。head指针始终指向哑节点;尾节点指向最后一个或者倒数第二个元素。图1展示了一个包含两个元素的队列。

图1

如代码4所示,插入一个元素涉及到更新两个指针,都是通过CAS操作完成的:链接新节点到目前的最后节点(语句C),重设尾节点为新节点(语句D)。如果第一个操作失败了,那么队列的状态没有改变,线程会重试直到成功。一旦第一个操作成功了,本次新增元素操作被视为已经生效,另一个线程可以立即看到更新。此时还剩下第二个操作,但是这个任务可以被认为是收尾(cleanup)因为任何其他线程都可以识别出是否需要收尾工作和如何完成它。

队列始终处于两个状态之一:正常或者中间状态(图2)。正常状态是指一次insert操作完成到下一次insert操作之前;中间状态是指C成功之后。在正常状态,tail指向的尾节点的next总是null;在中间状态,它指向非空。任何线程都可以区别通过tail.next判断现在是什么状态,这是实现帮助其他线程完成insert操作的关键。

图2

insert操作首先检查队列是否在中间状态(语句A)。如果是,一定存在其他某个线程正在尝试insert,执行到了C、D之间。这时不需要等待那个线程完成,当前线程可以帮助它完成insert操作,即把tail指针移动一步(语句B)。它会持续的检查tail指针,直到队列处在正常状态,这时它才会开始自己的insert操作。

第一个CAS(语句C)可能失败,因为可能两个线程都在访问队列的最后一个元素;失败意味着没有生效,需要重试。如果第二个CAS操作(D)失败,线程不需要重试,因为其他线程会替它完成(使用语句B)。

图3

非阻塞算法底层应用

如果你深入到JVM和OS,你会发现到处都是非阻塞算法。GC使用它们加速并发和并发收集;调度起使用它们高效的调度线程、实现复杂锁。在Java6中,基于锁的SynchronousQueue被替换为非阻塞的版本。几乎没有开发者直接使用SynchronousQueue,但是它有被用作线程池的工作队列,参见Executors.newCachedThreadPool()。评测表明新的非阻塞异步队列提供了三倍的加速。Java的后续版本还有加入更多优化。

总结

非阻塞算法会比基于锁的算法复杂很多。开发非阻塞算法是非常专业的领域,算法正确性的证明极其困难。但是Java的并发性能的改进很多都来自于非阻塞算法的使用。随着并发性能变得日益重要,我们可以期待在未来的Java平台看到更多的非阻塞算法。