java多线程——CAS

阅读 541
收藏 24
2017-09-19
原文链接:mp.weixin.qq.com

关于无锁队列,网上有很多介绍了,我做一个梳理,从它是什么再到它有哪些特性以及应用做一个总结,方便自己使用和记录。

本文主要内容:

非阻塞同步是什么

cas是什么

特性

ABA问题

无阻塞队列

1
非阻塞同步

互斥同步属于一种悲观的并发策略,总认为只要不去做正确的同步措施,肯定会出问题,无论共享数据是否真的会出现竞争,它都要进行加锁。

而基于冲突检测的乐观并发策略,是先进行操作,如果没有竞争,就操作成功了,如果有竞争,产生冲突了,就采用补救措施,常见的就是不断的重试。

CAS就是一种乐观并发策略,除了CAS以外,还有

  • Test-and-Set(测试并设置),

  • Fetch-and-Increment(获取并增加),

  • Swap(交换),

  • LL/SC(加载链接/条件存储)

以上这些都需要硬件指令集的支持才具备原子性。比如在IA64、x86 CPU架构下可以通过cmpxchg指令完成CAS功能,而在ARM和PowerPC架构下,需要ldrex/strex指令来完成LL/SC的功能。

2
CAS是什么

cas全称为Compare-and-Swap(比较并交换),有3个操作数,分别是内存位置V、旧的的预期值A、新值B,那么当且仅当V符合旧的预期值A时,处理器用新值B更新V的值为B。

这些处理过程有指令集的支持,因此看似读-写-改操作只是一个原子操作,所以不存在线程安全问题。我们看个cas的操作过程伪代码:

int value ;

int compareAndSwap (int oldValue,int newValue){

    int old_reg_value =value ;

    if (old_reg_value==old_reg_value)

        value =newValue;

    return old_reg_value ;

}

当多个线程尝试使用CAS同时更新同一个变量的时候,只有其中一个线程能够更新变量的值。当其他线程失败后,不会像获取锁一样被挂起,而是可以再次尝试,或者不进行任何操作,这种灵活性就大大减少了锁活跃性风险。

3
CAS特性

我们知道采用锁对共享数据进行处理的话,当多个线程竞争的时候,都需要进行加锁,没有拿到锁的线程会被阻塞,以及唤醒,这些都需要用户态到核心态的转换,这个代价对阻塞线程来说代价还是蛮高的,那cas是采用无锁乐观方式进行竞争,性能上要比锁更高些才是,为何不对锁竞争方式进行替换?

要回答这个问题,我们先举个例子。

当你开车在上班高峰期的时候,如果通过交通信号灯来控制车流,可以实现更高的吞吐量,而环岛虽然无红绿灯让你等待,但你一圈不一定能绕出你先出去的那个路口,有时候可能得多走几圈,而在低拥堵的时候,环岛则能实现更高的吞吐量,你一次就可以成功,而红路灯反而效率低下了,即便人不多,你依然需要等待。

这个例子依然适应锁和cas的比较,在高度竞争的情况下,锁的性能将超过cas的性能,但在中低程度的竞争情况下,cas性能将超过锁的性能。多数情况下,资源竞争一般都不会那么激烈。

4
非阻塞无锁链表

我们参考一个ConcurrentLinkedQueue 的源码实现,来看下cas的应用。

ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列,它是个单向链表,每个链接节点都拥有一个当前节点的元素和下一个节点的指针。

 Node< E> {

    volatile E item;

    volatile Node< E> next;

}

它采用先进先出的规则对节点进行排序,当我们添加一个元素的时候,它会添加到队列的尾部(tail),当我们获取一个元素时,它会返回队列头部(head)的元素。tail节点和head节点方便我们快速定位最后一个和第一个元素。

我们看下添加一个元素的源码实现:

public boolean offer (E e) {

    checkNotNull(e);

    final Node<E> newNode = new Node<E>(e) ;

   

   //从tail执向的节点开始循环,查找尾部节点,

   //然后插入,直到插入成功。

    for (Node<E> t = tail, p = t;;) {

        Node<E> q = p.next;

        if (q == null) {

            // p 是最后一个节点

            if (p.casNext(null, newNode)) {

                if (p != t)

                    casTail(t, newNode);  // 更新tail节点指针指向newNode

                return true;

            }

            // 没有竞争上cas的线程,继续循环

        }

        else if (p == q)

            p = (t != (t = tail)) ? t : head ;

        else

            p = (p != t && t != (t = tail)) ? t : q;

    }

}

上述代码主要做了如下功能:

1、从tail指针指向的节点开始循环,查找尾节点,尾节点的特征是next为null。

2、如果当前节点的nextNode!=null,则继续查找nextNode的nextNode。

3、如果当前节点的nextNode==null,表明找到尾部节点,则添加newNode到尾部节点的nextNode。

4、更新tail指针,一般指向最新尾节点.

5、如果tail节点nextNode==null,则不更新,表明上一次已经指向最新的尾node。

6、如果!=null,则更新为newNode,2次插入操作更新一次

示图:

上面的代码算法过于复杂,简化如下:

while ( true){

    //添加尾节点的next节点,成功之后,更新tail的指针指向最新尾节点

    if (tail.casNext( null, newNode)) {

        casTail(tail, newNode) ; 

        return true;

    }

}

为何要2次插入node之后,再更新tail的指针?

1、减少tail的写入次数,从而减小write开销

2、tail的读次数增加不会影响性能,虽然增加一次循环开销,但相对于写来说并不大。

3、tail加快入队效率,不会每次入队都从head开始找尾部node

有两次CAS操作,如何保证一致性?

1、如果第一个cas更新成功,第二个失败,那么对了tail会出现不一致的情况。而且即便是都更新成功了,在执行两个cas之间,仍然可能有另外一个线程会访问这个队列,那么如何保证这种多线程情况下不会出错。

2、对于第一个问题,即便tail更新失败,上述代码也会循环的找到真正的尾节点,在这里不是强制要求以tail为尾节点,它只是一个靠近尾节点的指针。

3、第二种情况,如果线程B抵达时候,发现线程A正在执行更新,那么B线程会通过反复循环来检查队列的状态,直到A完成更新,B线程又拿到了nextNode最新信息,添加新的node,从而使两个线程不会相互干扰。

5
ABA问题

尽快CAS看起来很完美,但从语义上来说并不是完美的,存在这样一个逻辑漏洞:

如果一个变量V初次读取的时候是A值,并且在准备赋值的时候检查到它依然是A值,那么我们就认定它没有改变过。如果在这期间它的值被改为B,后来又改为A,那么CAS就会误认为它从来没有被改变过,这个漏洞也被成为“ABA”问题。

在c的内存管理机制中广泛使用的内存重用机制,如果是cas更新的是指针,机会出现一些指针错乱的问题。常见的ABA问题解决方式,就是在更新的时候增加一个版本号,每次更新之后版本号+1,从而保证数据一致。

不过大部分情况下ABA问题都不会影响到程序的正确性,如果需要解决,可以特殊考虑下,或者采用传统的互斥同步会更好。

end

每周一篇技术干货,坚持原创,关注游戏研发,扫描关注更多

评论