操作系统第3章.ppt

1、第三章 调度与死锁,在多道程序环境下，进程数目往往多于处理机数目，这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。,高级、中级和低级调度,高级调度的主要任务是按给定的原则从外存后备作业中挑选若干作业调入内存，为它们建立进程并分配必要的资源，以使它们获得竞争处理机的权利。 中级调度的主要任务是按给定的原则将处于外存对换区中的具备运行条件的就绪进程调入内存，或将内存中处于就绪状态或阻塞状态的进程交换到外存对换区中。 低级调度的主要任务是按照某种原则选取一个处于就绪状态的进程，将处理机分配给它。,进程调度算法,1进程调度 进程调度的任务是控制协调进程对CPU的竞争即按一

2、定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程,2确定算法的原则,具有公平性 资源利用率高（特别是CPU利用率） 在交互式系统情况下要追求响应时间（越短越好） 在批处理系统情况下要追求系统吞吐量,3各种进程调度算法,先来先服务进程调度算法（FCFS） 按照进程就绪的先后次序来调度进程 优点:实现简单 缺点:没考虑进程的优先级,（1）先来先服务（FCFS）算法 先来先服务作业调度算法是一种较简单的作业调度算法，即每次调度是从后备作业队列中选择一个最先进入该队列的作业，将它调入内存，分配资源、创建相应的进程，放入进程就绪队列准备运行。 FCFS算法利于长作业，不利于短作业，

3、而大多数的作业是I/O繁忙的短作业。以FCFS作为主调度算法是不常用的。,短作业优先调度算法是指操作系统在进行作业调度时以作业长短作为优先级进行调度。该调度算法可以照顾到实际上占作业总数绝大部分的短作业，使它们能比长作业优先调度执行。这时后备作业队列按作业优先级由高到低顺序排列，当作业进入后备队列时要按该作业优先级放置到后备队列相应的位置。 实践证明，该调度算法的性能是最好的，单位时间的作业吞吐量也最大，但也存在缺点：对长作业极为不利。,（2）短作业优先调度算法（SJF）,（3）动态优先级调度算法 当几个作业几乎同时进入后备队列时，短作业的优先级高，它先被调度执行。但随着时间的推移，长作业的优

4、先级逐渐增大，长作业就可能在后进入后备队列的短作业之前被操作系统调度执行。 分析动态优先级调度算法，可以认为该算法既照顾了短作业，又不会使长作业长期得不到服务，从而实现了一种良好的折中。,高优先权优先调度算法,优先选择就绪队列中优先级最高的进程投入运行 优先级根据优先数来决定,确定优先数的方法 静态优先数法： 在进程创建时指定优先数，在进程运行时优先数不变 动态优先数法： 在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变,时间片轮转程序调度算法(RRRound Robin),把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CP

5、U，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行,分时系统中常用时间片轮转法,时间片选择问题： 固定时间片 可变时间片 与时间片大小有关的因素： 系统响应时间 就绪进程个数 CPU能力,时间片轮转调度算法,多队列反馈调度算法：,将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间片越小，级别越低，时间片越长，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列，.当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进

6、程第一次就绪时，进入第一级队列,* 首先系统中设置多个就绪队列，并为各个队列赋予不同的优先级。 * 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大 * 各个队列按照先进先出调度算法 一个新进程就绪后进入第一级队列的末尾，按FCFS原则排队等待调度，当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，如到第n队列，便采取按时间片轮转的方式运行。,* 进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列 * 当有一个优先级更高的进程就绪时

7、，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾 * 当第一级队列空时，就去调度第二级队列，如此类推 * 当时间片到后，进程放弃CPU，回到下一级队列,进程调度的时机,当一个进程运行完毕，或由于某种错误而终止运行 当一个进程在运行中处于等待状态（等待I/O） 分时系统中时间片到,进程调度的时机-2,当有一个优先级更高的进程就绪（可抢占式），例如：新创建一个进程，一个等待进程变成就绪 在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语）,有5个批处理作业（A，B，C，D，E）几乎同时到达一个计算中心，估计的运行时间分别为2，4，6，8，10分钟，它们的优先数分别为1，2

8、，3，4，5（1为最低优先级），对下面的各种调度算法分别计算作业的平均周转时间。 （1）最高优先级优先； （2）时间片轮转（时间片为2分钟）； （3）FIFO（作业到达顺序为C，D，B，E，A）； （4）短作业优先。,例：假设某多道系统提供100K主存空间，对主存采用“最先适应”分配分区算法的可变管理方式，有下列作业序列：,计算在各种调度算法下，作业被选中的次序 假定系统在10：30时开始调度，计算在各种算法下，作业被选中的时间，开始执行的时间，以及周转时间（忽略调度所需时间，且作业都是计算型的）,先来先服务,最短计算时间优先,两种占用CPU的方式,可剥夺式（可抢占式Preemptive）：

9、当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用 不可剥夺式（不可抢占式 Non-preemptive ）： 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去,例：在单CPU和两台输入/输出设备（I1，I2）的多道程序设计环境下，同时投入3个作业A、B、C运行。这3个作业对CPU和输入/输出设备的使用顺序和时间如下： A：I2(30ms);CPU(10ms);I1(30ms);CPU(10ms);I2(20ms) B: I1(20ms);CPU(20ms);I2(40ms) C: CPU(30ms);I1(20m

10、s);CPU(10ms);I1(10ms) 假定CPU、I1、I2都能并行工作，A优先级最高，B次之，C优先级最低，优先级高的作业可以抢占优先级低的作业的CPU但不抢占I1和I2，试求： （1）3个作业从投入到完成分别需要的时间。 （2）从投入到完成的CPU利用率。 （3）I/O设备利用率。,1.支持多道程序设计的操作系统在运行过程中,不断地选择新进程运行来实现CPU的共享,但其中( )不是引起操作系统选择新进程的直接原因. A.运行进程的时间片用完 B.运行进程出错 C.运行进程要等待某一事件发生 D.有新进程进入就绪队列,2.为什么说多级反馈队列调度算法能较好地满足各类用户的需要? 1)对

11、于终端型作业用户而言,由于他们所提交的大多属于交互型作业,作业通常比较短小,系统只要能使这些作业在第1个队列所规定的时间片内完成,便可使终端型作业用户满意. 2)对于短批处理作业用户而言,他们的作业开始时像终端型作业一样的响应时间,对于稍长的作业,通常也只需要在第2个队列和第3个队列中各执行一个时间片即可完成,其周转时间仍然较短. 3)对于长批处理作业用户而言,他们的长作业将依次在第1、2,直到第n个队列中运行,然后再按轮转方式运行,用户不必担心其作业长期得不到处理.,死锁,死锁的基本概念 死锁的解决方案 （预防，避免，检测及解除） 资源分配图,死锁的现象,死锁的基本概念,死锁的定义： 一组进

12、程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到资源，这种现象称为进程死锁，这一组进程就称为死锁进程。,死锁（Deadlock）,关于死锁的一些结论： 参与死锁的进程最少是两个 （两个以上进程才会出现死锁） 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。,产生死锁的四个必要条件,互斥条件（资源独占） 不可强占条件（不可剥夺） 请求和保持条件（部分分配，占有申请） 环路等待条件,1) 互斥条件（资源独占）：,一个资源每次只能给一个进程使用 2) 不可

13、强占条件（不可剥夺）： 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放,3) 请求和保持条件：（部分分配，占有申请）,一个进程在申请新的资源的同时保持对原有资源的占有。 （只有这样才是动态申请，动态分配）,4) 环路等待条件：,存在一个进程等待队列 P1 , P2 , , Pn, 其中P1等待P2占有的资源，P2等待P3占有的资源，Pn等待P1占有的资源，形成一个进程等待环路。,死锁的解决方案,1. 产生死锁的例子 申请不同类型资源产生死锁,死锁产生例子1：,我们先来看一个申请不同类型资源的死锁例子，假定有两个进程Pl和P2都要修改文件F，修改时都需要一条暂时存放信息的

14、磁带，而只有一台磁带机T可用。于是Pl和P2。可有如下形式：,分析：从上面的申请-释放过程可以看出，进程Pl和P2有可能“同时”分别到达rl和r2处，例如，P2首先得到T，然后Pl得到F，接着Pl到达r1，最后P2到达r2，此时，若Pl继续运行，则占有F的进程Pl将阻塞在T上，若P2继续运行，则占有T的进程P2将阻塞在F上，如果P2不能前进，则P1也不能继续下去，反之亦然。我们说这两个进程处在死锁状态。,简单的死锁例子,申请同类资源产生死锁（如内存）,设有资源R，R有m个分配单位，由n个进程P1,P2,Pn（n m）共享。假设每个进程对R的申请和释放符合下列原则： * 一次只能申请一个单位 *

15、 满足总申请后才能使用 * 使用完后一次性释放,申请同类资源产生死锁（如内存）,m=2，n=3 资源分配不当导致死锁产生。,解决死锁的方法,不让死锁发生： 静态策略： 动态策略： 让死锁发生：,死锁预防,定义： 在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。,死锁预防,破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请。,死锁预防,破坏“请求和保持”条件 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一

16、次性分配。,死锁预防,破坏“环路等待”条件 采用资源有序分配法： 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。,破坏“循环等待”条件,死锁避免定义,定义： 在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。,安全状态与不安全状态,安全状态： 如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安全状态。,死锁避免,安全序列： 一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余

17、资源量与所有进程Pj (j i )当前占有资源量之和，系统处于安全状态。 (安全状态一定是没有死锁发生的),安全状态与不安全状态,不安全状态:不存在一个安全序列，不安全状态可能导致死锁。,银行家算法,n：系统中进程的总数 m：资源类总数 Available: ARRAY1.m of integer; Max: ARRAY1.n,1.m of integer;,银行家算法,Allocation: ARRAY1.n,1.m of integer; Need: ARRAY1.n,1.m of integer; Request: ARRAY1.n,1.m of integer;,银行家算法,简记符号：

18、 Available可利用资源量 Maxi最大需求量 Allocationi分配量 Needi需求量 Requesti请求量,银行家算法,当进程pi提出资源申请时，系统执行下列步骤： (1)若RequestiNeedi,转（2）； 否则错误返回 （2）若RequestiAvailable, 转（3）；否则进程等待,(3）假设系统分配了资源，则有： Available:=Available-Requesti; Allocationi:=Allocationi+Requesti; Needi:=Needi-Requesti (4)若系统新状态是安全的，则分配完成 若系统新状态是不安全的，则恢复原状

19、态，进程等待,安全性算法,为进行安全性检查，定义数据结构： Work:ARRAY1.m of integer; Finish:ARRAY1.n of Boolean;,安全性算法,安全性检查的步骤： (1) Work:=Available; Finish:=false; (2) 寻找满足条件的i： a.Finishi=false; b.NeediWork; 如果不存在，则转(4),安全性算法,(3) Work:=Work+Allocationi; Finishi:=true; 转(1) (4) 若对所有i,Finishi=true,则系统处于安全状态，否则处于不安全状态,安全性算法,银行家算法

20、之例,假定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-15 所示。,T0时刻的资源分配表,(1) T0时刻的安全性：,T0时刻的安全序列,(2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图

21、3-15 中的圆括号所示。 再利用安全性算法检查此时系统是否安全。,P1申请资源时的安全性检查,(3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)，让P4等待。 (4) P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0); 系统暂时先假定可

22、为P0分配资源，并修改有关数据，如图 3-18 所示。,为P0分配资源后的有关资源数据,【作业：】:某系统有A、B、C、D这4类资源供5个进程共享，进程对资源的需求和分配情况如下表：,现在系统还剩资源A类1个，B类5个，C类2个和D类0个，请按银行家算法回答： 1）现在系统是否处于安全状态？ 2）如果现在进程P2提出需要（0，4，2，0）个资源的要求，系统能否满足它的请求？,3.7.1死锁检测： 允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生。 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。,3.7死锁的检测与解除,死锁的检测与解除,检测时机： 当进程等待

23、时检测死锁 （其缺点是系统的开销大） 定时检测 系统资源利用率下降时检测死锁,死锁的检测与解除,死锁检测算法 * 每个进程和资源指定唯一编号 * 设置一张资源分配表 记录各进程与其占用资源之间的关系 * 设置一张进程等待表 记录各进程与要申请资源之间的关系,死锁的检测与解除,死锁检测算法 资源分配表 进程等待表 r1 p2 p1 r1 r2 p5 p2 r3 r3 p4 p4 r4 r4 p1 ,3.7.2死锁的解除：,重要的是以最小的代价恢复系统的运行。方法如下： 1）重新启动 2）撤消进程 3）剥夺资源 4）进程回退,1.资源分配图,用有向图描述进程的死锁 准确、形象 系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例。,资源分配图,二元组G=（V，E） V：结点集，分为P，R两部分 P=p1,p2,pn R=r1,r2,rm E：边的集合，其元素为有序二元组 (pi,rj)或(rj,pi),资源分配图,表示法 资源类（资源的不同类型） 用方框表示 资源实例（存在于每个资源中） 用方框中的黑圆点表示 进程 用圆圈中加进程名表示,资源分配图,分配边： 资源实例进程的一条有向边 申请边： 进程资源类的一条有向边,有环有死锁,有环无死锁,2.死锁定理 如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则