掌握 Android 和 Java 线程原理上,跨平台移动开发工具
顺序性
原子性
前面说过,一个线程对应了一个轻量级进程。而进程之前的切换,是内核采完全公平算法进行切换的,我们无法控制这个过程。所以一个正在运行的线程,可能随时被内核切换,变成非运行状态,一旦我们正在运行的线程发生了切换,就会导致当前线程的执行过程发生中断,这种情况下就会产生线程安全问题。
看一下这样一个简单的函数
int count;
void methodA(){
count = 0;
count = count + 1;
assert count > 1:"产生了线程安全问题";
}
这个简单的函数在多线程并发的情况下,count 就会产生线程安全问题。它再多线程中运行的流程可能如下。
如果函数按照上图的流程执行,就会出现 count 的值为 2 的情况,和我们预期的值不一样,导致程序崩溃。
可见性
想要了解什么是可见性,我们先要了解一点计算机硬件的架构知识。硬件层面将存储体系划分为外存、主存、高速缓存和寄存器,后三者又称为内存。为什么要这样设计呢?因为 CPU 的运行速度是远高于内存的读写速度的,如果 CPU 直接读写内存,就会出现 CPU 要浪费很多时间在等待内存的读写上,这一点和前面提到的 I/O 密集型场景会让 CPU 造成浪费是一样的道理。为了解决这个问题,于是设计了寄存器,高速缓存和主存三种内存存储器,寄存器是 CPU 的工作内存,它的读写速度如果是火箭,高速缓存的读写速度就是汽车,而内存的读写速度就是人走路的速度。
再来说一说高速缓存,它也被称为 Cache,是位于 CPU 与主内存间的一种容量较小但速度很高的存储器,一般分为 L1,L2,L3 三级缓存,在运行速度方面,L1 最快、L2 次快、L3 最慢;容量大小方面,L1 最小、L2 较大、L3 最大,如骁龙 865 的 L2 就是 512KB,L3 是 4MB。
CPU 在读数据会先在最快的寄存器寻找需要的数据,找不到再去 L1,L2,L3 最后到 L4 一次寻找。写数据时,也会先将数据写道寄存器,然后再同步到 L1,L2 或者 L3 中的 Cache,最后再同步到内存中。在这种架构下,多核 CPU 就会产生数据不一致的情况。
为什么会产生不一致的情况呢?以上面双核的架构运行这个函数为例。
int a = 0;
void methodA(){
a = a+1 ;
printf(a);
}
这个函数被 CPU0 中的线程 A 和 CPU1 中的线程 B 同时执行,将两个线程都执行完毕后,a 的值应该是 2,因为被加 1 了两次,但是在这种存储架构下,就会出现 a 的值为 1 的情况。
会出现这个问题的原因就是可见性,CPU0 对 a 的操作,不能让其他的线程立刻可见,所以就出现了线程的安全性问题。
顺序性
为了性能优化,虚拟机和 CPU 都会对指令重排序,这样就会导致我们的程序执行的顺序实际编码的顺序不一致。
这里举一个我们用的非常频繁的例子:单例,来说明顺序性导致的线程安全问题。这是一个双重检查单例模式的实现,在大部分情况下,程序都能正常运行,一旦发生顺序问题,就可以导致程序崩溃。
public class Singleton {
private static Singleton instance;
private Singleton(){
}
public static Singleton getInstance(){
if(instance==null){
synchronized(Singleton.class){
if(instance==null){
instance = new Singleton();
}
}
}
return instance;
}
}
new Singleton 的创建过程分为:分配内存,在内存中初始化 Instance,然 M 的地址赋值给 Instance 这三步,如果这三步的顺序被重排,按照如下执行。
可以看到,如果先把 M 的地址赋值给 Instance 这一步先执行,此时切换了线程 B,线程 B 会判断 instance 不会空,然后返回未初始化的 Singlenton,导致程序崩溃。
通过前面一节的讲解,我们已经知道了产生线程安全的原因,那么如何解决线程安全呢?主要有两个解决方案
确保任何时候,都只能有一个线程进入共享的程序段(临界区)
确保各个线程之间没有共享的资源(临界资源)
互斥或者同步可以实现任何时候,都只有一个线程能进入到临界区,线程本地变量如 LocalThread 可以实现线程间没有临界资源。下面详细介绍一下互斥,同步,线程本地变量这三种实现线程安全的方法。
互斥
这里首先介绍一下实现互斥的几种常用的方式
屏蔽中断
软件实现的锁变量
软件实现的互斥算法
硬件指令
屏蔽中断
屏蔽中断是单核处理器系统中,实现互斥最简单的办法。某个线程进入临界区后立即屏蔽所有中断,屏蔽中断后,CPU 便无法进行线程的切换,没有线程的切换,也就不会导致多个线程进入临界区引起的并发问题,当这个线程离开临界区时,再将中断打开。
但是这个方案有两个明显的缺点
用户进程不能拥有屏蔽中断的权利,如果用户进程拥有屏蔽中断的权利,那么随便一个恶意软件无限屏蔽中断就可以让系
统无响应。所以只有系统进程才能使用这种方式实现互斥。
在多核处理器中,屏蔽中断只能屏蔽自己线程所处的 CPU,而无法屏蔽其他 CPU,这种情况下即使屏蔽也中断,依然还会有其他线程能进入临界区
因为这两个明显的缺点,屏蔽中断并不是一个比较好的互斥的方式
软件实现的锁变量
软件实现的锁变量是很多新手程序员常用的实现互斥的方式。我们经常会在程序中看到通过 boolean 或者 int 类型的变量来实现 if else 的判断,比如当值为 true 时,进入 if 的逻辑,false 时,进入 else 的逻辑。
在前面已经说过,原子性是产生线程安全的原因之一,但是 boolean 或者 int 这些常用的基本类型的赋值操作是不具备原子性的,所以通过软件实现的锁变量用在临界区的互斥上,依然会导致多个线程都能进入临界区产生线程安全问题。
因此,软件实现的锁变量,也不是一个比较好的互斥的方式。
软件实现的互斥算法
比较有名的互斥算法是 Peterson 算法,这里简单的介绍一下这个算法的实现。
int turn;
int flat[2] = {false};
void engerRegion(int threadId){
flag[threadId] = true;
turn = 1 - threadId;
while(flat[threadId] == true&& turn == (1 - threadId)){};
//临界区
……
//退出临界区
flag[threadId] = false;
}
现在有两个线程 P0 和 P1,当 P0 进入到临界区之前,会将 flag[0]置为 true,并将标志位 turn 设置为 1(1-线程号 0),然后通过 while 循环判断另一个线程的 flag 标志是否为 trueflag[1] == true 以及 turn 变量是否等于另一个线程号 turn==1,如果是的话则说明另一个线程在临界区,会进入 while 循环等待,如果不是,则说明另一个线程没在临界区,可以进入临界区。
为什么这个算法能实现互斥呢?有这两种场景
P0 和 P1 同时都在执行这段代码
在这种情况下,线程 P0 将 turn 置为了 1,这个时候线程 P1 又将 turn 置为了 0。当线程 P0 进入 while 判断,对 P0 来说,这个时候 flag[1-线程号]也就是 flag[1] 为 true,但是 turn 却是 flase,不满足 while 循环的条件,所以 P0 会进入临界区。但是 P1 在 while 判断时,flag[0]为 true,并且 turn 为 0,满足 while 的条件,于是会一直循环,直到 p0 退出临界区。
只有一个线程在执行这段代码
在这种情况下,如果是 P0 在执行这段代码,while 循环的判断中,flag[1]是 false,不满足 while 循环的判断,于是 P0 会进入临界区。
可以看到,不管是同时只有一个线程在执行这段代码,还是同时两个线程都执行这段代码,都能保证只有一个线程进入临界区。这个时候会有人问,如果是三个线程,四个线程或者多个线程的情况呢?这就是 Peterson 算法的缺点,它只能满足两个线程的互斥,但是基于 Peterson 衍生出来的 Filger 算法能满足多个线程的互斥,Filger 主要是将 flag 和 turn 进行了扩展,思路都是一样的,这里就不详讲了,它的实现如下。
// initialization
level[N] = { -1 }; // current level of processes 0...N-1
waiting[N-1] = { -1 }; // the waiting process of each level 0...N-2
// code for process #i
for(l = 0; l < N-1; ++l) {
level[i] = l;
waiting[l] = i;
while(waiting[l] == i &&
(there exists k ≠ i, such that level[k] ≥ l)) {
// busy wait
}
}
// critical section
level[i] = -1; // exit section
通过互斥算法可以实现互斥,但是软件实现的互斥在性能上不太好,特别是在大量的并发情况下,通过 while 循环遍历的方式,性能会更差。所以互斥算法也不是比较好的互斥的方式。
硬件指令
屏蔽中断,软件锁变量和互斥算法都不是很好的实现互斥的方式,那么有没有实现互斥的最好的办法呢?有,那就是硬件支持的互斥。
从早期处理器支持的:测试并设置(Test-and-Set), 获取并增加(Fetch-and-Increment),交换(Swap)。到现代处理器才开始支持的:比较并交换(Compare-and-Swap),加载链接/条件存储(Load-Linked/Store-Conditional)。这五种指令都是通过硬件支持的原子操作,通过这五种方式,我们就能比较完美的实现互斥。
硬件指令原子性的原理都是通过 lock 指令将内存总线锁住,以禁止其他 CPU 在本指令结束之前访问内存,内存总线只有一条,并且是独占的,不管多核还是单核,同一时间,只有一个 CPU 能占用总线。
这里详细介绍一下测试并设置(TAS)和比较并交换(CAS),加载链接/条件存储(LL/SC)**这两个硬件指令,因为这两个是用的最多的两个指令。
测试并设置(TAS)
TAS 指令会向某个内存地址(这个内存地址只有 1bit,所以值非 0 即 1)写入值 1,并且返回这块内存地址存的原始值。TAS 指令是原子的,这是由实现 TAS 指令的硬件保证的(这里的硬件可以是 CPU,也可以是实现了 TAS 的其他硬件),我们看一下如何通过 TAS 实现自旋锁。
byte lock = 0 //shared state
void engerRegion(){
//获取锁
while(test_and_set(lock)==1){}
// 临界区代码
……
//释放锁
lock = 0 //release
}
在 while 循环中,通过 test_and_set 对 lock 进行操作,如果 lock 返回值为 1,说明已经有其他线程将 lock 的值设置成了 1,所以会在 while 中不断的循环,知道其他线程退出临界区,将 lock 设置成了 1,这次,这个线程就可以进入临界区,并且重新将 lock 设置成了 1。通过空转循环检测的锁被称为自旋锁,TAS 是 Linux 系统中实现自旋锁最常用的一种方式。
但是 TAS 也有一些缺点
第一点是 TAS 的值非 0 即 1,这就导致通过 TAS 实现的锁只有两种状态,它用来实现互斥是很合适的,但是在一些更复杂的条件判断中,仅仅只通过互斥可能会满足不了要求。
第二个涉及到了 TAS 保证可见性的处理,当 TAS 每次将 lock 写为 1 时,都需要发送缓存一致性协议(缓存一致性协议后面会详细讲)通知其他 Cache lock 值已经失效,而发送协议需要占用总线流量,所以 TAS 在总线流量占用是比较大的。
比较并交换(CAS)
CAS 指通过将某个内存中的值与指定数据进行比较,当数值一样时将内存中的数据替换为新的值,CAS 的逻辑比 TAS 要复杂很多,所以这里通过代码模拟 CAS 的过程。
boolean cas(long lock, long oldValue, long newValue)
{
if(lock != oldValue)
return false;
lock = newValue;
return true;
}
lock 是我们的锁,当他和和指定的值 oldValue 不等时,CAS 返回失败;如果相等时,CAS 成功,将 lock 设置成新值。虽然这里面的步骤很多,但是整个流程由硬件支持的原子性操作。CAS 的汇编指令是 cmpxchg,它的实现如下。
#define LOCK_IF_MP(mp) __asm cmp mp, 0 \
__asm je L0 \
__asm _emit 0xF0 \
__asm L0:
inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
// alternative for InterlockedCompareExchange
int mp = os::is_MP();
__asm {
mov edx, dest
mov ecx, exchange_value
mov eax, compare_value
LOCK_IF_MP(mp) // 如果是多处理器的话,则需要添加 Lock 锁住总线
cmpxchg dword ptr [edx], ecx
}
}
通过 cmpxchg 的汇编可以看到,如果是多处理器情况,会在指令添加 lock 前缀,lock 是对原子性,可见性和顺序性的保证。
Intel 的手册对 lock 前缀的说明如下:
确保对内存的读改写操作原子执行。在 Pentium 及 Pentium 之前的处理器中,带有 lock 前缀的指令在执行期间会锁住总线,使得其他处理器暂时无法通过总线访问内存。但这也会带来昂贵的开销。从 Pentium 4,Intel Xeon 及 P6 处理器开始,intel 在原有总线锁的基础上做了一个很有意义的优化:如果要访问的内存区域(area of memory)在 lock 前缀指令执行期间已经在处理器内部的缓存中被锁定(即包含该内存区域的缓存行当前处于独占或以修改状态),并且该内存区域被完全包含在单个缓存行(cache line)中,那么处理器将直接执行该指令。由于在指令执行期间该缓存行会一直被锁定,其它处理器无法读/写该指令要访问的内存区域,因此能保证指令执行的原子性。这个操作过程叫做缓存锁定(cache locking),缓存锁定将大大降低 lock 前缀指令的执行开销,但是当多处理器之间的竞争程度很高或者指令访问的内存地址未对齐时,仍然会锁住总线。
禁止该指令与之前和之后的读和写指令重排序。
把值数据刷新到内存中。
cmpxchg 只在 Intel 的架构上才支持,ARM 架构并不支持 CAS,所以在 Android 系统上的原子操作并不是通过 CAS 来实现的。
我们接着看一下如何通过 CAS 实现一个自旋锁。
int lock = 0 //shared state
void engerRegion(){
//获取锁
while(cas(lock,0,1)){}
// 临界区代码
……
//释放锁
lock = 0 //release
}
在 while 的条件判断中,lock 会和 oldValue 比较是否相等,如果不等,说明有其他线程将 lock 设置成了 1 并进入了临界区,所以当前线程会通过 while 空循环不断的进行 cas 操作,知道其他线程退出临界区,将 lock 设置成了 0,此时 cas 成功,并将 lock 改成了 1。
CAS 比 TAS 性能更好,是因为它改进了 TAS 中提到的两个缺点
CAS 的可以实现更复杂的条件判断,因为 lock 并不是 byte,所以我们可以设置成任意一个数字代表了其中一个条件
CAS 只有在 cas 成功时,才会将 lock 的值写为期待值,也就是只会写一次值,所以只需要发送一次 MESI 广播,告知其他的 cachelock 已经被改写。
CAS 解决了 TAS 的值非零即一的问题,但也带来了另外一个问题,也就是 ABA 问题。
int lock = 0 //shared state
void method1(){
//获取锁
while(cas(lock,0,1)){}
// 临界区代码
……
//释放锁
lock = 0 //release
}
void method2(){
//获取锁
while(cas(lock,1,0)){}
// 临界区代码
……
//释放锁
lock = 1 //release
}
如果有 1,2,3 三个线程,1 和 2 线程访问 method1,3 线程访问 method2。线程 1 和线程 2 都要访问 method1,但是线程 1 先进入到 method1 的临界区,这个时候 lock 的值是 1,线程 2 由于 cas 失败,会陷入 while 循环阻塞。这个时候线程 3 要访问 method2,并且进入临界区的条件时 lock 值为 1,线程 3 满足进入临界区的条件,但同时将 lock 值改为 1,这个时候线程 2cas 成功了,于是线程 1 和线程 2 这个时候都在临界区,此时就有了线程安全问题。ABA 问题总结起来就是一个值 A 改成了 B,又被改成了 A,但是 cas 检测不出被改动过。
为什么 TAS 没有 ABA 的问题呢?因为 TAS 进入临界区的条件是只有 lock 为零才能进入临界区,其他条件都无法进入临界区,所以它也无法实现上面这种多条件的并发任务。JVM 通过给每个变量添加了版本号,来通过版本是否一致解决了 ABA 问题。
加载链接/条件存储(LL/SC)
为什么要介绍 LL/SC 呢?因为 ARM 平台并不支持 CAS,只支持 LL/SC,所以作为 Android 开发,需要对 LL/SC 能够了解。LL/SC 和 CAS 在理论上是等价的,LL 指令读取一个内存中的数据并存到一个寄存器,然后在寄存器修改这个值,随后用 SC 指令将它写回到原来的内存位置中。如果 LL 在修改值时失败,就代表了 LL/SC 失败,什么情况下 LL 会失败呢?收到 MESI 一致性协议广播时都会修改失败。LL/SC 在 ARM 的汇编指令是 LDREX 和 STREX。
可见性和顺序性
通过互斥可以解决线程安全问题,但是互斥的值是要能保证原子性,可见性和顺序性的,硬件指令是能保证原子性的,但是可见性和顺序性如何保证呢?可见性和顺序性都需要硬件来支持,软件都是无法保证的。
可见性
先说说如何保证可见性,为了解决前面提到的不同的 CPU 中 cache 的值不一样的情况,CPU 都实现了缓存一致性协议,比如 Intel 的缓存一致性协议是 MESI ,缓存一致性协议是 CPU 硬件的组成之一,是 CPU 必须要实现的部分。这里以 MESI 为案例讲解缓存一致性,它由四部分组成
Modified(修改),表示当前 cache 的内容有效,数据已被修改而且与内存中的数据不一致,数据只在当前 cache 里存在
Exclusive(独享),表示当前 cache 的内容有效,数据与内存中的数据一致,数据只在当前 cache 里存在
Shared(共享),表示当前 cache 的内容有效,数据与内存中的数据一致,数据在多个 cache 里存在
Invalid(无效),表示当前 cache 无效
MESI 如何保证一致性呢?比如当某个 CPU 要修改这个 CPU 的 Cache 的某个值时,需要将 Invalid 或者 Modified 指令发送给其他所以的 CPU,告知其他 CPU 的 Cache 中的这个值无效了或者已经被修改了。当某个 CPU 要读取 Cache 中的值时,如果当前值时 Modified 或者 Invalid 的,则需要从主内存重新读取值。
那么问题来了,既然硬件已经有了缓存一致性协议,为什么还会有可见性的问题呢?为什么 java 还需要用 violate 保证可见性呢?
首先 MESI 只是并不是所有的 CPU 架构都支持的,其次 MESI 只保证了 L1 到 L3 的 cache 的一致性,但是为了解决缓存一致性协议导致的 I/O 阻塞问题,CPU 又增加了一个 StroreBuffer,StroreBuffer 并不能保证一致性,为什么要增加 StroreBuffer 呢?
当某个 CPU 修改本地缓存中的一条数据,那么你必须将 Invalid(无效)状态通知到其他拥有该缓存数据的 CPU 缓存中,并且等待确认。等待确认的过程会阻塞处理器,这会降低处理器的性能。因为等待远远比一个指令的执行时间长的多。为了避免这种 CPU 运算能力的浪费,Store Bufferes 被引入使用。处理器把它想要写入到主存的值写到缓存,然后继续去处理其他事情,当所有失效确认(Invalidate Acknowledge)都接收到时,数据才会最终被提交。
这种方案会有一个问题,这个被修改的值在收到失效确认确认前,一直在 StoreBuffer 中,没有提交到 Cache 中,如果这个时候,这个 CPU 想要使用这个值,会发现值还是原来的值,修改并没有成功。为了解决这个问题,CPU 会先从 StoreBuffer 中取值,如果不存在,再重 Cache 中取值,这个的解决方案称为 Store Forwarding,但是这个方案又会产生另外一个 Bug,这个 Bug 会导致顺序性问题。由于篇幅限制,为什么会 Store Forwarding 会产生顺序性问题,就不再这里详细说了,有兴趣的可以去了解一下。
总之,缓存一致性协议并不能保证可见性。所以为了保证可见性,需要采用内存屏障来实现。内存屏障就是在指令前后加入屏障指令,硬件层确保屏障之间的指令具有可见性,如 Load Barrier 和 Store Barrier 即读屏障和写屏障
在指令前插入 Load Barrier,可以让高速缓存中的数据失效,强制从新从主内存加载数据
在指令后插入 Store Barrier,能让写入缓存中的最新数据更新写入主内存,让其他线程可见
顺序性
顺序性也是通过内存屏障来实现的,只要在禁止重排的代码的汇编指令的前后插入内存屏障指令,CPU 和编译器就不会对中间指令进行重排。内存屏障在上面讲过了,所以就不再讲了。
案例分析
讲完了实现互斥的方式,接下来介绍一个通过上面提到的方式实现原子操作的案例:信号量。我在《深入理解Android进程间通信机制》这篇文章中提到过信号量,它是 Linux 的一种 IPC 通信机制,信号量通过 V 和 P 操作来实现对信号量的加 1 和减 1 操作,并且是具有原子性的,它是如何实现原子性的呢?接下来看一下
下面是 Linux 系统中对信号量实现减操作的代码
void down(struct semaphore *sem)
{
unsigned long flags;
raw_spin_lock_irqsave(&sem->lock, flags);
if (likely(sem->count > 0))
sem->count--;
else
__down(sem);
raw_spin_unlock_irqrestore(&sem->lock, flags);
}
可以看到,信号量在 down 操作中,是通过 raw_spin_lock_irqsave 来对 lock 进行加锁,并通过 raw_spin_unlock_irqrestore 来释放锁的。raw_spin_lock_irqsave 由两个部分组成,一个是 spin_lock,一个是 irq,raw_spin_lock 表示自旋锁,irq 表示屏蔽硬件中断。这里只看 raw_spin_lock 的实现。raw_spin_lock 在不同的架构平台有不同的实现,比如 arm 平台就是用 LL/SC 实现的。
define _raw_spin_lock(lock) __raw_spin_lock(&(lock)->raw_lock)
static inline void __raw_spin_lock(raw_spinlock_t *lock)
{
unsigned long tmp;
asm volatile(
"1: ldrex %0, [%1]\n"
" teq %0, #0\n"
" strexeq %0, %2, [%1]\n"
" teqeq %0, #0\n"
" bne 1b"
: "=&r" (tmp)
: "r" (&lock->lock), "r" (1)
: "cc");
smp_mb();
}
可以看到这里用到了 ldrex 和 strex 两个汇编指令,也就是 LL/SC 保证了信号量的原子性。
同步
了解了如何通过互斥来实现线程安全问题,接下来说一说实现线程安全的另一种方式:同步。在大部分人的观点中,互斥都是属于同步的一种特殊情况。可以这么认为,但是这里还是将同步单独拿出来讲,是因为通过非互斥的同步,也是可以实现线程安全的,只要能做到让各个线程彼此协作,先后按照一定顺序访问临界资源就可以了。如何实现按照顺序访问临界资源呢?可以以协程做参考。
协程在前面讲用户空间实现的线程中讲到过,在一个进程对应多个协程的情况下,这些协程虽然都能访问临界资源,但是并没有线程安全问题,因为他们并不是并发的。虽然协程的使用场景也比较有限,但依然也是一种解决线程安全的方法。
除了协程,我们也可以通过如屏障 CyclicBarrier,条件 Condition,让步 yield 等方式,来实现各个线程对临界区的协同访问,避免多个线程同时访问临界资源。
线程本地变量
解决线程安全的第三个办法就是使用线程本地变量,让各个线程之间不存在共享资源,这样也就不存在线程安全问题了。线程本地变量使用的地方很广泛,比如 JAVA 就为我们提供了 ThreadLocal 来实现线程本地变量。先通过一个简单的 demo 看看如何使用 ThreadLocal。
public class ThreadLocalTest {
static ThreadLocal threadLocal = new ThreadLocal();
public static void main(String[] args) {
threadLocal.set(true);
System.out.println("Main ThreadLocal Value = " + threadLocal.get());
new Thread(new Runnable() {
@Override
public void run() {
threadLocal.set(false);
System.out.println("ThreadLocal_1 Value = " + threadLocal.get());
}
}).start();
new Thread(new Runnable() {
@Override
public void run() {
System.out.println("ThreadLocal_2 Value = " + threadLocal.get());
}
}).start();
}
}
评论