2.3 处理器调度
- 处理器调度的层次
- 处理器调度的算法
- 单道环境下的调度
- 多道环境下的调度
- 低级调度方式算法
一、 处理器调度的层次
（1）处理器调度层次：
1、一般分为三个层次：1、高级调度 2、中级调度 3、低级调度
高级调度：一般发生在新建态到其他状态和其他状态到终止态之间的切换
高级调度本质上和内存紧密关联，主要体现在内存方面的调度
中级调度：主要是在挂起状态和非挂起状态之间切换的时候发生的调度
低级调度：主要是针对CPU的调度，他对应着进程在CPU上的切换过程（如进程在就绪、运行和等待态之间发生的切换）
如图：
2、作业与进程：（作业调度一般是高级调度，进程调度则是低级调度）
作业是用户向计算机提交的任务实体，而进程则是计算机完成任务的执行实体，是系统分配资源的基本单位；（作业和进程是任务和执行之间的关系）
一个作业可由多个进程组成，且必须至少由一个进程组成，反之不成立；
Linux等分时系统中，并不强调作业概念；
（2）调度原则：
1、合理性：既要保证系统实现特殊功能的要求，又要能对各个任务合理的分配处理器份额（公平性）
2、有效性：要能使得系统的各个资源能被充分的利用
（3）最理想的目标：
- 单位时间运行尽可能多的作业 （提高系统吞吐率）
- 让处理器尽可能忙碌 （提高CPU利用率）
- 响应时间和周转时间尽可能短
- 各种IO设备得以充分利用
- 对所有的作业都是公平合理的
这些目标有些可能是冲突的，现实中尽量都兼顾，不一定都最优
（4）调度算法设计理念
-
调度算法与系统的设计目标保持一致
（如：服务器系统处理器调度算法和个人电脑的处理器调度算法肯定不一致） -
注意系统资源均衡使用
-
保证提交的作业在截止时间内完成
-
设法缩短作业的平均周转时间
大多数操作系统的都采取比较简单的调度算法，因为调度算法本身就会产生一定的开销
（5）调度决策的依据
依据包括：作业到达时间、作业优先级、作业所需CPU时间、存储要求、其他资源要求等
（6）性能衡量指标
1、作业平均周转时间：
作业的周转时间：从作业进入系统到作业完成的时间间隔
设有$n$个作业，第$i$个作业进入系统时间为$S_i$，完成的时间为$E_i$，则其周转时间$T_i$为 $E_i - S_i$；
这批作业平均周转时间为：
$T = \frac{\sum_{}T_i} {n}$
常常用于衡量不同调度算法对同一作业流的性能
2、平均带权周转时间：
设ri为作业i的实际执行时间
则平均带权周转时间（设为$W$）为：
$W = \frac{\sum_{} \frac{T_i}{r_i}} {n}$
常常用来衡量同一调度算法对不同作业流的性能衡量；
二、 处理器调度的算法
典型算法：
先来先服务算法 （FCFS，first come first service，非抢占式）：
只将作业到达系统的时间作为调度的依据；
最短作业优先算法（SJF，Shortest Job First，非抢占式）：
计算量越小的进程将会优先得到系统的调度（一旦开始周转就要进行到底，不能被其他作业抢占）；
这样可以降低整体的等待时间，从而降低整体周转时间；
最短剩余时间优先算法（SRTF，Shortest Remaining Time First，可抢占式）
首先执行剩余处理时间最少的过程;(当前作业的调度会被其他新来的、需要更短时间的作业抢占，是SJF调度算法的抢占版本)
上面三种调度算法考虑的因素都很片面，FCFS只考虑作业到达时间，SJF和SRTF只考虑作业的执行时间；
由于调度算法考虑因素的不全面，往往导致系统的性能不够好，或者不够公平；
比如SJF调度算法，会让一些很早就到达系统的计算量大的作业，长时间得不到CPU资源而处于饥饿状态，
这就不公平了；
（进程饥饿：指当等待时间给进程推进和响应带来明显影响称为进程饥饿）
最高相应比优先算法（HRN，Highest Response_ratio Next，非抢占式）：
响应比 = 作业周转时间 / 作业处理时间
= （作业处理时间 + 作业等待时间）/ 作业处理时间
= 1 + （作业等待时间 / 作业处理时间）
这样，作业的调度既受作业的等待时间影响，又受作业的处理时间影响；
在作业的等待时间一定的情况下，作业的处理时间越小，响应比就越大；（同SJF思想相同）
在作业的处理时间一定的情况下，作业的等待时间越大，响应比就越大；（弥补了SJF的缺点）
三、 单道环境下的调度
如题：
对于FCFS算法来说，执行的顺序为：J1、J2、J3、J4
对于SJF算法来说，执行的顺序为： J1、J3、J4、J2
对HRN算法来说，执行的顺序为： J1、J3、J2、J4
每执行完一个作业，都要计算剩余作业的相应比，处理器周转剩余作业中相应比最大的作业；
可以看到HRN算法的平均周转时间和平均带权周转时间不一定是最优的；
四、 多道环境下的调度
以有两道环境为例（内存中可以同时存放两个作业，且仍然是单核CPU），假设有四个任务，采用SRTF算法：
作业的执行顺序为： J2、J3、J4、J1
两道的环境中，如果内存中已经存放了两个作业，则即使已经出现了新的作业，仍然不能放入内存。
只有当内存中的一个作业执行完了，才能根据调度算法选择作业放入内存并且周转。
另外要注意，内存中的作业之间是可以互相抢占调度的。
五、 低级调度方式算法
（1）步骤：
记住进程的状态
决定进程什么时候获得处理器
决定进程占用处理器多长时间
把处理器分配给进程
收回处理器
（2）低级调度方式：
1、 可抢占式：
比正在运行的进程优先级更高的进程就绪时，可强行剥夺正在运行进程的CPU，提供给更高优先级的进程使用，或者当运行进程的时间片用完后被剥夺；
2、不可抢占式：
某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去；
如今的操作系统大都是可抢占式的调度方式了，因为只有这样才能更好的支进程持并发运行；
有些系统中是讲可抢占和不可抢占一起使用，有些进程不可抢占，如：内核进程、原语；
（3）低级调度算法：
1、先来先服务算法：
按照进程进入就绪队列的先后分配处理器，进程一旦占有处理器将一直运行，知道结束或阻塞；
（不可抢占，算法效率不高，不利于IO频繁的进程）
2、时间片轮转算法：
就绪队列中的每个进程轮流的运行一个时间片，时间片结束时，强迫当前进程让出处理器，等待下一轮调度；
（可抢占式，利于IO频繁的进程）
时间片的选取，不能太小也不能太大，要综合进程个数、切换开销、系统效率和相应时间等多方面综合考虑；
3、保证调度算法
对每个任务作出明确的性能保证，然后去实现它；
例如：
在一个有n个进程运行的系统中，保证每个进程获得CPU处理能力的1/n;
然后跟踪每一个进程自创建以来已经用了多少CPU时间，根据每个进程应获得的CPU时间，计算实际获得CPU时间和应获得的CPU时间之比，优先调度比率最低的进程；
4、彩票调度算法
彩票调度算法是保证调度算法的一种具体的实现方式；
算法为每一个进程发放一定数量的彩票，调度算法随机选择一张彩票，持有该彩票的进程获得系统资源。如果有些进程需要更多的机会，可以被给予更多的彩票，增加中奖机会；
（算法反应速度快，合作进程还可以交换彩票）
还有很多调度算法如：优先权调度、多级反馈队列调度等
