《四章处理机调度.ppt》由会员分享，可在线阅读，更多相关《四章处理机调度.ppt（49页珍藏版）》请在三一办公上搜索。
1、第四章 处理机调度,4.1 作业的概念及其状态4.2 作业调度4.3 进程调度4.4 调度算法,4.1.1 作业与作业步,作业:就是要求计算机给以计算(或处理)的一个相对独立的任务.也是一个相对独立的计算任务在计算机上的执行过程,作业步:是一个作业在执行过程中,从逻辑上可以细分成一个一个 顺序处理的基本单位.这个基本单位称为作业步.,典型的作业控制过程：“编译”、“连接装配”、“运行”。,4.1 作业的概念及其状态,.典型的作业步,在作业执行过程中，各个作业之间联系密切，上一作业步的执行结果作为下一步的执行前提。,作业、作业步与进程之间的关系,用户,作业,作业,作业步,作业步,.,作业,进程,
2、进程,.,4.1.2 作业控制方式,作业的类型与组织形式,脱机作业：,是指用户不能和计算机直接交互需要通过操作员从中干预的作业,联机作业：,是用户通过外围设备直接与计算机系统进行交互，并且控制作业的运行，这种作业也叫交互型作业。,联机作业多出现在分时系统中，而脱机作业经常出现在批处理系统中。,作业的组成：,程序、数据和作业说明书,作业说明书：,作业基本情况描述作业控制描述作业资源要求描述,作业说明书是用户用作业控制语言编写的。,4.1.3 作业的状态,作业在整个活动期间经历的四种状态是：,提交状态：把一个作业输入到计算机中的一个过程。后备状态：作业在磁盘上的后备队列中所处的状态。执行状态：把处
3、于后备状态的作业调入内存的状态。完成状态：一个作业的主进程执行结果时所处的状态。,提交状态,后备状态,完成状态,运行状态,运行,就绪,等待,作业调度,Spooling,作业的状态及转换,4.1.4 作业控制块（JCB),作业控制块（JCB：Job Control Block）用以标识作业的存在，记录了与该作业有关的信息，其具 体内容根据作业调度的要求而定。对于不同的系统，JCB 的内容有所不同。,作业控制块,占用CPU的时间,作业提交之后，有一定的调度策略，总得在一定的时间内完成。,程序执行时需要,为作业调度提供一定的调度依据,脱机还是联机的,长作业还是短作业I/O型还是计算型,和资源要求配合
4、使用,作业调度对一个作业而言只使用一次进程调度对一个进程而言可能使用多次。,注意：,4.2.1 作业调度的功能,4.2 作业调度,作业调度：作业管理程序按一定策略从后备作业中挑选一个作业，把它装入内存并且为它们分配必要的资源，并为作业创 建一个主进程以便它能够执行。,作业调度的功能：,通过调度算法从后备队列中挑选一个作业投入运行为选中的作业做好运行前的准备工作。在作业结束时做好善后工作（回收资源）,作业调度的作用：,完成作业从后备状态到执行状态和从执行态到完成状态的转换,作业从后备态到执行状态,算法1：,BEGIN 从后备队列中选出一个作业;While(资源要求不满足）放弃该作业;If（后备作
5、业队列为空）EXIT 按调度算法从后备队列中挑出一个作业；调用存储管理，设备管理程序看是否满足资源要求；分配资源；调用进程管理程序建立进程；进程调度；END,作业从执行状态到完成状态,算法2：,BEGIN 回收分给该作业各个进程的全部资源；计算该作业的执行时间；撤销所有进程及作业的JCB;转入调用下一个作业；END,4.2.2 衡量调度性能的指标,1、调度算法应达到的目标,每次运行尽可能多的作业让处理机保持忙碌状态使输入输出设备得以充分利用对所有的作业公平合理,吞吐量,利用率问题,公平性原则,2、确定调度算法时应考虑的因素,调度算法应与系统的总体设计目标一致注意系统资源的均衡使用，使输入输出繁
6、忙的作业与CPU繁忙的作业搭配运行应保证进入系统的作业在规定的截至时间内运行结束,3、调度算法性能的衡量,批处理系统中衡量作业调度算法性能的两个指标：,平均周转时间和平均带权周转时间,（1）周转时间：,i作业的周转时间定义为：,Ti=Tsi-Tti,其中：Tsi为i作业完成时间，Tti为作业的提交时间。,平均周转时间：,T=,1,n,i=1,n,Ti,一个作业的周转时间可分为2部分：,（1）等待时间（从后备态到执行态）；（2）执行时间,可以表示为：,Ti=Twi+Tri,（2）带权周转时间：,i=,其中：Ti是作业周转时间,Tri是作业执行时间,Ti,Tri,平均带权周转时间：,n,i=1,1
7、,n,W=,i,4.2.3 作业调度算法,1、先来先服务调度算法：,严格按照作业先来后到的次序进行调度。,例：,有四个作业，它们的提交、执行时间如下,2、短作业优先调度算法：,选取执行时间最短的作业作为下次服务的对象,例：,有四个作业，它们的提交、执行时间如下,3、响应比高者优先调度算法：,介于(FCFS)和短作业优先调度算法(SJF)之间的算法,是对二者的折中,响应比=,(等待时间+执行时间),执行时间,=,1+,等待时间,执行时间,例：,有四个作业，它们的提交、执行时间下表,如采用响应比高者优先调度算法(HRN)来计算平均周转时间和平均带权周转时间(其中时间单位为小时,按十进制计算.,r2
8、=1+(10.0-8.3)/0.5=4.4,r3=1+(10.0-8.5)/0.1=16,r4=1+(10.0-9.0)/0.4=3.75,此时,各作业的响应比为:,r2=1+(10.1-8.3)/0.5=4.6,r4=1+(10.1-9.0)/0.4=3.75,此时,各作业的响应比为:,r4=1+(10.6-9.0)/0.4=5,此时,各作业的响应比为:,平均周转时间为(2.0+1.6+2.3+2.0)/5=1.975,4、优先数调度算法：,可以综合考虑有关因素,如作业缓急程序,作业长短,等待时间的长短,外部设备,使用情况等,并根据系统设计目标分析这些因素的重要程度,按比例确定各作业的优先数
9、,系统按优先数高来调度作业.,例：,在后备作业队列中等待运行的同时有3个作业1、2、3，已知它们的各自运行时间为a、b、c，且a b c.,证明：采用短作业优先调度算法能获得最小平均周转时间,证明：采用短作业优先调度算法,因此作业执行顺序为：123。作业1执 行时间为a,等待时间为0.作业2执行时间为b,等待时间为a.作业3执 行时间为c,等待时间为(a+b).因此：3个作业总的周转时间 T1=(a+(a+b)+(a+b+c)=3a+2b+c,不失一般性，假设调度顺序为213，则其总的周转时间为 T2=b+(b+a)+(b+a+c)=3b+2a+c,T2-T1=(3b+2a+c)-(3a+2b
10、+c)=(b-a)0,例：,有一个具有2道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用高优先级优先的抢占式调度算法。在下表所示的作业序列作业优先数即为进程优先数，优先数越小，优先级越高。,列出所有作业进入内存时间及结束时间计算平均周转时间,各作业的周转时间为：,作业A：20（执行）30（内存内等待）20（执行）70作业B：30（执行）作业C：20（内存外等待B执行）20（内存外等待A执行）50（执行）90作业D：20（内存为等待A执行）50（内存内等待C执行）20（执行）90,作业的平均周转时间为：（70309090）/470（分钟）,例：,在某多道程序系统中，供用户使用的
11、内存空间为100K,磁带机2台，打印机1台。系统采用可变式分区分配方式管理内存，对磁带机和打印机采用静态分配方式，并假设输入、输出操作的时间忽略不计。现有一作业序列如下表所示。,写出作业调度选中的作业调度次序如果把一个作业的周转时间定义为到达系统至计算完成的时间，则最大和最小的作业周转时间是多少？作业全部执行结束的时间是多少？,假设作业调度采用先来先服务算法，优先分配内存的低地址区域且不准移动已在内存中的作业，在内存中的作业平分CPU时间，问：,8：00时，作业1到达。,作业1,0,15K,100K-1,8：00内存分配情况,剩余资源：1台磁带机,8：20时，作业3到达。,作业1,0,15K,
12、100K-1,8：20内存分配情况,剩余资源：无,8：20时，作业2到达。申请的资源打印机被作业1占用，作业2等待,作业3,75K,8：30时，作业1运行完毕。,0,15K,100K-1,8：30内存分配情况,剩余资源：无,作业3,75K,作业2等待。,8：30时，作业4到达。而作业2的内存资源不满足，继续等待。,0,15K,100K-1,8：30内存分配情况,作业3,75K,作业4,95K,8：35时，作业5到达。而作业2的内存资源不满足，继续等待。同时作业5要求的磁带机资源不满足，作业5等待。,9：00时，作业3运行完毕，释放占用的资源和内存。,0,100K-1,9：00内存分配情况,75
13、K,作业4,95K,9：00时，根据先来先服务调度算法，由于资源都能得到满足，选中等待作业中的作业2进入内存。作业5继续等待,0,100K-1,9：00内存分配情况,75K,作业4,95K,作业2,30K,9：10时，作业4运行完毕。作业5申请的打印机资源被作业2占用，作业5继续等待。,0,100K-1,9：10分内存分配情况,75K,95K,作业2,30K,9：15时，作业2运行完毕。作业5申请的所有资源可用，作业5进入内存执行至9：30结束。,作业选中的次序：13425,作业1的周转时间：8:308:0030 作业2的周转时间：9:158:2055 作业3的周转时间：9:008:2040
14、作业4的周转时间：9:108:3040 作业1的周转时间：9:308:3555,作业全部执行完毕的时间：9：30,在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。,进程调度要解决的问题,WHAT：按什么原则分配CPU 进程调度算法WHEN：何时分配CPU 进程调度的时机HOW：如何分配CPU CPU调度过程（进程的上下文切换）,4.3 进程调度,1、进程调度的任务,2、确定调度算法的原则,具有公平性。资源利用率高（特别是CPU的利
15、用率）。在交互式系统情况下要追求响应时间越短越好。在批处理系统情况下要追求系统吞吐量。,就是控制协调进程对CPU的竞争即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。,3、进程调度算法,先进先出(FIFO)算法最高优先权优先调度算法时间片轮转算法 多级反馈队列 调度算法,1）.先进先出(FIFO)算法,该算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便执行下去，直到该进程完成或阻塞时，才释放处理机。优点:实现简单.缺点:没考虑进程的优先级,2）.基于优先数的调度算法（HPF):,确定优先数的方法：,静态优先数法：在进程创建时指定优先数，在进
16、程运行时优先数不变。动态优先数法：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。,优先选择就绪队列中优先级最高的进程投入运行。,占用CPU的方式,非剥夺方式：分派程序一旦把处理机分配给某进程后便让它 一直运行下去，直到进程完成或发生某事件而 阻塞时，才把处理机分配给另一个进程。剥夺方式：当一个进程正在运行时，系统可以基于某种原 则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。,3）、时间片轮转调度算法:,时间片选择问题：,固定时间片可变时间片,与时间片大小有关的因素,系统响应时间就绪进程个数CPU能力,把CPU划分成若干个时
17、间片，并且按顺序赋给就绪队列中的 每个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列未尾，同时系统选择另一进程运行。,4）、多级反馈队列调度算法：,首先系统中设置多个就绪队列每个就绪队列分配给不同时间片，优先级高的为第一队列，时间片最小，随着队列级别的降低，时间片加大。各个队列按照先进先出调度算法一个新进程就绪后进入第一级队列进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，者进入到一级队列中去。当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列未尾。当第一级队列为空时，就去调度第二级队列，如
18、此类推。当时间片到时，进程放弃CPU，回到下一级队列。,将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小。最后一级采用时间片轮转，其他队列采用先进先出；系统从第一级调度，当第一级为空时，系统转向第二个队列,当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列。,时间片,小,大,优先级,高,低,运行,等待,1级,2级,3级,假设：,1级队列中无进程,选择优先级最大的进程资源得不到满足等待（等待某个事件）时间片用尽有更高优先级进入处于等待状态进程进入就绪态时，排在第1级队列中
19、,特点：,采用短作业优先的办法,照顾了I/O型的作业,照顾了长作业,例1：,假设有一台计算机，它有1M内存，操作系统占用200K,每个用户进程也占用200K，用户进程等待I/O的时间为80，若增加1M内存，则CPU的利用率将提高多少？,例2：,假设就绪队列中有10个进程，系统将时间片设为200ms,CPU进行进程切换要花费10ms,问：系统开销所占的比率为多少？,进程调度的时机,当一个进程运行完毕，或由于某种错误而终止运行。当一个进程在运行中处于等待状态（等待I/O).分时系统中时间片到。当有一个优先级更高的进程就绪（可抢占式）在进程通信中，执行中的进程执行了某种原语操作。,进程的切换,进程切
20、换：一个进程让出处理器，由另一个进程占用处理器的过程。进程的切换使系统中的各进程均有机会占用CPU.进程的切换是由进程状态的变化引起的，而进程状态的变化又与出现中断有关。当有中断事件发生时，当前运行的进程被中断，中断响应后由OS处理出现的中断事件。中断处理后，某些进程的状态会发生变化，也可能又创建了一些新的进程。因此，要进行队列的调整。然后，进程调度根据预定的调度算法从就绪队列选一个进程占用CPU。这个占用CPU运行的进程可能仍是被中断的进程，也可能是另一个进程。,何时切换进程,只要OS取得对CPU的控制，进程切换就可能发生，如:超级用户调用来自程序的显式请求(如：打开文件)，该进程通常会被阻
21、塞陷阱最末一条指令导致出错，会引起进程移至退出状态中断 外部因素影响当前指令的执行，控制被转移至IH（中断处理程序）,CPU调度过程,保存现场：(保护程序执行的顺序）顺序保存，最后一步保存PSW。选择要运行的程序：如果没有就绪进程，系统会安排一个IDLE进程，没有其他进程时，该进程一直运行，在执行过程中可接受中断。恢复现场：最后一步恢复选中进程的PSW.,进程（上下文）切换的步骤,保存处理器的上下文，包括程序计数器和其他寄存器。用新状态和其他相关信息更新正在运行进程的PCB.把原来的进程移到合适的队列就绪、阻塞。选择另一个要执行的进程。更新被选中进程的PCB.从被选中进程中重装入CPU上下文。,
