处理机调度课件

1、要解决的问题WHAT：按什么原则分配CPU 进程调度算法WHEN：何时分配CPU 进程调度的时机HOW： 如何分配CPU CPU调度过程（进程的上下文切换）第1页，共56页。 一批作业从进入系统到作业运行完毕可能经历三级调度高级、低级和中级调度。一. 高级调度(High Scheduling) 又称为作业调度接纳调度或长程调度, 用于批处理系统, 确定将外存后备队列中哪些作业调入内存, 并为它们创建进程。实时系统和分时系统的前台作业不需要作业调度。每次作业调度时, 都必须做出两个决定: 1) 接纳多少个作业: 取决于多道程序度。 2) 接纳哪些作业(用什么调度算法): 先来先服务、短作业优先、

2、优先权、响应比优先。3.1 处理机调度的基本概念 3.1.1 高级、低级和中级调度响应/运行第2页，共56页。二. 低级调度(进程调度,短程调度) 进程调度的任务是控制协调进程对CPU的竞争, 即按照一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。它是最基本的一种调度, 批处理系统, 实时系统和分时系统都必须有进程调度。它通过进程调度程序来完成。1. 进程调度程序的主要功能可描述如下：(1) 记录系统中各进程的状况 为了很好地实现进程调度, 进程调度程序首先必须管理系统中各进程的PCB，将进程的状态变化及资源需求情况及时地记录到PCB中。通过PCB变化来准确地掌握系统

3、中所有进程的状态特征和执行情况。第3页，共56页。(2) 选择进程真正占有CPU 这是进程调度的实质, 即按照系统规定的调度策略从就绪队列中选择一个进程占有CPU执行。进程调度依据的算法与系统的设计目标相一致。对于不同的系统, 通常采用不同的调度策略。对于批处理系统常采用短进程的进程优先, 以减少各进程的周转时间。对于分时系统, 更多地采用时间片轮转。(3) 进行进程上下文的切换 当进程调度选中一个进程占有CPU时, 进程调度程序要做的主要工作则是进行进程上下文切换: 将正在执行进程的运行现场保留在该进程的PCB中, 以便以后该进程恢复执行。将刚选中进程的运行现场恢复起来, 并将CPU的控制权

4、交给被选中进程, 使其执行。第4页，共56页。2. 进程调度方式 (1)非抢占方式(Non preemptive mode) 在非抢占方式下, 调度程序一旦把 CPU分配给某一进程后便让它一直运行下去, 直到进程完成或发生某事件而不能运行时，才将CPU分给其它进程。 这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。 (2)抢占方式(Preemptive mode) 当一个进程正在执行时，系统可以基于某种策略剥夺CPU给其它进程。剥夺的原则有： 优先权原则、短进程优先原则、时间片原则。 显然这种调度方式多用在分时系统和实时系统中，以便及时响应各进程的请求。第5页，共56页。3.

5、 进程调度的时机 所谓进程调度的时机，是指什么情况下引起进程调度程序工作。进程调度的时机是与进程调度的方式有关的。进程调度的时机如下：正在执行的进程正确完成, 或由于某种错误而终止运行(陷阱或中断) ；执行中的进程提出I/O请求, 等待I/O完成时;在分时系统中, 按照时间片轮转, 分给进程的时间片用完时；按照优先级调度时, 有更高优先级进程变为就绪时(抢占方式)；在进程通讯中, 执行中的进程执行了某种原语操作, 如wait操作、阻塞原语和唤醒原语时, 都可能引起进程调度。第6页，共56页。三. 中级调度(中程调度) 中级调度使暂时停止的进程不再占用宝贵的内存资源, 将它们调到外存上去成为挂起

6、状态。当处于挂起就绪的进程重新具备运行条件且内存稍有空闲时, 中级调度将它重新调入内存, 挂在活动就绪队列上等待进程调度。中级调度实质上就是存储管理中的对换功能。 进程调度频率最高(10100ms/次)调度算法简单快速; 作业调度频率最低约几分钟一次,调度算法允许花费较多的时间; 中级调度介于两者之间。第7页，共56页。3.1.2. 调度队列模型1. 仅有进程调度的调度队列模型 在分时系统中, 通常仅有进程调度, 采用FIFO算法。CPU就 绪 队 列阻 塞 队 列时间片完进程调度等待事件事件出现交互用户完成第8页，共56页。2. 具有高级和低级调度的调度队列模型 在批处理系统中,不仅需要进程

7、调度而且需要作业调度。CPU就 绪 队 列阻 塞 队 列时间片完进程调度事件1出现 后备队列完成阻 塞 队 列事件2出现 阻 塞 队 列事件n出现 .等待事件1等待事件2等待事件n作业调度第9页，共56页。3. 具有三级调度的调度队列模型 在具有三级调度系统中, 增加了在外存的挂起状态CPU就 绪 队 列就 绪 挂 起 时间片完进程调度事件出现后备队列完成阻 塞 挂 起阻 塞 队 列 挂起等待事件作业调度事件出现中级调度交互作业调出第10页，共56页。 对于不同的系统, 有不同的设计目标, 采用不同的调度算法。调度算法实质上是个策略问题面向用户的准则： 周转时间短 交互式系统的响应时间快 截止

8、时间保证 优先权准则(公平合理)面向系统的准则： 单位时间内运行尽可能多的进程, 吞吐量高 使处理机尽可能保持“忙碌”利用率高 使内外存、I/O设备得以均衡、充分利用3.1.3. 调度算法的评价准则第11页，共56页。进程(作业)平均周转时间（周转时间、吞吐量） 设某进程创建时间为Si, 结束的时间为Ei 它的周转时间(全过程所用时间)为 Ti =Ei Si 系统为它提供的实际服务时间为Tsi 则进程平均周转时间T,带权平均周转时间W为： T W= 其中，n为被测定进程流中的进程数ni=1Tin1ni=1Tin1Tsi 要设计一个理想的调度算法是一件十分困难的事,在实际系统中, 调度算法往往折

9、衷考虑。 大多数操作系统都采用比较简单的调度算法第12页，共56页。3.2 调度算法1.先进先出调度算法(FIFO) (先来先服务FCFS) 作业调度按照进入后备队列的先后次序调度, 进程调度按照进入进程就绪队列的先后次序来调度 优点:实现简单 缺点:不利于短作业(进程),紧迫性作业(进程)得不到及时处理2.短作业(进程)优先调度算法(SJF,SPF) 选择就绪队列中估计运行时间最短的进程投入运行 优点: 平均周转时间,带权平均周转时间都改善 缺点: 对长作业(进程)非常不利 不能保证紧迫性作业(进程)得到及时处理 估计运行时间不准确第13页，共56页。3. 优先权调度算法(HPFHighes

10、t Priority First)优先选择就绪队列中优先权最高的进程投入运行非抢占式优先权算法:仅在事件发生放弃处理机时抢占式优先权算法: 可将正在运行的运行权剥夺 优先权的类型静态优先权: 在进程创建时指定优先权, 在进程运行时优先数不变动态优先权: 在进程创建时创立一个优先权，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变 确定优先权的依据进程类型、对资源的需求、根据用户要求第14页，共56页。4. 高响应比优先调度算法： 改进短作业(进程)优先调度算法,优先权用下式动态计算出来 优先权= =上式可看出 等待时间相同要求服务的时间越短优先权越高, 有利于短作业 要求服务时间相

11、同,等待时间越长优先权越高,近似于先来先服务 长作业的优先权会随等待时间加长而升高,长作业也会得到执行等待时间+要求服务时间 响应时间 要求服务时间 要求服务时间第15页，共56页。 把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行 分时系统中常用时间片轮转法时间片选择问题： 固定时间片、可变时间片确定时间片大小的因素： 系统响应时间、就绪进程个数、CPU能力 5.时间片轮转调度算法第16页，共56页。6.多队列反馈调度算法： 系统按优先级设置多

12、级就绪队列第一级优先级最高 各就绪队列分配不同的时间片,优先级高的第一级队列时间片最小, 随着队列优先级的降低, 时间片加大 各个队列按照先进先出调度算法 一个新进程就绪后进入第一级就绪队列 进程由于等待事件而放弃CPU后, 进入等待队列, 一旦等待的事件发生, 则回到原来的就绪队列 当有一个优先级更高的进程就绪时, 可以抢占CPU,被抢占进程回到原来一级就绪队列末尾 当第一级队列空时, 就去调度第二级队列, 如此类推 时间片用完后进程放弃CPU, 进入下一级就绪队列第17页，共56页。 实时系统中, 对实时进程的调度有截止时间的要求1.实现实时调度的基本条件 1) 提供必要的信息 就绪时间、

13、开始截止时间或完成截止时间、处理时间、资源要求、优先级( 硬实时任务赋绝对优先级)。 2) 系统处理速度快 若系统中有m 个周期性硬实时任务, 处理时间为Ci周期时间为Pi , 则处理机处理速度应达到可调度条件: 1 (单处理机) n (多处理机) 3) 采用抢占式调度机制以满足对截止时间的要求 4) 具有快速切换机制: 快速中断响应、快速任务分派3.3 实时调度CiPii=1nCiPii=1n第18页，共56页。2. 实时调度算法的分类 1) 非抢占式调度算法 非抢占式轮转调度算法(响应时间数秒到数十秒) 轮转一圈后调度 非抢占式优先权调度算法(响应时间数百毫秒) 当前进程完成(或被阻塞)后

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

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

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

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

18、已占有的资源第26页，共56页。P1： 申请打印机申请扫描仪使用释放打印机释放扫描仪P2： 申请扫描仪申请打印机使用释放打印机释放扫描仪死锁的例子:竞争非剥夺性资源进程推进顺序不当引起死锁第27页，共56页。Req(R1) Req(R2) Rel(R1) Rel(R2)Rel(R1)Rel(R2)Req(R1)Req(R2)P2P1不安全区竞争非剥夺性资源推进顺序不当进入不安全区第28页，共56页。3.5.2产生死锁的四个必要条件1) 互斥条件（资源独占）： 一个资源每次只能给一个进程使用2) 请求和保持条件: (部分分配,占有申请) 在申请新资源的同时保持对原有资源的占有3) 不可剥夺条件（

19、不可强占）： 资源申请者不能强行的从资源占有者手中夺取资源, 资源只能由占有者自愿释放4) 循环等待条件： 存在进程-等待资源环形链 P1 , P2 , , Pn, 其中P1等待P2占有的资源, P2等待P3占有的资源, , Pn等待P1占有的资源。第29页，共56页。3.6 死锁的预防 3.6.1 强限制预防 确定资源分配算法,保证不发生死锁。做法是破坏产生死锁的四个必要条件之一。1. 破坏“请求和保持(部分分配)”条件 每个进程运行前必须一次性申请运行期所需全部资源, 若所需资源均可满足则全部分配。该进程运行中不再请求资源, 屏弃请求条件。 简单、安全; 但资源利用率低,要长期等待。2.

20、破坏“不可剥夺”条件 在允许进程动态申请资源前提下, 规定: 某进程在申请新的资源不能立即满足而被阻塞之前, 必须释放已占有的资源(可能造成前一段工作失效), 若需要再重新申请(增加开销)。第30页，共56页。3.破坏“循环等待”条件 采用资源有序分配法:允许进程动态申请资源, 对系统中所有资源编号, 进程申请资源时应严格按资源编号递增次序进行,否则不予分配。P1：申请1申请3申请4P2：申请2申请4申请8Pn：申请1申请2申请8缺点: 资源利用仍不充分第31页，共56页。3.6.2 避免死锁的银行家算法 前面的三种方法由于限制太强, 资源利用率都不太高。能否放宽限制条件？ E.W.Dijks

21、tra于1968年提出银行家算法, 此算法要事先知道每个进程对资源的最大需求量; 算法的基本思路:允许进程动态申请资源,但在每次分配资源前先对本次分配的安全性进行检查, 以判断这种分配是否可能导致死锁, 若分配可能导致系统死锁, 则不予分配, 否则分配该资源。(检查每次分配后是否仍存在安全分配序列) 显然, 此法避免了死锁且资源利用率高。第32页，共56页。1. 安全序列： 如果进程序列P1，Pn对每个Pi(1in)进程, 它以后尚需要的资源量不超过系统当前剩余资源量与所有Pj (j Available(2,3,0),让P4等待4) 若P0请求资源,发出请求向量Request(0,2,0)假定

22、分配,资源为: 检查此刻的安全性：Available(2,1,0)已不满足任何进程的需要, 不安全; 不予分配Available 仍为(2,3,0) 。 Max Allocation Need Available 进程 A B C A B C A B C A B C P0 7 5 3 0 3 0 7 2 3 2 1 0 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1第40页，共56页。检查此刻的安全性 Max Allocation Need Available 进程 A B

23、C A B C A B C A B C P0 7 5 3 0 2 0 7 3 3 2 2 0 P1 3 2 2 3 0 2 0 2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1安全, 可将(0,1,0)分配给P0若将P0请求改为Request(0,1,0)假定分配, 资源变为: 进 Work Allocation Need W+ A Finish 程 A B C A B C A B C A B C P1 2 2 0 3 0 2 0 2 0 5 2 2 trueP3 5 2 2 2 1 1 0 1 1 7 3 3

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

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

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

27、(Non preemptive mode) (2)抢占方式(Preemptive mode)3. 进程调度的时机 (1) 执行进程正确完成 或错误终止 (2) 执行进程提出I/O请求, 等待I/O完成时; (3) 分时系统时间片轮转, 分给进程的时间片用完时 (4) 优先级调度, 抢占方式中有更高优先级进程就绪 (5) 执行进程执行wait、阻塞原语和唤醒原语等操作第48页，共56页。4. 调度算法(1)先进先出调度算法(FIFO) (先来先服务FCFS)(2)短作业(进程)优先调度算法(SJF,SPF)(3)优先权调度算法(HPFHighest Priority First)(4)高响应比优

28、先调度算法(5)时间片轮转调度算法(6)多队列反馈调度算法5. 常见的实时调度算法(1) 最早截止时间优先算法(Earliest Deadline First)(2) 最低松弛度优先算法(Least Laxity First)6. 调度的实现过程 保存现进程现场、更新它的PCB、把它移至合适队列 选择要执行的进程、更新它的PCB、恢复新进程现场第49页，共56页。7. 死锁(Deadlock)的定义：进程组中各进程都无限等待被该组另一进程所占的资源注意：参与死锁的进程最少是两个、至少有两个 已占有资源、该组所有进程都在等待资源8.产生死锁的四个必要条件 (1) 互斥条件(资源独占): 一个资源

29、只能给一个进程使用 (2) 请求和保持条件: 部分分配, 保持原资源申请新资源 (3) 不可剥夺条件: (不可强占, 只能由占有者自愿释放) (4) 循环等待条件: 形成等待环9. 死锁的预防(强限制) 破坏产生死锁的四个必要条件之一(后3条)10. 避免死锁的银行家算法(宽限制) 检查每次分配后是否仍存在安全分配序列 避免了死锁且资源利用率高第50页，共56页。11. 死锁的检测 允许死锁发生,OS应不断检测死锁是否发生12. 资源分配图结点集: 各进程结点P, 各资源类结点R边集: 元素为有序二元组, 分配边(rj,pi) 申请边(pi,rj) 13. 死锁定理资源分配图无环路, 则没有死锁, 有环路则可能存在死锁 若各资源类只含一个资源, 环路是死锁的充分必要条件14. 资源分配图化简方法() (1)找只有分配边的进程结点,去掉分配边变为孤立结点 (2)把相应的资源分配给等待进程, 申请边变为分配边 重复(1) (2) 直到无法再化简, 若仍有环路则死锁发生15. 死锁的解除(关键是代价