《操作系统课件4.ppt》由会员分享，可在线阅读，更多相关《操作系统课件4.ppt（52页珍藏版）》请在三一办公上搜索。
1、1,调度策略考虑：周转时间 吞吐率响应时间 设备利用率研究的内容有：作业与进程的关系 作业调度策略与算法进程调度策略与算法,本章主要讨论处理机分配问题,2,1.作业的状态及其转换提交状态：一个作业在其处于输入设备进入外部存储设备的过程称为提交状态后备状态（收容状态）：输入管理系统不断地将作业输入到外存对应部分（或称输入井），如果一个作业的全部信息已全部输入到输入井，在它还没有被调度去执行前，该作业处于后备状态。运行状态：作业一旦被作业调度程序选中而被送入主存中投入运行。完成状态：作业运行完毕，但它所占用的资源尚未被系统全部回收时，该作业处于完成状态,4.1 分级调度,3,作业状态及其转换图,s
2、pooling系统,提交,收容,交换调度,完成,作业调度,进程调度,外存,线程调度,内存,输入井,4,高级调度（作业调度、宏观调度）按一定原则对外存输入井上的作业进行调度，并建立进程PCB。它决定允许哪些作业竞争系统资源。由于这种调度决定哪些作业可以进入系统，所以也称收容调度。作业一旦被系统收容，就便成进程或进程组。所做的工作：1 选择作业；2 分配资源；3 建立作业的进程；4 建立有关的表格 5 作业的善后处理。,2调度的层次,5,中级调度（交换调度）它决定允许哪些进程竞争处理机。中级调度通过使进程临时挂起和激活的方法对系统负载波动作出反映，以便获得平稳的系统操作和实现较好的系统综合性能目标
3、，中级调度的作用使作为作业进入系统和将中央处理机分配给这些作业二者之间的一个缓冲。引入中级调度的目的是为了提高内存的利用率和系统吞吐量,调度的层次（续）,6,低级调度（进程调度）它决定了存在就绪进程时，哪一个就绪进程将分配到中央处理机，并且把中央处理机实际分配给这个进程（即低级调度是将处理机分配给进程）。低级调度是由每秒可操作许多次的处理机调度程序执行，处理机调度程序应常驻内存。进程调度的方式：非抢占方式，抢占方式。抢占的方式有：1 时间片原则；2 优先级原则；3 短进程优先原则,调度的层次（续）,7,作业是用户向计算机提交任务的任务实体。进程是计算机为了完成用户任务实体而设置的执行实体。显然
4、，计算机要完成一个任务实体，必须要有一个以上的执行实体，一个作业总是由一个以上的多个进程组成。,3作业与进程的关系,8,作业调度的功能：按某种算法从后备队列中挑选一个或一批作业调入内存.后备作业队列与作业控制块 系统中有若干作业在输入井中，为了管理和调度作业，就必须记录已进入系统的各作业的情况，系统为每个作业设置了一个作业控制块（JCB）。内容：作业名、作业状态、作业调度，以及资源申请和一些控制信息。,4.2 作业的调度,9,作业控制块JCB,作业控制块JCB,10,作业调度按照某种调度算法从后备作业队列中选取作业，使其进入内存运行。作业调度程序的主要功能是审查系统是否能满足用户作业的资源要求
5、以及按照一定的算法选取作业。,1作业调度及其功能,11,按照某种调度算法从后备作业队列中选取作业。为被选取的作业分配内存和外设资源（当系统为动态分配外设时，作业所申请的外设只作为调度的参考因素）。因此要用到内存分配程序和外设分配程序。为选中的作业建立相应的进程。为作业开始运行做好一切准备工作。如构造和读写作业运行时所需要的有关表格及建立负责其运行控制的作业运行控制程序。在作业运行完毕或运行过程中因某种原因需要撤离时，作业调度程序还有完成作业的善后处理工作，如收回分配给他的全部资源,2.作业调度应完成如下几方面的工作,12,（1）作业从后备状态到执行状态（2）作业从执行状态到完成状态,作业调度中
6、状态的转换过程,13,后备作业队列空,按调度算法从作业中选出一作业,调用存储、设备管理程序，审核资源要求,资源要求能满足？,放弃该作业,否,分配资源,调用进程管理程序建立进程,进程调度,否,是,出口,作业从后备状态到执行状态,是,14,撤销该作业的所有进程及作业的JCB,调用存储管理，设备管理回收分配给该作业的全部资源,调用会计程序，计算该作业的执行费用,调度下一个作业,作业从执行状态到完成状态,15,1)调度目标 对所有作业应该是公平合理 应使设备有高的利用率 每天执行尽可能多的作业 有快的响应时间,3.作业调度目标与性能衡量,16,2）.衡量一个作业调度算法是否满足系统设计的要求 给出两个
7、常用的评价在批处理系统中对作业调度算法优劣的性能量度1周转时间：作业i从提交时刻tsi到完成时刻tei称为作业的周转时间。Ti=Tei-Tsi 完成 提交,作业调度目标与性能衡量,17,作业平均周转时间为（有n个作业，n=1)nT=1/n Ti i=1一个作业的周转时间说明了该作业在系统内停留的时间包含两部分：一是等待时间；二为执行时间Ti=Twi+Tri(停留时间),作业调度目标与性能衡量,18,2带权周转时间Wi：Wi=Ti/Tri平均带权周转时间为：nW=1/n Wi i=1,作业调度目标与性能衡量,19,进程调度的功能：从就绪队列中挑选一个进程到处理机上运行。作业调度程序在挑选作业进入
8、主存运行时，要为该作业建立相应的进程。在作业完成后要撤销该作业的全部进程。一个进程被建立后，系统为了便于对进程的管理，将系统中的所有进程按其状态将其组织成不同的进程队列。,4.3进程调度,20,进程调度程序：负责进程调度功能的内核程序。作业调度与进程调度程序的区别：前者是挑选作业进主存运行、后者是挑选就绪进程到处理机上运行。进程调度的核心问题就是，采用什么算法把处理机分配给进程。,进程调度,21,进程调度,4.3.1进程调度的功能 1记录系统中所有进程的执行情况 2选择占有处理机的进程 3进行进程上下文的切换4.3.2进程调度的时机1 执行完毕 2 执行中的进程阻塞自己3 执行P原语被阻塞，执
9、行V原语唤醒4 提出I/O请求被阻塞 5 时间片用完6 执行系统调用,22,进程的上下文切换过程：用户态执行进程A代码进入OS核心（通过时钟中断或系统调用）保存进程A的上下文，恢复进程B的上下文（CPU寄存器和一些表格的当前指针）用户态执行进程B代码注：上下文切换之后，指令和数据快速缓存cache通常需要更新，执行速度降低,4.3.3进程上下文切换,23,（1）先来先服务（FCFS）调度算法 将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。它优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短。,4.4调度算法
10、,24,在单道环境下，某批处理有四道作业，已知他们的进入系统的时刻、估计运算时间如下：,用FCFS算法计算作业的运行情况、平均周转时间和平均带权周转时间,FCFS调度算法（续）,25,FCFS调度算法（续）,26,完成,D,C,B,A,CPU,进程调度算法,FCFS(先来先服务调度算法)最简单的调度原则是先进先出就绪队列,27,根据进程到达就绪队列的时间来分配中央处理机，一旦一个进程获得了中央处理机，就一直运行到结束，先来先服务是非剥夺调度。这种调度从形式上讲是公平的，但它使短作业要等待长作业的完成，重要的作业要等待不重要作业的完成。从这个意义上讲又是不公平的。先进先出调度使响应时间的变化较小
11、，因此它比其它大多数调度都可预测。由于这种调度方法不能保证良好的响应时间，在处理交互式用户时很少用这种方法。,FCFS(先来先服务调度算法),28,FCFS的特点,比较有利于长作业，而不利于短作业。有利于CPU繁忙的作业，而不利于I/O繁忙的作业。,29,在当今系统中，先进先出很少作为调度主模式，而是常常嵌套在其它的调度模式中。例如，许多调度模式根据优先级将处理机分配给进程，但具有相同优先级的进程却按先进先出进行分配。,FCFS(先来先服务调度算法),30,选择调度算法时应考虑的问题,进程调度的算法较多，在设计进程调度算法时应考虑的因素多，比如：尽量提高资源利用率，减少处理机的空闲时间，对于用
12、户作业要较合理的平均响应时间，以及尽可能地增强CPU的处理能力。,31,（2）.最短作业优先法（SJF）,该算法总是优先调度要求运行时间最短的作业,运行顺序 1 3 4 2,作业 进入时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转 1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.30 10.80 2.30 4.60 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,平均周转时间 T1.55h平均带权周转时间T5.15,32,SJF的特点,优点：比FCF
13、S改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量；缺点：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。,33,最高响应比作业优先算法是对FCFS方式和SJF方式的一种综合平衡响应比R定义：R1 W/T其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。,(3)最高响应比作业优先算法（HRN）,34,响应比R不仅是要求运行时间的函数，而且还是等待时间的函数。由于R与要求运行时间成反比，故对短作业是有利的，另一方面，因R与等待时间成正比，故长作业随着其等待时间的增长
14、，也可获得较高的响应比。这就克服了短作业优先算法的缺点，既照顾了先来者，又优待了短作业，是上述两种算法的一种较好的折中。,最高响应比作业优先算法（HRN）,35,最高响应比作业优先算法（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 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.675,36,开始只有
15、作业1，被选中执行时间2；作业1执行完毕，作业2、作业3、作业4响应比依次为:R2=1+(10-8.5)/0.5=4 R3=1+(10-9.00)/0.1=11 R4=1+(10-9.5)/0.2=3.5 作业3被选中，执行时间0.1；,37,作业3执行完毕，响应比依次为:R2=1+(10.10-8.5)/0.5=4.5R4=1+(10.10-9.5)/0.2=4作业2被选中，执行时间0.5；作业2执行完毕，作业4被选中，执行时间0.2,38,时间片轮转法主要用于进程调度。采用此算法的系统，其进程就绪队列往往按进程到达的时间来排序。进程调度程序总是选择就绪队列中的第一个进程，也就是说按照先来先
16、服务原则调度，但一旦进程占用处理机则仅使用一个时间片。在使用完一个时间片后，进程还没有完成其运行，它必须释放出处理机给下一个就绪的进程，而被抢占的进程返回到就绪队列的末尾重新排队等待再次运行。,(4)轮转法（Round Robin）,39,图 轮转法调度,40,时间片轮转策略特别适合于分时系统中使用，当多个进程驻留在主存中时，在进程间转接处理机的开销一般是不大的。在轮转法中，时间片长度的选取非常重要，时间片长度的选择会直接影响系统开销和响应时间，如果时间片长度过短，则调度程序剥夺处理机的次数增多，这将使进程上下文交换次数也大大增加，加重了系统开销。如果时间片长度选择过长（大）。大到一个进程足以
17、完成其全部运行工作所需的时间，那么时间片轮转法就退化为先来先服务策略了。最佳的时间片量值应能使分时用户得到好的响应时间,轮转法（RR）,41,这个最佳的时间片值是多少呢？显然，它将随系统而异。随负载而异，同时也随进程而异。时间片的选取是实现各种调度算法的关键之处，而时间片的额定通常应考虑终端数目，处理机能力、各终端任务的急迫程度、外存传输速度等方面的因素。时间片轮转法亦可应用于批处理系统的处理机调度。,轮转法（RR）,42,时间片 SR/Nmax R响应时间 Nmax最大进程数 每当一轮调度开始时，系统便根据就绪队列中已有进程数目计算一次值。作为新一轮调度的时间片。这种方法得到的时间片是随就绪
18、队列中的进程数变化的。,轮转法（RR）,43,（5）优先级调度算法,一种常用的进程调度算法是把处理机分配给具有最高优先级的进程（用于实时系统）在这种算法中，首先考虑的问题是如何确定进程的优先级。一种是静态优先级，另一种是动态优先级。1)静态优先级 静态优先级是在系统创建时确定的，一经确定之后在整个进程运行期间不再改变，确定静态优先级的有关静特性是：紧急程度、运行的时间长短、类型、要求的资源等。在有的系统中，分配给作业的优先级还取决于它所占用的内存的多少，运行时间长短，作业越大，占用内存越多，运行时间越长，分配给它的优先级越低。显然，不论是根据作业的执行时间，还是根据作业的大小所确定的优先级，都
19、有利于短作业。,44,作业要求的资源,根据作业要求系统提供的处理机时间，内存的大小和I/O设备的数量，来确定作业的优先级，如果系统赋予作业的优先级反比于系统的估计执行时间，就形成短作业优先的算法。由于作业需要的执行时间事先难于确定，只是把用户自报的估计时间作为依据，为防止用户少报自己的作业时间以获得优先服务，在采用短作业优先算法时，应采取适当的防备措施。,45,进程类型,系统中有两类进程，系统进程和用户进程。系统进程的优先级比用户进程的优先级高，特别是某些系统进程，必须赋予它一种特权，当它需要处理机时，应尽快的到满足。例如，设备管理器中的I/O进程便是如此。这不仅是为了保证I/O设备尽可能忙碌
20、，一提高设备利用率，更主要的是为了避免由于响应不及时，将造成信息的丢失。在用户进程中，I/O繁忙的进程应优先于CPU繁忙的进程，以保证CPU和I/O设备之间的并行操作。在分时系统中，前台进程应优先于后台进程。,46,2)动态优先级 虽然基于静态优先级的调度算法比较简单，但毕竟不够精确。因为进程的优先级在它执行前就已算好，且在整个执行期间都保持不变，但随着进程的推进，计算优先级所依赖的特征很多都将随之改变，因此静态优先级并非自始至终都能准确地反映出这些特性，如果能在进程运行中，不断的随着特性的改变而修改其优先级，显然可以实现更多精确的调度，从而获得更好的调度性能，这对分时系统显得格外重要.,47
21、,就绪进程队列分成两个：新创建进程队列：按FCFS方式排成；进程优先级按速率a增加；P=a*t(a0)享受服务队列：已得到过时间片服务的进程按FCFS方式排成；进程优先级按速率b增加；P=b*t(ab0)新创建进程等待时间的确定：当新创建进程优先级与享受服务队列中最后一个进程优先级相同时，转入享受服务进程队列；另外，当享受服务进程队列为空时，新创建进程队列的头一个进程也将转入享受服务进程队列。,线性优先调度（Selfish Round Robin）,SRR算法的优先级变化,49,2.SRR算法与FCFS算法和时间片轮转算法的关系,当ba0时，两个不同队列中的就绪态进程的优先级将永远不会相等，享
22、受服务队列中永远只有一个进程；SRR算法退化成FCFS算法；当ab=0时，SRR算法就是时间片轮转算法；SRR界于FCFS和RR,50,（6）多级反馈队列,多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。优点：为提高系统吞吐量和缩短平均周转时间而照顾短进程为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程不必估计进程的执行时间，动态调节,设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按时间片轮转算法调度直到完成。仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。,1.多级反馈队列算法,52,2.几点说明,不同进程的时间片不同。简单轮转法中时间片对每个进程相同。实际上不同进程对时间片的长度要求是不同的。I/O型进程往往用不满时间片，因此时间片可以短一些。计算型进程则要求时间片长一些，减少调度次数。进程采用动态优先级。优先级与时间片是结合在一起的：优先级越高，时间片越短；优先级越低，时间片越长。,
