第 14 篇已经能用时钟轮转两个计算任务，但没有输入时，键盘消费者没有可处理的数据。
反复取得时间片再检查空队列，只会重复得到同一个结果。
本篇增加 BLOCKED 状态：消费者登记等待条件后退出就绪集合，生产者改变条件时再把它变回 RUNNABLE。

关键问题发生在检查条件与登记等待之间。
若输入恰好在这段间隙到达，生产者可能发现没有等待者，随后消费者却仍按旧结果进入阻塞，形成“条件已经满足，任务仍然睡着”的丢失唤醒。
实验用真实 PIT 中断分别制造错误顺序和受保护顺序，再把同一套等待接口接到定时睡眠、idle 与持续运行的键盘任务。

阻塞任务暂时退出就绪集合

RUNNABLE 表示可以执行，BLOCKED 表示正在等某项外部条件。
两者都可能保留完整调用栈，但调度器只从 RUNNABLE 中选下一个任务。
时钟每次到来不应把所有 BLOCKED 任务重新置为就绪，否则每个任务仍要定期醒来轮询。

1
2
3
4
5
6
7
8
9
运行中的消费者
    │ 条件不满足：登记等待，保存调用续点
    ▼
BLOCKED ── 生产者改变条件并唤醒 ──→ RUNNABLE
                                        │ 调度器选中
                                        ▼
                              RUNNING：从阻塞调用返回
                                        │
                                   重新检查条件

本篇没有改变 switch_context 的栈布局。
阻塞和第 13 篇的主动让出都在普通调用边界切走，局部变量仍留在各自任务栈中。
区别在于让出者立即回到 RUNNABLE，而阻塞者要等唤醒或期限到达以后才能再次被选择。

任务对象增加 waiting_on、sleeping 和 wake_tick。
waiting_on 指向正在等待的队列；定时睡眠使用另两个字段记录登记状态和到期 tick。
当前任务只能登记一种等待，不能同时出现在事件队列与定时睡眠集合里。

三个任务槽只需要一个等待位集合

任务表仍然只有三个槽：bootstrap、事件消费者和定时睡眠任务。
等待队列用位掩码记录任务槽，不额外申请链表节点：

1
struct wait_queue { unsigned mask; };

例如 mask == 2 表示槽位 1 正在等待，槽位 2 对应位值 4。
槽位 0 留给 bootstrap/idle，不允许进入阻塞协议。
接口名保留 queue，但这里不承诺按登记先后 FIFO 唤醒；实现按任务槽从小到大查找第一个等待者。

位集合与任务字段同时表达归属。
登记要求 waiting_on 为空、没有定时睡眠，并且对应位尚未设置；唤醒要求被选任务确为 BLOCKED，且 waiting_on 指回同一个队列。
这些断言检查重复登记和元数据不一致，避免同一个任务被两条等待路径重复唤醒。

等待队列对象必须比已登记任务的等待过程活得更久。
本篇事件队列和键盘队列都是静态对象，不会在任务睡着时离开作用域。
接口并没有引用计数，也不能安全接受已经失效的栈上队列指针。

条件检查和登记等待共享一个关中断区间

正确消费者的核心顺序是保存 flags、CLI、循环检查条件、登记并阻塞，恢复后继续检查，最后消费并恢复原 flags。
以下省略故障注入，只保留调用协议：

1
2
3
4
5
6
uint32_t flags = irq_save();
while (!wait_event)
    task_block_locked(&event_waiters);
wait_event = 0;
++wait_consumed;
irq_restore(flags);

task_block_locked() 不替调用者重新检查业务条件。
它只负责登记当前任务并切走，因此调用者必须把条件判断也放在同一个 IRQ 排除区间里。
只在阻塞函数内部 CLI，会留下“外部已经判断为空，内部尚未登记”的原始间隙。

1
2
3
4
5
6
7
8
9
10
11
void task_block_locked(struct wait_queue *q)
{
    require_locked();
    struct task *t = &tasks[current];
    KASSERT(q && !t->waiting_on && !t->sleeping &&
            !(q->mask & (1u << current)));
    t->waiting_on = q;
    q->mask |= 1u << current;
    block_current();
    KASSERT(!t->waiting_on && !(q->mask & (1u << current)));
}

block_current() 要求处于普通任务调用路径、不是 bootstrap、没有 trap 嵌套和禁止抢占层数。
随后把任务改成 BLOCKED，记录阻塞次数，并调用同一个 schedule_locked()。
登记队列位和改状态之间 IF 始终为零，普通生产者 IRQ 无法在中途观察到半完成登记。

切走时 IF=0 不代表新任务必须永远关中断。
恢复过的任务按各自协议恢复 flags。新任务在 PIT 已初始化的入口开启中断，idle 使用专门的 STI/HLT 路径。
等消费者再次恢复，原来的阻塞调用先在 IF=0 下返回，由外层条件循环决定下一步。

这个原子范围依赖单 CPU，生产者只能经普通可屏蔽 IRQ 或遵守同一协议的代码进入。
CLI 不屏蔽 NMI，也不阻止另一个 CPU；本篇的原子登记不能直接作为 SMP 等待队列实现。
xv6 教材用条件与调度状态的锁交接讨论同类问题，但其 RISC-V 与多 CPU 锁协议不能直接换成本实验的 CLI。

唤醒只改变可运行资格

生产者先发布条件，再查找等待者。
实验中的 PIT 生产者将 wait_event 置一，再执行 wake_one_locked()；键盘 IRQ 则先写入原始字节队列，再调用同一唤醒接口。
等待者被选中以后会先从等待集合移除，再成为 RUNNABLE：

1
2
3
4
5
6
q->mask &= ~(1u << i);
tasks[i].waiting_on = 0;
tasks[i].state = RUNNABLE;
need_resched = 1;
++wait_wakes;
return 1;

接口返回一表示找到并唤醒一个等待者，返回零表示当时无人等待。
空集合上的唤醒不会保留一个供未来任务消费的“通知额度”。
真正持久的条件保存在 wait_event 或键盘字节队列中，消费者应当检查它们。

唤醒也不会立即跳入消费者代码。
IRQ handler 继续完成自己的工作与 EOI，再由第 14 篇的最外层退出协议处理 need_resched。
这保留了“设备处理完成后才切换”的顺序，同时允许键盘事件主动请求下一次选择。

恢复后使用 while 而非 if，因为唤醒并不授予某一份数据的独占所有权。
多个消费者可能竞争同一条件，设备错误也可能使唤醒发生时没有新增可消费字节。
当前键盘实现收到状态字节后就可能尝试唤醒，包括字节被丢弃的路径；消费者醒来发现队列仍空，应重新登记等待。

本篇事件标志只表示一份可消费条件，没有实现累加信号量。
每个阶段只安排一次生产，所以不会用一个布尔值假装保留任意多次事件。
键盘使用已有环形队列保存多个原始字节，并继续沿用队列满时的丢弃与重置协议。

用三个发生顺序检查同一条件循环

事件自检安排三个阶段，每阶段将条件清零、等待集合清空，再武装一次 PIT 生产动作。
下一次真实 timer_irq() 进入 task_tick()，由 wait_tick() 完成生产并记录唤醒返回值。
三个阶段分别覆盖生产早于检查、发生在检查与登记之间、以及登记之后。

发生位置 正确消费者的行为 生产时唤醒人数
首次条件检查之前 看到条件已真，直接消费 0
检查为空以后、登记以前到达硬件请求 IF=0，生产者尚不能进入；登记后再处理 1
已经 BLOCKED 以后 生产者找到已登记任务并置就绪 1

第一阶段主动开启中断等待生产到达，再关中断进入正式条件循环。
这段测试安排使用 HLT，不代表正常消费者每次都应先等待一个 IRQ；它只是确定事件已经先发生。
唤醒返回零在这里完全正常，因为条件循环随后能直接看到已经保存的事件。

第三阶段不插入特殊窗口，消费者在 IF=0 下登记后切走。
PIT 以后到来，等待位已经存在，正常唤醒一人。
每阶段消费结束还会要求队列位和任务归属都清空，再次唤醒返回零，检查同一登记没有残留。

错误版本让真实生产者进入检查与登记之间

第二阶段的 wait-lost 变体在已经判定 !wait_event 后恢复中断。
它用 HLT 等真实 PIT 把事件置一，再 CLI，但故意不重新检查外层条件，直接登记并阻塞：

1
2
3
4
5
消费者：检查 wait_event=0
        恢复 IF=1
PIT IRQ：wait_event=1；等待集合为空；wake_one 返回0
消费者：CLI；仍按旧判断登记；状态变成 BLOCKED
后续 IRQ：事件仍为1，但那次生产已经结束

错误发生在控制流继续执行旧判断的分支。
即使登记与改 BLOCKED 都在 CLI 内，生产者也已经提前完成，之后不会仅因条件仍为真而自动再发同一通知。
这是可确定安排的丢失唤醒，不依赖反复碰运气触发短时间竞态。

下一次 PIT 检查故障状态，要求事件为一、消费者为 BLOCKED、等待掩码为二，且第二阶段的生产唤醒数为零。
GDB 在 wait_lost_observed 检查这些客体变量，同时核对当前处于 trap 深度一且 IF=0。
这一证据来自实际 IRQ 路径，脚本没有通过直接调用 C 生产函数伪造中断。

故障镜像还包含明确的救援分支。
记录丢失唤醒后经过至少三个 tick，PIT 主动再调用一次唤醒，允许消费者完成剩余阶段。
最终“生产消费都完成”必须与 lost=1、rescued=1 一起阅读，不能把救援后的完成误写成错误算法自行恢复。

丢失唤醒被检测、随后由测试救援完成的客体画面

本次故障断点读到 wait_event=1、消费者为 BLOCKED、等待掩码为 2、第二阶段唤醒人数为 0，救援尚未执行。
故障镜像最终记录 produced=3、consumed=3、woken=0/0/1、lost=1、rescued=1。
截图是救援完成后的汇总；故障发生时的 BLOCKED、条件值与零唤醒证据保存在 GDB 日志中。

正确版本等硬件请求挂起，却不提前运行生产者

修复版本在相同的第二阶段保持 IF=0。
测试代码有界轮询 PIC 的 IRR，等 IRQ0 请求位变为一，同时断言软件 tick 和生产计数没有变化。
此时证明的是“硬件请求已到达，软件 handler 尚未运行”。

timer_pending() 用 OCW3 的 0x0a 选择读取 IRR，读取请求位不会完成中断确认。
Intel 8259A 数据手册印刷页 13、16–17给出了对应位布局：RR=1、RIS=0、P=0；这是状态读取，不是会确认中断的 Poll 命令。
GDB 在 wait_pending_observed 进一步核对 PIC 状态：IRR0 已置位、IRQ0 未被屏蔽、ISR 尚无在处理的中断。
此外还要求当前任务为一、IF=0、事件仍为零、等待集合仍空。

1
2
3
4
5
消费者：CLI；检查 wait_event=0
硬件：  PIC IRR0=1，CPU 因 IF=0 尚未进入 IRQ
消费者：登记等待；BLOCKED；切换到可开中断的执行流
PIT IRQ：wait_event=1；发现等待位；移除登记并置 RUNNABLE
消费者：恢复旧调用；重新检查条件；消费

这次窗口安排没有通过同步调用绕过 CLI。
生产者只有在其他符合协议的执行流开启中断以后才能进入；届时消费者登记已经完成，因此不会发生“查找零人后才睡下”的顺序。
正常三个阶段的唤醒返回值应为 0,1,1，错误变体为 0,0,1，另计一次救援唤醒。

IRR 轮询最多执行一百万次，超出上限就断言失败，避免测试无限等待。
这段较长的关中断窗口仅用于受控注入，正常阻塞入口不会轮询 PIC，也不应按这个测试写生产等待逻辑。
本次受保护窗口读到 irr=01 imr=fe isr=00，软件生产计数仍为前一阶段的一次，当前事件未生产、等待集合为空。
正常镜像最终 produced=3、consumed=3、woken=0/1/1，未出现丢失唤醒或救援。

定时睡眠登记截止 tick 后阻塞

等待时间到达使用相同的 BLOCKED 状态，但不挂事件队列。
sleep_ticks(n) 先校验 n 不大于 0x7fffffff；n=0 立即返回，不产生等待或切换。
非零请求在 CLI 内记录 wake_tick = timer_ticks + n，设置 sleeping，再调用 block_current()。

1
2
3
4
5
6
7
8
uint32_t flags = irq_save();
struct task *t = &tasks[current];
KASSERT(!t->waiting_on && !t->sleeping);
t->wake_tick = timer_ticks + ticks;
t->sleeping = 1;
block_current();
KASSERT(!t->sleeping && tick_reached(timer_ticks, t->wake_tick));
irq_restore(flags);

每个 PIT tick 扫描两个普通任务槽。
只有 BLOCKED、sleeping 且截止已到达的任务才清除 sleeping、改为 RUNNABLE；事件等待者不会因时间流逝被顺便唤醒。
PIT 同时保留第 14 篇的调度请求，因此状态更新以后仍由中断出口选择任务。

被置为 RUNNABLE 不保证恰好在截止 tick 内执行到调用者下一句。
其他任务、不可抢占区间与当前调度选择都可能推迟实际恢复。
接口承诺不早于指定 tick 间隔，测试应使用“至少经过 n”，不能要求睡眠恰好等于 n。

测试任务先执行一次 sleep_ticks(0)，再连续八次睡眠三个 tick。
每次返回后比较无符号 tick 差值至少为三，再累计通过次数。
这个检查验证八次真实阻塞与 PIT 到期恢复；零等待路径只验证可正常通过，不额外宣称它单独覆盖了所有 IF 组合。

tick 回绕按半区间比较

32 位 tick 递增会回绕，因此不能直接用 now >= deadline 判断所有到期情况。
当前函数使用模减法：

1
2
3
4
static int tick_reached(uint32_t now, uint32_t deadline)
{
    return (uint32_t)(now - deadline) < 0x80000000u;
}

例如 deadline 为 0xfffffffe，now 已回绕到 1，模减法结果为 3，表示已经越过截止。
若 now 仍为 0xfffffffe，deadline 为 1，差值为 0xfffffffd，落在另一半区间，判定尚未到达。
相等时差值为零，也属于到期。

半区间算法要求比较距离没有跨越无法区分方向的半个计数空间。
接口把单次睡眠限制在 0x7fffffff tick 内，当前 tick handler 每次都扫描睡眠任务，不允许把任意久以前的截止值当仍可无歧义比较。
这不提供绝对时间或跨重启期限，也不表示实际中断停顿能被软件 tick 完整追补。

演示对相等、跨回绕已到期、跨回绕未到期和半区间边界运行直接断言。
这些是比较函数的边界检查；八次睡眠实验没有实际运行满 32 位 tick 周期，不能把它们描述成整周期实测。

没有普通任务可运行时，bootstrap 执行 idle

事件消费者和睡眠任务可能同时 BLOCKED，原来的环形调度必须仍能找到一个可运行上下文。
本篇把已有 bootstrap 作为 idle，不再给 idle 新申请一页栈。
启用 idle 模式后，调度器先扫描普通槽，只有它们都不适合运行时才选择槽位零。

idle 因而不会在正常计数或消费任务仍可运行时占用普通轮转名额。
它也永远不执行阻塞接口，始终作为无普通任务就绪时的后备执行流。
该策略没有一般优先级系统，仅给 bootstrap 一个固定的最低选择顺序。

1
2
3
4
5
6
7
8
9
(void)irq_save();
KASSERT(current == 0);
if (tasks[1].state == RUNNABLE || tasks[2].state == RUNNABLE)
    task_yield();
else {
    ++wait_idle_halts;
    wait_idle_observed();
    __asm__ volatile("sti; hlt" ::: "memory");
}

检查就绪状态时 IF=0，避免检查为空后、准备停机前有 IRQ 把任务置就绪。
STI 和 HLT 必须放在同一个汇编块中相邻执行；依据 Intel 指令手册，IF 原为零时 STI 对普通可屏蔽中断的识别延后覆盖紧随指令。
这使 pending IRQ 能在执行 HLT 后唤醒处理器，而不会先处理完事件、再执行一个失去唤醒来源的 HLT。

每次时钟仍会唤醒 CPU 处理 tick，必要时再回 idle。
因此这是周期时钟下的空闲等待，不是无周期 tick 的省电系统，也没有测量真实机器功耗。
GDB 必须结合 QEMU monitor 的 HLT=1 与 current=0 验证停机状态，单看 wait_idle_halts 增长只说明代码走到了停机之前。

键盘消费者改成持久任务

自检结束以后创建 keyboard_consumer，它调用已有 keyboard_loop()。
原始扫描码解析、大小写与行编辑继续在任务上下文执行，IRQ1 只接收原始字节、写队列并尝试唤醒。
任务检查队列时 CLI；空队列则登记等待，恢复后通过循环再次检查。

1
2
3
4
5
6
7
8
if (keyboard_consumer_paused || tail == head) {
    ++keyboard_blocks;
    task_block_locked(&keyboard_waiters);
    continue;
}
uint8_t byte = raw[tail];
tail = (tail + 1) % QUEUE_SIZE;
++keyboard_bytes;

这里 continue 返回的是循环入口，不是假设唤醒必然带来字符后直接读取 raw。
取出一个原始字节并更新 tail 后才开启中断，随后调用解析器和行编辑输出。
一个按键包含按下与释放等扫描码，原始字节数并不等于最终字符数。

键盘初始化仅清除 PIC 中的 IRQ1 屏蔽位，保留 PIT 当前屏蔽设置。
时钟屏蔽辅助函数也按位修改 IRQ0，不通过写入固定整字节意外屏蔽键盘。
正常运行时主 PIC 的 IRQ0 和 IRQ1 都开启；缺少任一条都可能让睡眠或输入等待失效。

队列溢出时继续保留第 09 篇的丢弃计数、丢弃待处理字节、重置解析器与重试整行提示。
唤醒接口没有改变原始队列容量，也没有保证输入永不丢失。
keyboard_consumer_paused 是诊断控制，在正常无输入场景为零；暂停期间恢复需要后续唤醒事件，不能把调试器改变量当成设备通知。

用真实输入检查阻塞、唤醒和再次阻塞

脚本先等键盘任务登记等待，再让 QEMU 自由运行 0.2 秒。
要求 tick 增长，但 keyboard_bytes 与 keyboard_blocks 不变，任务仍为 BLOCKED，等待位仍存在。
这说明任务没有在每个 tick 醒来再次登记；运行的是 IRQ 与 idle。

随后通过 QEMU monitor 依次发送 h、i、Enter，并给每个按键留出处理时间。
检查实际 IRQ1 次数、唤醒次数与原始字节消费数，要求串口出现 LINE: hi，行长度归零，键盘任务再次 BLOCKED。
释放码也经过 IRQ 与原始队列，所以这次输入的字节统计应覆盖按下和释放，而非只数三个可见字符。

脚本还核对无丢弃、PIC 的 IRQ0/IRQ1 均未屏蔽且 ISR 已清空。
正常与丢失唤醒变体都继续执行这条输入路径，防止故障救援只完成自检，却留下不能使用的系统。
本次两个镜像均通过 0.2 秒无输入观察，idle 为 current=0 且 QEMU 报告 HLT=1。
输入 h、i、Enter 后，实际 IRQ=6、wakes=6、bytes=6，串口输出 LINE: hi，行长度归零，键盘任务再次阻塞；主 PIC 为 imr=fc isr=00。

自检回收两张栈，键盘任务继续持有一张

事件消费者与睡眠任务完成后标记 DEAD，由 bootstrap 从自己的栈上回收两页。
回收前检查 canary、等待队列归属、sleeping、trap_depth 与 preempt_count 都已清理，再执行填充值扫描与 page_free()。
等待指针不能留到槽位复用以后，否则新任务可能被旧等待队列误认为仍在睡眠。

在 wait_demo_done 时，预期生产和消费各三次、睡眠通过八次、等待掩码为空，空闲页数恢复到本篇自检开始前。
随后创建持久键盘任务，会再次分配一张栈页。
到 keyboard_ready 或正常输入等待时，空闲页数应是自检初始值减一，不能声称运行系统已经归还所有任务页。

正常事件顺序、定时睡眠和自检栈回收的客体画面

本次两镜像均完成八次三 tick 睡眠，自检栈填充扫描为 372、196 字节，回收两页后空闲页恢复为 16064。
创建持久键盘任务后，空闲页保持为 16063。最后一轮正常与故障自检的 idle 计数分别为 24、22，该计数受调试停顿影响，不要求再次运行完全相同。
栈填充扫描仍只是本次写入痕迹，不是 guard page，也不证明任意未来调用链都能放进 4096 字节。
第 13、14 篇通过标记与协作式 387 次切换的旧断言同时保留，检查累计行为没有被等待路径破坏。

下载与复现

下载第 15 篇完整源码。
冻结源码提交为 f9979c5bc8710264161f927e5854736fa08b5b39；仓库实现目录为 examples/build-an-os，附件将其内容直接放在 os-day-15 内。
继续使用第 01 篇工具链镜像，顺序运行：

1
2
3
4
unzip os-day-15.zip
cd os-day-15
podman run --rm -v "$PWD:/work" -w /work localhost/build-an-os:day01 make build check-wait
podman run --rm -v "$PWD:/work" -w /work localhost/build-an-os:day01 make check

正常镜像为 build/mbr.img，故障变体为 build/mbr-wait-lost.img。
脚本 tools/check-wait.sh 保存 build/wait-{normal,lost}-{serial,gdb,qemu}.txt，并通过真实 QEMU monitor 截取两张实验画面。
GDB 共用容器 loopback 的 1234 端口，各定向检查应顺序执行。

本轮定向 check-wait check-keyboard check-tasks check-preempt、累计 make check 和 make screenshot help 均退出 0。
源码附件独立解压验证：make check 退出 0，包含正常等待、丢失唤醒与真实键盘输入，以及全部累计检查。
源码内 docs/day15-evidence.md 记录这次证据和实现限制。

等待条件、登记动作和任务状态现在使用同一个单 CPU 中断排除协议，任务不再靠持续轮询发现数据。
所有任务仍在 ring 0 共享地址空间，第 16 篇将增加用户态入口和访问权限，让应用错误不能任意改写内核。

练习

  1. 根据正常与故障时间线，解释第一阶段 wake=0 为什么正确，第二阶段 wake=0 为什么可能造成丢失唤醒；判断条件时必须同时观察什么状态？
  2. 手算 now=2、deadline=0xffffffff 与反向组合的模减法结果，说明半区间限制为什么不可省略。
  3. 对照 wait_demo_done 和 keyboard_ready 两个断点，分别写出预期空闲页数，并指出仍占用最后一张任务栈的执行流。

上一篇：14 - 抢占调度。

下一篇：16 - 进入用户态。

参考资料

  • MIT xv6 RISC-V book rev5：第 8–9 章的调度续点、条件复查、sleep/wakeup 与丢失唤醒讨论；本篇使用单 CPU 的 IRQ 排除实现同一时序约束。
  • Intel 8259A 数据手册：印刷页 13、16–17 的 OCW3、IRR/ISR 读取与逐位屏蔽规则。
  • Intel SDM Vol. 3A：中断门、IF 与中断返回规则，解释等待登记期间普通 IRQ 为什么不能进入。
  • Intel Software Developer Manuals：STI 的中断识别延迟、HLT 的恢复条件与 CLI 的边界；本篇继续使用第 08 篇的 PIC/PIT 配置。