《处理机调度》课件.ppt

《《处理机调度》课件.ppt》由会员分享，可在线阅读，更多相关《《处理机调度》课件.ppt（57页珍藏版）》请在三一办公上搜索。

1、第三章 处理机调度(CPU调度),无论在多道批处理系统还是分时系统中,系统中的用户进程数都远远超过处理机数,除用户进程要占用处理机外,操作系统还要建立若干个系统进程完成系统功能。这么多的进程竞争处理机,就要求系统提供进程调度功能,以便采用一些策略,将处理机动态地分配给系统中的各个就绪进程,使之执行。分配处理机的任务是由处理机调度程序完成的;处理机是计算机最重要的资源,如何提高处理机的利用率及改善系统性能,在很大程度上取决于处理机调度性能的好坏,处理机调度成为操作系统设计中心工作。,要解决的问题WHAT：按什么原则分配CPU 进程调度算法WHEN：何时分配CPU 进程调度的时机HOW：如何分配C

2、PU CPU调度过程（进程的上下文切换）,一批作业从进入系统到作业运行完毕可能经历三级调度高级、低级和中级调度。一.高级调度(High Scheduling)又称为作业调度接纳调度或长程调度,用于批处理系统,确定将外存后备队列中哪些作业调入内存,并为它们创建进程。实时系统和分时系统的前台作业不需要作业调度。每次作业调度时,都必须做出两个决定:1)接纳多少个作业:取决于多道程序度。2)接纳哪些作业(用什么调度算法):先来先服务、短作业优先、优先权、响应比优先。,3.1 处理机调度的基本概念 3.1.1 高级、低级和中级调度,响应/运行,二.低级调度(进程调度,短程调度)进程调度的任务是控制协调进

3、程对CPU的竞争,即按照一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。它是最基本的一种调度,批处理系统,实时系统和分时系统都必须有进程调度。它通过进程调度程序来完成。1.进程调度程序的主要功能可描述如下：(1)记录系统中各进程的状况 为了很好地实现进程调度,进程调度程序首先必须管理系统中各进程的PCB，将进程的状态变化及资源需求情况及时地记录到PCB中。通过PCB变化来准确地掌握系统中所有进程的状态特征和执行情况。,(2)选择进程真正占有CPU 这是进程调度的实质,即按照系统规定的调度策略从就绪队列中选择一个进程占有CPU执行。进程调度依据的算法与系统的设计目标相一

4、致。对于不同的系统,通常采用不同的调度策略。对于批处理系统常采用短进程的进程优先,以减少各进程的周转时间。对于分时系统,更多地采用时间片轮转。(3)进行进程上下文的切换 当进程调度选中一个进程占有CPU时,进程调度程序要做的主要工作则是进行进程上下文切换:将正在执行进程的运行现场保留在该进程的PCB中,以便以后该进程恢复执行。将刚选中进程的运行现场恢复起来,并将CPU的控制权交给被选中进程,使其执行。,2.进程调度方式(1)非抢占方式(Non preemptive mode)在非抢占方式下,调度程序一旦把 CPU分配给某一进程后便让它一直运行下去,直到进程完成或发生某事件而不能运行时，才将CP

5、U分给其它进程。这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。(2)抢占方式(Preemptive mode)当一个进程正在执行时，系统可以基于某种策略剥夺CPU给其它进程。剥夺的原则有：优先权原则、短进程优先原则、时间片原则。显然这种调度方式多用在分时系统和实时系统中，以便及时响应各进程的请求。,3.进程调度的时机 所谓进程调度的时机，是指什么情况下引起进程调度程序工作。进程调度的时机是与进程调度的方式有关的。进程调度的时机如下：,正在执行的进程正确完成,或由于某种错误而终止运行(陷阱或中断)；执行中的进程提出I/O请求,等待I/O完成时;在分时系统中,按照时间片轮转,分

6、给进程的时间片用完时；按照优先级调度时,有更高优先级进程变为就绪时(抢占方式)；在进程通讯中,执行中的进程执行了某种原语操作,如wait操作、阻塞原语和唤醒原语时,都可能引起进程调度。,三.中级调度(中程调度)中级调度使暂时停止的进程不再占用宝贵的内存资源,将它们调到外存上去成为挂起状态。当处于挂起就绪的进程重新具备运行条件且内存稍有空闲时,中级调度将它重新调入内存,挂在活动就绪队列上等待进程调度。中级调度实质上就是存储管理中的对换功能。进程调度频率最高(10100ms/次)调度算法简单快速;作业调度频率最低约几分钟一次,调度算法允许花费较多的时间;中级调度介于两者之间。,3.1.2.调度队列

7、模型,1.仅有进程调度的调度队列模型 在分时系统中,通常仅有进程调度,采用FIFO算法。,CPU,就 绪 队 列,阻 塞 队 列,时间片完,进程调度,等待事件,事件出现,交互用户,完成,2.具有高级和低级调度的调度队列模型 在批处理系统中,不仅需要进程调度而且需要作业调度。,3.具有三级调度的调度队列模型 在具有三级调度系统中,增加了在外存的挂起状态,对于不同的系统,有不同的设计目标,采用不同的调度算法。调度算法实质上是个策略问题面向用户的准则：周转时间短 交互式系统的响应时间快 截止时间保证 优先权准则(公平合理)面向系统的准则：单位时间内运行尽可能多的进程,吞吐量高 使处理机尽可能保持“忙

8、碌”利用率高 使内外存、I/O设备得以均衡、充分利用,3.1.3.调度算法的评价准则,进程(作业)平均周转时间（周转时间、吞吐量）设某进程创建时间为Si,结束的时间为Ei 它的周转时间(全过程所用时间)为 Ti=Ei Si 系统为它提供的实际服务时间为Tsi 则进程平均周转时间T,带权平均周转时间W为：T W=其中，n为被测定进程流中的进程数,要设计一个理想的调度算法是一件十分困难的事,在实际系统中,调度算法往往折衷考虑。大多数操作系统都采用比较简单的调度算法,3.2 调度算法,1.先进先出调度算法(FIFO)(先来先服务FCFS)作业调度按照进入后备队列的先后次序调度,进程调度按照进入进程就

9、绪队列的先后次序来调度 优点:实现简单 缺点:不利于短作业(进程),紧迫性作业(进程)得不到及时处理2.短作业(进程)优先调度算法(SJF,SPF)选择就绪队列中估计运行时间最短的进程投入运行 优点:平均周转时间,带权平均周转时间都改善 缺点:对长作业(进程)非常不利 不能保证紧迫性作业(进程)得到及时处理 估计运行时间不准确,3.优先权调度算法(HPFHighest Priority First)优先选择就绪队列中优先权最高的进程投入运行非抢占式优先权算法:仅在事件发生放弃处理机时抢占式优先权算法:可将正在运行的运行权剥夺 优先权的类型静态优先权:在进程创建时指定优先权,在进程运行时优先数不

10、变动态优先权:在进程创建时创立一个优先权，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变 确定优先权的依据进程类型、对资源的需求、根据用户要求,4.高响应比优先调度算法：改进短作业(进程)优先调度算法,优先权用下式动态计算出来 优先权=上式可看出 等待时间相同要求服务的时间越短优先权越高,有利于短作业 要求服务时间相同,等待时间越长优先权越高,近似于先来先服务 长作业的优先权会随等待时间加长而升高,长作业也会得到执行,把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队

11、列末尾。同时系统选择另一个进程运行 分时系统中常用时间片轮转法时间片选择问题：固定时间片、可变时间片确定时间片大小的因素：系统响应时间、就绪进程个数、CPU能力,5.时间片轮转调度算法,6.多队列反馈调度算法：系统按优先级设置多级就绪队列第一级优先级最高 各就绪队列分配不同的时间片,优先级高的第一级队列时间片最小,随着队列优先级的降低,时间片加大 各个队列按照先进先出调度算法 一个新进程就绪后进入第一级就绪队列 进程由于等待事件而放弃CPU后,进入等待队列,一旦等待的事件发生,则回到原来的就绪队列 当有一个优先级更高的进程就绪时,可以抢占CPU,被抢占进程回到原来一级就绪队列末尾 当第一级队列

12、空时,就去调度第二级队列,如此类推 时间片用完后进程放弃CPU,进入下一级就绪队列,实时系统中,对实时进程的调度有截止时间的要求1.实现实时调度的基本条件 1)提供必要的信息 就绪时间、开始截止时间或完成截止时间、处理时间、资源要求、优先级(硬实时任务赋绝对优先级)。2)系统处理速度快 若系统中有m 个周期性硬实时任务,处理时间为Ci周期时间为Pi,则处理机处理速度应达到可调度条件:1(单处理机)n(多处理机)3)采用抢占式调度机制以满足对截止时间的要求 4)具有快速切换机制:快速中断响应、快速任务分派,3.3 实时调度,2.实时调度算法的分类 1)非抢占式调度算法 非抢占式轮转调度算法(响应

13、时间数秒到数十秒)轮转一圈后调度 非抢占式优先权调度算法(响应时间数百毫秒)当前进程完成(或被阻塞)后调度 2)抢占式调度算法 严格要求的实时系统,响应时间在数十毫秒以内 基于时钟中断的抢占式调度算法 时钟中断到来时调度 立即抢占的优先权调度算法 立即剥夺当前进程 调度时间见P 83 图3-6,3.几种常见的实时调度算法 1)最早截止时间优先算法(Earliest Deadline First)根据任务的开始截止时间确定优先级。2)最低松弛度优先算法(Least Laxity First)根据任务的松弛度(紧急程度)确定优先级 根据任务完成截止时间和本身运行时间确定松弛度 松弛度=必须完成时间

14、-本身运行时间-当前时间 P 85 图 3-9,保存现场:顺序保存进程的上下文,包括程序计数器和其它寄存器 用新状态和相关信息更新正在运行进程的PCB 把该进程移至合适的队列-就绪、阻塞 选择另一个要执行的进程,更新该进程的PCB 从被选中进程中重装入 CPU 上下文,恢复现场 若无就绪进程,系统会安排一个闲逛进程(idle),一直运行,在执行过程中可接收中断。,3.4 CPU调度的实现,操作系统的核心 向上提供无中断的虚拟机器,在核心内不允许中断特点:核心常驻内存,短小精焊,为进程运行提供舞台 核心的组成中断处理:时钟、I/O、虚拟存储器进程管理:调度 控制 通讯 互斥 同步等原语管理:提供

15、一系列原语,同步,通信,创建,撤消等队列管理:中断之后调度之前(运行-就绪-等待队列)现场管理:保存现场、恢复现场时钟管理:绝对时钟、间隔时钟、虚时钟,保存现场、分析中断源 处理中断原语管理、队列管理、时钟管理、进程调度 恢复现场,中断,核心入口,核心处理流程 唯一入口:中断,由硬件完成,作业:P101 2,3,5,3.5死锁,死锁的基本概念死锁的解决方案（预防，避免，检测及解除）资源分配图,3.5.1 死锁的基本概念,死锁(Deadlock)的定义：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程说明:参与

16、死锁的进程最少是两个参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源注意：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。,死锁产生的原因1.竞争资源引起永久性资源:可被多个进程多次使用(可再用资源)剥夺性资源(CPU、内存）非剥夺性资源(磁带机、打印机)竞争非剥夺性资源会引起死锁临时性资源:只可使用一次的资源；如信号量,中断信号,同步信号等(可消耗性资源)竞争临时性资源也会引起死锁2.进程推进顺序不当引起 对资源采用“申请-分配-使用-释放”模式,由于推进顺序不当两进程都要申请对方已占有的资源,P1：申请打印机申请扫描仪使用释放打印机释放扫描仪,P2：申请扫描仪申请打印

17、机使用释放打印机释放扫描仪,死锁的例子:竞争非剥夺性资源进程推进顺序不当引起死锁,Req(R1)Req(R2)Rel(R1)Rel(R2),Rel(R1)Rel(R2)Req(R1)Req(R2),P2,P1,不安全区,竞争非剥夺性资源,推进顺序不当进入不安全区,3.5.2产生死锁的四个必要条件,1)互斥条件（资源独占）：一个资源每次只能给一个进程使用2)请求和保持条件:(部分分配,占有申请)在申请新资源的同时保持对原有资源的占有3)不可剥夺条件（不可强占）：资源申请者不能强行的从资源占有者手中夺取资源,资源只能由占有者自愿释放4)循环等待条件：存在进程-等待资源环形链 P1,P2,Pn,其中

18、P1等待P2占有的资源,P2等待P3占有的资源,Pn等待P1占有的资源。,3.6 死锁的预防 3.6.1 强限制预防,确定资源分配算法,保证不发生死锁。做法是破坏产生死锁的四个必要条件之一。1.破坏“请求和保持(部分分配)”条件 每个进程运行前必须一次性申请运行期所需全部资源,若所需资源均可满足则全部分配。该进程运行中不再请求资源,屏弃请求条件。简单、安全;但资源利用率低,要长期等待。2.破坏“不可剥夺”条件 在允许进程动态申请资源前提下,规定:某进程在申请新的资源不能立即满足而被阻塞之前,必须释放已占有的资源(可能造成前一段工作失效),若需要再重新申请(增加开销)。,3.破坏“循环等待”条件

19、 采用资源有序分配法:允许进程动态申请资源,对系统中所有资源编号,进程申请资源时应严格按资源编号递增次序进行,否则不予分配。,缺点:资源利用仍不充分,3.6.2 避免死锁的银行家算法,前面的三种方法由于限制太强,资源利用率都不太高。能否放宽限制条件？E.W.Dijkstra于1968年提出银行家算法,此算法要事先知道每个进程对资源的最大需求量;算法的基本思路:允许进程动态申请资源,但在每次分配资源前先对本次分配的安全性进行检查,以判断这种分配是否可能导致死锁,若分配可能导致系统死锁,则不予分配,否则分配该资源。(检查每次分配后是否仍存在安全分配序列)显然,此法避免了死锁且资源利用率高。,1.安

20、全序列：如果进程序列P1，Pn对每个Pi(1in)进程,它以后尚需要的资源量不超过系统当前剩余资源量与所有Pj(j i)进程当前占有资源量之和,则系统处于安全状态(不会发生死锁),称此序列为安全序列。若系统不存在这样一个安全序列,则称系统处于不安全状态,不安全状态可能引起系统死锁。例如:避免死锁的实质是如何使系统不进入不安全状态。,安全序列:P2,P1,P3,2.银行家算法(发贷款检查安全性,先给能及时还贷者)算法使用的数据结构：n:系统中进程的总数;m:资源类总数当前可用向量 Available:ARRAY1.m of integer;最大需求矩阵 Max:ARRAY1.n,1.m of i

21、nteger;已分配矩阵 Allocation:ARRAY1.n,1.m of integer;尚需求矩阵 Need:ARRAY1.n,1.m of integer;Needi,j=MAXi,j-Allocatini,j本次请求向量 Request:ARRAY1.m of integer;进程Pi的资源向量为：Maxi,Allocationi,Needi,算法:当进程Pi提出资源申请Request时,执行下列步骤:(1).若RequestNeedi,转(2)否则错误返回(2).若RequestAvailable,转(3)否则进程等待(3).系统试探分配资源,修改数据,则有:Available:

22、=Available-Request;Allocationi:=Allocationi+Request;Needi:=Needi-Request;(4).系统执行安全性算法,检查如果按此分配后,系统新状态是安全的,则将资源正式分配给进程Pi,若新状态是不安全的,则恢复原状态 进程Pi等待,3.安全性算法设置工作向量 Work:系统可供给进程继续运行所需的m类资源数目 Finish:能执行完标志(可提供足够资源使进程完成)安全性检查的步骤：(1)初值:Work:=Available;Finish:=false;(2)寻找满足条件的Pk：Finishk=false;且 NeedkWork;(向量比

23、较)如果不存在，则转(4)(3)Work:=Work+Allocationk;Finishk:=true;转(2)(4)若对所有k,Finishk=true,则系统处于安全状态,否则处于不安全状态,进程 最大需求 已分配 尚需要 可用 P1 10 5 5 3 P2 4 2 2 P3 9 2 7,4.银行家算法实例(一种资源)：,安全序列:P2,P1,P3,银行家算法实例(多种资源)：假定系统有五个进程P0,P1,P2,P3,P4和三类资源ABC资源总数为10,5,7,T0时刻资源分配情况为:,1)检查T0时刻的安全性,P1 3 3 2 2 0 0 1 2 2 5 3 2 true,安全,P3

24、5 3 2 2 1 1 0 1 1 7 4 3 true,P4 7 4 3 0 0 2 4 3 1 7 4 5 true,P2 7 4 5 3 0 2 6 0 0 10 4 7 true,P0 10 4 7 0 1 0 7 4 3 10 5 7 true,检查此刻的安全性,安全,可将(1,0,2)分配给P1,2)T1时P1发出请求Request(1,0,2)假定分配,资源变为:,P1 2 3 0 3 0 2 0 2 0 5 3 2 true,P3 5 3 2 2 1 1 0 1 1 7 4 3 true,P4 7 4 3 0 0 2 4 3 1 7 4 5 true,P0 7 4 5 0 1

25、0 7 4 3 7 5 5 true,P2 7 5 5 3 0 2 6 0 0 10 5 7 true,3)假定P4请求资源,发出请求向量Request(3,3,0)Request(3,3,0)Available(2,3,0),让P4等待4)若P0请求资源,发出请求向量Request(0,2,0)假定分配,资源为:,检查此刻的安全性：Available(2,1,0)已不满足任何进程的需要,不安全;不予分配Available 仍为(2,3,0)。,检查此刻的安全性,安全,可将(0,1,0)分配给P0,若将P0请求改为Request(0,1,0)假定分配,资源变为:,P1 2 2 0 3 0 2

26、0 2 0 5 2 2 true,P3 5 2 2 2 1 1 0 1 1 7 3 3 true,P4 7 3 3 0 0 2 4 3 1 7 3 5 true,P0 7 3 5 0 2 0 7 3 3 7 5 5 true,P2 7 5 5 3 0 2 6 0 0 10 5 7 true,3.7 死锁的检测与解除,允许死锁发生，系统必须提供检测和解除死锁的手段,操作系统应不断监视系统进展情况，判断死锁是否发生。,死锁的检测,1.资源分配图用有向图描述进程的死锁:准确、形象 系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例。二元组G=（V，E）V：结点

27、集，分为P，R两部分 P=p1,p2,pn R=r1,r2,rm E：边的集合,其元素为有序二元组 分配边(rj,pi):资源实例进程的一条有向边申请边(pi,rj):进程资源类的一条有向边,有环有死锁,有环无死锁,2.死锁定理 如果资源分配图中没有环路,则系统中没有死锁,如果图中存在环路则系统中可能存在死锁。如果每个资源类中只包含一个资源实例,则资源分配图环路是死锁存在的充分必要条件。资源分配图化简方法：1）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点。2）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边。3）重复(1)(2)操作直到无法再化简,若所

28、有结点都为孤立结点则无死锁,否则死锁发生,3.7.2死锁的解除,一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。死锁的解除(关键是代价最小)：1）重新启动2）撤消进程3）剥夺资源4）进程回退,处理机调度(1)高级调度(作业调度接纳调度或长程调度)将后备队列中作业调入内存,并创建进程。(2)低级调度(进程调度,短程调度)从就绪队列中选中一进程,把CPU使用权交给它。(3)中级调度:内存紧张时将内存的进程挂起调到外存 或内存稍有空闲时将它激活重新调入内存 2.进程调度方式(1)非抢占方式(Non preemptive mode)(2)抢占方式(Preemptive mode)

29、3.进程调度的时机(1)执行进程正确完成 或错误终止(2)执行进程提出I/O请求,等待I/O完成时;(3)分时系统时间片轮转,分给进程的时间片用完时(4)优先级调度,抢占方式中有更高优先级进程就绪(5)执行进程执行wait、阻塞原语和唤醒原语等操作,4.调度算法(1)先进先出调度算法(FIFO)(先来先服务FCFS)(2)短作业(进程)优先调度算法(SJF,SPF)(3)优先权调度算法(HPFHighest Priority First)(4)高响应比优先调度算法(5)时间片轮转调度算法(6)多队列反馈调度算法5.常见的实时调度算法(1)最早截止时间优先算法(Earliest Deadline

30、 First)(2)最低松弛度优先算法(Least Laxity First)6.调度的实现过程 保存现进程现场、更新它的PCB、把它移至合适队列 选择要执行的进程、更新它的PCB、恢复新进程现场,7.死锁(Deadlock)的定义：进程组中各进程都无限等待被该组另一进程所占的资源注意：参与死锁的进程最少是两个、至少有两个 已占有资源、该组所有进程都在等待资源8.产生死锁的四个必要条件(1)互斥条件(资源独占):一个资源只能给一个进程使用(2)请求和保持条件:部分分配,保持原资源申请新资源(3)不可剥夺条件:(不可强占,只能由占有者自愿释放)(4)循环等待条件:形成等待环9.死锁的预防(强限制

31、)破坏产生死锁的四个必要条件之一(后3条)10.避免死锁的银行家算法(宽限制)检查每次分配后是否仍存在安全分配序列 避免了死锁且资源利用率高,11.死锁的检测 允许死锁发生,OS应不断检测死锁是否发生12.资源分配图结点集:各进程结点P,各资源类结点R边集:元素为有序二元组,分配边(rj,pi)申请边(pi,rj)13.死锁定理资源分配图无环路,则没有死锁,有环路则可能存在死锁 若各资源类只含一个资源,环路是死锁的充分必要条件14.资源分配图化简方法()(1)找只有分配边的进程结点,去掉分配边变为孤立结点(2)把相应的资源分配给等待进程,申请边变为分配边 重复(1)(2)直到无法再化简,若仍有

32、环路则死锁发生15.死锁的解除(关键是代价最小)：重新启动、撤消进程、剥夺资源、进程回退,课后题,P102 16、17、18、19、20 补充1:三个进程共享四个资源,这些资源的分配与释放只能一次一个,已知每一进程 最多需要两个资源,请问该系统会发生死锁码？试说明原因。,补充2:设三个进程P1,P2,P3,各按如下顺序执行：进程P1 进程P2 进程P3 在执行时能否产生死锁？如果可能，请说明在什么情况下会产生死锁？并给出一个防止死锁产生的修改办法。,P（S1）P（S2）:V（S1）V（S2）,P（S3）P（S1）:V（S3）V（S1）,P（S2）P（S3）:V（S2）V（S3）,上机安排:院机

33、房二楼电科1-2：第七、八周 周一、三.3-4节电科3-4：第九、十周 周一、三.3-4节计科1-3：第七、八周 周一.5-6节 周三.1-2节内容:p 1 进程管理，要求:事先预习看懂程序P10 func timeint()函数模拟时间片中断 process1,process2,process3 模拟3 个进程P14 case 配合goto 及“进程”中的标号等模拟并发其中的 if 语句的条件改为：else if(x=0.33)and(x=0.67)and(exe=3)P 3 框图2 改为：,进程调度过程scheduler,send 发送 receive 接收init 初始化 random 随机数 find 选进程 scheduler 调度 block 阻塞 p wait操作 wakeup 唤醒 v signal操作 timeint 时间片中断 eexit 退出 process1、process1、process1 模拟3个并发进程main 主程序,