考研笔记

调度的目标

这一节给出的是度量工具。下一节的所有算法之所以有优劣之分，全靠这几个指标来评判；而计算题的分数，也几乎全部落在这几个公式上。

指标一共五个，其中周转时间和带权周转时间是绝对主力。

机制

五个指标

CPU 利用率利用率有效工作时间有效工作时间空闲等待时间衡量 CPU 忙碌的程度。多道程序设计的初衷就是提高它。

系统吞吐量系统吞吐量完成的作业数总共花费的时间单位时间内完成多少道作业。长作业多则吞吐量低。

周转时间——这是最重要的一个。周转时间作业完成时间作业提交时间它衡量的是从用户提交到最终拿到结果，一共等了多久。注意这段时间里包含四部分：在外存后备队列上等待作业调度的时间、进入内存后等待进程调度的时间、在 CPU 上实际执行的时间、以及等待 I/O 完成的时间。

带权周转时间带权周转时间作业周转时间作业实际运行时间这个指标存在的理由是：周转时间的绝对值对短作业不公平。一个需要运行 1 秒的作业等了 10 秒，和一个需要运行 100 秒的作业等了 10 秒，用户的感受完全不同——前者觉得系统慢得离谱，后者觉得还行。带权周转时间把”运行时长”这个因素除掉，反映的是用户的相对等待感受。

由定义可知 带权周转时间恒 ≥ 1。等于 1 意味着作业一提交就立即独占 CPU 跑完，中间零等待。这是一个很好用的自检点：如果算出来小于 1，一定是算错了。

等待时间等待时间周转时间实际运行时间进程处于等待处理机状态的时间之和。

这里有一个范围限定必须留意：对”进程”而言，等待时间不包括等待 I/O 的时间——因为进程等 I/O 时并不需要 CPU 服务，调度算法对此无能为力；而对”作业”而言，还要额外加上它在外存后备队列上等待作业调度的那段时间。

响应时间响应时间首次产生响应的时刻提交请求的时刻从用户提交请求到首次产生响应所用的时间。注意是首次，不是完成。这是交互式系统最看重的指标，也是分时系统采用时间片轮转的原因。

指标之间是互相冲突的

一个必须建立的认识是：不存在在所有指标上都最优的算法。

追求吞吐量和平均周转时间，就应该让短作业先跑（SJF 类算法），但这必然让长作业等待更久，甚至饥饿。

追求响应时间，就应该频繁轮转（RR），但每次切换都有上下文切换开销，时间片越小切换越频繁，CPU 利用率反而下降。

追求公平，就不能总照顾短作业，那么平均周转时间必然变差。

所以选择算法的实质，是根据系统类型决定牺牲哪个指标。批处理系统愿意牺牲响应时间换吞吐量；分时系统愿意牺牲平均周转时间换响应时间；实时系统连平均值都不在乎，只在乎最坏情况。

边界

周转时间 vs 等待时间 vs 响应时间

三个”时间”极易混淆，用一条时间轴上的三个问题区分：

  • 周转时间问：“从提交到全部做完，一共多久？”
  • 等待时间问：“这段时间里，干等着没被服务的部分有多久？”
  • 响应时间问：“从提交到第一次有反应，多久？”

关键差别在终点：周转时间的终点是完成，响应时间的终点是首次响应。一个作业可能 1 毫秒就给出首次响应，却要 10 秒才跑完。

等待时间的口径随对象而变

这是最容易失分的地方，务必按对象区分：

对象等待时间包含什么
进程等待处理机的时间
作业等待处理机的时间 + 在外存后备队列上等待作业调度的时间

两者都不包含等待 I/O 的时间。 因为进程在做 I/O 时是在被”服务”，只不过服务它的是设备而非 CPU。

带权周转时间 ≥ 1 是硬约束

前面已述，这是最好用的自检点。同理，周转时间 ≥ 实际运行时间、等待时间 ≥ 0。计算题算完随手验一遍，能挡掉大部分低级错误。

对照速查

指标公式谁最在乎
CPU 利用率有效工作时间 / 总时间所有系统
系统吞吐量完成作业数 / 总时间批处理
周转时间完成时间 − 提交时间批处理
带权周转时间周转时间 / 实际运行时间（≥1）批处理（对短作业公平）
等待时间周转时间 − 实际运行时间所有系统
响应时间首次响应时刻 − 提交时刻分时 / 交互式
想优化的目标代价
平均周转时间 ↓长作业可能饥饿
响应时间 ↓切换频繁，CPU 利用率 ↓
公平性 ↑平均周转时间 ↑

考点

  • 五个公式（周转时间与带权周转时间是主力）
  • 带权周转时间恒 ≥ 1，可用作自检
  • 响应时间的终点是”首次响应”而非”完成”
  • 等待时间不含等待 I/O 的时间；作业的等待时间还要加上外存排队时间
  • 指标之间互相冲突，选择算法即选择牺牲哪一项

链接

反向链接