Toki

lec12 Coordination

Coordination

Coordination

课前准备

调度和锁机制帮助掩盖了一个进程的存在对另一个进程的影响，但到目前为止，我们还没有任何抽象来帮助进程有意地进行交互。

进程交互：条件同步

Xv6 使用了一种称为 sleep 和 wakeup 的机制，这允许一个进程在等待某个事件时进入睡眠状态，并在事件发生后由另一个进程将其唤醒。这种机制也被称为 序列协调 或 条件同步机制。

引入：信号量

它用于协调生产者和消费者。信号量维护一个计数，并提供两种操作：

“V” 操作（针对生产者）用于增加计数；
“P” 操作（针对消费者）则等待计数值非零，然后递减计数并返回。

如果只有一个生产者线程和一个消费者线程，并且它们在不同的 CPU 上执行，且编译器没有过度优化，那么这种实现是正确的：

消费者会浪费大量的时间在轮询上，我们希望有一种机制，在count为0时消费者主动让出CPU，在需要时唤醒消费者使其开始执行工作

优化轮询：sleep & wakeup

假设有一对 sleep 和 wakeup 的调用，工作方式如下：

sleep(chan) 在一个任意值 chan（称为等待通道）上休眠
wakeup(chan) 唤醒所有在 chan 上休眠的进程（如果有），使它们的 sleep 调用返回。
- 如果没有进程在 chan 上等待，wakeup 不做任何事情。

这段代码看起来没问题，但也有这样一种情况：while的判定后，sleep调用前，如果count变为了非0，并想要唤醒一个线程，但此时没有睡眠线程，于是什么都不做；而后消费者调用 sleep 进入睡眠，于是便错过了这次唤醒。这被称为 lost wake-up 丢失唤醒

问题的根源在于，P 只在 s->count == 0 时才睡眠的这个不变量被 V 在恰好错误的时刻运行所破坏了。

一个错误的解决方法是上移锁的位置，这会导致死锁，消费者睡眠时，生产者永远也获取不了锁：

我们需要修改 sleep 接口，传递一个锁进去：进程休眠后，释放这个锁；再次被唤醒时，也即 sleep 返回前，获取这个锁

如此，我们同时保证了条件判定，以及睡眠这两个操作的原子性

Code: Sleep and wakeup

sleep的基本思路是，sleep 中释放锁，然后标记进程状态为 sleeping，在特定 channel 上等待唤醒。然后切换线程。从 sched 返回后获取该锁

wakeup的基本思路是，寻找一个指定通道上的 sleeping 的进程，将其标记为 runable

二者可以使用任何数字作为通道

sleep

在开头需要获取进程的锁，此时同时持有进程锁和信号量锁——这是必要的，在进程睡眠前我们不能让任何人修改我们的信号量并唤醒我们的进程

一旦获取了进程锁，我们就可以释放信号量锁——因为唤醒一个进程前，需要获取该进程的锁。从而我们避免了丢失唤醒

一个小问题：死锁。如果进程锁和信号量锁/条件锁是同一个，那么这个sleep中就会发生死锁

现在我们就可以修改进程的状态：channel 和 state

wakeup

某个时刻，生产者会获取条件锁，修改信号量，然后调用 wakeup 唤醒这个 channel 上的线程

wakeup 遍历进程列表，寻找当前 channel 上 sleeping 的线程，将其唤醒（即state设为runable）。

在这个过程中需要先获取进程锁，以保证不变量的有效性

为什么双锁可以确保不丢失唤醒？

对于 sleep，从判定条件一直到进程睡眠前，在这个临界区内本线程要么持有进程锁，要么持有条件锁，要么二者同时持有

对于 wakeup，获取当前的进程状态前，其必定已经持有了条件锁和进程锁，这保证了唤醒线程时，没有任何线程处于判定条件和睡眠前的临界区，从而可以安全地唤醒线程

唤醒多个线程与伪唤醒

有时会有多个进程在同一个通道上休眠，wakeup 会将它们全部唤醒。但在另一个成功获取条件锁的进程释放它前，所有其他进程都会被卡在 acquire 这一步

当某个进程成功通过后，如果信号量已经被消耗掉了，他会再次进入睡眠，这是一个 伪唤醒

Code: Pipes

struct pipe

使用一个管道锁，一个循环缓冲区，一个读一个写指针。

缓冲区满即 nwrite == nread + PIPESIZE，空即 nwrite == nread，读取时需要通过 buf[nread % PIPESIZE]，write同理

pipewrite

pipewrite 先获取管道锁，然后一个个拷贝字节到管道的缓冲区中。

在这个过程中，如果缓冲区满则唤醒消费者，然后生产者进入睡眠并释放掉管道锁

piperead

piperead 首先获取管道锁，在缓冲区非空时将数据一个一个读取到目标地址

若读取完毕，则唤醒可能存在的生产者，让他继续干活；然后释放掉管道锁并返回

双通道与多进程唤醒

不同的休眠通道高效的区分了读写，避免了冲突，也方便代码的编写

在不太可能出现大量读取者和写入者同时等待同一个管道的情况下，这可能使系统更高效。除了第一个进程，其他进程都会被伪唤醒

Code: Wait, exit, and kill

利用 sleep 和 wakeup 可以实现很多功能，比如 wait

wait 概述

子进程死亡时，父进程可能正在 wait 中睡眠、或在进行其他操作，即便是后一种，父进程也应在后续的 wait 中注意到子进程的死亡

通过 exit 退出的进程被 xv6 置于 ZOMBIE 状态，父进程使用 wait 注意到后，将子进程的状态置为 UNUSED，复制其退出状态，返回退出子进程的PID

如果父进程先于子进程退出，那么子进程会被托管给 init 进程来进行后续的清理工作。所以每个进程都会有父进程进行清理工作

主要的问题在于父进程和子进程的 wait 和 exit，exit 和 exit 之间的竞争和死锁

wait：代码

wait 使用进程锁作为条件锁。

先获取它，然后遍历进程表；

如果有子进程，若为ZOMBIE则释放它的资源、拷贝返回状态、返回pid；否则睡眠等待一个子进程退出，使用当前进程作为信号量；

若没有子进程，则释放条件锁并返回

先父后子：避免死锁

wait 中使用了父进程的锁和子进程的锁，它们的获取顺序必须是固定的，即先父进程，后子进程

parent：死锁 or not

在不持有子进程锁的情况下查看 parent 可能导致死锁：如果pp的parent就是它自己

但是如果一个进程的 parent 只有它的 parent 可以修改的话，那么这就是安全的

exit

exit 记录退出状态、释放部分资源、将自己的子进程托管给 init、唤醒等待的父进程、标记自己为僵尸状态。

必须先获取父进程的条件锁，然后获取自己的进程锁，再更改状态，永久让出CPU

前者是防止丢失唤醒，后者是防止资源被提前被清理

这里可以刚获取了父进程锁，然后就唤醒父进程，它会被阻塞在第一步

kill

kill 直接杀死目标程序会太过复杂，因为目标程序可能处于敏感操作、另一CPU中等等状态。

因此，kill 只是设置目标进程的 p->killed，usertrap 最后尝试返回到用户空间前会检查这个属性，如果是则调用 exit

如果目标进程处于睡眠状态，kill会将其唤醒，这可能带来的一定的风险，因为目标条件并不成立。

然而，对 sleep 的调用总是被一个循环包裹用于检查条件，所以这问题不大。一些循环还会检查 p->killed，如果被设置则放弃当前活动。也有一些循环没有检查，因为该操作是一整块事务操作中的一部分，它们只会等到从 usertrap 返回时被杀死

Real World

xv6 调度策略：round robin

6的调度器实现了一种简单的调度策略，即依次运行每个进程。这种策略称为轮转法。

真正的操作系统实现了更复杂的策略，例如允许进程具有优先级。其思想是调度器会优先选择高优先级的可运行进程，而不是低优先级的可运行进程。

这些策略可能会迅速变得复杂，因为往往存在相互竞争的目标：例如，操作系统可能还希望保证公平性和高吞吐量。

复杂的策略可能导致意想不到的交互，例如优先级反转和队列效应。优先级反转可能发生在低优先级进程和高优先级进程共享一个锁时，当低优先级进程获取该锁后，可能会阻止高优先级进程的进展。当许多高优先级进程都在等待一个获取共享锁的低优先级进程时，可能会形成一个长队列；一旦形成，这个队列可能会持续很长时间。为了避免这些问题，复杂的调度器中需要额外的机制。

其他同步方法

睡眠（sleep）和唤醒（wakeup）是一种简单而有效的同步方法，但还有许多其他方法。

所有这些方法的首要挑战都是避免“丢失唤醒”问题

channel 查找

在唤醒过程中扫描整个进程列表以查找匹配的通道（chan）的进程是低效的。

更好的解决方案是将睡眠和唤醒中的通道替换为一种数据结构，该结构保存睡眠在该结构上的进程列表，例如等待队列

所有这些机制都有一个共同点：睡眠条件受到某种类型的锁的保护，该锁在睡眠时原子性地释放。

wakeup

xv6 的唤醒会引发一堆指定通道上的进程苏醒，他们中的大多数都是不必要苏醒的，这被称为 thundering herd

大多数条件变量具有两种唤醒原语：信号（signal），唤醒一个进程；广播（broadcast），唤醒所有等待的进程。

semaphore

信号量（semaphore）通常用于同步。

它的计数作为抽象的一部分可以避免“丢失唤醒”问题：有一个显式的唤醒次数。计数还可以避免虚假唤醒和雷鸣般的群体问题。

终止进程

终止进程并清理它们在xv6中引入了很多复杂性。

在大多数操作系统中，这甚至更加复杂，因为例如目标进程可能在内核深处处于睡眠状态，解除其堆栈需要非常谨慎的编程。

许多操作系统使用显式的异常处理机制（如longjmp）来解除堆栈。

xv6对kill的支持并不完全令人满意：有些睡眠循环可能应该检查p->killed。一个相关的问题是，即使对于检查p->killed的睡眠循环，睡眠和kill之间仍存在竞争；后者可能在受害者的循环检查p->killed之后但在它调用睡眠之前设置p->killed并尝试唤醒受害者。如果发生这种情况，受害者在它等待的条件发生之前可能不会注意到p->killed。这可能会在相当晚的时候发生（例如，当virtio驱动程序返回受害者正在等待的磁盘块时）或者永远不会发生（例如，如果受害者正在等待控制台的输入，但用户没有输入任何内容）。

信号

还有其他事件可能会导致睡眠进程被唤醒，即使它正在等待的事件尚未发生。例如，当一个Unix进程处于睡眠状态时，另一个进程可能会向它发送信号。在这种情况下，进程将以-1返回中断的系统调用，并且错误代码设置为EINTR。应用程序可以检查这些值并决定如何处理。xv6不支持信号，因此不会出现这种复杂性。

空闲进程搜索

一个真正的操作系统会通过一个显式的空闲列表在常数时间内找到空闲的proc结构，而不是在allocproc中使用线性时间搜索；xv6为了简化而使用线性扫描。

线程切换中的锁

线程切换过程中一个进程先获取自己的锁，然后调用switch函数切换到调度器线程，调度器线程再释放进程锁。

也就是这样：想要休眠时，获取自己的锁，修改自己的状态并切换到调度器，然后调度器释放自己的锁

休眠前先获取锁

防止尚未完全睡眠、切换到调度器前，被识别为 runable 并运行

swtch 不允许持有除进程锁外的锁

xv6中，调用 swtch 时，必须持有进程锁，且不能持有其他任何锁

why ?

假如一个进程持有了其他锁进入休眠，那么其他想要使用获取这把锁的进程就会永远等待——而不会被定时器中断，因为 acquire 会关闭中断。

又或者原进程重新被调度并释放这个锁——而这在单核处理器上永远也不会发生

Sleep & Wakeup：Coordination

XV6通过Sleep&Wakeup实现了coordination

引入：busy-wait

一个进程有意的在等待另一个进程产生的特定事件，一种实现方法是 busy-wait，然而事件的发生是不可预测的，无休止地等待下去过于浪费CPU资源。

我们希望在等待期间使原进程休眠，在特定事件发生后，唤醒它，即 sleep & wakeup：

uart：sleep & wakeup & channel

生产者等待 uart 发生上一个字符，sleep：

uart 发送完成，触发中断，wakeup 生产者：

uartintr 会做一些检查确保 uart 确实处于空闲状态

sleep 和 wakeup 会通过一个 channel 连接在一起。wakeup 会找到在这个 channel 上的进程，唤醒它

Sleep&wakeup的一个优点是它们可以很灵活，它们不关心代码正在执行什么操作，你不用告诉sleep函数你在等待什么事件，你也不用告诉wakeup函数发生了什么事件，你只需要匹配好64bit的sleep channel就行。

UART实际上支持一次传输4或者16个字符，所以一个更有效的驱动会在每一次循环都传输16个字符给UART，并且中断也是每16个字符触发一次。更高速的设备，例如以太网卡通常会更多个字节触发一次中断。

Lost wakeup

但实际上需要将一个锁作为第二个参数传入 sleep，我们不太可能设计一个sleep函数并完全忽略需要等待的事件。这是一种稍微丑陋的实现

遗漏唤醒

原始的方式可能在 while 判定和 sleep 前的窗口期遗漏唤醒：

调用 sleep 时持有条件锁

所以不能在 whlie 和 sleep 间留窗口期，需要预先加锁；但这样又会造成死锁，中断都打断不了：

先获取进程锁后释放条件锁

生产者需要获取锁，所以只能在 sleep 中解锁，需要传入一个参数：条件锁

修改进程状态需要进程锁，所以 sleep 还需要获取进程锁

为了防止在获取进程锁和释放条件锁的窗口期被中断、被wakeup，需要先获取进程锁后释放条件锁

最终的 sleep 长这样：

于是我们保证了 修改进程状态与释放条件锁 这两个步骤的原子性

后续 sheduler 会释放进程锁

wakeup：持两个锁时查看进程状态

wakeup 的调用者必须持有条件锁，在查看进程状态前又必须获取进程锁。

以防止在窗口期进程的状态被修改、又或者丢失 wakeup

sleep 包装在 while 中

为了防止 wakeup 唤醒一堆线程，结果部分线程是假唤醒

灵活的 sleep&wakeup

sleep和wakeup的规则稍微有点复杂。因为你需要向sleep展示你正在等待什么数据，你需要传入锁并遵循一些规则，某些时候这些规则还挺烦人的。
另一方面sleep和wakeup又足够灵活，因为它们并不需要理解对应的condition，只是需要有个condition和保护这个condition的锁。