天天看点

如何保证线程安全有序性_线程安全问题及产生的原因,原子性、可见性、有序性...

竞态(Race Condition) 是指计算的正确性依赖于相对时间顺序(Relative Timing)或者线程的交错(Interleaving)。根据这个定义可知,竞态不一定就导致计算结果的不正确,它只是不排除计算结果时而正确时而错误的可能。竞态往往伴随着读取脏数据 ( Dirty Read )问题,即线程读取到一个过时的数据、丢失更新(Lost Update)问题,即一个线程对数据所做的更新没有体现在后续其他线程对该数据的读取上。

竞态的两种模式:read-modify-write( 读改写 )和 check-then-act ( 检测而后行动 )。

Read-modify-write( 读改写 )操作,该操作可以被细分为这样几个步骤 :读取一个共享变量的值( read ),然后根据该值做一些计算( modify ),接着更新该共享变量的值 (write )。例如,“++” 就是 read-modify-write 模式的一个实例。“sequenece++”实际上相当于如下伪代码表示的几个指令的组合。

如何保证线程安全有序性_线程安全问题及产生的原因,原子性、可见性、有序性...

一个线程在执行完指令①之后到开始( 或者正在 ) 执行指令②的这段时间内其他线程可能已经更新了共享变量( sequence )的值,这就使得该线程在执行指令②时使用的是共享变量的旧值(  读脏数据 )。接着,该线程把根据这个旧值计算出来的结果更新到共享变量,而这又使得其他线程对该共享变量所做的更新被“覆盖”,即造成了更新丢失。

check-then-act( 检测而后行动 )操作 ,该操作可以被细分为这样几个步骤:读取某个共享变量的值,根据该变量的值决定下一步的动作是什么。例如,if-else 语句就是该模式的一个实例。

从上述分析中我们可以总结出竞态产生的一般条件。设01和 02 是并发访问共享变量V的两个操作 ,这两个操作并非都是读操作。如果一个线程在执行01 期间 ( 开始执行而未执行结束 )另外一个线程正在执行 02 ,那么无论 02 是在读取还是更新 V 都会导致竞态 。 从这个角度来看,竞态可以被看作访问( 读取 、更新 )同一组共享变量的多个线程所执行的操作相互交错(Interleave),比如一个线程读取共事变量并以该共享变量为基础进行计算的期间另外一个线程更新了该共享变量的值而导致的干扰( 读取脏数据 )或者冲突( 丢失更新 )的结果。

对于局部变量(包括形式参数和方法体内定义的变量),由于不同的线程各自访问的是各自的那一份局部变量,因此局部变量的使用不会导致竞态!

原子性

原子(Atomic)的字面意思是不可分割的( Indivisible )。对于涉及共享变量访问的操作,若该操作从其执行线程以外的任意线程来看是不可分割的,那么该操作就是原子操作,相应地我们称该操作具有原子性( Atomicity )。

许多资料都会提及原子操作的定义中的“不可分割”,但是很少有资料会对其含义做进一步的解释。而弄清楚“不可分割” 的具体含义是理解原子性的关键所在。所谓 “不可分割”,其中一个含义是指访问( 读 、写 )某个共享变量的操作从其执行线程以外的任何线程来看,该操作要么已经执行结束要么尚未发生,即其他线程不会 “看到” 该操作执行了部分的中间效果。

在生活中我们可以找到的一个原子操作的例子就是人们从ATM机提取现金:尽管从ATM    软件的角度来说,一笔取款交易涉及扣减户主账户余额、吐钞器吐出钞票、新增交易记录等一系列操作,但是从用户( 我们 )的角度来看 ATM 取款就是一个操作。该操作要么成功了 ,即我们拿到现金( 户主账户的余额会被扣减 ),这个操作发生过了;要么失败了,即我们没有拿到现金。这个操作就像从来没有发生过一样( 当然,户主账户的余额也不会被扣减)。除非 ATM软件有缺陷,否则我们不会遇到吐钞口吐出部分现金而我们的账户余额却没被扣除这样的部分结果。在这个例子中,户主账户余额就相当于我们所说的共享变量,而ATM机及其用户( 人 ) 就分别相当于上述定义中原子操作的执行线程和其他线程。

设01和 02 是访问共享变量 V 的两个原子操作,这两个操作并非都是读操作。那么一个线程执行 01 期间 ( 开始执行而未执行完毕 ),其他线程无法执行 02。也就是说,访问同一组共享变量的原子操作是不能够被交错的,这就排除了一个线程执行一个操作期间另外一个线程读取或者更新该操作所访问的共享变量而导致的干扰 ( 读脏数据 ) 和冲突 ( 丢失更新 )的可能。这就是 “不可分割” 的第二个含义。由此可见,使一个操作具备原子性也就消除了这个操作导致竞态的可能性。

理解原子操作这个概念还需要注意以下两点。

• 原子操作是针对访问共享变量的操作而言的。也就是说,仅涉及局部变量访问的操作元所谓是否是原子的,或者干脆把这一类操作都看成原子操作。

• 原子操作是从该操作的执行线程以外的线程来描述的,也就是说它只有在多线程环境下有意义。换言之,单线程环境下一个操作无所谓是否具有原子性,或者我们干脆把这一类操作都看成原子操作。

总的来说,Java中有两种方式来实现原子性。一种是使用锁( Lock )。锁具有排他性, 即它能够保障一个共享变量在任意一个时刻只能够被一个线程访问。这就排除了多个线程 在同一时刻访问同一个共享变量而导致干扰与冲突的可能,即消除了竞态。另一种是利用处理器提供的专门 CAS(Compare-and-Swap )指令,CAS 指令实现原子性的方式与锁实现原子性的方式实质上是相同的,差别在于锁通常是在软件这一层次实现的,而 CAS 是直接在硬件( 处理器和内存 ) 这一层次实现的,它可以被看作“硬件锁”。

在Java语言中,long 型和 double 型以外的任何类型的变量的写操作都是原子操作, 即对基础类型( long/double 除外,仅包括 byte 、boolean 、short 、char 、float 和 int )的变量和引用型变量的写操作都是原子的。这点由Java语言规范JLS(Java  Language Specification )规定。由 Java 虚拟机具体实现。

对long/double型变量的写操作由于 Java 语言规范并不保障其具有原子性,因此在多个线程并发访问同一 long/double 型变量的情况下 ,一个线程可能会读取到其他线程更新该变量的“ 中间结果”。

尽管如此,Java语言规范特别地规定对于 volatile 关键字修饰的 long/double 型变量的写操作具有原子性。因此,我们只需要用 volatile 关键字修饰清共享变量 value ,就可以保障对该变量的写操作的原子性。volatile 关键字仅能够保障变量写操作的原子性,它并不能保障其他操作(比如read-modify- write 操作和 check-then-act 操作) 的原子性。

Java语言中针对任何变量的读操作都是原子操作。

从原子操作的“不可分割” 特性可知,使一个操作具有原子性就可以消除该操作导致竞态的可能性。因此,我们可以将 read-modify-write 操作和 check-then-act 操作转换为原子操作来消除竞态。

可见性

在多线程环境下,一个线程对某个共享变量进行更新之后,后续访问该变量的线程可能无法立刻读取到这个更新的结果,甚至永远也无法读取到这个更新的结果。这就是线程安全问题的另外一个表现形式:可见性(Visibility)。

如果一个线程对某个共享变量进行更新之后,后续访问该变量的线程可以读取到该更新的结果,那么我们就称这个线程对该共享变量的更新对其他线程可见,否则我们就称这个线程对该共享变量的更新对其他线程不可见。可见性就是指一个线程对共享变量的更新的结果对于读取相应共享变量的线程而言是否可见的问题。多线程程序在可见性方面存在问题意味着某些线程读取到了旧数据(Stale Data),而这可能导致程序出现我们所不期望的结果。

可见性问题与计算机的存储系统有关。程序中的变量可能会被分配到寄存器(Register) 而不是主内存中进行存储。每个处理器都有其寄存器,而一个处理器无法读取另外一个处理器上的寄存器中的内容。因此,如果两个线程分别运行在不同的处理器上,而这两个线程所共享的变量却被分配到寄存器上进行存储,那么可见性问题就会产生。 另外,即便某个共享变量是被分配到主内存中进行存储的,也不能保证该变量的可见性。 这是因为处理器对主内存的访问并不是直接访问,而是通过其高速缓存( Cache )子系统进行的。一个处理器上运行的线程对变量的更新可能只是更新到该处理器的写缓冲器( Store Buffer)中,还没有到达该处理器的高速缓存中,更不用说到主内存中了。而一个处理器的写缓冲器中的内容无法被另外一个处理器读取,因此运行在另外一个处理器上的线程无法看到这个线程对某个共享变量的更新。即便一个处理器上运行的线程对共享变量的更新结果被写入该处理器的高速缓存,由于该处理器将这个变量更新的结果通知给其他处理器的时候,其他处理器可能仅仅将这个更新通知的内容存入无效化队列(Invalidate Queue)中,而没有直接根据更新通知的内容更新其高速缓存的相应内容,这就导致了其他处理器上运行的其他线程后续再读取相应共享变量时,从相应处理器的高速缓存中读取到的变量值是一个过时的值。

虽然一个处理器的高速缓存中的内容不能被另外一个处理器直接读取,但是一个处理器可以通过缓存一致性协议(Cache Coherence Protocol)来读取其他处理器的高速缓存中的数据,并将读到的数据更新到该处理器的高速缓存中。这种一个处理器从其自身处理器缓存以外的其他存储部件中读取数据并将其反映( 更新 )到该处理器的高速缓存的过程, 我们称之为缓存同步。相应地,我们称这些存储部件的内容是可同步的,这些存储部件包括处理器的高速缓存、主内存。缓存同步使得一个处理器( 上运行的线程 ) 可以读取到另外一个处理器( 上运行的线程 )对共享变量所做的更新,即保障了可见性。因此,为了保障可见性,我们必须使一个处理器对共享变量所做的更新最终被写入该处理器的高速缓存或者主内存中( 而不是始终停留在其写缓冲器中 ),这个过程被称为冲刷处理器缓存。并且,一个处理器在读取共享变量的时候,如果其他处理器在此之前已经更新了该变量,那么该处理器必须从其他处理器的高速缓存或者主内存中对相应的变量进行缓存同步。这个过程被称为刷新处理器缓存。因此,可见性的保障是通过使更新共享变量的处理器执行冲刷处理器缓存的动作,并使读取共享变量的处理器执行刷新处理器缓存的动作来实现的。

那么,在Java平台中我们如何保证可见性呢?volatile 关键字所起到的一个作用就是,提示JIT 编译器被修饰的变量可能被多个线程共享,以阻止JIT编译器做出可能导致程序运行不正常的优化。另外一个作用就是读取一个 volatile 关键字修饰的变量会使相应的处理器执行刷新处理器缓存的动作,写一个 volatile 关键字修饰的变量会使相应的处理器执行冲刷处理器缓存的动作,从而保障了可见性。

对于同一个共享变量而言,一个线程更新了该变量的值之后,其他线程能够读取到这个更新后的值,那么这个值就被称为该变量的相对新值。如果读取这个共享变量的线程在读取并使用该变量的时候其他线程无法更新该变量的值,那么该线程读取到的相对新值就被称为该变量的最新值。

可见性的保障仅仅意味着一个线程能够读取到共享变量的相对新值,而不能保障该线程能够读取到相应变量的最新值。

有序性

有序性(Ordering) 指在什么情况下一个处理器上运行的一个线程所执行的内存的访问操作在另外一个处理器上运行的其他线程看来是乱序的 ( Out  of  order )。所谓乱序,是指内存访问操作的顺序看起来像是发生了变化。在进一步介绍有序性这个概念之前,我们需要先介绍重排序的概念。

重排序的概念

顺序结构是结构化编程中的一种基本结构,它表示我们希望某个操作必须先于另外一个操作得以执行。另外,两个操作即便是可以用任意一种顺序执行,但是反映在代码上这两个操作也总是有先后关系。但是在多核处理器的环境下,这种操作执行顺序可能是没有保障的:编译器可能改变两个操作的先后顺序;处理器可能不是完全依照程序的目标代码所指定的顺序执行指令;另外,一个处理器上执行的多个操作,从其他处理器的角度来看其顺序可能与目标代码所指定的顺序不一致。这种现象就叫作重排序(Reordering)。

重排序是对内存访问有关的操作(读和写)所做的一种优化,它可以在不影响单线程程序正确性的情况下提升程序的性能。但是,它可能对多线程程序的正确性产生影响,因为它可能导致线程安全问题。与可见性问题类似,重排序也不是必然出现的。

重排序的潜在来源有许多,包括编译器(在Java平台中这基本上指 JIT 编译器 )、处理器和存储子系统( 包括写缓冲器 Store Buffer 、高速缓存 Cache )。为了便于下面的讲解,我们先定义几个与内存操作顺序有关的术语 。

• 源代码顺序( Source Code ): 源代码中所指定的内存访问操作顺序 。

• 程序顺序( Program Order ): 在给定处理器上运行的目标代码( Object Code ) 所指定的内存访问操作顺序 。尽管Java虚拟机执行Java代码有两种方式 :解释执行 ( 被执行的是字节码 Byte Code )和编译执行 ( 被执行的是机器码 )。为便于讨论,这里仅将目标代码定义为字节码。

• 执行顺序( Execution Order ):  内存访问操作在给定处理器上的实际执行顺序。

• 感知顺序( Perceived Order ): 给定处理器所感知到( 看到 )的该处理器及其他处理器的内存访问操作发生的顺序。

在此基础上,我们将重排序划分为指令重排序(Instruction  Reorder) 和存储子系统重排序两种,如表所示。

如何保证线程安全有序性_线程安全问题及产生的原因,原子性、可见性、有序性...

指令重排序

在源代码顺序与程序顺序不一致,或者程序顺序与执行顺序不一致的情况下,我们就说发生了指令重排序(Instruction Reorder)。指令重排序是一种动作,它确确实实地对指令的顺序做了调整,其重排序的对象是指令。在其他编译型语言( 如 C++ )中,编译器是可能导致指令重排序的:编译器出于性能的考虑,在其认为不影响程序( 单线程程序 )正确性的情况下可能会对源代码顺序进行调整,从而造成程序顺序与相应的源代码顺序不一致。在 Java 平台中,静态编译器( javac )基本上不会执行指令重排序,而 JIT 编译器则可能执行指令重排序。

处理器也可能执行指令重排序,这使得执行顺序与程序顺序不一致。处理器对指令进行重排序也被称为处理器的乱序执行(Out-of order Execution)。现代处理器为了提高指令执行效率,往往不是按照程序顺序逐一执行指令的,而是动态调整指令的顺序,做到哪条指令就绪就先执行哪条指令,这就是处理器的乱序执行。在乱序执行的处理器中,指令是一条一条按照程序顺序被处理器读取的( 亦即 “顺序读取”),然后这些指令中哪条就绪了哪条就会先被执行,而不是完全按照程序顺序执行 ( 亦即 “乱序执行” )。这些指令执行的结果 ( 要进行写寄存器或者写内存的操作 ) 会被先存入重排序缓冲器 ( ROB ,  Reorder Buffer),而不是直接被写入寄存器或者主内存。重排序缓冲器会将各个指令的执行结果按照相应指令被处理器读取的顺序提交 ( Commit ,即写入 ) 到寄存器或者内存中去 ( 亦即 “顺序提交” )。在乱序执行的情况下,尽管指令的执行顺序可能没有完全依照程序顺序, 但是由于指令的执行结果的提交 ( 即反映到寄存器和内存中 )仍然是按照程序顺序来的。 因此处理器的指令重排序并不会对单线程程序的正确性产生影响。

处理器的乱序执行还采用了一种被称为猜测执行(Speculation)的技术。猜测执行技术就好比没有卫星导航时代在陌生地方开车遇到岔路口的情形:虽然我们不确定其中哪条路能够通往目的地,但是我们可以凭猜测( 猜其能够到达目的地 )走其中一条路,万一猜错了 ( 前路不通 ) 可以掉头重新走另外一条路。猜测执行能够造成 if 语句的语句体先于其条件语句被执行的效果,即可能导致指令重排序。例如,对于以下程序中的语句③ ( if 语句 ) 和语句⑤,处理器可能会先逐一读取数组data 中的各个元素,并计算这些元素的和 sum,将其临时存放到ROB中,接着再去读取变量ready的值。如果 ready 的值为true , 那么再将 ROB 中临时存放的 sum 的值写到主内存中( 通过高速缓存 )。相反,如果 ready 的值为 false,那么通过丢弃ROB中临时存放的 sum 的值就可以实现该 if 语句的语句体( 语句⑤ )没有被执行到的效果。虽然,这并不会对单线程程序的正确性产生影响。但是它可能导致多线程程序出现非预期的结果:在writer方法和 reader方法由不同的线程并发执行的情况下,语句⑤先于语句③被执行使得data数组的内容提前被读取,此时数组的内容可能是其初始值([1, 2, 3, 4, 5, 6, 7, 8]),而 reader 方法在源代码中先判断 ready 变量的值再读取 data 数组的目的是希望能够读取到 writer 方法执行线程更新后的数组内容 ( [1, 1, 1, 1, 1, 1,1, 1] )。因此,猜测执行可能使这个多线程程序出现了非预期的结果,即影响了正确性。

如何保证线程安全有序性_线程安全问题及产生的原因,原子性、可见性、有序性...

可见,处理器的指令重排序并不会对单线程程序的正确性产生影响,但是它可能导致多线程程序出现非预期的结果。

存储子系统重排序

主内存(RAM)相对于处理器是一个慢速设备。为了避免其拖后腿,处理器并不是直接访问主内存,而是通过高速缓存( Cache )访问主内存的。在此基础上,现代处理器还引入了写缓冲器 ( Store Buffer,也称 Write Buffer )以提高写高速缓存操作( 以实现写主内存 )的效率。有的处理器( 如 Intel 的 x86 处理器 )对所有的写主内存的操作都是通过写缓冲器进行的。这里,我们将写缓冲器和高速缓存统称为存储子系统,它其实是处理器的子系统。

即使在处理器严格依照程序顺序执行两个内存访问操作的情况下。在存储子系统的作用下其他处理器对这两个操作的感知顺序仍然可能与程序顺序不一致,即这两个操作的执行顺序看起来像是发生了变化。这种现象就是存储子系统重排序,也被称为内存重排序( Memory Ordering)。

指令重排序的重排序对象是指令,它实实在在地对指令的顺序进行调整,而存储子系统重排序是一种现象而不是一种动作,它并没有真正对指令执行顺序进行调整,而只是造成了一种指令的执行顺序像是被调整过一样的现象,其重排序的对象是内存操作的结果。习惯上为了便于讨论,在论及内存重排序问题的时候我们往往采用指令重排序的方式来表述。即我们也会用“内存操作 X 被重排序到内存操作 Y 之后” 这样的表述称呼内存重排序。

从处理器的角度来说,读内存操作的实质是从指定的RAM地址加载数据( 通过高速缓存加载 )到寄存器,因此读内存操作通常被称为Load,写内存操作的实质是将数据( 可能作为操作数直接存储在指令中,也可能存储在寄存器中)存储到指定地址表示的 RAM 存储单元中,因此写内存操作通常被称为 Store。所以,内存重排序实际上只有以下 4 种可能,如表所示。

如何保证线程安全有序性_线程安全问题及产生的原因,原子性、可见性、有序性...
如何保证线程安全有序性_线程安全问题及产生的原因,原子性、可见性、有序性...

内存重排序可能导致线程安全问题。假设处理器Processor 0和处理器 Processor 1 上的两个线程按照如表所示的交错顺序各自执行其代码,其中 data、ready 是这两个线程的共享变量,其初始值分别为 0 和 false。Processor 0上的线程所执行的处理逻辑是更新数据 data 并在此之后将相应的更新标志ready 的值设为 true。Processor 1 上的线程所执行的处理逻辑是当数据更新标志 ready 的值不为 true ( 表示该线程所需的数据尚未被其他线程更新 ) 时无限等待直到 ready 的值为 true,只有在 ready 的值为 true 的情况下才将 data 的值打印出来。

假设Processor 0依照程序顺序先后执行 S1 和 S2,那么 S1 和 S2 的操作结果会被先后写入写缓冲器中。但是由于某些处理器( 比如 ARM 处理器 )的写缓冲器为了提高将其中的内容写入高速缓存的效率而不保证写操作结果先入先出( FIFO , First-In-First-Out ) 的顺序,即较晚到达写缓冲器的写操作结果可能更早地被写入高速缓存,因此 S2 的操作结果可能先于 S1 的操作结果被写入高速缓存,即S1 被重排序到 S2 之后( 内存重排序 )。这就导致了 Processor 1 上的线程读取到 ready 的值为 true 时,由于S1 的操作结果仍然停留在 Processor 0 的写缓冲器之中,而一个处理器并不能读取到另外一个处理器的写缓冲器中的内容,因此 Processor 1上的线程读取到的 data 值仍然是其初始值0。可见,此时内存重排序导致了 Processor 1上的线程的处理逻辑无法达到其预期目标。即导致了线程安全问题。

如何保证线程安全有序性_线程安全问题及产生的原因,原子性、可见性、有序性...

貌似串行语义

重排序并非随意地对指令、内存操作的结果进行杂乱无章的排序或者顺序调整,而是遵循一定的规则。编译器(主要是JIT编译器 )、处理器( 包括其存储子系统 )都会遵守这些规则,从而给单线程程序创造一种假象( Illusion )指令是按照源代码顺序执行的。 这种假象就被称为貌似串行语义( As-if-serial Semantics )。貌似串行语义只是从单线程程序的角度保证重排序后的运行结果不影响程序的正确性,它并不保证多线程环境下程序的正确性。

为了保证貌似串行语义,存在数据依赖关系的语句不会被重排序,只有不存在数据依赖关系的语句才会被重排序。如果两个操作(指令)访问同一个变量(地址),且其中一个操作(指令)为写操作,那么这两个操作之间就存在数据依赖关系(Data Dependency),如表所示。

如何保证线程安全有序性_线程安全问题及产生的原因,原子性、可见性、有序性...

另外,存在控制依顿关系的语句是可以允许被重排序的。如果一条语句(指令)的执行结果会决定另外一条语句(指令)能否被执行,那么这两条语句(指令)之间就存在控制依赖关系(Control Dependency)。存在控制依赖关系的语句最典型的就是 if 语句中的条件表达式和相应的语句体。允许这种重排序意味着处理器可能先执行 if 语句体所涉及的内存访问操作 ,然后再执行相应的条件判断!允许对存在控制依颇关系的语句进行重排序同样也是出于性能考虑。这是因为,存在控制依赖关系的语句( 如 if 语句 ) 会影响处理器对指令序列执行的并行程度。

保证内存访问的顺序性

我们知道硬件和软件的因素都可能导致程序的感知顺序与源代码顺序不一致,而这种不一致可能导致线程安全问题。那么,如何避免重排序导致的线程安全问题呢?这个问题实质上就是如何保证感知顺序与源代码顺序一致,即有序性。

我们知道貌似串行语义只是保障重排序不影响单线程程序的正确性。从这个角度出发,有序性的保障可以理解为通过某些措施使得貌似串行语义扩展到多线程程序,即重排序要么不发生,要么即使发生了也不会影响多线程程序的正确性。因此,有序性的保障也可以理解为从逻辑上部分禁止重排序。当然,这并不意味着从物理上禁止重排序而使得处理器完全依照源代码顺序执行指令,因为那样性能太低!

从底层的角度来说,禁止重排序是通过调用处理器提供相应的指令(内存屏障)来实现的。当然,Java作为一个跨平台的语言,它会替我们与这类指令打交道,而我们只需要使用语言本身提供的机制即可。前面我们介绍的 volatile 关键字、synchronized 关键字都能够实现有序性。