临界区是一段访问共享状态或其他共享资源的代码,不能与会和它发生冲突的操作并发执行。在并发计算中,通常通过互斥来保护临界区,使参与执行的各个执行上下文在任一时刻,只有一个能够进入由同一同步机制保护的区域。临界区指的是受保护的代码,而不是用于保护代码的锁或其他机制。
目的与范围
并发执行允许多个线程或进程在彼此重叠的时间段内推进执行。它们的操作可以在单个处理器上交错执行,也可以在不同处理器上同时运行。当它们访问共享内存时,某种特定的交错顺序可能破坏顺序执行时成立的假设。
例如,将一个共享计数器加一可能包含三个步骤:
- 读取计数器。
- 计算该值加一的结果。
- 将结果写回。
如果两个线程在任何一方写回之前都读到了相同的初始值,它们就可能写入相同的递增结果。这样便丢失了一次递增。这是竞态条件的一个例子。
临界区将必须协调执行的操作归在一起。它的范围由需要保护的性质决定,不一定只涉及单个变量或单条语句。例如,更新链式结构可能需要修改多个指针,同时保持它们之间的关系。单独保护每一次赋值,仍可能导致整个操作出错。
互斥针对特定的保护域生效。两个互不相关的临界区如果使用不同的锁,并且彼此不干扰,就可以同时执行。反过来,不同函数也可能因为访问同一份共享状态而需要使用同一把锁。
基本结构
传统的临界区模型将参与者的执行划分为四个部分:
- **进入区:**取得访问受保护资源的许可。
- **临界区:**执行受保护的操作。
- **退出区:**释放该许可。
- **剩余区:**执行受保护区域以外的工作。
一种典型实现使用互斥锁:
acquire(counter_lock)
try:
counter = counter + 1
finally:
release(counter_lock)
这是一段伪代码:try 和 finally 的确切行为取决于所用语言或编程环境。这里的目的是说明,即使控制流意外离开受保护的操作,也必须释放锁。
所有相互冲突的访问都必须遵循同一套同步协议。对写入加锁并不能让未同步的读取变得安全,而用互不相关的锁保护同一个对象,也不能使这些访问之间形成互斥。
锁通常与一个不变式相关联:每当受保护的状态可供其他参与者访问时,该条件都应成立。临界区在修改状态的过程中可以暂时破坏这个不变式,但必须在解除保护之前恢复它。
正确性要求
经典的临界区问题研究的是:相互协作的参与者如何协调进入临界区,同时满足若干性质。
互斥
在任一时刻,最多只能有一个参与者在互斥区域内执行。对于 个参与者,令 表示参与者 是否处于该区域内。这一要求可以表示为
这是一项安全性性质:它排除了一种不希望出现的状态。但仅凭这一性质,并不能保证任何参与者最终都能进入。
前进性
如果临界区无人占用,并且有参与者希望进入,那么不打算进入的参与者不得使下一个进入者的选择被无限期推迟。
前进性依赖于对执行过程的假设。如果持锁者永久停止执行,或者调度器始终不运行某个必须采取行动的参与者,协议通常就无法保证操作能够完成。
有界等待
参与者请求进入后,在它获准进入之前,其他参与者能够进入的次数应有一个上限。
有界等待比仅仅保证系统中的某处持续取得进展更强。一种机制可能反复允许某些参与者进入,却无限期地推迟另一个参与者,这种情况称为饥饿。有界等待也不同于按实际时间规定的截止期限:被其他参与者抢先进入的次数有界,并不一定意味着等待时长有界。
实际的同步接口并非都保证有界等待或先到先得。必须将公平性与基本的互斥保证区分开来。
实现机制
互斥锁与信号量
互斥锁通常具有所有权:获取锁的参与者负责释放它。争用锁的线程可能被操作系统挂起,直到锁可用,不过具体实现往往会将短暂自旋与阻塞结合起来。
信号量维护一个由同步操作控制的计数。只有一个许可的信号量可以实现互斥进入,但其所有权规则不一定与互斥锁相同。允许多个许可的信号量限制的是并发程度,而不是建立一个只能独占的临界区。
自旋锁与原子指令
自旋锁通过反复检查锁的状态或尝试获取锁来等待,而不是挂起调用者。当受保护的操作很短,并且持锁者很可能很快得到运行并释放锁时,自旋锁可能很有用。长时间自旋会消耗处理器时间,而且当持锁者未被调度运行时,性能可能很差。
锁的实现通常依赖原子操作,例如测试并置位或比较并交换。相对于相互竞争的操作,这些操作能够使锁的状态转换不可分割。普通读取后再执行普通写入并不足够:两个参与者可能都观察到未加锁状态,并且都认为自己取得了锁的所有权。
对于一些简单任务,例如递增计数器,原子操作也可以替代显式临界区。但它不会自动保护涉及多个对象或一系列相互依赖操作的不变式。
中断与调度控制
在内核(操作系统)中,禁用本地中断可以防止当前处理器上的特定中断处理程序打断受保护的工作。禁用抢占则可以防止某些由调度产生的交错执行。
这两种措施单独使用,都无法排除另一个处理器上的执行。因此,多处理器内核通常将本地执行控制与锁结合使用。这些技术各有不同的使用限制,不能普遍替代应用层的同步机制。
内存顺序与可见性
保护共享内存并不只是要防止同时进入。编译器或处理器可能对操作进行重排;如果没有同步规则加以约束,不同处理器也可能以不同顺序观察到内存操作的效果。
语言的内存模型规定了同步如何影响可见性和顺序。在常见的互斥锁接口中,释放锁与随后获取同一把锁之间会建立一种顺序关系,使获取锁的线程能够看到此前受保护的写入。
因此,自行编写的锁即使在源代码层面看似能够保证互斥,如果没有合适的原子操作和内存顺序语义,仍然可能是错误的。在 C 和 C++ 等语言中,相互冲突且未经同步的非原子内存访问可能构成数据竞争,并导致未定义行为。
C 和 C++ 中的 volatile 限定符不能替代互斥锁或原子同步。同样,缓存一致性本身也不能建立多步骤并发算法所需的执行顺序。
性能与失效情形
争用与粒度
当多个参与者在彼此重叠的时间段内尝试获取同一把锁时,就会发生锁争用。争用会引入等待,并可能限制并行计算带来的收益。
粗粒度加锁使用少量锁来保护较大范围的状态。这种方式便于分析,但可能使原本能够独立进行的操作串行执行。细粒度加锁则将保护工作分配给更多的锁,以额外开销和更复杂的交互为代价,提高潜在的并发程度。
缩短临界区可以减少等待,但其边界仍必须涵盖维持受保护不变式所需的全部操作。例如,将共享数据的读取移到锁外,即使后续写入仍受保护,也可能使之后据此作出的决策失效。
死锁与重入
当参与者循环等待彼此持有的锁时,就可能发生死锁。一个常见例子是:一个线程持有锁 A 并等待锁 B,另一个线程则持有锁 B 并等待锁 A。始终按统一顺序获取锁,是防止此类情况的一种方法。
线程尝试再次获取自己已持有的非递归互斥锁时,也可能发生死锁。递归锁允许所有者重复获取,但不会自动使受保护的代码能够安全地处理重入调用。在临界区内执行的回调,即使运行在持锁线程上,也可能观察到暂时不一致的状态。
与调度的相互影响
高优先级线程可能需要等待低优先级线程持有的锁。如果其他可运行的工作延迟了持锁线程的执行,高优先级线程就可能遭遇优先级反转。一些同步系统使用优先级继承或优先级上限协议来控制这种行为,尤其是在实时操作系统中。
临界区内耗时较长或耗时不可预测的操作,包括阻塞式输入输出,可能增加所有共享该锁的参与者的等待时间。
历史与相关概念
随着人们研究如何协调共享内存系统中的进程,临界区问题成为并发编程的基础课题。艾兹格·W. 迪杰斯特拉于 1965 年发表了互斥问题的一种早期解法。后来的软件算法,包括彼得森双进程算法,成为在明确的共享内存行为假设下研究互斥性和前进性的标准示例。
这类算法在形式验证中仍然十分重要,但教科书中的证明往往假定了比现代系统上普通加载和存储操作所能提供的更强的顺序保证。具体实现必须同时满足算法的假设和编程语言的内存模型。
临界区不同于数据库事务。受锁保护的区域通常不提供回滚、持久化存储或故障后恢复功能。事务内部可能使用锁,但其语义更为广泛。
临界区也不必对应单条机器指令,或在实际执行中完全不可中断。它的执行可以暂停;关键的互斥保证在于,在此期间,其他遵循同一协议的参与者不能进入与之冲突的受保护区域。
某些系统将“临界区”用作特定接口的名称。在微软 Windows中,临界区对象是一种基于所有权的同步原语,用于同一进程内的线程,并允许拥有它的线程递归获取。这些特定接口的性质并不是一般意义上临界区的定义。