处理机调度-(2)课件

操作系统

OperatingSystem北方工业大学计算机系NorthChinaUniversityofTechnologyDepartmentofComputer授课教师：宋丽华Email：slh2g@126.comTel:88803939五教1102为什么要管理处理机?★处理机是计算机中最宝贵的资源，处理机调度策略是否合适直接影响着计算机的性能。★在批处理系统用户一旦将作业提交就失去了对作业的控制，用户希望系统的周转时间尽量短。交互式系统中用户以交互方式工作，好象整个计算机都为一个用户工作，这时希望系统的响应时间快。★由此可以看出，不同的操作系统类型和用户要求，处理机的管理策略应该有所不同。衡量调度策略的指标★周转时间——一个作业从投入计算机到结束所使用的时间。★吞吐量——在给定的时间内，一个计算机系统所完成的总的工作量。★响应时间——从用户向计算机发出指令到计算机将结果返回给用户需要的时间。★设备利用率——主要指输入输出设备的使用情况。--小--大--短--高第四章处理机调度4.1分级调度4.2作业调度4.3进程调度4.4调度算法4.1分级调度★操作系统中一个程序运行相关的概念：作业、进程、线程。它们是程序在计算机中不同运行阶段的不同体现，为此应该有不同的调度程序。程序的各种状态及相应的调度方式4.1分级调度★处理机调度分四个级别进程调度（低级）：按某种策略选择一个就绪进程占用处理机，在确定了占用处理机的进程后，必须进行进程上下文切换，以便为运行进程准备好执行环境。线程调度（微级）：负责各个线程的调度。第四章处理机调度4.1分级调度4.2作业调度4.3进程调度4.4调度算法4.2作业调度作业调度程序的功能作业调度程序的目标和性能衡量4.2.1作业调度程序的功能★记录已经进入系统的各个作业的情况。作业调度要记录作业进入系统时的一些信息，并跟踪作业在运行中的状态变化情况。这些信息记录在作业控制块JCB，它建立和撤消都是由作业调度程序完成的。★选择作业。从输入井中选择符合“条件”的作业送到内存的作业缓冲区中，使这些作业的状态由“后备”状态变为“运行”状态。4.2.1作业调度程序的功能

★为被选中的作业做执行前的准备。建立进程，分配作业运行需要的资源，如内存和外部设备。作业调度程序只能保证该作业具有使用处理机的资格，而不能分配处理机资源。

★作业运行结束后的善后处理和资源回收。统计作业的运行时间，作业执行状态等信息的输出。撤消该作业的所有进程和该作业的JCB。作业调度程序的处理流程例题当作业进入完成状态，操作系统（）A将删除该作业并收回其所占资源，同时输出结果；B收回其所占资源，输出结果，并将该作业的控制块从当前作业队列中删除；C将收回该作业所占资源并输出结果；D将输出结果并删除内存中的作业。B4.2.2作业调度算法的目标和性能衡量★调度目标：1）对所有的作业应该是公平合理的。2）应使设备有较高的利用率。3）单位时间内执行尽可能多的作业。4）有快的响应时间。★由于这些目标的相互冲突，任一调度算法要想同时满足上述目标是不可能的。★周转时间=作业完成时间–作业提交时间。 Ti=Tei–Tsi★平均周转时间：

注意：★一个作业的周转时间说明了它在系统内部停留的时间，应该包括两部分：等待时间和执行时间。 Ti=Twi+Tri

★Twi：是作业由后备状态到执行状态的等待时间，不包括作业进入执行状态后的等待时间。★Tri：是作业在执行状态的时间。4.2.2作业调度算法的目标和性能衡量

★带权周转时间=作业的周转时间 作业执行时间★如果有多个作业同时进入系统，则平均带权周转时间：4.2.2作业调度算法的目标和性能衡量★一般来说，作业的平均周转时间短，说明作业在系统的时间短，用户等待的时间短，系统的利用率高，所以，应该选择平均周转时间短的作业调度算法。Wi=Ti/Tri第四章处理机调度4.1分级调度4.2作业调度4.3进程调度4.4调度算法4.3进程调度进程调度程序的功能进程调度的时机进程调度性能评价4.3.1进程调度程序的功能1）记录和保持系统中所有进程的有关情况和状态特征：由进程调度模块管理PCB表的内容，记录进程状态。2）选择占用处理机的进程：在处理机空闲时，根据一定的原则选择一个进程来运行。3）进行进程上下文切换：上下文切换时首先检查是否可以做切换，然后保存被切换进程的上下文，由调度程序选择一个进程，装载该进程的上下文，控制转向该进程，从刚恢复的程序计数器所指示的指令地址开始执行。4.3.2进程调度的时机★引起进程调度的原因有以下7类：一个进程完成其任务时。执行中的进程自己调用阻塞原语，进入等待状态。执行了一次P操作，资源不满足；执行V操作激活了等待队列的进程。执行的进程提出I/O请求后被阻塞。在分时系统中时间片已经用完。执行完系统调用，系统返回用户态之前，由于系统进程结束，需求调度新的进程。在采用可剥夺调度方式的系统中，当具有更高优先级的进程要求处理机时。【13年考研28题】

下列选项中，会导致用户进程从用户态切换到内核态的操作是()I.整数除以零II.sin()函数调用III.read系统调用A.仅I、IIB.仅I、IIIC.仅II、IIID.I、II和IIIB4.3.2进程调度的时机★可剥夺方式：在就绪队列中一旦有优先级高于当前执行进程的进程存在便立即发生进程调度，转让处理机。★而不可剥夺方式即使在就绪队列存在有优先级高于当前执行进程时，当前进程仍将继续占有处理机，直到该进程自己因调用原语操作或等待I/O而进入阻塞状态，或时间片用完时才重新发生调度让出处理机。4.3.3进程调度性能评价★进程调度策略的好坏直接影响作业调度的性能。★作业调度性能评价周转时间平均周转时间带权周转时间平均带权周转时间4.3.3进程调度性能评价★进程调度性能评价定性调度的可靠性简洁性定量CPU的利用率进程在就绪队列中等待时间与执行时间之比…第四章处理机调度4.1分级调度4.2作业调度4.3进程调度4.4调度算法4.4调度算法先来先服务轮转法多级反馈轮转法优先级法最短作业优先法最高响应比优先法4.4调度算法思想：按作业和就绪进程到来的次序进行调度。这种算法优先考虑在系统中等待时间最长的作业，而不管它要求运行时间的长短。优点：算法简单，公平，容易实现缺点：对于短作业或短进程，等待时间长★作业调度算法—FCFS（Firstcomefirstserve）4.4调度算法★作业调度算法—FCFS下面是4个作业在系统中从提交、运行的信息。作业提交时间运行时间开始时间完成时间周转时间带权周转时间18228.50.5390.149.50.2平均周转时间：T=1.725平均带权周转时间W=6.87581010.510.61010.510.610.8221.61.314166.54.4调度算法思想：比较作业缓冲区中的作业预计的运行时间，选择预计时间最短的作业进入运行状态。优点：算法简单，可得到最大系统吞吐率，效率高。缺点：主要问题是对长作业不利，如果系统不断地接收短作业，就会使长作业长时间等待。★短作业优先算法—SJF（shortestjobfirst）4.4调度算法★短作业优先算法—SJF作业提交时间运行时间开始时间完成时间周转时间带权周转时间18228.50.5390.149.50.2平均周转时间：T=1.55平均带权周转时间W=5.15810.31010.11010.810.110.322.31.10.814.61144.4调度算法响应比=响应时间/预计执行时间响应时间=等待时间+预计执行时间所以响应比为：1+作业等待时间/预计执行时间思想：当需要从就绪队列中选择进程投入运行时，先计算每个进程的响应比，选择响应比最高的进程运行优点：短作业响应比高，执行时间短；长作业响应比随着等待时间增加而提高，不会过长等待。既照顾了短作业、也考虑到了长作业。缺点：每次调度前计算响应比增加了系统开销。★最高响应比优先—HRN（highestresponse-rationext）4.4调度算法作业提交时间运行时间开始时间完成时间周转时间带权周转时间18228.50.5390.149.50.20平均周转时间：T=1.625W=5.675★最高响应比优先—HRN810.11010.61010.610.110.822.11.11.314.2116.54.4调度算法算法描述：根据分配给进程的优先数来决定运行进程。算法的核心：是确定进程或作业的优先级静态法：静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。动态法：动态优先权是指，在创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。★优先级法HPF（highestpriorityfirst）特点：静态优先级法简单，但缺点是公平性差，可能会造成优先级低的长期等待；动态优先级法资源利用率高，公平性好，缺点是系统开销较大，实现复杂。4.4调度算法静态法作业调度确定优先级原则由用户根据作业的紧急程度输入一个适当的优先级；由系统或操作员根据作业的类型确定；系统根据作业要求的资源确定优先级。进程调度确定优先级原则按照进程的类型确定；将作业的优先级作为它所属进程的优先级。★优先级法HPF（highestpriorityfirst）4.4调度算法动态法优先级确定原则根据进程占有CPU时间长短确定占用的时间越长，下次调度的优先级越低；占用的时间越短，下次调度的优先级越高。根据就绪进程等待CPU的时间长短确定等待时间越长，优先级越高；等待时间越短，优先级越低。★优先级法HPF（highestpriorityfirst）4.4调度算法算法描述：将CPU的处理时间分成固定大小的时间片。如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的CPU而排到就绪队列的末尾，等待下一次调度。★轮转法RR（roundrobin）优点：具有公平性；易于实现，算法简单；缺点：CPU存在较大额外开销，用于进程切换和调度。4.4调度算法时间片：时间片长度的选择会直接影响系统开销和响应时间。太长，则使每一个进程均能在一个时间片内完成，RR算法褪化成了FCFS；太短，导致频繁的时间片中断和调度，CPU额外开销大。★轮转法RR（roundrobin）计算表达式：q＝R/Nmaxq：时间片长度；R：系统对响应时间的要求Nmax：就绪队列要求的最大进程数量02134567891011121314151617t(a)q=1(a)q=4AAAABBBCCCCDDEEEEq=1和q=4的进程运行情况4.4调度算法★轮转法RR（roundrobin）作业情况时间片进程名ABCDE平均到达时间01234服务时间43424RRq=1完成时间151216917周转时8带权周转时间3.753.673.533.333.46RRq=4完成时间47111317周转时间46910138.4带权周转时间122.2553.332.54.4调度算法★轮转法RR（roundrobin）4.4调度算法算法描述：把就绪队列按照进程到达就绪队列的类型和进程被阻塞时的阻塞原因分成不同的就绪队列，每个队列按FCFS原则排列，各队列之间的进程享有不同的优先级，但同一队列内优先级相同。多级反馈轮转法与优先级法在原理上的区别是，一个进程在它执行结束之前，可能需要反复多次通过反馈循环执行，而不是优先级法中的一次执行。★多级反馈轮转法特点：复杂，实现困难；是FCFS，RR，HPF的综合应用。4.4调度算法设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。★多级反馈轮转法多级反馈队列调度算法就绪队列1就绪队列2就绪队列3就绪队列nS1S2S3至CPU至CPU至CPU