信号量是并发计算中用于协调执行和管理资源访问的一种同步原语。它维护可用许可的逻辑计数,并提供以原子方式获取或释放许可的操作。有许可可用时,获取操作便可继续;否则,调用方会等待或收到表示失败的结果,具体取决于所使用的操作。信号量可以限制同时使用某项资源的参与者数量、规定不同活动之间的执行顺序,也可以传递工作已就绪或容量已可用的通知。
起源与术语
艾兹格·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 |
具体的返回值、中断规则、计数上限和调度保证取决于所用接口。
抽象行为
信号量的初始计数为 。它有两项基本操作:
- **获取:**如果有可用许可,则消耗一个许可并继续执行。如果没有,则等待,直到可以获取许可。
- **释放:**增加一个许可;如果有参与者正在等待,则允许其中一个继续执行。
这些变化必须表现为原子操作:并发调用方不能同时获取同一个许可;在检查可用性与进入等待状态之间发生竞争时,也不能丢失释放操作的效果。
在一种常见的非负计数模型中,抽象状态转换如下:
当 时,获取操作会等待,而不是立即执行减一。这些表达式规定的是行为,而非实现方式:先进行普通比较,再进行普通减一,并不能提供所需的原子性。
有些教科书采用另一种表述:先将计数减一,并允许内部计数为负,以表示正在等待的参与者。这只是表示等待状态的另一种方式,并不意味着公开的信号量接口必须暴露负值。
许可与所有权
信号量通常不会将许可与某个特定的所有者关联起来。一个线程或进程可以获取许可,再由另一个线程或进程释放。这使生产者—消费者之间的信号通知成为可能,但也意味着错误的释放操作可能凭空增加一个许可。
在资源管理中,初始化为 个许可的信号量可以施加以下约束:
其中, 是已成功获取但尚未释放的许可数量。这一约束依赖于程序将每次成功获取与恰好一次释放配对,并且不释放从未获取过的许可。仅仅设置初始值,并不能让普通计数信号量检测出这类错误。
主要类型
计数信号量
计数信号量可表示任意非负数量的许可,但受实现上限约束。将其初始化为 个许可后,最多可以同时有 个已获取但尚未释放的许可;此后的调用方必须等待。
典型用途包括限制对固定大小连接池的访问、跟踪空闲缓冲区槽位,以及统计排队的工作项。
二元信号量
二元信号量最多只有一个可用许可。它可以表示资源是否可独占使用,也可以表示一个待处理的通知。
二元信号量不一定等同于仅将初始值设为一的计数信号量。如果普通计数信号量收到多余的释放操作,其计数可能超过一。二元信号量接口将状态限制为零或一,但对多余释放操作的处理方式各不相同:可能拒绝该操作,可能不产生额外效果,也可能将其视为违反接口使用要求。
有界信号量
有界信号量会强制执行预先设定的上限,该上限通常是资源的初始容量。在提供这一功能的接口中,释放操作若使计数超出上限,就会被视为错误。有界信号量可以暴露获取与释放操作不匹配的问题,而普通计数信号量可能会默默接受这些操作。
不同库对二元信号量和有界信号量这两个术语的用法并不完全一致。
常见协调模式
限制并发访问
初始化为 的信号量可以将同时执行某项操作的参与者数量限制为 :
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()
如果生产者在消费者开始等待之前就释放了许可,该许可仍会保持可用。这种保留通知的能力是信号量通知机制的一项典型特征。
重复释放可以在计数信号量中累积多个许可,但信号量本身并不存储相关数据。如果每个许可都对应一个独立的数据项,就需要队列或其他存储机制。
有界生产者—消费者缓冲区
容量为 的有界缓冲区通常使用:
empty,初始值为 ,用于统计未使用的位置;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。
信号量用于工作线程协调、有界队列、资源池、设备访问和准入控制。限制未完成请求数量的信号量控制的是并发量,而不一定是请求速率:如果请求完成得很快,固定数量的许可也能支持很高的每秒请求数。
这一基本抽象以可靠的共享信号量状态为前提。若要将许可控制扩展到可能各自独立发生故障的多台机器,就会引入持有者超期、通信丢失和客户端状态过时等额外问题,需要采用超出本地信号量范畴的协议来解决。