Java的并发知识体系有两部分组成
Thread、Runnable、ThreadGroup和Future、ExecutorService等对象;通过它们创建、管理线程。其中Future、ExecutorService是位于java.util.concurrent下的Java并发工具包
synchronized和java.util.concurrent.lock下的各种锁
这两部分是组成并发基础工具,第1部分负责创建、管理线程;第2部分实现线程之间的通讯协作。通过这两部分的组合可以实现支持并发的数据结构,比如Java并发工具包中的BlockingQueue
、ConcurrentHashMap
这部分的关键是掌握Java并发工具包,它的效率更高、封装更加便捷。
并发程序设计需要考虑任务的分割、调度执行和结果合并,这已经有相关的算法和模式来支持(比如基于数据分割、基于任务划分,至于通用的模式有Fork-Join、Map/Reduce)。这些算法和模式依赖的底层技术是——线程通讯协作,所以对于并发程序设计大家讨论最多的是锁
Java中的锁有两个实现,传统的synchronized块和java.util.concurrent.lock下的各种锁。其实不仅仅Java,其他语言乃至一些IT系统中都有锁的概念,比如文件锁、数据库的锁。大家的实现也基本上大同小异,只是由于背后有一个计算机科学中的理论支持——PV原语。
小知识:PV原语也叫PV操作,它是1965年由著名的荷兰计算机科学家E.W.Dijkstra提出。老爷爷还贡献过一个以自己名字命名的最短路径算法,还写过一个《GOTO有害论》一篇论文促进了结构化程序设计的发展。为了表彰他的杰出贡献,在1972年被授予象征计算机科学最高荣誉的——图灵奖。
假设我们有一个变量,修改这个变量的操作是一个原子操作比如就是一条CPU指令(事实上也就是一条CPU指令——TSL)。给它起个名字叫信号量吧(带信号的变量)
P操作:S=S-1,若S<0,进程将暂停执行,等待唤醒(Wait)
V操作:S=S+1,若S<=0,将唤醒一个阻塞在S上的进程(Wake)
在并发程序设计对任务分割后需要一种技术手段实现任务之间的协作,这就是同步和互斥。PV原语可以同时解决这两个问题,换句话说锁除了用来实现互斥还可以实现同步(任务之间通讯、协作)。看一下通过PV原语如何解决经典的生产者消费者的问题,这个问题同时涉及到同步和互斥的要求。
表示buffer空(is_empty)和满(is_full)都属于同步;读写buffer的时候需要互斥
buffer满的时候阻塞生产者,唤醒消费者;buffer空的时候阻塞消费者,唤醒生产者;设置变量buffer_mutex用于buffer读写的互斥
buffer默认有一个空闲空间。is_full=0,is_empty=1
生产者
next = product();
P(is_emtpy); //如果“不”为空就阻塞自己
P(buffer_mutex)
put_buffer(next);
V(buffer_mutex)
V(is_full); //已经不是“空”了,唤醒消费者
消费者
P(is_full);//如果“不”为满就阻塞自己
P(buffer_mutex)
next = get_buffer();
V(buffer_mutex)
consumer();
V(is_empty); //已经不是“满”了,唤醒生产者
注意P(is_emtpy)的意义是——如果不为空则阻塞自己;V(is_full)表示如果已经不是空则唤醒消费者。所以这两个变量的意义其实是“通信的状态变量”
在Linux关于它的实现叫futex(fast user-space locking)。它还是一个系统调用,无论什么样的语言在Linux中执行锁相关操作最终都是调用这个函数。一起看一下Java中的体现
public class MainTest implements Runnable {
private int b = 0;
public synchronized void test1() throws InterruptedException {
System.out.print("test1 " + Integer.toHexString(this.hashCode()));
b = 20;
Thread.sleep(1000L);
}
public synchronized void test2() throws InterruptedException {
System.out.print("test2 " + Integer.toHexString(this.hashCode()));
b = 40;
Thread.sleep(1000L);
}
public static void main(String args[]) throws InterruptedException {
MainTest test = new MainTest();
Thread thread = new Thread(test);
thread.start();
test.test2();
}
@Override
public void run() {
try {
test1();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
代码中通过synchronized
实现了test1和test2的互斥,JVM的代码看起来头皮发麻,阅读它的代码实在是一件非常让人作呕的事情。
这里用一种偷懒的方式来研究synchronized
的实现机制,通过strace观察JVM使用的系统调用从而判断synchrionized
的实现(其实JVM中所有的锁都是这种实现)。通过在Linux中执行strace -f -F -o out.txt java MainTest
。
如果没有strace请执行相关命令安装(Ubuntu中是apt-get installs trace),其中-f -F参数执行跟踪每个线程的调用 -o 执行输出结果到文件中。strace是输出第一列是线程ID,第二列是系统调用名、参数以及返回值
在这个输出中最“显眼”的是函数futex,这就是前面说的fast user-space locking。它的函数原型是
看似复杂,其实关键的参数只有三个。
uaddr
是一块用户空间的内存地址,op
存放操作类型,有两种类型:FUTEX_WAIT: uaddr中的值是否为val,如果是则让进程休眠,直到FUTEX_WAKE唤醒或者超时(time-out)。FUTEX_WAKE: 唤醒val个等待在uaddr上进程。
在out.txt中查找test1和test2关键字,关联的线程ID是24817
。
test1是程序最后输出的,它需要等待唤醒,所以在它执行之前一定是在不断的执行FUTEX_WAIT,向上找到“最近一次”的FUTEX_WAIT。
注意到,函数的第一个参数是0x7f978413b954
,这个就是“信号量”所在的内存地址。也就是说24817
和24777
相互竞争的就是“这个变量”。重新看test1输出的上面,果然发现了2477
执行FUTEX WAKE
的代码。
这证明了我们的推断是正确的。
如果我们把synchronized
修改成ReentrantLock
在执行上述的分析动作结果其实是大同小异的。这说明无论“上层”语言如何的封装最后在操作系统这里都会统一变成某个系统调用,从这点上讲“锁”本身上没有性能高低,看你如何合理的使用它。
UNIX很简单。但需要有一定天赋的人才能理解这种简单 ——Dennis Ritchie
不知道有多少人勇敢的问过这样一句话——为什么并发就一定要锁?这句话很傻,但是细想我们很难给出一个答案。这就是反思的力量,反思让我们不再膨胀,反思让我们知道——我们弱智到连愚蠢的问题都回答不出来。
并发设计之所以需要锁是由于CPU无法做到顺序一致、存储一致和原子性。
对于单核CPU每一颗CPU都有多条流水线,可以同时执行“不关联”的多条指令(比如:a=10; b=10可以在多条流水线上执行)。充分利用流水线可以提高CPU的吞吐率,所以高级语言(比如Java)经过编译优化可能会打乱指令的顺序,即便编译器不进行优化,CPU也会在执行指令前进行乱序执行。所以顺序的代码即便在单核CPU上还是可能被乱序执行(前提是不相关的两条语句)。
多核CPU情况更加复杂,两个线程会被两个CPU执行
t1:读(Load)a的变量;写入(Store)b的变量
t2: 读(Load)b的变量;读取(Load)a的变量
执行的时候,t1和t2会被调度到不同的CPU核上执行;对于t1来说load a和store b是不关联的,所以它可能先store b后load a;对于t2来说可能会先load a然后 load b。这就是CPU乱序执行(这里只是举个例子,每个CPU都有自己的乱序规则,Intel的可以参考《Intel® 64 and IA-32 Architectures Software Developer’s Manual》)。
CPU访问数据永远都是先把数据放到Cache然后再读取,这是由于CPU的速度要比内存的速度快很多(如果把一个CPU周期比作1公里那么CPU访问内存就是3个马拉松的距离——3*42公里)。这就导致了两个问题:
单核CPU中Cache和内存的数据一致性
多核CPU中Cache之间的一致性
第2个问题比较容易解决,CPU的设计者们提出来MESI协议,简单来说通过它可以协同多核CPU中的Cache保持一致。由于这不是一篇关于MESI的文章,所以这里不再做详细展开说明。需要补充的一点是,很多CPU为了优化MESI都增加了Store Buffer、Invalidate Queue的部件来降低对Invalid状态写入数据的性能开销,包括现在主流的Intel CPU也是这样的架构。
解决第1个问题需要引入一个新的概念——内存屏障 (Memory Barrier)。这个技术不但能解决Cache和内存一致性的问题而且还能解决乱序执行的问题。这个名词听起来比较抽象,其实它就是三个CPU指令分别实现写屏障(Store Barrier)、读屏障(Load Barrier)和全屏障(Full Barrier)。在Intel的CPU中它们是:
sfence指令为写屏障:把Cache的数据刷新到内存;保证了sfence前后Store(写)指令的顺序,防止Store重排序
lfence指令读屏障(Load Barrier):读不涉及到“写回”一致性,所以只保证了lfence前后的Load(读)指令的顺序,防止Load重排序
mfence指令全屏障(Full Barrier):把Cache的数据刷新到内存;保证了mfence前后Store(写)和Load(读)指令的顺序,防止Store和Load重排序
在Linux中这三个指令对应smp_wmb、smp_rmb、smp_mb这三个函数。
需要注意一点,顺序一致、存储一致是由CPU和操作系统协同完成的而原子性则必须有应用程序(或者说是编程语言)自己完成。
原子性是指多个操作是在一起完成的,每步操作都不可从“总体”中分开去单独执行。CPU提供了CAS指令来实现一些原子操作。需要注意的是,原子性必须是建立在顺序一致和存储一致的基础上的,否则是不可能实现原子操作的。
CPU的CAS指令粒度比较小,只能保证比较、赋值操作的原子性但是无法保证更大粒度资源的原子性。这就需要引入锁,也就是前面我们一直在说的futex,它通过CPU的原子指令实现了PV操作(其实futex的实现要复杂的多)。
总结:CPU和操作系统合作保证了顺序一致、存储一致;操作系统基于此两点实现PV原语(也叫信号量)。应用程序通过信号量来控制进程之间的协作、通讯。这三者是层层递进,不可分割的。
当我们讨论锁其实就是在讨论信号量(PV),而实现信号量必须由底层(CPU和操作系统)实现顺序一致和存储一致
看山是山,看山不是山,看山还是山,最后一个境界——为什么那个被叫做“山”?
欢迎关注公众账号了解更多信息“写程序的康德——思考、批判、理性”
最后分享一个公众账号:JavaQ(分享Java实战技术、职场经历、经验感悟,让抽象难懂的技术通俗易懂)