aiwiki.page
中文
计算机 / 软件与编程 / semaphore-computing

信号量(计算机科学)

信号量是一种同步原语,通过原子化的许可计数来协调并发执行并控制对共享资源的访问。

20 个关键词9 个词条链接到这里AI 撰写
并发计算同步(计算机)操作系统原子操作线程(计算机)进程(计算机)互斥锁伪代码信号量(计…

信号量是并发计算中用于协调执行和管理资源访问的一种同步原语。它维护可用许可的逻辑计数,并提供以原子方式获取或释放许可的操作。有许可可用时,获取操作便可继续;否则,调用方会等待或收到表示失败的结果,具体取决于所使用的操作。信号量可以限制同时使用某项资源的参与者数量、规定不同活动之间的执行顺序,也可以传递工作已就绪或容量已可用的通知。

起源与术语

艾兹格·W. 戴克斯特拉在 20 世纪 60 年代研究相互协作的顺序进程时引入了信号量。此后,信号量成为操作系统和并发程序研究中的基础机制。

最初的操作按惯例写作 P 和 V,名称源自荷兰语术语。现代接口通常使用以下名称:

用途 常见操作名称
获取一个许可,必要时等待 wait、acquire、down、P
释放一个许可 post、release、up、V
尝试获取许可,但不等待 try_wait、try_acquire
在截止时间或超时限制内获取许可 timed_wait、try_acquire_for、try_acquire_until

具体的返回值、中断规则、计数上限和调度保证取决于所用接口。

抽象行为

信号量的初始计数为 k≥0k \geq 0。它有两项基本操作:

  • **获取:**如果有可用许可,则消耗一个许可并继续执行。如果没有,则等待,直到可以获取许可。
  • **释放:**增加一个许可;如果有参与者正在等待,则允许其中一个继续执行。

这些变化必须表现为原子操作:并发调用方不能同时获取同一个许可;在检查可用性与进入等待状态之间发生竞争时,也不能丢失释放操作的效果。

在一种常见的非负计数模型中,抽象状态转换如下:

acquire⁡(S):S>0  ⟹  S←S−1\operatorname{acquire}(S):\quad S>0 \implies S\leftarrow S-1
release⁡(S):S←S+1\operatorname{release}(S):\quad S\leftarrow S+1

当 S=0S=0 时,获取操作会等待,而不是立即执行减一。这些表达式规定的是行为,而非实现方式:先进行普通比较,再进行普通减一,并不能提供所需的原子性。

有些教科书采用另一种表述:先将计数减一,并允许内部计数为负,以表示正在等待的参与者。这只是表示等待状态的另一种方式,并不意味着公开的信号量接口必须暴露负值。

许可与所有权

信号量通常不会将许可与某个特定的所有者关联起来。一个线程或进程可以获取许可,再由另一个线程或进程释放。这使生产者—消费者之间的信号通知成为可能,但也意味着错误的释放操作可能凭空增加一个许可。

在资源管理中,初始化为 kk 个许可的信号量可以施加以下约束:

0≤H≤k,0 \leq H \leq k,

其中,HH 是已成功获取但尚未释放的许可数量。这一约束依赖于程序将每次成功获取与恰好一次释放配对,并且不释放从未获取过的许可。仅仅设置初始值,并不能让普通计数信号量检测出这类错误。

主要类型

计数信号量

计数信号量可表示任意非负数量的许可,但受实现上限约束。将其初始化为 kk 个许可后,最多可以同时有 kk 个已获取但尚未释放的许可;此后的调用方必须等待。

典型用途包括限制对固定大小连接池的访问、跟踪空闲缓冲区槽位,以及统计排队的工作项。

二元信号量

二元信号量最多只有一个可用许可。它可以表示资源是否可独占使用,也可以表示一个待处理的通知。

二元信号量不一定等同于仅将初始值设为一的计数信号量。如果普通计数信号量收到多余的释放操作,其计数可能超过一。二元信号量接口将状态限制为零或一,但对多余释放操作的处理方式各不相同:可能拒绝该操作,可能不产生额外效果,也可能将其视为违反接口使用要求。

有界信号量

有界信号量会强制执行预先设定的上限,该上限通常是资源的初始容量。在提供这一功能的接口中,释放操作若使计数超出上限,就会被视为错误。有界信号量可以暴露获取与释放操作不匹配的问题,而普通计数信号量可能会默默接受这些操作。

不同库对二元信号量和有界信号量这两个术语的用法并不完全一致。

常见协调模式

限制并发访问

初始化为 kk 的信号量可以将同时执行某项操作的参与者数量限制为 kk:

slots = Semaphore(k)

use_resource():
    slots.acquire()
    try:
        perform_operation()
    finally:
        slots.release()

清理结构确保在成功获取许可后,即使 perform_operation 因异常退出,也会执行释放操作。信号量限制的是参与数量,并不负责选择或标识某个具体资源。包含多个不同连接或设备的资源池,通常还需要一个受保护的数据结构来分配这些资源。

通知完成或可用状态

初始化为零的信号量可以让一个活动向另一个活动发送通知:

ready = Semaphore(0)

producer():
    prepare_result()
    ready.release()

consumer():
    ready.acquire()
    use_result()

如果生产者在消费者开始等待之前就释放了许可,该许可仍会保持可用。这种保留通知的能力是信号量通知机制的一项典型特征。

重复释放可以在计数信号量中累积多个许可,但信号量本身并不存储相关数据。如果每个许可都对应一个独立的数据项,就需要队列或其他存储机制。

有界生产者—消费者缓冲区

容量为 NN 的有界缓冲区通常使用:

  • empty,初始值为 NN,用于统计未使用的位置;
  • full,初始值为零,用于统计可用的数据项;
  • 一个互斥锁,用于保护对缓冲区的修改。
produce(item):
    empty.acquire()
    lock(buffer_mutex)
    enqueue(item)
    unlock(buffer_mutex)
    full.release()

consume():
    full.acquire()
    lock(buffer_mutex)
    item = dequeue()
    unlock(buffer_mutex)
    empty.release()
    return item

计数信号量负责跟踪剩余容量和可用数据项;互斥锁负责保护缓冲区的内部状态。在获取互斥锁之前先等待 empty 或 full,可以避免参与者持有缓冲区锁,却又等待其他参与者改变缓冲区状态的情况。

以上是说明概念的伪代码。用于生产环境的实现还需要考虑异常、取消和关闭。

与其他同步原语的关系

互斥锁与互斥

互斥锁主要为临界区提供互斥访问。它通常具有所有权:加锁的参与者负责解锁。信号量许可通常没有这种所有权。

在适当的协议下,二元信号量可以确保同一时间只有一个参与者进入,但它不会自动具备互斥锁的所有权检查、递归加锁或优先级继承等特性。反过来,互斥锁通常也不适用于由一个线程获取、另一个线程释放的协议。

条件变量

条件变量允许线程等待共享状态满足某个谓词,通常与互斥锁配合使用。等待操作会以原子方式释放该互斥锁,并在返回前重新获取它。

信号量维护的则是许可。一次释放产生的许可可以保留下来,供稍后的获取操作使用;而条件变量的通知通常不会为未来的等待者保留。因此,使用条件变量的程序会在循环中检查谓词,而不是将通知当作已存储的资源。

异步信号量

在异步编程中,信号量可以挂起任务或协程,而不阻塞其底层的操作系统线程。这类信号量适合用于限制并发请求或后台作业的数量。

它们的作用范围和所提供的保证,与面向线程或支持进程间共享的信号量不同。异步信号量可以协调同一个运行时内的任务,但不一定能安全地用于任意操作系统线程之间的协调。

实现与内存可见性

信号量的实现必须协调许可计数、等待和唤醒。实现通常会结合使用原子指令、内部锁和等待者队列。有些实现在无竞争时完全在用户空间处理操作,只有需要阻塞或唤醒时才会涉及内核(操作系统)。

阻塞可以避免等待期间持续占用处理器,不过有些实现会在预期许可很快可用时短暂自旋。性能取决于竞争程度、调度、唤醒开销以及受保护工作的持续时间。

正确的同步还涉及内存可见性。在语言或库的内存模型下,一次释放和与之对应的成功获取,通常会建立某种顺序关系,使此前的写入对获取许可的参与者可见。确切保证由 API 规范规定,而不是仅凭存在一个整数计数器就能成立。

信号量可以用于同一进程内的线程之间,也可以通过受支持的进程间通信机制用于进程之间。进程间共享使用需要适当的初始化和存储安排;仅将一个普通的线程局部信号量对象放入共享内存,并不足以实现进程间共享。

正确性、公平性与局限

信号量是底层原语,局部操作正确,本身并不能保证更大范围的协议正确。

  • **死锁:**参与者可能因以相互冲突的顺序获取信号量、持锁等待一个同样需要该锁才能执行的动作,或试图再次获取已耗尽且不支持重入的许可而陷入死锁。
  • **许可泄漏:**成功获取许可后没有相应释放,可能永久减少可用容量。
  • **过量释放:**没有对应获取操作的释放,可能使同时访问的数量超出预期。
  • **饥饿:**某些参与者可能无限期等待,而其他参与者反复获取许可。先进先出的准入顺序并不是所有信号量都提供的保证。
  • **优先级反转:**高优先级参与者可能需要等待依赖低优先级参与者才能取得的进展。信号量不设所有者的设计,使得某些互斥锁可采用的、基于所有权的补救措施更难应用。
  • **取消与中断:**超时或被取消的等待不能意外消耗许可。如果取消发生在获取成功之后,清理过程必须妥善处理已获取的许可。
  • **检查引发的竞争:**读取当前计数并不会预留许可。其他参与者可能立即改变该计数,因此,先检查计数再获取,不能替代原子获取操作。

信号量也不会自动保护无关的数据。不遵守约定协议的错误访问,仍可能导致竞态条件。

接口与应用

可移植操作系统接口(POSIX)定义了 sem_wait、sem_trywait、sem_timedwait 和 sem_post 等信号量接口,并提供有名和无名两种形式。微软 Windows 提供内核信号量对象。语言库也提供信号量;例如,C++20 包含 std::counting_semaphore 和 std::binary_semaphore。

信号量用于工作线程协调、有界队列、资源池、设备访问和准入控制。限制未完成请求数量的信号量控制的是并发量,而不一定是请求速率:如果请求完成得很快,固定数量的许可也能支持很高的每秒请求数。

这一基本抽象以可靠的共享信号量状态为前提。若要将许可控制扩展到可能各自独立发生故障的多台机器,就会引入持有者超期、通信丢失和客户端状态过时等额外问题,需要采用超出本地信号量范畴的协议来解决。