谈到锁,离不开多线程,或者进程间的通信。为了更好地从底层原理去了解锁的机制,形成体系化的知识,这篇文章我会从进程间通信底层原理说起,然后介绍一下Java中各种线程通信的实现机制,最后做一个系统的总结。
还记得上次跟你撕逼内存模型的那个人吗,他又来了,并且向你甩出了一堆问题:
1、为什么需要通信
1.1、竞态条件
我们知道,在操作系统中,互相协作的进程之间可能共享一些彼此都能读写的公共存储区,假设两个进程都需要改写这个公共的存储区那么就会产生竞争关系了。
下面举个例子
假设两个进程a和b共享一个脱机目录,脱机目录中有许多槽位,free记录了下一个空的槽位,进程可以往下一个空槽位中写入内容。
进程a准备往下一个空槽位写入内容"test",进程b准备往下一个空槽位写入内容“good”。
我们来分析下极端情况:
可以发现,由于发生了时钟中断,两个进程都往槽位3写入了内容,进程b的内容被进程a的内容覆盖掉了。
像这种由于两个或者多个进程读写某些共享数据,最后结果取决于进程运行的精确时序,称为竞态条件
。
为了避免这种竞态条件
的出现,就需要找出存在这种竞态条件
的程序片段,通过互斥
的手段来阻止多个进程同时读写共享的数据。
1.2、临界区
对共享内存进行访问的程序片段称为临界区
。
为了实现互斥而选择适当的原语是任何操作系统的主要涉及内容之一。后面我们会详细讨论各种实现互斥的手段,这些手段也是实现进程通信或者线程通信的技术基础。
还是以上面的例子来说明,为了避免竞态条件
的产生,我们需要把获取空槽位和往槽位写内容的程序片段作为一个临界区,任何不同的进程,不可以在同一个时刻进入这个临界区:
如上图,进程b试图在a离开临界区之前进入临界区,会进入不了,导致阻塞,通常表现的行为为:进程挂起或者自旋等待。
为了实现这种临界区的互斥,需要进程之间能够像对话一样,确认是否可以进入临界区执行代码,这种对话即进程通信
。有很多经典的处理方法,下面我们就逐个的来介绍。
2、常见的实现进程通信的手段
2.1、忙等待的互斥(自旋等待)
所谓忙等待,指的是进程自己一直在循环判断是否可以获取到锁了,这种循环也称为自旋
。下面我们通过屏蔽中断
和锁变量
的介绍,依次引出忙等待的相关互斥手段方法。
2.1.1、屏蔽中断
如下图,在进程进入临界区之前,调用local_irq_disable
宏来屏蔽中断,在进程离开临界区之后,调用local_irq_disable
宏来使能中断。
CPU只有发生时钟中断或其他中断才会进行进程切换,也就是说,屏蔽中断后,CPU不会切换到其他进程。但是,这仅仅对执行disable的那个CPU有效,其他CPU仍将继续运行,也就是说多核处理器这种手段无效。
另外,这个屏蔽中断是用户进程触发的,如果用户进程长时间没有离开临界区,那就意味着中断一直启用不了,最终导致整个系统的终止。
由此可见,在这个多核CPU普及的时代,屏蔽中断并不是实现互斥的良好手段。
2.1.2、锁变量
上面一种硬件的解决方案,既然硬件解决不了,那么我们尝试通过软件层面的解决方案去实现。我们添加一个共享锁变量,变量为0,则表示可进入临界区,进入之后,设置为1,离开临界区重置为0,如下图所示:
但是由于对Lock的check和set是分为两步,并非原子性的,那么可能会出现如下情况:
也就是说在进程a把Lock设置为1之前,b就进行check和set操作了,也获取到了Lock=0,导致两个进程同时进入了临界区。
这种非原子性的检查并设置锁操作还是会存在竞态条件,并不能作为互斥的解决方案。
接下来我们升级一下程序,为了避免这种竞态条件
,我们让进程间严格轮换的方式去争抢使用Lock的机会。
2.1.3、严格轮换法
所谓严格轮换法,就是指定一个标识位turn
,当turn=0的时候让进程a进入临界区,当turn=1的时候,让进程b进入临界区。以下是实现代码:
1 | // 进程a |
这种方法可能导致在循环中不停的测试turn,这称为
忙等待
,比较浪费CPU,只有有理由认为等待时间是非常短的情形下,才使用忙等待
,用于忙等待的锁,称为自旋锁(spin lock)。
假设现在进程a在临界区里面,并且执行了turn=1,准备把临界区轮换给进程b,但是这个时候进程b正在处理其他事情,那么这个临界区就一直被进程b阻塞了。进程a想重新进入也需要等待。
也就是说,我唱完一首歌,把麦给了你,轮到你唱,这个时候你拿着麦去上厕所了。那么我想唱歌,也只能等到你上完厕所,唱完歌,把麦的使用权交接给我,我才可以继续唱。
你上厕所竟然影响到了我唱歌,就是所谓的临界区外运行的进程阻塞了其他想进入临界区的进程。
看来这种解决方案并不是一个很好的选择。
接下来我们通过一种G.L.Peterson
发现的一种互斥算法来实现互斥功能。
2.1.4、Peterson解法
既然Linus
说了Talk is cheap. Show me the code.
话不多说,我们直接上代码:
1 |
|
算法关键代码是while循环,如果并发执行,当进程0调用完enter_region
之后,变量值如下:
1 | interested[0] = TRUE |
进程1调用完enter_region
后,给turn赋值=1,覆盖了进程0的赋值:
1 | interested[0] = TRUE |
然后进程1发现turn == process
成立,并且interested[other] == TRUE
,然后卡在这里自旋等待,直到另一个进程离开了临界区。
可以看到,这个算法只适用于两个进程间的互斥处理,更多进程就没办法了。
接下来,我们通过一种硬件指令的方式,帮助我们更好的实现互斥。
2.1.5、基于硬件指令
基于硬件指令一般是基于冲突检测的乐观并发策略:先进行操作,如果没有其他进程争用共享数据,操作就成功了,如果产生了冲突,就进行补偿,不断重试。
乐观并发策略需要硬件指令集的发展才能进行,需要硬件指令实现:操作+冲突检的原子性。
这类指令有:
- 测试并设置锁 Test and Set Lock (TSL)
- 获取并增加 Fetch-and-Increment
- 交换 Swap
- 比较并交换 Compare-and-Swap (CAS)
- 加载链接/条件存储 Load-linked / Store-Conditional LL/SC
2.1.5.1、TSL指令
测试并设置锁 Test and Set Lock (TSL),指令格式如下:
TSL RX, LOCK
作用是将一个内存字lock读到寄存器RX,然后将lock设置为一个非0值。
执行原理:执行TSL指令的CPU会锁住内存总线,禁止其他CPU在这个指令结束之前访问内存。
为了使用TSL指令,需要使用一个共享变量lock来协调多内存的访问。lock=0时,任何进程都可以使用TSL指令将其设置为1,并读写共享内存,当操作结束时,进程使用move指令将lock的值重新设置为0。下面是实现的关键代码:
1 | enter_region: |
如果TSL原子操作没有成功,则重新跳转到enter_region
方法循环执行。这个跟Peterson
算法有点类似,不过TSL可以支持任意多个进程的并发执行。**
2.1.5.2、CAS指令
IA64 和 X86 使用cmpxchg指令完成CAS功能。
cas 内存位置 旧预期值 新值
CAS存在ABA问题,可以使用版本号进行控制,保证其正确性。
JDK中的CAS,相关类:
Unsafe
里面的compareAndSwapInt()
以及compareAndSwapLong()
等几个方法包装提供。只有启动类加载器加载的class才能访问他,或者通过反射获取。
硬件指令既可以实现忙等互斥,也可以实现进程挂起阻塞,关键看具体的实现代码,这里使用了JNE指令进行跳转循环等待,后面我们会介绍用TSL指令实现进程挂起阻塞的互斥量。
2.2、睡眠与唤醒(进程挂起)
以上的解法都是可以实现互斥的,但是存在忙等,导致浪费CPU时间的问题,如果同步资源锁定时间很短,那么这个等待还是值得的,但是如果锁占用时间过长,那么自旋就会浪费CPU资源了。另外可能会导致优先级反转问题
:
如下图,进程H优先级较高,进程L先进入了临界区,然后H变到就绪状态,准备运行,现在H开始忙等待。H就绪是L不会被调度到,不会离开临界区,所以H会永远等待下去:
为了不浪费CPU资源,我们可以使用进程间通信的原语sleep
和wakeup
,sleep
造成调用者阻塞,直到其他进程唤醒它。下面我们根据经典的生产者消费者的问题,引出信号量以及阻塞的概念。
2.2.1、生产者消费者问题
如下图,生产者往队列里面生产消息,消费者从队列里面取消息进行消费:
当消息队列满的时候,生产者准备进行睡眠,但还没睡着:
消费者消费了一条消息之后,他认为生产者正在睡觉,准备通知生产者也起床干活生产消息了:
可是这个时候,生产者实际上都还没真正睡着,所以:wakeup信号丢失了!!!
wakeup信号丢失之后,生产者才真正的睡着了,这个时候消费者却不知道生产者睡着了,于是一直在消费消息,知道消息消费完了,消费者自己也睡觉了。最后两个进程都睡着了,世界清静了:
生产者消费者完整代码如下:
1 |
|
怎么解决这种进程之间不同步,导致的死锁问题呢,接下来我们就通过信号量来实现。
2.2.2、信号量
通过使用一个整型变量来累计唤醒次数,以供之后使用。这个变量就是信号量。可以通过以下方式操作这个变量:
- down:可以用sleep来表示,如果此刻信号量大于0,则将其值-1,如果=0,则进入进程进行睡眠;
- up:可以用wakeup来表示,up操作会使信号量+1,如果因为多个进程睡眠而无法完成先去的down操作,系统会选择一个进程唤醒并完成down操作,但信号量值仍是0,取而代之的是睡眠进程数量减1;
检查数值、修改变量值以及可能发生的睡眠或者唤起操作是原子性的。
信号量原理:
检查数值、修改变量值以及可能发生的休眠或者唤起操作是原子性的,通常将up和down作为系统调用来实现;
当执行以下操作时,操作系统暂时屏蔽全部中断:检查信号量、更新、可能发生的休眠或者唤醒,这些操作需要很少的指令,因此中断不会造成影响;
如果是多核CPU,信号量同时会被保护起来,通过使用TSL或者XCHG指令确保同一个时刻只有一个CPU对信号量进行操作。
使用信号量解决进程同步问题代码如下:
1 |
|
如上,每个进程在进入关键区域之前执行down操作,在离开关键区域之后执行up操作,这样就可以确保互斥了。上面的代码实际上是通过两种不同的方式来使用信号量:
mutex
:用于互斥,确保任意时刻只有一个进程能够对缓冲区相关变量进行读写,互斥是用于避免进程混乱锁必须的一种操作;full
和empty
:通过计数,确保事件的发生或者不发生,这两个信号量的用意与mutex不同。
2.2.3、互斥量
如果仅仅是需要互斥,而不是计数能力,可以使用信号量的简单版本:mutex 互斥量。一般用整型表示,通过调用:
mutex_lock
:进行加锁,如果加锁时处于解锁状态(0表示解锁,其他值表示加锁,比1大的值表示加锁的次数),则调用成功;mutex_unlock
:进行解锁。
互斥量可以通过TSL或者XCHG指令实现,下面是用户线程包的mutex_lock
和mutex_unlock
的代码:
1 | mutex_lock: |
以上代码和
enter_region
的区别?
enter_region
失败的时候会始终重试,而这里会调度其他进程进行执行,这样迟早拥有锁的进程会进入运行并释放锁;- 在用户线程中,
enter_region
通过忙等待试图获取锁,将永远循环下去,绝对不会得到所,因为其他线程不能得到运行进行释放锁。没有时钟停止运行时间过长的线程。线程库无法像进程那样通过时钟中断强制线程让出CPU。在单核系统中如果一个线程霸占了CPU,那么该进程中的其他线程就无法执行了。
由于thread_yield
仅仅是一个用户空间的进程调度,所以它运行非常快捷。这样mutex_lock
和mutex_unlock
都不需要任何内核调用,从而实现了在用户空间中的同步,这个过程仅仅需要少量的同步。
有些线程包也会提供mutex_trylock
,尝试获取锁或者失败,让调用方自己决定是等待下去还是使用个替代方法。
2.3、管程
为了能够编写更加准确无误的程序,于是出现了管程(monitor)的概念:
管程
是程序、变量和数据结构等组成的集合,构成一个特殊模块或者软件包,进程可以调用管程中的程序,但是不能在管程之外声明的过程中直接访问管程内的数据结构。
注意:管程是语言概念而C语言不支持它。 下面是pascal语言描述的管程:
1 | monitor example |
管程中任意时刻只能有一个活跃的进程,从而实现了互斥。特定语言的编译器知道如何编译管程,翻译为底层的机器码:当进程调用管程中的程序的时候,改程序的前面几条指令会检查管程中是否有其他活跃的进程,如果有,则挂起当前调用。
管程的互斥由编译器负责决定。 通用做法是使用互斥量
和二进制信号量
。
Java中的synchronized关键字正是基于管程实现的,我们后面会具体介绍。
通过临界区的自动互斥,管程比信号量更容易保证并行编程的正确性。但是管程是编程语言的概念,需要编译器识别并用某种方式对互斥做出保证,C语言就没有管程,所以不能依赖编译器来遵守互斥规则。
2.4、消息传递
无论是通过硬件指令,还是信号量阻塞,或者管程,都是设计用来解决一个或者多个CPU上的互斥问题的。但是在分布式系统中农,不同服务器的CPU有自己的私有内存,通过网络相连,这些原语就会失效了。所以需要其他方式来实现进程间的通信,最常见的就是消息传递
。
2.5、屏障
这个是专门给进程组而不是进程间实现同步的。
有写程序中划分了若干阶段,并且规定,除非所有进程都准备就绪着手下一个阶段,否则任何进程都不能进入下一个阶段,可以在每个阶段结尾安装屏障来实现这种行为,当一个进程达到屏障的时候,就会被屏障阻拦,直到所有进程都达到该屏障为止。
第2节内容主要提炼于《现代操作系统》一书,并添加了一些辅助理解的图片,给枯燥的描述添加一点趣味儿。
3、常见的Java线程实现通信的手段和原理
线程通信是建立在线程模型之上的,我们首先来讲一下Java的线程模型。
关于Java线程采用的线程模型
注意:上面说的互斥量实现,是
用户线程包
中的实现,所以不需要内核调用。而Java中的互斥量会有所不同,还是需要进行系统调用,由用户态切换到内核态。JVM规范未指定Java线程需要用哪种线程模型。
常见线程实现方式有以下几种:
使用内核线程实现
内核线程(KLT
, Kernel-Level Thread)是直接由操作系统内核支持的线程,内核完成线程切换,内核通过操纵调度器对线程进行调度,并负责将线程的任务映射到各个处理器上。
各种线程操作,如创建、析构及同步,都需要进行系统调用
,需要在用户态
和内核态
中来回切换。
程序通过内核线程的高级接口:轻量级进程(LWP
, Light Weight Process)操作内核线程。他们之间的关系如下:
每个轻量级进程
都需要有一个内核线程
的支持,因此轻量级进程要消耗一定的内核资源如内核线程的栈空间,所以一个系统能够支持的轻量级进程的数量是有限的。
内核线程相当于内核的分身,这样可以内核同时处理多件事情,支持多线程的内核叫多线程内核。
使用用户线程实现
我们上面将的互斥量的实现,即使基于用户线程的。用户线程建立在用户控件的线程库上,系统内核感知不到线程的实现。线程的创建、同步、销毁和调度都是在用户态中进行,无需内核帮助。
缺点:没有内核的帮忙,线程操作,线程阻塞同步处理起来是很麻烦的事情。
使用用户线程+轻量级进程混合实现
Java线程的实现
JVM规范并没有限定Java线程需要那种模型,对于Windows和Linux版本使用的是1:1的线程,映射到轻量级进程中。
3.1、synchronized关键字
通过使用synchronized
,可以实现任意大语句块的原子性单位,使我们能够解决volatile无法实现的read-modify-write
问题。底层命令可以参考我这篇文章:2.3、同步操作Synchronized
**Java中的synchronized
关键字也是通过管程实现的,保证了操作单原子性和可见性。**在同一类中的synchronized方法,同一时刻只能有一个线程在调用。
3.1.1、synchronized锁特点
3.1.1.1、锁升级
管程通用做法是通过互斥量实现的,这会导致线程挂起阻塞,这种传统的锁称为重量级锁
。在JDK1.6之后引入了轻量级锁
和偏向锁
的概念。为此,存在一个锁升级的过程。
对象头中记录了对象的锁类型,我们再来回顾一下对象的内存布局:
我们先来介绍下轻量级锁和偏向锁。
轻量级锁
之所以叫轻量级锁
,是与互斥量导致线程挂起阻塞这种重量级锁
对比的叫法,没错,我就是比互斥重量级锁轻巧多了。
**从未锁定到轻量级锁定的过程还是有点繁琐的,涉及复制Mark Word
,CAS
指定锁记录,指定失败的情况下可能还需要膨胀为重量级锁
;在释放锁的时候会CAS
替换Mark Word
,替换失败则说明有其他线程在等待获取锁,这个时候在释放锁的同时需要唤起其他线程。**我整理了一个图,方便更加直观的观察到这个过程Mark Word
的变化:
偏向锁
所谓偏向锁,就是在数据无竞争的情况下,消除同步原语,进一步提高运行性能。
轻量级锁
在无竞争情况下使用CAS消除同步使用的互斥量,偏向锁
在无竞争的情况把整个同步都消除了,更加轻量级。
为什么叫偏向锁
,以为偏心呀,老是偏袒第一个获取到他的线程。如果接下来的确没有其他线程竞争,那持有偏向锁的线程就永远不需要再进行同步了。
如果开启了偏向锁(JDK1.8默认是开启的),那么当锁对象第一次被线程获取的时候,虚拟机就会尝试设置为偏向锁模式:
一旦有其他线程竞争,那么偏向模式就结束了。变为未锁定或者轻量级锁的状态。他们之间的升级关系如下图所示:
3.1.1.2、锁优化
为了提高synchronized的性能,HotSpot虚拟机团队在JDK 1.6版本花费了大量精力进行锁优化,包括:
自旋锁
:为了避免互斥量频繁进行内核态切换带来的压力,引入了自旋锁。默认会自旋10次试图获取锁,可以使用参数设置:-XX:PreBlockSpin
;自适应自旋锁
:如果一个锁自旋很少成功,那么获取这个锁可能会去掉自旋阶段;如果自旋获取成功概率比较高,那么运行自旋等待持续时间相对更长;锁消除
:这是即时编译器
干的活,一般通过逃逸分析
的数据支持进行锁消除
,一般程序员都不会直接在单线程代码中显示的使用锁,但是有时候虽然只有一行代码:- str = “a” + “b” + “.”
- 但是在JDK5之前底层是翻译为了StringBuffer的append()操作,该方法是包含
synchronized
锁的,所以这种情况及时编译器还是会进行锁消除。
锁粗化
:如果一些列连续的锁操作都是反复对同一个对象的加锁和解锁,并没有线程竞争,那么这个时候为了优化性能,会扩大锁的范围。
当然,上面提及的锁升级,也是锁优化的一种手段。
3.1.1.3、可重入
对于同一个锁,如果一个线程成功进入了临界区,那么该线程在持有锁的同时,可以反复进入该锁。synchronized锁的对象头markword会记录该锁的线程持有者和进入锁的次数的计数器。
每退出一个synchronized方法块,计数器就-1,直到0的时候就释放锁。
3.1.1.4、悲观锁
为什么说它是一把悲观锁呢,因为假设有一个线程获取到了锁,那么其他尝试获取锁的线程只能等待,于是悲观的去睡觉了,等到别人叫醒之后才重新去竞争获取锁。
3.1.2、synchronized锁使用场景
3.2、理清各种锁的分类
我们在各种文章书籍里面可能会看到对锁的各种分类,都是什么意思呢?现在我们就通过简短的描述来解释下,让大家有个形象的认识。
3.2.1、乐观锁和悲观锁
乐观锁
乐观锁总是很乐观的认为不会有太多人会抢占锁,所以一般不会先进行加锁,等到出了问题之后再处理。典型的实现如CAS。
对于乐观锁,可能如果发现的确出现了问题,一般会通过自旋,或者直接放弃等的方式进行处理。
锁以乐观锁适用于并发写入少,大部分是读的场景。这样就可以提高加快自旋的成功率了。
悲观锁
悲观锁就是很悲观的认为会有很多人想占用这个锁,悲观锁为了保证自己可以拿到锁,一上来就尝试锁定,如果锁不住,那就放弃了,直接睡觉去了,也就是线程挂起,等到下次有人叫他起床的时候,才会重新参与到锁的竞争中来。
对于竞争比较激烈,临界区消耗比较多的时间的场景,比较适合悲观锁。不管临界区消耗多长的时间,也不会加大互斥锁的开销。
3.2.2、自旋锁和阻塞锁
自旋锁
这个概念,详细看完上文的你应该比较了解了,就是获取锁失败之后,循环重试。
阻塞锁
这个概念,详细看完上文的你应该比较了解了,就是获取锁失败之后,挂起线程。
3.2.3、共享锁和排他锁
共享锁
又称读锁,既然共享了,那么就不能随便删除和修改了。不然人家好端端的看着你up给他的Java教学视频,突然下一秒变成了动画片,叫人家怎么能接受呢?
排它锁
跟共享锁不一样,排他锁就是一旦获取到了他之后,其他线程就再也不能获取到了。既然别人获取不到了,那么获取到排他锁的我就可以随意的进行修改内容了。
3.2.4、可重入锁
可重入锁
这个比较容易理解,我们在上面讲synchronized的时候已经介绍了。
可重入锁在反复多次使用同一个锁的场景下,避免了死锁的发生。
3.2.5、公平锁和非公平锁
公平锁
公平锁,就是完全按照请求顺序来分配的锁,保证了对所有线程公平。
非公平锁
跟公平锁不一样,是不完全按照请求顺序来处理的。
Java并发包中的
ReentrantLock
锁就提供了非公平锁和公平锁的实现。
为什么要有公平锁呢?设想一下,我们到银行办理业务取票了,如果不管发生什么情况,完全按照顺序来办理,这就是公平锁。
但是轮到一个号之后,假如那个号的人刚好去外面买东西了,如果大家要继续等它回来办理,就会很花时间,于是索性让人去抢柜台窗口,先抢到的人就先办理,如果连续两次都抢位失败了,那么我们就把这个人放入排队队列,等到抢到窗口的人办理完了业务,再轮流叫唤他们,这就是非公平锁。
但是如果窗口的那个人办理业务的时间很久,突然叫一大波人冲上来抢窗口,是抢不到的呀,也就是说对于业务执行时间很长的场景,非公平锁其实效率并不高。
很明显,公平锁吞吐量小,但可以保证每个线程在等一段时间总有机会执行;
而非公平锁吞吐量更大,但是可能有些线程会长时间得不到执行。
3.2.6、可中断锁和不可中断锁
可中断锁
可以响应线程中断的锁,如ReentrantLock.lockInterruptibly()。
不可中断锁
不可以响应线程中断的锁,如ReentrantLock.lock()。
其实Java并发包中针对不同的使用场景,也提供了很多的锁,我们可以直接拿来用。关于其实现思路,由于篇幅所限,我打算后面单独放到一篇文章中讲解,包括实现原理,使用场景等。相信有了本文这些底层知识之后,在看其他顶层的实现,都会得心应手点。
4、结语
好了,我们今天就讲到这里了,能够看到这里的朋友们是真的很热爱技术,想对你们说:加油,大家都是最棒的!!!
本文为arthinking基于相关技术资料和官方文档撰写而成,确保内容的准确性,如果你发现了有何错漏之处,烦请高抬贵手帮忙指正,万分感激。
大家可以关注我的博客:itzhai.com
获取更多文章,我将持续更新后端相关技术,涉及JVM、Java基础、架构设计、网络编程、数据结构、数据库、算法、并发编程、分布式系统等相关内容。
如果您觉得读完本文有所收获的话,可以关注我的账号,或者点个赞。码字不易,你的支持很重要。
关注我的公众号,及时获取最新的文章。
References
《现代操作系统》
《深入理解Java虚拟机:JVM高级特性与最佳实践》