第6章处理机调度课件

(一)处理机的多级调度

(二)作业调度

(三)进程调度

第六章处理机调度1

(一)处理机的多级调度一.处理机调度的功能

确定数据结构

制订调度策略(调度原则)

给出调度算法

具体的实施处理机分派不同类型的操作系统往往采用不同的处理机分配方法。

2

二.批处理系统中的处理机调度处理机调度分为两级：作业调度和进程调度。

1.作业调度作业调度又称为宏观调度。任务——对存放在辅存设备上的大量作业，以一定的策略进行挑选，分配主存等必要的资源，建立作业对应的进程，使其投入运行。

2.进程调度进程调度又称为微观调度。任务——对进入主存的所有进程，确定哪个进程在什么时候获得处理机，使用多长时间。

3

三.多任务操作系统中的处理机调度在分时系统或支持多任务并发执行个人计算机操作系统中，系统将用户提交的任务处理为进程，一个进程又可以创建多个子进程，形成可以并发执行的多进程。进程调度的任务是：当处理机空闲时，以某种策略选择一个就绪进程去运行，并分配处理机的时间。

4

四.多线程操作系统中的处理机调度在支持多线程运行的系统中，一个进程可以创建一个线程，也可以创建多个线程。系统为进程分配它所需要的资源，而处理机的分配单位则为线程。系统提供线程调度程序，其功能是当处理机空闲时，以某种策略选择一个就绪线程去运行，并分配处理机时间。

5

(二)作业调度一.作业的状态作业在整个活动期间一共有四种状态，提交状态：用户将自己的程序和数据提交给系统，等待输入。后备状态：作业已存放在磁盘上，等待调度。执行状态：作业进入主存开始运行。完成状态：作业计算完成开始，退出系统。

6运行就绪完成等待后备提交作业调度作业调度作业录入执行运行就绪完成等待后备提交作业调度作业调度作业录入执行运行就绪完成等待后备提交作业调度作业调度作业录入执行7

二.作业调度的功能

1.确定数据结构建立作业控制块jcb(jobcontrolblock)。作业控制块记录了每个作业类型、状态、资源请求及分配情况。

2.确定调度策略与调度算法

3.分配资源为选中的作业分配所需要的系统资源。

4.善后处理收回该作业所占用的全部资源，撤消作业控制块以及与该作业有关的全部进程。

8

三.作业控制块作业控制块jcb存在于系统的整个过程中，jcb是一个作业存在的标志。jcb的主要内容如下：

作业名

资源要求（用户提供） 资源使用情况 估计执行时间 进入系统时间 最迟完成时间 开始执行时间 要求的主存量 已执行时间 要求外设的类型及台数 主存地址 要求文件量和输出量 外设台号

类型 优先级 控制方式（联机/脱机） 状态（后备/执行/完成） 作业类型（CPU偏多，I/O偏多，均衡）

9

四.作业调度算法性能的衡量采用平均周转时间和平均带权周转时间来衡量作业调度算法性能的好坏。

1.周转时间一个作业提交给计算机系统到该作业的结果返回给用户所需要的时间。

(1)定义ti=tci-tsi

ti—作业i的周转时间

tsi—作业i的提交时间

tci—作业i的完成时间

(2)意义说明作业i在系统中停留时间的长短。

(3)平均周转时间t=

n为进入系统的作业个数10

2.带权周转时间

(1)定义一个作业的周转时间与其运行时间的比值。

wi=

(2)意义说明作业i在系统中相对等待时间。

(3)平均带权周转时间

t=

tri为作业的实际执行时间11

五.作业调度算法

1.先来先服务调度算法(FCFS)(1)策略：按作业来到的先后次序进行调度。

(2)特点：简单，易实现。

(3)讨论在先来先服调度算法下的周转时间与带权周转时间

作业提交时间执行时间开始时间完成时间周转时间带权周转时间

18.00 2.00 2 8.50 0.503 9.00 0.1049.500.20

8.0010.002.001

10.0010.502.004

10.5010.601.6016

10.6010.801.306.5

平均周转时间t=

平均带权周转时间w=1.7256.87512

五.作业调度算法

2.短作业优先调度算法

(1)策略：按作业按作业请求运行的时间长短进行调度。

(2)特点：易实现，系统吞吐量高；只照顾短作业，而没有考虑长作业的利益易实现。

(3)讨论短作业优先调度算法下的周转时间与带权周转时间作业提交时间执行时间开始时间完成时间周转时间带权周转时间

18.00 2.00 2 8.50 0.503 9.00 0.1049.500.20

平均周转时间t=

平均带权周转时间w=1.555.15

8.0010.002.001

10.3010.802.304.6

10.0010.101.1011

10.1010.300.80413先来先服务调度算法和短作业优先调度算法（比较）143.响应比高者优先调度算法：先来先服务和短作业优先算法都有其片面性，先来先服务调度算法只考虑作业的等待时间，而忽视了作业的运行时间，短作业优先算法则相反，只考虑了作业的运行时间，而忽视了作业的等待时间。响应比高者优先调度算法是介于这两种算法之间的一种折中的算法。15作业提交时间执行时间开始时间完成时间周转时间带权周转时间

18.00 2.00 2 8.50 0.503 9.00 0.1049.500.20

8.0010.002.001

10.0010.101.1011

作业1执行之后，计算其余作业的响应比响应比2=1+（10.00–8.50）/0.5=1+3=4响应比3=1+（10.00–9.00）/0.1=1+10 =11响应比4=1+（10.00–9.50）/0.2=1+2.5=3.5因为作业3的响应比最高，所以选择作业3执行作业3执行之后，计算其余作业的响应比响应比2=1+（10.10–8.50）/0.5=1+3.2=4.2响应比4=1+（10.10–9.50）/0.2=1+3=4因为作业2的响应比较高，所以选择作业2执行

10.1010.602.10 4.2

10.6010.801.306.5

平均周转时间t=1.625平均带权周转时间w=5.67516

响应比高者优先调度算法的特点响应比高者优先调度算法其调度性能不如短作业优先算法好，但它及照顾到用户到来先后，又考虑到系统服务时间长短，从理论上讲是比较完备的调度算法。但作业调度程序要统计作业的等待时间，使用用户的估计的运行时间，并要作浮点运算（这是系统程序最忌讳的）浪费大量的计算时间，这是系统程序所不允许的。174.优先数调度算法优先数调度算法是综合考虑各方面的因素（作业等待时间、运行时间、缓急程度，系统资源使用等），给每个作业设置一个优先数，调度程序总是选择一个优先数最大（或者最小）的作业调入（系统）内存。这种算法实现的困难在于如何综合考虑，这些因素之间的关系怎样处理。算法思想： 计算优先数，确定优先级，根据优先级大小挑选作业。 例如，优先数=等待时间2–要求执行时间–16*输出量特点： 迅速地执行一个短作业，但偶尔也要执行一个在磁盘中等待了很久的作业。此时“等待时间”的值远远超过其他2项目的和185.均衡调度算法均衡调度算法就是一种更为理想化的调度算法，如何实现就更困难，并且算法本身的开销有时会远大于先来先服务和短作业优先调度算法。 先来先服务和短作业优先调度算法是2种开销较小的算法，这也是这两种算法被众多系统采用的最根本的原因。19

(三)进程调度一.调度/分派结构

1.调度 在众多处于就绪状态的进程中，按一定的原则选择一个进程。 组织和维护就绪进程队列。包括确定调度算法、按调度算法组织和维护就绪进程队列。

2.分派 当处理机空闲时，是移出就绪队列中第一个进程，并赋予它使用处理机的权利。

调度与进程控制和进程通信的功能有密切的联系，当一个进程阻塞时，这种进程将进入相应的等待队列中，并让出CPU，调用进程分派程序选择一个就绪进程占用CPU；当一进程被唤醒时，这种进程将插入到就绪进程队列中。在一般的操作系统教材中把上述功能称为进程调度。

20

3.调度∕分派结构图

ready_q

scheduler

suspwakeupreceive……pcb6……pcb4pcb3pcb2pcb1

dispatcher

CPU21

二.进程调度的功能1.记录和保持系统中所有进程的有关情况和状态特征 有关进程调度的信息是记录在PCB中的，在进程调度中用到的主要是进程的状态、调度优先级（优先数）、就绪进程队列等。2.决定分配（处理机）策略 确定进程调度的策略，例如，先来先服务、优先数调度策略，调度策略的不同，组织就绪进程队列的方式也不同。

优先调度原则——

进程就绪队列按进程优先级高低排序

先来先服务原则——

进程就绪队列按进程来到的先后次序排序22

3.实施处理机的分配 调度时机（UNIX系统中）： （1）进程完成； （2）进程阻塞； （3）进程出错挂起； （4）分时系统中时间片到； （5）高优先级进程就绪（抢占式系统）；4.进程调度的准则 （1）CPU使用率；40%~90%

（2）吞吐率；单位时间内所完成的进程数 （3）周转时间； （4）响应时间；交互式系统 （5）等待时间；23

三.进程调度方式

1.什么是调度方式当一进程正在处理机上执行时，若有某个更为“重要而紧迫”的进程需要进行运行，系统如何分配处理机。

2.非剥夺方式一种是让正在执行的进程继续执行，直到该进程完成或发生某事件而进入“完成”或“阻塞”状态时，才把处理机分配给“重要而紧迫”的进程。

3.剥夺方式当“重要而紧迫”的进程一到，便暂停正在执行的进程，立即把处理机分配给优先级更高的进程。

24

四.进程调度算法（与作业调度算法有何关系？）

1.进程优先数调度算法

(1)什么是进程优先数调度算法 预先确定各进程的优先数，系统把处理机的使用权赋予就绪队列中具备最高优先权(优先数和一定的优先级相对应)的就绪进程。

优先数调度算法是目前操作系统广泛采用的一种进程调度算法，这种算法按照某种原则由系统（或用户、或系统与用户结合）赋予每个进程一个优先数，在处理机空闲时，进程调度程序就从就绪进程中选择一个优先数最大（或者最小）的进程占用CPU（该进程就从就绪状态转换成运行状态）。25

(2)优先数的分类及确定静态优先数——*在进程被创建时确定，且一经确定后在整个进程运行期间不再改变。*静态优先数的确定 系统确定：运行时间、使用资源，进程的类型 用户确定：紧迫程度，计费标准 系统与用户结合：用户可以为本用户的进程设置优先数，但不是作调度用，系统还要根据系统情况把用户设置的进程优先数作为确定进程优先数的一个参数26

动态优先数——*进程优先数在进程运行期间可以改变。*动态优先数的确定——

进程使用CPU超过一定数值时，降低优先数； 进程进行I/O操作后，增加优先数 进程等待时间超过一定数值时，提高优先数27

2.循环轮转调度算法

(1)什么是循环轮转调度算法当CPU空闲时，选取就绪队列首元素，赋予一个时间片，当时间片用完时，该进程转为就绪态并进入就绪队列末端。

该队列排序的原则是什么？pcb1pcb2pcbnCPU完成28

(2)简单循环轮转调度就绪队列中的所有进程以等速度向前进展

q=t/nt为响应时间，n为进入系统的进程数目。

q值如何确定?(3)循环轮转调度算法的发展可变时间片轮转调度、多重时间片循环调度29

系统按进程转换成就绪状态的时间的降序排队，调度程序每次调度，总是从队首移出一程的PCB，然后，将此进程投入运行（由就绪状态转换成运行状态）。一个运行时间片到的进程从运行状态转换成就绪状态后，排在就绪队列的队尾。评价：优点是实现简单、系统开销小缺点是不灵活，当系统中进程较少时，系统开销变大

为什么？由于该算法简单易于实现，且系统开销较小，早期的分时操作系统和目前一些应用系统中广泛采用了这种调度算法。

30

(3)循环轮转调度算法的发展可变时间片轮转调度——将固定时间片改为可变时间片

为了克服前种调度算法的缺点，人们设计出一种可变时间片的调度算法，其思想是：时间片的大小是可变的，系统可根据系统中当前的进程数来确定时间片的大小。 这种算法从理论上克服了系统中进程数很少时系统开销大的缺点，但修改时间片的大小，统计系统进程的数量也需要消耗系统时间，还有一个调整时间片大小的周期，太大，等于是固定时间片，太小，系统开销很大，得不尝失。例如，响应时间t=3s，当n=30，q=0.1s；当n=6，q=0.5s多重时间片循环调度 将单一就绪队列改为多就绪队列（见下页）31

五.调度用的进程调度变迁图（多重时间片循环调度）运行500ms100ms因I∕O而等待高优先就绪低优先就绪进程调度进程调度时间片到请求I/OI/O完成32

1.队列结构

I/O等待队列——

一个进程如果请求I/O，进入I/O等待队列

低优先就绪队列——

一个进程如果在运行中超过了它的时间量，进入低优先就绪队列

高优先就绪队列——

当进程从等待状态变为就绪状态时，进入高优先就绪队列

2.进程调度算法优先调度与时间片调度相结合的调度策略33

(1)当CPU空闲时，若高优先就绪队列非空，则从高优先就绪队列中选择一个进程运行，分配时间片为100ms。

(2)当CPU空闲时，若高优先就绪队列为空，则从低优先就绪队列中选择一个进程运行，分配时间片为500ms。

3.调度效果优先照顾了I∕O量大的进程；适当照顾了计算量大的进程。34

【问】某计算机系统中，进程调度采用时间片轮转调度算法。每个进程得到的时间片可随进程的执行情况而变化，在过去的时间里，若进程经常启动外设则给它分配较短的时间片；若启动外设次数很少则分配一个较长的时间片。为什么？【答】这种分配方法能够提高处理器（CPU）的利用率。

因为启动外设的速度是很慢的，在某个进程使用外设的过程中是处于一种阻塞的状态，CPU只能闲置，极大地降低了CPU利用率，CPU完全可以利用该进程读写外设的时间运行其他的进程。比如一个进程A每使用CPU时间为1ms就要进行外设操作，假设外设操作时间为30ms，那么如果给他分配的时间片为1ms，好，那么CPU没有被耽误；如果分配5ms，那么CPU闲置4ms；如果分配30ms，那29ms中CPU都没事干。

35

【问】在系统中设置两个就绪队列，一个是时间片较短的进程就绪队列，另一个是时间片较长的进程就绪队列。那么，在进程调度时应优先从哪个队列中选取一个就绪进程占有CPU？为什么？【答】这是进程调度中的短任务优先原则。如果两个进程A和B，A要1ms就能做完，B要30ms才能做完，那么如果A不幸排在B后面，那么A要等30ms才能运行，那么程序响应时间和交互体验很差。如果先A后B，那么A的响应时间为1ms，B为31ms；如果先B后A，那么A的响应时间为31ms，B为30ms。

36

第六章小结一.处理机的两级调度二.作业调度

1.作业的四种状态

2.作业控制块

3.周转时间、带权周转时间：定义物理意义

4.常用的作业调度算法先来先服务短作业优先对一批作业，若采用两中不同的调度算法，能分析、计算调度性能的好坏。37

三.进程调度

1.调度方式非剥夺方式剥夺方式

2.常用的进程调度算法优先数调度循环轮转调度

3.调度用的进程状态变迁图通过调度用的进程状态变迁图，能分析系统采用的调度策略，调度性能的好坏。能分析因果变迁及条件。38（2013真题）45.(7分)某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许一个人通过。参观者的活动描述如下：cobegin参观者进程i：{ …

进门；

…

参观；

…

出门；

…}coend请添加必要的信号量和P、V(或wait()、signal())操作，以实现上述操作过程中的互斥与同步。

要求写出完整的过程，说明信号量含义并赋初值。

39解答：main(){

intempty=500；

//semaphoreempty=500;//可容纳人数的上限

int

mutex=1；

//用于出入口资源的控制

cobegin

visitori();

coend}visitori(){ ……

P(empty);

P(mutex);

进门

V(mutex);

参观

P(mutex);

出门；

V(mutex);

V(empty); ……}40（2014真题）【47】系统中有多个生产者进程和消费者进程，共享用一个可以存1000个产品的缓冲区（初始为空），当缓冲区为未满时，生产者进程可以放入一件其生产的产品，否则等待；当缓冲区为未空时，消费者进程可以取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品，请用信号量P，V（wait，signed）操作实现进程间的互斥和同步，要求写出完整的过程；并指出所用信号量的含义和初值。41解答：main(){

intempty=1000，full;

int

mutex=1,s0j=0;

cobegin Pi();C0();Cj();

coend

}Pi(){ while(1){

生产一产品；

P(empty);

P(mutex);

产品放入缓冲区；

V(mutex);

V(full);}}42C0(){

for(intt=1;t<=10;t++){

P(full);

P(mutex);

取出一个产品；

V(mutex);

V(full);

消费一个产品;}V(s0j);}Cj(){ while(1){ P(s0j); V(s0j);

P(full);

P(mutex);

取出一个产品

V(mutex);

V(empty);

消费一个产品

}}43(2011真题)【45】(8分)某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：cobegin{

process顾客i

{ 从取号机取号； 等待叫号; 获得服务;

}

process营业员

{

while(TRUE)

{ 叫号; 为顾客服务;

}

}}coend

请添加必要的信号量和P、V(或wait()、signal())操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。44解答：main(){

int

seets=10;//表示空余座位

int

mutex=1;//管理取号机的互斥信号量

intcustom=0;//顾客数量信号量

cobegin process顾客i(); process营业员();

coend

}45process营业员(){ while(1){

P(custom); //看是否有顾客 叫号； 为顾客服务；

}}process顾客i();{

P(seets);//找个空位

P(mutex);//取号机空否

从取号机上取号；

V(mutex);//放开取号机

V(custom);//通知营业员等待叫号；

V(seets);//离开座位接受服务；}46(2009真题)45.（7分）三个进程P1、P2、P3互斥使用一个包含N（N>0）个单元的缓冲区。P1每次用produce（）生成一个正整数并用put（）送入缓冲区某一空单元中；P2每次用getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。

47解答：定义信号量S12控制P1与P2之间的同步； 信号量S13控制P1与P3之间的同步； 信号量empty控制生产者与消费者之间的同步； 信号量mutex控制进程间互斥使用缓冲区。

main(){ int

s12=0,s13=0,emp