操作系统原理课件第五章资源分配与调度培训教材.ppt

第五章 资源分配与调度5.1 资源管理概述 5.1.1 资源管理的目的和任务目的：n1、保证资源的高利用率；n2、在“合理”时间内使所有顾客有获得所需资源的机会；n3、对不可共享的资源实施互斥使用；n4、防止由资源分配不当而引起的死锁5.1 资源管理概述5.1.1 资源管理的目的和任务n对资源的管理应包括以下几个方面：n1、资源管理的描述数据结构n2、确定资源的分配原则和调度原则n3、执行资源分配（实施）n4、存取控制和安全保护n5.1.2 资源的几种分类方法(自学)5.3资源分配策略5.3.1 概述n资源分配有两种方式：n静态分配：当一个进程（或程序）运行前，将它要求的资源一次分配加该进程，直到该进程终止，释放其占用的所有资源这种分配方法效率太低；n动态分配：当一个进程要求使用某个（类）资源时，向系统提出资源的请求，系统响应程序的请求将某种资源分配给请求者，这种方法使得系统资源的利用率提高，但有可能造成死锁5.3资源分配策略5.3.1 概述n几种分配策略：n1、先请求先服务（FIFO）n2、优先调度n3、针对设备特性的调度5.4 死锁5.4.1 死锁的概念n例1：有两个进程PA和PB，它们在运行的过程中要共享使用两个独占设备R1和R2。

设SR1：表示设备R1可用，初值为1；SR2表示设备R2可用，两个进程并发执行的程序如下：5.4 死锁5.4.1 死锁的概念n在这两个进程并发执行时，当PA进程占有R1、PB进程占用R2时，PA要求R2，由于PB已占R2有而得不到，PA进程只有等待；PB申请R1，由于PA已占有R1，而得不到，PB进程只有等待，就出现了死等的情况5.4 死锁5.4.1 死锁的概念例2：三个进程共享使用一台打印机的程序若有一个进程少写了一个V操作5.4 死锁5.4.1 死锁的概念 例3：生产者消费者问题n当缓冲区满时，生产者仍可顺利执行p(mutex)操作，于是它对缓冲区有控制权，然后，当它执行p(empty)时，由于没有空缓冲区被挂起能将这个生产者释放的是有一个消费者从缓冲区中取走一个产品，并执行v(empty)操作，但由于缓冲区已被生产者占用，出现了死锁5.4 死锁5.4.1 死锁的概念n死锁简单的定义：n死锁就是两个或两个以上的进程等候着一个永远不会发生的事件时所处的一种系统状态n教材上关于死锁的定义：n两个或两个以上并发进程，如果每个进程持有某种资源，而又等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。

此时，每个进程都占用了一定的资源，但又都不能向前推进这种现象称为死锁5.4 死锁5.4.2 死锁的起因计算机系统产生死锁的根本原因就是资源有限且操作不当5.4 死锁5.4.2 死锁的起因n产生死锁的四个必要条件：n1、互斥条件n2、不可剥夺条件n3、部分分配条件n4、环路等待条件互斥条件： 进程对所分配的资源进行排他性使用不可剥夺条件：进程已经获得资源，在未使用完之前，不能被剥夺，只能等到使用完成时由自己释放5.4 死锁5.4.2 死锁的起因 部分分配条件：进程已经保持了至少一个资源，但是又提出了新的资源请求，而该资源又已经被其他进程占有，此时请求进程阻塞，但对其已获资源保持不放环路等待条件：发生死锁时，必然存在一个进程资源的环形链，即进程集p1, p2, p3pn中，p1等待p2资源，p2等待p3资源5.4 死锁5.4.2 死锁的起因n一、解决死锁问题的几个策略n为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一n条件1：难以否定，但可采用相应的技术，如利用假脱机技术，即用可共享使用的设备模拟非共享的设备；n条件2：容易否定，可制定相应的规则即可，例如，当一个进程（程序）申请某资源被拒绝，则必须释放已占用的资源，如需要再与其它所需资源一起申请。

对CPU还可进行可剥夺分配5.4 死锁 5.4.3 解决死锁问题的策略n条件3：也是很容易否定的，只要分配策略上规定一个进程（或程序）一次将所需资源一次申请到位用完后释放可以全部用完后，统一释放，也可使用完后立即释放，只要是一次申请到的，系统就不会出现死锁n条件4：实际上系统不采用部分分配，也就破坏了环路条件n二、解决死锁的基本方法n1、预防死锁；n2、避免死锁；n3、检测死锁和解除死锁5.4 死锁 5.4.3 解决死锁问题的策略n一、静态资源分配法n预先分配一个进程要用的所有资源是防止死锁的一种安全而简单的方法，但设备的使用效率太低其缺点也是明显的：n1、一个用户（进程）在程序运行之前很难提出将要使用的全部设备；n2、设备（资源）的浪费太大，有些资源在进程运行过程中可能只有很少的时间才用到，有的甚至不会用到，例如，一个分支语句5.4 死锁 5.4.3 死锁的预防5.4 死锁 5.4.3 死锁的预防n二、有序资源分配法n这种算法资源按某种规则系统中的所有资源统一编号（例如打印机为1、磁带机为2、磁盘为3、等等），申请时必须以上升的次序n系统要求申请进程：1、对它所必须使用的而且属于同一类的所有资源，必须一次申请完；2、在申请不同类资源时，必须按各类设备的编号依次申请。

5.4 死锁 5.4.3死锁的预防n例如：进程PA，使用资源的顺序是R1，R2；n 进程PB，使用资源的顺序是R2，R1；n若采用动态分配有可能形成环路条件，造成死锁n采用有序资源分配法：R1的编号为1，R2的编号为2；n PA：申请次序应是：R1，R2n PB：申请次序应是：R1，R2n 这样就破坏了环路条件，预防了死锁的发生 为了提高设备的利用率，应采用动态的设备分配方法，但应设法避免发生死锁，若存在发生死锁的可能性，则拒绝分配预防死锁： 采用的分配策略本身就否定了产生死锁的四个必要条件之一，这就保证了不会发生死锁；死锁避免： 是在动态分配资源的策略下采用某种算法来预测可能发生的死锁，从而拒绝可能产生死锁的某个资源的请求5.4 死锁 5.4.4 死锁的避免5.4 死锁 5.4.4 死锁的避免n银行算法n避免死锁算法中最有代表性的算法是Dijkstra E.W 于1968年提出的银行家算法：n 该算法需要检查申请者对资源的最大需求量，如果系统现存的各类资源可以满足申请者的请求，就满足申请者的请求n这样申请者就可很快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完成，所以可避免死锁的发生。

5.4 死锁 5.4.4 死锁的避免n例子：假定系统有10个资源（为了说明问题的简单，不管它是什么资源），目前分配的情况如上表：n此时，系统中只剩下2个资源，这时就要考察能满足哪个进程，不能满足P和R的最大要求，能满足Q，于是将剩下的2个资源分配给Q，Q就能完成，然后释放所占用的6个资源n可满足P，也可满足R，这时不论分给谁都能保证完成n1、概念n安全状态：系统按照某种序列为多个进程分配资源直到最大需求，如果能够保证所有进程全部顺利执行完毕，则称系统是安全的5.4 死锁 5.4.4 死锁的避免银行家算法：实例1单一资源的银行家算法n系统中有P1, P2, P3三个进程，需要12台某设备P1需要的最大资源数量为10台，P2为4台，P3为9台在T0时刻： 在T0时刻，有安全序列（P2, P1, P3）则称在此时刻系统是安全状态n从安全状态到不安全状态的转化：如果P3再申请1台资源n2、采取的数据结构n（1）可利用资源量Available:向量，Availablej = k,表示Rj资源有k个，其数值随该类资源的分配和回收而动态改变2）最大需求矩阵Max：进程对资源的需求量maxI, j = k, 表示Pi对Rj的最大需求为k个。

n（3）分配矩阵Allocationi： Allocationi, j = k，Rj资源已经分配了k个给Pin（4）需求矩阵Needi ：还需要的资源数n NeedIi, j = k,Pi尚需要Rj资源k个n（5）请求矩阵Requestin其中存在如下关系：Max need allocation5.4 死锁 5.4.4 死锁的避免n3、银行家算法n设request：是Pi进程的请求向量，当Pi发了资源请求后，系统按下述步骤检查：（1）如果Requesti= Needi，则转向步骤（2）；否则出错;（2）若Requesti = Available，则转向步骤（3）；否则出错;（3）系统试探性地把要求的资源分配给进程Pi，并修改以下数据结构的值：Available=Available-Requesti； Allocationi= Allocationi+ Requesti； Needi= Needi- Requesti；（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给Pi进程，完成本次分配；否则，试探性分配作废，恢复原来的资源分配状态，Pi进程进入等待状态。

5.4 死锁 5.4.4 死锁的避免n4、安全性算法n（1）设置两个向量：工作向量work，它表示系统可提供给进程继续运行所需的各类资源数目，执行安全性算法开始时，work初值=Available；finish表示系统是否有足够的资源分配给进程，使之运行完成，开始时，finishi=false；当有足够资源分配给进程时，令finishi=true；n（2）从进程集合中找到满足下述条件的进程：nfinishi= false；nNeedi = work；若找到执行（3），否则执行（4）；n（3）当进程Pi获得资源后，顺序执行直到完成，并释放它的资源，执行：nwork= work+ Allocationi；nfinishi= true；ngo to step(2);n（4）若所有进程的finishi= true，则系统处于安全状态，否则，处于不安全状态 5.4 死锁 5.4.4 死锁的避免n例：系统有五个进程P0，P1，P2，P3，P4，三种类型的资源A，B，C，各种资源数量分别为10，5，7，在T0时刻资源分配情况如下表：5.4 死锁 5.4.4 死锁的避免n1、T0时刻的安全性5.4 死锁 5.4.4 死锁的避免n2、P1发出Request（1，0，2），能分配资源给它吗？n执银行家算法：n（1）Request(1,0,2)=Need(1,2,2)n（2）Request(1,0,2)= Available (3,3,2)n（3）试探性分配，修改数据结构nAvailable=Available-Request=(3,3,2)-(1,0,2)=(2,3,0)；nAllocation= Allocation+ Request=(2,0,0)+(1,0,2)=(3,0,2)；nNeed= Need- Request=(1,2,2)-(1,0,2)=(0,2,0)；5.4 死锁 5.4.4 死锁的避免n新时刻分配状态：5.4 死锁 5.4.4 死锁的避免n新时刻安全性检查：n所以系统是安全的，系统为P1分配资源成功。

5.4 死锁 5.4.4 死锁的避免n3、P4发出Request（3，3，0），能分配资源给它吗？n执银行家算法：n（1）Request(3,3,0) Available (2,3,0)n所以不能分配资源给它，它必须等待n4、P0发出Request（0，2，0），能分配资源给它吗？(若Request（0，1，0），如何？)5.4 死锁5.4.5 死锁的检测和恢复 死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，且能通过外力破坏死锁发生的必要条件，从而使并发进程从死锁状态中解脱出来5.4 死锁5.4.5 死锁的检测和恢复n死锁的检测：n 很难找到切实可行的办法n 通常的方法是程序员的经验，如UNIX系统中，可考察进程的运行时间在UNIX系统中有命令PS可显示进程占用CPU的时间，若发现有一组进程在一段时间内没有占用CPU，就认为这类进程出现了死锁5.4 死锁5.4.5 死锁的检测和恢复一、死锁检测方法：化简资源分配图法 1。