7.Scheduling: Introduction
- 前面我们了解了低层的用于运行进程的机制，现在该来谈一谈高层的policy来决定如何调度进程上CPU了。这章就来学习下调度进程的算法。
7.1 Workload Assumptions
- 在往下走之前，我们先做一些假设，有关于在系统中运行的进程的假设，这些假设我们叫做workload。当然我们做的这些假设其实在OS中是不切实际不现实的，但是随着深入下去，我们会逐渐接近实际情况，逐渐打破这些假设。
- 我们也经常把进程叫做job，对job我们做出如下五个假设：
- 1.每个job运行时间相等
- 2.所有job都在同一时间到达
- 3.一旦job开始运行，就运行到job完成
- 4.所有的job都只使用CPU（也就是说没有I/O请求）
- 5.Job的运行时长已知
7.2 Scheduling Metrics
- 既然是调度算法，那么就要有一个调度指标，根据这个调度指标来决定让哪个进程上CPU。
- 首先我们使用一个最简单的调度指标：turnaround time（周转时间）。周转时间的定义为，job的完成时间减去job到达系统的时间：。因为我们假设所有job同时到达系统，也就是说，因此 。
- 注意，周转时间是一种performance的指标，是我们这一章首要考虑的。另一种指标考虑的是fairness。这两种指标好比鱼与熊掌，不可得兼。
7.3 First In, First Out (FIFO)
- 最基本的算法First In, First Out (FIFO)，有时也叫 First Come, First Served (FCFS)。过于简单不多赘述。优点是简单易实现。
- 假设A、B、C几乎同时到达，但是FIFO是挑一个先到达的，所以假设A比B先一点，B比C先一点。
- 此种情况下，计算每个job的平均周转时间：。
- 现在让我们打破第一个假设，即不再认为所有job都运行相同的时间，这种情况下FIFO的性能有时就不是很好。例如以下情况：
- 此种情况下，计算每个job的平均周转时间：。
- 这种问题叫 convoy effect（护航效应），就是说对资源占用较少的job排在了对资源占用较多的job后面。那咋办呢？且看下一种算法。
7.4 Shortest Job First (SJF)
- 短作业优先，顾名思义，运行时间短的job先上CPU运行。
- 在之前的例子上，可得到如下图运行顺序：
计算每个job的平均周转时间：。
在我们假设所有job同时到达的情况下，SJF是一个优化的调度策略。但实际情况下往往不是所有job同时到达的。
- 现在让我们打破假设2，即job有可能在任何时刻到达，这种情况下应该怎么办？如果用SJF可能会出现以下情况，A先到，B、C在10s到，且A运行100s，B、C分别运行10s：
- 这时每个job的平均周转时间：。
7.5 Shortest Time-to-Completion First (STCF)
- 为了解决上面这种情况，考虑到我们之前学过的timer interrupt和context switch我们采用新的算法Shortest Time-to-Completion First (STCF)或者叫Preemptive Shortest Job First (PSJF) 。也就是抢占式的SJF，即当一个job到达时，如果它的运行时间短，那可以抢占当前job正在使用的CPU。
- 在之前的例子上，如下图：
- 这时每个job的平均周转时间：。
7.6 A New Metric: Response Time
- 如果我们知道job的运行时间并且job仅仅使用CPU的话，那么周转时间是我们唯一的指标，STCF是一个很好的策略。但事实上，坐在终端前的用户希望能够和系统进行交互，因此我们必须考虑另一个指标：response time（响应时间）。
- 响应时间的定义为job第一次上CPU的时间减去job到达系统的时间：。
- 对图7.5，A的响应时间为0，B为0，C为10。
- 之前的STCF对于考虑周转时间的情况下是很好的，但是却不利用响应时间，你想想你要是C的用户，你的程序要10s才能得到响应，你急不急？所以我们应该使用一种对于响应时间敏感的算法。
7.7 Round Robin
- 为了解决上述问题，采用 Round Robin（RR）的算法。基本思想就是不让每个job运行到它技术，每个job在CPU上都只能运行一个时间片（time slice有时也叫scheduling quantum），然后换下一个job上来运行。重复以上直到所有job运行结束。注意，时间片的长度必须是timer interrupt的倍数。
- 举个栗子，A、B、C同时到达，每个都要运行5s。SJF算法运行图如7.6，RR算法运行图如7.7：
- RR算法每个job的平均响应时间：，SJF算法每个job的平均响应时间：，只能说高下立判。
- RR算法中，时间片的长度太长或者太短都不行。
- 如果太短了，那么context switch的代价会影响整个性能。
- 如果太长了，那么回到了老问题，响应时间太长。
- 举个栗子，还是上面的ABC，看图7.7，A在13s结束，B在14s结束，C在15s结束，其实很差劲。如果考虑周转时间的话，RR真的拉跨。又回到了那句话，performance和fairness不能得兼。
7.8 Incorporating I/O
- 现在该打破第四个假设了，也就是说程序是需要I/O操作的。
- 那么程序在等待I/O的时候，其实CPU是空闲的，进程是blocked的。那么这时就应该安排别的进程上CPU，等待I/O的进程等到I/O结果了，再恢复该进程。
- 举个栗子，A、B各需要50msCPU，区别在于，A每10ms就发起一次I/O请求，B不需要I/O。
- 假设我们用的是STCF，很明显，这时CPU的利用率是很低的。所以应该充分利用CPU，像下面这样：
7.9 No More Oracle
- 现在该打破最后一个假设了，也就是说调度器不知道每个job需要运行时长。这个时候SJF/STCF都不好用了，RR也是一样。别着急后续会讲。
7.10 Summary
- 两个调度指标周转时间和响应时间，不可得兼。
- 针对两者，对应有不同的算法。
