Skip to content

07. Scheduling: Introduction

Scheduling Metrics

有两种指标：

  1. 周转时间：completion - arrival

  2. 响应时间：first run - arrival

Scheduling Algorithms

  1. 先进先出。缺点：如果只是简单的先进先出调度，可能耗时多的任务排在前面，耗时较少任务不得不在之后才能运行。这不是最好的解决方案

  2. Shortest Job First 最短任务优先，不抢占。先运行最短的任务，在运行次短的。但如果所有工作不是同时到达的，先到达的是一个特别长的任务，这个机制就不得不等最长的任务运行完，再运行其他的，哪怕其他的用的时间很短。

  3. Shortest Time-to-Completion First （STCF）最短完成时间优先。这是抢占的。每当新的工作到达就绪队列时候，OS 就会确定剩余工作核心工作中谁的剩余时间最少

在早期的批处理系统，也就是 50s–60s 的大型机系统里，用户把程序写在穿孔卡和磁带，交给操作员，第二天甚至几小时后再来取结果。因此，在早期，用户不与系统交互，调度目标是最小化平均周转时间，只考虑周转时间这一个指标。因此 Shortest Time-to-Completion First 的策略是最优的。

后续有了分时系统，分时系统让多个用户“同时”使用一台计算机，并且每个人都觉得系统在立刻响应自己。用户坐在终端前并期望系统快速响应，因此引入了响应时间这一新的度量标准。

响应时间不看任务本身运行的时间，只看从任务到达系统到首次运行的时间。

STCF 对响应时间不友好，是因为某些任务（尤其是长任务）可能在很长时间内得不到任何 CPU 时间，从而导致首次运行被无限推迟。

Round Robin

为了解决这个问题，介绍一种新的调度算法：Round-Robin。每个进程运行一个固定时间片（time quantum）用完就被抢占，放到队列尾部。

假设有 N 个进程，时间片为 q，任意一个新到达的进程，最多等待 (N−1) × q，就一定能第一次运行。

大大优化响应时间，但对周转时间不利，频繁抢占也会带来 context switch 的开销。