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 locktail 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年。深深的感叹:

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

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

热评文章