昆明理工大学 《操作系统》第三章处理机调度

《昆明理工大学 《操作系统》第三章处理机调度》由会员分享，可在线阅读，更多相关《昆明理工大学 《操作系统》第三章处理机调度（57页珍藏版）》请在金锄头文库上搜索。

1、福州大学数计学院福州大学数计学院主讲教师主讲教师: : 单单 红红计算机操作系统计算机操作系统第三章处理机调度第三章处理机调度调度策略考虑：调度策略考虑：周转时间周转时间 吞吐率吞吐率相应时间相应时间 设备利用率设备利用率研究的内容有：研究的内容有：作业与进程的关系作业与进程的关系 作业调度策略与算法作业调度策略与算法进程调度策略与算法进程调度策略与算法 几种调度策略的评价几种调度策略的评价 本章主要讨论处理机分配问题本章主要讨论处理机分配问题1.1.作业的状态及其转换作业的状态及其转换提提交交状状态态：一一个个作作业业北北提提交交给给机机房房后后或或用用户户通通过过终终端端键键盘想计算机键入

2、其作业时所处的状态盘想计算机键入其作业时所处的状态后后备备状状态态：作作业业的的全全部部信信息息都都已已通通过过输输入入机机输输入入，并并由由操操作作系系统统将将其其存存在在磁磁盘盘的的某某些些分分区区（存存放放作作业业的的输输入入井井）中等待运行。中等待运行。运运行行状状态态：作作业业一一旦旦被被作作用用调调度度程程序序选选中中而而被被送送入入主主存存中投入运行。中投入运行。完完成成状状态态：作作业业完完成成其其全全部部运运行行，释释放放出出其其所所占占用用的的全全部资源。准备退出系统时的作业。部资源。准备退出系统时的作业。3.1 3.1 分级调度分级调度 作业状态及其转换图作业状态及其转换

3、图 spoolingspooling系统系统提交提交收容收容外存外存就绪就绪等待等待运行运行就绪就绪等待等待交换调度交换调度完完成成作业调度作业调度进程调度进程调度高级调度高级调度（作业调度、宏观调度）按一定原则对外（作业调度、宏观调度）按一定原则对外存输入井上的作业进行调度，并建立进程存输入井上的作业进行调度，并建立进程PCBPCB。它决定允。它决定允许哪些作业竞争系统资源。由于这种调度决定哪些作业许哪些作业竞争系统资源。由于这种调度决定哪些作业可以进入系统，所以也称收容调度。作业一旦被系统收可以进入系统，所以也称收容调度。作业一旦被系统收容，就便成进程或进程组。容，就便成进程或进程组。 中

4、中级级调调度度（交交换换调调度度）它它决决定定允允许许哪哪些些进进程程竞竞争争处处理理机机。中中级级调调度度通通过过使使进进程程临临时时挂挂起起和和激激活活的的方方法法对对系系统统负负载载波波动动作作出出反反映映，以以便便获获得得平平稳稳的的系系统统操操作作和和实实现现较较好好的的系系统统综综合合性性能能目目标标，中中级级调调度度的的作作用用使使作作为为作作业业进进入入系系统统和和将将中中央央处处理理机机分分配配给给这这些些作作业业二二者者之之间间的的一一个缓冲个缓冲。2 2 调度的层次调度的层次低低级级调调度度（进进程程调调度度）它它决决定定了了存存在在就就绪绪进进程程时时，哪哪一一个个就就

5、绪绪进进程程将将分分配配到到中中央央处处理理机机，并并且且把把中中央央处处理理机机实实际际分分配配给给这这个个进进程程（即即低低级级调调度度是是将将处处理理机机分分配配给给进进程程）。低低级级调调度度是是由由每每秒秒可可操操作作许许多多次次的的处处理理机机调调度度程程序序执执行行，处理机调度程序应常驻内存。处理机调度程序应常驻内存。2 2 调度的层次调度的层次 作业是用户向计算机提交任务的任务实体。作业是用户向计算机提交任务的任务实体。 进进程程是是计计算算机机为为了了完完成成用用户户任任务务实实体体而而设设置的执行实体。置的执行实体。 显显然然，计计算算机机要要完完成成一一个个任任务务实实体

6、体，必必须须要要有有一一个个以以上上的的执执行行实实体体，一一个个作作业业总总是是由由一一个以上的多个进程组成。个以上的多个进程组成。3 3作业与进程的关系作业与进程的关系作作业业调调度度的的功功能能：按按某某种种算算法法从从后后备备队队列列中中挑挑选选一个或一批作业调入内存，并创建一个或一批作业调入内存，并创建PCB.PCB.1 1后备作业队列与作业控制块后备作业队列与作业控制块 系系统统中中有有若若干干作作业业在在输输入入井井中中，为为了了管管理理和和调调度度作作业业，就就必必须须记记录录已已进进入入系系统统的的各各作作业业的的情情况况，系系统统为为每每个个作作业业设设置置了了一一个个作作

7、业业控控制制块块（JCBJCB）。）。内内容容：作作业业名名、作作业业状状态态、作作业业调调度度，以以及及资资源源申请和一些控制信息。申请和一些控制信息。3.2 3.2 作业的调度作业的调度 作业控制块作业控制块JCBJCB 作业名作业名 作业类型作业类型 资源要求资源要求 资源使用情况资源使用情况 优先级优先级 当前状态当前状态 其它其它作作业业调调度度按按照照某某种种调调度度算算法法从从后后备备作作业业队队列中选取作业，使其进入内存运行。列中选取作业，使其进入内存运行。 作作业业调调度度程程序序的的主主要要功功能能是是审审查查系系统统是是否否能能满满足足用用户户作作业业的的资资源源要要求求

8、以以及及按按照照一一定定的的算算法选取作业。法选取作业。1 1作业调度及其功能作业调度及其功能按按照照某某种种调调度度算算法法从从后后备备作作业业队队列列中中选取作业。选取作业。为为被被选选取取的的作作业业分分配配内内存存和和外外设设资资源源（当当系系统统为为动动态态分分配配外外设设时时，作作业业所所申申请请的的外外设设只只作作为为调调度度的的参参考考因因素素）。因因此要用到内存分配程序和外设分配程序。此要用到内存分配程序和外设分配程序。为选中的作业建立相应的进程。为选中的作业建立相应的进程。为为作作业业开开始始运运行行做做好好一一切切准准备备工工作作。如如构构造造和和读读写写作作业业运运行行

9、时时所所需需要要的的有有关关表表格格及及建建立立负负责责其其运运行行控控制制的的作作业业运运行行控制程序。控制程序。在在作作用用运运行行完完毕毕或或运运行行过过程程中中因因某某种种原原因因需需要要撤撤离离时时，作作业业调调度度程程序序还还有有完完成成作作业业的的善善后后处处理理工工作作，如如收收回回分分配配给给他的全部资源，它们将从系统中抹去他的全部资源，它们将从系统中抹去2.2.作业调度应完成如下几方面的工作作业调度应完成如下几方面的工作1)1)调度目标调度目标 对所有作业应该是公平合理对所有作业应该是公平合理 应使设备有高的利用率应使设备有高的利用率 每天执行尽可能多的作业每天执行尽可能多

10、的作业 有快的响应时间有快的响应时间3.3.作业调度目标与性能衡量作业调度目标与性能衡量2 2）作业调度的转换过程）作业调度的转换过程 （1 1）作业从后备状态到执行状态）作业从后备状态到执行状态 P85(a)P85(a)框图框图 （2 2）作业从执行状态到完成状态）作业从执行状态到完成状态 P85(b)P85(b)框图框图3.3.作业调度目标与性能衡量作业调度目标与性能衡量后备作业队列空后备作业队列空按调度算法从作按调度算法从作业中选出一作业业中选出一作业调用存储、设备管理调用存储、设备管理程序，审核资源要求程序，审核资源要求资源要求能满足？资源要求能满足？放弃该放弃该作业作业否否分配资源分

11、配资源调用进程管理调用进程管理程序建立进程程序建立进程进程调度进程调度否否是是出出口口作业从后备状态到执行状态作业从后备状态到执行状态撤销该作业的所有进程及作业的撤销该作业的所有进程及作业的JCB调用存储管理，设备管理回收调用存储管理，设备管理回收分配给该作业的全部资源分配给该作业的全部资源调用会计程序，计算该作业的执行费用调用会计程序，计算该作业的执行费用调度下一个作业调度下一个作业作业从执行状态到完成状态作业从执行状态到完成状态3 3）. .衡量一个作业调度算法是否满足系统设计的要衡量一个作业调度算法是否满足系统设计的要 求求 给给出出两两个个常常用用的的评评价价在在批批处处理理系系统统中

12、中对对作作业业调调度度算算法法优劣的性能量度优劣的性能量度1 1周转时间：周转时间：作业作业i i从提交时刻从提交时刻tsitsi到完成时刻到完成时刻teitei称为作业的周转时间。称为作业的周转时间。TiTi= =TeiTei- -TsiTsi 完成完成 提交提交3.3.作业调度目标与性能衡量作业调度目标与性能衡量作业平均周转时间为（有作业平均周转时间为（有n n个作业，个作业，n=1)n=1) n nT=1/n TiT=1/n Ti i=1 i=1一个作业的周转时间说明了该作业在系统内停留的时间一个作业的周转时间说明了该作业在系统内停留的时间包含两部分：一是等待时间；二为执行时间包含两部分

13、：一是等待时间；二为执行时间Ti = Twi - TriTi = Twi - Tri( (停留时间停留时间) )3.3.作业调度目标与性能衡量作业调度目标与性能衡量2 2带权周转时间带权周转时间WiWi：Wi=Ti/TriWi=Ti/Tri平均带权周转时间为：平均带权周转时间为： n nW=1/n WiW=1/n Wi i=1 i=13.3.作业调度目标与性能衡量作业调度目标与性能衡量（1 1）先来先服务（先来先服务（FCFSFCFS）调度算法）调度算法 将将用用户户作作业业和和就就绪绪进进程程按按提提交交顺顺序序或或变变为为就就绪绪状状态态的的先先后后排排成成队队列列，并并按按照照先先来来先

14、先服服务务的的方方式式进进行行调调度度处处理理，是是一一种种最最普普遍遍和和最最简简单单的的方方法法。它它优优先先考考虑虑在在系系统统中中等等待待时时间间最最长长的的作作业业，而而不不管管要要求求运行时间的长短。运行时间的长短。进程调度算法和作业调度算法。进程调度算法和作业调度算法。作业作业 进入时刻进入时刻 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转时间带权周转时间18：008：0010：28：5010：0010：39：0010：5011：49：5011：0011： 周转时间周转时间T1T12.00 2.00 带权周转时间带权周转时间W1W12/22/21 1 周转时间周

15、转时间T2T22.00 2.00 带权周转时间带权周转时间W2W2先来先服务算法分析结果先来先服务算法分析结果 周转时间周转时间T3T32.00 2.00 带权周转时间带权周转时间W3W3 周转时间周转时间T4T41.30 1.30 带权周转时间带权周转时间W4W46.50 6.50 周转时间周转时间TiTiTeiTeiTsi Tsi 带权周转时间带权周转时间WiWiTi/TriTi/Tri 平均周转时间平均周转时间T T1/nTi1/nTii=1n 该算法总是优先调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业。作业作业 进入时刻进入时刻 开始时刻开始时刻 完成时刻完成时刻

16、 周转时间周转时间 带权周转时间带权周转时间 1 81 8：00 800 8：00 1000 10： 2 8 2 8：50 1050 10：30 1130 11： 3 9 3 9：00 1000 10：00 1000 10： 4 9 4 9：50 1050 10：10 1010 10：（2 2）. .最短作业优先法（最短作业优先法（SJFSJF）平均周转时间平均周转时间T T1.55 1.55 平均带权周转时间平均带权周转时间T=4.65 T=4.65 最最高高响响应应比比作作业业优优先先算算法法是是对对FCFSFCFS方方式式和和SJFSJF方方式式的的一一种种综综合合平平衡衡相相应应比比R

17、 R定定义义为为系系统统对对作作业业的的响响应应时间与作业要求运行时间的比值时间与作业要求运行时间的比值R R响应时间响应时间 / / 要求运行时间要求运行时间( (作业等待时间需运行时间作业等待时间需运行时间)/ )/ 需运行时间需运行时间1 1已等待时间已等待时间 / / 需运行时间需运行时间1 1W/TW/T(3)(3)最高相应比作业优先算法（最高相应比作业优先算法（HRNHRN） 响响应应比比R R不不仅仅是是要要求求运运行行时时间间的的函函数数，而而且且还还是等待时间的函数。是等待时间的函数。由由于于R R与与要要求求运运行行时时间间成成反反比比，故故对对短短作作业业是是有有利利的的

18、，另另一一方方面面，因因R R与与等等待待时时间间成成正正比比，故故长长作作业业随随着着其其等等待待时时间间的的增增长长，也也可可获获的的较较高高的的相相应应比比。这这就就克克服服了了短短作作业业优优先先数数法法的的缺缺点点，既既照照顾顾了了先先来来者者，又又优优待待了了短短作作业业，是是上上述述两两种种算算法法的的一一种种较较好好的折中。的折中。作业作业 进入时刻进入时刻 开始时刻开始时刻 完成时刻完成时刻 周转时刻周转时刻 带权周转时刻带权周转时刻 1 81 8：00 800 8：00 1000 10：00 00 2 8 2 8：50 1050 10：50 1150 11：00 00 3

19、9 3 9：00 1000 10：00 1000 10：10 10 4 9 4 9：50 1150 11：00 1100 11：20 20 平均周转时间平均周转时间T T平均带权周转时间平均带权周转时间W WR1R1（等等待待时时间间执执行行时时间间）/ / 执执行行时间时间2 / 22 / 21 1R2R2）（）（ （）（）/ 0.50 / 0.50 1 1R3R3）（）（ （1 1）/ 0.10 / 0.10 R4R4）+ +（11.00) 11.00) （）（） 1 1 时时间间片片轮轮转转法法主主要要用用于于进进程程调调度度。采采用用此此算算法法的的系系统统，其其程程序序就就绪绪队队列

20、列往往往往按按进进程程到到达达的的时时间间来来排排序序。进进程程调调度度程程序序总总是是选选择择就就绪绪队队列列中中的的第第一一个个进进程程，也也就就是是说说按按照照先先来来先先服服务务原原则则调调度度，但但一一旦旦进进程程占占又又处处理理机机仅仅使使用用一一个个时时间间片片。在在使使用用先先一一个个时时间间片片后后，进进程程还还没没又又完完成成其其运运行行，它它必必须须释释放放出出处处理理机机给给下下一一个个就就绪绪的的进进程程，而而被被抢抢占占的的进进程程返返回到就绪队列的末尾重新排队等待在次运行。回到就绪队列的末尾重新排队等待在次运行。(4) (4) 轮转法（轮转法（RRRR）时时间间片

21、片轮轮转转策策略略特特别别适适合合于于分分时时系系统统中中使使用用，当当多多个个进进程程驻驻留留在在主主存存中中时时，在在进进程程间间转转接接处处理理机机的的开开销销一一般是不大的。般是不大的。 在在轮轮转转法法中中，时时间间片片长长度度的的选选取取非非常常重重要要，时时间间片片长长度度的的选选择择会会直直接接影影响响系系统统开开销销和和响响应应时时间间，如如果果时时间间片片长长度度过过短短，则则调调度度程程序序剥剥夺夺处处理理机机的的次次数数增增多多，这这将将使使进进程程上上下下文文交交换换次次数数也也大大大大增增加加，加加重重了了系系统统开开销销。如如果果时时间间片片长长度度选选择择过过长

22、长（大大）。大大到到一一个个进进程程足足以以完完成成其其全全部部运运行行工工作作所所需需的的时时间间，那那么么时时间间片片轮轮转转法法就就退退化化为为先先来来先先服服务务策策略略了了。最最佳佳的的时时间间片片量量值值应应能能使使分分时时用用户得到好的响应时间户得到好的响应时间 响应时间响应时间 S SRT/NmaxRT/Nmax R R响应时间响应时间 NmaxNmax最大进程数最大进程数 每每当当一一轮轮调调度度开开始始时时，系系统统便便根根据据就就绪绪队队列列中中已已有有进进程程数数目目计计算算一一次次值值。作作为为新新一一轮轮调调度度的的时时间间片片。这这种种方方法法得得到到的的时时间间

23、片片是是随随就就绪绪队队列列中中的进程数变化的。的进程数变化的。 进进程程调调度度的的功功能能：从从就就绪绪队队列列中中挑挑选选一一个个进进程到处理机上运行。程到处理机上运行。 作作业业调调度度程程序序在在挑挑选选作作业业进进入入主主存存运运行行时时，要要为为该该作作业业建建立立相相应应的的进进程程。在在作作业业完完成成后后要要撤撤销该作业的全部进程。销该作业的全部进程。 一一个个进进程程被被建建立立后后，系系统统为为了了便便于于对对进进程程的的管管理理，将将系系统统中中的的所所有有进进程程按按其其状状态态将将其其组组织织成成不同的进程队列。不同的进程队列。3.3 3.3 进程调度进程调度进程

24、调度程序：负责进程调度功能的内核程序。进程调度程序：负责进程调度功能的内核程序。作作业业调调度度与与进进程程调调度度程程序序的的区区别别：前前者者是是挑挑选选作作业业进进主主存存运运行行、后后者者是是挑挑选选就就绪绪进进程程到到处处理理机上运行。机上运行。进进程程调调度度的的核核心心问问题题就就是是，采采用用什什么么算算法法把把处处理机分配给进程。理机分配给进程。 进程调度的算法较多，在设计进程调度算进程调度的算法较多，在设计进程调度算法时应考虑的因素多，比如：尽量提高资源利法时应考虑的因素多，比如：尽量提高资源利用率，减少处理机的空闲时间，对于用户作业用率，减少处理机的空闲时间，对于用户作业

25、要较合理的平均响应时间，以及尽可能地增强要较合理的平均响应时间，以及尽可能地增强CPUCPU的处理能力。的处理能力。3.4 3.4 选择调度算法时应考虑的问题选择调度算法时应考虑的问题1. FIFO(1. FIFO(先来先服务调度算法先来先服务调度算法) ) 最简单的调度原则是先进先出最简单的调度原则是先进先出(FIFO)(FIFO)就绪队列就绪队列ABCDCPU完成完成3.5 3.5 调度算法调度算法根根据据进进程程到到达达就就绪绪队队列列的的时时间间来来分分配配中中央央处处理理机机，一一旦旦一一个个进进程程获获得得了了中中央央处处理理机机，就就一一直直运运行行到到结结束束，先先来来先服务是

26、非剥夺调度。先服务是非剥夺调度。这这种种调调度度从从形形式式上上讲讲是是公公平平的的，但但它它使使短短作作业业要要等等待待长长作作业业的的完完成成，重重要要的的作作业业要要等等待待不不重重要要作作业业的的完完成成。从这个意义上讲又是不公平的。从这个意义上讲又是不公平的。先先进进先先出出调调度度使使响响应应时时间间的的变变化化较较小小，因因此此它它比比其其它它大大多多数数调调度度都都可可预预测测。由由于于这这种种调调度度方方法法不不能能保保证证良良好好的响应时间，在处理交互式用户时很少用这种方法。的响应时间，在处理交互式用户时很少用这种方法。在当今系统中，先进现出很少作为调度在当今系统中，先进现

27、出很少作为调度模式，而是常常嵌套在其它的调度模式中。模式，而是常常嵌套在其它的调度模式中。例如，许多调度模式根据优先级将处理机分例如，许多调度模式根据优先级将处理机分配给进程，但具有相同优先级的进程却按先配给进程，但具有相同优先级的进程却按先进先出进行分配。进先出进行分配。根根据据作作业业要要求求系系统统提提供供的的处处理理机机时时间间，内内存存的的大大小小和和I/OI/O设设备备的的数数量量，来来确确定定作作业业的的优优先先数数，如如果果系系统统赋赋予予作作业业的的反反比比于于系系统统的的估估计计执执行行时时间间，就就形形成成短短作作业业优优先先的的算算法法。由由于于作作业业需需要要的的执执

28、行行时时间间事事先先难难于于确确定定，只只是是把把用用户户自自保保的的估估计计时时间间作作为为依依据据，为为防防止止用用户户少少报报自自己己的的作作业业时时间间以以获获得得优优先先服服务务，在在采采用用短短作作业业优优先先算算法法时时，应应采采取取适适当的防备措施。当的防备措施。 2. 2. 作业要求的资源作业要求的资源 在有的系统中，分配给作业的优在有的系统中，分配给作业的优先数还取决于它所占用的内存的多少，先数还取决于它所占用的内存的多少，作业越大，占用内存越多，分配给它作业越大，占用内存越多，分配给它的优先数越低。显然，不论是根据作的优先数越低。显然，不论是根据作业的执行时间，还是根据作

29、业的大小业的执行时间，还是根据作业的大小所确定的优先数，都有利于短作业。所确定的优先数，都有利于短作业。 3.3.动态优先数动态优先数 虽虽然然基基于于静静态态优优先先数数的的调调度度算算法法比比较较简简单单，也也颇颇为为流流利利，但但毕毕竟竟不不够够精精确确。因因为为进进程程的的优优先先数数在在它它执执行行前前就就已已算算好好，且且在在整整个个执执行行期期间间都都保保持持不不变变，但但随随着着进进程程的的推推进进，计计算算优优先先数数所所依依赖赖的的特特征征很很多多都都将将随随之之改改变变，因因此此静静态态优优先先数数并并非非自自始始至至终终都都能能准准确确地地反反映映出出这这些些特特性性，

30、如如果果能能在在进进程程运运行行中中，不不断断的的随随着着特特性性的的改改变变而而修修改改其其优优先先数数，显显然然可可以以实实现现更更多多精精确确的的调调度度，从从而而获获得得更更好好的的调调度度性性能能，这对分时系统显得格外重要这对分时系统显得格外重要. .4.4.时间片轮转算法时间片轮转算法 FCBA.CPU完成完成ABC当当时时间间片片很很大大时时，每每个个进进程程得得到到比比完完成成该该进进程程多多的的处处理理机机时时间间，此此时时轮轮转调度模式退化为先进先出模式。转调度模式退化为先进先出模式。当当时时间间片片非非常常小小时时，上上下下文文转转换换开开销销就就成成了了决决定定因因素素

31、，系系统统性性能能降降低低，大大多多数数时时间间都都消消耗耗在在处处理理机机的的转转换换上上，只有少许用在用户的计算上。只有少许用在用户的计算上。这这个个最最佳佳的的时时间间片片值值是是多多少少呢呢？显显然然，它它将将随系统而异。随负载而异，同时也随进程异。随系统而异。随负载而异，同时也随进程异。 时时间间片片的的选选取取是是实实现现各各种种调调度度算算法法的的关关键键之之处处，而而时时间间片片的的独独额额定定通通常常应应考考虑虑终终端端数数目目，处处理理机机能能力力、各各终终端端任任务务的的急急迫迫程程度度、外外存存传传输输速速度度等等方方面面的的因因素素。时时间间片片轮轮转转法法亦亦可可应

32、应用用于于批批处处理理系系统统的的处处理机调度。理机调度。一一种种常常用用的的进进程程调调度度算算法法是是把把处处理理机机分分配配给给具具有有最最高高优优先先数的进程（用于实时系统）数的进程（用于实时系统） 在在这这种种算算法法中中，首首先先考考虑虑的的问问题题是是如如何何确确定定进进程程的的优优先数。先数。 一种是静态优先数，另一种是动态优先数。一种是静态优先数，另一种是动态优先数。1)1)静态优先数静态优先数 静静态态优优先先数数是是在在系系统统创创建建时时确确定定的的，一一经经确确定定之之后后在在整整个个进进程程运运行行期期间间不不再再改改变变，确确定定静静态态优优先先数数的的有有关关静

33、静特特性是：性是：5.5.优先级调度算法优先级调度算法 系系统统中中由由两两类类进进程程，系系统统进进程程和和用用户户进进程程。系系统统进进程程的的优优先先数数比比用用户户进进程程的的优优先先数数高高，特特别别是是某某些些系系统统进进程程，必必须须赋赋予予它它一一种种特特权权，当当它它需需要要处处理理机机时时，应应尽尽快快的的到到满满足。足。 例如，设备管理器中的例如，设备管理器中的I/OI/O进程便是如此。这不仅是进程便是如此。这不仅是为了保证为了保证I/OI/O设备尽可能忙碌，一提高设备利用率，更设备尽可能忙碌，一提高设备利用率，更主要的是为了避免由于响应不及时，将造成信息的丢失。主要的是

34、为了避免由于响应不及时，将造成信息的丢失。在用户进程中，在用户进程中，I/OI/O繁忙的进程应优先与繁忙的进程应优先与CPUCPU繁忙的进程，繁忙的进程，以保证以保证CPUCPU和和I/OI/O设备之间的并行操作。在分时系统中，前设备之间的并行操作。在分时系统中，前台进程应优先于后台进程。台进程应优先于后台进程。 进程类型进程类型什么是多处理机系统什么是多处理机系统 多处理机操作系统的分类多处理机操作系统的分类 多处理机系统调度策略多处理机系统调度策略 3.6 3.6 多处理机调度多处理机调度 多多处处理理机机系系统统：是是一一个个具具有有两两个个或或多多个个处处理理机机并并能能相相互互进进行

35、行通通信信以以协协同同一一个个大大的的给给定定问问题题求求解解的的计计算算机系统。机系统。特点：特点： 1 1） 有两个或多个处理机有两个或多个处理机2 2） 共享主存或高速通信网络共享主存或高速通信网络3 3） 共享输入输出子系统共享输入输出子系统4 4） 有单一完整的操作系统有单一完整的操作系统5 5） 各级硬件和软件相互作用各级硬件和软件相互作用3.6.1.3.6.1.什么是多处理机系统什么是多处理机系统主要功能：主要功能： 进程分配进程分配 更好的利用多机硬件更好的利用多机硬件 资源在处理机之间的分配资源在处理机之间的分配 改善程序的响应时间改善程序的响应时间 处理机的负载平衡处理机的

36、负载平衡 处理机间的协调和同步处理机间的协调和同步 因处理机故障引起的系统重组因处理机故障引起的系统重组 广广意意上上说说，使使用用多多处处理理机机协协调调工工作作，来来完完成成用用户户所所要要求求任任务务的的计计算算机机系系统统。这这包包扩扩了了并并行行处处理理系系统统（ parallel parallel processing processing systemsystem） ， 例例 如如 数数 据据 流流 机机(dataflow (dataflow machine)machine)和和细细胞胞阵阵列列处处理理机机(Celluar (Celluar array array process

37、ors)processors)等等, ,也也包包扩扩了了在在物物理理上上分分散散且且通通过过不不同同的的物物理理传传输输媒媒体体传传输输数数据据的的机机算算机机网网络络系系统统和和计计算算机机网网络络为为基基础础的的, ,对对用用户户透透明明的的分分布布式式系系统统, ,以以及及在在同同一一的的计计算算机机系系统统里里共共享享内内存存的的多多处处理理机机系系统统. . 广广义义的的计计算算机机系系统统的的一一个个共共同同的的特特点点是是有有n n个个处处理理器器(n1),(n1),能能做做到到真真正正的的并并行行处理处理, ,也就是能同时执行也就是能同时执行n n条指令条指令. . 本本节节所

38、所介介绍绍的的多多处处理理机机操操作作系系统统是是指指哪哪些些用用来来并并行行执执行行用用户户的的几几个个程程序序，以以提提高高系系统统的的吞吞吐吐率率；或或 行行 余余操操作作以以提提高高系系统统可可靠靠性性的的多多处处理理操操作作系系统统。这这种种系系统统由由共共享享公公共共内内存存和和外外设设的的n(n1)n(n1)个个 CPUCPU组成。组成。 从从概概念念上上说说，在在多多处处理理机机系系统统中中的的各各进进程程的的行行为为与与在在单单机机系系统统下下的的行行为为相相同同。因因此此，对对多多处处理理机机操操作作系系统统的的要要求求与与对对多多道道程程序序的的批批处处理理系系统统没没有

39、有太太多多的的区区别别。但但是是，多多处处理理环环竟竟下下，进进程程可可在在各各处处理理机机间间进进行行透透明明迁迁移移，从从而而，由由进进程程上上下下文文切切换换等等带带来来的的系系统统开开销销将将使使得得多多处处理理机机操操作作系系统统的的复复杂杂度度大大大大增增加加。另另外外，由由于于多多处处理理机机系系统统并并行行地地执执行行用用户户的的几几个个程程序序（进进程程），这又带来了多处理机条件下的并发执行问题。这又带来了多处理机条件下的并发执行问题。多处理机操作系统的分类多处理机操作系统的分类使使用用多多处处理理机机系系统统的的主主要要原原因因是是提提高高系系统统的的可可靠靠性性和和在在发

40、发生生故故障障时时能能将将低低使使用用；另另一一个个原原因因是是提提高高系系统统吞吞吐吐 。因因此此，一一个个多多处处理理机机操操作作系系统统除除了了提提高高资资原原分分配配和和管管理理，进进程程和和处处理理机机管管理理，内内存存和和数数据据集集保保护护以以及及文文件件系系统统等等功功能能之之外外，还还能能提提供供系系统统结结构构重重组组的的能能力力，以以支支持持系系统统的的降降级级使使用用。因因此此，多多处处理理机机的的调调度度策策略略也也必必须须考考虑虑到到降级使用和结构重组问题。降级使用和结构重组问题。 目目前前为为止止的的多多处处理理机机操操作作系系统统可可以以分分为为三三类类： (1

41、) (1) 主从式（主从式（master-slave configurationmaster-slave configuration）(2) (2) 独立监控系统独立监控系统(Separate supervisor) (Separate supervisor) (3) (3) 移动式监控系统移动式监控系统(floating supervisor)(floating supervisor) 主主从从式式中中，指指定定一一台台特特定定的的处处理理机机为为主主处处理理机机，由由它它负责对全系统的执行进行控制负责对全系统的执行进行控制. . 在在主主从从式式操操作作系系统统中中，主主处处理理器器上上执

42、执行行操操作作系系统统程程序序，以以控控制制其其它它从从处处理理机机的的状状态态，并并为为从从处处理理机机分分配配任任务务。DEC DEC system system 10 10 ,Cyber ,Cyber 170 170 以以及及多多处处理理机机UNIXUNIX系系统统MPXMPX都都是是主主从从式式结结构构. .在在主主从从式式操操作作系系统统中中, ,如如果果从从处处理理机机需需要要主主处处理理机机提提供供服服务务时时, ,它它们们采采用用硬硬件件中中断断方方式式中中断断处处理理机机上上执执行行的的进进程程以以要要求求主主处处理理机机提提供供服服务务. .这这种种结结构构的的操操作作系系

43、统统一一般般重重组组功功能能较较差差, ,因因为为只只有有主主处处理理机机上上执执行行操操作作系系统统程程序序. .如如果果主主处处理理机机失失败败或或发发生生不不可可恢恢复复的的错错误误时时, ,整整个个系系统统将将会会瘫瘫痪痪. .(1)(1)主从式主从式（master-slave configurationmaster-slave configuration） 独立监控系统的监控程序在每个处理机上执行独立监控系统的监控程序在每个处理机上执行, , 每个处理机为自己的需要提供服务又互相通报执每个处理机为自己的需要提供服务又互相通报执行情况行情况. .一般来说一般来说, ,每个监控程序能重新

44、装入或在不每个监控程序能重新装入或在不同的处理机上复制独立的副本同的处理机上复制独立的副本. . 独独立立监监控控系系统统不不像像主主从从结结构构那那样样易易于于崩崩溃溃, ,但但其其监控程序在各处理机中的副本会占去大量的内存监控程序在各处理机中的副本会占去大量的内存. .(2)(2)独立监控系统独立监控系统( (Separate supervisorSeparate supervisor) ) 移动式监控系统移动式监控系统：移动式监控系统把监控程：移动式监控系统把监控程序根据需要从一个处理机移到另一个处理机上序根据需要从一个处理机移到另一个处理机上. .使使所有资原有比较均衡的负载所有资原有

45、比较均衡的负载. . 移动式监控系统的处理机调度以及服务请求移动式监控系统的处理机调度以及服务请求冲突等大都采用优先级的方式来解决冲突等大都采用优先级的方式来解决. .所以所以 移动移动式监控系统是一种效率最高式监控系统是一种效率最高, ,实现也最难的多处理实现也最难的多处理操作系统操作系统. .(3)(3)移动式监控系统移动式监控系统(floating supervisor)(floating supervisor)（1 1） 多处理机系统与单机调度的区别多处理机系统与单机调度的区别 多多处处理理机机调调度度与与单单机机调调度度的的主主要要区区别别涉涉及及两两个个资资源源分分配问题：配问题：

46、一是存放程序或数据的存储器分配及如何访问他们的问题。一是存放程序或数据的存储器分配及如何访问他们的问题。 在在多多机机系系统统中中，由由于于各各进进程程在在物物理理上上也也同同时时执执行行而而不不是是单单机机系系统统那那样样的的交交叉叉执执行行，这这些些在在物物理理上上同同时时执执行行的的进进程程可可能能同同时时访访问问物物理理存存储储器器的的同同一一地地址址。处处理理机机对对同同一一存存储储块块的的访访问问必必须须是是顺顺序序的的。各各进进程程同同时时访访问问物物理理存存储储器器上上的同一地址是不允许的。的同一地址是不允许的。3.6.3 3.6.3 多处理机系统调度策略多处理机系统调度策略

47、二二是是将将等等待待执执行行的的就就绪绪进进程程分分配配到到哪哪一一个个处处理理机机上上执执行行的问题。的问题。 在在单单机机系系统统中中，由由于于只只有有一一个个处处理理机机，在在调调度度程程序序中中选选取取了了某某个个就就绪绪状状态态的的进进程程之之后后，不不须须再再选选择择处处理理机机。而而在在多多机机系系统统中中，为为了了尽尽量量做做到到让让各各处处理理机机负负荷荷平平恒恒，可可能能会会会会将将处处理理机机在在进进程程之之间间进进行行多多次次切切换换。如如果果被被切切换换进进程程正正在在执执行行其其临临界界区区部部分分或或系系统统中中进进程程数数目目相相当当多多，这这种种频繁的上下文转

48、换将会使系统效率大大下降。频繁的上下文转换将会使系统效率大大下降。 为了解决进程对处理机的分配问题，在有的多出理机系为了解决进程对处理机的分配问题，在有的多出理机系统中采用了局部就绪对列的方法限制进程的转移。统中采用了局部就绪对列的方法限制进程的转移。 局部就绪对列：局部就绪对列：就是把处于就绪状态的进程分成不同就是把处于就绪状态的进程分成不同的组，并使每一组进程和一个处理机对应起来。这样，每个的组，并使每一组进程和一个处理机对应起来。这样，每个处理机只执行以其对应就绪对列中的进程。各个就绪对列中处理机只执行以其对应就绪对列中的进程。各个就绪对列中的进程读断发生横向转移。这种方法减少了调度程序

49、的开销。的进程读断发生横向转移。这种方法减少了调度程序的开销。但是，处理机的使用率却因此下降。例如：系统中某个局部但是，处理机的使用率却因此下降。例如：系统中某个局部就绪对列中因等待进程较多而使得对应的处理机十分繁忙，就绪对列中因等待进程较多而使得对应的处理机十分繁忙，而另外的处理机则因就绪对列为空而处于空闲状态。而另外的处理机则因就绪对列为空而处于空闲状态。 多处理机系统的调度目标是：以最高的可靠性，使用最少的处理机在最短的时间多处理机系统的调度目标是：以最高的可靠性，使用最少的处理机在最短的时间内完成最多的可以并行完成的进程。内完成最多的可以并行完成的进程。 多处理机的调度有两种评价模型：

50、 一种是确定性模型，另一种是随机性模性。 确定性模型：进程调度执性之前，估计出这些被调度进程所须要的执行时间，以及这些进程之间的相互关系。 调度程序的目的：是根据给定的执行时间和相互关系，确定出一个最佳的执行顺序。 因此，确定性模型只用来确定给定进程的执行顺序，而随机性模性则常被用来研究动态调度技术。 （2 2）多处理机的调度评价）多处理机的调度评价 动态调度：动态调度：在一个特定的时刻，将进程分配到一个特在一个特定的时刻，将进程分配到一个特定的处理机上执行。随机模型中的进程执行时间是一个具定的处理机上执行。随机模型中的进程执行时间是一个具有平均值和标准偏移值的随机变量。有平均值和标准偏移值的随机变量。 无论是确定模型还是随机模型，我们都可以把一个无论是确定模型还是随机模型，我们都可以把一个包含进程集合的工作集用优先图的方式表现出来，图中节包含进程集合的工作集用优先图的方式表现出来，图中节点的集合点的集合T=T1T=T1，T2T2，TnTn代表进程的集合，结点的加权代表进程的集合，结点的加权集合集合W=W1,W2W=W1,W2，WnWn代表各进程在处理机上执行时间的代表各进程在处理机上执行时间的集合。对于确定模型来说，集合。对于确定模型来说，W W中各元素为随机变量。中各元素为随机变量。