《计算机系统与系统软件》PPT电子课件教案-第四章资源分配与调度.ppt

1,第四章 资源分配与调度,概述 资源分配机构 资源分配策略 死锁,2,资源,执行一个程序所需要的全部硬件设备、软件设备和数据。,3,资源的分类（1）,物理资源 程序资源,4,资源的分类（2）,单一访问入口资源 多访问入口资源,5,资源的分类（3）,虚拟资源资源有限而形成，目的是使每个用户都达到似乎每个进程都拥有它申请的全部资源的效果。 如果一个用户要求的存储空间很大，则只须将它的部分安排在主存中，其余部分留在外存，并由os自动实现这两类存储器之间的信息交换，从而为用户提供了虚拟存储器。 类似的还有虚拟打印机,6,资源管理的目标（1）,正确使用资源 对各种不同的资源设置相应的数据结构，用于描述它们的特性。,7,资源管理的目标（2）,保证资源的利用率 多用户、多进程共享系统资源有利于提高资源的利用率，但须解决相应的资源分配问题。 静态分配：作业所需的资源是在调度到该作业时根据用户给出的信息进行分配，并在作业运行完毕时释放所分配到的全部资源。 动态分配：进程所需资源是在进程运行中根据运行情况动态的分配、使用和释放。,两种分配方式,8,资源管理的目标（3）,方便用户的使用 对用户来说达到似乎拥有它所申请的全部资源的效果。,9,资源管理的任务,解决资源分配问题； 解决对资源的存取、使用问题； 提供对资源存取的控制和实行安全保护措施。,10,资源管理功能,资源数据结构 确定资源的分配原则和调度原则 执行资源分配 存取控制和安全保护,资源信息块 资源描述器,to who when how much how,分配 回收,合法性检查,11,资源分配机构,机构是进行资源分配所必需的基本部件： 数据结构（资源信息块、资源描述器） 互斥技术（锁原语、pv原语） 等待资源的队列,12,资源描述器,描述各类资源的最小分配单位的数据结构。 rd（resource descriptor）。 内容：资源名、资源类型、最小分配单位的大小、最小分配单位的地址、分配标志、勾链字、存取权限、密级、最后一次存取时间、记帐信息、资源其他特性。 一个资源分配单位对应一个资源描述器，各资源描述器通过某种方式组织（表、队列）。,13,资源信息块,rib（recource information block），说明资源、请求者、实施分配所需的必要信息,rib,pcbi,pcbj,pcbk,rd1,rd2,rdn,14,中央处理机资源信息块,pcbi,pcbj,pcbk,pcba,15,中央处理机资源信息块,系统中的进程在其生命周期内居留在各种队列中，这些队列记录了进程的状态，进程状态的改变实质上是进程在这些队列的移动。 基本队列： all-process-queue：进程总链，记录了系统中所以进程。进程被创建时进入该队列，进程被撤消时从该队列删除。 ready-queue：就绪队列，记录了活动的并准备运行的每个进程。 wait-q-queue：等待队列，记录了因为某种原因（x）而等待的进程队列。,16,资源分配策略,先请求先服务 优先调度,17,先请求先服务,fifo（first in first out），也称简单排队策略。即排队队列按照提出请求的先后次序排序。 优点：实现简单 缺点：不对请求的特征、执行时间长短等考虑，因而后到的短作业响应时间长。,18,优先调度,是一种比较灵活的调度策略，可以优先照顾需要尽快处理的作业或进程。 该策略对每个进程或作业要指定一个优先级，优先级别反映了进程要求处理的紧迫程度。,19,pcbi,pcbj,表头,pcbk,fifo：按照请求的先后次序排序,优先调度：按照优先级别的高低排序,先,后,高,低,20,死锁,两个或两个以上进程彼此之间出现互相等待的情况，即每个进程都抓住一些为其他进程所等待的资源不放，其结果是谁也得不到所申请的全部资源，这样所有的进程都无法继续进行。,21,死锁例（1）,两小孩玩玩具，甲玩皮球，乙玩手枪，他们都想要对方的玩具，却又都不肯让出自己手中的玩具，于是僵局出现了 。,22,死锁例（2）,main( ) int full=0; int empty=n; int mutex=1; cobegin producer( ); consumer( ); coend ,producer( ) while(生产未完成) 生产一个产品； p(empty); p(mutex); 送一个产品到有界缓冲区； v(mutex); v(full); ,consumer( ) while(还要继续消费） p (full); p(mutex); 从有界缓冲区中取产品； v(mutex); v(empty); 消费一个产品； ,23,死锁例2结论,将p操作颠倒，会发生死锁 将v操作颠倒，不会发生死锁,24,死锁产生的根本原因,系统资源不足 进程推进顺序非法,25,产生死锁的四个必要条件（1）,互斥条件：涉及的资源是非共享的，即进程对它所需要的资源进行排他性控制。 否定该条件很难。,26,产生死锁的四个必要条件（2）,不剥夺条件： 进程所获得的资源在未使用完毕前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放 否定该条件：容易实现，即使用抢占的进程调度方式。,27,产生死锁的四个必要条件（3）,部分分配 进程每次申请它所需要的一部分资源。 否定该条件：容易实现，即规定进程在获得它所需的全部资源前，不能投入一行。 即使用静态分配方式。,28,产生死锁的四个必要条件（4）,环路条件 存在一种进程的循环链，链中的每个进程已经获得的资源同时被链中的下一个进程所申请。 否定该条件：否定环路，预测是否会发生环路。,29,p1,p2,r1,r2,30,死锁的预防,31,采用静态分配方法 采用有控分配方法 当死锁发生时，检测出死锁，并设法修复,32,33,死锁例1,1.竞争资源产生死锁。 设系统有打印机、读卡机各一台，它们被进程p和q共享。两个进程并发执行，它们按下列次序请求和释放资源： 请求读卡机 请求打印机 请求打印机 请求读卡机 释放读卡机 释放读卡机 释放打印机 释放打印机,34,它们执行时，相对速度无法预知，当出现进程p占用了读卡机，进程q占用了打印机后，进程p又请求打印机，但因打印机被进程q占用，故进程p处于等待资源状态；这时，进程q执行，它又请求读卡机，但因读卡机被进程p占用而也只好处于等待资源状态。它们分别等待对方占用的资源，致使无法结束这种等待，产生了死锁。,35,p,读卡机,打印机,q,36,死锁例2,pv操作使用不当产生死锁。 设进程q1和q2共享两个资源r1和r2。s1和s2是分别代表资源r1和r2能否被使用的信号量，由于资源是共享的，所以必须互斥使用，因而s1和s2的初值均为1。假定两个进程都要求使用两个资源，它们的程序编制如下：,37,进程q1 进程q2 p(s1); p(s2); p(s2); p(s1); 使用r1和r2； 使用r1和r2； v(s1); v(s2); v(s2); v(s1); ,38,由于q1和q2并发执行，于是可能产生这样的情况：进程q1执行了p（s1）后，在执行p（s2）之前，进程q2执行了p（s2），当进程q1再执行p（s2）时将等待，此时，q2再继续执行p（s1），与处于等待。这种等待都必须由对方来释放，显然，这是不可能的，又产生了死锁。,39,死锁例3,资源分配不当引起死锁。 若系统中有m个资源被n个进程共享，当每个进程都要求k个资源，而mnk时，即资源数小于进程所要求的总数时，如果分配不得当就可能引起死锁。例如，m=5，n=5，k=2，采用的分配策略是为每个进程轮流分配。首先，为每个进程轮流分配一个资源，这时，系统中的资源都已分配完了；于是第二轮分配，各进程都处于等待状态，导致了死锁。,40,死锁例4,对临时性资源的使用不加限制而引起的死锁。 在进程通信时使用的信件可以看作是一种临时性资源，如果对信件的发送和接收不加限制的话，则可能引起死锁。比如，进程p1等待进程p3的信件s3来到后再向进程p2发送信件s1；p2又要等待p1的信件s1来到后再向p3发送信件s2；而p3也要等待p2的信件s2来到后才能发出信件s3。在这种情况下就形成了循环等待，永远结束不了，产生死锁。,41,层次分配法,这种分配策略将阻止循环等待条件的出现。在层次分配策略下，资源被分成多个层次，一个进程得到某一层的一个资源后，它只能再申请在较高一层的资源；当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源；当一个进程获得了某一层的资源后，它所再申请该层中的另一个资源，那么，必须先释放该层中的已占资源。,42,这种策略的一个变种是按序分配策略。把系统的所有资源排一个顺序，例如，系统共有m个资源，用ri表示第i个资源，于是这m个资源是： r1,r2, ,rm 规定任何进程不得在占用资源ri（1=i=m)后再申请rj（ji）。不难证明，按这种策略分配资源时不会发生死锁。事实上，若在时刻t1，进程p1处于永远等待资源rk1的状态，则rk1必为另一个进程假定是p2所占用。若p2可以运行到,43,结束，那么p1就不会处于永远等待状态；所以一定在某个时刻t2，进程p2处于永远等待资源rk2的状态。如此推下去，按假定，系统只有有限个进程，即必须某个n，在时刻tn时，进程pn永远等待资源rkn的状态，而rkn必为前面的某个进程pi（1=i =n)占用。于是，按照上述的按序分配策略，当p2占用了rk1后再申请rk2，则必有： k1k2,44,依次类推，可得 k1k2kikn 但是，进程pi是占有rkn申请rki，那么，必定有： knki 这就产生了矛盾。所以按序