Zacard's Notes

LinkedBlockingQueue，我所忽略的并发安全细节

发表于 | 分类于 | | 阅读次数

首先抛出一个问题：

LinkedBlockingQueue首尾2把锁是如何保证并发安全的？

背景

我们知道，要保证共享变量的多线程并发读写安全需要用同一把锁。但是LinkedBlockingQueue有putLock和takeLock2把锁，是如何保证并发安全的呢？

先来看下LinkedBlockingQueue源码上的注释：

A variant of the “two lock queue” algorithm

“two lock queue” algorithm的一个变种。那什么是”two lock queue” algorithm呢？

two lock queue algorithm

这其实是Maged M. Michael 和 Michael L. Scott在1996年发表的论文 Simple, Fast, and Practical Non-Blocking and Blocking描述的其中一种算法

为了提高并发队列的性能，他们提出了一种lock free的无锁算法（基于CAS）。但是在某些不支持CAS指令的机器上，他们同样提出了优化的算法，就是“two lock queue”算法

为什么要用2把锁

如果用一把锁，不管是enqueue入队操作和dequeue出队操作，都需要获取这把唯一的排它锁。在高并发下容易引起激烈竞争导致性能下降。而我们分析下queue的2个主要操作：

  • enqueue操作：总是在队列尾部插入节点
  • dequeue操作：总是在队列头部删除节点

可以发现，enqueue和dequeue在大部分情况下都是相互独立的，并没有发生冲突，无需锁住整个队列。我们自然而然就能想到一个锁的常见优化方法：分段锁。所以队列用头尾2个锁可以大大降低冲突的概率

但是用2把锁在临界点会有些不太好处理的逻辑：

  • 在一个空队列入队一个节点
  • 只剩最后一个节点的时候出队这个节点

这2种情况都需要同时操作修改头尾指针，即需要同时获取head lock和tail lock

危险的逻辑来了，同时获取多把锁非常容易造成死锁。即使我们小心翼翼的设计这块加锁/解锁顺序，这块代码逻辑就会出现多次加锁/解锁逻辑，性能反而可能会下降

论文的算法既然有个“simple”，我们看看论文的算法是如何处理的：

并发分析

伪代码（摘自论文）如下：

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
structure node_t {value: data type, next: pointer to node_t}
 structure queue_t {Head: pointer to node_t, Tail: pointer to node_t,
                       H_lock: lock type, T_lock: lock type}
 
 initialize(Q: pointer to queue_t)
    node = new_node()		// Allocate a free node
    node->next = NULL          // Make it the only node in the linked list
    Q->Head = Q->Tail = node	// Both Head and Tail point to it
    Q->H_lock = Q->T_lock = FREE	// Locks are initially free
 
 enqueue(Q: pointer to queue_t, value: data type)
    node = new_node()	        // Allocate a new node from the free list
    node->value = value		// Copy enqueued value into node
    node->next = NULL          // Set next pointer of node to NULL
    lock(&Q->T_lock)		// Acquire T_lock in order to access Tail
       Q->Tail->next = node	// Link node at the end of the linked list
       Q->Tail = node		// Swing Tail to node
    unlock(&Q->T_lock)		// Release T_lock
 
 dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean
    lock(&Q->H_lock)	        // Acquire H_lock in order to access Head
       node = Q->Head		// Read Head
       new_head = node->next	// Read next pointer
       if new_head == NULL	// Is queue empty?
          unlock(&Q->H_lock)	// Release H_lock before return
          return FALSE		// Queue was empty
       endif
       *pvalue = new_head->value	// Queue not empty.  Read value before release
       Q->Head = new_head	// Swing Head to next node
    unlock(&Q->H_lock)		// Release H_lock
    free(node)			// Free node
    return TRUE		// Queue was not empty, dequeue succeeded

可以看到：队列初始化的时候new了一个空节点，这样在首次入队的时候，队列就不再是空队列，无需修改head指针。在只剩最后一个元素的时候也不是只有一个节点，无需修改tail指针。巧妙的避开了同时修改头尾指针的情况

但是这里还是有个并发问题，假设以下执行顺序：

  • 线程A执行enqueue到第16行
  • 线程B执行dequeue到第24行

线程A在执行完16行的时候已经将首个元素节点入队了，然而线程B在执行24行的时候很有可能没法立即读到这个最新节点。因为2个线程使用不同锁保护，且没有用类似java中的volatile的手段来保证可见性

也就是说这个算法有个可见性问题：

新入队的元素可能无法被立即读到而顺利出队

这个问题挺明显的，作者不至于没有注意。网上搜索了下，看到有位博主对这段有解释：

好在一般来讲next指针是32位数据，而现代的CPU已经能保证多线程程序中内存对齐了的32位数据读写操作的原子性，而一般来讲编译器会自动帮你对齐32位数据，所以这个不是问题

这位博主的的意思应该是：对于节点指针的赋值是一个原子操作，所以其他线程能立即读到这次操作的最新值

个人不认同这个解释，因为原子性（有关原子性/原子操作后面再专门讲下）并不代表可见性！一个原子操作只是代表这个操作是不可分割，不可中断，其他线程不会读到操作一半的值。最典型的例子：在32位多核机器读写long类型的值可能存在问题，因为写long操作是被拆分成写高32位和写低32位两部分的，不是一个原子操作了。然而即便是读写int这种32位数据，在没有voltail或者锁的保护下，也仍然无法做到可见性！

个人看法：这个算法应该确实存在可见性问题。但是，出现的条件比较严苛，必须要队列为空的时候入队，同时有出队线程在读。然而即使出现这种情况，也只会使出队操作表现为无数据，并不影响queue的正确性：

  • queue仍然表现为FIFO的特性，没有错乱
  • 数据也不会丢失，只会延迟读取（出队）

我们看下LinkedBlockingQueue是怎么处理这块的吧

LinkedBlockingQueue

先贴下put()和take()的源码（jdk-1.8）：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// offer,即enqueue入队
public boolean offer(E e) {
    if (e == null) throw new NullPointerException();
    final AtomicInteger count = this.count;
    if (count.get() == capacity)
        return false;
    int c = -1;
    Node<E> node = new Node<E>(e);
    final ReentrantLock putLock = this.putLock;
    putLock.lock();
    try {
        if (count.get() < capacity) {
        		// 这里直接把enqueue这个私有方法内联进来方便分析
        		// enqueue(node);
        		last = last.next = node;
          
            c = count.getAndIncrement();
            if (c + 1 < capacity)
                notFull.signal();
        }
    } finally {
        putLock.unlock();
    }
    if (c == 0)
        signalNotEmpty();
    return c >= 0;
}
// poll,即dequeue出队
public E poll() {
    final AtomicInteger count = this.count;
    if (count.get() == 0)
        return null;
    E x = null;
    int c = -1;
    final ReentrantLock takeLock = this.takeLock;
    takeLock.lock();
    try {
        if (count.get() > 0) {
          	// 这里直接把dequeue这个私有方法内联进来方便分析
            // x = dequeue();
          	Node<E> h = head;
        		Node<E> first = h.next;
        		h.next = h; // help GC
        		head = first;
        		x = first.item;
        		first.item = null;
          
            c = count.getAndDecrement();
            if (c > 1)
                notEmpty.signal();
        }
    } finally {
        takeLock.unlock();
    }
    if (c == capacity)
        signalNotFull();
    return x;
}

并发分析

逻辑和论文基本一致，所以看起来也有一样的可见性问题。请看以下执行序列：

  • 线程A执行到17行
  • 线程B执行到43行

在这个执行序列中，线程A本质上已经将节点入队了，且更新了队列容量。但是由于队列节点无法保证可见性，似乎也没法被线程B立即读到。如果真的是这样，第46行代码是很可能会报NullPointerException的，这肯定不是一个库会有的行为

回过头来再仔细看了一遍注释（源码第97行）和代码：

1
2
3
4
5
6
7
Visibility between writers and readers is provided as follows:
     
      Whenever an element is enqueued, the putLock is acquired and
      count updated.  A subsequent reader guarantees visibility to the
      enqueued Node by either acquiring the putLock (via fullyLock)
      or by acquiring the takeLock, and then reading n = count.get();
      this gives visibility to the first n items.

其实LinkedBlockingQueue的注释中有专门对于可见性的解释说明：

当一个元素入队，获取了putLock并且count更新后。随后的出队线程保证能读到最新入队的节点需要用以下2种的任意一种方法：

  • 方法一：出队线程用时获取putLock：这块大家都能理解，相当于获取2把锁，必然能保证可见性
  • 方法二：获取takeLock后，执行n = count.get()即可保证可见性

之前对于方法二为什么能保证可见性一直没有想明白，为什么执行下count.get()就能保证节点的可见性。直到最近看到《深入Java虚拟机（第三版）》出了，突然想到volatile的语义（count是个AtomicInteger，对于AtomicInteger的读写本质上都是读写一个volatile变量）：

  1. 保证被修饰的变量对所有线程的可见性
  2. 禁止指令重排序优化

附加规则：如果是写操作，会强制将本处理器的缓存写入了主内存，该写入动作也会引起别的处理器或者别的内核无效化(Invalidate)其缓存

基于第2点语义可以得出：当线程1执行到17后，由于完成了volatile的写操作，将强制将缓存的修改写入主内存，因此对于入队节点的更新操作也会立即写入主内存，并且其他核的相关缓存会失效。因此到线程2执行到43行的时候必然能读到最新的值！

volatile的这个技巧的典型应该场景如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private volatile boolean initialized;
private Properties config;
public void init(){
    config = readFromFile();
    initialized = true;
}
public void start(){
    while(!initialized){
        sleep();
    }
    doSomethingWithConfig();
}

假设线程A执行init()后，线程B立即执行了start()。如果没有volatile的第2条语义保证，线程B执行第14行代码，使用的config很可能没有初始化好或者初始化好了，但是对线程B还不可见。这样很可能执行报错！

总结

“two lock queue” 算法并没有保证线程可见性，而使queue的enqueue入队操作对dequeue出队立即可见，存在不可预知的延迟。然而基于此算法的LinkedBlockingQueue利用volatile的“禁止重排序”语义保证了可见性

举一反三一下，使用同样技巧的还有FutureTask：

1
2
3
4
5
// 源码第92行
private volatile int state;
// 源码第104行
private Object outcome; // non-volatile, protected by state reads/writes

感想

学习到了：

当使用volatile变量后，其他变量的修改要保证可见性其实已经无需额外使用volatile修饰，只需要在使用的时候优先读写这个volatile即可

另外，看到大哥李（Doug Lea）的博客上说，LinkedBlockingQueue这段500行的代码写了将近1年。深深的感叹：

并发编程从来都不是一件简单的事，性能优化的路上也没有终点

坚持原创技术分享，您的支持将鼓励我继续创作！

热评文章