作业四
一、阅读“Three Easy Pieces”的7 Scheduling: Introduction，并进行总结。
1 教材内容总结
《Three Easy Pieces》的第七章简要介绍了什么是进程调度、进程调度好坏的评判标准并举了一些简单的进程调度算法的例子。
首先，为了简化进程调度模型，本章从规定五个进程调度的强假设出发：
1、每个进程要完成的工作花费的时间相同
2、所有进程同时到达进程队列
3、没有抢占、所有进程运行到结束为止
4、所有进程不涉及I/O操作
5、所有进程完成工作所需时间已知
同时并以一个简单的评判标准：平均进程完成时间
提出了最朴素的进程调度算法FIFO：即先来先服务。
显然，这个算法在五个假设均成立的情况下就是最优的调度算法。
接下来，我们放松假设1，即每个进程所花费时间不等长时，我们很容易发现：当进程序列不是以用时长度递增的顺序排队时，其性能就达不到最优。
于是，我们提出了改进调度算法SJF：即用时最短的进程先服务。
这样在后四个假设条件满足的情况下，SJF能够达到最优。
接下来，我们放松假设2，即每个进程并非同一时间到达进程队列，这样，当进程序列不是以长度递增的顺序到达时，SJF的性能也达不到最优。
由于我们的评判标准只关注每个进程的完成时间，所有进程越早完成越好，过长的进程堵在前面会影响后面所有的进程，我们便想到：能不能让用时短的进程“插队”完成？
于是，我们放松假设3，提出了调度算法STCF：即所剩时间最短的进程先服务。
这样一来，我们似乎得到了在已有评判标准基础上的最优调度算法。
然而，随着时代的发展，计算机的交互性变得越来越重要， 这一评判标准确实适用于过去批处理形式的机器，但是并不适用于需要及时响应的计算机。
于是，我们提出了新的性能评判标准：响应时间
在这一新的评判标准下，STCF就不再是最优的调度算法了：因为用时较长的进程会被用时较短的进程一直阻塞，导致响应时间变长。
所以，我们试图提出一种“响应时间友好”的调度算法：Round Robin：即每个进程运行相同时间的“时间片”后，不论是否完成，随后都服务下一个进程，如此往复，直至所有进程完成。
这样的调度算法确实能够实现很小的响应时间。
但是，RR算法有两个重大的缺陷：
1、由于进程切换需要进行上下文切换（寄存器、TLB、CPU-Cache、分支预测器等等的保存与恢复），会带来性能损耗。若是为了追求降低响应时间而不断缩小“时间片”长度，会导致上下文切换频率不断增大，带来不可忽视的性能损耗。
2、在 评判标准下，RR算法反而是表现最差的调度算法：因为其从结果来看是不断地延后了每个进程的结束时间。
我们能否找到同时在 和 评判标准下表现都优秀的调度算法呢？
很遗憾，二者是矛盾的： 要求我们公平对待每个进程，这样就必然会带来 的延长，因为我们要尽可能让新来的进程“插队”，以获得更小的响应时间，这样就延后了已有进程的完成时间。
同时 要求我们更偏向于完成时间短的进程，但这样也必然会带来 的增加，因为用时长的进程会一直被阻塞。
所以，这二者之间并非独立的，我们无法分别优化某一个调度算法在这两个评判标准下的表现，而是只能在二者之间寻找折中点。
在着手寻找算法之前，别忘了还有假设4和假设5没有放松。
我们先来放松假设4：即存在进程涉及I/O操作，由于观察到当进程执行I/O操作时，CPU是空闲的，所以我们很容易将已有的调度算法进行拓展：只需在当前进程执行I/O操作时调度其它进程即可。更宏观地说：将I/O密集型进程和CPU密集型进程组合执行。
最后我们可以放松假设5了：CPU并不知道每个进程所需花费的时间，放松这一假设后，我们似乎前面提到的大部分调度算法都失效了，因为他们都是建立在我们已知每个进程所需花费的时间基础之上的。所以我们的调度算法在之前的基础上，应该有一个“试探”进程所需花费时间的功能。这就是下一章要讲解多级反馈队列算法。
2 个人观点
CPU调度算法比起一个计算机领域的问题，其更像是一个运筹学的问题，很多设计来源于生活实际。总的来说，CPU调度算法就是在“性能”与“公平”两个方面进行权衡。
为了提升性能，我们提出了：SJF,STCF 等算法，为了提升公平性：我们提出了：RR、优先级调度等算法。
在其中，我认为设计最成功的是抢占机制和优先级机制，他们同时提高了调度算法的性能与公平性，并且具有很强的拓展性：如通过多级反馈队列算法利用优先级间接实现了“短进程优先“，提高了性能，Windows系统的调度算法也通过优先级解决了进程的”饥饿“问题，提高了公平性。
二、回答问题
对某系统进行监测后发现，在阻塞I/O之前，平均每个进程运行时间为T。一次进程切换需要的时间为S，这里S实际上就是开销。对于采用时间片长度为Q的轮转调度，请给出以下各种情况的CPU利用率的计算公式：（a）Q = ∞ （b）Q > T （c）S < Q < T （d）Q = S （e）Q趋近于0
(a) 每个进程在结束前都不会进行切换，一个进程的完成对应一次进程切换，故CPU利用率为
(b)同(a)
(c) 进程结束前会被调度走，从整体考虑，忽略每个进程最后一次被调度上CPU可能运行时间不满Q的情况，CPU利用率为
(d)考虑到S一般小于T，套用(c)中公式
(e)考虑到S一般小于T，套用(c)中公式易知CPU利用率趋向于0