操作系统概念学习笔记 10CPU调度 多道程序操作系统的基础。通过在进程之间切换CPU，操作系统可以提高计算机的吞吐率。
对于单处理器系统，每次只允许一个进程运行：任何其他进程必须等待，直到CPU空闲能被调度为止。
多道程序的目标是在任何时候都有某些进程在运行，以使CPU的使用率最大化。多道程序的思想较为简单，当一个进程必须等待时，，操作系统会从该进程拿走CPU的使用权，而将CPU交给其他进程。
CPU-I/O 区间周期
CPU的成功调度依赖于进程的如下属性：
进程执行由CPU执行周期和I/O等待周期组成。进程在这两个状态之间切换(CPU burst—I/O bust)。
进程执行从CPU区间（CPU burst）开始，在这之后是I/O区间（I/O burst）。接着另外一个CPU区间，然后是另外一个I/O区间，如此进行下去，最终，最后的CPU区间通过系统请求中止执行。
经过大量CPU区间的长度的测试。发现具有大量短CPU区间和少量长CPU区间。I/O约束程序通常具有很多短CPU区间。CPU约束程序可能有少量的长CPU区间。这种分布有助于选择合适的CPU调度算法。
CPU程序调度
每当CPU空闲时，操作系统就必须从就绪队列中选择一个进程来执行。进程选择由短期调度程序（short-term scheduler）或CPU调度程序执行。调度程序从内存中选择一个能够执行的进程，并为之分配CPU。
就绪队列不必是先进先出（FIFO）队列，也可为优先队列、树或简单的无序链表。不过队列中所有的进程都要排队以等待在CPU上运行。队列中的记录通常为进程控制块（PCB）。
抢占调度：
CPU调度决策可在如下4种情况环境下发生：
（1）当一个进程从运行切换到等待状态（如：I/O请求，或者调用wait等待一个子进程的终止）
（2）当一个进程从运行状态切换到就绪状态（如：出现中断）
（3）当一个进程从等待状态切换到就绪状态（如：I/O完成）
（4）当一个进程终止时
对于第1和4两种情况，没有选择而只有调度。一个新进程（如果就绪队列中已有一个进程存在）必须被选择执行。对于第２和第３两种情况，可以进行选择。
当调度只能发生在第1和4两种情况下时，称调度是非抢占的（nonpreemptive）或协作的（cooperative）；否则，称调度方案为抢占的（preemptive）。采用非抢占调度，一旦CPU分配给一个进程，那么该进程会一直使用CPU直到进程终止或切换到等待状态。
抢占调度对方问共享数据是有代价（如加锁）的，需要新的机制来协调对共享数据的访问。
抢占对于操作系统内核的设计也有影响。在处理系统调用时，内核可能忙于进程活动。这些活动可能涉及要改变重要内核数据(如I/O队列)。
因为根据定义中断能随时发生，而且不能总是被内核所忽视，所以受中断影响的代码段必须加以保护以避免同时访问。操作系统需要在任何时候都能够接收中断，否则输入会丢失或输出会被改写。为了这些代码段不被多个进程同时访问，在进入时就要禁止中断，而在退出时要重新允许中断。
分派程序
分派程序（dispatch）是一个模块，用来将CPU的控制交给由短期调度程序选择的进程。
其功能包括：
分派程序停止一个进程而启动另一个所花的时间成为分派延迟（dispatch latency）。
调度准则
为了比较CPU调度算法所提出的准则：
需要使CPU使用率和吞吐量最大化，而使周转时间、等待时间和响应时间最小化。绝大多数情况下需要优化平均值，有时需要优化最大值或最小值，而不是平均值。
调度算法先到先服务调度
最简单的CPU调度算法是先到先服务算法（First-Come，First-Served scheduling）：先请求CPU的进程先分配到CPU。FCFS策略可以用FIFO队列来容易实现。当一个进程进入就绪队列，其PCB链接到队列的尾部。当CPU空闲时，CPU分配给位于队列头的进程，接着运行进程从队列中删除。
FCFS策略的代码编写简单且容易理解，不过采用FCFS策略的平均等待时间通常比较长。当进程CPU区间时间变化很大，平均等待时间会变化很大。
比如以下例子
进程 区间时间
P1 24
P2 3
P3 3
如果按照P1 P2 P3 顺序到达，Gantt图如下:
平均等待时间：(0+24+27)/3 = 17
如果按P2 P3 P1 顺序到达，
平均等待时间：(0+3+6)/3 = 3
另外考虑在动态情况下的性能，假设有一个CPU约束进程和许多I/O约束进程，CPU约束进程会移回到就绪队列并被分配到CPU。再次所有I/O进程会在就绪队列中等待CPU进程的完成。由于所有其他进程都等待一个大进程释放CPU，这称之为护航效果（convoy effect）。与让较短进程最先执行相比，这样会导致CPU和设备使用率变的很低。
FCFS调度算法是非抢占的。对于分时系统（每个用户需要定时的等待一定的CPU时间）是特别麻烦。允许一个进程保持CPU时间过长是个严重错误。
最短作业优先调度（shortest-job-first scheduling，SJF）
将每个进程与下一个CPU区间段相关联。当CPU为空闲时，它会赋给具有最短CPU区间的进程。如果两个进程具有同样长度，那么可以使用FCFS调度来处理。注意，一个更为适当地表示是最短下一个CPU区间的算法，这是因为调度检查进程的下一个CPU区间的长度，而不是其总长度。
比如以下例子
进程 区间时间
P1 6
P2 8
P3 7
P4 3
SJF: (0+3 + 9 + 16)/4 = 7
FCFS: (0+6+14+21)/4 = 10.25
SJF算法的平均等待时间最小。SJF算法的真正困难是如何知道下一个CPU区间的长度。对于批处理系统的长期（作业）调度，可以将用户提交作业时间所制定的进程时间极限作为长度。SJF调度经常用于长期调度。
它不能在短期CPU调度层次上加以实现。我们可以预测下一个CPU区间。认为下一个CPU区间的长度与以前的相似。因此通过计算下一个CPU区间长度的近似值，能选择具有最短预测CPU区间的进程来运行。下一个CPU区间通常可预测为以前CPU去剪的测量长度的指数平均（exponential average）。
SJF算法可能是抢占的或非抢占的。抢占SJF算法可抢占当前运行的进程，而非抢占的SJF算法会允许当前的进程先完成其CPU区间。抢占SJF调度有时称为最短剩余时间优先调度（shortest-remaining-time-first scheduling）。
比如以下例子
进程 到达时间 区间时间
P1 0 ８
P2 1 ４
P3 2 ９
P4 3 ５
根据Gantt图：
平均等待时间：
(0+0+(5-3)+(10-1)+(17-2))/4 = 26/4 = 6.5
非抢占SJF:
(0+(8-1)+(12-3)+(17-2))/4 = 7.75
优先级调度（priority scheduling algorithm）没有什么可留恋，只有抑制不住的梦想，
