临界区问题及其解决办法（抢占式内核和非抢占式内核）

假设某个系统有 n 个进程 {P₀，P₁，…，P_n-1}。每个进程有一段代码，称为临界区，进程在执行该区时可能修改公共变量、更新一个表、写一个文件等。该系统的重要特征是，当一个进程在临界区内执行时，其他进程不允许在它们的临界区内执行。也就是说，没有两个进程可以在它们的临界区内同时执行。

临界区问题是设计一个协议以便协作进程。在进入临界区前，每个进程应请求许可。实现这一请求的代码区段称为进入区；临界区之后可以有退出区，其他代码为剩余区。一个典型进程 P_i 的通用结构如图 1 所示。

图 1 典型进程 P_i 的通用结构

进入区和退出区被框起来，以突出这些代码区段的重要性。

临界区问题的解决方案应满足如下 3 条要求：

1. 互斥：如果进程 P_i 在其临界区内执行，那么其他进程都不能在其临界区内执行。
2. 进步：如果没有进程在其临界区内执行，并且有进程需要进入临界区，那么只有那些不在剩余区内执行的进程可以参加选择，以便确定谁能下次进入临界区，而且这种选择不能无限推迟。
3. 有限等待：从一个进程做出进入临界区的请求直到这个请求允许为止，其他进程允许进入其临界区的次数具有上限。

假定每个进程的执行速度不为 0。然而，对于 n 个进程的相对速度不作任何假设。

在任一给定时间点，一个操作系统可能具有多个处于内核态的活动进程。因此，操作系统的实现代码（内核代码）可能出现竞争条件。

例如，有一个内核数据结构链表，用于维护打开系统内的文件。当打开或关闭一个新文件时，应更新这个链表（向链表增加一个文件，或从链表中删除一个文件）。如果两个进程同时打开文件，那么这两个独立的更新操作可能产生竞争条件。其他导致竞争条件的内核数据结构包括维护内存分配、维护进程列表及中断处理等的数据结构。内核开发人员应确保操作系统没有这些竞争条件。

有两种常用方法，用于处理操作系统的临界区问题：抢占式内核与非抢占式内核：

• 抢占式内核允许处于内核模式的进程被抢占；
• 非抢占式内核不允许处于内核模式的进程被抢占。处于内核模式运行的进程会一直运行，直到退出内核模式、阻塞或自愿放弃CPU控制。

显然，非抢占式内核的数据结构基本不会导致竞争条件，因为在任一时间点只有一个进程处于内核模式。然而，对于抢占式内核，就不这样简单了；这些抢占式内核需要认真设计，以便确保内核数据结构不会导致竞争条件。对于 SMP 体系结构，抢占式内核更难设计，因为在这些环境下两个处于内核态的进程可以同时运行在不同处理器上。

那么，为何会有人更喜欢抢占式内核而不是非抢占式内核呢？

抢占式内核响应更快，因为处于内核模式的进程在释放 CPU 之前不会运行任意长的时间。（当然，在内核模式下持续运行很长时间的风险可以通过设计内核代码来最小化。）再者，抢占式内核更适用于实时编程，因为它能允许实时进程抢占在内核模态下运行的其他进程。