The Wayback Machine - https://web.archive.org/web/20221028225636/https://baike.sogou.com/kexue/d10271.htm

竞争条件

编辑
逻辑电路中的竞态条件。此处∆t1和∆t2表示逻辑单元的延迟。当输入信号A从低变高时,电路将输出持续时间为(∆t1 + ∆t2) − ∆t2 = ∆t1尖峰。

竞争条件,或竞争冒险是指在电子设备、软件或其他系统中,系统的实质性行为取决于其他不可控事件的时间或顺序的情况。当系统存在一个或多个可能的不合期望的行为时,其可能出现错误。

1954年,竞争条件一词已经被使用,例如大卫·霍夫曼的博士论文《时序开关电路的综合》。 [1]

竞争条件尤其会出现在逻辑电路、多线程或分布式软件程序中。

1 电子学编辑

一个典型的例子是,来自同一信号源、沿着不同路径传播的信号输入到一个逻辑门的情况。门的若干输入可以在先后略微不同的时刻改变,以响应源信号的改变。在恢复到符合设计意图的状态之前,输出可能会在短时间内变为错误的状态。某些系统可以承受此类故障;而有的系统可能会迅速偏离其设计行为,例如当该输出被用作包含存储器的其他系统的时钟信号时(实际上,该临时故障将变成永久故障)。

例如,考虑一个二输入与门,在一个输入端输入一个逻辑信号A,在另一个输入端输入它的反相,非A。理论上,输出(A与非A, A AND NOT A)永远不为真。然而,如果当A从假变为真时,A值的变化传播到第二个输入比第一个输入花费更长的时间,那么将会出现一个短暂的时间段,在此期间两个输入都为真,因此门的输出也将为真。[2]

包括卡诺图在内的各种设计技术鼓励设计师在竞争条件引发问题之前识别并消除它们。通常可以添加冗余逻辑来消除某些种类的竞争。

除了这些问题之外,一些逻辑元件可能进入亚稳态,这给电路设计者带来了进一步的问题。

1.1 临界与非临界形式

当内部变量的改变顺序决定了状态机最终所处的状态时,就会出现临界竞争条件。

当内部变量的改变顺序不能决定状态机最终的状态时,就会出现非临界竞争条件。

1.2 静态、动态和必要形式

当一个信号和它的补码组合在一起时,就会出现静态竞争状态。

动态竞争条件指的是只需要一次状态改变但是却出现了多次状态跳变。这是由于门之间的相互作用。它可以通过使用不超过两级的逻辑门控来消除。

当一个输入在小于总反馈传播时间内有两次跳变时,就会出现必要竞争条件。为了消除这种问题,有时使用感应延迟线元件来有效地增加输入信号的维持时间。

2 软件编辑

当应用程序依赖进程或线程的顺序或时序来正常运行时,软件中就会出现竞争条件。与电子产品一样,存在导致无效执行和错误的临界竞争条件。当进程或线程依赖于某个共享状态时,通常会出现临界竞争条件。对处于临界区的共享状态的操作很关键,必须互斥的。不遵守这条规则就有可能破坏共享状态。

C11和C++11标准中定义的内存模型使用术语“数据竞争”来表示在共享内存位置上的、至少有一个为写操作的潜在并发操作导致的竞争条件。包含数据竞争的C或C++程序的行为是未定义的。[3][4]

众所周知,竞争条件很难复现和调试的,因为最终结果是不确定的,取决于干扰线程之间的相对时序。因此,在调试模式下运行、添加额外日志记录或附加调试器(通常称为“海森堡Bug”)时,产品系统中出现的问题可能会消失。因此,最好通过仔细的软件设计来避免竞争条件,而不是试图在以后修复它们。

2.1 例子

作为一个简单的例子,让我们假设两个线程想要将全局整数变量的值增加一。理想情况下,将进行以下操作顺序:

线程1 线程2 整数值
0
读取值 0
增加值 0
写回 1
读取值 1
增加值 1
写回
2

如上所示,最终值为2。但是,如果两个线程同时运行而没有锁定或同步,操作的结果可能是错误的。下面的可选操作序列演示了这种情况:

线程1 线程2 整数值
0
读取值 0
读取值 0
增加值 0
增加值 0
写回 1
写回 1

在这种情况下,最终值是1,而不是预期的2。出现这种情况是因为这里的增量操作不是互斥的。互斥操作是指在访问内存位置等资源时不能中断的操作。

2.2 计算机安全

许多软件竞争条件都与计算机安全相关。竞争条件使攻击者有权访问共享资源并导致使用该资源的其他操作者发生故障,从而导致包括拒绝服务[5]和权限提升在内的后果。[6][7]

一种具体的竞争条件包括检查某个前置条件(例如认证),然后基于这个前置条件进行某项操作,但是在检查和操作的时间间隔内条件却可能被改变。当这种错误存在于对安全敏感的代码中时,就会产生一个称为检查时间到使用时间(TOCTTOU)的安全漏洞。

竞争条件也被有意用来创建硬件随机数生成器和物理上不可克隆的函数。[8]其实现方式使通过设计到节点的路径相同的电路拓扑,并依靠生产制造上的不同随机确定哪些路径将首先完成功能。通过测量生产出来的每个电路的竞争结果的特定集,可以为每个电路生成一份档案并保密,以便以后验证电路的身份。

2.3 文件系统

两个或多个程序在试图修改或访问文件系统时可能会发生冲突,这可能会导致数据损坏或权限提升。[6]一个常用的解决方案是文件锁定。一种更麻烦的补救方法是以一个唯一的进程(守护进程或功能类似的进程)对该文件具有独占访问权,而需要访问该文件中数据的所有其他进程只通过与该进程的进程间通信来访问该文件中的数据。这需要在进程级别进行同步。

文件系统中存在一种不同形式的竞争条件:不相关的程序可能会突然耗尽可用资源,如磁盘空间、内存空间或处理器周期,从而相互影响。没有经过仔细设计来预测和处理这种竞争条件的软件的行为可能会变得不可预测。在一个看起来非常可靠的系统中,这种风险可能会被长期忽视。但是最终可能会累积足够数据或者添加一定的数量的其他软件,则可能严重破坏系统的许多部分。这种情况的一个例子是火星探测器“精灵”在着陆后不久就几乎消失了。一个解决方案是软件在开始一项任务之前请求并保留它需要的所有资源;如果这个请求失败了,那么任务被推迟,避免了许多可能发生故障的地方。或者,这些点中的每一个都可以配备错误处理,或者在继续之前,可以在事后验证整个任务的成功与否。一种更常见的方法是在开始任务之前简单地验证是否有足够的系统资源可用;然而这种方法可能不可行,因为在复杂的系统中,其他正在运行的程序的动作可能是不可预测的。

2.4 建立关系网

考虑一个像IRC这样的分布式聊天网络,在这个网络中,启动信道的用户会自动获得信道操作的权限。如果同一网络不同端的不同服务器上的两个用户试图同时启动相同名称的信道,每个用户各自的服务器将授予每个用户信道操作的权限,因为两个服务器都还没有接收到另一个服务器已被分配该信道的信号。(这个问题已经通过各种IRC服务器实现得到了很大程度的解决。)

在这种竞争情况下,“共享资源”的概念涵盖了网络状态(存在哪些信道,以及哪些用户启动了这些信道并因此拥有哪些权限),每台服务器都可以自由更改,只要它向网络上的其他服务器发送有关更改的信号,以便它们可以更新对网络状态的概念。然而,网络上的延迟使得上述竞争条件可能出现。在这种情况下,通过对共享资源的访问施加某种形式的控制(比如,指定一台服务器来控制谁拥有哪些特权)来避开竞争条件,这意味着将分布式网络转变为集中式网络(至少对于网络操作的这一部分)。

当用非阻塞套接字编写计算机程序时,竞争条件也可能存在,在这种情况下,程序的性能取决于网络链路的速度。

2.5 生命关键系统

生命关键系统中的软件缺陷可能是灾难性的。Thrac-25放射治疗机层导致至少三名患者死亡,数人受伤,其缺陷之一则为存在竞争条件。[9]

另一个例子是由俄亥俄州的第一能源公司(以及其他电力设施)使用的通用能源公司提供的能源管理系统,。报警子系统中存在竞争情况;当三条下垂的电力线同时跳闸时,竞争条件的存在使得系统没有向技术监控人员发出警报,从而使他们误失了发现问题的时机。这个软件缺陷最终导致了2003年北美大停电。[10]通用电气能源公司后来开发了一个软件补丁来纠正以前未发现的错误。

3 计算之外的例子编辑

3.1 生物

神经科学表明,哺乳动物(大鼠)的大脑也可能出现竞争条件。[11][12]

4 工具编辑

存在许多软件工具来帮助检测软件中的竞争条件。它们可以大致分为两组:静态分析工具和动态分析工具。

线程安全分析(Thread Safety Analysis)是一个静态分析工具,用于基于注释的进程内静态分析,最初作为gcc的一个分支实现,现在在CLang中重新实现,支持PThreads。[13]

动态分析工具包括:

  • Intel Inspector,一种内存和线程检查及调试工具,用于提高C/C++和Fortran应用程序的可靠性、安全性和准确性;Intel Advisor,一款基于采样的SIMD矢量化优化和共享内存线程辅助工具,适用于C、C++、C#和Fortran软件开发人员和架构师;
  • 线程消毒剂(ThreadSanitizer),它使用二进制(基于Valgrind)或源代码、基于LLVM的插桩技术,并支持PThreads[14]和Helgrind,一种Valgrind工具,用于检测使用POSIX pthreads线程原语的C、C++和Fortran程序中的同步错误。[14]
  • 数据竞争检测器[15]旨在用Go语言查找数据竞争。

5 基准编辑

有几个旨在评估数据竞争检测工具有效性的参考基准

  • 数据竞争平台(DataRaceBench[16])是一个基准测试套件,旨在系统地和定量地评估数据竞争检测工具,这些工具分析用OpenMP编写的多线程应用程序。

参考文献

  • [1]

    ^Huffman, David A. "The synthesis of sequential switching circuits." (1954)..

  • [2]

    ^Unger, S.H. (June 1995). "Hazards, Critical Races, and Metastability". IEEE Transactions on Computers. 44 (6): 754–768. doi:10.1109/12.391185..

  • [3]

    ^"ISO/IEC 9899:2011 - Information technology - Programming languages - C". Iso.org. Retrieved 2018-01-30..

  • [4]

    ^"ISO/IEC 14882:2011". ISO. 2 September 2011. Retrieved 3 September 2011..

  • [5]

    ^"CVE-2015-8461: A race condition when handling socket errors can lead to an assertion failure in resolver.c". Internet Systems Consortium. Retrieved 5 June 2017..

  • [6]

    ^"Vulnerability in rmtree() and remove_tree(): CVE-2017-6512". CPAN. Retrieved 5 June 2017..

  • [7]

    ^"security: stat cache *very large* race condition if caching when follow_symlink disabled". lighttpd. Retrieved 5 June 2017..

  • [8]

    ^Colesa, Adrian; Tudoran, Radu; Banescu, Sebastian (2008). "Software Random Number Generation Based on Race Conditions". 2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing: 439–444. doi:10.1109/synasc.2008.36. ISBN 978-0-7695-3523-4..

  • [9]

    ^"An Investigation of Therac-25 Accidents — I". Courses.cs.vt.edu. Retrieved 2011-09-19..

  • [10]

    ^Kevin Poulsen (2004-04-07). "Tracking the blackout bug". Securityfocus.com. Retrieved 2011-09-19..

  • [11]

    ^"How Brains Race to Cancel Errant Movements". Discover Magazine blogs. 2013-08-03..

  • [12]

    ^Schmidt, Robert; Leventhal, Daniel K; Mallet, Nicolas; Chen, Fujun; Berke, Joshua D (2013). "Canceling actions involves a race between basal ganglia pathways". Nature Neuroscience. 16 (8): 1118–24. doi:10.1038/nn.3456. PMC 3733500. PMID 23852117..

  • [13]

    ^"Thread Safety Analysis"..

  • [14]

    ^"Helgrind: a thread error detector"..

  • [15]

    ^"Data Race Detector"..

  • [16]

    ^"DataRaceBench"..

阅读 92
版本记录
  • 暂无