CPU服务、就绪与时间账本

四个任务都能正确保存和恢复寄存器，仍可能有一个很久轮不到CPU。上下文切换解决“怎样交接执行”，调度政策还要解决“下一段时间交给谁”。比较政策之前，先需要一份不会把等待算成运行的共同账本。

形式陈述

一台CPU，四份尚未完成的工作

本单元使用自定实例SCHED-16。时间单位为毫秒，CPU每运行1毫秒就交付1毫秒服务。任务均只有一段CPU工作，不做I/O、没有锁等待、不迁移到其他CPU；上下文切换暂按零成本处理。真实应用当然复杂得多，这些限制让我们能先把政策本身算清。

任务	到达时刻 $a_i$	需要的CPU服务 $b_i$
A	0	9
B	1	4
C	2	2
D	4	1

“B在1到达”表示它从1开始有资格竞争CPU；“B需要4”表示它累计实际运行4毫秒才能完成。若B等了10毫秒但一次也没运行，它仍需要4毫秒，不会因为墙钟走过而自动接近完成。

总需求为 $9+4+2+1=16$ 。这解释了实例的名字，也给出第一项核验：只要CPU从0开始从不无故空闲、没有切换成本，全部工作恰在16完成。不同政策可以改变各任务完成的时刻，却不能把总共16的工作凭空变成12。

状态里留下什么

在时刻 $t$ ，任务的累计服务 $s_i(t)$ 是它在 $[a_i,t)$ 内实际占用CPU的各段长度之和。剩余服务为

r_i(t)=b_i-s_i(t).

这里的 $b_i$ 是实验观察者知道的输入。只有明确允许知道时长的SJF、SRTF政策可以据此作决定；FIFO、轮转和反馈队列的选择规则不能偷看它。模拟器需要知道何时结束，与操作系统事先知道程序将运行多久，是两件事。

任务尚未到达时处于NEW；到达后可以是READY或RUNNING；服务达到 $b_i$ 后转成DONE。加入I/O的变体还会用到BLOCKED，它表示等待外部事件，当前没有运行资格。状态的意义沿用切换页，不重新定义另一套线程生命周期。

任意时刻都检查三件事：至多一个任务RUNNING；READY任务在相应队列恰出现一次； $0\le s_i\le b_i$ 且 $s_i+r_i=b_i$ 。选任务的政策可以不同，这些安全条件不能放宽。把一个任务重复入队，即使最后平均数“看起来不错”，也已不是合法调度。

直觉

运行一段，怎样更新

若在 $[u,v)$ 内只有A运行，则只把 $s_A$ 增加 $v-u$ 、把 $r_A$ 减少同样的量；其他任务的服务不变。该区间可能被三类事件截断：当前工作完成、政策规定的时间片用尽，或到达/唤醒触发抢占。应在最早发生的那个事件处停下，再决定下一步。

假设先给A运行 $[0,2)$ ，再给B运行 $[2,4)$ 。到4为止，服务是 $(2,2,0,0)$ ，剩余是 $(7,2,2,1)$ 。C从2到4一直就绪，故等了2；D恰在4到达，等待仍为0。不能把D放进 $[2,4)$ 的等待账单，也不能因为B在1到达就给它记3毫秒运行。

同一墙钟区间内，A与B实际服务、C就绪等待，以及4时刻的队列边界 — 服务只在实际运行时增加

用半开区间 $[u,v)$ 表示运行，可以让相邻两段共用边界而不重复计时。 $[0,2)$ 与 $[2,4)$ 总长4，时刻2本身没有一段需要另付的时间。

例子与边界

同一时刻的动作也要排好顺序

SCHED-16统一采用以下边界约定：先结算刚结束的运行；已完成者退出；把此刻新到达者按A、B、C、D顺序加入相应队尾；若当前任务只是用尽时间片，则在新到达者之后重新排队；最后作新的选择。唤醒事件若出现，与到达一同按任务名处理。

例如轮转中，A的第一片恰在2结束，而C也在2到达。1时刻已经入队的B在前，随后是C，最后才是重新排队的A，因此队列为B、C、A。另一个系统可以规定A先重排，再处理C；那也可能正确，但它是另一条轨迹，不能把两种约定的完成时间拼到同一答案里。

抢占是一个仍有资格运行的任务被政策暂停，它回到READY。阻塞是任务暂时没有资格运行，例如等待磁盘数据，它转到BLOCKED。给BLOCKED任务更高优先级不会使磁盘提前交付数据；只有唤醒事件才能让它重新参加选择。

把墙钟时间分账

一个任务到完成为止，时间可以分成实际服务 $b_i$ 、就绪但没有运行的等待 $W_i$ ，以及阻塞时间 $B_i$ 。若三种状态互斥并覆盖它的存活区间，则

C_i-a_i=b_i+W_i+B_i.

主例没有阻塞，因此 $W_i=C_i-a_i-b_i$ 。若把模型扩成“运行1、I/O等待3、再运行1”，并且期间无需排队，任务5毫秒完成，服务为2、阻塞为3、就绪等待为0。直接算 $5-2=3$ 然后说“排队等了3毫秒”，会把设备等待错怪给CPU政策。

考虑切换开销时，本单元把每个尚未完成、可运行但未获CPU服务的任务视作处在等待中；整机另有DISPATCH区间。于是切换时间不增加任何 $s_i$ ，却可能增加多个任务的等待。任务的等待总和可以大于整机墙钟时间，因为同一毫秒里可以有好几个任务同时等待。

推论与应用

一眼发现不合法的时间线

对任意观察区间 $[0,T)$ ，令 $H(T)$ 为切换/调度开销、 $I(T)$ 为CPU空闲时间。在本单核、单位速度模型下，必须满足

\sum_i s_i(T)+H(T)+I(T)=T.

若画出的条带覆盖0到16，却累计给A10、B4、C2、D1，总服务17，就发生了重叠或重复记账。若只有15，则漏了工作或把一段空闲藏掉了。总量核验不能证明每次选择都符合某个算法，但能先排除一大类漂亮而错误的图。

本页允许任意满足状态合同的政策；只有声明为工作保守时，才要求有READY任务就不空闲。主动等待未来短任务的离线计划不工作保守，却未必违反状态安全。到多核、变速CPU或锁依赖场景，守恒式和资格规则要相应重写，不能机械沿用单核的16毫秒终点。

接下来在调度指标页，把这份事件账本变成可比较的周转、首次响应和利用率。

参考资料

Remzi H. Arpaci-Dusseau、Andrea C. Arpaci-Dusseau，Operating Systems: Three Easy Pieces, Ch.7, §§7.1–7.2：工作负载假设与度量接口；SCHED-16数据、边界次序和守恒核验为本单元自定。
Fernando J. Corbató、Marjorie Merwin-Daggett、Robert C. Daley，“An Experimental Time-Sharing System”，AFIPS Spring Joint Computer Conference 21，1962，pp.335–344，尤其pp.336–338的时间片、中断与使用时间记账。

形式陈述 ​

一台CPU，四份尚未完成的工作 ​

状态里留下什么 ​

运行一段，怎样更新 ​

同一时刻的动作也要排好顺序 ​

把墙钟时间分账 ​

一眼发现不合法的时间线 ​

反向链接