处理机调与死锁学习教案

1、会计学1处理机调与死锁处理机调与死锁第一页，编辑于星期一：十点 三十九分。用户用户用户作业1作业2作业3作业4外存后备队列作业调度程序内存CPU进程调度第1页/共76页第二页，编辑于星期一：十点 三十九分。3.1.1 处理机调度的层次1 高级调度 长程调度、作业调度，调度对象为作业。低级调度 进程调度、短程调度，调度对象为进程。3 中级调度 内存调度，为提高内存利用率和系统吞吐量。第2页/共76页第三页，编辑于星期一：十点 三十九分。CPU就绪队列阻塞队列后备作业队列高级调度低级调度时间片用完进程完成等待事件事件解除第3页/共76页第四页，编辑于星期一：十点 三十九分。3.1.2 处理机算法的

2、目标1 处理机算法的共同目标（1）资源利用率（2）公平性（3）平衡性（4）策略强制执行性第4页/共76页第五页，编辑于星期一：十点 三十九分。3.1.2 处理机算法的目标2 批处理系统的目标（1）平均周转时间短作业提交开始到作业完成为止的时间间隔系统：作业的平均周转时间尽可能少用户：自己作业周转时间尽量少指标：平均周转时间指标：带权周转时间第5页/共76页第六页，编辑于星期一：十点 三十九分。作业平均周转时间（T）带权平均周转时间（W）T（ ）=niTi1n1n为作业数目， 第i个作业的周转时间Ti Ei SiEi：作业完成时间 Si：作业提交时间W（ ） n1=niriTi1ri 为某作业i

3、的实际执行时间3.1.2 处理机算法的目标第6页/共76页第七页，编辑于星期一：十点 三十九分。3.1.2 处理机算法的目标2 批处理系统的目标（2）系统吞吐量（3）处理机利用率高3 分时系统的目标（1）响应时间快（2）均衡性4 实时系统的目标（1）截止时间的保证（2）可预测性第7页/共76页第八页，编辑于星期一：十点 三十九分。3.2.1 批处理系统中的作业1 作业和作业步 （1）作业（Job）：程序+数据+作业说明符 （2）作业步：作业执行过程中的加工步骤2 作业控制块（JCB） (1)作业存在的标识 (2)保存系统对作业进行管理和调度的所有信息第8页/共76页第九页，编辑于星期一：十点

4、三十九分。3.2.1 批处理系统中的作业3 作业运行的三个阶段和三种状态后备状态运行状态完成状态（1）三个阶段收容阶段运行阶段完成阶段（2）三种状态第9页/共76页第十页，编辑于星期一：十点 三十九分。3.2.2 作业调度的主要任务1 决定接纳多少个作业多道程序度2 接纳哪些作业调度算法第10页/共76页第十一页，编辑于星期一：十点 三十九分。3.2.3 先来先服务和短作业优先算法1 先来先服务算法 （1）FCFS：First Come First Serve （2）适用于作业、进程调度 （3）选择最先进入的作业/进程 （4）例子：第11页/共76页第十二页，编辑于星期一：十点 三十九分。作业

5、作业到达到达t服务服务t开始开始t结束结束tTWA01B1100C21D3100011101101102102202111001100100199平均周转时间：t=100带权平均周转时间优点：实现简单（优待大作业） 缺点：对短作业不利3.2.3 先来先服务和短作业优先算法第12页/共76页第十三页，编辑于星期一：十点 三十九分。2 短作业优先算法 （1）SJ（P）F：Shortest Job（Process） First （2）适用于作业、进程调度 （3）选择短的作业/进程 （4）例子：3.2.3 先来先服务和短作业优先算法第13页/共76页第十四页，编辑于星期一：十点 三十九分。进程进程AB

6、CDE平均平均到达到达t01234服务服务t43524 先先 来来 先先 服服 务务 算算 法法开始开始t完成完成tTW 短短 作作 业业 优优 先先 算算 法法开始开始t完成完成tTW作业情况算法0447712121414184162102111490469131846913418163983.2.3 先来先服务和短作业优先算法第14页/共76页第十五页，编辑于星期一：十点 三十九分。1 优先级调度算法（PSA）3.2.4 优先级调度算法和高响应比优先调度算法先来先服务算法等待时间为优先级短作业优先算法作业长短为优先级优先级调度算法作业的紧迫程度第15页/共76页第十六页，编辑于星期一：十点

7、 三十九分。2 高响应比优先权调度算法（HRRN）（1）HRRN是介于FCFS和SJP（F）之间的一种折中算法（2）优先权3.2.4 优先级调度算法和高响应比优先调度算法优先权=（等待时间+要求服务时间）/要求服务时间动态优先权：随等待时间延长而增加响应比R=（等待时间+要求服务时间）/要求服务时间 =响应时间/要求服务时间第16页/共76页第十七页，编辑于星期一：十点 三十九分。2 高响应比优先权调度算法（HRRN）（3）优点等待时间相同，则处理时间短，优先级R高。作业处理时间相同，则等待时间决定优先级R。对于长作业，等待足够时间，R增加，可获得处理机。SJFFCFS（4）缺点增加系统开销3

8、.2.4 优先级调度算法和高响应比优先调度算法第17页/共76页第十八页，编辑于星期一：十点 三十九分。2 高响应比优先权调度算法（HRRN）（5）例子到达到达t服务服务t开始开始t完成完成tTWA04B13C25D32E44平均平均04Rb=1，Rc，Re=047Rc=1，Rd=2，79Rc，914141841621263143.2.4 优先级调度算法和高响应比优先调度算法第18页/共76页第十九页，编辑于星期一：十点 三十九分。（1）FCFS（2）SJ（P）F（3）HRN第19页/共76页第二十页，编辑于星期一：十点 三十九分。Page 21名称名称ABCDE平均平均到达到达01234CP

9、U36452FCFS开始开始完成完成TWSJF开始开始完成完成TWHRN开始开始完成完成TW0339913131818203181115163803142037914793119511503391115152091131813177第20页/共76页第二十一页，编辑于星期一：十点 三十九分。1 进程调度的任务 (1)保存处理机现场信息 (2)按某种算法选取进程 (3)把处理机分配给进程2 进程调度机制 (1)排队器 (2)分派器 (3)上下文切换机制 3.3.1 进程调度的任务、机制和方式第21页/共76页第二十二页，编辑于星期一：十点 三十九分。3 调度方式 (1)非抢占式 引发进程调度的事

10、件执行完毕、进程阻塞、执行原语 特点实现简单、开销小、不能立即执行（2）抢占式 基本原则优先权原则、短作业（进程）优先、时间片原则 特点开销大、公平、响应及时 第22页/共76页第二十三页，编辑于星期一：十点 三十九分。3.3.2 轮转调度算法（RR）1 轮转法的基本原理 按FCFS将就绪进程排成一个就绪队列，进程按时间片轮流使用CPU。3 时间片大小的确定 太长不能及时响应 太短频繁切换，降低CPU效率2 进程切换时机（1）时间片未完，进程已完成（2）时间片完，进程未完成第23页/共76页第二十四页，编辑于星期一：十点 三十九分。ABCDEABCDEABCEACE(a) q1(b) q412

11、345678910 11 12 13 14 15 16 17t第24页/共76页第二十五页，编辑于星期一：十点 三十九分。进程名 A B C D E 平均 到达时间 0 1 2 3 4 作业 情况 时 间 片 服务时间 4 3 4 2 4 完成时间 15 12 16 9 17 周转时间 15 11 14 6 13 11.8 RR q=1 带权周转时间 3.75 3.67 3.5 3 3.33 3.46 完成时间 4 7 11 13 17 周转时间 4 6 9 10 13 8.4 RR q=4 带权周转时间 1 2 2.25 5 3.33 2.5 第25页/共76页第二十六页，编辑于星期一：十点

12、 三十九分。3.3.3 优先级调度算法1 优先级调度算法类型 （1）非抢占式优先权调度算法 批处理系统、实时性要求不高的实时系统 （2）抢占式优先权算法 严格的实时系统，高性能的分时、批处理系统第26页/共76页第二十七页，编辑于星期一：十点 三十九分。 优先级调度算法2 优先级的类型（1）静态优先级进程创建时确定，在进程整个运行期间保持不变。进程类型进程对资源的需求用户要求 简单易行，系统开销小，但不够精确，优先级低的进程长期不被调用第27页/共76页第二十八页，编辑于星期一：十点 三十九分。 优先级调度算法2 优先级的类型（2）动态优先级进程创建之初确定，随进程推进或等待时间的增加而改变随

13、等待时间的增长，优先级相应提高抢占式调度方式中，规定当前进程的优先级随运行 时间的推移而下降第28页/共76页第二十九页，编辑于星期一：十点 三十九分。3.3.4 多队列调度算法就绪队列多个不同队列不同优先级不同队列不同调度算法第29页/共76页第三十页，编辑于星期一：十点 三十九分。3.3.5 多级反馈队列调度算法1 调度机制（1）建立多个就绪队列，优先级递减就绪队列 1就绪队列 2就绪队列 3就绪队列 nS1S2S3至CPU至CPU至CPU至CPU(时间片： S1 S2 S3)第30页/共76页第三十一页，编辑于星期一：十点 三十九分。3.3.5 多级反馈队列调度算法1 调度机制（2）每个

14、队列都采用FCFS算法，第n个队列 采用RR方式调度（3）按队列优先级调度。首先调度最高优先级 队列中的进程运行，仅当第一队列空闲时 才调度第二队列中的进程运行。第31页/共76页第三十二页，编辑于星期一：十点 三十九分。3.3.5 多级反馈队列调度算法2 调度算法性能 若规定第一个队列的时间片略大于多数人机交互所需处理时间时，便能较好满足各种类型用户的需要。终端型用户短批处理作业用户长批处理作业用户第32页/共76页第三十三页，编辑于星期一：十点 三十九分。1 典型死锁的例子 P1：申请R1 申请R2 P2：申请R2 申请R1 P1拥有R1申请R2，P2拥有R2申请R1 第33页/共76页第

15、三十四页，编辑于星期一：十点 三十九分。3.5.1 资源问题1 可重用性资源和消耗性资源 (1)可重用性资源：供用户使用多次的资源一个可重用性资源单元只能分配给一个进程使用请求资源使用资源释放资源系统中每一类可重用性资源中的单元数目是相对 固定的，进程在运行期间既不能创建也不能删除计算机系统中大多数资源都属于可重用性资源第34页/共76页第三十五页，编辑于星期一：十点 三十九分。3.5.1 资源问题1 可重用性资源和消耗性资源 (2)可消耗性资源：临时资源可以请求若干个可消耗性资源单元进程运行过程中，可以不断的创造可消耗性资源的单元每一类可消耗性资源中的单元数目是可以不断变化的生产者创建，消费

16、者进程消耗第35页/共76页第三十六页，编辑于星期一：十点 三十九分。3.5.1 资源问题2 可抢占性资源和不可抢占性资源 (1)可抢占性资源磁带机、打印机等（2）不可抢占性资源CPU、主存等，此类资源不会引起死锁第36页/共76页第三十七页，编辑于星期一：十点 三十九分。3.5. 计算机系统中的死锁竞争非剥夺性资源R1：磁带机 R2：打印机 R1R2P1P2第37页/共76页第三十八页，编辑于星期一：十点 三十九分。3.5. 计算机系统中的死锁竞争可消耗性资源P1： Release(S1)； Reqaest(S3)； P2： Release(S2)； Request(S1)； P3： Rel

17、ease(S3)； Request(S2)； P1： Request(S3)； Release(S1)； P2： Request(S1)； Release(S2)； P3： Request(S2)； Release(S3)； S2P1S3P3S1P2第38页/共76页第三十九页，编辑于星期一：十点 三十九分。3.5. 计算机系统中的死锁进程间推进顺序非法（）合法P1：Request(R1)；Request(R2)；P1：Releast(R1)；Release(R2)；P2：Request(R2)；Request(R1)；P2：Release(R2)；Release(R1)； 第39页/共76页

18、第四十页，编辑于星期一：十点 三十九分。3.5. 计算机系统中的死锁（2）进程间推进顺序非法P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1) P1Rel(R2)D第40页/共76页第四十一页，编辑于星期一：十点 三十九分。3.5. 计算机系统中的死锁（2）进程间推进顺序非法 若并发进程P1和P2按曲线所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R1，P2保持了资源R2，系统处于不安全状态。因为这时两进程再向前推进，便可能发生死锁。例如，当P1运行到P1：Request(R2)时，将因R2已被P2占用而阻

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

20、第四十四页，编辑于星期一：十点 三十九分。1 产生死锁的必要条件互斥条件请求和保持条件不剥夺条件环路等待条件第44页/共76页第四十五页，编辑于星期一：十点 三十九分。2 处理死锁的基本方法1 预防死锁2 避免死锁3 检测死锁4 解除死锁0 鸵鸟策略第45页/共76页第四十六页，编辑于星期一：十点 三十九分。1 摒弃“请求和保持”条件（1）思想：要么分配所有资源，要么不分配 3.6.1 预防死锁（2）优点：简单易实现、安全性好 （3）缺点：资源浪费严重、进程延迟进行 第46页/共76页第四十七页，编辑于星期一：十点 三十九分。2 摒弃“不剥夺”条件（1）思想：逐个提出对资源的请求，有需求不满足

21、时 释放资源，视为剥夺。 3.6.1 预防死锁（2）优点：进程可快速开始 （3）缺点：实现复杂、开销大；延长周转时间； 运行具有信息不连续性第47页/共76页第四十八页，编辑于星期一：十点 三十九分。3 摒弃“环路等待”条件（1）思想：对全部资源编号，规定申请资源时按编号 递增顺序。 3.6.1 预防死锁（2）优点：资源利用率和系统吞吐量改善 （3）缺点：限制新设备的添加；资源浪费； 限制用户编程的灵活性第48页/共76页第四十九页，编辑于星期一：十点 三十九分。1 避免死锁 分配资源前，先计算此次资源分配的安全性，若不会进入不安全状态，则分配资源，否则，进程等待。 3.6.2 系统安全状态2

22、 系统安全状态 系统能按某种进程顺序(P1，P2，Pn)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。 称为系统安全状态，P1，P2，Pn为安全序列。第49页/共76页第五十页，编辑于星期一：十点 三十九分。3 系统不安全状态 如果系统无法找到这样一个安全序列，则称系统处于不安全状态。 3.6.2 系统安全状态4 进入不安全状态，可能会导致死锁 不进入不安全状态，一定不会死锁 第50页/共76页第五十一页，编辑于星期一：十点 三十九分。5 例子 12台磁带机，三个进程在T0时刻的状态 3.6.2 系统安全状态进 程 最 大 需 求 已 分 配 可

23、 用 P1 10 5 3 P2 4 2 P3 9 2 为安全序列 第51页/共76页第五十二页，编辑于星期一：十点 三十九分。6 由安全状态向不安全状态转换 T0时刻P3又申请1台，剩余2台 3.6.2 系统安全状态 找不到安全序列 第52页/共76页第五十三页，编辑于星期一：十点 三十九分。1 所需数据结构(1)可利用资源向量Available3.6.3 利用银行家算法避免死锁 m个元素的数组每类可利用的资源数目初始值是系统中所配置的该类全部可用资源的数目数值随该类资源的分配和回收而动态地改变 Availablej=K，则表示系统中现有R j类资源K个第53页/共76页第五十四页，编辑于星期

24、一：十点 三十九分。1 所需数据结构(2)最大需求矩阵Max3.6.3 利用银行家算法避免死锁 nm的矩阵n个进程中的每一个进程对m类资源的最大需求如果Maxi,j=K，则表示进程i需要Rj类资源的最 大数目为K第54页/共76页第五十五页，编辑于星期一：十点 三十九分。1 所需数据结构(3)分配矩阵Allocation3.6.3 利用银行家算法避免死锁 nm的矩阵定义了系统中每一类资源当前已分配给每一 进程的资源数如果Allocationi,j=K，则表示进程i当前已分 得R j类资源的数目为K第55页/共76页第五十六页，编辑于星期一：十点 三十九分。1 所需数据结构(4)需求矩阵Need

25、3.6.3 利用银行家算法避免死锁 nm的矩阵表示每一个进程尚需的各类资源数如果Needi,j=K，则表示进程i还需要R j类资源K个Needi, j=Maxi, j-Allocationi, j 第56页/共76页第五十七页，编辑于星期一：十点 三十九分。2 银行家算法3.6.3 利用银行家算法避免死锁 设Request i是进程Pi的请求向量，如果Request i j =K，表示进程P i需要K个R j类型的资源。当P i发出资源请求后，系统按下述步骤进行检查：(1) 如果Requesti jNeedi,j，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (

26、2) 如果RequestijAvailablej，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。 第57页/共76页第五十八页，编辑于星期一：十点 三十九分。2 银行家算法3.6.3 利用银行家算法避免死锁 (3) 系统试探着把资源分配给进程P i，并修改下面数据结构中的数值： Availablej:= Availablej-Request ij； Allocationi,j:= Allocationi,j+Request ij； Needi,j:= Needi,j-Request ij； (4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进

27、程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 第58页/共76页第五十九页，编辑于星期一：十点 三十九分。3 安全性算法3.6.3 利用银行家算法避免死锁(1) 设置两个向量： 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available。 Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi:=false；当有足够资源分配给进程时，再令Finishi:=true。 第59页/共76页第六十页，编辑于星期一：十点 三十九分。3 安全性

28、算法3.6.3 利用银行家算法避免死锁(2) 从进程集合中找到一个能满足下述条件的进程： Finishi=false； Needi,jWorkj；若找到，执行步骤(3)，否则，执行步骤(4)。第60页/共76页第六十一页，编辑于星期一：十点 三十九分。3 安全性算法3.6.3 利用银行家算法避免死锁(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj:= Workj+Allocationi,j； Finishi:=true； go to step （2）； (4) 如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于

29、不安全状态。 第61页/共76页第六十二页，编辑于星期一：十点 三十九分。4 例子3.6.3 利用银行家算法避免死锁假定系统中有五个进程P0，P1，P2，P3，P4和三类资源A，B，C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。 Max Allocation Need Available 资源 情况 进 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1 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

30、0 1 1 P4 4 3 3 0 0 2 4 3 1 第62页/共76页第六十三页，编辑于星期一：十点 三十九分。4 例子3.6.3 利用银行家算法避免死锁(1) 检测T0时刻的安全性（板书讲解）Max Allocation Need Available 资源 情况 进 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1 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 存在着

31、一个安全序列P1，P3，P4，P2，P0，故系统是安全的第63页/共76页第六十四页，编辑于星期一：十点 三十九分。4 例子3.6.3 利用银行家算法避免死锁(2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查是否分配资源给P1.（板书讲解）Max Allocation Need Available 资源 情况 进 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1 2 2 (3 0 2) (0 2 0) P2 9 0 2 3 0 2 6 0 0 P

32、3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 第64页/共76页第六十五页，编辑于星期一：十点 三十九分。4 例子3.6.3 利用银行家算法避免死锁(3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：（板书讲解）Max Allocation Need Available 资源 情况 进 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1 2 2 (3 0 2) (0 2 0) P2 9 0 2 3 0 2 6 0

33、 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 第65页/共76页第六十六页，编辑于星期一：十点 三十九分。4 例子3.6.3 利用银行家算法避免死锁(4) P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查：（板书讲解）Max Allocation Need Available 资源 情况 进 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1 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