JAVA并发编程(二)-线程基础

串行、并发和并行

串行:完成事情A之后再去完成事情B再去完成事情C

并发:事情A(花费5分钟,等待10分钟),事情B(花费7分钟,等待3分钟),事情C(花费10分钟),则总共需要5+7+10分钟,A事情在等待的时候可以做事情B,B事情在等待的时候可以做事情C

并行:事情A,事情B,事情C同时进行

竞态

在多线程编程下,经常会出现同样的输出,不同的输出,有时候是正确的,有时候是错误的,这样的结果称为竞态.

来看一个多线程的例子:

public class RaceConditionDemo {
    public static void main(String[] args) throws Exception {
        Thread[] workerThreads = new Thread[4];
        for (int i = 0; i < 4; i++) {
            workerThreads[i] = new WorkerThread(i, 10);
        }
        // 待所有线程创建完毕后，再一次性将其启动，以便这些线程能够尽可能地在同一时间内运行
        for (Thread ct : workerThreads) {
            ct.start();
        }
    }
    // 模拟业务线程
    static class WorkerThread extends Thread {
        private final int requestCount;
        public WorkerThread(int id, int requestCount) {
            super("worker-" + id);
            this.requestCount = requestCount;
        }
        @Override
        public void run() {
            int i = requestCount;
            String requestID;
            RequestIDGenerator requestIDGen = RequestIDGenerator.getInstance();
            while (i-- > 0) {
                // 生成Request ID
                requestID = requestIDGen.nextID();
                processRequest(requestID);
            }
        }
        // 模拟请求处理
        private void processRequest(String requestID) {
            // 模拟请求处理耗时
            Tools.randomPause(50);
            System.out.printf("%s got requestID: %s %n",
                    Thread.currentThread().getName(), requestID);
        }
    }
}

public final class RequestIDGenerator implements CircularSeqGenerator {
    /**
     * 保存该类的唯一实例
     */
    private final static RequestIDGenerator INSTANCE = new RequestIDGenerator();
    private final static short SEQ_UPPER_LIMIT = 999;
    private short sequence = -1;
    // 私有构造器
    private RequestIDGenerator() {
        // 什么也不做
    }
    /**
     * 返回该类的唯一实例
     *
     * @return
     */
    public static RequestIDGenerator getInstance() {
        return INSTANCE;
    }
    /**
     * 生成循环递增序列号
     *
     * @return
     */
    @Override
    public short nextSequence() {
        if (sequence >= SEQ_UPPER_LIMIT) {
            sequence = 0;
        } else {
            sequence++;
        }
        return sequence;
    }
    /**
     * 生成一个新的Request ID
     *
     * @return
     */
    public String nextID() {
        SimpleDateFormat sdf = new SimpleDateFormat("yyMMddHHmmss");
        String timestamp = sdf.format(new Date());
        DecimalFormat df = new DecimalFormat("000");
        // 生成请求序列号
        short sequenceNo = nextSequence();
        return "0049" + timestamp + df.format(sequenceNo);
    }
}

期望是每次请求这个类,都能够获得最新的ID,但是从结果来看

worker-3 got requestID: 0049200310213205000 
worker-0 got requestID: 0049200310213205002 
worker-0 got requestID: 0049200310213205004 
worker-2 got requestID: 0049200310213205000 
worker-1 got requestID: 0049200310213205001

不同线程之间很快就出现了相同的id,这里结果就是产生了竞态,按照代码来说,这里总共要生成40个id,预期需要输出到39才对,这里最大的值才为38,所以结果是不符合我们期望的

竞态产生的原因及条件

如上面这个例子所看,为什么会产生竞态,原因在于sequence++在java中执行的操作其实是分为三步

load(sequence,r1)//将变量sequence的值从内存中读取到寄存器r1
increment(r1)//将寄存器r1的值增加1
store(sequence,r1)//将寄存器r1的值写入变量sequence对应的内存空间

所以我们这里会发现我们有可能线程1正在increment(r1)的时候,线程2又load(sequence,r1),导致本来线程2读取了过时的数据,即获取到了脏数据,或者在store数据的时候,其他线程已经将数据更新了,相当于将过时的数据又重新覆盖到了内存中.

线程安全性

一般而言,如果一个类在单线程环境下能够正常运行并且在多线程下不用任何改变也能获得正确的结果,我们称为线程安全,如上面的例子,在多线程的情况下获得的结果有可能不是预期的,那么就是线程不安全的,可以说一个线程安全的类不会导致竞态,一个线程不安全的类会导致竞态

java中常用的ArrayList,HashMap,SimpleDateFormat都是线程不安全的,大家要慎重使用

原子性

多线程中的原子性类似于数据库中的原子性,说明这个操作是不可分割的,含义为一个线程访问共享变量(被多个线程访问的变量)的操作,在其他线程看来要么这个操作尚未开始,要么这个操作就已经结束了.

在JAVA中,基础数据类型,long和double类型在jvm规范中无需实现为原子性,其他数据类型需要(byte,boolean,int,short,char,float)实现为原子性,long和double不需要实现原因为,在32位的JVM下,long和double是8个字节64位的,机器需要对64位的值进行两次更新,一次是对低32位进行更新,一次是对高32位进行更新,多线程下可能会导致一个线程更新了值的高32位,另外一个线程更新了值的低32位,导致值完全不对,引起错误.当然在64位的JVM下,long和double的写操作也是原子的.

两个原子操作合在一起是原子操作吗?
不是,例如a = 1,b=2;
在执行完a=1,准备执行b=2的时候,其他线程现在获取到b的值并非是2.

可见性

如果一个线程对某个共享变量进行更新之后,其他线程可以读取到该更新结果,则称为该线程对该变量的更新对其他线程可见,否则称为不可见.多线程的环境下,正是因为某些线程读取到了旧数据使程序出现我们不期望的结果.

另一方面,可见性问题与计算机的存储系统有关,程序中的变量可能会被分配到寄存器中而不是主内存中进行存储,每个处理器都有其寄存器,而一个处理器是无法获取其他寄存器上的内容的,因此,如果正好两个线程运行在不同的处理器上,又都正好将变量放到寄存器上存储,那么就会有可见性的问题.即使某个共享变量是分配到主内存中进行存储的,也不能保证该变量的可见性,因为处理器对内存的访问不是直接访问,而是通过其高速缓存(Cache)子系统进行的.一个处理器上运行的线程对变量的更新可能只是更新到该处理器的写缓存器(sotre buffer)中,还没有到达该处理器的高速缓存中,更不用说到主内存中了.而一个处理器的写缓冲器中的内容又无法被另一个处理器读取,因此运行在另一个处理器上的线程无法看到这个线程对共享对量的更新.即便一个处理器将共享变量的更新结果写入高速缓存,可能该处理器将变量更新的结果通知给其他处理器的时候,其他处理器可能仅仅将这个更新通知内容存入无效化队列,而没有直接更新其高速缓存的相应内容,这就导致其他处理器读取相应共享变量时,从自身处理器的高速缓存中读取到的变量是一个过时的值.处理器对内存的读写操作,是通过寄存器(Register),高速缓存(Cache),写缓冲器(Store Buffer)和无效化队列等部件执行内存的读写操作的.
虽然一个处理器的高速缓存内容不能被其他处理器直接读取,但是可以通过缓存一致性协议来读取其他处理器的高速缓存中的数据,并将读取到的数据更新到该处理器的高速缓存中,这种处理器从自身处理器缓存以外的其他存储部件中读取数据并更新到自身处理器的高速缓存的过程,我们称为缓存同步.缓存同步使得一个处理器可以读取到另一个处理器上对其他共享变量的更新,保障了可见性.所以,为了保障可见性,我们必须使一个处理器对共享变量所做的更新最终写入该处理器的高速缓存或者主内存中,这个过程称为冲刷处理器缓存.并且一个处理器在读取共享变量的时候,如果其他处理器在此之前已经更新了该变量,那么必须要从其他处理器的高速缓存或者主内存中对相应的变量进行缓存同步,这个过程称为刷新处理器缓存.因此,可见性的保障是通过使更新共享变量的处理器执行冲刷处理器缓存的动作,并使读取共享变量的处理器执行刷新处理器缓存的动作来实现的.

可见性和原子性的关联

原子性可以保障线程更新的变量值是原始值或者相对新值(其他线程能够读取到该线程更新后的值,则称为该值是该共享变量的相对新值),如果读取这个共享变量并使用该变量的时候,其他线程无法改变该变量的值,则我们称为是该变量的最新值.

可见性是一个线程对共享变量的更新对于其他线程是否可见,保障可见性才意味着其他值可以读取到共享变量的相对新值.

java中的volatile关键字

//TODO

有序性

在单线程下重排序可以保证最终执行的结果与程序顺序执行的结果一致，但是在多线程下就会存在问题.有序性指在什么情况下一个处理器上运行的线程执行的内存访问操作在另一个处理器上运行的其他线程看来是乱序的.顺序结构是我们希望某个操作必须先于另外一个操作得以执行,但是在多和处理器下,这种代码的操作顺序是没有保障的,重排序的发生的场景如下:

编译器可能改变两个操作的先后顺序
处理器可能不是完全依照程序的目标代码所指定的顺序执行指令
一个处理器上执行的多个操作,从其他处理器的角度来看执行的顺序又与代码顺序不一致

重排序是对内存能访问的有关操作(读和写)所做的一种优化,它可以在不影响单线程程序正确性的情况下提升程序的性能,但是它可能会导致线程安全问题.

源代码顺序:源代码中指定的内存访问操作顺序
程序顺序:在给定处理器上运行的代码指定的内存访问操作顺序.java有解释执行和编译执行,具体可以查看

Java 是编译型语言还是解释型语言？ - 知乎
https://www.zhihu.com/question/19608553

执行顺序:内存访问操作在给定处理器上的实际执行顺序
感知顺序:给定处理器所感知到的处理器及其他处理器的内存访问操作发生的顺序

重排序类型	表现	重排序来源
指令重排序	源代码顺序不一致	编译器
指令重排序	执行顺序与程序顺序不一致	JIT编译器,处理器
存储子系统排序	源代码顺序,程序顺序和执行顺序三者保持一致,但是感知顺序与执行顺序不一致	高速缓存,写缓冲器

指令重排序

编译器导致的指令重排序

在源代码顺序与程序顺序不一致或者执行顺序与程序顺序不一致的情况下,称为发生了指令重排序.

JAVA包括两种编译器,静态编译器(javac)和动态编译器(JIT编译器)前者的作用是将Java源代码编译成字节码文件(.class)文件,它是在代码编译结点接入的,后者的作用是将字节码动态编译为JAVA虚拟机宿主机的本地代码(机器码),即JAVA可以跨平台运行,它是在java程序运行过程中介入的

int a = 1; //①
int b = 2;//②
int c = a + b;//③

如上述代码,代码执行时变量c依赖变量a和b,但是变量a和b的执行顺序不影响结果,所以有可能先执行②,再执行①,最后才执行③

public class Singleton {
  static Singleton instance;
  static Singleton getInstance(){
    if (instance == null) {
      synchronized(Singleton.class) {
        if (instance == null)
          instance = new Singleton();
        }
    }
    return instance;
  }
}

我们先看 instance = new Singleton() 的未被编译器优化的操作

指令 1：分配一块内存 M；
指令 2：在内存 M 上初始化 Singleton 对象；
指令 3：然后 M 的地址赋值给 instance 变量。

编译器优化后的操作指令

指令 1：分配一块内存 M；
指令 2：将 M 的地址赋值给 instance 变量；
指令 3：然后在内存 M 上初始化 Singleton 对象。

现在有A，B两个线程，我们假设线程A先执行getInstance()方法，当执行编译器优化后的操作指令2时（此时候未完成对象的初始化），这时候发生了线程切换，那么线程B进入，刚好执行到第一次判断instance == null 会发现instance
不等于null了，所以直接返回instance，而此时instance是没有初始化的

重排序并非是一定会出现的,只是偶尔会出现,但是也不能无视多线程下之下指令重排序导致的线程安全问题.

处理器导致的指令重排序

处理器也可能执行指令重排序,这使得执行顺序与程序顺序不一致,处理器对指令进行重排序也称为处理器的乱序执行,处理器为了提高指令的执行效率,往往不是按照程序顺序逐一执行指令的,而是动态的调整指令的顺序,哪条指令就绪就先执行哪条指令,指令是一条一条按照顺序被处理器读取的,但是指令中哪条就绪就会先被执行,而不是完全按照程序顺序执行.这些指令的结果执行的结果会先存入重排序缓冲器(ROB),而不是直接写入寄存器或者主内存,重排序缓冲器会将各个指令的执行结果按照顺序进行提交,即使是执行的顺序不一致,但是执行结果的提交(反映到寄存器和内存中)仍然是按照程序顺序来的.

处理器中的猜测执行

猜测执行:通过提前判读并执行有可能需要的程序指令的方式提高执行速度：当处理器执行指令时(每次5条)，采用的是"猜测执行"的方法。这样可使处理器超级处理能力得到充分的发挥，从而提升软件性能。被处理的软件指令是建立在猜测分支基础之上，因此结果也就作为"预测结果"保留起来。一旦其最终状态能被确定，指令便可返回到其正常顺序并保持永久的机器状态.

例如:处理器会先执行语句5,将值临时存到ROB(ROB，Re-order Buffe,重排序缓存)中,然后判断语句3是否为true,如果为true则直接把值更新到主内存中,否则直接抛弃该值,则可以达到相同的效果,单线程情况下这是没问题的,但是多线程的情况下,先执行语句5,会导致上面语句1和2还未执行完成,数组中的值还是初始值,导致最终返回的sum值是错误的.

public class SpeculativeLoadExample {
    private boolean ready = false;
    private int[] data = new int[]{1, 2, 3, 4, 5, 6, 7, 8};
    public void writer() {
        int[] newData = new int[]{1, 2, 3, 4, 5, 6, 7, 8};
        for (int i = 0; i < newData.length; i++) {// 语句①（for循环语句）
            // 此处包含读内存的操作
            newData[i] = newData[i] - i;
        }
        data = newData;
        // 此处包含写内存的操作
        ready = true;// 语句②
    }
    public int reader() {
        int sum = 0;
        int[] snapshot;
        if (ready) {// 语句③（if语句）
            snapshot = data;
            for (int i = 0; i < snapshot.length; i++) {// 语句④（for循环语句）
                sum += snapshot[i];// 语句⑤
            }
        }
        return sum;
    }
}

存储子系统重排序

主内存(RAM)相对于处理器是一个慢速设备,为了提升效率,处理器并不是直接访问主内存,而是通过高速缓存(Cache)访问主内存的,现在处理器还引入了写缓冲器(store buffer)以提高写高速缓存操作以提高写主内存的效率
v2-d69cecab903313c776b50de1c43050bc_b

一个处理器执行了写操作A、B，但由于某些处理器的写缓冲器为了提高将内容写入高速缓存的效率而不保证写操作结果先进先出，这导致了可能该处理器执行顺序是先A后B,但是其他处理器先感知到了B,后感知到了A操作,这种其他处理器感知顺序不一致就认为发生了存储子系统重排序.

指令重排序的重排序对象是指令,它是对指令的顺序进行调整,而存储子系统重排并非对指令进行调整过,只是感知上发生了顺序被调整.

从处理器的角度来说,读取内存操作的实质是从指定的RAM地址加载数据(通过告诉缓存加载)加载到寄存器,读取内存操作称为load,写内存操作实际将数据存储到指定地址表示的RAM存储单元中,因此写内存操作通常称为sotre.所以内存重排序可能有以下4种可能.

重排序类型	含义
LoadLoad重排序(loads reordered after loads)	一个处理器先后执行两个读内存操作L1和L2,其他处理器对这两个内存的操作感知顺序可能是L2,L1,即L1被重排序到L2之后
StoreStore重排序(Stores reordered after stores)	一个处理器上先后执行两个写内存操作W1和W2,其他处理器对这两个内存操作的感知顺序可能是W2,W1,即W1被重排序到W2之后
LoadStore重排序(Loads reordered after stores)	该重排序指一个处理器上先后执行读内存操作L1和写内存操作W2,其他处理器对这两个内存操作感知顺序可能是W2,L1,即L1被重排序到W2之后
StoreLoad重排序(Stores reordered after loads)	一个处理器先后执行写内存操作W1和读内存操作L2,其他处理器对这两个内存操作感知顺序为L2,W1,即W1被重排序到L2之后

貌似串行语义(As-if-serial Semantics)

重排序并非随意的对指令进行随意调整,而是遵循一定规则,编译器,处理器都会遵守这些规则,从而给单线程程序创造一种假象-指令是按照源代码顺序执行的.这种假象称为貌似串行语义,它无法保证多线程下的正确性.貌似串行语义,存在数据依赖关系的语句不会被重排序,只有不存在数据依赖关系的语句才会被重排序.如果两个操作指令访问同一个变量,且其中一个操作为写操作,那么这两个操作之间就存在数据依赖关系.

数据依赖关系:

类型	示例	说明
写后读(WAR)	x=1;y=x+1;	后一条语句包含前一条语句的执行结果
读后写(RAW)	y=x;x=1;	前一条语句读取了一个变量,后一个语句更新了该变量
写后写(WAW)	x=1;x=2;	两条语句对同一个变量进行写操作

int a = 1; //①
int b = 2;//②
int c = a + b;//③

如上述代码,代码执行时变量c依赖变量a和b,但是变量a和b的执行顺序不影响结果,所以有可能先执行②,再执行①,最后才执行③

单处理器的系统是否会收到重排序的影响?

单处理器只会收到编译期的重排序影响,即静态编译器造成的重排序,不会产生运行期重排序

如何保证内存访问的顺序性

禁止重排序是通过调用处理器提供相应的指令(内存屏障)来实现的,JAVA中即使用volatile关键字,synchronized 关键字都可以实现有序性.

上下文切换

把线程想象是工人,每个工人对产品进行一定时间的装配后,交给另一个工人进行装配,按照规则各个工人轮流操作该产品,这种时间成为时间片,时间片决定了一个现场可以连续占用处理器运行的时间长度.当一个进程中的线程由于其时间片用完或者其自身的原因被迫或主动暂停其运行时,另外个线程可以被线程调度器选中占用处理器开始或者继续其运行.一个线程被剥夺处理器的使用权,另一个线程开始或者继续运行的过程称为线程上下文切换.

线程实际上是以断断续续运行的方式使其任务进展的,这种方式意味着线程切出和切入的时候操作系统需要保存和恢复相应线程的进度信息,即切入和切除那一刻线程所执行任务进行到什么程度了,这进度信息称为上下文.它一般包括寄存器的内容和程序计数器的内容.

从JAVA的角度来看,一个线程在RUNNABLE和非RUNNABLE(BLOCKED,WAITING和TIMED_WAITING)的状态切换的过程就是上下文切换的过程.

上下文切换的分类及原因

自发性上下文切换

java中执行以下方法都会导致自发性上下文切换

Thread.sleep()
Object.wait()
Thread.yield()-可能不生效,是不可靠的
Thread.join()
LockSupport.park()

线程发起了I/O操作或者等待其他线程的锁也会导致线程上下文切换.

非自发性上下文切换

指线程由于线程调度器的原因被迫切除,导致非自发性上下文切换,例如:时间片用完或者其他线程优先级更高的线程需要运行.

JAVA中垃圾回收(GC)动作也可能导致非自发向上下文切换,因为垃圾回收器在执行垃圾回收过程中需要暂停所有应用线程才能完成其工作.

上下文切换的开销

上下文切换的开销包括直接开销和间接开销

直接开销:

操作系统保存和恢复上下文需要的开销,主要是处理器的时间开销
线程调度器进行线程调度的开销(按照一个规则决定哪个线程会占用处理器)

间接开销:

处理器高速缓存重新加载的开销.一个被切出的线程可能在后面会在另一个从未运行过的处理器上运行,那么该处理器需要重新从内存或者通过缓存一致性协议从其他处理器加载到高速缓存中
上下文切换可能会导致一级高速缓存的内容被冲刷(flush),即一级高速缓存中的内容会被写入下一级高速缓存或者主内存RAM当中

线程越多,可能导致的上下文切换的开销也就可能越大,所以需要考虑线程与任务的合理性.

线程的活性故障

导致一个线程处于非RUNNABLE状态的因素除了资源限制之外,还有程序自身的错误或者缺陷,由于资源稀缺性或者程序自身的问题和缺陷导致线程一直处于非RUNNABLE状态或者线程处于RUNNABLE状态但是要执行的任务一直无法进展的现象称为线程活性故障.

常见的线程活性故障:

死锁(Dead Lock):线程X持有资源A的时候等待另一个线程释放资源B,线程Y持有资源B的时候等待线程X释放资源A,导致永远处于非RUNNABLE状态
锁死(Lockout):一直无法获得使线程活跃的条件,导致线程一直沉睡
活锁(LiveLock):线程可能处于RUNNABLE状态,但是线程需要执行的任务一直没有进展
饥饿(Starvation):线程一直无法获得所需的资源使得任务无法进展

总结

参考来源:《JAVA多线程编程实战指南》

Java并发之原子性，可见性，有序性

Java内存访问重排序的研究 - 美团云的文章 - 知乎 https://zhuanlan.zhihu.com/p/28774796