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

时间：2021-07-04 06:16:36

–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，那就再读一次。

标签：

相关文章