操作系统3——处理机调度（作业调度+进程调度）
操作系统3——处理机调度（作业调度+进程调度）
目录
3、作业调度——短作业优先调度算法（SJF）short job first
3、作业调度——优先级调度算法（PSA）priority-scheduling algorithm first
5、进程调度——时间片轮转调度算法(RR—Round Robin)
1、处理机的调度层次和目标
（1）什么是处理及调度？
在多道程序环境下，进程数目通常多于处理机的数目，系统必须按一定方法动态地把处理机分配给就绪队列中的一个进程。
（2）什么是作业？
作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等，作业是用户提交给系统的一项相对独立的工作。
（3）什么是作业步？
每个作业会配置一个作业说明书，作业的每个步骤称为一个作业步。每个作业设置一个JCB（作业控制块）是作业唯一的符号标识，包含作业标识，用户名称，用户账号，作业类型，作业状态，调度信息等。
（4）作业状态间转换：
处理机调度的层次：
|
处理机调度层次 |
高级调度 |
也称作业调度或长程调度，调度对象是作业，吧后备状态的作业调入到内存 |
|
中级调度 |
也称中程调度，调度对象是暂时不能运行的进程，调至外存 |
|
|
低级调度 |
也称进程调度或短程调度，调度对象是进程 |
（5）处理机调度算法的目标：
|
对于处理机调度算法目标 |
资源利用率高（CPU利用率）； 公平性； 平衡性 |
|
批处理系统目标 |
平均周转时间； 平均带权周转时间短；（周转时间/服务时间） 吞吐量； 处理机利用率 |
|
分时系统的目标 |
响应时间快； 均衡性； |
|
实时系统目标 |
截止时间保证； 可预测性； |
（6）进程的调度方式分类：
进程调度的任务：保存处理机的现场信息；按照某种算法选取进程；分配处理机给进程。
调度方式：
1.抢占式：当某一进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，该进程仍继续执行，直到其完成或发生某种事件而进入完成或阻塞状态时。
2.非抢占式：当某一进程正在处理机上执行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即暂停正在执行的进程。
2、作业调度——先来先服务调度算法（FCFS）
（1）算法思想：按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度，
（2）优缺点：
- 有利于长作业（进程），而不利于短作业（进程）
- 有利于CPU繁忙型作业（进程） ，而不利于I/O繁忙型作业（进程）
- 用于批处理系统
- 可用于作业调度，也可用于进程调度
（3）调度算法的评价标准
周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。
平均周转时间：
带权周转时间：进程（或作业）的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS
（4）FCFS算法实例
3、作业调度——短作业优先调度算法（SJF）short job first
（1）算法思想：从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。
（2）优缺点：
- 降低作业的平均等待时间，提高系统吞吐量；
- 对长作业不利，长作业长期不被调度——饥饿；
- 必须预知作业的运行时间；
- 完全未考虑作业的紧迫程度；
- 人机无法交互；
（3）SJF算法实例
3、作业调度——优先级调度算法（PSA）priority-scheduling algorithm first
算法思想：基于作业的紧迫程度，外部赋予作业优先级，调度算法根据优先级调度。
4、作业调度——高响应比优先调度算法（HRRF）
（1）算法思想：HRRF是FCFS和SJF的结合，克服了两种算法的缺点，设置响应比最高的作业优先启动。等待时间+服务时间=该作业的响应时间。
（2）调度策略
响应比最高的作业优先启动：
因等待时间+服务时间=该作业的响应时间，故该优先级又相当于响应比RP。据此，又可表示为：
（3）HRRF的小结：
- 等待时间相同的作业，则要求服务的时间愈短，其优先级愈高；
- 要求服务的时间相同的作业，则等待时间愈长，其优先级愈高；
- 是FCFS和SJF的结合，克服了两种算法的缺点；
- 长作业，优先级随等待时间的增加而提高，其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机；
- 缺点：要进行响应比计算，增加了系统开销；
5、进程调度——时间片轮转调度算法(RR—Round Robin)
进程调度的任务：是控制、协调进程对CPU的竞争
- （1）保存处理机的现场信息
- （2）按算法调度进程
- （3）处理机分配给进程
（1）时间片轮转调度算法的原理：系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便停止该进程的执行，并将其放就绪队列尾；然后，再把处理机分配给就绪队列中新的队首。
（2）时间片大小的确定：与时间片大小有关的因素：系统响应时间；就绪进程个数；CPU能力
（3）算法的特点：
- 采用比FCFS更加公平的处理机分配方式，每个进程大约获得1/n的处理及时间 ；
- 进程上下文切换，增加系统开销；
- 没有考虑到进程的紧急程度；
- 既可以是抢占式的，也可以是非抢占式的；
- 缺点：紧迫任务响应慢。
6、进程调度——优先级调度算法
（1）抢占式优先级调度算法
把处理机分配给优先级最高的进程，但在执行期间，只要出现另一个优先级更高的进程，则进程调度程序就立即停止当前进程的执行，并将处理机分配给新到的优先级最高的进程。只要系统中出现一个新的就绪进程，就进行优先级比较
（2）非抢占式优先级调度算法
系统一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去，直至完成。
（3）静态优先级调度算法
静态优先级在创建进程时确定，且在进程的整个运行期间保持不变。
（4）动态优先级调度算法
优先级随进程的推进或随其等待时间的增加而改变，以获得更好的调度性能。
7、进程调度——多队列调度算法
原理：设置多个就绪队列，并为各个队列赋予不同的优先级。
第一个队列的优先级最高，第二个队列次之，其余各队列的优先级逐个降低。
各个队列中时间片的大小也各不相同，队列优先级愈高，时间片就愈小。
队列的转换：
（1）仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；
（2）仅当第1~(i-1) 队列均空时，才会调度第i队列中的进程运行
（3）如果处理机正在第i队列中为某进程服务时，又有新进程进入优先级较高的队列(第1~(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先级进程