处理机调度-new.ppt

《处理机调度-new.ppt》由会员分享，可在线阅读，更多相关《处理机调度-new.ppt（31页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第四章 处理机调度提纲提纲n4.1 分级调度分级调度n4.2 作业调度作业调度n4.3 进程调度进程调度n4.4 调度算法调度算法4.1 分级调度分级调度1 作业的状态及其转换作业的状态及其转换n一个作业从提交给计算机系统到执行结束退出系统，一个作业从提交给计算机系统到执行结束退出系统，一般都要经历一般都要经历4个状态个状态:提交提交收容收容执行执行完成完成n(1)提交状态提交状态:一个作业在其处于从输入设备进入一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态。外部存储设备的过程称为提交状态。n(2)收容状态收容状态(后备状态后备状态):若一个作业的全部信息若一个作业的全部信息已全

2、部被输入进输入井，那么，在它还未被调度已全部被输入进输入井，那么，在它还未被调度去执行之前，该作业处于收容状态。去执行之前，该作业处于收容状态。n(3)执行状态执行状态:作业调度程序从后备作业中选取若作业调度程序从后备作业中选取若干个作业到内存投入运行。这些被选中的作业处干个作业到内存投入运行。这些被选中的作业处于执行状态。于执行状态。n(4)完成状态完成状态:当作业运行完毕，但它所占用的资当作业运行完毕，但它所占用的资源尚未全部被系统回收时，该作业处于完成状态。源尚未全部被系统回收时，该作业处于完成状态。提交后备执行完成退出SPOOLing输入作业调度1作业调度2SPOOLing输出2.分级

3、调度分级调度n(1)作业调度作业调度：又称宏观调度，或高级调度。其主：又称宏观调度，或高级调度。其主要任务是按一定的原则对外存输入井上的大量后备要任务是按一定的原则对外存输入井上的大量后备作业进行选择，给选出的作业分配内存、输入输出作业进行选择，给选出的作业分配内存、输入输出设备等必要的资源，并建立相应的进程。另外，当设备等必要的资源，并建立相应的进程。另外，当该作业执行完毕时，还负责回收系统资源。该作业执行完毕时，还负责回收系统资源。n(2)交换调度交换调度：又称中级调度。其主要任务是按照：又称中级调度。其主要任务是按照给定的原则和策略，将处于外存交换区中的就绪状给定的原则和策略，将处于外存

4、交换区中的就绪状态或等待状态的进程调入内存，或把处于内存就绪态或等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。状态或内存等待状态的进程交换到外存交换区。n(3)进程调度进程调度：又称微观调度或低级调度。其主：又称微观调度或低级调度。其主要任务是按照某种策略和方法选取一个处于就绪要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。在确定了占用处理机的状态的进程占用处理机。在确定了占用处理机的进程后，系统必须进行进程上下文切换以建立与进程后，系统必须进行进程上下文切换以建立与占用处理机进程相适应的执行环境。占用处理机进程相适应的执行环境。n(4)线程

5、调度线程调度。分级调度分级调度4.2 作业调度作业调度n作业调度作业调度从从后备状态后备状态到到执行状态执行状态的转变的转变从从执行状态执行状态到到完成状态完成状态的转变的转变周转时间：周转时间：作业作业i的周转时间的周转时间Ti为为Ti=Tei-Tsi其中其中Tei为作业为作业i的完成时间，的完成时间，Tsi为作业的提交时间。为作业的提交时间。对于被测定作业流所含有的对于被测定作业流所含有的n（n=1）个作业来说，个作业来说，其平均周转时间为：其平均周转时间为：一个作业的周转时间说明了该作业在系统内停留的时一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：等待时间、执行时间，即：

6、间，包含两部分：等待时间、执行时间，即：Ti=TwiTriTwi指作业指作业i由后备状态到执行状态的等待时间，它不由后备状态到执行状态的等待时间，它不包括作业进入执行状态后的等待时间。包括作业进入执行状态后的等待时间。带权周转时间带权周转时间带权周转时间是作业周转时间与作业执行时间的比：带权周转时间是作业周转时间与作业执行时间的比：Wi=Ti/Tri对于被测定作业流所含有的几个作业来说，其平均带对于被测定作业流所含有的几个作业来说，其平均带权周转时间为：权周转时间为：4.3 进程调度进程调度进程上下文切换进程上下文切换n进程上下文进程上下文正文段正文段数据段数据段硬件寄存器的内容硬件寄存器的内

7、容n存放存放CPU将要执行的下条指令地址的程序计数器将要执行的下条指令地址的程序计数器PCn处理机状态寄存器处理机状态寄存器PSn存放过程调用（或系统调用）时所传递参数的通用寄存放过程调用（或系统调用）时所传递参数的通用寄存器存器R以及堆栈指针寄存器以及堆栈指针寄存器S等等有关数据结构有关数据结构nPCB等在内的所有与执行该进程有关的管理和控制用等在内的所有与执行该进程有关的管理和控制用表格、数组、链等表格、数组、链等n进程上下文切换，包括进程上下文切换，包括4个步骤：个步骤：(1)决定是否做上下文切换以及是否允许做上下决定是否做上下文切换以及是否允许做上下文切换。文切换。n包括对进程调度原因

8、的检查分析，以及当前执行进程包括对进程调度原因的检查分析，以及当前执行进程的资格和的资格和CPU执行方式的检查等。执行方式的检查等。(2)保存当前执行进程的上下文。保存当前执行进程的上下文。(3)使用某种进程调度算法，选择一个处于就绪使用某种进程调度算法，选择一个处于就绪状态进程。状态进程。(4)恢复或装配所选进程的上下文，将恢复或装配所选进程的上下文，将CPU控制控制权交给所选进程。权交给所选进程。4.4 调度算法调度算法n进程调度进程调度n作业调度作业调度1.先来先服务调度算法先来先服务调度算法（FCFS First Come First Serve）n思想：思想：将用户作业或就绪进程按提

9、交顺序或变为就绪状态将用户作业或就绪进程按提交顺序或变为就绪状态的顺序排成队列，并按照先进先出的方式进行调度的顺序排成队列，并按照先进先出的方式进行调度处理，是一种最简单的方法。处理，是一种最简单的方法。n特点特点:(1)实现简单实现简单(2)适于作业调度、进程调度适于作业调度、进程调度(3)公平公平?n对执行时间较短的作业或进程来说，等待时间可能较长对执行时间较短的作业或进程来说，等待时间可能较长例例1:如果作业队列依次如果作业队列依次(几乎同时几乎同时)到达如下到达如下3个作业，按个作业，按“先先来先服务来先服务”的方式进行调度完成后，计算平均等待时间：的方式进行调度完成后，计算平均等待时

10、间：作业需运行时间J150J210J31运行情况：运行情况：0506061平均等待时间平均等待时间=（0+50+60）/336.67如果到达顺序为如果到达顺序为J3、J2、J1，运行情况：，运行情况：011161平均等待时间平均等待时间=（0+1+11）/3=4J1J2J3J3J2J1例例2:在单道环境下，某批处理显然有四道作业，已知在单道环境下，某批处理显然有四道作业，已知他们的进入系统的时刻、估计运算时间如下：他们的进入系统的时刻、估计运算时间如下：作业作业进入时刻进入时刻(h)运行时间运行时间(h)12348.008.509.009.502.000.500.100.20用用FCFS算法计

11、算作业的运行情况、平均周转时间和算法计算作业的运行情况、平均周转时间和平均带权周转时间平均带权周转时间作业作业进入时刻进入时刻运行时间运行时间开始时刻开始时刻完成时刻完成时刻 周转时间周转时间带权周转带权周转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（h）2.轮转调度算法（轮转调度算法（Round Robin）n思想：思想：将将CPU的处

12、理时间分成固定大小的时间片的处理时间分成固定大小的时间片T。如果一个进程在被调度选中之后用完了系统规定的如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己时间片，但未完成要求的任务，则它自行释放自己所占有的所占有的CPU而排到就绪队列的末尾，等待下一次而排到就绪队列的末尾，等待下一次调度。调度。进程调度程序调度当前就绪队列中的第一个进程。进程调度程序调度当前就绪队列中的第一个进程。n特点：特点：（1）该算法适于进程调度，一般不适于作业调度）该算法适于进程调度，一般不适于作业调度（为什么？）（为什么？）n轮转法一般只能分配那些轮转法一般只能分配那些可抢占资源

13、可抢占资源，将他们随时抢占，将他们随时抢占再分配给其他进程，再分配给其他进程，cpu是可抢占资源的一种，但打印是可抢占资源的一种，但打印机等为不可抢占资源，由于作业掉队是对除了机等为不可抢占资源，由于作业掉队是对除了cpu之外之外的所有系统硬件资源的分配，其中包含有不可抢占的资的所有系统硬件资源的分配，其中包含有不可抢占的资源，所以作业调度不使用轮转法。源，所以作业调度不使用轮转法。（2）适应系统：分时系统）适应系统：分时系统（3）时间片长度的取值）时间片长度的取值固定时间片固定时间片时间片长度：时间片长度：几十毫秒几十毫秒 几百毫秒几百毫秒(例如例如 50ms)过长：响应速度慢过长：响应速度

14、慢 算法会退化为算法会退化为FCFS；过短：进程切换过于频繁过短：进程切换过于频繁系统开销系统开销(overhead)大。大。可变时间片可变时间片设系统对响应时间的要求是设系统对响应时间的要求是R，就绪队列中最大进程数为，就绪队列中最大进程数为Nmax。因为因为 R|T|*Nmax 所以所以|T|R/Nmax一种可行的办法是，每当一轮调度开始时，系统便根据就绪队列中已一种可行的办法是，每当一轮调度开始时，系统便根据就绪队列中已有进程数目计算一次有进程数目计算一次T值，作为新一轮调度的时间片。这种方法得到的值，作为新一轮调度的时间片。这种方法得到的时间片值随就绪队列中的进程数变化。时间片值随就绪

15、队列中的进程数变化。3.最短作业优先调度算法最短作业优先调度算法(SJF Shortest Job First)n思想：思想：选择那些估计需要执行时间最短的作业投入执行。选择那些估计需要执行时间最短的作业投入执行。n例：如果作业队列依次例：如果作业队列依次(几乎同时几乎同时)到达如下到达如下3个作业个作业,按最短作业优先法（按最短作业优先法（SJF）调度。）调度。作业需运行时间J150J210J31011161平均等待时间平均等待时间=（0+1+11）/3=4J3J2J1优点优点:（1）可使得系统在单位时间内处理的作业）可使得系统在单位时间内处理的作业个数最多个数最多吞吐量最大。吞吐量最大。（

16、2）对同一批作业而言，该算法使得作业）对同一批作业而言，该算法使得作业的平均等待时间最短。的平均等待时间最短。缺点：缺点：可能使得某些运行时间较长的作业得不到可能使得某些运行时间较长的作业得不到调度执行的机会。调度执行的机会。两种调度方式：两种调度方式：（1）非剥夺方式非剥夺方式（2）剥夺方式剥夺方式，即最短剩余时间优先，即最短剩余时间优先Shortest-Remaining-Time First(SRTF)。最短剩余时间：从作业当前运行到完成所需时间。最短剩余时间：从作业当前运行到完成所需时间。最短剩余时间优先调度是抢占算法。最短剩余时间优先调度是抢占算法。该算法允许比当前进程剩余时间更短的

17、进程来抢占该算法允许比当前进程剩余时间更短的进程来抢占 非剥夺方式示例非剥夺方式示例：Process Arrival Time Burst TimeP10.07 P22.04 P34.01 P45.04n平均等待时间平均等待时间=(0+6+3+7)/4=4P1P3P273160P4812剥夺方式示例：剥夺方式示例：Process Arrival Time Burst TimeP10.07 P22.04 P34.01 P45.04n平均等待时间平均等待时间=(9+1+0+2)/4=3P1P3P242110P457P2P1164.最高响应比优先调度算法最高响应比优先调度算法（HRN：Highest

18、 Response ratio Next）n思想：思想：响应比响应比R定义如下：定义如下：R=(W+T)/T=1+W/TnT为该作业估计需要的执行时间为该作业估计需要的执行时间nW为作业的等待时间为作业的等待时间每当要进行作业调度时，系统计算每个作业的响应每当要进行作业调度时，系统计算每个作业的响应比，选择其中比，选择其中R最大者投入执行。最大者投入执行。n特点：特点：介于介于FCFS和和SJF 之间的一种折中算法之间的一种折中算法由于每次调度前要计算响应比，系统开销也要相应由于每次调度前要计算响应比，系统开销也要相应增加增加R=(W+T)/T=1+W/T例子：例子：作业到达时间需运行时间开始

19、时间完成时间等待时间J18:0050分8:008:500分J28:3020分J38:4015分J48:555分8:50 9:10 20分分9:15 9:30 35分分9:10 9:15 15分分平均等待时间平均等待时间(0203515)417.5分别采用分别采用FCFS、SJF算法进行调度，各自的平均等待时算法进行调度，各自的平均等待时间？反映了什么问题？间？反映了什么问题？5.优先级调度算法（优先级调度算法（HPF：Highest Priority First）n思想：思想：系统或用户按某种原则为作业或进程指定一个优先系统或用户按某种原则为作业或进程指定一个优先级，系统按优先级进行调度。级，

20、系统按优先级进行调度。n特点：特点：可被用于作业或进程的调度可被用于作业或进程的调度n注意注意：(1)优先级的确定优先级的确定n静态法：在作业或进程开始执行之前就确定它们的优先静态法：在作业或进程开始执行之前就确定它们的优先级，一旦开始执行之后就不能改变。级，一旦开始执行之后就不能改变。n动态法：随着作业或进程的执行，其优先级不断变化。动态法：随着作业或进程的执行，其优先级不断变化。(2)影响优先级因素影响优先级因素n外因：任务的紧迫程度、付费、进程类型外因：任务的紧迫程度、付费、进程类型(系统、用户进系统、用户进程程)。例如，在操作系统中，对于键盘中断的处理优先级。例如，在操作系统中，对于键

21、盘中断的处理优先级和对于电源掉电中断的处理优先级是不相同的。和对于电源掉电中断的处理优先级是不相同的。n内因：作业类型（内因：作业类型（IO型、计算型）、资源需求型、计算型）、资源需求(3)剥夺剥夺/非剥夺优先级调度非剥夺优先级调度n非剥夺方式：获得处理机的进程，直至终止、等待非剥夺方式：获得处理机的进程，直至终止、等待n剥夺方式：获得处理机的进程，直至终止、等待、出现剥夺方式：获得处理机的进程，直至终止、等待、出现高优先级的就绪进程高优先级的就绪进程nUNIX：可剥夺、动态优先级调度：可剥夺、动态优先级调度 6.多级队列算法（多级队列算法（MLQ：Multilevel Queue）思想：多个就绪队列，进程所属的队列固定。不同就思想：多个就绪队列，进程所属的队列固定。不同就绪队列具有不同优先级；各个队列拥有自己的调度算绪队列具有不同优先级；各个队列拥有自己的调度算法；处理机要在不同队列中调度。法；处理机要在不同队列中调度。例如：某通用系统例如：某通用系统 队列队列1 1：实时进程就绪队列（：实时进程就绪队列（HPF）队列队列2 2：分时进程就绪队列（：分时进程就绪队列（RR）队列队列3 3：批处理进程就绪队列（：批处理进程就绪队列（HPF）