《《计算机系统与系统软件》ppt电子课件教案-第四章 资源分配与调度》由会员分享，可在线阅读，更多相关《《计算机系统与系统软件》ppt电子课件教案-第四章 资源分配与调度（45页珍藏版）》请在金锄头文库上搜索。
1、第四章 资源分配与调度概述资源分配机构资源分配策略死锁1资源执行一个程序所需要的全部硬件设备 、软件设备和数据。2资源的分类（1）物理资源程序资源3资源的分类（2）单一访问入口资源 多访问入口资源4资源的分类（3）虚拟资源资源有限而形成，目的是使每个用 户都达到似乎每个进程都拥有它申请的全部资 源的效果。如果一个用户要求的存储空间很大，则只 须将它的部分安排在主存中，其余部分留在外 存，并由OS自动实现这两类存储器之间的信息 交换，从而为用户提供了虚拟存储器。类似的还有虚拟打印机5资源管理的目标（1）正确使用资源对各种不同的资源设置相应的数据结 构，用于描述它们的特性。6资源管理的目标（2）保
2、证资源的利用率多用户、多进程共享系统资源有利于提高资源 的利用率，但须解决相应的资源分配问题。静态分配：作业所需的资源是在调度到该作 业时根据用户给出的信息进行分配，并在作业 运行完毕时释放所分配到的全部资源。动态分配：进程所需资源是在进程运行中根 据运行情况动态的分配、使用和释放。两 种 分 配 方 式7资源管理的目标（3）方便用户的使用对用户来说达到似乎拥有它所申请的 全部资源的效果。8资源管理的任务解决资源分配问题； 解决对资源的存取、使用问题； 提供对资源存取的控制和实行安全保护 措施。9资源管理功能资源数据结构确定资源的分配原则和调度原则执行资源分配存取控制和安全保护 资源信息块资源
3、描述器 TO WHOWHENHOW MUCHHOW 分配回收合法性检查10资源分配机构机构是进行资源分配所必需的基本部件：数据结构（资源信息块、资源描述器 ）互斥技术（锁原语、PV原语）等待资源的队列11资源描述器描述各类资源的最小分配单位的数据结构。 RD（Resource Descriptor）。内容：资源名、资源类型、最小分配单位的大小 、最小分配单位的地址、分配标志、勾链字、 存取权限、密级、最后一次存取时间、记帐信 息、资源其他特性。一个资源分配单位对应一个资源描述器，各 资源描述器通过某种方式组织（表、队列）。12资源信息块RIB（Recource Information Bloc
4、k），说明 资源、请求者、实施分配所需的必要信 息等待队列指针 可利用资源队列指 针 分配程序入口地址RIBPCBi PCBj PCBk RD1 RD2RDn 13中央处理机资源信息块就绪队 列指针 运行指针进程调度程序入口地 址PCBi PCBj PCBk PCBa 14中央处理机资源信息块系统中的进程在其生命周期内居留在各种队 列中，这些队列记录了进程的状态，进程状态 的改变实质上是进程在这些队列的移动。 基本队列： ALL-PROCESS-QUEUE：进程总链，记录了 系统中所以进程。进程被创建时进入该队列， 进程被撤消时从该队列删除。 READY-QUEUE：就绪队列，记录了活动的并
5、准备运行的每个进程。 WAIT-Q-QUEUE：等待队列，记录了因为某 种原因（X）而等待的进程队列。15资源分配策略先请求先服务优先调度16先请求先服务FIFO（First In First Out），也称简单排队 策略。即排队队列按照提出请求的先后 次序排序。 优点：实现简单 缺点：不对请求的特征、执行时间长短等 考虑，因而后到的短作业响应时间长。17优先调度是一种比较灵活的调度策略，可以优 先照顾需要尽快处理的作业或进程。该策略对每个进程或作业要指定一个 优先级，优先级别反映了进程要求处理 的紧迫程度。18PCBi PCBj 表头PCBk FIFO：按照请求的先后次序排序优先调度：按照优
6、先级别的高低排序先后高低19死锁两个或两个以上进程彼此之间出现互 相等待的情况，即每个进程都抓住一些 为其他进程所等待的资源不放，其结果 是谁也得不到所申请的全部资源，这样 所有的进程都无法继续进行。20死锁例（1）两小孩玩玩具，甲玩皮球，乙玩手枪， 他们都想要对方的玩具，却又都不肯让 出自己手中的玩具，于是僵局出现了 。21死锁例（2）main( ) int full=0;int empty=n;int mutex=1;cobeginproducer( );consumer( );coend Producer( ) While(生产未完成)生产一个产品；P(empty);P(mutex);送
7、一个产品到有界缓冲 区；V(mutex);V(full); Consumer( ) while(还要继续消费）P (full);P(mutex);从有界缓冲区中取产品；V(mutex);V(empty);消费一个产品； 22死锁例2结论 将P操作颠倒，会发生死锁 将V操作颠倒，不会发生死锁23死锁产生的根本原因 系统资源不足 进程推进顺序非法24产生死锁的四个必要条件（1）互斥条件：涉及的资源是非共享的，即进 程对它所需要的资源进行排他性控制。否定该条件很难。25产生死锁的四个必要条件（2）不剥夺条件：进程所获得的资源在未使用完毕前， 不能被其他进程强行夺走，即只能由获 得该资源的进程自己来释
8、放 否定该条件：容易实现，即使用抢占的进 程调度方式。26产生死锁的四个必要条件（3）部分分配进程每次申请它所需要的一部分资源 。 否定该条件：容易实现，即规定进程在获 得它所需的全部资源前，不能投入一行 。即使用静态分配方式。27产生死锁的四个必要条件（4）环路条件存在一种进程的循环链，链中的每个 进程已经获得的资源同时被链中的下一 个进程所申请。 否定该条件：否定环路，预测是否会发生 环路。28P1P2R1R229死锁的预防30 采用静态分配方法 采用有控分配方法 当死锁发生时，检测出死锁，并设法修 复3132死锁例11.竞争资源产生死锁。 设系统有打印机、读卡机各一台，它们被 进程P和Q
9、共享。两个进程并发执行，它 们按下列次序请求和释放资源：请求读卡机 请求打印机请求打印机 请求读卡机释放读卡机 释放读卡机释放打印机 释放打印机33它们执行时，相对速度无法预知，当出现 进程P占用了读卡机，进程Q占用了打印 机后，进程P又请求打印机，但因打印机 被进程Q占用，故进程P处于等待资源状 态；这时，进程Q执行，它又请求读卡机 ，但因读卡机被进程P占用而也只好处于 等待资源状态。它们分别等待对方占用 的资源，致使无法结束这种等待，产生 了死锁。34P读卡机打印机Q35死锁例2PV操作使用不当产生死锁。 设进程Q1和Q2共享两个资源r1和r2。s1和 s2是分别代表资源r1和r2能否被使
10、用的信 号量，由于资源是共享的，所以必须互 斥使用，因而s1和s2的初值均为1。假定 两个进程都要求使用两个资源，它们的 程序编制如下：36进程Q1 进程Q2 P(s1); P(s2);P(s2); P(s1); 使用r1和r2； 使用r1和r2； V(s1); V(s2);V(s2); V(s1); 37由于Q1和Q2并发执行，于是可能产生这样 的情况：进程Q1执行了P（s1）后，在执 行P（s2）之前，进程Q2执行了P（s2） ，当进程Q1再执行P（s2）时将等待，此 时，Q2再继续执行P（s1），与处于等待 。这种等待都必须由对方来释放，显然 ，这是不可能的，又产生了死锁。38死锁例3资
11、源分配不当引起死锁。 若系统中有m个资源被n个进程共享，当每个进程 都要求k个资源，而mnk时，即资源数小于进 程所要求的总数时，如果分配不得当就可能引 起死锁。例如，m=5，n=5，k=2，采用的分配 策略是为每个进程轮流分配。首先，为每个进 程轮流分配一个资源，这时，系统中的资源都 已分配完了；于是第二轮分配，各进程都处于 等待状态，导致了死锁。39死锁例4对临时性资源的使用不加限制而引起的死锁。 在进程通信时使用的信件可以看作是一种临时性 资源，如果对信件的发送和接收不加限制的话 ，则可能引起死锁。比如，进程P1等待进程P3 的信件s3来到后再向进程P2发送信件s1；P2又 要等待P1的
12、信件s1来到后再向P3发送信件s2； 而P3也要等待P2的信件s2来到后才能发出信件 s3。在这种情况下就形成了循环等待，永远结 束不了，产生死锁。40层次分配法这种分配策略将阻止循环等待条件的出现 。在层次分配策略下，资源被分成多个 层次，一个进程得到某一层的一个资源 后，它只能再申请在较高一层的资源； 当一个进程要释放某层的一个资源时， 必须先释放所占用的较高层的资源；当 一个进程获得了某一层的资源后，它所 再申请该层中的另一个资源，那么，必 须先释放该层中的已占资源。41这种策略的一个变种是按序分配策略。把系统的 所有资源排一个顺序，例如，系统共有m个资 源，用ri表示第i个资源，于是这
13、m个资源是：r1,r2, ,rm 规定任何进程不得在占用资源ri（1=i=m)后再 申请rj（jI）。不难证明，按这种策略分配资 源时不会发生死锁。事实上，若在时刻t1，进 程P1处于永远等待资源rk1的状态，则rk1必为 另一个进程假定是P2所占用。若P2可以运行到42结束，那么P1就不会处于永远等待状态；所以一 定在某个时刻t2，进程P2处于永远等待资源rk2 的状态。如此推下去，按假定，系统只有有限 个进程，即必须某个n，在时刻tn时，进程Pn永 远等待资源rkn的状态，而rkn必为前面的某个 进程Pi（1=i =n)占用。于是，按照上述的按 序分配策略，当P2占用了rk1后再申请rk2，则 必有：k1k243依次类推，可得k1k2kikn 但是，进程Pi是占有rkn申请rki，那么，必 定有：knki这就产生了矛盾。所以按序分配策略可以 防止死锁。44层次分配比静态分配在实现上要多花一点代价， 但它提高了资源使用率。然而，如果一个进程 使用资源的次序和系统内规定各层资源的次序 不同时，这种提高可能不明显。例如，一个进 程在执行中，较早地使用绘图仪，而仅到快结 束时才用磁带机。但是，系统规定，磁带机所 在层次低于绘图仪所在层次。这样，进程使用 绘图仪前就必须先申请到磁带机，这台磁带机 就在一长时间里空闲着直到进程执行到结束前 才使用，这无疑是低效率的。45
