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

条件变量

条件变量是一种同步原语,通常与互斥锁配合使用,让线程高效等待共享状态满足指定条件。

21 个关键词7 个词条链接到这里2 个尚未撰写AI 撰写
同步(计算机)线程(计算机)互斥锁并发计算原子操作队列(数据类型)伪代码临界区条件变量

条件变量是一种同步(计算机科学)原语,允许线程暂停执行,直到涉及共享状态的某个条件可能已经成立。它通常与互斥锁配合使用:互斥锁保护共享状态,条件变量则让线程能够等待状态变化,而不必反复检查该状态。等待操作以原子方式释放互斥锁并开始等待;在等待操作正常返回之前,线程会重新获取互斥锁。收到通知并不代表条件一定成立,因此线程必须再次检查条件。

用途与基本模型

在并发计算中,仅有互斥往往还不够。线程可能安全地获取了锁,却发现自己还不能继续执行:例如,队列为空、缓冲区已满,或者某项操作仍在进行。

持续检查状态是否变化会浪费处理器时间。持有互斥锁时进入休眠,又可能阻止其他线程做出所需的状态变更。条件变量通过协调互斥锁的释放与等待状态的进入,同时解决这两个问题。

通常的编程模型由三个要素组成:

  • 共享状态,例如队列和关闭标志。
  • 互斥锁,用于保护对该状态的访问。
  • 谓词,即基于该状态的布尔表达式,用于决定线程能否继续执行。

例如,消费者可能等待谓词“队列非空,或者已请求关闭”成立。

条件变量通常不会存储或求值这个谓词。虽然它的名称中带有“条件”,但条件本身属于程序的数据和逻辑。一个条件变量可以支持多个谓词,不过使用不同的条件变量可以让通知更有针对性。

基本操作

各接口有所不同,但大多数都提供以下操作。

操作 含义
等待(wait) 释放关联的互斥锁并暂停执行;在正常返回之前重新获取互斥锁。
通知一个线程(notify one),或发送信号(signal) 解除某个等待线程的阻塞,具体效果取决于接口的确切保证。
通知所有线程(notify all),或广播(broadcast) 解除当前在该条件变量上等待的所有线程的阻塞。
限时等待(timed wait) 等待,直到收到通知、到达截止时间或超时时限,或者出现其他允许返回的情况。

这里的**信号(signal)**指条件变量通知,而不是操作系统信号。

通知通常只是使线程具备运行资格,并不保证它立即执行。按照当今大多数接口采用的语义,被唤醒的线程仍须获取互斥锁,并且可能需要与其他线程竞争。

原子释放与等待

等待操作最重要的保证是:相对于相关同步操作,释放互斥锁与进入等待是以原子方式协调完成的。

如果没有这一保证,就可能出现以下执行顺序:

  1. 消费者发现队列为空。
  2. 消费者释放互斥锁。
  3. 生产者添加一个元素并发送通知。
  4. 通知发出之后,消费者才开始休眠。

这样一来,即使队列中已有可用元素,消费者仍可能一直休眠。正确使用条件变量可以消除这一间隙:在等待线程释放互斥锁之后才获取该锁并改变状态的线程,无法像上述情形那样,将通知插入锁的释放与等待线程登记等待之间。

这是同步协议提供的原子性保证,并不一定对应单条硬件原子操作指令。

在循环中等待

标准的等待模式如下:

lock(mutex)
while not predicate(shared_state):
    wait(condition, mutex)

perform_operation_on_shared_state()
unlock(mutex)

必须使用循环,原因有两个,而且彼此独立。

首先,许多接口允许出现**虚假唤醒**:等待操作可能在没有应用程序能够识别的对应通知时返回。

其次,即使确实收到了通知,也不意味着所需状态会为某个特定的等待线程保留。例如,生产者可能添加一个元素并唤醒一个消费者,但另一个消费者可能先获取互斥锁并取走该元素。被唤醒的消费者随后就必须再次等待。

因此,在通常的语义下,即使某个实现从不产生虚假唤醒,将 while 替换为 if 仍会使代码出错。

有些库提供接受谓词参数的等待操作。从概念上说,这种操作会在内部执行上述循环;它并没有消除保护和重新检查谓词的必要性。

示例:有界生产者—消费者队列

有界队列(数据类型)可以说明,为什么一个互斥锁可能与多个条件变量配合使用。生产者等待空余容量,消费者等待可用元素。

以下伪代码假定容量为正、不设关闭机制,并且各项操作都能完成而不抛出异常:

shared:
    queue
    capacity
    mutex
    not_empty
    not_full

put(item):
    lock(mutex)
    while queue.size == capacity:
        wait(not_full, mutex)

    queue.push(item)
    notify_one(not_empty)
    unlock(mutex)

take():
    lock(mutex)
    while queue.is_empty():
        wait(not_empty, mutex)

    item = queue.pop()
    notify_one(not_full)
    unlock(mutex)
    return item

互斥锁既保护队列,也保护由队列状态导出的谓词。每次等待都会释放同一个互斥锁,使其他线程得以改变状态。

两个条件变量区分了不同的等待原因。如果只使用一个条件变量,并且每次只通知一个线程,那么通知可能选中一个谓词仍不成立的线程,而不是能够继续执行的线程。广播可以解决这种选择问题,但可能造成不必要的唤醒。

关闭协议会增加另一种状态转换。例如,消费者可以在队列为空且队列仍开放时等待。关闭队列时,通常需要通知所有受影响的等待线程,让它们都能观察到新状态。

通知与持久状态

条件变量并不是用来保存通知的队列。如果没有线程正在等待,通知通常不会产生持久效果。

这并不意味着线程必须先开始等待,有用的工作才能到来。正确编写的代码会先检查持久存在的共享状态。如果生产者在消费者启动之前就添加了元素,消费者会发现队列非空,从而不进入等待。

当同步协议使线程错过相关变化,并在不该休眠时进入休眠,就发生了唤醒丢失。常见原因包括:

  • 在未持有所需锁的情况下检查谓词。
  • 在缺少必要同步的情况下修改谓词所依赖的状态。
  • 将锁的释放与等待操作分开。
  • 将通知当作会被保存的事件记录。

在常规设计中,检查谓词和更新使谓词发生变化的状态,都使用同一个互斥锁。一些更专门的设计会将条件变量与原子操作结合使用,但这些设计需要单独论证其正确性;仅仅将一个标志设为原子变量,并不能消除检查与等待之间的所有间隙。

在锁内还是锁外通知

是否必须持有锁才能发送通知,取决于具体接口。有些接口要求持有关联的锁;另一些则允许在解锁之后通知。

如果接口允许这两种方式,那么只要谓词更新经过适当同步,且对象生命周期得到安全管理,两种位置都可能是正确的。解锁之后再通知可能减少即时的锁竞争,但这并不是普遍适用的优化。正确性取决于状态管理协议,而不只是通知的位置。

与其他同步机制的关系

互斥锁与管程

互斥锁控制对临界区的进入。条件变量则控制因状态条件而产生的等待。二者解决的是互补的问题:条件变量本身并不提供互斥。

条件变量与管程密切相关。管程是一种将受保护的状态、互斥执行的操作和条件等待结合在一起的抽象。有些语言通过类似管程的对象提供条件变量,而不是将其作为独立分配的原语。

信号量

信号量维护一个计数。即使当前没有线程等待,释放信号量也可以留下一个许可,供后续获取操作使用。

条件变量通常没有对应的许可计数。资源是否可用必须体现在共享状态中,被唤醒的线程必须重新判断。两种机制都能实现生产者—消费者协调,但它们的不变量和通知行为并不相同。

忙等待与自旋锁

自旋锁通过反复尝试获取锁来等待。条件变量通常允许阻塞的线程在等待应用程序状态变化时停止消耗处理器时间。

实现内部仍可能使用短暂的自旋。决定性的区别在于条件变量的接口及其等待状态变化的语义,而不是保证每次等待都会立即进入操作系统内核。

通知语义与历史发展

条件变量是在 20 世纪 70 年代与基于管程的并发方法一同发展起来的。C. A. R. 霍尔于 1974 年提出的管程形式与霍尔式通知语义相关:发送通知会将管程内的执行权转交给一个等待线程,而发送通知的线程则暂停执行。因此,可以在线程恢复执行时,对条件作出更强的推断。

与 Mesa 编程环境相关的 Mesa 式通知语义则允许发送通知的线程继续执行。被唤醒的线程要等到之后重新获取管程锁,才能执行。届时,相关条件可能已经发生变化。

如今广泛使用的条件变量接口,在这一点上大多采用 Mesa 式模型。因此,最好将通知理解为重新检查状态的提示,而不是谓词仍然成立的保证。

接口与实现

许多应用程序编程接口都提供条件变量:

  • 可移植操作系统接口(POSIX)线程提供 pthread_cond_wait、pthread_cond_timedwait、pthread_cond_signal 和 pthread_cond_broadcast。
  • C++ 提供 std::condition_variable 和 std::condition_variable_any。
  • Java 通过 Object.wait、notify 和 notifyAll 提供管程等待机制,并通过 java.util.concurrent.locks.Condition 提供显式的条件对象。
  • Python 提供 threading.Condition。
  • 微软 Windows 提供可与临界区或轻量级读写锁配合使用的条件变量操作。

这些接口在锁的要求、中断与取消行为、超时所用的时钟,以及对唤醒对象选择的保证等方面有所不同。

实现通常将用户空间的内部管理机制与操作系统提供的阻塞设施结合使用。在 Linux 上,这类实现通常使用 futex 操作。内部计数器、等待线程队列和顺序协调协议共同协调通知与阻塞,而不会向应用程序代码暴露这些细节。

正确性与局限

内存可见性

通知不能替代对共享数据访问的同步。在常规的基于互斥锁的模式中,内存可见性由锁操作和语言的内存模型保证。重新获取互斥锁之后,等待线程就可以查看经过适当同步的更新。

即使通知看起来按预期顺序发生,未经同步的状态访问仍可能造成竞态条件或数据竞争。

超时

发生超时,并不能证明线程重新获得互斥锁时谓词为假。状态变化与超时到期可能几乎同时发生,因此仍须在锁的保护下检查谓词。

反复使用相对时长等待,也可能超出预期的总时限,因为每次唤醒都可能重新开始完整的等待时长。使用绝对截止时间可以避免这种特定的延长。时钟的选择也很重要,因为墙上时钟的校时与经过时长的测量具有不同的行为特征。

活性与效率

条件变量通常不保证公平地选择等待线程,也不保证等待时间有界。正确的谓词循环确定了操作何时可以安全执行,但它本身并不保证每个线程最终都能继续执行。

广播可能造成惊群:大量线程被唤醒,争抢同一个互斥锁,而大多数线程又重新进入休眠。反过来,通知的等待线程过少,也可能使已有的工作无人处理。通知策略必须与状态转换使线程得以继续执行的方式相匹配。

条件变量也不能防止死锁。虽然等待会释放关联的互斥锁,但线程可能仍持有其他锁,而能够使其谓词成立的线程恰好需要这些锁。

最后,对象生命周期和关闭过程都需要显式协调。只要线程仍可能访问条件变量及其保护的状态,或在其上等待,这些对象就必须保持有效。如果没有完整的关闭协议就销毁同步对象或弃置等待线程,可能导致无效访问,或使线程永久阻塞。