第三章 处理机调度与死锁

东北农业大学王艳操作系统原理用户用户用户作业1作业2作业3作业4外存后备队列作业调度程序内存CPU进程调度第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.1.1处理机调度的层次1高级调度长程调度、作业调度，调度对象为作业。低级调度进程调度、短程调度，调度对象为进程。3中级调度内存调度，为提高内存利用率和系统吞吐量。第三章处理机调度与死锁CPU就绪队列阻塞队列后备作业队列高级调度低级调度时间片用完进程完成等待事件事件解除第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.1.2处理机算法的目标1处理机算法的共同目标〔1〕资源利用率〔2〕公平性〔3〕平衡性〔4〕策略强制执行性第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.1.2处理机算法的目标2批处理系统的目标〔1〕平均周转时间短作业提交开始到作业完成为止的时间间隔系统：作业的平均周转时间尽可能少用户：自己作业周转时间尽量少指标：平均周转时间指标：带权周转时间第三章处理机调度与死锁①作业平均周转时间〔T〕②带权平均周转时间〔W〕T＝（）×å=niTi1n为作业数目，第i个作业的周转时间Ti＝Ei–SiEi：作业完成时间Si：作业提交时间W＝（）×

ri为某作业i的实际执行时间3.1处理机调度的层次和调度算法的目标3.1.2处理机算法的目标第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.1.2处理机算法的目标2批处理系统的目标〔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〕三个阶段收容阶段→运行阶段→完成阶段〔2〕三种状态第三章处理机调度与死锁3.2作业与作业调度

3.2.2作业调度的主要任务1决定接纳多少个作业多道程序度2接纳哪些作业调度算法第三章处理机调度与死锁3.2作业与作业调度

3.2.3先来先效劳和短作业优先算法1先来先效劳算法〔1〕FCFS：FirstComeFirstServe〔2〕适用于作业、进程调度〔3〕选择最先进入的作业/进程〔4〕例子：第三章处理机调度与死锁作业到达t服务t开始t结束tTWA01B1100C21D31000111011011021022021110011001001991.99平均周转时间：t=100带权平均周转时间w=25.9975优点：实现简单〔优待大作业〕缺点：对短作业不利3.2作业与作业调度3.2.3先来先效劳和短作业优先算法第三章处理机调度与死锁2短作业优先算法〔1〕SJ〔P〕F：ShortestJob〔Process〕First〔2〕适用于作业、进程调度〔3〕选择短的作业/进程〔4〕例子：3.2作业与作业调度3.2.3先来先效劳和短作业优先算法第三章处理机调度与死锁进程ABCDE平均到达t01234服务t43524

先来先服务算法开始t完成tTW

短作业优先算法开始t完成tTW作业情况算法0447712121414184162102115.5143.592.804691318469134182.67163.231.592.2582.143.2作业与作业调度3.2.3先来先效劳和短作业优先算法第三章处理机调度与死锁1优先级调度算法〔PSA〕3.2作业与作业调度3.2.4优先级调度算法和高响应比优先调度算法先来先效劳算法→等待时间为优先级短作业优先算法→作业长短为优先级优先级调度算法→作业的紧迫程度第三章处理机调度与死锁2高响应比优先权调度算法〔HRRN〕〔1〕HRRN是介于FCFS和SJP〔F〕之间的一种折中算法〔2〕优先权3.2作业与作业调度3.2.4优先级调度算法和高响应比优先调度算法优先权=〔等待时间+要求效劳时间〕/要求效劳时间动态优先权：随等待时间延长而增加响应比R=〔等待时间+要求效劳时间〕/要求效劳时间=响应时间/要求效劳时间第三章处理机调度与死锁2高响应比优先权调度算法〔HRRN〕〔3〕优点＊等待时间相同，那么处理时间短，优先级R高。＊作业处理时间相同，那么等待时间决定优先级R。＊对于长作业，等待足够时间，R增加，可获得处理机。——SJF——FCFS〔4〕缺点＊增加系统开销3.2作业与作业调度3.2.4优先级调度算法和高响应比优先调度算法第三章处理机调度与死锁2高响应比优先权调度算法〔HRRN〕〔5〕例子到达t服务t开始t完成tTWA04B13C25D32E44平均04Rb=1，Rc=0.4Rd=0.5，Re=047Rc=1，Rd=2，Re=0.7579Rc=1.4，Re=1.2591414184162122.463143.58.42.383.2作业与作业调度3.2.4优先级调度算法和高响应比优先调度算法〔1〕FCFS〔2〕SJ〔P〕F〔3〕HRN名称ABCDE平均到达01234CPU36452FCFS开始完成TWSJF开始完成TWHRN开始完成TW0339913131818203181115161.332.753810.63.220314203791479311951153.171.252.22.58.62.02033911151520911318131771.333.253.43.59.62.49621第三章处理机调度与死锁3.3进程调度1进程调度的任务

(1)保存处理机现场信息

(2)按某种算法选取进程

(3)把处理机分配给进程2进程调度机制

(1)排队器

(2)分派器

(3)上下文切换机制3.3.1进程调度的任务、机制和方式第三章处理机调度与死锁3.3进程调度3调度方式

(1)非抢占式

＊引发进程调度的事件——执行完毕、进程阻塞、执行原语＊特点——实现简单、开销小、不能立即执行〔2〕抢占式＊根本原那么—优先权原那么、短作业〔进程〕优先、时间片原那么＊特点—开销大、公平、响应及时第三章处理机调度与死锁3.3进程调度3.3.2轮转调度算法〔RR〕1轮转法的根本原理按FCFS将就绪进程排成一个就绪队列，进程按时间片轮流使用CPU。3时间片大小确实定太长——不能及时响应太短——频繁切换，降低CPU效率2进程切换时机〔1〕时间片未完，进程已完成〔2〕时间片完，进程未完成第三章处理机调度与死锁第三章处理机调度与死锁第三章处理机调度与死锁3.3进程调度3.3.3优先级调度算法1优先级调度算法类型〔1〕非抢占式优先权调度算法＊批处理系统、实时性要求不高的实时系统〔2〕抢占式优先权算法＊严格的实时系统，高性能的分时、批处理系统第三章处理机调度与死锁3.3进程调度3.3.3优先级调度算法2优先级的类型〔1〕静态优先级进程创立时确定，在进程整个运行期间保持不变。①进程类型②进程对资源的需求③用户要求简单易行，系统开销小，但不够精确，优先级低的进程长期不被调用第三章处理机调度与死锁3.3进程调度3.3.3优先级调度算法2优先级的类型〔2〕动态优先级进程创立之初确定，随进程推进或等待时间的增加而改变①随等待时间的增长，优先级相应提高②抢占式调度方式中，规定当前进程的优先级随运行时间的推移而下降第三章处理机调度与死锁3.3进程调度3.3.4多队列调度算法就绪队列→多个不同队列→不同优先级不同队列→不同调度算法第三章处理机调度与死锁3.3进程调度3.3.5多级反响队列调度算法1调度机制〔1〕建立多个就绪队列，优先级递减第三章处理机调度与死锁3.3进程调度3.3.5多级反响队列调度算法1调度机制〔2〕每个队列都采用FCFS算法，第n个队列采用RR方式调度〔3〕按队列优先级调度。首先调度最高优先级队列中的进程运行，仅当第一队列空闲时才调度第二队列中的进程运行。第三章处理机调度与死锁3.3进程调度3.3.5多级反响队列调度算法2调度算法性能假设规定第一个队列的时间片略大于多数人机交互所需处理时间时，便能较好满足各种类型用户的需要。＊终端型用户＊短批处理作业用户＊长批处理作业用户第三章处理机调度与死锁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可重用性资源和消耗性资源(2)可消耗性资源：临时资源③可以请求假设干个可消耗性资源单元②进程运行过程中，可以不断的创造可消耗性资源的单元①每一类可消耗性资源中的单元数目是可以不断变化的④生产者创立，消费者进程消耗第三章处理机调度与死锁3.5产生死锁的原因和必要条件3.5.1资源问题2可抢占性资源和不可抢占性资源(1)可抢占性资源磁带机、打印机等〔2〕不可抢占性资源CPU、主存等，此类资源不会引起死锁第三章处理机调度与死锁3.5产生死锁的原因和必要条件3.5.２计算机系统中的死锁１竞争非剥夺性资源R1：磁带机R2：打印机

第三章处理机调度与死锁3.5产生死锁的原因和必要条件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)；Release(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占用而阻塞；当P2运行到P2：Request(R1)时，也将因R1已被P1占用而阻塞，于是发生了进程死锁。第三章处理机调度与死锁3.5产生死锁的原因和必要条件3.5.３死锁的定义、必要条件和处理方法互斥条件请求和保持条件不剥夺条件环路等待条件死锁：多个进程因共享资源而产生的僵局，没有外力作用将无法向前推进。第三章处理机调度与死锁3.5产生死锁的原因和必要条件3.5.3处理死锁的根本方法1预防死锁2防止死锁3检测死锁4解除死锁0鸵鸟策略出现频率极少时，置之不理设置条件，破坏死条件之一分配资源时防止进入不平安状态允许发生，及时检测并消除撤销挂起进程，回收资源第三章处理机调度与死锁1产生死锁的必要条件互斥条件请求和保持条件不剥夺条件环路等待条件第三章处理机调度与死锁2处理死锁的根本方法1预防死锁2防止死锁3检测死锁4解除死锁0鸵鸟策略第三章处理机调度与死锁1摒弃“请求和保持〞条件〔1〕思想：要么分配所有资源，要么不分配3.6.1预防死锁〔2〕优点：简单易实现、平安性好〔3〕缺点：资源浪费严重、进程延迟进行3.6预防死锁的方法第三章处理机调度与死锁3.6预防死锁的方法2摒弃“不剥夺〞条件〔1〕思想：逐个提出对资源的请求，有需求不满足时释放资源，视为剥夺。3.6.1预防死锁〔2〕优点：进程可快速开始〔3〕缺点：实现复杂、开销大；延长周转时间；运行具有信息不连续性第三章处理机调度与死锁3.6预防死锁的方法3摒弃“环路等待〞条件〔1〕思想：对全部资源编号，规定申请资源时按编号递增顺序。3.6.1预防死锁〔2〕优点：资源利用率和系统吞吐量改善〔3〕缺点：限制新设备的添加；资源浪费；限制用户编程的灵活性第三章处理机调度与死锁3.6预防死锁的方法1防止死锁分配资源前，先计算此次资源分配的平安性，假设不会进入不平安状态，那么分配资源，否那么，进程等待。3.6.2系统平安状态2系统平安状态系统能按某种进程顺序(P1，P2，…，Pn)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。称为系统平安状态，〈P1，P2，…，Pn〉为平安序列。第三章处理机调度与死锁3.6预防死锁的方法3系统不平安状态如果系统无法找到这样一个平安序列，那么称系统处于不平安状态。3.6.2系统平安状态4进入不平安状态，可能会导致死锁不进入不平安状态，一定不会死锁第三章处理机调度与死锁3.6预防死锁的方法5例子

12台磁带机，三个进程在T0时刻的状态3.6.2系统平安状态<P2,P1,P3>为平安序列第三章处理机调度与死锁3.6预防死锁的方法6由平安状态向不平安状态转换

T0时刻P3又申请1台，剩余2台3.6.2系统平安状态找不到平安序列第三章处理机调度与死锁3.6预防死锁的方法1所需数据结构(1)可利用资源向量Available3.6.3利用银行家算法防止死锁＊m个元素的数组＊每类可利用的资源数目＊初始值是系统中所配置的该类全部可用资源的数目＊数值随该类资源的分配和回收而动态地改变＊Available[j]=K，那么表示系统中现有Rj类资源K个第三章处理机调度与死锁3.6预防死锁的方法1所需数据结构(2)最大需求矩阵Max3.6.3利用银行家算法防止死锁＊n×m的矩阵＊n个进程中的每一个进程对m类资源的最大需求＊如果Max[i,j]=K，那么表示进程i需要Rj类资源的最大数目为K第三章处理机调度与死锁3.6预防死锁的方法1所需数据结构(3)分配矩阵Allocation3.6.3利用银行家算法防止死锁＊n×m的矩阵＊定义了系统中每一类资源当前已分配给每一进程的资源数＊如果Allocation[i,j]=K，那么表示进程i当前已分得Rj类资源的数目为K第三章处理机调度与死锁3.6预防死锁的方法1所需数据结构(4)需求矩阵Need3.6.3利用银行家算法防止死锁＊n×m的矩阵＊表示每一个进程尚需的各类资源数＊如果Need[i,j]=K，那么表示进程i还需要Rj类资源K个Need[i,j]=Max[i,j]-Allocation[i,j]

第三章处理机调度与死锁3.6预防死锁的方法2银行家算法3.6.3利用银行家算法防止死锁

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

(3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Available[j]:=Available[j]-Requesti[j]；Allocation[i,j]:=Allocation[i,j]+Requesti[j]；Need[i,j]:=Need[i,j]-Requesti[j]；(4)系统执行平安性算法，检查此次资源分配后系统是否处于平安状态。假设平安，才正式将资源分配给进程Pi，以完本钱次分配；否那么，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。第三章处理机调度与死锁3.6预防死锁的方法3平安性算法3.6.3利用银行家算法防止死锁(1)设置两个向量：①工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行平安算法开始时，Work:=Available。

②Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false；当有足够资源分配给进程时，再令Finish[i]:=true。第三章处理机调度与死锁3.6预防死锁的方法3平安性算法3.6.3利用银行家算法防止死锁(2)从进程集合中找到一个能满足下述条件的进程：①Finish[i]=false；②Need[i,j]≤Work[j]；假设找到，执行步骤(3)，否那么，执行步骤(4)。第三章处理机调度与死锁3.6预防死锁的方法3平安性算法3.6.3利用银行家算法防止死锁(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work[j]:=Work[j]+Allocation[i,j]；Finish[i]:=true；gotostep〔2〕；(4)如果所有进程的Finish[i]=true都满足，那么表示系统处于平安状态；否那么，系统处于不平安状态。第三章处理机调度与死锁3.6预防死锁的方法4例子3.6.3利用银行家算法防止死锁假定系统中有五个进程{P0，P1，P2，P3，P4}和三类资源{A，B，C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如下图。第三章处理机调度与死锁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，3，0)，系统按银行家算法进行检查：〔板书讲解〕第三章处理机调度与死锁3.6预防死锁的方法4例子3.6.3利用银行家算法防止死锁(4) P0请求资源：P0发出请求向量Requst0