操作系统 第三章 2 调度算法
调度的实质就是一种资源分配。
1.先来先服务调度算法FCFS
按照作业提交，或进程变为就绪状态的先后次序分派CPU；
新作业只有当当前作业或进程执行完或阻塞才获得CPU运行
被唤醒的作业或进程不立即恢复执行，通常等到当前作业或进程出让CPU。
- 缺点：
不利于短作业（进程）不利于I/O繁忙的作业（进程）。
2.短作业（进程）优先调度算法SJF/SPF （方式：分抢占和非抢占）
EP：
- A执行到1时刻，B 作业进入，但B运行时间8>A的4，所以接续执行A。——>就绪队列：B。
- 在时刻3时，C作业进入，又C运行时间3<A的4 ，C为短作业，所以执行C。——>就绪队列：AB
- C执行到4时，D作业进入，D的运行时间2<C的3，所以，执行D，直到D执行完。——>就绪队列：CAB
- 按顺序执行完就绪队列C、A、B
- 优点：
SJF/SPF调度算法能有效的降低作业的平均等待时间，提高系统吞吐量。
- 缺点：
1. 对短作业有利，但同时造成了对长作业的不利。
2.由于作业（进程）的长短含主观因素，不一定能真正做到短作业优先。
3.未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）的及时处理。、
3.高优先权优先调度算法HPF
1）静态优先权：创建进程时确定，整个运行期间保持不变。一般利用某一范围的一个整数来表示，又称为优先数。
动态优先权：创建进程时赋予的优先权可随进程的推进或随其等待时间的增加而改变。
2）非抢占式优先权算法
抢占式优先权算法 关键点：新作业产生时
3）高响应比优先调度算法HRRN （Highest Response Raito Next）
HRRN为每个作业引入动态优先权，使作业的优先级随着等待时间的增加而以速率a提高：
优先权 =（等待时间+要求服务时间) / 要求服务时间
= 响应时间 / 要求服务时间
- 特点：
- 利于短作业
- 长作业有照顾
- 先来先服务
需要进行调度选择的时候比较各自优先权 ：
- 作业完成时
- 新作业产生时（抢占、非抢占）
- 时间片完成时
- 进程阻塞时
EP：
4.多级反馈队列算法 FB
1）设置多个就绪队列，各队列有不同的优先级,优先级从第一个队列依次降低。
2） 赋予各队列进程执行时间片大小不同,
优先权越高，时间片越短。
当一个新进程进入内存，引发的调度过程：
- 准备调度：先将它放入第一个队列的末尾，按FCFS原则排队等待调度。
- IF时间片内完成，便可准备撤离系统；
- IF时间片内未能完成，调度程序便将该进程转入第二队列的末尾等待再次被调度执行。
- 当第一队列中的进程都执行完，系统再按FCFS原则调度第二队列。在第二队列的稍放长些的时间片内仍未完成，再依次将它放入第三队列。
- 依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。
仅当优先权高的队列（如第一队列）空闲时，调度程序才调度第二队列中的进程运行；仅当第1~（i-1）队列均空时，才会调度第i队列中的进程运行。
EP：
5.算法比较
