#操作系统概念阅读笔记5 ##CPU调度
###基本概念
CPU－I/O区间周期
- 进程执行由CPU和I／O等待周期组成。进程在这两个状态之间切换。
CPU调度程序
- 所谓CPU调度程序，其实就是：当CPU空闲时，操作系统如何从就绪队列中选择一个进程来执行的策略。
抢占调度
- 非抢占调度，一旦CPU分配给一个进程，那么该进程会一直使用CPU直到进程终止或切换到等待状态。
- 抢占调度，可能一个进程正在运行时，另一个新的进程也到来。而依据调度策略与当前各进程状态，新进程应该先执行。那么，新进程会抢占CPU进行执行，原进程切换到就绪状态。
####分派程序 分派程序是一个模块，用来将CPU的控制交给由短期调度程序选择的进程。 功能包括：
- 切换上下文
- 切换到用户模式
- 跳转到用户程序的合适位置，以重新启动程序
调度准则
- CPU使用率
- 吞吐量：一个时间单元内所完成进程的数量
- 周转时间：从进程提交到进程完成的时间段称为周转时间。
- 等待时间：为在就绪队列中等待所花费时间之和
- 响应时间：开始响应所需要的时间，响应时间指从进程提交到被运行第一段代码的时间
调度算法
1.先到先服务调度（FCFS）
非抢占。 补充概念：护航效果：所有其他进程等待一个大进程释放CPU的状态
2.最短作业优先调度（SJF）
- 这一算法将每个进程与其下一个CPU区间段相关联。当CPU为空闲时，它会赋给具有最短CPU区间的进程。 如果两个进程具有同样长度，那可以使用FCFS调度来处理。
-
SJF调度算法的平均等待时间最小。
- SJF的难点就是如何得知下一个CPU区间的长度。书上采用，预测下一个CPU区间为以前CPU区间的测量长度的指数平均。T（n＋1）＝åt（n）＋（1-å）T（n）
- 抢占SJF调度：最短剩余时间优先调度 也存在非抢占SJF
3.优先级调度
- SJF可作为通用优先级调度算法的一个特例
- （书上默认）优先级越高，数值越小 即 优先级1比优先级2的优先级要高 优先级调度可以是抢占的或者非抢占的。
- 主要问题：无穷阻塞或饥饿＝》它可能会导致某个低优先级进程无线等待CPU
- 解决：使用老化技术，以逐渐增加在系统中等待很长时间的进程的优先级
4.轮转法调度（RR）
- 定义一个较小时间单元，称为时间片。
- 将就绪队列保存为进程的FIFO队列。新进程增加到就绪队列的尾部。CPU调度程序就从就绪队列中选择第一个进程，设置定时器在一个时间片之后中断，再分排该进程。（1进程在时间片中运行完，进程自动释放CPU，下一个进程开始执行 2.进程未在时间片内执行完，定时器产生中断并产生操作系统中断，然后进行上下文切换，将进程加入到就绪队列的尾部，就绪队列中下一个进程开始执行）
- 该策略的平均等待时间通常较长 具体效率和时间片大小有关 适合分时（交互系统）
5.多级队列调度
将就绪队列分成多个独立队列，每个队列有自己的调度算法，每个队列有自己的优先级
6.多级反馈队列调度
在上面的基础上，允许等待时间过长的进程转移到更高优先级的队列
典型例题
##5.4 考虑下列进程集，进程占用的 CPU 区间长度以毫秒来计算：
| 进程 | 区间时间 | 优先级 |
|---|---|---|
| P1 | 10 | 3 |
| P2 | 1 | 1 |
| P3 | 2 | 3 |
| P4 | 1 | 4 |
| P5 | 5 | 2 |
假设在时刻 0 以进程 P1，P2，P3，P4，P5 的顺序到达。
a.画出 4 个 Gantt 图分别演示用 FCFS、SJF、非抢占优先级（数字小代表优先级高）和 RR（时间片＝1）算法调度时进程的执行过程。
FCFS:P1->P2->P3->P4->P5
SJF:P2->P4->P3->P5->P1
非抢占优先级：P2->P5->P1->P3->P4
RR: P1->P2->P3->P4->P5->P1->P3->P5->P1->P5->P1->P5->P1->P5->P1->P1->P1->P1->P1
b.在 a 里每个进程在每种调度算法下的周转时间是多少？
1.
c.在 a 里每个进程在每种调度算法下的等待时间是多少？ d.在 a 里哪一种调度算法的平均等待时间对所有进程而言最小？
答：a.甘特图略 b.周转时间
| FCFS | RR | SJF | 非抢占优先级 | |
|---|---|---|---|---|
| P1 | 10 | 19 | 19 | 16 |
| P2 | 11 | 2 | 1 | 1 |
| P3 | 13 | 7 | 4 | 18 |
| P4 | 14 | 4 | 2 | 19 |
| P5 | 19 | 14 | 9 | 6 |
c.等待时间
| FCFS | RR | SJF | 非抢占优先级 | |
|---|---|---|---|---|
| P1 | 0 | 9 | 9 | 6 |
| P2 | 10 | 1 | 0 | 0 |
| P3 | 11 | 5 | 2 | 16 |
| P4 | 13 | 3 | 1 | 18 |
| P5 | 14 | 9 | 4 | 2 |
d.SJF平均等待时间最短
##5.5 下面哪些算法会引起饥饿 a.先来先服务 b.最短工作优先调度 c.轮换法调度 d.优先级调度
答：最短工作优先调度和优先级调度算法会引起饥饿 ##5.7
考虑一个运行十个I/O限制任务和一个CPU限制任务的系统。假设，I/O限制任务一次分配给一个I/O操作1毫秒的CPU计算，但每个I/O操作的完成需要 10毫秒。同时，假设间接的上下文切换要0.1毫秒，所有的进程都是长进程。对一个RR调度来说，以下情况时CPU 的利用率是多少：
a.时间片是1毫秒
b.时间片是10毫秒答：
a.时间片是1毫秒：不论是哪个进程被调度，这个调度都会为每一次的上下文切换花费一个0.1毫秒的上下文切换。CPU的利用率是1/1.1*100=92%。
b.时间片是10毫秒：这I/O限制任务会在使用完1毫秒时间片后进行一次上下文切换。这个时间片要求在所有的进程间都走一遍，因此，10＊1.1+10.1(因为每个I / O限定任务执行为1毫秒，然后承担上下文切换的任务，而CPU限制任务的执行10毫秒在承担一个上下文切换之前) 。因此，CPU的利用率是20／21.1*100=94%
