聊聊并发(五)原子操做的实现原理

2019年12月09日 阅读数:46
这篇文章主要向大家介绍聊聊并发(五)原子操做的实现原理,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

1    引言html

原子(atom)本意是不能被进一步分割的最小粒子,而原子操做(atomic operation)意为不可被中断的一个或一系列操做。在多处理器上实现原子操做就变得有点复杂。本文让咱们一块儿来聊一聊在Inter处理器和Java里是如何实现原子操做的。java

2    术语定义编程

术语名称缓存

英文安全

解释架构

缓存行并发

Cache line框架

缓存的最小操做单位ide

比较并交换工具

Compare and Swap

CAS操做须要输入两个数值,一个旧值(指望操做前的值)和一个新值,在操做期间先比较下在旧值有没有发生变化,若是没有发生变化,才交换成新值,发生了变化则不交换。

CPU流水线

CPU pipeline

CPU流水线的工做方式就象工业生产上的装配流水线,在CPU中由5~6个不一样功能的电路单元组成一条指令处理流水线,而后将一条X86指令分红5~6步后再由这些电路单元分别执行,这样就能实如今一个CPU时钟周期完成一条指令,所以提升CPU的运算速度。

内存顺序冲突

Memory order violation

内存顺序冲突通常是由假共享引发,假共享是指多个CPU同时修改同一个缓存行的不一样部分而引发其中一个CPU的操做无效,当出现这个内存顺序冲突时,CPU必须清空流水线。

3    处理器如何实现原子操做

32IA-32处理器使用基于对缓存加锁或总线加锁的方式来实现多处理器之间的原子操做。

3.1   处理器自动保证基本内存操做的原子性

首先处理器会自动保证基本的内存操做的原子性。处理器保证从系统内存当中读取或者写入一个字节是原子的,意思是当一个处理器读取一个字节时,其余处理器不能访问这个字节的内存地址。奔腾6和最新的处理器能自动保证单处理器对同一个缓存行里进行16/32/64位的操做是原子的,可是复杂的内存操做处理器不能自动保证其原子性,好比跨总线宽度,跨多个缓存行,跨页表的访问。可是处理器提供总线锁定和缓存锁定两个机制来保证复杂内存操做的原子性。

3.2   使用总线锁保证原子性

第一个机制是经过总线锁保证原子性。若是多个处理器同时对共享变量进行读改写(i++就是经典的读改写操做)操做,那么共享变量就会被多个处理器同时进行操做,这样读改写操做就不是原子的,操做完以后共享变量的值会和指望的不一致,举个例子:若是i=1,咱们进行两次i++操做,咱们指望的结果是3,可是有可能结果是2。以下图

1

(例1

缘由是有可能多个处理器同时从各自的缓存中读取变量i,分别进行加一操做,而后分别写入系统内存当中。那么想要保证读改写共享变量的操做是原子的,就必须保证CPU1读改写共享变量的时候,CPU2不能操做缓存了该共享变量内存地址的缓存。

处理器使用总线锁就是来解决这个问题的。所谓总线锁就是使用处理器提供的一个LOCK#信号,当一个处理器在总线上输出此信号时,其余处理器的请求将被阻塞住,那么该处理器能够独占使用共享内存。

3.3 使用缓存锁保证原子性

第二个机制是经过缓存锁定保证原子性。在同一时刻咱们只需保证对某个内存地址的操做是原子性便可,但总线锁定把CPU和内存之间通讯锁住了,这使得锁按期间,其余处理器不能操做其余内存地址的数据,因此总线锁定的开销比较大,最近的处理器在某些场合下使用缓存锁定代替总线锁定来进行优化。

频繁使用的内存会缓存在处理器的L1L2L3高速缓存里,那么原子操做就能够直接在处理器内部缓存中进行,并不须要声明总线锁,在奔腾6和最近的处理器中可使用缓存锁定的方式来实现复杂的原子性。所谓缓存锁定就是若是缓存在处理器缓存行中内存区域在LOCK操做期间被锁定,当它执行锁操做回写内存时,处理器不在总线上声言LOCK#信号,而是修改内部的内存地址,并容许它的缓存一致性机制来保证操做的原子性,由于缓存一致性机制会阻止同时修改被两个以上处理器缓存的内存区域数据,当其余处理器回写已被锁定的缓存行的数据时会起缓存行无效,在例1中,当CPU1修改缓存行中的i时使用缓存锁定,那么CPU2就不能同时缓存了i的缓存行。

可是有两种状况下处理器不会使用缓存锁定。第一种状况是:当操做的数据不能被缓存在处理器内部,或操做的数据跨多个缓存行(cache line),则处理器会调用总线锁定。第二种状况是:有些处理器不支持缓存锁定。对于Inter486和奔腾处理器,就算锁定的内存区域在处理器的缓存行中也会调用总线锁定。

以上两个机制咱们能够经过Inter处理器提供了不少LOCK前缀的指令来实现。好比位测试和修改指令BTSBTRBTC,交换指令XADDCMPXCHG和其余一些操做数和逻辑指令,好比ADD(加),OR(或)等,被这些指令操做的内存区域就会加锁,致使其余处理器不能同时访问它。

4    JAVA如何实现原子操做

java中能够经过循环CAS的方式来实现原子操做。

4.1 使用循环CAS实现原子操做

JVM中的CAS操做正是利用了上一节中提到的处理器提供的CMPXCHG指令实现的。自旋CAS实现的基本思路就是循环进行CAS操做直到成功为止,如下代码实现了一个基于CAS线程安全的计数器方法safeCount和一个非线程安全的计数器count

001

       private AtomicInteger atomicI = new AtomicInteger(0);

002

003

       private int i = 0;

004

005

       public static void main(String[] args) {

006

007

              final Counter cas = new Counter();

008

009

              List<Thread> ts = new ArrayList<Thread>(600);

010

011

              long start = System.currentTimeMillis();

012

013

              for (int j = 0; j < 100; j++) {

014

015

                     Thread t = new Thread(new Runnable() {

016

017

                            @Override

018

019

                            public void run() {

020

021

                                   for (int i = 0; i < 10000; i++) {

022

023

                                          cas.count();

024

025

                                          cas.safeCount();

026

027

                                   }

028

029

                            }

030

031

                     });

032

033

                     ts.add(t);

034

035

              }

036

037

              for (Thread t : ts) {

038

039

                     t.start();

040

041

              }

042

043

       //等待全部线程执行完成

044

045

              for (Thread t : ts) {

046

047

                     try {

048

049

                            t.join();

050

051

                     } catch (InterruptedException e) {

052

053

                            e.printStackTrace();

054

055

                     }

056

057

              }

058

059

              System.out.println(cas.i);

060

061

              System.out.println(cas.atomicI.get());

062

063

              System.out.println(System.currentTimeMillis() - start);

064

065

       }

066

067

       /**

068

069

        *使用CAS实现线程安全计数器

070

071

        */

072

073

       private void safeCount() {

074

075

              for (;;) {

076

077

                     int i = atomicI.get();

078

079

                     boolean suc = atomicI.compareAndSet(i, ++i);

080

081

                     if (suc) {

082

083

                            break;

084

085

                     }

086

087

              }

088

089

       }

090

091

       /**

092

093

        *非线程安全计数器

094

095

        */

096

097

       private void count() {

098

099

              i++;

100

101

       }

102

103

}

Java1.5开始JDK的并发包里提供了一些类来支持原子操做,如AtomicBoolean(用原子方式更新的 boolean 值),AtomicInteger(用原子方式更新的 int 值),AtomicLong(用原子方式更新的 long 值),这些原子包装类还提供了有用的工具方法,好比以原子的方式将当前值自增1和自减1

Java并发包中有一些并发框架也使用了自旋CAS的方式来实现原子操做,好比LinkedTransferQueue类的Xfer方法。CAS虽然很高效的解决原子操做,可是CAS仍然存在三大问题。ABA问题,循环时间长开销大和只能保证一个共享变量的原子操做。

  1. ABA问题。由于CAS须要在操做值的时候检查下值有没有发生变化,若是没有发生变化则更新,可是若是一个值原来是A,变成了B,又变成了A,那么使用CAS进行检查时会发现它的值没有发生变化,可是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面追加上版本号,每次变量更新的时候把版本号加一,那么ABA就会变成1A-2B3A

Java1.5开始JDKatomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法做用是首先检查当前引用是否等于预期引用,而且当前标志是否等于预期标志,若是所有相等,则以原子方式将该引用和该标志的值设置为给定的更新值。

1

public boolean compareAndSet(

2

               V      expectedReference,//预期引用

3

4

               V      newReference,//更新后的引用

5

6

              int    expectedStamp, //预期标志

7

8

              int    newStamp //更新后的标志

9

)

  1. 循环时间长开销大。自旋CAS若是长时间不成功,会给CPU带来很是大的执行开销。若是JVM能支持处理器提供的pause指令那么效率会有必定的提高,pause指令有两个做用,第一它能够延迟流水线执行指令(de-pipeline,使CPU不会消耗过多的执行资源,延迟的时间取决于具体实现的版本,在一些处理器上延迟时间是零。第二它能够避免在退出循环的时候因内存顺序冲突(memory order violation)而引发CPU流水线被清空(CPU pipeline flush),从而提升CPU的执行效率。
  2. 只能保证一个共享变量的原子操做。当对一个共享变量执行操做时,咱们可使用循环CAS的方式来保证原子操做,可是对多个共享变量操做时,循环CAS就没法保证操做的原子性,这个时候就能够用锁,或者有一个取巧的办法,就是把多个共享变量合并成一个共享变量来操做。好比有两个共享变量i2,j=a,合并一下ij=2a,而后用CAS来操做ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性,你能够把多个变量放在一个对象里来进行CAS操做。

4.2 使用锁机制实现原子操做

锁机制保证了只有得到锁的线程可以操做锁定的内存区域。JVM内部实现了不少种锁机制,有偏向锁,轻量级锁和互斥锁,有意思的是除了偏向锁,JVM实现锁的方式都用到的循环CAS,当一个线程想进入同步块的时候使用循环CAS的方式来获取锁,当它退出同步块的时候使用循环CAS释放锁。详细说明能够参见文章Java SE1.6中的Synchronized

5      参考资料

  1. Java SE1.6中的Synchronized
  2. Intel 64IA-32架构软件开发人员手册
  3. 深刻分析Volatile的实现原理

转载自并发编程网 – ifeve.com本文连接地址: 聊聊并发(五)原子操做的实现原理

聊聊并发(一)深刻分析Volatile的实现原理

聊聊并发(二)Java SE1.6中的Synchronized

聊聊并发(三)Java线程池的分析和使用

聊聊并发(四)深刻分析ConcurrentHashMap

聊聊并发(五)原子操做的实现原理

聊聊并发(六)ConcurrentLinkedQueue的实现原理分析

聊聊并发(七)——Java中的阻塞队列

聊聊并发(八)——Fork/Join框架介绍

聊聊并发(九)Java中的Copy-On-Write容器

聊聊并发(十)生产者消费者模式