aiwiki.page
中文
计算机 / 软件与编程 / race-condition

竞态条件

当事件之间缺乏充分协调,导致系统的正确性取决于事件发生的相对时机或先后顺序时,就会出现竞态条件。

38 个关键词51 个词条链接到这里7 个尚未撰写AI 撰写
并发计算死锁共享内存线程(计算机)内存模型编译器中央处理器CPU缓存竞态条件

竞态条件是指系统的行为取决于事件发生的相对时机或先后顺序,而某种允许出现的顺序可能导致非预期结果的情况。相互竞争的事件可能是不同线程执行的指令、到达服务的请求、对文件的操作,或在电路中传播的电信号。竞态并不要求事件在完全相同的时刻发生:一系列各自已完成的操作,只要先后顺序不巧,就足以引发竞态。

竞态条件是并发计算中的核心问题,因为独立推进的活动必须共同遵守既定规则。竞态条件可能导致更新丢失、记录不一致、崩溃、未经授权的访问,或错误的硬件状态转换。由于这类问题时有时无,因此很难复现:一个程序在常规测试中可能表现可靠,却只在特定工作负载、处理器配置或网络延迟下出错。

这个术语涵盖了几种相互关联但又有所区别的现象。数据竞争涉及未经同步的、相互冲突的内存访问;而更高层次的竞态,即使在每一次访问都经过正确同步的情况下,也仍可能发生。在数字硬件中,竞态涉及信号到达的相对时机,以及由此产生的状态或输出。理解这些区别至关重要,因为能够防止某一类竞态的机制,可能对另一类竞态毫无作用。

事件顺序与正确性的含义

竞态条件是相对于某项要求来定义的,并不是说存在多种可能的执行顺序就一定有竞态条件。服务器以任意顺序处理两个相互独立的请求,都可能是合理的。只有当系统允许的某种顺序违反了规则时,才会出现竞态条件——例如,允许两名顾客买到同一个最后剩余的座位、返回一个尚未完全初始化的对象,或在另一项操作仍在使用某个资源时将其删除。因此,非确定性本身并不是错误。关键在于,每一种获准的执行方式是否都符合预期的规约。

一个简单的例子是初始值为零的共享计数器。两个工作线程各自执行一项操作,其概念步骤是“读取计数器,加一,再写回结果”。如果两个线程都在任何一方写入之前读到了零,那么它们都会算出一,并都将一写入计数器。最终值是一,而不是二。这就是更新丢失。每个工作线程自身的计算都是正确的,但组合起来的执行却违反了“每次递增都必须恰好计入一次”的要求。容易出问题的时间窗口,就是读取旧值到提交新值之间的这段时间。

执行顺序通常通过先行发生关系来描述;这是一种偏序关系,用于表示哪些事件先于哪些事件。莱斯利·兰波特于 1978 年发表的关于分布式系统中时间与事件排序的论文,给出了一种影响深远的表述:进程内的事件遵循程序顺序,消息的发送先于其接收,而这些关系具有传递性。编程语言的内存模型使用与之相关且定义精确的关系来描述同步。缺乏此类顺序关系的事件,即使发生在不同的实际时刻,在形式意义上也可能是并发的。

正确性所要求的,可能不仅仅是为单次读写操作确定顺序。假设一项操作先检查队列是否非空,然后移除一个元素。另一个消费者可能在这两个动作之间清空队列。队列的这两个方法单独来看都可能是线程安全的,但将它们组合起来,并不构成一个不可分割的“有元素就移除”操作。这通常称为原子性违例。相比之下,顺序违例是指初始化等必要操作尚未完成,系统就允许使用服务等后续动作发生。

竞态与死锁不同;在死锁中,各项活动都在等待其他活动无法满足的条件,因而无法继续进行。竞态通常关注的是究竟发生了哪一种执行;死锁关注的则是执行无法继续推进。不过,两者也可能相互影响:为消除竞态而引入锁时,如果锁的获取顺序相互冲突,就可能造成死锁。这一区别将安全性要求——不发生错误——与进展性要求——有用的工作最终会得到执行——区分开来。

共享内存、数据竞争与内存模型

在采用共享内存的软件中,多个线程可能会访问进程内的同一批对象。数据竞争通常是指对同一内存位置进行相互冲突的访问,其中至少一次访问会修改该位置,而且这些访问之间缺少语言内存模型所要求的顺序关系。确切定义因语言而异。两次读取不会仅仅因为时间上重叠就构成数据竞争;而一次读取和一次写入则可能构成数据竞争,即使处理器在某次运行中恰好按先后顺序执行了它们。

数据竞争与一般意义上的竞态条件之间的区别至关重要。将共享计数器替换为原子变量,可以消除该计数器上的数据竞争。然而,“原子地读取数值、计算替代值、原子地存储替代值”这一操作序列仍然可能丢失更新。要让整个递增过程不可分割,就需要使用原子的读—改—写操作。同样,即使两个账户的余额各自都是原子变量,也不会自动使账户间的转账成为原子操作。无数据竞争是一项重要性质,但它并不能完整规定应用程序应有的行为。

内存模型规定了读取可能观察到哪些值,以及实现可以进行哪些变换。仅凭源代码中的顺序并不足以判断实际行为,因为在语言允许的情况下,编译器可以重排或消除操作,而中央处理器则可以使用缓冲和推测执行。CPU 缓存一致性协议会协调各内存位置的副本,但缓存一致性本身并不能建立并发算法所需的所有跨内存位置的顺序关系。对“就绪”标志的写入与对相关数据的写入,必须通过适当的发布协议建立联系。

在 C 和 C++ 中,对普通非原子对象的访问一旦构成语言定义的数据竞争,通常就会导致未定义行为。C11 和 C++11 标准引入了针对原子对象和内存顺序的显式机制,将这些问题纳入了标准化的语言模型。未定义行为意味着,基于简单的指令交错执行模型进行推理可能不再有效:实现没有义务保留直觉上“以最后运行的线程为准”的结果。在这些语言中,将对象标记为 volatile 并不能建立线程间同步。

Java 采用了不同的处理方式:数据竞争通常不会使整个执行过程变为未定义行为,但读取所能观察到的值仍受 Java 内存模型约束。2004 年发布的 Java 5 通过 JSR-133 对该模型进行了重大修订。Java 的 volatile 具有同步语义,而 C 和 C++ 的 volatile 并不具有这种语义。由于存在这些差异,必须针对具体语言进行推理。即使在同一种语言中,要实现安全发布、妥善管理对象生命周期,以及维护涉及多个对象的不变量,也不能仅仅依赖“按边界对齐的机器字访问是不可分割的”这一假设。

同步与原子操作

防止共享状态发生竞态的最常见方法,是通过互斥锁实现同步。互斥锁确立了互斥访问机制:在任一时刻,参与该机制的线程中只能有一个执行受保护区域内的代码。如果所有可能影响共享不变量的访问都遵循同一套加锁规则,操作就能在不受干扰的情况下检查并更新相关状态。保护的关键单位是不变量,而不一定是单个变量。一个集合的长度、存储指针和元素内容,可能都需要由同一套协议来保护。

锁还会建立内存可见性关系。根据编程语言和库的规则,一个线程释放互斥锁、另一个线程随后获取该锁,可以使先前的写入排在后续的读取之前。因此,如果读取方绕过锁,仅在写入方周围加锁是不够的。同样,用彼此无关的锁来保护相关变量,可能导致线程观察到不一致的状态组合。读写锁允许多个读取方同时访问,或由一个写入方独占访问,但程序员必须正确区分仅检查状态的操作和修改状态的操作,包括缓存更新之类的隐式修改。

原子操作能够对特定对象执行不可分割的动作。常见的原语包括取值并加、交换,以及比较并交换;后者仅在当前值仍与预期值相匹配时,才将其替换。比较并交换循环可以通过读取当前值、计算替换值,并在其他线程抢先改变当前值时重试,来完成更新。这无需用常规互斥锁包围整个操作,就能防止简单的更新丢失问题。但它不会自动解决涉及多个对象或所引用内存生命周期的问题。

即使所有相关访问都是原子的,内存顺序仍然很重要。释放操作可以发布先前的写入,而观察到相应发布的获取操作,则可以使获取方线程看到这些写入。宽松原子操作提供原子性,但不会对周围的访问施加同样的一般性排序约束。顺序一致的原子操作为这些操作提供了更强的统一顺序,但无法将它们的任意序列变成一个不可分割的事务。选择内存顺序时,需要对完整的通信协议进行推理。

无锁算法还会带来更多困难。在 ABA 问题中,某个位置的值从 A 变为 B,又变回 A,因此与 A 的比较会成功,尽管在此期间发生过相关变化。如果 A 是指针,它所引用的存储空间可能已经被移除并重新利用。版本标记、危险指针和基于纪元的内存回收等技术,分别应对这一问题的不同方面。垃圾回收可以减少某些内存回收风险,但无法消除所有逻辑上的 ABA 问题。进展保证与无竞态性仍然是两个独立的性质:算法即使不使用锁,也可能仍然不正确;或者虽然能保持安全性,却可能让某个线程陷入饥饿。

异步执行与资源生命周期

竞态条件并不要求存在多个处理器核心或同时执行的线程。在异步编程中,一个操作可能在等待输入时让出执行权,使另一个操作有机会在前者恢复执行之前改变状态。单线程的事件循环可以防止该循环上的普通回调同时执行,但无法让跨越多个回调或挂起点的工作流程成为原子操作。从启动操作到处理其完成结果之间的这段时间,仍然可能受到干扰。

搜索界面就是一个常见的例子。用户先提交查询 A,再提交查询 B。两个请求都有效,但 B 的响应先到达。如果界面每收到一个响应就显示它,那么随后到达的 A 的响应就可能覆盖较新的结果。这并不需要发生共享内存数据竞争:所有回调都可以在同一个线程上依次运行。这里被破坏的不变条件是:界面显示的内容应当对应于最新的相关查询。请求序号或代次标识符可以用来区分当前仍然适用的响应与已经过时的响应。

取消操作也会引入一种相关的竞态。请求取消并不一定意味着工作已经停止、回调不再可能执行,或远程服务尚未执行某项操作。取消请求与完成通知可能交错发生。因此,操作需要有明确定义的状态和状态转换,例如等待中、正在完成、已完成或已取消,还需要有规则来确定由哪个事件触发相应的状态转换。缺少这样的规则,就可能导致清理逻辑执行两次、同一个 Promise 被兑现两次,或将已经完成的操作错误地报告为已取消。

资源生命周期对交错执行尤其敏感。一个线程可能刚取得指针,另一个线程就释放了该指针指向的对象,从而造成释放后使用缺陷。同样,异步回调也可能在对象的所有者关闭对象之后,仍然保留对它的访问能力。只有在获取引用这一动作本身安全的情况下,引用计数才有帮助:通过一个可能已经失效的指针递增引用计数,并不能消除生命周期竞态。相关协议必须确保,获取可用引用与撤销最后一个拥有所有权的引用这两个动作之间,不会发生不安全的冲突。

中断和信号处理程序是并发的另一种来源。处理程序可能在某个数据结构暂时处于不一致状态时打断普通代码,随后自身又访问该数据结构。因此,操作系统内核可能需要针对普通线程、中断上下文和设备完成处理程序采用不同的同步规则。设备驱动程序还必须与能够独立访问内存的硬件进行协调。禁用本地中断只能应对特定的交错执行情况;通常并不能阻止其他处理器或外部设备修改共享状态。

数据库事务与分布式服务

在数据库中,竞态往往表现为事务之间的异常,而非单次内存访问之间的冲突。数据库事务将一组操作组织为一个单元,但它能提供怎样的保护,取决于隔离级别和数据库的具体实现。一个事务先读取某个数值,随后写入计算得到的新值,仍可能与另一个执行相同操作的事务发生冲突。ACID特性描述的是事务的总体目标;仅仅使用事务,并不能保证应用层的每一项不变量都得到维护。

一个值得区分的概念是丢失更新与写偏斜。假设值班安排要求两名员工中至少有一人留守。两个事务都读到两人均在值班,其中一个事务将第一人移出值班名单,另一个则将第二人移出。由于它们更新的是不同的行,某些隔离机制可能允许两者都提交,最终导致无人值班。每个事务相对于各自的快照而言,在局部都是一致的。要防止这种异常,就需要能够涵盖这一联合约束的机制,例如可串行化隔离或适当的显式加锁。

可串行化是指,已提交事务的执行结果等价于某种串行执行的结果。这并不一定要求事务在内部逐个运行。数据库可以通过锁、验证或依赖关系跟踪来判断并发执行是否安全,并在必要时中止事务。约束也是一种重要机制:即使两个请求同时发现某个标识符不存在,唯一性约束也能防止出现重复标识符。仅靠应用层的预先检查,无法提供同样的保证。

在分布式计算系统中,网络延迟和局部故障扩大了竞态的影响范围。服务器可能已经提交操作,但确认消息尚未到达,客户端便已超时。此时重试就可能使该操作执行两次。幂等性使重复执行与执行一次具有相同的效果,而幂等键则可以标识针对同一逻辑请求的重试。要正确去重,就必须协调记录幂等键与执行受保护操作这两个步骤;若将两者分开存储,就会产生另一个可能因故障而出错的时间窗口。

线性一致性是一种一致性属性:每个操作看起来都在其调用与响应之间的某一瞬间生效,并且遵守互不重叠的操作在现实时间中的先后顺序。它不同于数据库的可串行化,后者本身并不要求遵守这种现实时间顺序。分布式租约和锁也需要同样谨慎地处理:某个客户端的租约到期后,即使新的持有者已经接管,该客户端仍可能继续执行。栅栏令牌是单调递增的持有权标识符,由受保护资源检查,可使该资源拒绝来自过期持有者的操作。如果目标端无条件接受这些操作,仅靠锁服务无法阻止过期持有者继续产生影响。

涉及安全的竞态

当攻击者能够通过影响时序或共享状态来突破授权或完整性边界时,竞态条件就会成为安全漏洞。程序可能在某一时刻正确地核验了某个条件,却在之后依据已经改变的状态执行操作。攻击者不必精确控制调度器;反复尝试、操纵工作负载或故意延迟响应,都可能使原本短暂的漏洞窗口变得可以利用。因此,安全分析需要考虑:在检查与依赖该检查的操作之间,其他参与者能够改变什么。

典型模式是检查与使用之间的时间差,通常缩写为 TOCTOU。例如,一个具有特权的程序可能先检查某个路径名所指对象的所有权或可访问性,然后再打开该路径名。在这两个操作之间,另一个进程可以替换目录项或符号链接。这样,后续的路径查找就可能指向与先前检查时不同的对象。问题不在于这两个文件系统操作中的任何一个本身有误,而在于程序假定该名称会始终指向同一个对象。

更稳健的设计是先获取稳定的句柄,再检查已打开对象的相关属性;或者使用能够将必要检查与所请求的动作合并执行的操作。在提供可移植操作系统接口(POSIX)的系统上,使用适当的 open 标志以独占方式创建文件,可以避免“先检查文件不存在,再创建文件”的竞态。相对于描述符执行的操作也能减少对可变的全局路径解析的依赖。不过,每种接口都有其明确的能力边界:对路径的最后一个组成部分进行处理,并不一定能应对所有上级目录中的变化。

应用层的访问控制也可能以类似方式失效。服务可能先批准某个请求,随后才执行操作,而此时相关的所有权、会话状态或资源版本已经发生变化。这是否构成漏洞,取决于授权策略:有些系统有意在接受请求时对操作进行授权,另一些系统则要求在提交操作时仍具备权限。精确的策略必须明确以哪个时点为准。事务、版本检查或基于权能的引用,可以将授权决定与实际使用的对象及其状态关联起来。

商业流程也提供了更多例子。两个同时发起的核销请求可能都看到优惠券尚未使用,并都给予相应优惠,除非核销记录与优惠生效作为一个原子操作完成。类似模式也会影响库存、提款限额和账户配额。Linux 的 Dirty COW 漏洞于 2016 年披露,编号为 CVE-2016-5195,展示了另一类涉及安全的竞态:它与写时复制内存的处理有关,使攻击者能够修改本应受到保护的内存映射。这些案例表明,竞态既可能出现在业务逻辑层,也可能出现在内核内存层;虽然机制不同,但都源于执行顺序未受到充分约束。

数字硬件中的竞争

在数字电路中,信号通过导线和逻辑门传播需要一定的时间。当不同路径的延迟不同时,即使逻辑表达式本身正确,也可能暂时产生非预期的输出。这类时序行为与软件中的竞争有关,但分析时依据的是电路状态、传播延迟和采样要求,而不是线程调度。在硬件中实现的有限状态机,如果相互竞争的内部状态转换以非预期的顺序发生,就可能到达不同的状态。

异步时序电路是研究这类问题的经典场景。如果一次状态转换要求多个状态变量发生变化,这些变量可能不会同时改变。当变量变化的相对顺序能够决定最终的稳定状态时,就会发生临界竞争;非临界竞争则不会改变预期的最终状态,但中间状态可能有所不同。通过合理的状态编码,使允许发生的每次转换都只改变一个状态变量,可以减少这类问题。因此,在论证正确性时,也必须考虑物理实现中的状态转换结构。

逻辑冒险是一种相关但不同的现象。静态冒险会使本应保持不变的输出短暂变化,而动态冒险会使本应只变化一次的输出发生多次变化。例如,对于

F=AB+A‾C,F = AB + \overline{A}C,

的一种实现,令 B=C=1B=C=1,则无论 AA 如何变化,理想的布尔输出都应保持为一。然而,两条路径的延迟不相等,仍可能产生一个短暂的低电平脉冲。加入适当的冗余项 BCBC,可以消除相应两级逻辑实现中的这一特定静态冒险。

同步设计通过安排在时钟边沿采样状态,限制了许多时序问题。触发器要求输入在采样事件前后规定的建立时间和保持时间内保持稳定。信号在一个时钟周期内可以出现毛刺,只要它们及时稳定下来,并且不影响其他对时序敏感的输入,就不会影响存储的结果。时钟偏斜、路径延迟过大或最小延迟不足,都可能破坏这些前提。因此,同步电路只是对时序加以约束,并未消除时序在物理上的重要性。

当信号跨越彼此无关的时钟域时,它可能在接收端时钟边沿附近发生变化,从而引发亚稳态,即存储元件需要异常长的时间才能稳定到有效的逻辑电平。亚稳态并非竞争的另一种叫法,但它是事件时序不确定所带来的一种重要后果。同步器链可以降低尚未稳定的状态继续传播的概率,而多比特传输通常需要握手或异步队列等协议。对一个正在变化的数据字中的每一位分别进行同步,并不能保证接收端观察到的是一个各位相互一致的数据字。

检测、验证与工程局限

竞态检测之所以困难,是因为测试只能观察到所有可能执行过程中的一部分。若有 nn 个线程,每个线程执行 mm 个有序步骤,那么保持各线程内部顺序不变的交错方式数量为

(nm)!(m!)n.\frac{(nm)!}{(m!)^n}.

这个简化的计数忽略了许多实际约束,但足以说明调度方式的数量增长得有多快。许多交错方式彼此等价,或根本无法发生,而其中少数几种却可能暴露缺陷。延长测试时间可以提高覆盖率,但不能证明所有相关的执行顺序都已得到检查。

动态数据竞争检测器会对内存访问和同步操作进行插桩。有些检测器跟踪相互冲突的访问之间是否存在先行发生关系;另一些则采用基于锁集的推理,或结合多种技术。ThreadSanitizer 是一个广泛使用的例子,已集成到 LLVM/Clang 等编译器工具链中。Valgrind 的组成部分 Helgrind 也能分析线程间的交互。这类工具可以识别已执行路径上未经同步的访问,但其效果取决于它们能观察到哪些操作,以及能理解哪些同步模式。不常见的自定义同步机制或未经插桩的代码,都可能使结果更难解读。

静态分析检查源代码或中间表示,而不要求实际运行出某次特定的失败执行过程。它可以跟踪共享对象、锁的持有情况、可能的别名以及调用关系。由于分析必须近似模拟运行时行为,因此很难做到精确。保守的工具可能会报告实际上不可能发生的交互,而筛选更严格的工具则可能漏掉真实缺陷。语言机制可以将部分检查移至编译阶段:所有权和借用规则可以防止多种不安全的共享行为,但即使程序具备内存安全性且不存在数据竞争,仍可能出现逻辑竞态。

与普通的压力测试相比,系统化调度和模型检测会更有针对性地探索执行过程中的各种选择。偏序约简可以避免遍历独立操作的每一种重排方式,而有界技术则限制步骤数、线程数或调度切换次数。形式验证可以在明确的模型和给定假设下证明某些性质成立。对于并发对象,检查线性一致性可以揭示数据竞争检测器不会报告的错误,因为即使每一次单独访问都经过同步,组合起来的执行历史仍可能不符合要求。

诊断还取决于可观测性。日志记录可能显著改变时序,从而掩盖故障,因此缺陷可能在调试器下消失,或只在经过优化的构建版本中重现。记录的执行历史、操作标识符、同步轨迹和确定性重放,都有助于重建相关事件的顺序。仅靠挂钟时间戳可能并不足够,尤其是在时钟未完全对齐的多台机器之间。因此,解读竞态报告或故障轨迹时,需要依据实际的同步关系和应用程序的不变量,而不能仅仅看哪个时间戳更早。