操作系统课件第3章

第三章处理机调度与死锁为提高处理机利用率、改善系统性能（吞吐量、响应时间）需对处理机进行合理分配调度处理机调度的目的：分配处理机3.1处理机调度的层次高级、中级和低级调度调度分三级1.高级调度

也称为作业调度作业：用户在一次执行过程中或一个事务处理中要求计算机系统所做工作的集合作业调度：将外存上后备队列的作业调入内存、创建进程并分配资源、插入就绪队列接纳多少个作业接纳哪些作业分时系统、实时系统中不需要作业调度，作业直接送入内存2.低级调度称为进程调度选择就绪队列中某个进程获得处理机

调度方式1)非抢占方式：不允许其它进程抢占已经分配出去的处理机。实时系统中，不宜采用这种调度方式。2)抢占方式：允许调度程序将已分配出去的处理机重新分配给另一进程。3.中级调度主要目的：提高内存利用率和系统吞吐量。实现方式：对换暂时不能运行的进程调至外存上的挂起队列去等待。当进程重新具备运行条件时，中级调度将挂起队列中某个进程重新调入内存，挂在就绪队列上等待进程调度。3.2调度队列模型和调度准则调度队列模型1.仅有进程调度的调度队列模型这种调度适合于哪种系统？2.具有高级和低级调度的调度队列模型这种调度适合于哪种系统？3.同时具有三级调度的调度队列模型

高低中调度准则

1.面向用户的准则周转时间短。周转时间T：从作业被提交给系统，到作业完成为止的时间间隔。由4个部分组成：在后备队列等待的时间、进程在就绪队列中等待的时间、在CPU中执行的时间、I/O操作完成的时间。平均周转时间：平均带权周转时间：带权周转时间：W=T/TS（TS系统服务时间即CPU执行时间）(2)响应时间快。（评价分时系统，输入、处理、返回）(3)截止时间的保证。（评价实时系统）(4)优先权准则。2.面向系统的准则(1)系统吞吐量高吞吐量是指单位时间内完成的作业数(2)处理机利用率好(3)各类资源的平衡利用

---各类资源处于忙碌状态3.3调度算法

调度算法：资源分配方法。不同的系统，通常采用不同的调度算法。1.先来先服务调度算法（既可用于作业调度又可用于进程调度）2.短作业(进程)优先调度算法3.高优先权优先调度算法(FPF)静态优先权：创建进程时确定且在进程的整个运行期间保持不变。优先权是利用某一范围内的一个整数来表示。动态优先权：可以改变。高响应比优先调度算法

优先权=(等待时间+要求服务时间)/要求服务时间响应比Rp=响应时间/要求服务时间例：在一个批处理单道系统中，采用响应比高者优先的作业调度算法。现有3个作业，进入系统的时间和需要计算的时间如下表所示：（1）求出每个作业的开始时间、完成时间及周转时间并填入表中。（2）计算三个作业的平均周转时间为多少？（1）平均周转时间：（60+120+70）分钟/3=83.33分钟（2）带权平均周转时间：＝？分别采用FCFS、SJF、FPF求出每个作业的开始时间、完成时间、周转时间、带权周转时间并填入表中。计算系统的平均周转时间和平均带权周转时间。先来先服务调度算法计算结果最短作业优先作业算法计算结果最高响应比优先作业算法计算结果4.基于时间片的轮转调度算法

基本原理：系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。确定时间片大小考虑的因素@系统对响应时间的要求：响应时间=时间片*进程数。@就绪队列中的进程数目：时间片与就绪进程数成反比。@系统处理能力：人所能承受的响应时间一定，系统速度快则时间片可增长。q=1q=4ABCDEBCDEABCEACEABCDEAA1234567891011121314151617时间片大小对进程执行时间的影响5.多级反馈队列调度算法：不需事先知道各进程的执行时间，且还可以满足各种类型进程需要优先权降低时间片增大就绪队列1就绪队列2就绪队列3就绪队列nCPUCPUCPUCPUS1S2S3Sn(时间片：S1<S2<S3<Sn)3.5产生死锁的原因和必要条件死锁:多个进程在运行过程中因争夺资源而造成的一种僵局，若无外力作用，进程都将无法再向前推进。

产生死锁的原因非剥夺资源：磁带机、打印机资源追逐，各不相让占有并等待临时性资源：由一个进程产生，被另一个进程使用后便无用的资源。进程P1进程P2消息S3消息S1进程P3消息S2P1：Release(S1);Request(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)可能发生死锁产生死锁的必要条件

互斥条件(2)请求和保持条件（占有并等待）(3)不剥夺条件(4)环路等待条件1.必要条件（缺一不可）2.必须同时成立或存在处理死锁的基本方法

预防死锁(2)避免死锁(3)检测死锁(4)解除死锁

最好是预防，逐个降格主动措施（被动措施）（挽救措施）3.6预防死锁的方法

预防死锁

摒弃“请求和保持”条件2.

摒弃“不剥夺”条件3.摒弃“环路等待”条件

由于互斥条件不可破坏,至少破坏1/4变成要破坏1/3.形成死锁,要求4个条件同时成立,至少破坏其中1个就行!系统安全状态

安全状态：系统能按某种顺序如﹤P1,P2,…Pn﹥（称﹤P1,P2,…Pn﹥为安全序列），为每个进程分配资源，使每个进程都能顺利完成。不安全状态：不存在安全序列的状态。避免死锁的实质：如何使系统不进入不安全状态。安全状态例假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：进程最大需求已分配可用P1P2P310495223安全序列？p1→p2→p3

，p2→p3→p1

，p2→p1→p3利用银行家算法避免死锁

银行家算法中的数据结构可利用资源向量Available：一个含有m个元素的数组，其中，每一个元素代表一类可用的资源数目，其初始值是系统中所配置的该类全部可用资源数目。其值随资源的分配和回收而动态地改变。最大需求矩阵Max：是一个n×m的矩阵，定义了系统中n个进程中的每一个进程对m类资源的最大需求。分配矩阵Allocation：是一个n×m的矩阵，定义了系统中每一类资源当前已分配给每一进程的资源数。需求矩阵Need：是一个n×m的矩阵，表示每个进程尚需的该类资源数。上述三个矩阵的关系：Need[i,j]=Max[i,j]–Allocation[i,j]其中：Need[i,j]=k表示进程i还需要Rj

类资源k个。Max[i,j]=k表示进程i需要Rj

类资源的最大数目为k。Allocation[i,j]=k表示进程i当前已分得Rj类资源的数目为k。Available[j]=k表示系统中现有Rj类资源k个。银行家算法：Requesti[j]=k进程尚需要的资源Requesti<=Needi1出错N等待NRequesti<=AvailableY是否有足够的可利用资源2系统把要求的资源试探分配给进程PiAvailable:=Available-Requesti;Allocation:=Allocationi+Requesti;Needi

:=Needi-RequestiY3系统执行安全性算法4分配资源给进程Y试探分配作废N安全性算法：向量

Work

表示系统可提供给进程继续运行所需的各类资源数目，其初始化为当前可用的资源数。向量

Finish

是布尔型数组，表示系统是否有足够的资源分配给进程，使之运行完成。初始化为false。安全性检查的步骤：(1)Work:=Available;Finish:=false;(2)寻找满足条件的i：

a.Finish[i]=false;b.Need[i]≤Work;

如果不存在，则转(4)(3)Work:=Work+Allocation[i];Finish[i]:=true;转(2)(4)若对所有i，Finish[i]=true，则系统处于安全状态，否则处于不安全状态银行家算法之例

假定系统中有五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7。

T0时刻的资源分配表

T0时刻的安全性：

T0时刻的安全序列

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向量。④再利用安全性算法检查此时系统是否安全。P1申请资源时的安全性检查P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：①Request4(3,3,0)≤Need4(4,3,1);②Request