进程调度 ​

工作负载和假设 ​

探讨可用的策略之前，我们这里做一些简化假设，这些假设与系统中运行的进程有关，有时候被称为工作负载，确定工作负载是构建调度策略的关键部分，工作负载了解得越多，策略就越优化。之后慢慢放宽这些假定，最后开发出完全可操作的调度准则。

1. 每一个工作运行相同的时间
2. 所有的工作同时到达
3. 一旦开始，每个工作保持运行直到完成
4. 所有的工作只使用 CPU，不执行 I/O 操作
5. 每个工作的运行时间是已知的

调度指标：周转时间 ​

在这立个 flag，找个时间学 latex

$T_{周转时间}=T_{完成时间}-T_{到达时间}$

性能与公平 ​

上面的周转时间属于性能指标，同时性能指标还有个对头：公平指标。性能自不用提，谁会不喜欢一个在最短时间内完成最多工作的软件呢。然而性能和公平在调度系统中是矛盾的，跟现实世界一样，例如调度程序可以优化性能，但代价是阻止一些任务运行，这就降低了公平。

先进先出 ​

最简单的调度就是先进先出，而且它易于实现。然而缺点也很多，简单举个例子：

A进程需要 100 秒运行，B进程需要 10 秒运行，C进程也需要 10 秒运行，这时我们按照字母顺序运行进程，那C进程需要等待 110 秒才能开始运行，这可能听起来没什么，那你可以设想这一个场景：

你去商店买东西，包括你在内有两个人排队，然后你眼睁睁看着前面的人掏出了支票本，采购了几车的物品，你因此会多等很久，你感觉如何？

这个示例的平均周转时间如下：

$$[(100-0)-(110-0)-(120-0)]/3=110$$

所以先进先出的调度方式有可取之处，是还可以优化。

最短任务优先（SJF） ​

这个策略很简单：先运行最短的任务，然后运行次短的任务，考虑到所有工作同时到达的情况，这是最优调度算法。

上个例子用 SJF 策略调度的话，平均周转时间变成了这样：

$$(10+20+120)/3=50$$

看起来好了很多。但是到这里，这个策略仍是不切实际的，因为实际上，工作可以随时到达，而不是同时到达，我们再举个例子：

A进程需要 100 秒运行，b进程需要 50 秒运行，c进程需要 10 秒运行，我们按照 SJF 策略运行a进程和b进程，先从b进程开始运行，然而运行a进程的中间，c进程启动了，此时我们还是需要等着a进程完成，才能开始c进程的运行，即使c进程运行时间比a更短，然后就需要引入更新的策略了：最短完成时间优先（STCF）。

最短完成时间优先（STCF） ​

所以我们这里放开那个限制（工作必须保持运行直到完成），我们可以在c进程到达的时候抢占a进程，运行完c进程后再返回a进程。

可能你已经想起来了，上面提到的时钟中断和上下文切换理论在这里是完全可用的，在工作在不同时间到达的情况下，STCF 可被证明是最优的。

响应时间 ​

我们唯一的衡量是周转率周转时间，STCF 很好的策略。这对批处理系统很有意义，在面对用户的时候则要求系统的交互性好，因此新的度量标准诞生了：响应时间。

响应时间定义为任务到达系统到首次运行的时间，公式如下：

$$T_{响应时间}=T_{首次运行}-T_{到达时间}$$

虽然的 STCF 的周转时间很好看，但是对响应时间和交互性来说无疑是很糟糕的，假设你在 Terminal 前输入，等待 10 秒才能看见系统的回应，你肯定很不开心。

所以新的问题产生了：如何构建对响应时间敏感的调度程序？