处理机调.pptx

要解决的问题要解决的问题WHAT：按什么原则分配按什么原则分配CPU 进程调度算法进程调度算法WHEN：何时分配何时分配CPU 进程调度的时机进程调度的时机HOW：如何分配如何分配CPU CPU调度过程（进程的上下文切换）调度过程（进程的上下文切换）一批作业从进入系统到作业运行完毕可能经历三级一批作业从进入系统到作业运行完毕可能经历三级调度调度高级、低级和中级调度。高级、低级和中级调度。一一.高级调度高级调度(High Scheduling)又称为作业调度接纳调度或长程调度又称为作业调度接纳调度或长程调度,用于批处理用于批处理系统系统,确定将外存后备队列中哪些作业调入内存确定将外存后备队列中哪些作业调入内存,并为它并为它们创建进程。实时系统和分时系统的前台作业不需要作们创建进程。实时系统和分时系统的前台作业不需要作业调度。每次作业调度时业调度。每次作业调度时,都必须做出两个决定都必须做出两个决定:1)接纳多少个作业接纳多少个作业:取决于多道程序度。取决于多道程序度。2)接纳哪些作业接纳哪些作业(用什么调度算法用什么调度算法):先来先服务、短作业优先、优先权、响应比优先。先来先服务、短作业优先、优先权、响应比优先。3.1 处理机调度的基本概念处理机调度的基本概念 3.1.1 高级、低级和中级调度高级、低级和中级调度响应响应/运行运行二二.低级调度低级调度(进程调度进程调度,短程调度短程调度)进程调度的任务是控制协调进程对进程调度的任务是控制协调进程对CPU的竞争的竞争,即即按照一定的调度算法从就绪队列中选中一个进程，把按照一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。它是最基本的一种的使用权交给被选中的进程。它是最基本的一种调度调度,批处理系统批处理系统,实时系统和分时系统都必须有进程实时系统和分时系统都必须有进程调度。它通过进程调度程序来完成。调度。它通过进程调度程序来完成。1.进程调度程序的主要功能可描述如下：进程调度程序的主要功能可描述如下：(1)记录系统中各进程的状况记录系统中各进程的状况 为了很好地实现进程调度为了很好地实现进程调度,进程调度程序首先必须进程调度程序首先必须管理系统中各进程的管理系统中各进程的PCB，将进程的状态变化及资源，将进程的状态变化及资源需求情况及时地记录到需求情况及时地记录到PCB中。通过中。通过PCB变化来准确变化来准确地掌握系统中所有进程的地掌握系统中所有进程的状态特征和执行情况状态特征和执行情况。(2)选择进程真正占有选择进程真正占有CPU 这这是是进进程程调调度度的的实实质质,即即按按照照系系统统规规定定的的调调度度策策略略从从就就绪绪队队列列中中选选择择一一个个进进程程占占有有CPU执执行行。进进程程调调度度依依据据的的算算法法与与系系统统的的设设计计目目标标相相一一致致。对对于于不不同同的的系系统统,通通常常采采用用不不同同的的调调度度策策略略。对对于于批批处处理理系系统统常常采采用用短短进进程程的的进进程程优优先先,以以减减少少各各进进程程的的周周转转时时间间。对对于于分分时系统时系统,更多地采用时间片轮转。更多地采用时间片轮转。(3)进行进程上下文的切换进行进程上下文的切换 当进程调度选中一个进程占有当进程调度选中一个进程占有CPU时时,进程调度程进程调度程序要做的主要工作则是进行进程上下文切换序要做的主要工作则是进行进程上下文切换:将正在执将正在执行进程的运行现场保留在该进程的行进程的运行现场保留在该进程的PCB中中,以便以后该以便以后该进程恢复执行。将刚选中进程的运行现场恢复起来进程恢复执行。将刚选中进程的运行现场恢复起来,并并将将CPU的控制权交给被选中进程的控制权交给被选中进程,使其执行。使其执行。2.进程调度方式进程调度方式 (1)非抢占方式非抢占方式(Non preemptive mode)在非抢占方式下在非抢占方式下,调度程序一旦把调度程序一旦把 CPU分配给某分配给某一进程后便让它一直运行下去一进程后便让它一直运行下去,直到进程完成或发生直到进程完成或发生某事件而不能运行时，才将某事件而不能运行时，才将CPU分给其它进程。分给其它进程。这种调度方式通常用在批处理系统中。它的主要这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。优点是简单、系统开销小。(2)抢占方式抢占方式(Preemptive mode)当一个进程正在执行时，系统可以基于某种策略当一个进程正在执行时，系统可以基于某种策略剥夺剥夺CPU给其它进程。剥夺的原则有：给其它进程。剥夺的原则有：优先权原则、短进程优先原则、时间片原则。优先权原则、短进程优先原则、时间片原则。显然这种调度方式多用在分时系统和实时系统中，显然这种调度方式多用在分时系统和实时系统中，以便及时响应各进程的请求。以便及时响应各进程的请求。3.进程调度的时机进程调度的时机 所谓进程调度的时机，是指什么情况下引起进程所谓进程调度的时机，是指什么情况下引起进程调度程序工作。进程调度的时机是与进程调度的方式调度程序工作。进程调度的时机是与进程调度的方式有关的。进程调度的时机如下：有关的。进程调度的时机如下：1)正在执行的进程正确完成正在执行的进程正确完成,或由于某种错误而终或由于某种错误而终止运行止运行(陷阱或中断陷阱或中断)；2)执行中的进程提出执行中的进程提出I/O请求请求,等待等待I/O完成时完成时;3)在分时系统中在分时系统中,按照时间片轮转按照时间片轮转,分给进程的时分给进程的时间片用完时；间片用完时；4)按照优先级调度时按照优先级调度时,有更高优先级进程变为就绪有更高优先级进程变为就绪时时(抢占方式抢占方式)；5)在进程通讯中在进程通讯中,执行中的进程执行了某种原语操执行中的进程执行了某种原语操作作,如如wait操作、阻塞原语和唤醒原语时操作、阻塞原语和唤醒原语时,都可能都可能引起进程调度。引起进程调度。三三.中级调度中级调度(中程调度中程调度)中级调度使暂时停止的进程不再占用宝贵中级调度使暂时停止的进程不再占用宝贵的内存资源的内存资源,将它们调到外存上去成为挂起状将它们调到外存上去成为挂起状态。当处于挂起就绪的进程重新具备运行条件态。当处于挂起就绪的进程重新具备运行条件且内存稍有空闲时且内存稍有空闲时,中级调度将它重新调入内中级调度将它重新调入内存存,挂在活动就绪队列上等待进程调度。中级挂在活动就绪队列上等待进程调度。中级调度实质上就是存储管理中的对换功能。调度实质上就是存储管理中的对换功能。进程调度频率最高进程调度频率最高(10100ms/次次)调度算法调度算法简单快速简单快速;作业调度频率最低约几分钟一次作业调度频率最低约几分钟一次,调调度算法允许花费较多的时间度算法允许花费较多的时间;中级调度介于两中级调度介于两者之间。者之间。3.1.2.调度队列模型调度队列模型1.仅有进程调度的仅有进程调度的调度队列模型调度队列模型 在分时系统中在分时系统中,通常仅通常仅有进程调度有进程调度,采用采用FIFO算法。算法。CPU就就 绪绪 队队 列列阻阻 塞塞 队队 列列时间片完时间片完进程调度进程调度等待事件等待事件事件事件出现出现交互用户交互用户完成完成2.具有高级和低级调度的具有高级和低级调度的调度队列模型调度队列模型 在批处理系统中在批处理系统中,不仅需要不仅需要进程调度而且需进程调度而且需要作业调度。要作业调度。CPU就就 绪绪 队队 列列阻阻 塞塞 队队 列列时间片完时间片完进程进程调度调度事件事件1出现出现 后备后备队列队列完成完成阻阻 塞塞 队队 列列事件事件2出现出现 阻阻 塞塞 队队 列列事件事件n出现出现.等待事件等待事件1等待事件等待事件2等待事件等待事件n作业作业调度调度3.具有三级调度的具有三级调度的调度队列模型调度队列模型 在在具有三级调度具有三级调度系统中系统中,增加了在外存的挂起状态增加了在外存的挂起状态CPUCPU就就 绪绪 队队 列列就就 绪绪 挂挂 起起 时间片完时间片完进程进程调度调度事事件件出出现现后备后备队列队列完成完成阻阻 塞塞 挂挂 起起阻阻 塞塞 队队 列列 挂起挂起等待事件等待事件作业作业调度调度事件出现事件出现中级中级调度调度交互作业交互作业调出调出 对于不同的系统对于不同的系统,有不同的设计目标有不同的设计目标,采用不同采用不同的调度算法。调度算法实质上是个策略问题的调度算法。调度算法实质上是个策略问题面向用户的准则：面向用户的准则：l 周转时间短周转时间短l 交互式系统的响应时间快交互式系统的响应时间快l 截止时间保证截止时间保证l 优先权准则优先权准则(公平合理公平合理)面向系统的准则：面向系统的准则：l 单位时间内运行尽可能多的进程单位时间内运行尽可能多的进程,吞吐量高吞吐量高l 使处理机尽可能保持使处理机尽可能保持“忙碌忙碌”利用率高利用率高l 使内外存、使内外存、I/O设备得以均衡、充分利用设备得以均衡、充分利用3.1.3.调度算法的评价准则调度算法的评价准则进程进程(作业作业)平均周转时间平均周转时间（周转时间、吞吐量）（周转时间、吞吐量）设某进程创建时间为设某进程创建时间为Si,结束的时间为结束的时间为Ei 它的周转时间它的周转时间(全过程所用时间全过程所用时间)为为 Ti=Ei Si 系统为它提供的实际服务时间为系统为它提供的实际服务时间为Tsi 则进程平均周转时间则进程平均周转时间T,带权平均周转时间带权平均周转时间W为：为：T W=其中，其中，n为被测定进程流中的进程数为被测定进程流中的进程数 ni=1Tin1 ni=1Tin1Tsi 要设计一个理想的调度算法是一件十分困难的事要设计一个理想的调度算法是一件十分困难的事,在实际系统中在实际系统中,调度算法往往折衷考虑。调度算法往往折衷考虑。大多数操作系统都采用比较简单的调度算法大多数操作系统都采用比较简单的调度算法3.2 调度算法调度算法1.先进先出调度算法先进先出调度算法(FIFO)(先来先服务先来先服务FCFS)作业调度按照进入后备队列的先后次序调度作业调度按照进入后备队列的先后次序调度,进程进程调度按照进入进程就绪队列的先后次序来调度调度按照进入进程就绪队列的先后次序来调度 优点优点:实现简单实现简单 缺点缺点:不利于短作业不利于短作业(进程进程),紧迫性作业紧迫性作业(进程进程)得不到得不到及时处理及时处理2.短作业短作业(进程进程)优先调度算法优先调度算法(SJF,SPF)选择就绪队列中估计运行时间最短的进程投入运行选择就绪队列中估计运行时间最短的进程投入运行 优点优点:平均周转时间平均周转时间,带权平均周转时间都改善带权平均周转时间都改善 缺点缺点:对长作业对长作业(进程进程)非常不利非常不利 不能保证紧迫性作业不能保证紧迫性作业(进程进程)得到及时处理得到及时处理 估计运行时间不准确估计运行时间不准确3.优先权调度算法优先权调度算法(HPFHighest Priority First)优先选择就绪队列中优先权最高的进程投入运行优先选择就绪队列中优先权最高的进程投入运行非抢占式优先权算法非抢占式优先权算法:仅在事件发生放弃处理机时仅在事件发生放弃处理机时抢占式优先权算法抢占式优先权算法:可将正在运行的运行权剥夺可将正在运行的运行权剥夺 优先权的类型优先权的类型静态优先权静态优先权:在进程创建时指定优先权在进程创建时指定优先权,在进程运行在进程运行时优先数不变时优先数不变动态优先权动态优先权:在进程创建时创立一个优先权，但在在进程创建时创立一个优先权，但在其生命周期内优先数可以动态变化。如等待时间长其生命周期内优先数可以动态变化。如等待时间长优先数可改变优先数可改变 确定优先权的依据确定优先权的依据进程类型、对资源的需求、根据用户要求进程类型、对资源的需求、根据用户要求4.高响应比优先调度算法：高响应比优先调度算法：改进短作业改进短作业(进程进程)优先调度算法优先调度算法,优先权用下式动优先权用下式动态计算出来态计算出来 优先权优先权=上式可看出上式可看出 等待时间相同要求服务的时间越短优先权越高等待时间相同要求服务的时间越短优先权越高,有利于短作业有利于短作业 要求服务时间相同要求服务时间相同,等待时间越长优先权越高等待时间越长优先权越高,近近似于先来先服务似于先来先服务 长作业的优先权会随等待时间加长而升高长作业的优先权会随等待时间加长而升高,长作长作业也会得到执行业也会得到执行等待时间等待时间+要求服务时间要求服务时间 响应时间响应时间 要求服务时间要求服务时间 要求服务时间要求服务时间 把把CPU划分成若干时间片划分成若干时间片,并且按顺序赋给就绪并且按顺序赋给就绪队列中的每一个进程，进程轮流占有队列中的每一个进程，进程轮流占有CPU，当时间，当时间片用完时，即使进程未执行完毕，系统也剥夺该进片用完时，即使进程未执行完毕，系统也剥夺该进程的程的CPU，将该进程排在就绪队列末尾。同时系统，将该进程排在就绪队列末尾。同时系统选择另一个进程运行选择另一个进程运行 分时系统中常用时间片轮转法分时系统中常用时间片轮转法时间片选择问题：时间片选择问题：固定时间片、可变时间片固定时间片、可变时间片确定时间片大小的因素：确定时间片大小的因素：系统响应时间、就绪进程个数、系统响应时间、就绪进程个数、CPU能力能力 5.时间片轮转调度算法时间片轮转调度算法6.多队列反馈调度算法：多队列反馈调度算法：系统按优先级设置多级就绪队列第一级优先级最高系统按优先级设置多级就绪队列第一级优先级最高 各就绪队列分配不同的时间片各就绪队列分配不同的时间片,优先级高的第一级队优先级高的第一级队列时间片最小列时间片最小,随着队列优先级的降低随着队列优先级的降低,时间片加大时间片加大 各个队列按照先进先出调度算法各个队列按照先进先出调度算法 一个新进程就绪后进入第一级就绪队列一个新进程就绪后进入第一级就绪队列 进程由于等待事件而放弃进程由于等待事件而放弃CPU后后,进入等待队列进入等待队列,一一旦等待的事件发生旦等待的事件发生,则回到原来的就绪队列则回到原来的就绪队列 当有一个优先级更高的进程就绪时当有一个优先级更高的进程就绪时,可以抢占可以抢占CPU,被抢占进程回到原来一级就绪队列末尾被抢占进程回到原来一级就绪队列末尾 当第一级队列空时当第一级队列空时,就去调度第二级队列就去调度第二级队列,如此类推如此类推 时间片用完后进程放弃时间片用完后进程放弃CPU,进入下一级就绪队列进入下一级就绪队列 实时系统中实时系统中,对实时进程的调度有截止时间的要求对实时进程的调度有截止时间的要求1.实现实时调度的基本条件实现实时调度的基本条件 1)提供必要的信息提供必要的信息 就绪时间就绪时间、开始截止时间开始截止时间或或完成截止时间完成截止时间、处理时处理时间间、资源要求资源要求、优先级优先级(硬实时任务赋绝对优先级硬实时任务赋绝对优先级)。2)系统处理速度快系统处理速度快 若系统中有若系统中有m 个周期性硬实时任务个周期性硬实时任务,处理时间为处理时间为Ci周期时间为周期时间为Pi,则处理机处理速度应达到可调度条件则处理机处理速度应达到可调度条件:1 (单处理机单处理机)n (多处理机多处理机)3)采用抢占式调度机制以满足对截止时间的要求采用抢占式调度机制以满足对截止时间的要求 4)具有快速切换机制具有快速切换机制:快速中断响应、快速任务分派快速中断响应、快速任务分派3.3 实时调度实时调度CiPii=1nCiPii=1n2.实时调度算法的分类实时调度算法的分类 1)非抢占式调度算法非抢占式调度算法 非抢占式轮转调度算法非抢占式轮转调度算法(响应时间数秒到数十秒响应时间数秒到数十秒)轮转一圈后调度轮转一圈后调度 非抢占式优先权调度算法非抢占式优先权调度算法(响应时间数百毫秒响应时间数百毫秒)当前进程完成当前进程完成(或被阻塞或被阻塞)后调度后调度 2)抢占式调度算法抢占式调度算法 严格要求的实时系统严格要求的实时系统,响应时间在数十毫秒以内响应时间在数十毫秒以内 基于时钟中断的抢占式调度算法基于时钟中断的抢占式调度算法 时钟中断到来时调度时钟中断到来时调度 立即抢占的优先权调度算法立即抢占的优先权调度算法 立即剥夺当前进程立即剥夺当前进程 调度时间见调度时间见P 83 图图3-63.几种常见的实时调度算法几种常见的实时调度算法 1)最早截止时间优先算法最早截止时间优先算法(Earliest Deadline First)根据任务的开始截止时间确定优先级。根据任务的开始截止时间确定优先级。2)最低松弛度优先算法最低松弛度优先算法(Least Laxity First)根据任务的松弛度根据任务的松弛度(紧急程度紧急程度)确定优先级确定优先级 根据任务完成截止时间和根据任务完成截止时间和本身运行时间本身运行时间确定松弛度确定松弛度 松弛度松弛度=必须完成时间必须完成时间-本身运行时间本身运行时间-当前时间当前时间 P 85 图图 3-9 保存现场保存现场:顺序保存进程的上下文顺序保存进程的上下文,包括程序计包括程序计数器和其它寄存器数器和其它寄存器 用新状态和相关信息更新正在运行进程的用新状态和相关信息更新正在运行进程的PCB 把该进程移至合适的队列把该进程移至合适的队列-就绪、阻塞就绪、阻塞 选择另一个要执行的进程选择另一个要执行的进程,更新该进程的更新该进程的PCB 从被选中进程中重装入从被选中进程中重装入 CPU 上下文上下文,恢复现场恢复现场 若无就绪进程若无就绪进程,系统会安排一个闲逛进程系统会安排一个闲逛进程(idle),一直运行一直运行,在执行过程中可接收中断。在执行过程中可接收中断。3.4 CPU调度的实现调度的实现操作系统的核心操作系统的核心 向上提供无中断的虚拟机器向上提供无中断的虚拟机器,在核心内不允许中断在核心内不允许中断特点特点:核心常驻内存核心常驻内存,短小精焊短小精焊,为进程运行提供舞台为进程运行提供舞台 核心的组成核心的组成中断处理中断处理:时钟、时钟、I/O、虚拟存储器、虚拟存储器进程管理进程管理:调度调度 控制控制 通讯通讯 互斥互斥 同步等同步等原语管理原语管理:提供一系列原语提供一系列原语,同步同步,通信通信,创建创建,撤消等撤消等队列管理队列管理:中断之后调度之前中断之后调度之前(运行运行-就绪就绪-等待队列等待队列)现场管理现场管理:保存现场、恢复现场保存现场、恢复现场时钟管理时钟管理:绝对时钟、间隔时钟、绝对时钟、间隔时钟、虚时钟虚时钟 保存现场、分析中断源保存现场、分析中断源 处理中断处理中断原语管理、队列管理、时钟管理、进程调度原语管理、队列管理、时钟管理、进程调度 恢复现场恢复现场中断中断核心入口核心入口核心处理流程核心处理流程 唯一入口唯一入口:中断中断,由硬件完成由硬件完成 作业作业:P101 2,3,53.5死锁死锁死锁的基本概念死锁的基本概念死锁的解决方案死锁的解决方案 （预防，避免，检测及解除）（预防，避免，检测及解除）资源分配图资源分配图3.5.1 死锁的基本概念死锁的基本概念死锁死锁(Deadlock)的定义：的定义：一组进程中，每个进程都无限一组进程中，每个进程都无限等待等待被该组被该组进程中进程中另一进程所占有的资源另一进程所占有的资源，因而永远无法，因而永远无法得到的资源，这种现象称为进程死锁，这一组得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程进程就称为死锁进程说明说明:参与死锁的进程最少是两个参与死锁的进程最少是两个参与死锁的进程至少有两个已经占有资源参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的所有进程都在等待资源注意：注意：如果死锁发生，会浪费大量系统资源，如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。甚至导致系统崩溃。死锁产生的原因死锁产生的原因1.竞争资源引起竞争资源引起永久性资源永久性资源:可被多个进程多次使用可被多个进程多次使用(可再用资源可再用资源)剥夺性资源剥夺性资源(CPU、内存）、内存）非剥夺性资源非剥夺性资源(磁带机、打印机磁带机、打印机)竞争非剥夺性资源会引起死锁竞争非剥夺性资源会引起死锁临时性资源临时性资源:只可使用一次的资源；只可使用一次的资源；如信号量如信号量,中断信号中断信号,同步信号等同步信号等(可消耗性资源可消耗性资源)竞争临时性资源也会引起死锁竞争临时性资源也会引起死锁2.进程推进顺序不当引起进程推进顺序不当引起 对资源采用对资源采用“申请申请-分配分配-使用使用-释放释放”模式模式,由由于推进顺序不当两进程都要申请对方已占有的资源于推进顺序不当两进程都要申请对方已占有的资源P1：申请打印机申请打印机申请扫描仪申请扫描仪使用使用释放打印机释放打印机释放扫描仪释放扫描仪P2：申请扫描仪申请扫描仪申请打印机申请打印机使用使用释放打印机释放打印机释放扫描仪释放扫描仪死锁的例子死锁的例子:竞争非剥夺性资源进程推进顺序不当引起死锁竞争非剥夺性资源进程推进顺序不当引起死锁Req(R1)Req(R2)Rel(R1)Rel(R2)Rel(R1)Rel(R2)Req(R1)Req(R2)P2P1不安全区不安全区竞争非剥夺性资源竞争非剥夺性资源推进顺序不当推进顺序不当进入进入不安全区不安全区3.5.2产生死锁的四个必要条件产生死锁的四个必要条件1)互斥条件（资源独占）：互斥条件（资源独占）：一个资源每次只能给一个进程使用一个资源每次只能给一个进程使用2)请求和保持条件请求和保持条件:(部分分配部分分配,占有申请占有申请)在申请新资源的同时保持对原有资源的占有在申请新资源的同时保持对原有资源的占有3)不可剥夺条件（不可强占）：不可剥夺条件（不可强占）：资源申请者不能强行的从资源占有者手中夺资源申请者不能强行的从资源占有者手中夺取资源取资源,资源只能由占有者自愿释放资源只能由占有者自愿释放4)循环等待条件：循环等待条件：存在进程存在进程-等待资源环形链等待资源环形链 P1,P2,Pn,其中其中P1等待等待P2占有的资源占有的资源,P2等待等待P3占有的资源占有的资源,Pn等待等待P1占有的资源。占有的资源。3.6 死锁的预防死锁的预防 3.6.1 强限制预防强限制预防 确定资源分配算法确定资源分配算法,保证不发生死锁。做法保证不发生死锁。做法是破坏产生死锁的四个必要条件之一。是破坏产生死锁的四个必要条件之一。1.破坏破坏“请求和保持请求和保持(部分分配部分分配)”条件条件 每个进程运行前必须一次性申请运行期所需每个进程运行前必须一次性申请运行期所需全部资源全部资源,若所需资源均可满足则全部分配。该若所需资源均可满足则全部分配。该进程运行中不再请求资源进程运行中不再请求资源,屏弃请求条件。屏弃请求条件。简单、安全简单、安全;但资源利用率低但资源利用率低,要长期等待。要长期等待。2.破坏破坏“不可剥夺不可剥夺”条件条件 在允许进程动态申请资源前提下在允许进程动态申请资源前提下,规定规定:某某进程在申请新的资源不能立即满足而被阻塞之进程在申请新的资源不能立即满足而被阻塞之前前,必须释放已占有的资源必须释放已占有的资源(可能造成前一段工作可能造成前一段工作失效失效),若需要再重新申请若需要再重新申请(增加开销增加开销)。3.破坏破坏“循环等待循环等待”条件条件 采用资源有序分配法采用资源有序分配法:允许进程动态申请资允许进程动态申请资源源,对系统中所有资源编号对系统中所有资源编号,进程申请资源时应进程申请资源时应严格按资源编号递增次序进行严格按资源编号递增次序进行,否则不予分配。否则不予分配。P1：申请申请1申请申请3申请申请4P2：申请申请2申请申请4申请申请8Pn：申请申请1申请申请2申请申请8缺点缺点:资源利用仍不充分资源利用仍不充分3.6.2 避免死锁的避免死锁的银行家银行家算法算法 前面的三种方法由于前面的三种方法由于限制太强限制太强,资源利用率资源利用率都不太高。能否放宽限制条件？都不太高。能否放宽限制条件？E.W.Dijkstra于于1968年提出年提出银行家算法银行家算法,此此算法要事先知道每个进程对算法要事先知道每个进程对资源的资源的最大需求量最大需求量;算法的基本思路算法的基本思路:允许进程动态申请资源允许进程动态申请资源,但在每但在每次分配资源前先对本次分配的安全性进行检查次分配资源前先对本次分配的安全性进行检查,以判断这种分配是否可能导致死锁以判断这种分配是否可能导致死锁,若分配可能若分配可能导致系统死锁导致系统死锁,则不予分配则不予分配,否则分配该资源。否则分配该资源。(检查每次分配后是否仍存在安全分配检查每次分配后是否仍存在安全分配序列序列)显然显然,此法避免了死锁且资源利用率高。此法避免了死锁且资源利用率高。1.安全序列：安全序列：如果进程序列如果进程序列P1，Pn对每个对每个Pi(1in)进程进程,它以后尚需要的资源量不超过系统当前剩余资源量与它以后尚需要的资源量不超过系统当前剩余资源量与所有所有Pj(j Available(2,3,0),让让P4等待等待4)若若P0请求资源请求资源,发出请求向量发出请求向量Request(0,2,0)假定分配假定分配,资源为资源为:检查此刻的安全性：检查此刻的安全性：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检查此刻的安全性检查此刻的安全性 Max Allocation Need Available 进程进程 A B 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 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 true3.7 死锁的检测与解除死锁的检测与解除 允许死锁发生，系统必须提供检测和解除死锁允许死锁发生，系统必须提供检测和解除死锁的手段的手段,操作系统应不断监视系统进展情况，判断死操作系统应不断监视系统进展情况，判断死锁是否发生。锁是否发生。3.7.1死锁的检测死锁的检测1.资源分配图资源分配图用有向图描述进程的死锁用有向图描述进程的死锁:准确、形象准确、形象 系统由若干类资源构成，一类资源称为一个资源类；系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例。每个资源类中包含若干个同种资源，称为资源实例。二元组二元组G=（V，E）V：结点集，分为：结点集，分为P，R两部分两部分 P=p1,p2,pn R=r1,r2,rm E：边的集合：边的集合,其元素为有序二元组其元素为有序二元组 分配边分配边(rj,pi):资源实例资源实例进程的一条有向边进程的一条有向边申请边申请边(pi,rj):进程进程资源类的一条有向边资源类的一条有向边有环有死锁有环无死锁2.死锁定理死锁定理 如果资源分配图中没有环路如果资源分配图中没有环路,则系统中没有死锁则系统中没有死锁,如果图中存在环路则系统中可能存在死锁。如果图中存在环路则系统中可能存在死锁。如果每个资源类中只包含一个资源实例如果每个资源类中只包含一个资源实例,则资源则资源分配图环路是死锁存在的充分必要条件。分配图环路是死锁存在的充分必要条件。资源分配图化简方法：资源分配图化简方法：1）找一个非孤立点进程结点且只有分配边，去掉分）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点。配边，将其变为孤立结点。2）再把相应的资源分配给一个等待该资源的进程，）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边。即将某进程的申请边变为分配边。3）重复）重复(1)(2)操作直到无法再化简操作直到无法再化简,若所有若所有结点都为结点都为孤立结点则无孤立结点则无死锁死锁,否则死锁发生否则死锁发生3.7.2死锁的解除死锁的解除 一旦死锁发生则采取专门的措施，解除一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。死锁并以最小的代价恢复操作系统运行。死锁的解除死锁的解除(关键是代价最小关键是代价最小)：1）重新启动）重新启动2）撤消进程）撤消进程3）剥夺资源）剥夺资源4）进程回退）进程回退1.处理机调度处理机调度 (1)高级调度高级调度(作业调度接纳调度或长程调度作业调度接纳调度或长程调度)将后备队列中作业调入内存将后备队列中作业调入内存,并创建进程。并创建进程。(2)低级调度低级调度(进程调度进程调度,短程调度短程调度)从就绪队列中选中一进程从就绪队列中选中一进程,把把CPU使用权交给它。使用权交给它。(3)中级调度中级调度:内存紧张时将内存的进程挂起调到外存内存紧张时将内存的进程挂起调到外存 或内存稍有空闲时将它激活重新调入内存或内存稍有空闲时将它激活重新调入内存 2.进程调度方式进程调度方式 (1)非抢占方式非抢占方式(Non preemptive mode)(2)抢占方式抢占方式(Preemptive mode)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 First)(2)最低松弛度优先算法最低松弛度优先算法(Least Laxity First)6.调度的实现过程调度的实现过程 保存现进程现场、更新它的保存现进程现场、更新它的PCB、把它移至合适队列、把它移至合适队列 选择要执行的进程、更新它的选择要执行的进程、更新它的PCB、恢复新进程现场、恢复新进程现场7.死锁死锁(Deadlock)的定义：的定义：进程组中各进程都无限等待被该组另一进程所占的资源进程组中各进程都无限等待被该组另一进程所占的资源注意：注意：参与死锁的进程最少是两个、至少有两个参与死锁的进程最少是两个、至少有两个 已占有资源、该组所有进程都在等待资源已占有资源、该组所有进程都在等待资源8.产生死锁的四个必要条件产生死锁的四个必要条件 (1)互斥条件互斥条件(资源独占资源独占):一个资源只能给一个进程使用一个资源只能给一个进程使用 (2)请求和保持条件请求和保持条件:部分分配部分分配,保持原资源申请新资源保持原资源申请新资源 (3)不可剥夺条件不可剥夺条件:(不可强占不可强占,只能由占有者自愿释放只能由占有者自愿释放)(4)循环等待条件循环等待条件:形成等待环形成等待环9.死锁的预防死锁的预防(强限制强限制)破坏产生死锁的四个必要条件之一破坏产生死锁的四个必要条件之一(后后3条条)10.避免死锁的银行家算法避免死锁的银行家算法(宽限制宽限制)检查每次分配后是否仍存在安全分配序列检查每次分配后是否仍存在安全分配序列 避免了死锁且资源利用率高避免了死锁且资源利用率高11.死锁的检测死锁的检测 允许死锁发生允许死锁发生,OS应不断检测死锁是否发生应不断检测死锁是否发生12.资源分配图资源分配图结点集结点集:各进程结点各进程结点P,各资源类结点各资源类结点R边集边集:元素为有序二元组元素为有序二元组,分配边分配边(rj,pi)申请边申请边(pi,rj)13.死锁定理死锁定理资源分配图无环路资源分配图无环路,则没有死锁则没有死锁,有环路则可能存在死锁有环路则可能存在死锁 若各资源类只含一个资源若各资源类只含一个资源,环路是死锁的充分必要条件环路是死锁的充分必要条件14.资源分配图化简方法资源分配图化简方法()(1)找只有分配边的进程结点找只有分配边的进程结点,去掉分配边变为孤立结点去掉分配边变为孤立结点 (2)把相应的资源分配给等待进程把相应的资源分配给等待进程,申请边变为分配边申请边变为分配边 重复重复(1)(2)直到无法再化简直到无法再化简,若仍有环路则死锁发生若仍有环路则死锁发生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）上机安排上机安排:院机房二楼院机房二楼电科电科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 改为：改为：进程调度过程进程调度过程schedulerpd:=find;选优先数最小的选优先数最小的pdpdnilpd=nil and exe=nilpd优优exe优优exe=nilpcbexe.status:=r;pcbp