Lec12 Coordination

sleep 与 wakeup。

Published

2024-04-06

Modified

2024-10-23

1 课前准备

Read remainder of “Scheduling”, and corresponding parts of kernel/proc.c, kernel/sleeplock.c.

1.1 sleep 和 wakeup

进程睡眠允许内核线程等待特定事件，让出的 CPU 可以去做其他的工作，待事件回复时唤醒进程。

考虑生产者-消费者问题，使用锁的实现为：

struct semaphore {
    struct spinlock lock;
    int count;
};

void V(struct semaphore *s)
{
    acquire(&s->lock);
    s->count += 1;
    release(&s->lock);
}

void P(struct semaphore *s)
{
    while(s->count == 0);
    acquire(&s->lock);
    s->count -= 1;
    release(&s->lock);
}

以上的实现是开销很大的，当生产者生产效率很低时，持续高速的询问会耗费很多资源。我们引入 sleep 和 wakeup 机制：

void V(struct semaphore *s)
{
    acquire(&s->lock);
    s->count += 1;
    wakeup(s);
    release(&s->lock);
}

void P(struct semaphore *s)
{
    while(s->count == 0)
        sleep(s);
    acquire(&s->lock);
    s->count -= 1;
    release(&s->lock);
}

当消费者没有得到资源时，睡觉，等到生产者生产了资源再唤醒消费者。但这样有一个问题：lost wakeup。考虑刚刚执行完第 11 行，正准备执行下一行时，第二个线程在消费者上执行，它唤醒了一个不存在的信号量，因此无事发生。但实际上这个信号量正是第 12 行将要送去睡觉的那个。此时第 12 行被执行，但是它由于已经在睡觉之前被唤醒过，再也无法被唤醒，系统停摆。

为了修复这个错误，我们需要将第 11 到 12 行变为一个原子操作。一个可能的想法是，将消费者的 acquire 提前到最开始，但这又会导致死锁的问题：睡眠的线程由于一直持有锁，唤醒线程无法获取锁。因此我们需要在线程睡眠时同时释放锁，这导出了我们最终的实现：

void V(struct semaphore *s)
{
    acquire(&s->lock);
    s->count += 1;
    wakeup(s);
    release(&s->lock);
}

void P(struct semaphore *s)
{
    acquire(&s->lock);
    while(s->count == 0)
        sleep(s, &s->lock);
    s->count -= 1;
    release(&s->lock);
}

1.2 Code: sleep and wakeup

基本思想是让 sleep 将当前进程标记为 SLEEPING，然后调用 sched 释放 CPU；wakeup 查找在给定等待 channel 上休眠的进程并将其标记为 RUNNABLE。睡眠和唤醒的呼叫者可以使用任何彼此方便的号码作为 channel，xv6 经常使用参与等待的内核数据结构的地址。

有时会出现多个进程在同一个通道上休眠的情况；例如，多个进程从管道读取数据。一次唤醒调用即可将它们全部唤醒。其中一个将首先运行并获取调用 sleep 所用的锁，并且读取管道中等待的任何数据。其他进程会发现，尽管被唤醒，却没有数据可读取。从他们的角度来看，这次唤醒是“虚假的”，他们必须再次入睡。因此，总是在检查条件的循环内调用 sleep。

1.3 Code：Wait, exit, and kill

子进程在 exit 会被设置为 ZOMBIE 状态，待父进程的 wait 重新发现它时恢复为 UNUSED，如果父进程在子进程退出之前就先退出，则子进程会被交给 init 进程，它会永久调用 wait，因此每个子进程都需要一个父进程来清理。

wait 通过获取 wait_lock 开始，wait_lock 充当条件锁，有助于确保父级不会错过退出子级的唤醒。然后 wait 扫描进程表。如果它发现一个处于 ZOMBIE 状态的子进程，它会释放该子进程的资源及其 proc 结构，将子进程的退出状态复制到提供给 wait 的地址（如果不为 0），并返回子进程的进程 ID。如果 wait 找到子进程但没有退出，它会调用 sleep 来等待它们中的任何一个退出，然后再次扫描。 wait 经常持有两个锁，wait_lock 和某些进程的 pp->lock；避免死锁的顺序是先 wait_lock，然后 pp->lock。

exit 记录退出状态，释放一些资源，调用 reparent 把子进程给 init 进程，唤醒父进程，然后将调用者标记为僵尸，然后永久让出 CPU。在将其状态设置为 ZOMBIE 之前，exit 就唤醒父进程可能看起来不正确，但这是安全的：虽然唤醒可能会导致父进程运行，但 wait 中的循环因为没有获取到 p->lock 而无法进行检查，直到 p->lock 被 scheduler 释放。

exit 允许进程自行终止，而 kill 则允许一个进程请求另一个进程终止。如果直接销毁受害者进程，kill 会太复杂，因为受害者可能正在另一个 CPU 上执行，也许正在对内核数据结构进行敏感的更新。因此，kill 做的事情很少：它只是设置受害者的 p->killed，如果它正在睡觉，则将其唤醒。最终，受害者将进入或离开内核，此时，如果设置了 p->killed，usertrap 中的代码将调用 exit（它通过调用 killed 进行检查）。如果受害者运行在用户空间，它很快就会通过系统调用或因为计时器（或其他设备）中断而进入内核。

如果受害者进程处于睡眠状态，kill 的 wakeup 调用将导致受害者从睡眠中恢复。这具有潜在的危险，因为正在等待的条件可能不成立。但是，xv6 对 sleep 的调用始终包含在 while 循环中，该循环在 sleep 返回后重新测试条件。一些对 sleep 的调用还会在循环中测试 p->killed，如果设置了，则放弃当前活动。只有当这种放弃是正确的时候才会这样做。

一些特定的情况下，xv6 中的 sleep 循环不会检查进程控制块中的 killed 标志。这是因为这些代码位于一个多步系统调用的中间阶段，而这些阶段应该是原子性的。其中一个例子是 virtio 驱动程序，它没有检查 p->killed，因为磁盘操作可能是一组写操作中的一个，而这些写操作都是为了使文件系统处于正确状态而必要的。如果一个进程在等待磁盘 I/O 时被终止，它将不会退出，直到完成当前的系统调用，并且用户 trap 发现了 killed 标志。

1.4 进程锁

与每个进程关联的锁 (p->lock) 是 xv6 中最复杂的锁。考虑 p->lock 的一个简单方法是，在读取或写入以下任何 struct proc 字段时必须保持它：p->state、p->chan、p->killed、p->xstate 和 p ->pid。这些字段可以由其他进程或其他核心上的调度程序线程使用，因此它们很自然地必须受到锁的保护。

然而，p->lock 的大多数用途都是保护 xv6 进程数据结构和算法的更高级别方面。这是 p->lock 所做的全套事情：

防止进程槽位分配竞争：p->lock 与 p->state 一起，防止在为新进程分配 proc[] 槽位时出现竞争。
隐藏进程：在进程创建或销毁期间，p->lock 将进程隐藏起来，防止外部观察到它的存在。
防止父进程等待收集僵尸进程：防止父进程的 wait 调用收集到已经将状态设置为 ZOMBIE 但尚未让出 CPU 的进程。
防止另一个内核调度器在进程调用 swtch 之前运行 RUNNABLE 进程。
防止定时器中断导致进程在调用 swtch 时让出 CPU。
与条件锁一起防止 wakeup 忽略正在调用 sleep 但尚未让出 CPU 的进程。
防止 kill 的受害进程退出，并可能在 kill 检查 p->pid 和设置 p->killed 之间重新分配。
使 kill 的检查和写入 p->state 具有原子性。

此外，p->parent 字段由全局锁 wait_lock 保护，而不是由 p->lock 保护。只有进程的父进程修改 p->parent，尽管该字段既由进程自身读取，也由其他搜索其子进程的进程读取。wait_lock 的作用是在 wait 等待任何子进程退出时作为条件锁。退出的子进程会持有 wait_lock 或 p->lock，直到将其状态设置为 ZOMBIE，唤醒其父进程并让出 CPU 之后才会释放。wait_lock 还串行化了父进程和子进程的并发退出，以确保 init 进程能够从其等待中被唤醒。wait_lock 是一个全局锁，而不是每个父进程的单独锁，因为在一个进程获得它之前，它无法知道谁是其父进程。

1.5 Real World

xv6调度器实现了一个简单的调度策略，它依次运行每个进程。此策略称为 round robin。真实的操作系统实施更复杂的策略，例如允许进程具有优先级。这个想法是，调度程序将优先选择可运行的高优先级进程，而非可运行的低优先级进程。这些策略可能很快就会变得复杂，因为经常存在相互竞争的目标：例如，操作系统可能还希望保证公平性和高吞吐量。此外，复杂的策略可能会导致意外的交互，例如优先级反转 (priority inversion) 和 convoys。当低优先级进程和高优先级进程都使用特定的锁时，就会发生优先级反转，当低优先级进程获取该锁时，会阻止高优先级进程取得进展。当许多高优先级进程正在等待获取共享锁的低优先级进程时，就会形成一长串等待进程；convoys 一旦形成，就可以持续很长时间。为了避免此类问题，复杂的调度程序需要额外的机制。

sleep 和 wakeup 是一种简单而有效的同步方法，但还有很多其他方法。所有这些挑战中的第一个挑战是避免我们在本章开头看到的 lost wakeup 问题。最初的 UNIX 内核的 sleep 只是禁用中断，这已经足够了，因为 UNIX 运行在单 CPU 系统上。由于 xv6 在多处理器上运行，因此它添加了显式的睡眠锁。 FreeBSD 的 msleep 采用了相同的方法。 Plan 9 的 sleep 使用回调函数，该函数在睡眠前持有调度锁的情况下运行；该功能用作睡眠状况的最后一刻检查，以避免丢失唤醒。 Linux 内核的 sleep 使用显式进程队列，称为等待队列；队列有自己的内部锁。

替代在 wakeup 中扫描整个进程集合的低效方法是使用等待队列。Plan 9 中的 sleep 和 wakeup 称之为 rendezvous point。许多线程库将这种结构称为条件变量 (condition variable)，在这种上下文中，sleep 操作和 wakeup 操作被称为 wait 和 signal。所有这些机制都共享相同的特征：在等待过程中，睡眠条件受到某种锁的保护，在睡眠期间原子地释放。

当有多个进程等待唤醒时，操作系统会调度所有这些进程，它们会竞争检查睡眠条件。这种行为的进程有时被称为 thundering herd，最好避免。大多数条件变量都有两个方法来唤醒等待的进程：signal 唤醒一个进程，broadcast 唤醒所有等待的进程。

信号量通常用于同步。计数通常对应于诸如管道缓冲区中可用字节的数量或进程拥有的僵尸子进程的数量。使用显式计数作为抽象的一部分可以避免 lost wakeup 问题，因为有一个显式的计数记录唤醒的次数。

在操作系统中终止和清理进程引入了许多复杂性。处理深度睡眠中的受害进程的栈取消回溯需要小心，因为调用栈上的每个函数可能需要进行一些清理工作。一些语言通过提供异常机制来简化这个过程，但 C 语言不提供这种机制。

xv6 对 kill 的支持并不完全令人满意。相关的问题是，在一个线程即将进入睡眠状态时，kill 可能会设置 p->killed 并尝试唤醒此受害者。如果受害者在检查完 p->killed 之后但在调用 sleep 之前被尝试唤醒，那么受害者可能直到等待的条件发生后才会注意到 p->killed。这个时间可能很长，甚至到永远（比如受害者进程等待 console 输入，但是用户一直不输入）。

真正的操作系统会在常数时间内找到具有空闲列表的空闲 proc 结构，而不是在 allocproc 中进行线性时间搜索；xv6 只是为了简单起见。

2 Lecture

并无新鲜事。

--- title: "Lec12 Coordination" order: 12 date: 2024-4-6 date-modified: last-modified description: "sleep 与 wakeup。" --- ## 课前准备 > Read remainder of "Scheduling", and corresponding parts of `kernel/proc.c`, `kernel/sleeplock.c`. ### sleep 和 wakeup 进程睡眠允许内核线程等待特定事件，让出的 CPU 可以去做其他的工作，待事件回复时唤醒进程。考虑生产者-消费者问题，使用锁的实现为： ``` c struct semaphore { struct spinlock lock; int count; }; void V(struct semaphore *s) { acquire(&s->lock); s->count += 1; release(&s->lock); } void P(struct semaphore *s) { while(s->count == 0); acquire(&s->lock); s->count -= 1; release(&s->lock); } ``` 以上的实现是开销很大的，当生产者生产效率很低时，持续高速的询问会耗费很多资源。我们引入 sleep 和 wakeup 机制： ``` {.c code-line-numbers="true"} void V(struct semaphore *s) { acquire(&s->lock); s->count += 1; wakeup(s); release(&s->lock); } void P(struct semaphore *s) { while(s->count == 0) sleep(s); acquire(&s->lock); s->count -= 1; release(&s->lock); } ``` 当消费者没有得到资源时，睡觉，等到生产者生产了资源再唤醒消费者。但这样有一个问题：lost wakeup。考虑刚刚执行完第 11 行，正准备执行下一行时，第二个线程在消费者上执行，它唤醒了一个不存在的信号量，因此无事发生。但实际上这个信号量正是第 12 行将要送去睡觉的那个。此时第 12 行被执行，但是它由于已经在睡觉之前被唤醒过，再也无法被唤醒，系统停摆。为了修复这个错误，我们需要将第 11 到 12 行变为一个原子操作。一个可能的想法是，将消费者的 `acquire` 提前到最开始，但这又会导致死锁的问题：睡眠的线程由于一直持有锁，唤醒线程无法获取锁。因此我们需要在线程睡眠时同时释放锁，这导出了我们最终的实现： ``` c void V(struct semaphore *s) { acquire(&s->lock); s->count += 1; wakeup(s); release(&s->lock); } void P(struct semaphore *s) { acquire(&s->lock); while(s->count == 0) sleep(s, &s->lock); s->count -= 1; release(&s->lock); } ``` ### Code: sleep and wakeup 基本思想是让 `sleep` 将当前进程标记为 `SLEEPING`，然后调用 `sched` 释放 CPU；`wakeup` 查找在给定等待 channel 上休眠的进程并将其标记为 `RUNNABLE`。睡眠和唤醒的呼叫者可以使用任何彼此方便的号码作为 channel，xv6 经常使用参与等待的内核数据结构的地址。有时会出现多个进程在同一个通道上休眠的情况；例如，多个进程从管道读取数据。一次唤醒调用即可将它们全部唤醒。其中一个将首先运行并获取调用 `sleep` 所用的锁，并且读取管道中等待的任何数据。其他进程会发现，尽管被唤醒，却没有数据可读取。从他们的角度来看，这次唤醒是“虚假的”，他们必须再次入睡。因此，总是在检查条件的循环内调用 `sleep`。 ### Code：Wait, exit, and kill 子进程在 `exit` 会被设置为 `ZOMBIE` 状态，待父进程的 `wait` 重新发现它时恢复为 `UNUSED`，如果父进程在子进程退出之前就先退出，则子进程会被交给 `init` 进程，它会永久调用 `wait`，因此每个子进程都需要一个父进程来清理。 `wait` 通过获取 `wait_lock` 开始，`wait_lock` 充当条件锁，有助于确保父级不会错过退出子级的唤醒。然后 `wait` 扫描进程表。如果它发现一个处于 `ZOMBIE` 状态的子进程，它会释放该子进程的资源及其 `proc` 结构，将子进程的退出状态复制到提供给 `wait` 的地址（如果不为 0），并返回子进程的进程 ID。如果 `wait` 找到子进程但没有退出，它会调用 `sleep` 来等待它们中的任何一个退出，然后再次扫描。 `wait` 经常持有两个锁，`wait_lock` 和某些进程的 `pp->lock`；避免死锁的顺序是先 `wait_lock`，然后 `pp->lock`。 `exit` 记录退出状态，释放一些资源，调用 `reparent` 把子进程给 `init` 进程，唤醒父进程，然后将调用者标记为僵尸，然后永久让出 CPU。在将其状态设置为 `ZOMBIE` 之前，`exit` 就唤醒父进程可能看起来不正确，但这是安全的：虽然唤醒可能会导致父进程运行，但 `wait` 中的循环因为没有获取到 `p->lock` 而无法进行检查，直到 `p->lock` 被 `scheduler` 释放。 `exit` 允许进程自行终止，而 `kill` 则允许一个进程请求另一个进程终止。如果直接销毁受害者进程，`kill` 会太复杂，因为受害者可能正在另一个 CPU 上执行，也许正在对内核数据结构进行敏感的更新。因此，`kill` 做的事情很少：它只是设置受害者的 `p->killed`，如果它正在睡觉，则将其唤醒。最终，受害者将进入或离开内核，此时，如果设置了 `p->killed`，`usertrap` 中的代码将调用 `exit`（它通过调用 `killed` 进行检查）。如果受害者运行在用户空间，它很快就会通过系统调用或因为计时器（或其他设备）中断而进入内核。如果受害者进程处于睡眠状态，`kill` 的 `wakeup` 调用将导致受害者从睡眠中恢复。这具有潜在的危险，因为正在等待的条件可能不成立。但是，xv6 对 `sleep` 的调用始终包含在 `while` 循环中，该循环在 `sleep` 返回后重新测试条件。一些对 `sleep` 的调用还会在循环中测试 `p->killed`，如果设置了，则放弃当前活动。只有当这种放弃是正确的时候才会这样做。一些特定的情况下，xv6 中的 `sleep` 循环不会检查进程控制块中的 `killed` 标志。这是因为这些代码位于一个多步系统调用的中间阶段，而这些阶段应该是原子性的。其中一个例子是 `virtio` 驱动程序，它没有检查 `p->killed`，因为磁盘操作可能是一组写操作中的一个，而这些写操作都是为了使文件系统处于正确状态而必要的。如果一个进程在等待磁盘 I/O 时被终止，它将不会退出，直到完成当前的系统调用，并且用户 trap 发现了 `killed` 标志。 ### 进程锁与每个进程关联的锁 (`p->lock`) 是 xv6 中最复杂的锁。考虑 `p->lock` 的一个简单方法是，在读取或写入以下任何 `struct proc` 字段时必须保持它：`p->state`、`p->chan`、`p->killed`、`p->xstate` 和 `p ->pid`。这些字段可以由其他进程或其他核心上的调度程序线程使用，因此它们很自然地必须受到锁的保护。然而，`p->lock` 的大多数用途都是保护 xv6 进程数据结构和算法的更高级别方面。这是 `p->lock` 所做的全套事情： 1. 防止进程槽位分配竞争：`p->lock` 与 `p->state` 一起，防止在为新进程分配 `proc[]` 槽位时出现竞争。 2. 隐藏进程：在进程创建或销毁期间，`p->lock` 将进程隐藏起来，防止外部观察到它的存在。 3. 防止父进程等待收集僵尸进程：防止父进程的 `wait` 调用收集到已经将状态设置为 `ZOMBIE` 但尚未让出 CPU 的进程。 4. 防止另一个内核调度器在进程调用 `swtch` 之前运行 `RUNNABLE` 进程。 5. 防止定时器中断导致进程在调用 `swtch` 时让出 CPU。 6. 与条件锁一起防止 `wakeup` 忽略正在调用 `sleep` 但尚未让出 CPU 的进程。 7. 防止 `kill` 的受害进程退出，并可能在 `kill` 检查 `p->pid` 和设置 `p->killed` 之间重新分配。 8. 使 `kill` 的检查和写入 `p->state` 具有原子性。此外，`p->parent` 字段由全局锁 `wait_lock` 保护，而不是由 `p->lock` 保护。只有进程的父进程修改 `p->parent`，尽管该字段既由进程自身读取，也由其他搜索其子进程的进程读取。`wait_lock` 的作用是在 `wait` 等待任何子进程退出时作为条件锁。退出的子进程会持有 `wait_lock` 或 `p->lock`，直到将其状态设置为 `ZOMBIE`，唤醒其父进程并让出 CPU 之后才会释放。`wait_lock` 还串行化了父进程和子进程的并发退出，以确保 `init` 进程能够从其等待中被唤醒。`wait_lock` 是一个全局锁，而不是每个父进程的单独锁，因为在一个进程获得它之前，它无法知道谁是其父进程。 ### Real World xv6调度器实现了一个简单的调度策略，它依次运行每个进程。此策略称为 **round robin**。真实的操作系统实施更复杂的策略，例如允许进程具有优先级。这个想法是，调度程序将优先选择可运行的高优先级进程，而非可运行的低优先级进程。这些策略可能很快就会变得复杂，因为经常存在相互竞争的目标：例如，操作系统可能还希望保证公平性和高吞吐量。此外，复杂的策略可能会导致意外的交互，例如**优先级反转** (priority inversion) 和 **convoys**。当低优先级进程和高优先级进程都使用特定的锁时，就会发生优先级反转，当低优先级进程获取该锁时，会阻止高优先级进程取得进展。当许多高优先级进程正在等待获取共享锁的低优先级进程时，就会形成一长串等待进程；convoys 一旦形成，就可以持续很长时间。为了避免此类问题，复杂的调度程序需要额外的机制。 `sleep` 和 `wakeup` 是一种简单而有效的同步方法，但还有很多其他方法。所有这些挑战中的第一个挑战是避免我们在本章开头看到的 lost wakeup 问题。最初的 UNIX 内核的 `sleep` 只是禁用中断，这已经足够了，因为 UNIX 运行在单 CPU 系统上。由于 xv6 在多处理器上运行，因此它添加了显式的睡眠锁。 FreeBSD 的 `msleep` 采用了相同的方法。 Plan 9 的 `sleep` 使用回调函数，该函数在睡眠前持有调度锁的情况下运行；该功能用作睡眠状况的最后一刻检查，以避免丢失唤醒。 Linux 内核的 `sleep` 使用显式进程队列，称为等待队列；队列有自己的内部锁。替代在 `wakeup` 中扫描整个进程集合的低效方法是使用等待队列。Plan 9 中的 `sleep` 和 `wakeup` 称之为 rendezvous point。许多线程库将这种结构称为条件变量 (condition variable)，在这种上下文中，`sleep` 操作和 `wakeup` 操作被称为 `wait` 和 `signal`。所有这些机制都共享相同的特征：在等待过程中，睡眠条件受到某种锁的保护，在睡眠期间原子地释放。当有多个进程等待唤醒时，操作系统会调度所有这些进程，它们会竞争检查睡眠条件。这种行为的进程有时被称为 thundering herd，最好避免。大多数条件变量都有两个方法来唤醒等待的进程：`signal` 唤醒一个进程，`broadcast` 唤醒所有等待的进程。信号量通常用于同步。计数通常对应于诸如管道缓冲区中可用字节的数量或进程拥有的僵尸子进程的数量。使用显式计数作为抽象的一部分可以避免 lost wakeup 问题，因为有一个显式的计数记录唤醒的次数。在操作系统中终止和清理进程引入了许多复杂性。处理深度睡眠中的受害进程的栈取消回溯需要小心，因为调用栈上的每个函数可能需要进行一些清理工作。一些语言通过提供异常机制来简化这个过程，但 C 语言不提供这种机制。 xv6 对 `kill` 的支持并不完全令人满意。相关的问题是，在一个线程即将进入睡眠状态时，`kill` 可能会设置 `p->killed` 并尝试唤醒此受害者。如果受害者在检查完 `p->killed` 之后但在调用 `sleep` 之前被尝试唤醒，那么受害者可能直到等待的条件发生后才会注意到 `p->killed`。这个时间可能很长，甚至到永远（比如受害者进程等待 `console` 输入，但是用户一直不输入）。真正的操作系统会在常数时间内找到具有空闲列表的空闲 `proc` 结构，而不是在 `allocproc` 中进行线性时间搜索；xv6 只是为了简单起见。 ## Lecture 并无新鲜事。