Java 利用Map集合计算一个字符串中每个字符出现的次数
前言
CPU 、内存、I/O设备之间的速度差距十分大,为了提高CPU的利用率并且平衡它们的速度差异。计算机体系结构、操作系统和编译程序都做出了改进:
- CPU增加了缓存,用于平衡和内存之间的速度差异。
- 操作系统增加了进程、线程,以时分复用CPU,进而均衡CPU与I/O设备之间的速度差异。
- 编译程序优化指令执行次序,使得缓存能够得到更加合理地利用。
但是,每一种解决问题的技术出现都不可避免地带来一些其他问题。下面这三个问题也是常见并发程序出现诡异问题的根源。
- 缓存——可见性问题
- 线程切换——原子性问题
- 编译优化——有序性问题
CPU缓存导致的可见性问题
可见性指一个线程对共享变量的修改,另外一个线程可以立刻看见修改后的结果。缓存导致的可见性问题即指一个线程对共享变量的修改,另外一个线程不能看见。
单核时代:所有线程都是在一颗CPU上运行,CPU缓存与内存数据一致性很容易解决。
多核时代:每颗CPU都有自己的缓存,CPU缓存与内存数据一致性不易被解决。
例如代码:
public class Test {
private long count = 0;
private void add10K() {
int idx = 0;
while(idx++ < 10000) {
count += 1;
}
}
public static long calc() {
final Test test = new Test();
// 创建两个线程,执行 add() 操作
Thread th1 = new Thread(()->{
test.add10K();
});
Thread th2 = new Thread(()->{
test.add10K();
});
// 启动两个线程
th1.start();
th2.start();
// 等待两个线程执行结束
th1.join();
th2.join();
return count;
}
}
最后执行的结果肯定不是20000,cal() 结果应该为10000到20000之间的一个随机数,因为一个线程改变了count的值,有缓存的原因所以另外一个线程不一定知道,于是就会使用旧值。这就是缓存导致的可见性问题。
线程切换带来的原子性问题
原子性指一个或多个操作在CPU执行的过程中不被中断的特性。
UNIX因支持时分复用而名噪天下,早期操作系统基于进程来调度CPU,不同进程之间是不共享内存空间的,所以进程要做任务切换就需要切换内存映射地址,但是这样代价高昂。而一个进程创建的所有线程都是在一个共享内存空间中,所以,使用线程做任务切换的代价会比较低。现在的OS都是线程调度,“任务切换”——“线程切换”。
Java的并发编程是基于多线程的。任务切换大多数是在时间片结束时。
时间片:操作系统将对CPU的使用权期限划分为一小段一小段时间,这个小段时间就是时间片。线程耗费完所分配的时间片后,就会进行任务切换。
高级语言的一句代码等价于多条CPU指令,而OS做任务切换可以发生在任何一条CPU指令执行完后,所以,一个连续的操作可能会因任务切换而被中断,即产生原子性问题。
例如:count+=1
, 至少需要三条指令:
- 将变量count从内存加载到CPU寄存器;
- 在寄存器中执行+1操作;
- 将结果写入内存(缓存机制导致写入的是CPU缓存而非内存)
例如:
竞态条件
由于不恰当的执行时序而导致的不正确的结果,是一种非常严重的情况,我们称之为竞态条件(Race Condition)。
当某个计算的正确性取决于多个线程的交替执行时序时,那么就可能会发生竞态条件。最常见的会出现竞态条件的情况便是“先检查后执行(Check-Then-Act)”操作,即通过一个可能失效的观测结果来决定下一步的动作。
例子:延迟初始化中的竞态条件。
使用“先检查后执行”的一种常见情况就是延迟初始化。延迟初始化的目的是将对象的初始化操作推迟到实际被使用时才进行,同时要确保只被初始化一次。
Pandas的介绍与基本使用
public class LazyInitRace{
private ExpensiveObject instance = null;
public ExpensiveObject getInstance(){
if(instance == null){
instance = new ExpensiveObject();
}
return instance;
}
}
以上代码便展示了延迟初始化的情况。getInstance()
方法首先判断ExpensiveObject是否已经被初始化,如果已经初始化则返回现有的实例,否则,它将创建一个新的实例,并返回一个引用,从而在后来的调用中就无须再执行这段高开销的代码路径。
getInstance()
方法中包含了一个竞态条件,这将会破坏类的正确性,即得到错误的结果。
假设线程A和线程B同时执行getInstace()方法,线程A检查到此时instance为空,因此要创建一个ExpensiveObject的实例。线程B也会判断instance是否为空,而此时instance是否为空则取决于不可预测的时序,包括线程的调度方式,以及线程A需要花费多长时间来初始化ExpensiveObject实例并设置instance。如果线程B检查到instance为空,那么两次调用getInstance()时可能会得到不同的结果,即使getInstance通常被认为是返回相同的实例。
竞态条件并不总是产生错误,还需要某种不恰当的执行时序。然而,竞态条件也可能会导致严重的问题。假设LazyInitRace
被用于初始化应用程序范围内的注册表,如果在多次调用中返回不同的实例,那么要么会丢掉部分注册信息,要么多个行为对同一组对象表现出不一致的视图。
要避免竞态条件问题,就必须在某个线程修改该变量时,通过某种方式防止其他线程使用这个变量,从而确保其他线程只能在修改操作完成之前或者之后读取和修改状态,而不是在修改状态的过程中。
编译优化带来的有序性问题
有序性是指程序按照代码的先后顺序执行。编译器以及解释器的优化,可能让代码产生意想不到的结果。
以Java领域一个经典的案例,进行解释。
利用双重检查创建单例对象:
public class Singleton{
static Singleton instance;
static Singleton getInstance(){
if(instance == null){
synchronized(Singleton.class){
if(instance==null){
instance = new Singleton();
}
}
}
return instance;
}
}
假设有两个线程A和线程B,同时调用getInstance()
方法,它们会同时发现instance==null
,于是它们同时对Singleton.class
加锁,但是Java虚拟机保证只有一个线程可以加锁成功(假设为线程A),而另一个线程就会被阻塞处于等待状态(假设是线程B)。
线程A会创建一个Singleton实例,然后释放锁,锁释放后,线程B被唤醒,线程B再次尝试对Singleton.class
加锁,此时可以加锁成功,然后检查instance==null
时,发现对象已经被创建,于是线程B不会再创建Singleton实例。
但是,优化后new
操作的指令,将会与我们理解的不一样:
我们的理解:
- 分配一块内存M;
- 在内存M上初始化Singleton对象;
- 然后将内存M的地址赋值给instance变量。
但是优化后的执行路径却是这样:
- 分配一块内存M;
- 将内存M的地址赋值给instance变量;
- 在内存M上初始化Singleton对象。
优化后将造成如下问题:
在如上的异常执行路径中,线程B执行第一个判断if(instance==null)
时,会认为instance!=null
,于是直接返回了instance。但是此时的instance是没有进行初始化的,这将导致空指针异常。
注意,线程执行synchronized
同步块时,也可能被OS剥夺CPU的使用权,但是其他线程依旧是拿不到锁的。
解决如上问题的一个方案就是使用volatile
关键字修饰共享变量instance。
public class Singleton {
volatile static Singleton instance; //加上volatile关键字修饰
static Singleton getInstance(){
if (instance == null) {
synchronized(Singleton.class) {
if (instance == null)
instance = new Singleton();
}
}
return instance;
}
}
目前可以简单地将volatile
关键字的作用理解为:
-
禁用重排序;
-
保证程序的可见性(一个线程修改共享变量后,会立刻刷新内存中的共享变量值)。
小结
本篇博客介绍了导致并发编程bug出现的三个因素:可见性,有序性和原子性。本文仅限于引出这三个因素,后面将继续写文介绍如何来解决这些因素导致的问题。如有不足,还望各位看官指出,万分感谢。
参考:
[1]极客时间专栏王宝令《Java并发编程实战》
[2]Brian Goetz.Tim Peierls. et al.Java并发编程实战[M].北京:机械工业出版社,2016
消息队列rabbitmq的五种工作模式(go语言版本),消息队列RabbitMQ