S02E05 - 操作系统并发(2): 进程同步

Intro

#

当我们引入多进程后，程序的执行模式从顺序执行 演变为 并发执行。这意味着，进程 A 的第一条指令在其生命周期内开始执行，而进程 B 在进程 A 执行完毕之前也开始了它的执行。从宏观上看，多个进程都在“运行中”的状态。

并发执行的进程之间可能存在两种关系：无关进程，进程操作各自独立的变量集合，互不干涉。一个进程的执行状态和结果不会对其他进程产生任何影响——你在系统中同时运行一个文本编辑器和一个音乐播放器，它们通常是无关的；交互进程，共享某些资源（如内存、全局变量或文件）。一个进程的行为可能会影响到另一个进程的执行结果，如，多个进程需要读取并修改同一个计数器变量。这个共享的变量所在的区域，我们称之为临界区 (Critical Section)。

对于交互进程，如果缺乏有效的控制，程序的封闭性（一个进程的执行只取决于它自己的逻辑和输入）与可再现性（相同的输入总能得到相同的结果）将被打破。这通常会导致以下两类与“时间有关的错误” (Timing Errors / Race Conditions)：

1. 结果不确定：程序的最终输出取决于进程调度器（Scheduler）碰巧选择的执行顺序。

   • 例：假设两个进程并发执行 count++ 操作，该操作在底层通常分为三步：
     1. mov eax, [count] (从内存加载 count 到寄存器 eax)
     2. inc eax (寄存器 eax 自增)
     3. mov [count], eax (将 eax 的值写回内存) 如果初始 count 为 5，两个进程并发执行，可能出现以下交错执行顺序，导致最终 count 值为 6 而非预期的 7。

        时间	进程 A	进程 B	count (内存)
        t1	mov eax, [count] (eax=5)		5
        t2	inc eax (eax=6)		5
        t3		mov eax, [count] (eax=5)	5
        t4		inc eax (eax=6)	5
        t5	mov [count], eax		6
        t6		mov [count], eax	6

2. 永远等待/死锁：两个或多个进程因互相等待对方持有的资源而陷入永久阻塞的状态。

为了解决上述问题，操作系统必须提供机制来管理进程间的交互。我们的目的是要考察两类进程关系——互斥和同步，并解决其带来的问题。互斥 (Mutual Exclusion)的两个进程是竞争 关系，他们共同使用同一资源。为了解决互斥，需要确保在任何时刻，只有一个进程能够进入临界区访问共享资源，也就是说要建立一种访问约束；同步 (Synchronization)的两个进程是协作 (Cooperation) 关系，一组进程为了完成共同任务，需要按照预定的次序来执行。这就要求我们实现执行时序的协调。

常见的实现机制包括互斥锁 (Mutex Lock)、条件变量 (Condition Variable) 以及本次实验的主角——信号量 (Semaphore)。有关这些机制的理论基础和实现细节，可以参考 第一期的操作系统笔记。

这次实验的任务呼之欲出：我们要在操作系统内核中实现信号量机制，并利用它来解决

第一步：实现P/V操作

#

理论：P/V 操作流程

#

信号量是一种比互斥锁更通用的同步工具，它不仅能实现互斥，还能用于更复杂的同步场景。信号量有两个原子操作，即 P 操作和 V 操作。

1. P 操作 (Proberen - 荷兰语"测试")

   • 别名：wait(), down(), acquire()
   • 意图：申请一个资源。
   • 执行流程：
     1. 将信号量 value 减 1。
     2. 判断 value 的新值：
        • 如果 value >= 0：表示成功申请到资源，进程可以继续执行。
        • 如果 value < 0：表示当前已无可用资源，进程必须等待。此时，需要将当前进程放入 wait_list 队列，并阻塞 (block) 该进程，放弃 CPU 使用权。

2. V 操作 (Verhogen - 荷兰语"增加")

   • 别名：signal(), up(), release()
   • 意图：释放一个资源。
   • 执行流程：
     1. 将信号量 value 加 1。
     2. 判断 value 的新值：
        • 如果 value > 0：表示之前没有进程在等待资源，现在只是单纯地增加了可用资源数量。
        • 如果 value <= 0：表示有进程正在 wait_list 中等待。此时，需要从 wait_list 中取出一个进程，并唤醒 (wakeup) 它，使其重新进入就绪队列，等待被调度器执行。

实践(1)

#

信号量的结构

#

typedef struct {
    int value;         // 整数值，用于表示可用资源的数量
    list_t wait_list;  // 一个等待队列，用于存放被阻塞的进程
} sem_t;

• value 的含义：

  • value > 0: 表示当前有 value 个可用资源。
  • value = 0: 表示当前没有可用资源。
  • value < 0: 表示当前没有可用资源，并且有 abs(value) 个进程正在 wait_list 中等待该资源。

• 进程等待队列 wait_list： 一个通用的、基于双向链表实现的队列,用来来管理等待的进程。该队列可以存储 void* 类型的指针，我们用它来存放指向进程 PCB (proc_t*) 的指针。相关的 API 已经实现：

  • void list_init(list_t *list);：初始化一个空队列。
  • list_t *list_enqueue(list_t *list, void *ptr);：将指针 ptr 插入到队列 list 的尾部。
  • void *list_dequeue(list_t *list);：从队列 list 的头部取出一个元素并返回。如果队列为空，返回 NULL。

阻塞与唤醒进程

#

1. 阻塞当前进程：调用 proc_block() 函数。这个函数会将当前正在运行的进程的状态（proc->status）从 READY 修改为 BLOCKED。然后它会调用调度器（类似于 proc_yield()）。由于调度器 schedule() 只会从 READY 状态的进程中选择下一个要运行的进程，这个被标记为 BLOCKED 的进程自然就不会再被调度执行，从而实现了阻塞。

2. 唤醒指定进程：调用 proc_addready(proc_t *proc) 函数。个函数将传入的进程 proc 的状态从 BLOCKED 修改回 READY，并将其重新加入到可调度进程的列表中。这样，调度器在下一次调度时就有机会选中这个进程来执行，从而实现了唤醒。

实现 sem_p 和 sem_v

#

现在，你需要利用上面介绍的知识和 API，在 kernel/src/sem.c 文件中完成 sem_p(sem_t *sem) 和 sem_v(sem_t *sem) 这两个函数的实现。

由于信号量的 P/V 操作需要保证原子性，所以我觉得除了wiki要求的逻辑之外，还要加上开关中断的操作包围起来。

sem_p(sem_t *sem)

#

将value减1，如果value为负代表现在没有资源，需要将当前进程添加到wait_list中并暂时阻塞该进程，等到申请到资源时再唤醒。

sem_v(sem_t *sem)

#

V操作意为释放资源，首先将value加1，如果value非正代表有进程在等待资源，需要从wait_list中取出一个进程然后唤醒它，相当于把提供的这个资源给这个进程。

第二步：利用信号量改写内核

#

我们已经拥有了一个功能完备的信号量实现。接下来，我们将利用这个强大的同步原语来改进操作系统内核中两个存在问题的部分。具体来说，我们将重构标准输入和进程等待 (wait) 的实现逻辑，用基于信号量的阻塞-唤醒模型替代原有的忙等待 (Busy-Waiting) 方案。

应用一：重构标准输入机制

#

首先，我们需要理解当前内核处理字符输入的机制。相关内核代码位于 kernel/src/serial.c 中，我们仔细考察工作流程：

1. 首先在init_serial函数中初始化串行端口；

2. 当外部设备通过串行端口输入字符时，会触发硬件中断，serial_handle函数作为中断处理程序被调用。该函数

   1. 循环调用inb函数从串行端口读取数据，只要端口有数据，便会逐个读取字符；
   2. 对读入的字符进行处理：忽略特殊键（如箭头）;处理退格键（通过pop_back从缓冲区尾部删除字符，并更新屏幕显示）;将回车符\r转换成换行符\n;对于可打印的字符和换行符，函数会调用putchar将其回显到屏幕上(这个函数也是printf实现的较为底层的方式)，然后调用push_back将字符存入一个环形缓冲区buffer中。

   buffer由几个指针进行管理：

   • head: 指向缓冲区的队头，即下一个将被读取的字符。
   • tail: 指向下一个可以写入新字符的位置。
   • clapboard: 一个特殊的“隔板”指针。它指向自上次输入回车符 (\n) 之后的位置。这个设计模拟了终端的行缓冲行为：在用户按下回车之前，输入的字符被暂存，但应用程序无法读取。getchar() 函数只能读取 [head, clapboard) 这个区间内的字符。

3. getchar() 函数用于从缓冲区中获取一个字符。它调用 pop_front() 从 head 指针位置读取字符。如果没有可读字符（即 head == clapboard），当前实现会进入一个循环，不断调用 proc_yield() 让出 CPU，直到有字符可读为止。

   while ((ch = pop_front()) == 0) {
       proc_yield();
   }
   

   这虽然不是我们在第二集中使用sti(); hlt();cli();的忙等待那样极端，但是仍然面临着并发问题：yield轮询将“检查条件”和“根据条件执行操作”分成了两个独立的步骤，在这两个步骤之间，CPU可能会切换到其他进程，从而导致竞争条件。

而信号量的sem_p操作将这两个步骤合并成了一个由操作系统内核保证的、不可中断的原子操作。信号量为我们提供了一个优雅的解决方案，可以将忙等待转换为高效的阻塞等待。这里的核心思想是将“可读取的字符”视为一种资源，把输入输出建模成一个消费者/生产者问题。

• 资源：一个在 [head, clapboard) 范围内的待处理字符。
• 生产者 (Producer)：当用户输入回车符 (\n) 时，push_back 函数会更新 clapboard 的位置(==tail)。这一刻，一批新的字符（从旧的 clapboard 位置到新的 clapboard(tail) 位置）变为“可读取”状态。因此，中断处理程序中的 push_back 函数扮演了生产者的角色。
• 消费者 (Consumer)：调用 getchar() 的进程是消费者，它希望获取一个字符资源。

我们的设计如下：

1. 定义一个信号量 serial_sem，其 value 代表当前缓冲区中可供 getchar() 读取的字符数量。
2. 在 init_serial 中，将 serial_sem 初始化为 0，因为系统启动时没有任何输入。
3. 在 push_back 函数中，当检测到输入字符为 \n 时，意味着一批字符被“释放”给消费者。此时，我们需要对 serial_sem 执行 V 操作，增加资源的计数值。增加的数量等于新变为可读的字符数，即 tail - clapboard（需要考虑环形缓冲区的边界情况）。
4. 在 getchar 函数中，我们用 sem_p(&serial_sem) 来替代原来的 while 循环。
   • 如果 serial_sem 的 value > 0，P 操作会成功返回，意味着至少有一个字符可读。进程可以安全地调用 pop_front() 并获取字符。
   • 如果 serial_sem 的 value <= 0，P 操作会自动将当前进程阻塞，并让出 CPU。进程会在此处高效地“睡眠”，直到 push_back 中执行了 V 操作将其唤醒。

应用二：重构进程等待 (wait) 机制

#

与 getchar 类似，sys_wait 系统调用的当前实现也存在并发问题——当父进程调用 sys_wait 时，如果没有子僵尸进程可供回收，它会进入一个循环，不断调用 proc_yield() 让出 CPU，直到有子僵尸进程出现为止，但问题就是while的判断和yield之间可能会被调度器切换掉，从而导致竞争条件。

proc_t* zombie = proc_findzombie(curr);
while (zombie == NULL) {
  proc_yield();
  zombie = proc_findzombie(curr);
}

现在我们使用信号量改写这部分逻辑。我们将“已终止的、待回收的子僵尸进程”也看作一种资源。

• 资源：一个属于当前进程的、处于僵尸状态的子进程。
• 生产者 (Producer)：任何一个进程，当它执行完毕或被终止，在 proc_makezombie() 函数中转变为僵尸进程时，它就为自己的父进程“生产”了一个可回收的资源。
• 消费者 (Consumer)：调用 sys_wait() 的父进程。

由于每个进程都可能拥有自己的子僵尸进程，因此这种资源是与特定进程绑定的。合理的设计是为每个进程的 PCB 都配备一个独立的信号量，专门用来管理它自己的子僵尸进程。

设计如下：

1. 在 proc_t 结构体中增加一个 sem_t zombie_sem 成员。
2. 在进程被创建时（proc_alloc() 和 init_proc()），将这个 zombie_sem 初始化为 0，因为新进程还没有任何子僵尸进程。
3. 当一个进程终止，在 proc_makezombie() 函数的最后，它需要通知其父进程。这通过对其父进程的 zombie_sem 执行一次 V 操作来实现。这相当于子进程在说：“老灯，我已经结束了，你可以来回收我了”。（注意：需要处理父进程不存在的情况）。
4. 在 sys_wait 中，父进程不再需要循环。它只需在自己的 zombie_sem 上执行 P 操作。
   • 如果已有子僵尸进程（value > 0），P 操作成功返回，父进程接着调用 proc_findzombie() 必定能找到一个并进行回收。
   • 如果没有子僵尸进程（value <= 0），P 操作将使父进程高效阻塞，直到它的某个子进程终止并对其执行 V 操作。

你可能会担心，当一个 PCB 被回收并由 proc_alloc 重新分配给新进程，zombie_sem 被初始化时，里面的等待队列中的进程会丢失，导致进程永远不会被继续运行。但是这在这里是安全的。一个进程的 zombie_sem 只会被该进程自身在调用 wait 时 P 操作（导致阻塞）。当一个进程的 PCB 可以被回收时，它必然已经终止，不可能处于阻塞在自己 zombie_sem 上的状态。因此，重复初始化时，该信号量的等待队列一定是空的，不会产生问题。

思考：为何不用信号量改写 sys_sleep？

sys_sleep 的需求是“等待一段指定的时间”，而不是等待一个可计数的资源。时间对于所有进程是共享的、流逝的，它不能像字符或僵尸进程那样被一个进程“消耗”掉。信号量的模型与“资源数量”紧密耦合，强行用于计时会非常不自然。

对于这类“等待某个条件成真”（例如，currentTime >= wakeupTime）的场景，条件变量 (Condition Variable) 是一个更合适的同步原语。它与资源数量解耦，允许进程等待任意复杂的逻辑条件，这超出了本次实验的范围，但有助于你理解不同同步工具的适用场景。不同同步工具的适用场景。

第三步：实现用户信号量

#

理论：必要性，实现方案

#

我们已经为内核实现了信号量基础设施，并用信号量对内核的一些资源进行了管理，但这还不够。用户态的应用程序，尤其是并发执行的多个进程，也常常需要同步机制来保证它们操作的先后次序。本节的目标就是构建一套完整的用户信号量机制。

说是“用户信号量”，但实际上它们的实现仍然在内核中完成（因为资源管理当然是操作系统的工作）（好像有点废话）。然而，内核资源绝对不能直接暴露给用户进程，用户进程也绝不可以直接拿到内核中信号量结构体 (sem_t) 的地址，随意修改 value 或 wait_list——这样就让一个用户程序轻松地破坏整个系统的稳定性。

因此，我们必须引入一层抽象：在用户进程看来，一个信号量仅仅是一个非负整数句柄 (Handle) 或 ID (Identifier)，例如 0, 1, 2…。用户通过这个 ID 来告知内核它想操作哪个信号量。内核需要维护从 (进程, 信号量ID) 到实际内核信号量对象的映射关系。这种映射关系必须是进程隔离的。如果进程 A 和进程 B 碰巧都使用了 ID 为 5 的信号量，内核必须确保它们操作的是各自独立的信号量对象，除非它们之间有明确的共享关系。

既然信号量表是进程隔离的，那么两个独立的进程如何才能访问到同一个信号量以实现同步呢？

我们的设计约定：只有存在亲缘关系的进程（如父子、兄弟进程）才能共享信号量。这个机制通过 fork 系统调用来自然地实现：

• 当父进程调用 fork 创建子进程时，子进程会继承父进程的用户信号量表。
• 这意味着，如果父进程中 ID 为 s 的句柄指向内核中的信号量对象 S，那么在 fork 之后，子进程中 ID 为 s 的句柄也会指向同一个内核信号量对象 S。

这样，父子进程就可以通过同一个 ID 来操作同一个信号量，从而实现同步。

如何实现？

#

从几个数据结构说起：

1. 用户信号量的数据结构 (usem_t)

#

为了管理这些可能被多个进程共享的信号量，我们引入一个新的结构体 usem_t (位于 kernel/include/sem.h)，它包装了内核信号量：

// 概念性结构
typedef struct {
    sem_t sem; // 底层的、真正的内核信号量
    int ref;   // 引用计数 (Reference Count)
} usem_t;

• ref 字段至关重要，它记录了当前有多少个进程的信号量表正在引用这个 usem_t 对象。
  • 当一个 usem_t 被新创建时 (sem_open)，ref 初始化为 1。
  • 当一个进程 fork 时，子进程继承了父进程的信号量表，所有被继承的 usem_t 对象的 ref 都需要加 1。
  • 当一个进程关闭一个信号量句柄 (sem_close) 或进程退出时，它引用的 usem_t 对象的 ref 需要减 1。
  • 只有当 ref 减为 0 时，这个 usem_t 对象才能被认为是“空闲的”，可以被重新分配给新的 sem_open 请求。

2. 全局用户信号量池 (user_sem[])

#

内核需要一个地方来存放所有这些 usem_t 对象。我们预先分配一个全局数组 user_sem，它就是内核中所有可供用户使用的信号量的“资源池”。

管理这个资源池需要三个核心函数：

• usem_alloc(int value): 遍历 user_sem 数组，找到一个 ref 为 0 的 usem_t 对象（即空闲对象）。初始化它的 sem 成员，将 ref 置为 1，并返回指向它的指针。如果找不到，则返回 NULL。
• usem_dup(usem_t *usem): 非常简单，usem->ref++。当 fork 复制信号量表时调用。
• usem_close(usem_t *usem): 对应地，usem->ref--。当进程关闭句柄或退出时调用。

3. 进程的用户信号量表 (proc_t->usems)

#

每个进程如何维护它自己的“ID到信号量对象”的映射？这通过在 proc_t 结构体中增加一个数组成员 usems 来实现：

// 在 proc_t 结构体中
usem_t *usems[MAX_USEM]; // MAX_USEM 通常是 32

• 这个数组的下标就是用户程序看到的信号量 ID。
• 数组中存储的内容是一个指向全局 user_sem 池中某个 usem_t 对象的指针。
• 如果 proc->usems[i] == NULL，表示 ID 为 i 的句柄是未使用的。

4. 进程生命周期中对 usems 的管理

#

• 创建 proc_alloc: 新进程的 usems 数组必须被完全初始化为 NULL。
• 复制 proc_copycurr: 在 fork 过程中，子进程的 usems 表需要复制父进程的。对每一个非 NULL 的表项，不仅要复制指针，还必须调用 usem_dup() 来增加底层 usem_t 对象的引用计数。
• 销毁 proc_makezombie: 在进程退出时 (exit 系统调用最终会走到 proc_makezombie)，必须遍历该进程的 usems 表，对所有非 NULL 的表项调用 usem_close()，释放该进程对这些信号量的引用。

5. 进程信号量表辅助函数

#

为了方便管理 usems 表，还需要实现两个辅助函数。这两个函数是翻译用户的需求到内核的操作，是二者的桥梁。

• int proc_allocusem(proc_t *proc): 回应用户初始化一个信号量的需求。遍历 proc->usems 数组，找到第一个为 NULL 的位置，并返回其下标（即一个新的、可用的信号量ID）。如果表满了，返回 -1。
• usem_t *proc_getusem(proc_t *proc, int sem_id): 回应用户获取一个特定句柄的信号量的需求。检查 sem_id 是否在合法范围内（0 到 MAX_USEM-1），然后返回 proc->usems[sem_id]。

具体实现

#

syscall.c

#

• int sys_sem_open(int value)

  1. 为当前进程分配一个信号量ID：调用 proc_allocusem()。如果失败（返回-1），则系统调用失败。
  2. 从全局池中分配一个 usem_t 对象：调用 usem_alloc(value)。如果失败（返回NULL），则系统调用失败。
  3. 将两者关联起来：proc_curr()->usems[new_id] = new_usem;。
  4. 向用户返回 new_id。

• int sys_sem_p(int sem_id)

  1. 将 sem_id 翻译成 usem_t 指针：调用 proc_getusem(proc_curr(), sem_id)。
  2. 如果返回 NULL（ID无效或越界），则系统调用失败。
  3. 否则，对 usem->sem 执行 sem_p() 操作。
  4. 返回成功 (0)。

• int sys_sem_v(int sem_id)

  • 逻辑与 sys_sem_p 几乎一样，只是最后一步调用 sem_v()。

• int sys_sem_close(int sem_id)

  1. 翻译 sem_id：调用 proc_getusem()，失败则返回-1。
  2. 关闭引用：对获取到的 usem_t 指针调用 usem_close()。
  3. 清空进程表中的条目：proc_curr()->usems[sem_id] = NULL;，这样该 ID 就可被后续的 sem_open 重新使用。
  4. 返回成功 (0)。

sem.c

#

• usem_alloc(int value): 遍历 user_sem 数组，找到第一个 ref == 0 的元素，初始化其 sem 和 ref，然后返回指针。
• usem_dup(usem_t *usem): 增加 usem->ref 的引用计数。
• usem_close(usem_t *usem): 减少 usem->ref 的引用计数。

proc.c

#

• proc_alloc(): 在函数内，为新分配的 proc_t 初始化 usems 数组，将所有元素设为 NULL。
• proc_copycurr(): 遍历父进程的 usems 表。对于每个非 NULL 的项 parent->usems[i]，将子进程的对应项 child->usems[i] 指向同一个 usem_t，并调用 usem_dup() 增加引用计数。
• proc_makezombie(): 遍历垂死进程的 usems 表，对每个非 NULL 的项调用 usem_close()。
• proc_allocusem(proc_t *proc): 遍历 proc->usems，返回第一个 NULL 的下标，若无则返回 -1。
• proc_getusem(proc_t *proc, int sem_id): 实现下标检查，然后返回 proc->usems[sem_id]。