互斥锁(mutex,源自 mutual exclusion,意为“互斥”)是一种同步原语,每次只允许一个执行单元独占访问共享资源。在并发计算中,线程通常会在访问受保护的数据之前获取互斥锁,并在访问结束后释放它。如果互斥锁已被其他线程持有,获取操作可能需要等待,直到锁可用。互斥锁实现了互斥,有助于防止竞态条件,但其有效性取决于所有相关访问是否都遵循相同的同步协议。
操作与所有权
互斥锁有两种基本逻辑状态:未锁定和已锁定。其接口通常提供以下操作:
- 加锁,也称获取:取得独占所有权,必要时等待。
- 解锁,也称释放:放弃所有权,使其他执行单元能够获取该互斥锁。
- 尝试加锁:尝试获取互斥锁,但不等待锁变为可用,并报告成功或失败。
- 限时加锁(若支持):在超时时长或截止时间的约束下尝试获取互斥锁。
与普通的布尔标志不同,互斥锁会协调相互竞争的获取操作,确保两个线程不可能同时成功获得其所有权。
持有互斥锁期间执行的代码称为临界区。例如,以下伪代码保护了一个共享计数器:
lock(counter_mutex)
try:
counter = counter + 1
finally:
unlock(counter_mutex)
计数器递增可能涉及彼此分离的读取、算术运算和写入操作。如果没有同步,两个线程可能读到相同的旧值,并相互覆盖更新结果。如果每一次需要保护的并发访问都使用同一个互斥锁,相关操作就会串行执行。
传统的互斥锁具有所有者:获取它的线程负责释放它。在许多接口中,由另一个线程尝试解锁是无效操作,不过具体结果取决于接口和互斥锁类型。面向任务的异步互斥锁则可能将所有权与逻辑任务或守卫对象关联起来。
互斥锁通过约定来保护资源;它不会自动阻止代码在未获取锁的情况下访问该资源。
正确性与内存可见性
互斥只是共享数据同步所需保证的一部分。在适用的内存模型允许的情况下,现代处理器和编译器可能会重排操作。因此,标准互斥锁接口也会规定内存顺序方面的效果。
通常,释放互斥锁会发布此前的修改;另一个线程随后成功获取同一个互斥锁时,就会建立观察到这些修改所需的顺序。在使用相关术语的语言标准中,这有助于建立“先发生于”(happens-before)关系。
这些保证使互斥锁区别于普通标志。如果标志的实现没有采用适当的原子操作和内存顺序,它既可能无法排除竞争线程,也可能无法使受保护的写入对其他线程可见。C 和 C++ 等语言中的 volatile 限定符不能替代互斥锁同步。
正确的加锁方式必须保护完整的逻辑操作,而不只是其中的单条指令。例如,先检查队列是否非空、再移除一个元素,通常需要作为一个受保护的操作执行。如果在检查和移除之间释放互斥锁,其他线程就可能在此期间修改队列。
互斥锁常用于维护数据结构的不变量,例如确保元素计数与集合内容一致。每当所有权移交给另一个线程时,受保护的状态都必须满足所要求的不变量。
实现
互斥锁可以由操作系统、运行时或编程语言库提供。其实现通常将处理器级别的原子操作与挂起、唤醒等待线程的机制相结合。
快速路径与竞争路径
在无竞争的情况下,线程通常只需少量原子操作就能获取和释放互斥锁,无须进入操作系统内核。
在有竞争的情况下,实现可能会:
- 短暂重试,同时检查互斥锁是否已可用。
- 将线程置于等待状态。
- 安排某个等待线程在锁释放后变为可运行状态。
具体步骤因实现而异。有些实现会先自旋一小段时间再阻塞,另一些则会更早阻塞。这是在处理器时间与挂起、恢复线程的开销之间进行权衡。
在 Linux 上,快速用户空间互斥机制提供了一种机制,可根据用户内存中的某个值让相关线程等待或唤醒它们。线程库可以利用它实现互斥锁,使无竞争情况下的操作完全在用户空间内完成。快速用户空间互斥机制本身并不等同于完整的互斥锁:加锁协议及其他语义由使用它的库提供。
调度与公平性
释放互斥锁并不总能保证等待时间最长的线程接下来获取它。根据具体实现和调度方式,新到达的线程可能先于已经等待的线程获取锁。
因此,互斥本身并不保证公平性,也不保证不会发生饥饿。严格的移交策略可以提高可预测性,但其性能代价可能不同于优先考虑吞吐量的策略。
类型与接口差异
不同库和操作系统中的互斥锁语义有所不同。
| 类型或特性 | 含义 |
|---|---|
| 非递归互斥锁 | 不允许当前所有者按常规方式重复获取;尝试这样做的结果取决于接口。 |
| 递归互斥锁 | 允许所有者重复获取,但必须释放相同次数后,其他线程才能获取它。 |
| 错误检查互斥锁 | 检测指定的误用情况,例如某些所有权错误,并报告错误。 |
| 限时互斥锁 | 支持带超时时长或截止时间的获取操作。 |
| 健壮互斥锁 | 提供明确规定的方式,用于检测和处理所有者在持锁期间终止的情况。 |
| 进程共享互斥锁 | 在获得支持且正确初始化的情况下,可以协调不同进程中的执行单元。 |
这些特性不一定相互排斥。
递归互斥锁可以支持获取同一把锁的嵌套调用,但不能使任意重入行为都变得安全。嵌套执行的代码仍可能遇到只完成部分更新的状态。
健壮互斥锁不会自动修复受保护的数据。例如,支持该特性的 可移植操作系统接口(POSIX)可以报告前一个所有者已终止,随后恢复代码必须判断能否使受保护的状态恢复一致。
进程间使用的互斥锁必须专门为此用途设计。仅仅将一个普通的线程局部同步对象放入共享内存并不足够。
与其他同步机制的关系
信号量
信号量维护一个计数,可以表示多个可用许可。二元信号量可用于某些互斥协议,但通常不能与互斥锁互换使用。
两者的核心区别在于所有权:互斥锁通常必须由其所有者释放,而信号量通常可以由另一个线程发出信号。因此,信号量还支持事件通知和资源计数。
自旋锁
自旋锁会反复检查锁是否可用,而不是让等待线程休眠。如果等待时间很短,且持锁者可以在另一个处理器上运行,自旋就可能有用;但当等待时间较长或所有者无法运行时,自旋会浪费处理器时间。
术语的用法并不统一:有些系统将自旋锁视为互斥锁的一种,另一些系统则只用“互斥锁”指代阻塞式锁。混合式互斥锁可以结合自旋与阻塞。
读写锁
读写锁允许多个读取者同时访问,但要求写入者独占访问。对于某些以读取为主的工作负载,它可以提高并发程度,但也会增加簿记开销,并引入策略问题,例如优先照顾读取者还是写入者。它不一定比互斥锁更快。
条件变量
条件变量允许线程等待,直到有关共享状态的某个谓词可能变为真。条件变量的等待操作会以原子方式释放关联的互斥锁并进入等待协议,然后在返回前重新获取互斥锁。
必须在循环中检查谓词:
lock(queue_mutex)
try:
while queue is empty:
wait(queue_changed, queue_mutex)
item = remove_first(queue)
finally:
unlock(queue_mutex)
必须重新检查,因为唤醒可能是虚假的,也可能有其他线程在被唤醒的线程重新获取互斥锁之前改变了状态。
故障模式与局限
死锁
当线程无限期地等待彼此持有的锁时,就可能发生死锁。例如,一个线程持有互斥锁 A 并等待 B,另一个线程则持有 B 并等待 A。
一致的加锁顺序可以防止这种特定的循环等待模式。线程重新获取自己已经持有的非递归互斥锁,也可能造成自死锁,具体取决于互斥锁接口。递归互斥锁解决的是这一特定情形,而不是涉及多个资源的死锁。
优先级反转
当高优先级线程等待低优先级线程持有的互斥锁,而其他可运行的工作又延迟了锁所有者的执行时,就会发生优先级反转。优先级继承可以暂时提高所有者的有效优先级;在指定的调度假设下,优先级上限协议提供了另一种解决办法。这些特性在实时操作系统中尤为重要,但并非互斥锁普遍具备的属性。
竞争与可扩展性
竞争激烈的互斥锁会成为串行化瓶颈。此时,增加线程可能只会增加等待,而不会增加有效的并行计算。在处理器之间转移锁的所有权和受保护的数据,也可能产生 CPU 缓存通信流量。
粗粒度加锁使用较少的互斥锁来保护较大范围的状态,可以简化推理,但会降低并发程度。细粒度加锁可以让更多工作独立进行,代价则是所有权规则更加复杂,加锁顺序出错的风险也更高。
生命周期与异常执行
只要线程仍可能持有或尝试使用互斥锁,该锁就必须保持有效。销毁已锁定的互斥锁,或在其仍可被访问时释放其存储空间,都违反了通常的接口要求。
异常、提前返回、取消或所有者终止,都可能使互斥锁一直保持锁定,除非外围机制保证释放它。作用域守卫、上下文管理器和结构化清理机制,将释放操作与受保护作用域的生命周期关联起来。持有互斥锁期间执行的阻塞操作和回调,也可能延长持锁时间或引入意料之外的依赖关系。
在异步系统与分布式系统中的使用
在异步编程中,阻塞式互斥锁可能阻塞整个执行线程,包括需要运行其他任务的事件循环。异步互斥锁则会挂起等待的任务,同时允许执行器运行其他工作。不过,在跨越挂起点的期间一直持锁,仍可能造成竞争或死锁,具体取决于程序中的依赖关系。
本地互斥锁不会自动提供跨机器的互斥。分布式计算系统需要采用能够应对通信故障、进程故障和时序不确定性的协议。例如,租约到期后,新所有者可能获准继续执行,而旧所有者此时仍在运行;仅靠本地互斥锁的所有权规则无法处理这种情况。