操作系统教程—Linux实例分析孟庆昌第3章处理机调度

《操作系统教程—Linux实例分析孟庆昌第3章处理机调度》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章处理机调度3.1调度级别3.2作业调度3.3进程调度3.4性能评价标准3.5常用调度算法3.6Linux系统中的进程调度习题3.1调度级别一般来说，作业从进入系统到最后完成，可能要经历三级调度：高级调度、中级调度和低级调度。(1)高级调度：又称作业调度。(2)中级调度：为了使内存中同时存放的进程数目不至于太多，有时就需要把某些进程从内存中移到外存上，以减少多道程序的数目，为此设立了中级调度。(3)低级调度：又称进程调度。其主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程。3.2作业调度

2、3.2.1作业状态如前所述，作业从提交给系统，直到完成任务后退出系统前，在整个活动过程中它会处于不同的状态。通常，作业状态分为四种：提交、后备、执行和完成，如图3-1所示。图3-1作业的基本状态（1）提交状态——即用户向系统提交一个作业时，该作业所处的状态。（2）后备状态——即用户作业经输入设备（如读卡机）送入输入井（磁盘）中存放，等待进入内存时所处的状况。（3）执行状态——即作业分配到所需的资源，被调入内存，并且在处理机（CPU）上执行相应的程序时所处的状况。（4）完成状态——即作业完成了计算任务，

3、结果由打印机输出，最后由系统回收分配给它的全部资源，准备退出系统时的作业状况。3.2.2作业调度1.作业控制块（JCB）在多道批处理系统中通常有上百个作业被收容在输入井（磁盘）中。为了管理和调度作业，系统为每个作业设置了一个作业控制块（JCB），它记录该作业的有关信息。不同系统的JCB的组成内容有所区别。JCB的主要内容如图3-2所示。图3-2作业控制块2.作业调度的功能如上所述，作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转换。具体来说，通常作业调度程序要完成以下工作(这

4、就是作业调度的功能)。(1)记录系统中各个作业的情况。(2)按照某种调度算法从后备作业队列中挑选作业。(3)为选中的作业分配内存和外设等资源。(4)为选中的作业建立相应的进程。(5)作业结束后进行善后处理工作，如输出必要的信息，收回该作业所占用的全部资源，撤消与该作业相关的全部进程和该作业的JCB。3.3进程调度3.3.1进程调度的功能和时机进程只有在得到CPU之后才能真正活动起来。一个就绪进程怎样获得CPU的控制权呢?这是由进程调度实现的，进程调度也被称为低级调度。进程调度程序也往往被称为低级调度程

5、序，它完成进程状态从就绪态到运行态的转化。实际上，进程调度程序主要是完成一台物理的CPU转变成多台虚拟（或逻辑）的CPU的工作。1.功能进程调度的主要功能是：(1)保存现场。（2）挑选进程。（3）恢复现场。2.时机在什么情况下执行进程调度呢?一般是在以下事件发生后作进程调度：（1）完成任务。（2）等待资源。（3）运行到时。（4）发现标志。（5）创建新进程。图3-3进程调度流程3.3.2两级调度模型作业调度和进程调度是CPU主要的两级调度，二者的关系可用图3-4表示。图3-4两级调度简化队列图3.3.3

6、三级调度模型当一个系统中三级调度同时存在时，其相互间的关系如图3-5所示。简单来说，作业调度从后备作业中选择一批合适的作业放入内存，并创建相应的进程；进程调度从就绪队列中选择一个合适进程，令其投入运行；中级调度将在内存中驻留时间较长的进程换到磁盘上：从就绪队列转到就绪/挂起队列，从阻塞队列转到阻塞/挂起队列。当内存中有足够的可用空间时，中级调度就从就绪/挂起队列中选择一些合适的进程放入内存，使之进入就绪队列。图3-5三级调度简化队列3.4性能评价标准(1)所用算法应保证实现系统的设计目标。(2)对所有

7、作业或进程应公平对待。(3)均衡使用资源，尽量使系统中各种资源都同时得到利用。(4)兼顾响应时间和资源利用率。(5)基于相对优先级，但避免无限延期。(6)系统开销不应太大。3.4.2性能评价标准1.CPU利用率CPU的利用率可从0～100%。2.吞吐量吞吐量表示单位时间内CPU完成作业（或进程）的数量。3.周转时间从一个特定作业的观点出发，最重要的标准就是完成这个作业要花费多长时间。作业i的周转时间Ti为其中，tsi表示作业i的提交时刻，tci表示作业i的完成时刻。系统中n个作业的平均周转时间T为作业

8、周转时间没有区分作业实际运行时间长短的特性，因为长作业不可能具有比运行时间还短的周转时间。为了合理反映长短作业的差别，定义了另一个衡量标准——带权周转时间W，即W=T/R，其中T为周转时间，R为实际运行时间。平均带权周转时间W为4.就绪等待时间CPU调度算法并不真正影响作业执行或I／O操作的时间数量。各种CPU调度算法仅影响作业(进程)在就绪队列中所花费的时间数量。5.响应时间在交互式系统中，周转时间不可能是最好的评价标准。一个进程往往可以很早地就产生某