背景
从这章开始，我们将开始讨论 scheduling policies，主要讲了在做 process 切换的时候，我们如何做决定切换到哪个 process。在阅读这章原文的时候，除了学到各种 scheduling policies，我觉得更重要的是这篇文章所展现的方法论。它没有直接告诉我们现在操作系统所使用的 scheduling policies 是什么，而是先做些假设，将操作系统会面对的情况简单化，然后提出一个简单的 policies。最后，通过否定假设来不断修正 policies，最终达到一个符合目的的 policies。
Process VS Job VS Task
首先书本里出现了两个令人费解的 term，process 和 job。书里认为这两个是一样的，但是我还是去查了下这两者的区别。这个回答 可以仔细看下，基本上这三者没有太大的区别，只是从不同的 context，会有不同的叫法
假设
首先我们对 job 做了以下的假设：
- 所有的 job 运行的时间都是一样的
- 所有的 job 都是同时到达
- 一旦一个 job 开始了，在完成之前都无法被结束
- 所有的 job 都只使用 CPU
- 每个 job 运行时间都是已知的
我们可以看到，这些所有假设在现实中都是不成立的，但是基于这些假设，我们就有思路了，可以很快制定一些 policies。
度量
在考虑 polices 之前，我们要先确定如何衡量我们制定的策略。现在我们先主要考虑两个 metrics:
-
turnaround time
turnaround time.png
-
response time
Response Time.png
这两个都很简单，就不解释了。
First In, First out
这个策略就是，哪个 job 先进来，就先执行（First Come，First Served）。这个策略的优点就是简单，很容易实现，在我们的假设下，是非常完美的符合。来看下书中的例子：
FIFO example.png
A 的 turnaround time 是 10， B 的turnaround time 是 20 ，C 的 turnaround time 是 30，平均下来就是 20。接下来我们开始去掉我们的假设，在慢慢改进我们的策略。
首先，去掉 假设1。我们可以很容易想到一种情况，会导致 turnaround time 变的非常糟糕。
Why FIFO Is Not That Great.png
这个时候，A 的 turnaround time 是 100， B 的 turnaround time 是 110，C 的turnaround time 120，平均下来 turnaround time 是 110，跟之前相比就是一个非常糟糕的数字了。这个问题就是我们常说的 convoy effect。
Shortest Job First (SJF)
要解决上面这个问题，我们可以采用一个新的算法，即先运行时间最短的。这样的话运行图就会变为：
SJF Simple Example.png
这个的平均 turnaround time 是 50，马上就提升了两倍。接着我们在去掉假设 2，这又会带来什么问题呢？来看个图就知道了：
SJF With Late Arrivals From B and C.png
因为 B 和 C 都第 10 秒才到的，所以根据我们当前的算法来说，这个的 turnaround time 是 103.333，这就又引起了 convoy effect 。
Shortest Time-to-Completion First(STCF)
要解决这个问题，首先我们需要去掉 假设3，然后当有 job 进入的时候，操作系统会看哪个进程可以最快完成，就先运行哪个，然后在切换回来。所以我们之前的那个运行图就变为：
STCF Simple Example.png
这个算法的平均 turnaround time 是 50，这个就非常接近第一个算法。那这个算法的问题又是什么呢？这就涉及到我们第二个 metric，response time。
Response Time
现代的计算机对 responsive 要求很高，用户触发了什么之后，是希望立即得到反馈，SJF 的 response time 是 3.33（A 和 B 是 0， C 是 10），可以看到不是很好，那我们如何优化这个点呢？
Round Robin
这个算法的基本内容就是，每个进程运行一段时间（这个时间段我们称为 time slice），直到所有的进程运行结束。那运行图就会变为：
Round Robin.png
这个的 average response time 就是 1，就快了很多。那这个算法又有什么问题？
- turnaround time 一般会比较差
- 如果 time slice 设置的比较短，context switch 频繁发生，那 switch 的代价会比较高。
所以这就是一种权衡（tradeoff），注重 turnaround time ，response time 就会差，反之亦然。接下来，我们再来否定最后两个假设。
Incorporating I/0
现在我们再来看下有 I/O 发生的情况下，我们的算法会发生什么样的变化。假设我们有两个 jobs: A 和 B，它们都需要消耗 50 ms 的 CPU 时间。A 每运行 10 ms 会发起一次 I/O request（假设每次 I/O request 需要 10 ms 来完成），B 不会。那运行图为：
Poor Use Of Resources.png
这个解决方式也很简单：
Overlap Allows Better Use Of Resources.png
只需要在CPU 有空闲的时候，运行 B job 就好了。
最后
我们还需要搞定最后一个假设，即如何在不知道一个 job 的运行时间情况下，制定我们的 schedule policies，这个我们就留到下一章来讲。
网友评论