处理机调度与作业调度

本文介绍: 操作系统中的进程调度问题：包括进程调度多种算法的详细解释及计算过程

处理机调度

一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历如下的三级调度

高级调度

也称为作业调度、长程调度、接纳调度。调度对象是作业

主要功能：

·挑选若干作业进入内存

·为作业创建进程、分配必要的资源

·将新创建的进程插入就绪队列，准备执行

高级调度只有多道批处理操作系统中才有，分时和实时两种类型的OS中无需配置

高级调度运行频率较低，作业调度的周期较长，往往是一个或一批作业运行完毕才结束

中级调度

也称为内存调度

主要功能：

·实现进程的内外存切换

·实现进程的挂起与非挂起状态切换，即活动和静止状态的切换

中级调度实际上就是存储器管理中的对换功能

中级调度运行频率介于低级调度和高级调度之间

低级调度

也称为进程调度、短程调度。调度对象是进程

主要功能：

·决定就绪队列中的那个进程获得处理机

·有分配器（分配程序）执行把处理机分配给进程的具体操作

在多道批处理系统、分时和实时三种类型的OS中，都必须配置

低级调度的运行频率最高，一般进程调度算法不宜设计的太复杂

处理机调度算法的目标是提高资源利用率

CPU利用率=CPU有效工作时间/CPU总运行时间

CPU总运行时间=CPU有效工作时间+CPU空闲等待时间

一般使用周转时间的长短来评价批处理系统的性能

周转时间：作业提交给系统到作业完成的时间间隔

带权周转时间：周转时间/服务时间

作业调度

作业调度的主要任务有两个：①决定接纳多少作业②决定接纳那些作业

决定接纳多少作业：取决于多道程序度，即允许多少个作业同时在内存中允许

决定接纳那些作业：取决于调度算法

先来先服务调度算法

系统按照作业到达的先后次序进行调度。在就绪队列中等待时间越长的作业，优先级越高

可见进程先后进入内存的顺序为：P1-P2-P3-P4-P5。因此处理机也按照该顺序服务

	创建时刻	运行时间	CPU开始服务时间	结束服务时间	周转时间
P1	0	3	0	3	3-0=3
P2	2	6	3	9	9-2=7
P3	4	4	9	13	13-4=9
P4	6	5	13	18	18-6=12
P5	8	2	18	20	20-8=12

短作业优先调度算法

为了尽可能完成更多的作业，出现了短作业优先。作业所需服务时间越短，优先级越高

可见进程先后进入内存的顺序为：P1-P2-P3-P4-P5。按照运行时间长短排序为：P5-P1-P3-P4-P2

因此当进程P1执行完毕后，只有P2进程创建，因此执行进程P2。当P2执行完毕时（第9ms），进程P3、P4、P5都已经创建完毕，在就绪队列中排序。由于是短作业优先，因此优先执行进程P5，其次是P3，最后是P4

	创建时刻	运行时间	CPU开始服务时间	结束服务时间	周转时间
P1	0	3	0	3	3
P2	2	6	3	9	7
P3	4	4	11	15	11
P4	6	5	15	20	14
P5	8	2	9	11	3

高响应比优先调度算法

高响应比优点调度算法即考虑作业的等待时间，也考虑作业的服务时间。兼顾短作业，也不使长作业等待时间过长

优先权计算方式：

$priority=1+frac{WaitTime}{ServiceTime}$

其中Wai tTi m e是等待时间，Se r vi ceTi me是要求服务时间，pr io r i ty是优先权

优先权越大，越先进行服务

由上述公式可以看出①如果作业等待时间相同，则要求服务时间越短，优先权越高②如果要求服务时间相同，则等待时间越长，优先权越高③对于长作业而言，等待的时间越久优先权也高，也能获取处理机资源

可见进程先后进入内存的顺序为：P1-P2-P3-P4-P5

当进程P1执行完毕后，只有P2进程创建，因此执行进程P2。当P2执行完毕时（第9ms），进程P3、P4、P5都已经创建完毕，在就绪队列中排序。此时计算每个进程的响应比，分别为2.25、1.6、1.5。因此优先执行进程P3。P3执行完毕时（第13ms），计算进程P4、P5的响应比，分别为2.4和3.5。因此优先执行进程P5，最后执行进程P4

	创建时刻	运行时间	CPU开始服务时间	结束服务时间	周转时间
P1	0	3	0	3	3
P2	2	6	3	9	7
P3	4	4	9	13	9
P4	6	5	15	20	14
P5	8	2	13	15	7

轮转调度算法

轮转调度算法让就绪队列上的每个进程每次仅允许一个时间片，如果就绪队列上有n个进程，则每个进程每次都可以获得1/n的处理机时间

轮转调度算法中最重要的就是时间片的选择。如果时间片小，会频繁执行进程调度和进程上下文切换，导致系统开销增加；如果时间片太长，导致每个进程在一个时间片内完成，使轮转调度算法退化成先来先服务算法，无法满足用户需求

下图为轮询的过程，在进程创建之前不进入轮转。在程序运行结束后，退出轮转序列

第一轮	P1
第二轮	P1（第2ms，进程P2创建）	P2
第三轮	P1（第4ms，进程P3创建，进程P1运行结束）	P2	P3（第6m s，进程P4创建）	P4
第四轮		P2（第8m s，进程P5创建）	P3	P4	P5
第五轮		P2	P3	P4	P5（第15m s，进程P5运行结束）
第六轮		P2	P3（第17ms，进程P3运行结束）	P4
第七轮		P2（第19ms，进程P2运行结束）		P4（第20ms，进程P4运行结束）