处理机调度与死锁.ppt

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

1、东北农业大学王艳,操作系统原理,CPU,进程调度,第三章 处理机调度与死锁,3.1 处理机调度的层次和调度算法的目标,3.1.1 处理机调度的层次,1 高级调度 长程调度、作业调度，调度对象为作业。,低级调度 进程调度、短程调度，调度对象为进程。,3 中级调度 内存调度，为提高内存利用率和系统吞吐量。,第三章 处理机调度与死锁,第三章 处理机调度与死锁,3.1 处理机调度的层次和调度算法的目标,3.1.2 处理机算法的目标,1 处理机算法的共同目标,（1）资源利用率,（2）公平性,（3）平衡性,（4）策略强制执行性,第三章 处理机调度与死锁,3.1 处理机调度的层次和调度算法的目标,3.1.2

2、 处理机算法的目标,2 批处理系统的目标,（1）平均周转时间短,作业提交开始到作业完成为止的时间间隔,系统：作业的平均周转时间尽可能少,用户：自己作业周转时间尽量少,指标：平均周转时间,指标：带权周转时间,第三章 处理机调度与死锁,作业平均周转时间（T）,带权平均周转时间（W）,n为作业数目，第i个作业的周转时间Ti Ei SiEi：作业完成时间 Si：作业提交时间,W（）,ri 为某作业i的实际执行时间,3.1 处理机调度的层次和调度算法的目标,3.1.2 处理机算法的目标,第三章 处理机调度与死锁,3.1 处理机调度的层次和调度算法的目标,3.1.2 处理机算法的目标,2 批处理系统的目标

3、,（2）系统吞吐量,（3）处理机利用率高,3 分时系统的目标,（1）响应时间快,（2）均衡性,4 实时系统的目标,（1）截止时间的保证,（2）可预测性,第三章 处理机调度与死锁,3.2 作业与作业调度,3.2.1 批处理系统中的作业,1 作业和作业步（1）作业（Job）：程序+数据+作业说明符（2）作业步：作业执行过程中的加工步骤,2 作业控制块（JCB）(1)作业存在的标识(2)保存系统对作业进行管理和调度的所有信息,第三章 处理机调度与死锁,3.2 作业与作业调度,3.2.1 批处理系统中的作业,3 作业运行的三个阶段和三种状态,后备状态运行状态完成状态,（1）三个阶段,收容阶段运行阶段完

4、成阶段,（2）三种状态,第三章 处理机调度与死锁,3.2 作业与作业调度,3.2.2 作业调度的主要任务,1 决定接纳多少个作业,多道程序度,2 接纳哪些作业,调度算法,第三章 处理机调度与死锁,3.2 作业与作业调度,3.2.3 先来先服务和短作业优先算法,1 先来先服务算法（1）FCFS：First Come First Serve（2）适用于作业、进程调度（3）选择最先进入的作业/进程（4）例子：,第三章 处理机调度与死锁,0,1,1,101,101,102,102,202,1,1,100,1,100,100,199,1.99,平均周转时间：t=100带权平均周转时间w=25.9975,

5、优点：实现简单（优待大作业）缺点：对短作业不利,3.2 作业与作业调度,3.2.3 先来先服务和短作业优先算法,第三章 处理机调度与死锁,2 短作业优先算法（1）SJ（P）F：Shortest Job（Process）First（2）适用于作业、进程调度（3）选择短的作业/进程（4）例子：,3.2 作业与作业调度,3.2.3 先来先服务和短作业优先算法,第三章 处理机调度与死锁,作业情况,算法,0,4,4,7,7,12,12,14,14,18,4,1,6,2,10,2,11,5.5,14,3.5,9,2.8,0,4,6,9,13,18,4,6,9,13,4,1,8,2.67,16,3.2,3,

6、1.5,9,2.25,8,2.14,3.2 作业与作业调度,3.2.3 先来先服务和短作业优先算法,第三章 处理机调度与死锁,1 优先级调度算法（PSA）,3.2 作业与作业调度,3.2.4 优先级调度算法和高响应比优先调度算法,先来先服务算法等待时间为优先级,短作业优先算法作业长短为优先级,优先级调度算法作业的紧迫程度,第三章 处理机调度与死锁,2 高响应比优先权调度算法（HRRN）,（1）HRRN是介于FCFS和SJP（F）之间的一种折中算法,（2）优先权,3.2 作业与作业调度,3.2.4 优先级调度算法和高响应比优先调度算法,优先权=（等待时间+要求服务时间）/要求服务时间,动态优先权

7、：随等待时间延长而增加,响应比R=（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间,第三章 处理机调度与死锁,2 高响应比优先权调度算法（HRRN）,（3）优点,等待时间相同，则处理时间短，优先级R高。,作业处理时间相同，则等待时间决定优先级R。,对于长作业，等待足够时间，R增加，可获得处理机。,SJF,FCFS,（4）缺点,增加系统开销,3.2 作业与作业调度,3.2.4 优先级调度算法和高响应比优先调度算法,第三章 处理机调度与死锁,2 高响应比优先权调度算法（HRRN）,（5）例子,0,4,Rb=1，Rc=0.4Rd=0.5，Re=0,4,7,Rc=1，Rd=2，Re=0

8、.75,7,9,Rc=1.4，Re=1.25,9,14,14,18,4,1,6,2,12,2.4,6,3,14,3.5,8.4,2.38,3.2 作业与作业调度,3.2.4 优先级调度算法和高响应比优先调度算法,（1）FCFS,（2）SJ（P）F,（3）HRN,0,3,3,9,9,13,13,18,18,20,3,1,8,11,15,16,1.33,2.75,3,8,10.6,3.22,0,3,14,20,3,7,9,14,7,9,3,1,19,5,11,5,3.17,1.25,2.2,2.5,8.6,2.02,0,3,3,9,11,15,15,20,9,11,3,1,8,13,17,7,1.

9、33,3.25,3.4,3.5,9.6,2.496,第三章 处理机调度与死锁,3.3 进程调度,1 进程调度的任务(1)保存处理机现场信息(2)按某种算法选取进程(3)把处理机分配给进程,2 进程调度机制(1)排队器(2)分派器(3)上下文切换机制,3.3.1 进程调度的任务、机制和方式,第三章 处理机调度与死锁,3.3 进程调度,3 调度方式(1)非抢占式 引发进程调度的事件执行完毕、进程阻塞、执行原语 特点实现简单、开销小、不能立即执行,（2）抢占式 基本原则优先权原则、短作业（进程）优先、时间片原则 特点开销大、公平、响应及时,第三章 处理机调度与死锁,3.3 进程调度,3.3.2 轮转

10、调度算法（RR）,1 轮转法的基本原理,按FCFS将就绪进程排成一个就绪队列，进程按时间片轮流使用CPU。,3 时间片大小的确定 太长不能及时响应 太短频繁切换，降低CPU效率,2 进程切换时机,（1）时间片未完，进程已完成,（2）时间片完，进程未完成,第三章 处理机调度与死锁,第三章 处理机调度与死锁,第三章 处理机调度与死锁,3.3 进程调度,3.3.3 优先级调度算法,1 优先级调度算法类型（1）非抢占式优先权调度算法 批处理系统、实时性要求不高的实时系统（2）抢占式优先权算法 严格的实时系统，高性能的分时、批处理系统,第三章 处理机调度与死锁,3.3 进程调度,优先级调度算法,2 优先

11、级的类型,（1）静态优先级,进程创建时确定，在进程整个运行期间保持不变。,进程类型,进程对资源的需求,用户要求,简单易行，系统开销小，但不够精确，优先级低的进程长期不被调用,第三章 处理机调度与死锁,3.3 进程调度,优先级调度算法,2 优先级的类型,（2）动态优先级,进程创建之初确定，随进程推进或等待时间的增加而改变,随等待时间的增长，优先级相应提高,抢占式调度方式中，规定当前进程的优先级随运行 时间的推移而下降,第三章 处理机调度与死锁,3.3 进程调度,3.3.4 多队列调度算法,就绪队列多个,不同队列不同优先级,不同队列不同调度算法,第三章 处理机调度与死锁,3.3 进程调度,3.3.

12、5 多级反馈队列调度算法,1 调度机制,（1）建立多个就绪队列，优先级递减,第三章 处理机调度与死锁,3.3 进程调度,3.3.5 多级反馈队列调度算法,1 调度机制,（2）每个队列都采用FCFS算法，第n个队列 采用RR方式调度,（3）按队列优先级调度。首先调度最高优先级 队列中的进程运行，仅当第一队列空闲时 才调度第二队列中的进程运行。,第三章 处理机调度与死锁,3.3 进程调度,3.3.5 多级反馈队列调度算法,2 调度算法性能,若规定第一个队列的时间片略大于多数人机交互所需处理时间时，便能较好满足各种类型用户的需要。,终端型用户,短批处理作业用户,长批处理作业用户,第三章 处理机调度与

13、死锁,3.5 产生死锁的原因和必要条件,1 典型死锁的例子,P1：申请R1 申请R2,P2：申请R2 申请R1,P1拥有R1申请R2，P2拥有R2申请R1,第三章 处理机调度与死锁,3.5 产生死锁的原因和必要条件,3.5.1 资源问题,1 可重用性资源和消耗性资源,(1)可重用性资源：供用户使用多次的资源,一个可重用性资源单元只能分配给一个进程使用,请求资源使用资源释放资源,系统中每一类可重用性资源中的单元数目是相对 固定的，进程在运行期间既不能创建也不能删除,计算机系统中大多数资源都属于可重用性资源,第三章 处理机调度与死锁,3.5 产生死锁的原因和必要条件,3.5.1 资源问题,1 可重

14、用性资源和消耗性资源,(2)可消耗性资源：临时资源,可以请求若干个可消耗性资源单元,进程运行过程中，可以不断的创造可消耗性资源的单元,每一类可消耗性资源中的单元数目是可以不断变化的,生产者创建，消费者进程消耗,第三章 处理机调度与死锁,3.5 产生死锁的原因和必要条件,3.5.1 资源问题,2 可抢占性资源和不可抢占性资源,(1)可抢占性资源,磁带机、打印机等,（2）不可抢占性资源,CPU、主存等，此类资源不会引起死锁,第三章 处理机调度与死锁,3.5 产生死锁的原因和必要条件,3.5.计算机系统中的死锁,竞争非剥夺性资源,R1：磁带机 R2：打印机,第三章 处理机调度与死锁,3.5 产生死锁

15、的原因和必要条件,3.5.计算机系统中的死锁,竞争可消耗性资源,P1：Release(S1)；Reqaest(S3)；P2：Release(S2)；Request(S1)；P3：Release(S3)；Request(S2)；,P1：Request(S3)；Release(S1)；P2：Request(S1)；Release(S2)；P3：Request(S2)；Release(S3)；,第三章 处理机调度与死锁,3.5 产生死锁的原因和必要条件,3.5.计算机系统中的死锁,进程间推进顺序非法,（）合法,P1：Request(R1)；Request(R2)；P1：Releast(R1)；Rel

16、ease(R2)；P2：Request(R2)；Request(R1)；P2：Release(R2)；Release(R1)；,第三章 处理机调度与死锁,3.5 产生死锁的原因和必要条件,3.5.计算机系统中的死锁,（2）进程间推进顺序非法,第三章 处理机调度与死锁,3.5 产生死锁的原因和必要条件,3.5.计算机系统中的死锁,（2）进程间推进顺序非法,若并发进程P1和P2按曲线所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R1，P2保持了资源R2，系统处于不安全状态。因为这时两进程再向前推进，便可能发生死锁。例如，当P1运行到P1：Request(R2)时，将因R2已被P2占用而

17、阻塞；当P2运行到P2：Request(R1)时，也将因R1已被P1占用而阻塞，于是发生了进程死锁。,第三章 处理机调度与死锁,3.5 产生死锁的原因和必要条件,3.5.死锁的定义、必要条件和处理方法,互斥条件,请求和保持条件,不剥夺条件,环路等待条件,死锁：多个进程因共享资源而产生的僵局，没有外 力作用将无法向前推进。,第三章 处理机调度与死锁,3.5 产生死锁的原因和必要条件,3.5.3 处理死锁的基本方法,1 预防死锁,2 避免死锁,3 检测死锁,4 解除死锁,0 鸵鸟策略,出现频率极少时，置之不理,设置条件，破坏死条件之一,分配资源时避免进入不安全状态,允许发生，及时检测并消除,撤销挂

18、起进程，回收资源,第三章 处理机调度与死锁,1 产生死锁的必要条件,互斥条件,请求和保持条件,不剥夺条件,环路等待条件,第三章 处理机调度与死锁,2 处理死锁的基本方法,1 预防死锁,2 避免死锁,3 检测死锁,4 解除死锁,0 鸵鸟策略,第三章 处理机调度与死锁,1 摒弃“请求和保持”条件,（1）思想：要么分配所有资源，要么不分配,3.6.1 预防死锁,（2）优点：简单易实现、安全性好,（3）缺点：资源浪费严重、进程延迟进行,3.6 预防死锁的方法,第三章 处理机调度与死锁,3.6 预防死锁的方法,2 摒弃“不剥夺”条件,（1）思想：逐个提出对资源的请求，有需求不满足时 释放资源，视为剥夺。

19、,3.6.1 预防死锁,（2）优点：进程可快速开始,（3）缺点：实现复杂、开销大；延长周转时间；运行具有信息不连续性,第三章 处理机调度与死锁,3.6 预防死锁的方法,3 摒弃“环路等待”条件,（1）思想：对全部资源编号，规定申请资源时按编号 递增顺序。,3.6.1 预防死锁,（2）优点：资源利用率和系统吞吐量改善,（3）缺点：限制新设备的添加；资源浪费；限制用户编程的灵活性,第三章 处理机调度与死锁,3.6 预防死锁的方法,1 避免死锁,分配资源前，先计算此次资源分配的安全性，若不会进入不安全状态，则分配资源，否则，进程等待。,3.6.2 系统安全状态,2 系统安全状态,系统能按某种进程顺序

20、(P1，P2，Pn)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。称为系统安全状态，P1，P2，Pn为安全序列。,第三章 处理机调度与死锁,3.6 预防死锁的方法,3 系统不安全状态,如果系统无法找到这样一个安全序列，则称系统处于不安全状态。,3.6.2 系统安全状态,4 进入不安全状态，可能会导致死锁 不进入不安全状态，一定不会死锁,第三章 处理机调度与死锁,3.6 预防死锁的方法,5 例子,12台磁带机，三个进程在T0时刻的状态,3.6.2 系统安全状态,为安全序列,第三章 处理机调度与死锁,3.6 预防死锁的方法,6 由安全状态向不安全状态

21、转换,T0时刻P3又申请1台，剩余2台,3.6.2 系统安全状态,找不到安全序列,第三章 处理机调度与死锁,3.6 预防死锁的方法,1 所需数据结构,(1)可利用资源向量Available,3.6.3 利用银行家算法避免死锁,m个元素的数组,每类可利用的资源数目,初始值是系统中所配置的该类全部可用资源的数目,数值随该类资源的分配和回收而动态地改变,Availablej=K，则表示系统中现有R j类资源K个,第三章 处理机调度与死锁,3.6 预防死锁的方法,1 所需数据结构,(2)最大需求矩阵Max,3.6.3 利用银行家算法避免死锁,nm的矩阵,n个进程中的每一个进程对m类资源的最大需求,如果

22、Maxi,j=K，则表示进程i需要Rj类资源的最 大数目为K,第三章 处理机调度与死锁,3.6 预防死锁的方法,1 所需数据结构,(3)分配矩阵Allocation,3.6.3 利用银行家算法避免死锁,nm的矩阵,定义了系统中每一类资源当前已分配给每一 进程的资源数,如果Allocationi,j=K，则表示进程i当前已分 得R j类资源的数目为K,第三章 处理机调度与死锁,3.6 预防死锁的方法,1 所需数据结构,(4)需求矩阵Need,3.6.3 利用银行家算法避免死锁,nm的矩阵,表示每一个进程尚需的各类资源数,如果Needi,j=K，则表示进程i还需要R j类资源K个,Needi,j=

23、Maxi,j-Allocationi,j,第三章 处理机调度与死锁,3.6 预防死锁的方法,2 银行家算法,3.6.3 利用银行家算法避免死锁,设Request i是进程Pi的请求向量，如果Request i j=K，表示进程P i需要K个R j类型的资源。当P i发出资源请求后，系统按下述步骤进行检查：,(1)如果Requesti jNeedi,j，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。,(2)如果RequestijAvailablej，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。,第三章 处理机调度与死锁,3.6 预防死锁的方法,2 银行家算

24、法,3.6.3 利用银行家算法避免死锁,(3)系统试探着把资源分配给进程P i，并修改下面数据结构中的数值：Availablej:=Availablej-Request ij；Allocationi,j:=Allocationi,j+Request ij；Needi,j:=Needi,j-Request ij；,(4)系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,第三章 处理机调度与死锁,3.6 预防死锁的方法,3 安全性算法,3.6.3 利用银行家算法避免死

25、锁,(1)设置两个向量：,工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available。,Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi:=false；当有足够资源分配给进程时，再令Finishi:=true。,第三章 处理机调度与死锁,3.6 预防死锁的方法,3 安全性算法,3.6.3 利用银行家算法避免死锁,(2)从进程集合中找到一个能满足下述条件的进程：,Finishi=false；,Needi,jWorkj；若找到，执行步骤(3)，否则，执行步骤(4)。,第三章 处理

26、机调度与死锁,3.6 预防死锁的方法,3 安全性算法,3.6.3 利用银行家算法避免死锁,(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj:=Workj+Allocationi,j；Finishi:=true；go to step（2）；,(4)如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。,第三章 处理机调度与死锁,3.6 预防死锁的方法,4 例子,3.6.3 利用银行家算法避免死锁,假定系统中有五个进程P0，P1，P2，P3，P4和三类资源A，B，C，各种资源的数量分别为10、5、7，在T0时刻

27、的资源分配情况如图所示。,第三章 处理机调度与死锁,3.6 预防死锁的方法,4 例子,3.6.3 利用银行家算法避免死锁,(1)检测T0时刻的安全性（板书讲解）,存在着一个安全序列P1，P3，P4，P2，P0，故系统是安全的,第三章 处理机调度与死锁,3.6 预防死锁的方法,4 例子,3.6.3 利用银行家算法避免死锁,(2)P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查是否分配资源给P1.（板书讲解）,第三章 处理机调度与死锁,3.6 预防死锁的方法,4 例子,3.6.3 利用银行家算法避免死锁,(3)P4请求资源：P4发出请求向量Request4(3

28、，3，0)，系统按银行家算法进行检查：（板书讲解）,第三章 处理机调度与死锁,3.6 预防死锁的方法,4 例子,3.6.3 利用银行家算法避免死锁,(4)P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查：（板书讲解）,第三章 处理机调度与死锁,银行家算法,1 判断请求是否大于最大需求,2 判断请求是否大于可用资源量,3 假定资源分配，修改值,4 判断安全性,第三章 处理机调度与死锁,安全性算法,1 Finish=F；work=Available,2 找到Finish=F且需求量work的进程,3 修改值，重复2,4 若Finish全为T，则安全，否则不安全,

29、第三章 处理机调度与死锁,练习：若出现下面资源分配情况，试问（1）该状态是否安全；（2）若进程P2提出请求Request（1,2,2,2）后，系统能否将资源分配给它。,第三章 处理机调度与死锁,3.7 死锁的检测与解除,1 资源分配图（描述死锁）,由一组结点N和一组边E所组成的一个对偶G=(N，E),前提：保存有关资源的请求和分配信息 提供一种算法以检测系统是否死锁,(1)把N分为两个互斥的子集，即一组进程结点P=p1，p2，pn和一组资源结点R=r1，r2，rn,第三章 处理机调度与死锁,3.7 死锁的检测与解除,1 资源分配图（描述死锁）,（2）凡属于E中的一个边eE，都连接着P中的一个结

30、点和R中的一个结点，e=pi，rj是资源请求边，由进程pi指向资源rj。e=rj，pi是资源分配边，由资源rj指向进程pi。,第三章 处理机调度与死锁,3.7 死锁的检测与解除,1 资源分配图（描述死锁）,2 死锁定理,利用把资源分配图加以简化的方法，来检测当系统处于S状态时是否为死锁状态。,第三章 处理机调度与死锁,3.7 死锁的检测与解除,2 死锁定理,(1)找出一个既不阻塞又非独立的进程结点Pi。消去pi所求的请求边和分配边，使之成为孤立的结点。,(2)在进行一系列的简化后，若能消去图中所有的边，则称该图是可完全简化的；,(3)当且仅当S状态的资源分配图是不可完全简化的，则S为死锁状态；,第三章 处理机调度与死锁,3.7 死锁的检测与解除,2 死锁定理,第三章 处理机调度与死锁,3.7 死锁的检测与解除,3 死锁的解除,(1)剥夺资源,(2)撤销进程,4 原则,(1)所需撤销进程数量最少,(2)所付出代价最小,