Java多线程 -- JUC包源码分析17 -- 弱一致性与无锁队列

时间:2022-09-21 09:56:12

ConcurrentHashMap的弱一致性
SynchronousQueue的弱一致性
Exchanger的弱一致性
Linux内核无锁队列的弱一致性
总结

经过前面一系列的源码分析,我们基本覆盖了JUC包的所有组件。在这诸多组件中,我们总是不断看到一个如影随行的东西:CAS。

相当锁来讲,它的原子粒度更小,只是作用在一个基本变量上面(比如一个Integer, Long, 或者Reference),而不像Lock那样,全局加锁,因此它的并发度更大。

但任何事情总是有2面,在带来高并发度的同时,也带来了另一个问题:“弱一致性”。
因为“弱一致性”的存在,极大的增加了我们的编码难度。在前面ConcurrentHashMap,Exchanger, SynchronousQueue的分析中,我们都在一定程度上,感受都了“弱一致性”所带来的编码复杂度。

本文试图对前面所讲到的诸多“弱一致性问题“进行一个全面梳理,同时分析一下Linux内核的一个“地道的“真正的无锁队列,以及它所面对的弱一致性问题。

希望最终可以让大家对”弱一致性“有一个深刻理解,这也就能更好的理解,为什么”弱一致性“给编码带来了诸多复杂性。

ConcurrentHashMap的弱一致性

case1: clear函数的弱一致性

clear执行完毕,map中仍然还有元素存在。
原因: 因为是每个segment分别加锁,clear下一个segment的时候,上一个segment的锁已经释放,此时其他线程可以再往里面放元素。

case2: put进去的元素,get出来为null

原因:因为tab[index] = new HashEntry

case 3: put进去的元素,get出来为空

原因:因为get不加锁,在put执行 count = c 那行代码之前,虽然元素放进去了,但因为没有happen before约束,可能get不到。(具体代码此处就不再次列出,参见前面ConcurrentHashMap源码分析)

SynchronousQueue的弱一致性

在前面我们知道,TransferQueue/TransferStak都是基于一个单向链表实现的。多线程访问这个链表的时候,并没有加锁,只是对head/tail进行了CAS访问。因此就造成了以下的”弱一致性“问题:

//TransferQueue.transfer
Object transfer(Object e, boolean timed, long nanos) {
QNode s = null; // constructed/reused as needed
boolean isData = (e != null);

for (;;) {
QNode t = tail;
QNode h = head;
if (t == null || h == null)
continue;

if (h == t || t.isData == isData) {
QNode tn = t.next;
if (t != tail) //上面明明赋值的t = tail,此处却出现了t != tail。这是因为有其他线程在对tail做CAS操作。因此造成inconsist read
continue;
。。。
}

Exchanger的弱一致性

 private Object doExchange(Object item, boolean timed, long nanos) {
Node me = new Node(item);
int index = hashIndex();
int fails = 0;

for (;;) {
Object y;
Slot slot = arena[index];
if (slot == null)
createSlot(index);
else if ((y = slot.get()) != null &&
slot.compareAndSet(y, null)) { //slot里面有人等待交换,则把slot清空,Node拿出来,俩人在Node里面交互。把Slot让给后面的人,做交互地点
Node you = (Node)y;
if (you.compareAndSet(null, item)) {//slot清空了,正要准备在Node里面交换呢,却被别的线程抢了,导致you.compareAndSet失败。可谓螳螂扑蝉,黄雀在后
LockSupport.unpark(you.waiter);
return you.item;
}
}
。。。
}

上述问题之所以会发生,就是因为slot.comareAndSet和you.compareAndSet,各自分别都是原子的,但合在一起,却不是原子的。

Linux内核无锁队列的弱一致性

在Linux内核中,有一个基于RingBuffer做的完全无锁的队列kfifo,连CAS都没有用。当然,它有个前提:只能1读1写。
源码链接如下:
https://github.com/opennetworklinux/linux-3.8.13/blob/master/kernel/kfifo.c

struct kfifo {   
unsigned char *buffer; /* the buffer holding the data */
unsigned int size; /* the size of the allocated buffer */
unsigned int in; /* data is added at offset (in % size) */
unsigned int out; /* data is extracted from off. (out % size) */
spinlock_t *lock; /* protects concurrent modifications */
};

入队的时候,操作变量in;出队的时候,操作变量out。

unsigned int __kfifo_in(struct __kfifo *fifo,
const void *buf, unsigned int len)
{
unsigned int l;

l = kfifo_unused(fifo);
if (len > l)
len = l;

kfifo_copy_in(fifo, buf, len, fifo->in);
fifo->in += len; //入队,in指针前移
return len;
}

unsigned int __kfifo_out(struct __kfifo *fifo,
void *buf, unsigned int len)
{
len = __kfifo_out_peek(fifo, buf, len);
fifo->out += len; //出对, out指针前移
return len;
}

static inline unsigned int kfifo_unused(struct __kfifo *fifo)
{
return (fifo->mask + 1) - (fifo->in - fifo->out); //判断未用的空间
}

unsigned int __kfifo_out_peek(struct __kfifo *fifo,
void *buf, unsigned int len)
{
unsigned int l;

l = fifo->in - fifo->out;
if (len > l)
len = l;

kfifo_copy_out(fifo, buf, len, fifo->out);
return len;
}

从上面可以看出,无论是int, out,还是判断队列是否为空/为满,都没有加锁,也没有CAS,至所以能做到这点,是因为2个前提:
(1)只有1读1写,一个操作in,一个操作out
(2)弱一致性:放的时候,队列没有满,可能会判断成已满;取的时候,队列不为空,但判断成已空。但没有关系,生产者/消费者本来就是循环调用的,本次取不到,循环回来重试的时候,可能就取到了。

当然,关于kfifo,还有其他一些小技巧在里面,此次不再详述。大家可以参加下面的文章
http://blog.csdn.net/linyt/article/details/5764312

总结

在上面,我们列举了诸多“弱一致性”的例子,总结下来:
(1)至所以会出现这个问题,就是因为不加锁,或者锁的粒度太细(CAS)。没办法像Lock那样,可以有临界区,”大面积“的加锁,实现多个操作合在一起的原子操作。
(2)这个问题的解决办法,通常就是”循环重试“。因为inconsistent read,那就再读一次。