《处理机调度-new》由会员分享，可在线阅读，更多相关《处理机调度-new（31页珍藏版）》请在金锄头文库上搜索。
1、第四章 处理机调度提纲n4.1 分级调度n4.2 作业调度n4.3 进程调度n4.4 调度算法4.1 分级调度1 作业的状态及其转换n一个作业从提交给计算机系统到执行结束退出系统 ，一般都要经历4个状态:提交收容执行完成n(1)提交状态:一个作业在其处于从输入设备进入外 部存储设备的过程称为提交状态。n(2)收容状态(后备状态):若一个作业的全部信息已 全部被输入进输入井，那么，在它还未被调度去 执行之前，该作业处于收容状态。n(3)执行状态:作业调度程序从后备作业中选取若干 个作业到内存投入运行。这些被选中的作业处于 执行状态。 n(4)完成状态:当作业运行完毕，但它所占用的资源 尚未全部被
2、系统回收时，该作业处于完成状态。提交后备执行完成退出SPOOLing 输入作业调度1作业调度2SPOOLing 输出2. 分级调度n(1) 作业调度：又称宏观调度，或高级调度。其主 要任务是按一定的原则对外存输入井上的大量后备 作业进行选择，给选出的作业分配内存、输入输出 设备等必要的资源，并建立相应的进程。另外，当 该作业执行完毕时，还负责回收系统资源。n(2) 交换调度：又称中级调度。其主要任务是按照 给定的原则和策略，将处于外存交换区中的就绪状 态或等待状态的进程调入内存，或把处于内存就绪 状态或内存等待状态的进程交换到外存交换区。n(3) 进程调度：又称微观调度或低级调度。其主要 任务
3、是按照某种策略和方法选取一个处于就绪状 态的进程占用处理机。在确定了占用处理机的进 程后，系统必须进行进程上下文切换以建立与占 用处理机进程相适应的执行环境。n(4) 线程调度。分级调度4.2 作业调度n作业调度从后备状态到执行状态的转变从执行状态到完成状态的转变周转时间： 作业i的周转时间Ti为 Ti=Tei-Tsi 其中Tei为作业i的完成时间，Tsi为作业的提交时间。 对于被测定作业流所含有的n（n=1）个作业来说， 其平均周转时间为：一个作业的周转时间说明了该作业在系统内停留的时 间，包含两部分：等待时间、执行时间，即： Ti=TwiTri Twi指作业i由后备状态到执行状态的等待时间
4、，它不 包括作业进入执行状态后的等待时间。带权周转时间 带权周转时间是作业周转时间与作业执行时间的比：Wi=Ti/Tri对于被测定作业流所含有的几个作业来说，其平均带 权周转时间为：4.3 进程调度进程上下文切换n进程上下文正文段数据段硬件寄存器的内容n存放CPU将要执行的下条指令地址的程序计数器PCn处理机状态寄存器PSn存放过程调用（或系统调用）时所传递参数的通用寄 存器R以及堆栈指针寄存器S等有关数据结构nPCB等在内的所有与执行该进程有关的管理和控制用 表格、数组、链等n进程上下文切换，包括4个步骤：(1)决定是否做上下文切换以及是否允许做上下 文切换。n包括对进程调度原因的检查分析，
5、以及当前执行进程 的资格和CPU执行方式的检查等。(2) 保存当前执行进程的上下文。 (3) 使用某种进程调度算法，选择一个处于就绪 状态进程。(4) 恢复或装配所选进程的上下文，将CPU控制 权交给所选进程。4.4 调度算法n进程调度n作业调度1. 先来先服务调度算法 （FCFS First Come First Serve）n思想：将用户作业或就绪进程按提交顺序或变为就绪状态 的顺序排成队列，并按照先进先出的方式进行调度 处理，是一种最简单的方法。n特点:(1)实现简单(2)适于作业调度、进程调度(3)公平?n对执行时间较短的作业或进程来说，等待时间可能较长例1: 如果作业队列依次(几乎同
6、时)到达如下3个作业，按“先来 先服务”的方式进行调度完成后，计算平均等待时间：作业需运行时间 J150 J210 J31运行情况：0506061平均等待时间=（0+50+60）/336.67如果到达顺序为J3、J2、J1，运行情况：011161平均等待时间=（0+1+11）/3=4J1J2J 3J3J2J1例2: 在单道环境下，某批处理显然有四道作业，已知 他们的进入系统的时刻、估计运算时间如下：作业进入时刻(h)运行时间(h)12348.008.509.009.502.000.500.100.20用FCFS算法计算作业的运行情况、平均周转时间和 平均带权周转时间作业进入时刻运行时间开始时刻
7、完成时刻 周转时间带权周转12348.008.509.009.502.000.500.100.208.00 10.0010.50 10.6010.0010.5010.6010.802.002.001.601.301.004.0016.006.50 平均周转时间T1.725（h） 平均带权周转时间T6.875（h）2. 轮转调度算法（Round Robin）n思想：将CPU的处理时间分成固定大小的时间片T。如果一个进程在被调度选中之后用完了系统规定的 时间片，但未完成要求的任务，则它自行释放自己 所占有的CPU而排到就绪队列的末尾，等待下一次 调度。进程调度程序调度当前就绪队列中的第一个进程。n
8、特点：（1）该算法适于进程调度，一般不适于作业调度 （为什么？）n轮转法一般只能分配那些可抢占资源，将他们随时抢占 再分配给其他进程，cpu是可抢占资源的一种，但打印 机等为不可抢占资源，由于作业掉队是对除了cpu之外 的所有系统硬件资源的分配，其中包含有不可抢占的资 源，所以作业调度不使用轮转法。（2）适应系统：分时系统（3）时间片长度的取值 固定时间片 时间片长度：几十毫秒几百毫秒(例如 50ms) 过长：响应速度慢 算法会退化为FCFS； 过短：进程切换过于频繁系统开销(overhead)大。 可变时间片 设系统对响应时间的要求是R，就绪队列中最大进程数为Nmax。因为 R |T|*Nm
9、ax所以 |T| R/Nmax一种可行的办法是，每当一轮调度开始时，系统便根据就绪队列中已 有进程数目计算一次T值，作为新一轮调度的时间片。这种方法得到的 时间片值随就绪队列中的进程数变化。3. 最短作业优先调度算法(SJF Shortest Job First)n思想：选择那些估计需要执行时间最短的作业投入执行。n例：如果作业队列依次(几乎同时)到达如下3个作业, 按最短作业优先法（SJF）调度。作业需运行时间 J150 J210 J31011161平均等待时间=（0+1+11）/3=4J3J2J1优点:（1）可使得系统在单位时间内处理的作业 个数最多吞吐量最大。（2）对同一批作业而言，该算
10、法使得作业 的平均等待时间最短。缺点：可能使得某些运行时间较长的作业得不到 调度执行的机会。两种调度方式： （1）非剥夺方式（2）剥夺方式，即最短剩余时间优先Shortest- Remaining-Time First (SRTF)。最短剩余时间：从作业当前运行到完成所需时间 。最短剩余时间优先调度是抢占算法。该算法允许比当前进程剩余时间更短的进程来抢 占 非剥夺方式示例：Process Arrival Time Burst Time P10.07P22.04P34.01P45.04n平均等待时间 = (0 + 6 + 3 + 7)/4 = 4P1P3P273160P4812剥夺方式示例：Pr
11、ocess Arrival Time Burst Time P10.07P22.04P34.01P45.04n平均等待时间 = (9 + 1 + 0 +2)/4 = 3P1P3P242110P457P2P1164. 最高响应比优先调度算法 （HRN：Highest Response ratio Next）n思想：响应比R定义如下：R=(W+T)/T=1+W/TnT为该作业估计需要的执行时间nW为作业的等待时间每当要进行作业调度时，系统计算每个作业的响应 比，选择其中R最大者投入执行。n特点：介于FCFS和SJF 之间的一种折中算法由于每次调度前要计算响应比，系统开销也要相应 增加R=(W+T)
12、/T=1+W/T 例子：作业到达时间需运行时间开始时 间完成时间等待时间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思想：系统或用户按某种原则为作业或进程指定一个优先 级，系统按优先级进行调度。n特点：可被用于作业或进程的调度n注意：(1)优先级的确定n静态法：在作业或进程开始
13、执行之前就确定它们的优先 级，一旦开始执行之后就不能改变。n动态法：随着作业或进程的执行，其优先级不断变化。(2)影响优先级因素n外因：任务的紧迫程度、付费、进程类型(系统、用户进 程)。例如，在操作系统中，对于键盘中断的处理优先级 和对于电源掉电中断的处理优先级是不相同的。n内因：作业类型（IO型、计算型）、资源需求(3)剥夺/非剥夺优先级调度n非剥夺方式：获得处理机的进程，直至终止、等待n剥夺方式：获得处理机的进程，直至终止、等待、出现 高优先级的就绪进程nUNIX：可剥夺、动态优先级调度6.多级队列算法（MLQ：Multilevel Queue） 思想：多个就绪队列，进程所属的队列固定。不同就 绪队列具有不同优先级；各个队列拥有自己的调度算 法；处理机要在不同队列中调度。 例如：某通用系统队列1：实时进程就绪队列（HPF）队列2：分时进程就绪队列（RR）队列3：批处理进程就绪队列（HPF）
