第三章处理机调度与死锁1.ppt

1、第三章,处理机调度与死锁 （一）,2020/10/11,数学科学学院,2,本章主要内容,调度的基本概念 基本调度算法 死锁的基本概念 解决死锁的几种方法,2020/10/11,数学科学学院,3,调度主要讨论处理机分配问题,在多道单处理机系统环境下，内存就绪队列往往有多个进程等待处理机，而分配处理机的任务通常是由调度程序完成的。 由于处理机是计算机系统中最重要的资源，故提高处理机的利用率、改善系统性能很大程度取决于处理机调度性能的优劣。 处理机调度的主要目标 对CPU资源进行合理的分配使用，以提高CPU利用率 使各用户公平地得到处理机资源 减少用户的响应时间。 处理机调度管理问题是操作系统设计的

2、核心问题之一。,2020/10/11,数学科学学院,4,3.1 处理机调度的层次,多道批处理系统的一个作业被提交后，若想得到处理机运行，须经历作业调度、进程调度； 而一个终端型作业，则只需经历进程调度，即可获得处理机运行； 在作业执行过程，由于某种原因，可通过中级调度，将作业换出内存，将其挂起暂停执行，当条件允许，中级调度又可将其调入内存继续执行。 由上可看出，处理机调度是分层次的。 对于每一层次的调度，都可选择不同的调度方式和调度算法。,2020/10/11,数学科学学院,5,1处理机调度的层次 处理机是计算机系统中的重要资源，处理机调度算法对整个计算机系统的综合性能指标有重要影响。可把处理

3、机调度分成三个层次：高级调度，中级调度，低级调度 高级调度（作业调度/宏观调度/长程调度/接纳调度/收容调度） 按一定原则选择外存输入井上后备作业队列中的一个或多个作业进入内存，并为其建立相应的进程。 它决定允许哪些作业有资格竞争系统资源。 它只涉及虚拟处理机分配 分时与实时系统无须此层调度,3.1 处理机调度的层次,2020/10/11,数学科学学院,6,低级调度（进程调度/微观调度/短程调度） 当内存就绪队列不为空时，它决定哪一个就绪进程可分配到中央处理机（即低级调度是将处理机实际地分配给某进程）。 低级调度是由每秒可操作许多次的处理机调度程序执行，处理机调度程序应常驻内存。 进程调度的方

4、式：非抢占方式（非剥夺）：实时性差 抢占方式（剥夺） 抢占的方式有：1 时间片原则； 2 优先级原则； 3 短进程优先原则。,3.1 处理机调度的层次,2020/10/11,数学科学学院,7,中级调度（交换调度） 它决定允许哪些进程竞争处理机。 中级调度通过使进程临时挂起和激活的方法对系统负载波动作出反映，以便获得平稳的系统操作和实现较好的系统综合性能目标。 中级调度的作用是作为作业进入系统和将中央处理机分配给这些作业二者之间的一个缓冲 引入中级调度的目的是为提高内存的利用率和系统吞吐量,3.1 处理机调度的层次,2020/10/11,数学科学学院,8,3.1 处理机调度的层次,中级调度属内存

5、管理部分。涉及进程在内外存间的交换； 从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。（指令和数据必须在内存里才能被处理机直接访问）。,2020/10/11,数学科学学院,9,作业状态及其转换图,spooling 系统,提交,外存,就绪,等待,运行,就绪,等待,交换调度,完 成,作业调度,进程调度,后备,收容,执行,2020/10/11,数学科学学院,10,2、调度队列模型,2020/10/11,数学科学学院,11,2、调度队列模型,2020/10/11,数学科学学院,12,同时具有三级调度的调度队列模型,中级调

6、度,2020/10/11,数学科学学院,13,1作业调度及其功能 作业调度:按照某种调度算法，从后备作业队列中选取 一个或一批作业，使其进入内存运行。完成作业从后备状态到执行状态和从执行状态到完成状态的转变。 主要功能:是审查系统是否能满足用户作业的资源要求以及按照一定的算法选取作业。 记录已进入系统的各作业的情况（JCB：Job Control Block）； 按一定的调度算法，从后备作业中选择一个或几个作 业进入系统内存； 为被选中的作业创建进程，并且为其申请系统资源； 作业结束后作善后处理工作。,3.2 作业调度,2020/10/11,数学科学学院,14,后备作业队列空,按调度算法从后备

7、作 业队列中选出一作业,调用存储、设备管理 程序，审核资源要求,资源要求能满足？,放弃该 作业,否,分配资源,调用进程管理 程序建立进程,进程调度,否,是,出 口,作业从后备状态到执行状态,是,2020/10/11,数学科学学院,15,撤销该作业的所有进程及作业的JCB,调用存储管理，设备管理回收 分配给该作业的全部资源,调用会计程序，计算该作业的执行费用,调度下一个作业,作业从执行状态到完成状态,2020/10/11,数学科学学院,16,3.1 处理机调度的层次,2. 作业调度所考虑的问题： 每次能调入多少作业进入内存取决于系统的“多道程序度” 和资源利用情况； 选择哪些作业进入内存取决于调

8、度算法和资源利用情况； 何时调入作业进入内存取决于是否有作业退出系统，或内存是否有足够资源。,2020/10/11,数学科学学院,17,作业控制块JCB,2020/10/11,数学科学学院,18,作业调度算法规定了从后备作业队列中选择作业进入系统内存的原则。 调度原则 应与系统的整体设计目标一致，尽量提高系统的吞吐量 均衡利用系统中各种资源，考虑负载均匀 对所有作业应该公平合理，保证各类作业的执行 对优先级较高的作业优先调度 应有较快的响应时间,3.作业调度原则与性能衡量,3.2 作业调度,2020/10/11,数学科学学院,19, 性能衡量 通常采用平均周转时间和带权平均周转时间 周转时间T

9、i ： 作业i从提交时刻Tsi到完成时刻Tei称为作业的周转时间 Ti = Tei - Tsi 完成 提交,3.2 作业调度,2020/10/11,数学科学学院,20,作业平均周转时间为（有n个作业，n=1) n T=1/n Ti i=1 一个作业的周转时间说明了该作业在系统内停留的时间 其中包含两部分：一是等待时间；二为执行时间 即 Ti = Twi + Tri (停留时间),3.2 作业调度,2020/10/11,数学科学学院,21, 带权周转时间Wi： Wi=Ti/Tri Tri :作业i 的实际运行时间 平均带权周转时间为： W=,3.2 作业调度,2020/10/11,数学科学学院,

10、22,3.2 作业调度,响应时间：从提交一个请求到首次产生响应 CPU、I/O执行期：分CPU忙和I/O忙 截止时间：某任务必须开始执行（或必须完成）的最迟时间（开始截止、完成截止）。它是评价实时系统性能的重要指标。 优先权,2020/10/11,数学科学学院,23,（1）先来先服务（FCFS）调度算法 既适合作业调度，也适合进程调度。 将用户作业（/就绪进程）按提交顺序（/变为就绪状态）的先后排成队列，并按照先来先服务的方式进行调度处理。它是一种最普遍和最简单的方法。 优先考虑在系统中等待时间最长的作业（进程），而不管要求运行时间的长短。, 作业调度算法,3.2 作业调度,2020/10/1

11、1,数学科学学院,24,FCFS算法调度例,作业,2020/10/11,数学科学学院,25,3.2 作业调度,FCFS调度算法的特点： 实现简单； 效率较低； 有利于运行时间长的作业（进程），不利于短作业（进程）； 有利于CPU繁忙型的作业（进程），不利于I/O繁忙型的作业（进程）。,2020/10/11,数学科学学院,26,（2）短作业（进程）优先法（SJF/SPF）,既适合作业调度，也适合进程调度 短作业（进程）优先调度算法：考虑作业（进程）的运行时间，每次总是选择一个运行时间最短的作业（进程）执行. 分为：非抢占式和抢占式 一般情况下这种调度算法比先来先服务调度算法的效率要高一些。,3.

12、2 作业调度,2020/10/11,数学科学学院,27,SJF/SPF算法例1,2020/10/11,数学科学学院,28,SJF/SPF算法例2,2020/10/11,数学科学学院,29,3.2 作业调度,SJF/SPF优点：调度性能较好。 SJF/SPF缺点： 1）不利于长作业（进程）。 2）不考虑作业（进程）的紧迫程度。 3）估计的运行时间很难准确获得。 4）如果作业的到来顺序及运行时间不合适，可能会出现饥饿现象。 例如，系统中有一个运行时间很长的作业JN，和几个运行时间短的作业，若系统不断地有运行时间小于JN的作业的到来，这样作业JN就得不到调度而出现饥饿现象。,2020/10/11,数

13、学科学学院,30,3.2 作业调度,2020/10/11,数学科学学院,31,(3) 最高响应比作业优先算法（HRN） 最高响应比作业优先算法是对FCFS方式和SJF方式的一种综合平衡。 先来先服务和短作业优先算法都有其片面性。 先来先服务调度算法只考虑作业的等待时间，而忽视了作业的运行时间； 短作业优先算法则相反，只考虑了作业运行时间，而忽视了作业等待时间。 响应比高者优先调度算法是介于这两种算法之间的一种折衷的算法。,3.2 作业调度,2020/10/11,数学科学学院,32,3.2 作业调度,响应比R：系统对作业的响应时间与作业要 求运行时间的比值 R 响应时间 / 要求运行时间 (作业

14、等待时间需运行时间)/需运行时间 1已等待时间 / 需运行时间 1W/T,2020/10/11,数学科学学院,33,响应比R不仅是要求运行时间的函数，而且还是等待时间的函数。 由于R与要求运行时间成反比，故对短作业是有利的； 又因R与等待时间成正比，故长作业随着其等待时间的增长，也可获的较高的相应比。 该算法既照顾了先来者，又优待了短作业，是上述两种算法的一种较好的折衷。,3.2 作业调度,2020/10/11,数学科学学院,34,作业 提交时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转 1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.1

15、0 10.60 2.10 4.20 3 9.00 0.10 10.00 10.10 1.10 11.00 4 9.50 0.20 10.60 10.80 1.30 6.50 平均周转时间1.625h 带权周转时间 5.675h Rp(1): 作业2: 1+(10-8.5)/0.5=4 作业3: 1+(10-9)/0.1=11 作业4: 1+(10-9.5)/0.2=3.5 Rp(2): 作业2: 1+(10.1-8.5)/0.5=3.2 作业4: 1+(10.1-9.5)/0.2=3 作业执行顺序：1，3，2，4,3.2 作业调度,2020/10/11,数学科学学院,35,HRN例,注：式中的

16、时间按分钟计算,2020/10/11,数学科学学院,36,3.2 作业调度,该算法从理论上讲是比较完备的，但 作业调度程序要统计作业的等待时间，使用用户需估计的运行时间，不实际； 每次调度要做浮点运算（这是系统程序最忌讳的）浪费大量的计算时间，是系统程序所不允许的。,2020/10/11,数学科学学院,37,3.2 作业调度,（4）优先数调度算法 优先数调度算法是综合考虑各方面的因素（作业等待时间、运行时间、缓急程度，系统资源使用等），给每个作业设置一个优先数 调度程序总是选择一个优先级最高（即优先数最大或者最小）的作业调入（系统）内存。 这种算法实现的困难在于如何综合考虑，这些因素之间的关系

17、怎样处理。,2020/10/11,数学科学学院,38,3.3 进程调度,进程调度的功能 从就绪队列中挑选一个进程到处理机上运行 作业调度程序在挑选作业进入主存运行时，要为该作业建立相应的进程。在作业完成后要撤销该作业的全部进程。 一个进程被建立后，系统为了便于对进程的管理，将系统中的所有进程按其状态组织成不同的进程队列。,2020/10/11,数学科学学院,39,3.3 进程调度,进程调度的相关工作： 1.记录和保持系统中所有进程的有关情况和状态特征 有关进程调度的信息是记录在PCB中的，在进程调度中主要用到的是进程的状态、调度优先级（优先数）、就绪的进程队列等。 2.决定分配（处理机）策略

18、确定进程调度的策略，如先来先服务、优先数调度策略。调度策略不同，组织就绪进程队列的方式也不同。 先来先服务调度策略，就绪队列按等待时间大到小顺序排队； 优先数调度调度策略，就绪进程队列按优先数的升序（或降序）的方式排队。,2020/10/11,数学科学学院,40,3.3 进程调度,3.实施处理机的分配 进行进程上下文的切换 总而言之，进程调度包括： 调度算法的选择，即按什么原则分配CPU 调度时机的选择，即何时分配CPU 实施进程调度，即如何分配CPU，CPU调度过程（调度程序，进程的上下文切换）,2020/10/11,数学科学学院,41,3.3 进程调度,进程调度程序（或称调度程序）: 实施

19、进程调度的内核程序。 在通常的操作系统原理中，该程序属于系统进程的执行程序。 有些操作系统是把进程调度程序作一个特别的处理，如早期的操作系统中把进程调度程序称为交通控制程序，不属于系统中的任何进程。 进程上下文 是进程执行活动全过程的静态描述。包括计算机系统中与执行该进程有关的各种寄存器的值、程序段，在经过编译之后形成的机器指令代码集、数据集及各种堆栈值和PCB结构。,2020/10/11,数学科学学院,42,3.3 进程调度,进程调度的时机 指什么情况下引起进程调度程序工作。 进程调度的时机与进程调度的方式有关。 进程调度时机如下： （1）正在执行的进程正确完成或由于某种错误而终止运行； （

20、2）执行中的进程提出I/O请求，等待I/O完成时，转进程调度；,2020/10/11,数学科学学院,43,3.3 进程调度,（3）在分时系统中，按照时间片轮转，分给进程的时间片用完时； （4）按照优先级调度、短作业优先调度时，有更高优先级进程变为就绪时或出现更短进程时（即出现进程抢占因素时）； （5）在进程通信中，执行中的进程执行了某种原语操作，如P操作、阻塞原语和唤醒原语时，都可能引起进程调度,2020/10/11,数学科学学院,44,D,C,B,A,CPU,完成,3.3 进程调度,调度算法 1. 先来先服务调度算法 ( FCFS ) 最简单的调度原则是先进先出就绪队列,2020/10/11

21、,数学科学学院,45,3.3 进程调度,根据进程到达就绪队列的时间来分配中央处理机，一旦一个进程获得了中央处理机，就一直运行到结束，先来先服务是非剥夺调度。 这种调度从形式上讲是公平的，但它使短进程要等待长进程的完成，重要的进程要等待不重要进程的完成。从这个意义上讲又是不公平的。 先进先出调度使响应时间的变化较小，因此它比其它大多数调度都可预测。由于这种调度方法不能保证良好的响应时间，在处理交互式用户时很少用这种方法。,2020/10/11,数学科学学院,46,3.3 进程调度,在现代系统中，先进先出很少作为单独的调度模式，而是常常嵌套在其它的调度模式中。 例如，许多调度模式根据优先级将处理机

22、分配给进程，但具有相同优先级的进程却按先进先出进行分配。 2 .短进程优先调度算法（同短作业优先） 此时进程就绪队列按照进程执行时间的长短排队。 可分为抢占式和非抢占式。,2020/10/11,数学科学学院,47,3 . 时间片轮转法（RR：Round Robin） 简单时间片轮转法 时间片轮转法主要用于进程调度。 就绪队列往往按进程到达的时间来排序。 进程调度程序按照先来先服务原则调度。 把系统的响应时间分成大小相等（或不等）的时间单位，称时间片。 每个进程被调度后，占用一个时间片，时间片用完后，该进程让出CPU给下一个就绪的进程。 若该进程还没有完成其运行，则返回到就绪队列的末尾重新排队等

23、待再次运行。即由运行状态转换成就绪状态。如此，多个进程循环轮转。,3.3 进程调度,2020/10/11,数学科学学院,48,时间片轮转法例,2020/10/11,数学科学学院,49,时间片轮转策略特别适合于分时系统。 在轮转法中，时间片长度的选取非常重要，它会直接影响系统开销和响应时间。 如果时间片长度过短，则调度程序剥夺处理机的次数增多，这将使进程上下文交换次数也大大增加，加重了系统开销； 如果时间片长度选择过长（大）。大到一个进程足以完成其全部运行工作所需的时间，那么时间片轮转法就退化为先来先服务策略了； 最佳时间片量值应能使分时用户得到好的响应时间。,3.3 进程调度,2020/10/

24、11,数学科学学院,50,3.3 进程调度,最佳的时间片值是多少呢？ 它将随系统而异，随负载而异，同时也随进程而异。 时间片的选取是实现各种调度算法的关键之处，而时间片的值的确定通常应考虑终端数目，处理机能力、各终端任务的急迫程度、外存传输速度等方面的因素。 时间片轮转法亦可应用于批处理系统的处理机调度。,2020/10/11,数学科学学院,51,3.3 进程调度,设时间片为q，进程数为N，则进程的响应时间T=Nq q的选择一般在100毫秒级 影响时间片大小的因素： 系统响应时间T： N一定，T与q成正比； 就绪队列中进程数目N： T一定，就绪队列中进程数越多，q值就越小； 进程切换t（转换时

25、间)：t/q应不大于某值，否则会影响T，从而影响q； 系统处理能力：程序处理时间、切换次数、响应时间 一般处理能力:必须保证用户键入的命令可在一个时间片内处理完毕。,2020/10/11,数学科学学院,52,F,C,B,A,.,CPU,完成,3.3 进程调度,几种情况的调度： 进程在时间片内执行完毕提前调度 进程在执行过程中提出I/O而阻塞重新调度 进程在一时间片内未完成将该进程放就绪队列末，重新调度,2020/10/11,数学科学学院,53,3.3 进程调度,系统按进程转换成就绪状态的时间的降序排队，调度程序每次调度，总是从队首移出一程的PCB，然后，将此进程投入运行（由就绪状态转换成运行状

26、态）。一个运行时间片到的进程从运行状态转换成就绪状态后，排在就绪队列的队尾。 评价： 优点是实现简单、系统开销小 缺点是不灵活，当系统中进程较少时，系统开销变大 由于该算法简单易于实现，且系统开销较小，早期的分时操作系统和目前一些应用系统中广泛采用了这种调度算法。,2020/10/11,数学科学学院,54,3.3 进程调度,对简单时间片轮转法的改进 将固定时间片改为可变时间片可变时间片轮转法 将单就绪队列改为多就绪队列，每个队列所赋予的时间片不同。,2020/10/11,数学科学学院,55,3.3 进程调度, 可变时间片轮转法（固定周期轮转法） 思想：时间片的大小是可变的，系统可根据系 统中当

27、前的进程数来确定时间片的大小 该算法从理论上克服了系统中进程数很少时系统开销大的缺点。 但修改时间片的大小，统计系统进程的数量也需要消耗系统时间。 需调整时间片大小的周期，太大，等于是固定时间片，太小，系统开销很大，得不尝失。,2020/10/11,数学科学学院,56,时间片 qT/N, T响应时间, N最大进程数 每当一轮调度开始时，系统便根据就绪队列中已有进程数目计算一次q值，作为新一轮调度的时间片。 这种方法得到的时间片是随就绪队列中的进程数变化的。 例：若T=2s，N=20 ，q=0.1s， q=T/N， 设执行一轮后N=10， 若固定T，则q=o.2s, 可减少系统开销,3.3 进程

28、调度,2020/10/11,数学科学学院,57,3.3 进程调度,4.优先级调度算法一种常用的进程调度算法是把处理机分配给具有最高优先级的进程（用于分时系统和实时系统） 确定进程的优先数：一种是静态优先数，另一种是动态优先数（适合于分时系统和实时系统）。 优先级调度算法可分为：抢占式（适合于分时系统和实时系统）和非抢占式（适合于批处理系统）,2020/10/11,数学科学学院,58,3.3 进程调度,优先队列： 可按优先级设置多个队列 在队列中若有相同优先级作业，按先来先服务原则排队； 调度从最高优先级队列开始，每个队列次序按到达的先后顺序排队。,2020/10/11,数学科学学院,59,20

29、20/10/11,数学科学学院,60,3.3 进程调度,优先数调度算法是目前操作系统广泛采用的一种进程调度算法 这种算法按照某种原则由系统（或用户、或系统与用户结合）赋予每个进程一个优先数 在处理机空闲时，进程调度程序就从就绪进程中选择一个优先数最大（或者最小）的进程占用CPU（该进程就从就绪状态转换成运行状态）。 采用这种调度算法的关键是如何确定进程的优先数、一个进程的优先数确定之后是固定的还是随着该进程运行的情况的变化而变化。,2020/10/11,数学科学学院,61,3.3 进程调度,1)静态优先数 静态优先数是在系统创建时确定的，一经确定之后在整个进程运行期间不再改变。通常与作业优先数

30、相同。 在有的系统中，分配给作业的优先数还取决于它所占用的内存的多少。作业越大，占用内存越多，分配给它的优先数越低。 显然，不论是根据作业的执行时间，还是根据作业的大小所确定的优先数，都有利于短作业。,2020/10/11,数学科学学院,62,3.3 进程调度,确定进程优先数方法： 系统确定：（运行时间、使用资源，进程的类型） 用户确定：（紧迫程度，计费等） 系统与用户结合（用户可以为本用户的进程设置优先数，但不是作调度用，系统还要根据系统情况把用户设置的进程优先数作为确定进程优先数的一个参数）,2020/10/11,数学科学学院,63,3.3 进程调度,静态优先数确定规则： 进程类型：用户进

31、程（包括：I/O繁忙和CPU繁忙、交互型和批处理型，前台进程和后台进程） 系统进程优先级高于用户进程（以便管理） I/O繁忙优先级高于CPU繁忙进程（以保证CPU、 I/O并行） 交互型优先级高于批处理型进程（以满足响应时间） 前台进程优先级高于后台进程（分时系统）,2020/10/11,数学科学学院,64,3.3 进程调度,进程对资源的需求：作业短、I/O多、占内存少可获高优先级 用户需求：根据用户提供的外部优先数（考虑任务的紧迫程度及费用）及作业到达的顺序确定,2020/10/11,数学科学学院,65,3.3 进程调度,2）动态优先数 虽然基于静态优先数的调度算法比较简单，易行，但毕竟不够

32、精确。 因为进程的优先数在它执行前就已算好，且在整个执行期间都保持不变，但随着进程的推进，计算优先数所依赖的特征很多都将随之改变，因此静态优先数并非自始至终都能准确地反映出这些特性 如果能在进程运行中，不断的随着特性的改变而修改其优先数，显然可以实现更多精确的调度，从而获得更好的调度性能，这对分时系统显得格外重要.,2020/10/11,数学科学学院,66,3.3 进程调度,动态进程优先数： 在运行的过程中，根据系统的设计目标，不断地调整进程的优先数。 在进程创建时，先赋一初值，随着进程运行过程特性的改变修改优先数。使其更为准确。 优点：能比较客观地反映进程的实际情况和保证达到系统设计目标。

33、如：对已占用较长时间CPU的进程，可降低其优先级；对等待CPU时间较长的进程，可升高其优先级,2020/10/11,数学科学学院,67,3.3 进程调度,例：设进程优先数越小，其优先级越高 进程 服务时间 优先数 到达时刻 A 32 5 0 B 4 3 0 C 8 5 0 D 2 5 0 E 16 4 16 非剥夺静态设置方式下运行情况： 时间： 14 36 52 60 62 执行顺序：B A E C D T=39.6 W=8.575,2020/10/11,数学科学学院,68,剥夺式动态设置方式下运行情况（设：每执行10ms，优先数+1；等待20ms，优先数-1） 初始执行时间：A32，B4，

34、C8，D2，E16,注：X*表示X完成，Xa表示X执行的剩余时间为a,2020/10/11,数学科学学院,69,5. 多级反馈队列调度算法 前面的算法多数需事先估计运行时间，较困难。 多级反馈队列调度算法综合了前面的算法，且不必估计运行时间。 它是一种可满足各类进程需求的较好的算法。 算法思想：按不同作业的性质和类型，将就绪队列分为若干子队列。各作业固定分属一个队列，不同队列可采用不同的调度算法。,3.3 进程调度,2020/10/11,数学科学学院,70,3.3 进程调度,调度算法的实施过程： 1 设置多级就绪队列； 2 各级就绪队列具有不同大小的时间片； 3 一个新进程在系统队列（最高优先

35、级）； 4 按队列优先级从高到低进行进程调度； 5 一进程进入较高优先级队列时可能要重 新调度。 调度算法的特点：性能较好，能照顾到各种用户利益,2020/10/11,数学科学学院,71,就绪队列1,至CPU,S1,就绪队列2,S2,至CPU,就绪队列3,S3,至CPU,就绪队列n,Sn,至CPU,时间片：s1s2s3sn,优先级高,低,2020/10/11,数学科学学院,72,3.3 进程调度,调度算法： 1 设置多级就绪队列；各队列赋予不同的优先级，第一个队列优先级最高； 2 各级就绪队列具有不同大小的时间片；优先级最高的队列，时间片最短； 3 各队列按FCFS排队； 4 一个新进程插入一

36、级队列； 5 按队列优先级从高到低进行进程调度；仅当上级队列空才调度下级队列进程； 6 若进程在给定时间片未运行完毕，则降至下一级就绪队列。 7 进程的执行具有抢占性。,2020/10/11,数学科学学院,73,3.3 进程调度,说明： I/O类进程及交互类进程优先。一般设在一级队列。该级队列时间片的设置因尽量使多数I/O型进程产生一个I/O。以减少系统开销； CPU型进程运行过程中要逐级下降； 因等待某事件进入阻塞队列而又被唤醒的进程，一般插入到原队列。,2020/10/11,数学科学学院,74,实时调度是为了完成实时处理任务而分配计算机处理器的调度方法。 实时处理任务要求计算机在用户允许的

37、时限范围内给出计算机的响应信号。 实时处理任务可分为 硬实时任务（hard real-time task） 软实时任务（soft real-time task）。 其中，前者要求计算机系统必须在用户给定的时限内完成，后者允许计算机系统在用户给定的时限左右处理完毕。,3.4 实时调度算法,2020/10/11,数学科学学院,75,3.4 实时调度算法,一、对实时系统的要求： 1 提供必要的调度信息，如就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级； 2 调度方式，广泛采用抢占调度方式，特别是 在实时要求严格的实时系统； 3 具有快速响应外部中断的能力； 4 很快的任务分派能力和

38、进程和线程切换速度； 5 系统应有很强的处理能力。,2020/10/11,数学科学学院,76,3.4 实时调度算法,二、对几种调度算法的评述： 1 时间片轮转调度算法：这是一种常用于分时系统的调度算法，它只能适用于一般实时信息处理系统，而不能用于实时要求严格的实时控制系统。可获得数秒至数十秒的响应时间； 2 非抢占的优先级调度算法：常用于多道批处理系统的调度算法，也可用于实时要求不太严格的实时控制系统。可获得数秒至数百毫秒级的响应时间； 3 基于时钟中断抢占的优先级调度算法：用于大多数的实时系统中。调度延迟可降低为几十毫秒至几毫秒； 4 立即抢占的优先级调度算法：这种算法适用于实时要求比较严格

39、的实时控制系统。调度延迟可降为几十微秒。,2020/10/11,数学科学学院,77,3.4 实时调度算法,三、代表性的实时调度算法： 1 时限式调度法(deadline scheduling)：是一种以满足用户要求时限为调度原则的算法。有周期性调度和非周期性调度。 时限包括：处理开始时限（开始截止时间）和处理结束时限（完成截止时间）两种，在实际中可以使用任一种时限。 2 频率单调调度(rate monotonic scheduling)：是一种被广泛用于多周期性实时处理的调度算法。其基本原理是频率越长（周期越长）的任务优先级越低。,2020/10/11,数学科学学院,78,四、实时调度算法实例

40、,1 最早截止时间优先：在事前能知道各实时任务的开始截止时间，且对调度时延要求不太严格的情况下，可以采用此非剥夺性调度策略,1,3,4,2,1,2,3,4,开始截止时间,执行任务,任务到达,t,系统首先调度任务1执行，在任务1执行期间，任务2、3 先后到达，由于任务3的截止时间早于任务2的，故系统在 任务1后将调度任务3执行。,1,3,4,2,2020/10/11,数学科学学院,79,3.4 实时调度算法,2 具有完成截止时间的周期性实时任务的调度 例：如果系统中有两个周期性的实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms 任务B要求每50ms执行一次，执行时间为25ms。任

41、务A和B每次的开始截止时间分别为A1、A2、A3和B1、B2、B3见图。 为了保证不遗漏任何一次截止时间，可采用最早截止时间优先的剥夺策略。,2020/10/11,80,具有完成截止时间的周期性实时任务调度,A1(10) A2(30) A3(50) A4(70) A5(90) A6(110) A7(130) A8,0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160,t,0 10 30 40 45 55 70 80 90 100 110 130 140,A1 A2 A3 A4 A5 A6 A7,B1(20) B1(5) B2(15)

42、B2(10) B3(20),B1(25) B2(75) B3(125),开始截止时间,完成 A1 A2 A3 A4 A5 A6 A7 A8 截止 时间,0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160,t,B1 B2 B3,调度顺序,2020/10/11,数学科学学院,81,什么是多处理机系统 多处理机操作系统的分类 多处理机系统调度策略,3.5 多处理机调度（自学）,2020/10/11,数学科学学院,82,多处理机系统：是一个具有两个或多个处理机并能相互进行通信以协同一个大的给定问题求解的计算机系统。 特点： 1） 有两个或多

43、个处理机 2） 共享主存或高速通信网络 3） 共享输入输出子系统 4） 有单一完整的操作系统 5） 各级硬件和软件相互作用,3.5.1.什么是多处理机系统,2020/10/11,数学科学学院,83,主要功能： 进程分配 更好的利用多机硬件 资源在处理机之间的分配 改善程序的响应时间 处理机的负载平衡 处理机间的协调和同步 因处理机故障引起的系统重组,3.5.1.什么是多处理机系统,2020/10/11,数学科学学院,84,广义上说，多处理机系统是：使用多处理机协调工作，来完成用户所要求任务的计算机系统。它包括了 并行处理系统（parallel processing system），例如数据流机

44、(dataflow machine)和细胞阵列处理机(Celluar array processors)等 在物理上分散且通过不同的物理传输媒体传输数据的计算机网络系统和计算机网络为基础的,对用户透明的分布式系统 在同一的计算机系统里共享内存的多处理机系统. 广义的多处理机计算机系统的一个共同的特点是有n个处理器(n1),能做到真正的并行处理,即能同时执行n条指令.,3.5.1.什么是多处理机系统,2020/10/11,数学科学学院,85,这里的多处理机操作系统是指：用来并行执行用户的几个程序，以提高系统的吞吐率；或并行操作以提高系统可靠性的多处理操作系统。这种系统由共享公共内存和外设的n(n

45、1)个 CPU组成。 概念上，在多处理机系统中的各进程的行为与在单机系统下的行为相同。 故对多处理机操作系统的要求与对多道程序的批处理系统没有太多的区别。 但多处理机环境下，进程可在各处理机间进行透明迁移，由于进程上下文切换等带来的系统开销将使得多处理机操作系统的复杂度大大增加。 由于多处理机系统并行地执行用户的几个程序（进程），这又带来了多处理机条件下的并发执行问题。,3.5.1.什么是多处理机系统,2020/10/11,数学科学学院,86,使用多处理机系统的主要原因是 提高系统的可靠性； 在发生故障时能降级使用； 提高系统吞吐 。 故一个多处理机操作系统除了提高资源分配和管理，进程和处理机

46、管理，内存和数据集保护以及文件系统等功能之外，还能提供系统结构重组的能力，以支持系统的降级使用。 多处理机的调度策略也必须考虑到降级使用和结构重组问题。,3.5.1.什么是多处理机系统,2020/10/11,数学科学学院,87,多处理器系统的类型,(1) 紧密耦合(Tightly Coupted)MPS。 通常是通过高速总线或高速交叉开关，来实现多个处理器之间的互连的。 它们共享主存储器系统和I/O设备，并要求将主存储器划分为若干个能独立访问的存储器模块，以便多个处理机能同时对主存进行访问。 系统中的所有资源和进程，都由操作系统实施统一的控制和管理。,3.5.2多处理机操作系统的分类,2020

47、/10/11,数学科学学院,88,(2) 松散耦合(Loosely Coupled)MPS。 通常是通过通道或通信线路，来实现多台计算机之间的互连。 每台计算机都有自己的存储器和I/O设备，并配置了OS来管理本地资源和在本地运行的进程。 故每一台计算机都能独立地工作， 必要时可通过通信线路与其它计算机交换信息，以及协调它们之间的工作。,3.5.2多处理机操作系统的分类,2020/10/11,数学科学学院,89,对称多处理器系统和非对称多处理器系统,(1) 对称多处理器系统SMPS(Symmetric MultiProcessor System) 在系统中所包含的各处理器单元，在功能和结构上都是

48、相同的，当前的绝大多数MPS都属于SMP系统。例如，IBM公司的SR/6000 Model F50, 便是利用4片Power PC处理器构成的。 (2) 非对称多处理器系统 在系统中有多种类型的处理单元，它们的功能和结构各不相同，其中只有一个主处理器，有多个从处理器。,3.5.2多处理机操作系统的分类,2020/10/11,数学科学学院,90,3.5.2多处理机操作系统的分类,多处理机操作系统可以分为三类： (1) 主从式（master-slave configuration） (2) 独立监控系统(Separate supervisor) (3) 移动式监控系统(floating super

49、visor),2020/10/11,数学科学学院,91,(1)主从式（master-slave configuration） 主从式中，指定一台特定的处理机为主处理机，由它负责对全系统的执行进行控制. 在主从式操作系统中，主处理器上执行操作系统程序，以控制其它从处理机的状态，并为从处理机分配任务。 DEC system 10 ,Cyber 170 以及多处理机UNIX系统MPX都是主从式结构.,3.5.2多处理机操作系统的分类,2020/10/11,数学科学学院,92,3.5.2多处理机操作系统的分类,在主从式操作系统中,如果从处理机需要主处理机提供服务时,它们采用硬件中断方式中断处理机上执行

50、的进程，以要求主处理机提供服务. 这种结构的操作系统一般重组功能较差,因为只有主处理机上执行操作系统程序.如果主处理机失败或发生不可恢复的错误时,整个系统将会瘫痪.,2020/10/11,数学科学学院,93,(2)独立监控系统(Separate supervisor) 独立监控系统的监控程序在每个处理机上执行, 每个处理机为自己的需要提供服务又互相通报执行情况. 一般来说,每个监控程序能重新装入或在不同的处理机上复制独立的副本. 独立监控系统不像主从结构那样易于崩溃,但其监控程序在各处理机中的副本会占去大量的内存.,3.5.2多处理机操作系统的分类,2020/10/11,数学科学学院,94,(

51、3)移动式监控系统(floating supervisor) 移动式监控系统：移动式监控系统把监控程序根据需要从一个处理机移到另一个处理机上.使所有资源有比较均衡的负载. 移动式监控系统的处理机调度以及服务请求冲突等,大都采用优先级的方式来解决. 所以 移动式监控系统是一种效率最高,实现最难的多处理操作系统.,3.5.2多处理机操作系统的分类,2020/10/11,数学科学学院,95,（1） 多处理机系统与单机调度的区别 多处理机调度与单机调度的主要区别涉及两个资源分配问题： 存放程序或数据的存储器分配及如何访问他们 在多机系统中，由于各进程在物理上也同时执行，而不是单机系统那样的交叉执行，这

52、些在物理上同时执行的进程可能同时访问物理存储器的同一地址。 处理机对同一存储块的访问必须是顺序的。各进程同时访问物理存储器上的同一地址是不允许的。,3.5.3 多处理机系统调度策略,2020/10/11,数学科学学院,96,3.5.3 多处理机系统调度策略,将等待执行的就绪进程分配到哪一个处理机上执行 在单机系统中，由于只有一个处理机，在调度程序中选取了某个就绪状态的进程之后，不须再选择处理机。 而在多机系统中，为了尽量做到让各处理机负荷平衡，可能会将处理机在进程之间进行多次切换。 如果被切换进程正在执行其临界区部分或系统中进程数目相当多，这种频繁的上下文转换将会使系统效率大大下降。,2020

53、/10/11,数学科学学院,97,3.5.3 多处理机系统调度策略,为解决进程对处理机的分配问题，有些多处理机系统中采用了局部就绪队列的方法限制进程的转移。 局部就绪对列：把处于就绪状态的进程分成不同的组，并使每一组进程和一个处理机对应起来。 这样，每个处理机只执行与其对应就绪队列中的进程。各个就绪队列中的进程不断发生横向转移。这种方法减少了调度程序的开销。但处理机的使用率却因此下降。 如：系统中某个局部就绪队列中因等待进程较多，使得对应的处理机十分繁忙，而另外的处理机则因就绪队列为空而处于空闲状态。,2020/10/11,数学科学学院,98,多处理机系统的调度目标是： 以最高的可靠性，使用最

54、少的处理机在最短的时间内完成最多的可以并行完成的进程。,3.5.3 多处理机系统调度策略,2020/10/11,数学科学学院,99,3.5.3 多处理机系统调度策略,（2）多处理机的调度评价 多处理机的调度有两种评价模型： 一种是确定性模型，另一种是随机性模性。 确定性模型：进程调度执行之前，估计出这些被调度进程所需要的执行时间，及这些进程之间的相互关系。 调度程序的目的：是根据给定的执行时间和相互关系，确定出一个最佳的执行顺序。 故确定性模型只用来确定给定进程的执行顺序，而随机性模性则常被用来研究动态调度技术。,2020/10/11,数学科学学院,100,3.5.3 多处理机系统调度策略,（

55、3）多处理机系统调度方式 （自学） 自调度方式 成组调度方式 专用处理机分配方式,2020/10/11,数学科学学院,101,对称多处理器系统中的进程分配方式 在SMP系统中，所有的处理器都是相同的，因而可把所有的处理器作为一个处理器池(Processor pool)，由调度程序或基于处理器的请求，将任何一个进程分配给池中的任何一个处理器去处理。在进行进程分配时，可采用以下两种方式之一。 1) 静态分配(Static Assigenment)方式 2) 动态分配(Dynamic Assgement)方式,3.5.3 多处理机系统调度策略,2020/10/11,数学科学学院,102,非对称MPS中的进程分配方式 对于非对称MPS，其OS大多采用主从(Master-Slave)式OS，即OS的核心部分驻留在一台主机上(Master)，从机(Slave)上只是用户程序，进程调度只由主机执行 每当从机空闲时，便向主机发送一索求进程的信号，然后等待主