操作系统第3章

《操作系统第3章》由会员分享，可在线阅读，更多相关《操作系统第3章（74页珍藏版）》请在金锄头文库上搜索。

1、第三章 处理机调度与死锁 1第三章第三章 处理机调度与死锁处理机调度与死锁 3.1 3.1 处理机调度的层次处理机调度的层次 3.23.2 调度队列的模型和调度准则调度队列的模型和调度准则3.33.3 调度算法调度算法 3.4 3.4 实时调度实时调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 第三章 处理机调度与死锁 2本章主要讨论处理机分配问题本章主要讨论处理机分配问题调度策略考虑：调度策略考虑：周转时间周转时间 吞吐率吞吐率响应时间响应时间 设备利用率设备利用率研究的内

2、容有：研究的内容有：作业与进程的关系作业与进程的关系 作业调度策略与算法作业调度策略与算法进程调度策略与算法进程调度策略与算法 第三章 处理机调度与死锁 3调度的类型调度的类型n1 按常用的方法（按调度的层次）分为：作业调按常用的方法（按调度的层次）分为：作业调度（高级调度）、中级调度、进程调度（低级调度（高级调度）、中级调度、进程调度（低级调度）。度）。n2 按操作系统的类型分：批处理调度、分时调度、按操作系统的类型分：批处理调度、分时调度、实时调度、多处理机调度。实时调度、多处理机调度。3.1处理机的调度层次第三章 处理机调度与死锁 41 1 分级调度分级调度1.1.作业的状态及其转换作业

3、的状态及其转换提提交交状状态态：一一个个作作业业在在其其处处于于输输入入设设备备进进入入外外部部存存储储设设备备的过程称为提交状态的过程称为提交状态后后备备状状态态（收收容容状状态态）：输输入入管管理理系系统统不不断断地地将将作作业业输输入入到到外外存存对对应应部部分分（或或称称输输入入井井），如如果果一一个个作作业业的的全全部部信信息息已已全全部部输输入入到到输输入入井井，在在它它还还没没有有被被调调度度去去执执行行前前，该该作业处于后备状态。作业处于后备状态。运运行行状状态态：作作业业一一旦旦被被作作业业调调度度程程序序选选中中而而被被送送入入主主存存中中投入运行。投入运行。完完成成状状态

4、态：作作业业运运行行完完毕毕，但但它它所所占占用用的的资资源源尚尚未未被被系系统统全部回收时，该作业处于完成状态全部回收时，该作业处于完成状态第三章 处理机调度与死锁 5 作业作业状态状态及其转换图及其转换图 spoolingspooling系统系统提交提交收容收容 外存外存就绪就绪等待等待运行运行就绪就绪等待等待交换调度交换调度完完成成作业调度作业调度进程调度进程调度内存输入管理输入管理系统（作系统（作业注册、业注册、作业建立作业建立程序）程序）第三章 处理机调度与死锁 62 2调度的层次调度的层次高级调度（作业调度、宏观调度）按一定原则对外存输入井上的作业进行调度，并建立进程PCB。它决定

5、允许哪些作业竞争系统资源。由于这种调度决定哪些作业可以进入系统，所以也称收容调度。作业一旦被系统收容，就变成进程或进程组。 l 所做的工作：1 选择作业； 2 分配资源；3 建立作业的进程； 4 建立有关的表格 5 作业的善后处理。第三章 处理机调度与死锁 7中级调度中级调度（交换调度）它决定允许哪些进程竞（交换调度）它决定允许哪些进程竞争处理机。中级调度通过使进程临时挂起和激活争处理机。中级调度通过使进程临时挂起和激活的方法对系统负载波动作出反映，以便获得平稳的方法对系统负载波动作出反映，以便获得平稳的系统操作和实现较好的系统综合性能目标，中的系统操作和实现较好的系统综合性能目标，中级调度的

6、作用使进入系统的作业和已分配中央处级调度的作用使进入系统的作业和已分配中央处理机的作业二者之间的一个缓冲理机的作业二者之间的一个缓冲。引入中级调度的目的是为了提高内存的利用引入中级调度的目的是为了提高内存的利用率和系统吞吐量率和系统吞吐量第三章 处理机调度与死锁 8低低级级调调度度（进进程程调调度度）它它决决定定了了存存在在就就绪绪进进程程时时，哪哪一一个个就就绪绪进进程程将将分分配配到到中中央央处处理理机机，并并且且把把中中央央处处理理机机实实际际分分配配给给这这个个进进程程（即即低低级级调调度度是是将将处处理理机机分分配配给给进进程）。程）。 低低级级调调度度是是由由每每秒秒可可操操作作许

7、许多多次次的的处处理理机机调调度度程程序序执执行，行，处理机调度程序应常驻内存。处理机调度程序应常驻内存。进程调度的方式：非抢占方式，抢占方式。进程调度的方式：非抢占方式，抢占方式。抢占的方式有：抢占的方式有：1 时间片原则；时间片原则；2 优先级原则；优先级原则； 3 短进程优先原则短进程优先原则第三章 处理机调度与死锁 9 作业是用户向计算机提交任务的任务实体。 进程是计算机为了完成用户任务实体而设置的执行实体。 显然，计算机要完成一个任务实体，必须要有一个以上的执行实体，一个作业总是由一个以上的多个进程组成。 作业步、作业流3 3作业与进程的关系作业与进程的关系第三章 处理机调度与死锁

8、10作业调度的功能：按某种算法从后备队列中挑选一个或一批作业调入内存，并创建PCB.1后备作业队列与作业控制块 系统中有若干作业在输入井中，为了管理和调度作业，就必须记录已进入系统的各作业的情况，系统为每个作业设置了一个作业控制块（JCB）。内容：作业名、作业状态、作业调度，以及资源申请和一些控制信息。作业的调度作业的调度第三章 处理机调度与死锁 11 作业控制块JCB 作业名作业名 作业类型作业类型 资源要求资源要求 资源使用情况资源使用情况 调度信息（如调度信息（如优先级等）优先级等） 当前状态当前状态 其它其它作业控制块作业控制块JCBI/O为主或CPU为主内、外存量，预计运行时间，要求

9、I/O设备类型和数量外设类型与数量作业建立时间、进入系统时间、开始/完成时间、作业说明书文件等第三章 处理机调度与死锁 12 作业调度按照某种调度算法从后备作业队列中选取作业，使其进入内存运行。 作业调度程序的主要功能是审查系统是否能满足用户作业的资源要求以及按照一定的算法选取作业。包括：1)决定接纳多少个作业2)决定接纳哪些作业 2作业调度及其功能第三章 处理机调度与死锁 13按照某种调度算法从后备作业队列中选取作业。按照某种调度算法从后备作业队列中选取作业。为为被被选选取取的的作作业业分分配配内内存存和和外外设设资资源源（当当系系统统为为动动态态分分配配外外设设时时，作作业业所所申申请请的

10、的外外设设只只作作为为调调度度的的参参考考因因素素）。因因此此要用到内存分配程序和外设分配程序。要用到内存分配程序和外设分配程序。为选中的作业建立相应的进程。为选中的作业建立相应的进程。为为作作业业开开始始运运行行做做好好一一切切准准备备工工作作。如如构构造造和和读读写写作作业业运运行行时时所所需需要要的的有有关关表表格格及及建建立立负负责责其其运运行行控控制制的的作作业业运运行行控控制程序。制程序。在在作作业业运运行行完完毕毕或或运运行行过过程程中中因因某某种种原原因因需需要要撤撤离离时时，作作业业调调度度程程序序还还要要完完成成作作业业的的善善后后处处理理工工作作，如如收收回回分分配配给给

11、他他的全部资源，输出信息，撤销的全部资源，输出信息，撤销PCBPCB和作业控制块和作业控制块JCBJCB。作业调度应完成如下几方面的工作作业调度应完成如下几方面的工作第三章 处理机调度与死锁 14作业调度的转换过程作业调度的转换过程 （1 1）作业从后备状态到执行状态）作业从后备状态到执行状态 （2 2）作业从执行状态到完成状态）作业从执行状态到完成状态第三章 处理机调度与死锁 15后备作业队列空后备作业队列空按调度算法从作按调度算法从作业中选出一作业业中选出一作业调用存储、设备管理调用存储、设备管理程序，审核资源要求程序，审核资源要求资源要求能满足？资源要求能满足？放弃该放弃该作业作业否分配

12、资源分配资源调用进程管理调用进程管理程序建立进程程序建立进程进程调度进程调度否是出口作业从后备状态到执行状态第三章 处理机调度与死锁 16撤销该作业的所有进程及作业的撤销该作业的所有进程及作业的JCB调用存储管理，设备管理回收调用存储管理，设备管理回收分配给该作业的全部资源分配给该作业的全部资源调用会计程序，计算该作业的执行费用调用会计程序，计算该作业的执行费用调度下一个作业调度下一个作业作业从执行状态到完成状态第三章 处理机调度与死锁 171)调度目标 对所有作业应该是公平合理 应使设备有高的利用率 每天执行尽可能多的作业 有快的响应时间3.3.作业调度目标与性能衡量作业调度目标与性能衡量第

13、三章 处理机调度与死锁 182）.衡量一个作业调度算法是否满足系统设计的要求 给出两个常用的评价在批处理系统中对作业调度算法优劣的性能量度周转时间：作业i从提交时刻tsi到完成时刻tei称为作业的周转时间。Ti=Tei-Tsi 完成 提交第三章 处理机调度与死锁 19作业平均周转时间为（有n个作业，n=1) nT=1/n Ti i=1一个作业的周转时间说明了该作业在系统内停留的时间包含两部分：一是等待时间；二为执行时间Ti = Twi + Tri(停留时间)第三章 处理机调度与死锁 20带权周转时间Wi：周转时间和执行时间之比Wi=Ti/Tri平均带权周转时间为： nW=1/n Wi i=1第

14、三章 处理机调度与死锁 21进程调度进程调度的功能进程调度的功能 1 记录系统中所有进程的执行情况记录系统中所有进程的执行情况 2 选择占有处理机的进程选择占有处理机的进程 3 进行进程上下文的切换进行进程上下文的切换进程调度的时机进程调度的时机进程上下文切换进程上下文切换第三章 处理机调度与死锁 223.2 3.2 调度队列模型和调度准则调度队列模型和调度准则仅有仅有进程调度的调度队列模型进程调度的调度队列模型1执行时的三种情况：执行时的三种情况：（1）进程完成；）进程完成； （2）时间片完；）时间片完； （3）阻塞）阻塞3.2.1 3.2.1 调度队列模型调度队列模型第三章 处理机调度与死

15、锁 23具有作业和进程调度的调度队列模型具有作业和进程调度的调度队列模型2第三章 处理机调度与死锁 24模型2和模型1比较模型模型2在在os中不仅有进程调度，还有作业调度；中不仅有进程调度，还有作业调度；模型模型2设置若干个阻塞队列；设置若干个阻塞队列；模型模型2中各个队列（就绪队列、后备作业队列、中各个队列（就绪队列、后备作业队列、多个阻塞队列）可按不同的规则排列；模型多个阻塞队列）可按不同的规则排列；模型1中中的队列（就绪队列、阻塞队列）按的队列（就绪队列、阻塞队列）按FCFS的规则的规则排列；排列；模型模型2中的进程是非交互的，模型中的进程是非交互的，模型1是交互的。是交互的。第三章 处

16、理机调度与死锁 25具有作业、进程和中级调度的调度队列模型具有作业、进程和中级调度的调度队列模型3第三章 处理机调度与死锁 26模型3和模型2、模型1比较用户进程类型数不同用户进程类型数不同批处理作业对应的进程批处理作业对应的进程交互型进程（优先级高）交互型进程（优先级高）进程控制原语数不同进程控制原语数不同创建原语、撤销原语、阻塞原语和唤醒原语、创建原语、撤销原语、阻塞原语和唤醒原语、挂起原语和激活原语挂起原语和激活原语进程队列数不同进程队列数不同在内、外存的就绪队列和阻塞队列在内、外存的就绪队列和阻塞队列第三章 处理机调度与死锁 273.2.2 3.2.2 选择调度方式和调度算法的若干准则

17、选择调度方式和调度算法的若干准则调度算法选择时考虑的因素调度算法选择时考虑的因素系统设计目标系统设计目标批处理追求系统吞吐量；实时关心可靠和实时；分批处理追求系统吞吐量；实时关心可靠和实时；分时注重交互和及时响应时注重交互和及时响应均衡处理系统和用户的要求均衡处理系统和用户的要求系统资源利用率系统资源利用率I/O型和计算型作业搭配型和计算型作业搭配优先级优先级实时系统实时系统第三章 处理机调度与死锁 28选择调度方式和算法的若干准则选择调度方式和算法的若干准则面向用户的准则：周转时间短；响应时间快；截止时间的保证；优先权准则。面向系统的准则：系统的吞吐量高；处理机利用率好；各类资源的平衡利用；

18、对所有作业公平合理。第三章 处理机调度与死锁 29（1）周转时间）周转时间（2）响应时间）响应时间v定义：用户通过键盘提交一个请求开始，直到在屏幕定义：用户通过键盘提交一个请求开始，直到在屏幕上显示出结果为止的一段时间间隔。上显示出结果为止的一段时间间隔。v包括：把请求信号从键盘输入的时间；计算机对请求包括：把请求信号从键盘输入的时间；计算机对请求进行处理的时间；将响应信息回送终端显示的时间。进行处理的时间；将响应信息回送终端显示的时间。（3）截止时间）截止时间v定义：某任务必须开始执行的最迟时间，或必须完成定义：某任务必须开始执行的最迟时间，或必须完成的最迟时间。的最迟时间。（4）优先权）优

19、先权采用采用 抢占式调度方式抢占式调度方式第三章 处理机调度与死锁 30（1）先来先服务（FCFS）调度算法 将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。它优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短。3.3 3.3 调度算法调度算法第三章 处理机调度与死锁 31在单道在单道环境下，某批处理显然有四道作业，已知他们的进环境下，某批处理显然有四道作业，已知他们的进入系统的时刻、估计运算时间如下：入系统的时刻、估计运算时间如下：作业进入时刻(h)运行时间(h)12348.008.509.009.502.

20、000.500.100.20用用FCFS算法计算作业的运行情况、平均周转时间和平算法计算作业的运行情况、平均周转时间和平均带权周转时间均带权周转时间第三章 处理机调度与死锁 32作业进入时刻运行时间开始时刻 完成时刻周转时间 带权周转12348.008.509.009.502.000.500.100.208.0010.0010.5010.6010.0010.5010.6010.802.002.001.601.301.004.0016.006.50平均周转时间T1.725（h）平均带权周转时间T6.875第三章 处理机调度与死锁 33FCFS算法调度例2作业名 进入时间 运行时间（分） 需内存量

21、KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20 有用户空间有用户空间100KB，并规定作业相应程序装入内并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用存连续区域，并不能被移动，作业与进程均采用FCFS算法算法第三章 处理机调度与死锁 34有用户空间有用户空间100KB，并规定作业相应程序装入内存连续区域，并不能被移并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用动，作业与进程均采用FCFS算法算法作业名 进入时间 运行时间（分） 需内存量KB A 8:06 42 15

22、B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20100K15K60K10K15K9:189:18第三章 处理机调度与死锁 35优缺点优点：实现容易，具有一定公平性；优点：实现容易，具有一定公平性；缺点：不利于短作业（短进程），有利于缺点：不利于短作业（短进程），有利于长作业（长进程）长作业（长进程）第三章 处理机调度与死锁 36作业到达时间运行时间开始时刻 完成时刻周转时间 带权周转ABCD01231100110001101102110110220211001001991.001.001001.99例如，P92第三章 处理机调度与死锁 37

23、（2）.最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业运行顺序 1 3 4 2作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2.00 1.00 3 9.00 0.10 10.00 10.10 1.10 11.00 4 9.50 0.20 10.10 10.30 0.80 4.00 2 8.50 0.50 10.30 10.80 2.30 4.60 平均周转时间平均周转时间 T1.55h平均带权周转时间平均带权周转时间T5.15第三章 处理机调度与死锁 38SF

24、算法例2作业名 进入时间 运行时间（分） 需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20 有用户空间有用户空间100KB，并规定作业相应程序装入内存并规定作业相应程序装入内存连续区域，并不能被移动，作业按连续区域，并不能被移动，作业按SF算法，进程采算法，进程采用用FCFS算法算法.第三章 处理机调度与死锁 39作业名 进入时间 运行时间（分） 需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20第三章 处理机

25、调度与死锁 40优缺点优点：改善平均周转时间或评价带权周转优点：改善平均周转时间或评价带权周转时间。调度性能好。时间。调度性能好。缺点：缺点：对长作业不利；对长作业不利；紧迫作业、进程不能及时处理；紧迫作业、进程不能及时处理；执行时间可能有虚假执行时间可能有虚假第三章 处理机调度与死锁 41最高响应比作业优先算法是对FCFS方式和SJF方式的一种综合平衡响应比R定义为系统对作业的响应时间与作业要求运行时间的比值R响应时间 / 要求运行时间(作业等待时间需运行时间)/ 需运行时间1已等待时间 / 需运行时间1W/T(3)最高响应比作业优先算法（HRN）第三章 处理机调度与死锁 42 响应比R不仅

26、是要求运行时间的函数，而且还是等待时间的函数。 由于R与要求运行时间成反比，故对短作业是有利的，另一方面，因R与等待时间成正比，故长作业随着其等待时间的增长，也可获得较高的相应比。这就克服了短作业优先数法的缺点，既照顾了先来者，又优待了短作业，是上述两种算法的一种较好的折中。第三章 处理机调度与死锁 43最高响应比作业优先算法（HRN）示例：作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.10 10.60 2.10 4.20 3

27、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.67510.00时刻：R2=1.5/0.5=3; R3=1/0.1=10; R3=0.5/0.2=2.5; 10.10时刻：R2=1.6/0.5=3.2; R3=0.6/0.2=3;第三章 处理机调度与死锁 44(4) 优先级调度算法优先级调度算法方式：方式：v非抢占式优先级算法非抢占式优先级算法 在这种方式下，系统一旦把处理机分配给就绪队列中优在这种方式下，系统一旦把处理机分配给就绪队列中优先

28、权最高的进程后，该进程便一直执行下去，直至完成；先权最高的进程后，该进程便一直执行下去，直至完成； 或因发生某事件使该进程放弃处理机时，系统方可再将或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。处理机重新分配给另一优先权最高的进程。v抢占式优先级调度算法抢占式优先级调度算法 在执行期间，只要又出现了另一个其优先权更高的进程，在执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程进程调度程序就立即停止当前进程(原优先权最高的进原优先权最高的进程程)的执行，重新将处理机分配给新到的优先权最高的的执行，重新将处理机分配给新到的优先权最

29、高的进程。进程。第三章 处理机调度与死锁 45优先级类型v类型：静态优先级，动态优先级类型：静态优先级，动态优先级1)1)静态优先级静态优先级静静态态优优先先级级是是在在系系统统创创建建时时确确定定的的，一一经经确确定定之后在整个进程运行期间不再改变。之后在整个进程运行期间不再改变。优先数的表示：一般用某一范围的整数表示。优先数的表示：一般用某一范围的整数表示。第三章 处理机调度与死锁 46优先级的确定原则优先级的确定原则进程类型；进程类型；v接收进程、对换进程、磁盘接收进程、对换进程、磁盘I/O进程优先级进程优先级高于一般的用户进程；交互型用户进程高于高于一般的用户进程；交互型用户进程高于批

30、处理型作业对应的进程；批处理型作业对应的进程；进程对资源的需求；进程对资源的需求；v进程估计时间和内存需求量少的进程进程估计时间和内存需求量少的进程根据用户的要求；根据用户的要求；v根据用户作业的紧迫程度根据用户作业的紧迫程度第三章 处理机调度与死锁 472).2).动态优先级调度算法动态优先级调度算法虽然基于静态优先数的调度算法比较简单，系统虽然基于静态优先数的调度算法比较简单，系统开销小开销小，但毕竟不够精确、灵活。因为进程的优但毕竟不够精确、灵活。因为进程的优先数在它执行前就已算好，且在整个执行期间都先数在它执行前就已算好，且在整个执行期间都保持不变，但随着进程的推进，计算优先数所依保持

31、不变，但随着进程的推进，计算优先数所依赖的特征很多都将随之改变，赖的特征很多都将随之改变，因此静态优先数并因此静态优先数并非自始至终都能准确地反映出这些特性非自始至终都能准确地反映出这些特性。如果能在进程运行中，不断的随着特性的改变而如果能在进程运行中，不断的随着特性的改变而修改其优先数，显然可以实现更多精确的调度，修改其优先数，显然可以实现更多精确的调度，从而获得更好的调度性能，这就是从而获得更好的调度性能，这就是动态优先级动态优先级。如如 等待时间的增长，其优先级提高，每隔等待时间的增长，其优先级提高，每隔1010分钟分钟优先级加优先级加1 1第三章 处理机调度与死锁 48优先级算法调度例

32、子作业名 进入时间 运行时间（分） 优先级(数大优先级高) A 8:00 60 1 B 8:30 50 2 C 8:40 30 4 D 8:50 10 3平均周转时间 T70分平均带权周转时间T2.525第三章 处理机调度与死锁 49 时间片轮转法主要用于进程调度。采用此算法的系统，其程序就绪队列往往按进程到达的时间来排序。进程调度程序总是选择就绪队列中的第一个进程，也就是说按照先来先服务原则调度，但一旦进程占用处理机则仅使用一个时间片。在使用完一个时间片后，进程还没有完成其运行，它必须释放出处理机给下一个就绪的进程，而被抢占的进程返回到就绪队列的末尾重新排队等待再次运行。 (5) (5) 轮

33、转法（轮转法（RRRR）第三章 处理机调度与死锁 50 时间片轮转策略特别适合于分时系统中使用，当多个进程驻留在主存中时，在进程间转接处理机的开销一般是不大的。FCB A .CPU完成完成第三章 处理机调度与死锁 51 在轮转法中，时间片长度的选取非常重要，时间片长度的选择会直接影响系统开销和响应时间。当时间片很大时，每个进程得到比完成该进程多的处理机时间，此时轮转调度模式退化为先进先出模式。当时间片非常小时，上下文转换开销就成了决定因素，系统性能降低，大多数时间都消耗在处理机的转换上，只有少许用在用户的计算上。最佳的时间片量值应能使分时用户得到好的响应时间第三章 处理机调度与死锁 52时间片

34、大小的选择时间片大小的选择系统对响应时间的要求系统对响应时间的要求时间片与响应时间正比时间片与响应时间正比 SRt/Nmax Rt响应时间 Nmax最大进程数 S 时间片 第三章 处理机调度与死锁 53n 就绪队列中进程的数目就绪队列中进程的数目n时间片与终端数目反比 每当一轮调度开始时，系统便根据就绪队列中已有进程数目计算一次值。作为新一轮调度的时间片。这种方法得到的时间片是随就绪队列中的进程数变化的。n 系统的处理能力系统的处理能力第三章 处理机调度与死锁 54调度算法的考虑方面调度算法的考虑方面(1)为提高系统吞吐量和降低作业的平均周转时间为提高系统吞吐量和降低作业的平均周转时间而照顾短

35、作业；而照顾短作业；(2)为了得到较好的输入为了得到较好的输入/输出设备的利用率和对交输出设备的利用率和对交互用户的及时响应，而照顾互用户的及时响应，而照顾I/O型作业；型作业；(3)在作业运行过程中，按作业运行情况动态考虑在作业运行过程中，按作业运行情况动态考虑作业的性质是输入作业的性质是输入/输出型作业，还是计算型作输出型作业，还是计算型作业，并确定作业当时的运行性质作相应的调度。业，并确定作业当时的运行性质作相应的调度。(6) (6) 多级反馈队列调度算法多级反馈队列调度算法第三章 处理机调度与死锁 55第三章 处理机调度与死锁 56调度算法的实施过程调度算法的实施过程1 设置多级就绪队

36、列，每个队列对应一个调度级别设置多级就绪队列，每个队列对应一个调度级别（递减（递减）；）；2 各级就绪队列具有不同大小的时间片；各级就绪队列具有不同大小的时间片；随队列级数的增加其进程优先级降低，但时间片增大。随队列级数的增加其进程优先级降低，但时间片增大。3 一个新进程在系统队列中的排队规则；一个新进程在系统队列中的排队规则；4 按队列优先级高到低进行进程调度；按队列优先级高到低进行进程调度；5 一进程进入较高优先级队列时可能要重新调度。一进程进入较高优先级队列时可能要重新调度。第三章 处理机调度与死锁 57调度算法的性能调度算法的性能具有较好的性能，能照顾到各种用户利益。具有较好的性能，能

37、照顾到各种用户利益。能照顾到终端型作业用户的要求能照顾到终端型作业用户的要求能照顾到短型作业能照顾到短型作业能照顾到长批处理型作业用户的要求能照顾到长批处理型作业用户的要求第三章 处理机调度与死锁 583.4 实时调度实时调度实时调度是为了完成实时处理任务而分配计算机是为了完成实时处理任务而分配计算机处理器的调度方法。实时处理任务要求计算机在处理器的调度方法。实时处理任务要求计算机在用户允许的时限范围内给出计算机的响应信号。用户允许的时限范围内给出计算机的响应信号。实时处理任务可分为实时处理任务可分为 硬实时任务（硬实时任务（hard real-time task） 软实时任务（软实时任务（s

38、oft real-time task）。）。 其中，前者要求计算机系统必须在用户给定的其中，前者要求计算机系统必须在用户给定的时限内完成，后者允许计算机系统在用户给定的时限内完成，后者允许计算机系统在用户给定的时限左右处理完毕。时限左右处理完毕。第三章 处理机调度与死锁 59对实时系统的要求对实时系统的要求1 提供必要的调度信息，如就绪时间、开始截止提供必要的调度信息，如就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、时间和完成截止时间、处理时间、资源要求、优先级；优先级；2 调度方式，广泛采用抢占调度方式，特别是在调度方式，广泛采用抢占调度方式，特别是在实时要求严格的实时系统；实时

39、要求严格的实时系统；3 系统处理能力强；系统处理能力强；4 很快的进程和线程切换速度。很快的进程和线程切换速度。具有快速响应外部中断的能力具有快速响应外部中断的能力快速的任务分派能力快速的任务分派能力第三章 处理机调度与死锁 60对几种调度算法的评述：对几种调度算法的评述：1 非非抢抢占占式式轮轮转转调调度度算算法法：这这是是一一种种常常用用于于分分时时系系统统的的调调度度算算法法，它它只只能能适适用用于于一一般般实实时时信信息息处处理理系系统统，而而不不能能用用于于实实时时要要求求严严格格的的实实时时控控制制系系统。统。2 非非抢抢占占的的优优先先级级调调度度算算法法：常常用用于于多多道道批

40、批处处理理系系统统的的调调度度算算法法，也也可可用用于于实实时时要要求求不不太太严严格格的的实时控制系统。实时控制系统。3 基基于于时时钟钟中中断断抢抢占占的的优优先先级级调调度度算算法法：用用于于大大多数的实时系统中。多数的实时系统中。 4 立立即即抢抢占占的的优优先先级级调调度度算算法法：这这种种算算法法适适用用于于实时要求比较严格的实时控制系统。实时要求比较严格的实时控制系统。第三章 处理机调度与死锁 61第三章 处理机调度与死锁 62代表性的实时调度算法：代表性的实时调度算法：1 时限式调度法时限式调度法(deadline scheduling)： 是是一一种种以以满满足足用用户户要要

41、求求时时限限为为调调度度原原则则的的算算法法。有有周周期期性性调调度度和和非非周周期期性性调调度度。时时限限有有：处处理理开开始始时时限限（开开始始截截止止时时间间）和和处处理理结结束束时时限限（完完成成截止时间）两种，在实际中可以使用任一种时限。截止时间）两种，在实际中可以使用任一种时限。2 最最低低松松弛弛度度优优先先LLF(Least Laxity First)：根根据据任任务务紧紧急急( (或或松松弛弛) )的的程程度度，来来确确定定任任务务的的优优先先级级。任任务务的的紧紧急急程程度度愈愈高高，为为该该任任务务所所赋赋予予的的优先级就愈高，以使之优先执行。优先级就愈高，以使之优先执行

42、。第三章 处理机调度与死锁 63实时调度实例实时调度实例 在事前能知道各实时任务的开始截止时间，且对调度时延要求在事前能知道各实时任务的开始截止时间，且对调度时延要求不太严格的情况下可以采用最早截止时间优先的非剥夺性调度策略不太严格的情况下可以采用最早截止时间优先的非剥夺性调度策略134212 34开始截止时间执行任务任务到达t系统首先调度任务系统首先调度任务1执行，在任务执行，在任务1执行期间，任务执行期间，任务2、3先后到达，由于任务先后到达，由于任务3的截止时间早于任务的截止时间早于任务2的，故系统在的，故系统在任务任务1后将调度任务后将调度任务3执行。执行。1342第三章 处理机调度与

43、死锁 64LLF调度调度例：如果系统中有两个周期性的实时任务例：如果系统中有两个周期性的实时任务A和和B，任务任务A要求每要求每20ms执行一次，执行时执行一次，执行时间为间为10ms；任务任务B要求每要求每50ms执行一次，执行一次，执行时间为执行时间为25ms。任务任务A和和B每次的开始截每次的开始截止时间分别为止时间分别为A1、A2、A3和和B1、B2、B3见图。见图。松弛度松弛度= = 必须完成时间必须完成时间- -其本身的运行时间其本身的运行时间- -当前时间当前时间第三章 处理机调度与死锁 65 A1(20) A2(40) A3(60) A4(80) A5(100) A6(120)

44、 A7(140) A8(160) 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 t0 10 30 40 45 55 70 80 90 100 110 130 140A1 A2 A3 A4 A5 A6 A7 B1(20) B1(5) B2(15) B2(10) B3(20)B1(50) B2(100) B3(150)利用利用LLF进行调度的情况进行调度的情况松弛度= 必须完成时间-其本身的运行时间-当前时间第三章 处理机调度与死锁 66习题1有3道程序构成如下，它们在同一个系统中运行，该系统有输入/输出设备各一台。 A进程：输入

45、32s，计算8s，输出5s；B进程：输入21s，计算14s，输出35s；C进程：输入12s，计算32s，输出15s；问：（1）3道程序顺序执行时最短需要多少时间？（2）若三道并发执行，最短需要多少时间？（不计系统开销）第三章 处理机调度与死锁 67（1）顺序执行：各道程序执行时间之和。T=32+8+5+21+14+35+12+32+15=174s并发执行：考虑输入、计算、输出尽量并行操作。T=21+14+35+15+5=90s第三章 处理机调度与死锁 68习题2假定多道批处理系统，当第1个作业进入输入井后或内存中有一道程序完成后立即进行作业调度。有4道作业，其进入时间、需要计算时间及优先级如下

46、表。分别用FCFS、SF、优先级调度算法求T、W值。作业名进入时间 计算时间优先级（数大级高）A8:00601B8:10402C8:20304D8:30103第三章 处理机调度与死锁 69FCFS作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 A 8:00 60 8:00 9:00 60 60/60 B 8:10 40 9:00 9:40 90 90/40 C 8:20 30 9:40 10:10 110 110/30 D 8:30 10 10:10 10:20 110 110/10 平均周转时间平均周转时间T=(60+90

47、+110+110)/4=92.5分分 带权周转时间带权周转时间 W=(1+2.25+11/3+11)/4=4.48 执行顺序：执行顺序：A、B、C、D第三章 处理机调度与死锁 70SJF作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 A 8:00 60 8:00 9:00 60 60/60 B 8:10 40 9:40 10:20 130 130/40 C 8:20 30 9:10 9:40 80 80/30 D 8:30 10 9:00 9:10 40 40/10 平均周转时间平均周转时间T=(60+130+80+40)/

48、4=77.5分分 带权周转时间带权周转时间 W=(1+3.25+8/3+4)/4=2.73 执行顺序：执行顺序：A、D、C、B第三章 处理机调度与死锁 71优先级调度作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 A 8:00 60 8:00 9:00 60 60/60 B 8:10 40 9:40 10:20 130 130/40 C 8:20 30 9:00 9:30 70 70/30 D 8:30 10 9:30 9:40 70 70/10 平均周转时间平均周转时间T=(60+130+70+70)/4=82.5分分 带

49、权周转时间带权周转时间 W=(1+3.25+7/3+7)/4=3.40 执行顺序：执行顺序：A、C、D、BA, B, C, D优先数分别是:1、2、4、3 （数大级高）第三章 处理机调度与死锁 72习题3有有5个个批处理的作业（批处理的作业（A、B、C、D、E）几乎同时）几乎同时到达一个计算中心，估计的运行时间分别为到达一个计算中心，估计的运行时间分别为2，4，6，8，10分钟，它们的优先数分别为分钟，它们的优先数分别为1、2、3、4、5（1为最低优先级）。对下面的每种调度算法，为最低优先级）。对下面的每种调度算法，分别计算作业的平均周转时间。分别计算作业的平均周转时间。（1）最高优先级优先；

50、）最高优先级优先；（2）时间片轮转（时间片为）时间片轮转（时间片为2分钟）；分钟）；（3）FIFO（作业到达顺序为作业到达顺序为C,D,B,E,A）；）；（4）短作业优先。短作业优先。第三章 处理机调度与死锁 73（1）调度顺序）调度顺序E,D,C,B,A，平均周转时间平均周转时间=(10+18+24+28+30)/5=110/5=22分钟分钟（2）平均周转时间平均周转时间=(2+12+20+26+30)/5=90/5=18分分钟钟（3）调度顺序调度顺序C,D,B,E,A ，平均周转时间平均周转时间=(6+14+18+28+30)/5=96/5=19.2分钟分钟（4）调度顺序调度顺序 A, B

51、, C, D, E ，平均周转时间平均周转时间=(2+6+12+20+30)/5=70/5=14分钟分钟第三章 处理机调度与死锁 74作 业在一个多道程序设计系统中，不采用移动技术的可在一个多道程序设计系统中，不采用移动技术的可变分区分配方式管理主存。设用户空间为变分区分配方式管理主存。设用户空间为100M，现有现有4道作业，其进入时间、需要计算时间及道作业，其进入时间、需要计算时间及主存的需求存量如下表。分别用主存的需求存量如下表。分别用FCFS、SF调度调度算法求算法求T、W值。值。作业名进入输入井时间需计算时间主存需求存量JOB18.0时1小时20KJOB28.2时0.6时60KJOB38.4时0.5时25kJOB48.6时0.4时20k