操作系统第五章剖析

《操作系统第五章剖析》由会员分享，可在线阅读，更多相关《操作系统第五章剖析（78页珍藏版）》请在金锄头文库上搜索。

1、第五章第五章 资源分配与调度资源分配与调度 5.1 资源管理概述 5.2 资源分配机制 5.3 资源分配策略 5.4 死锁 5.1 资源管理的目的和任务 资源管理的目的： 1、保证资源的高利用率； 2、在“合理”时间内使所有“顾客(client)” 有获得所需资源的机会； 3、对不可共享的资源实施互斥使用； 4、防止由资源分配不当而引起的死锁。 5.1 5.1 资源管理功能资源管理功能 1. 资源数据结构的描述 构造资源分配所需的数据结构， 应包含该资源的物理名、逻辑名、 类型、地址、分配状态等信息。 2. 确定资源的分配原则 (调度原则) 确定资源分配原则，即决定资源 应分给谁，何时分配，分

2、配多少等 问题。 5.1.1 资源管理功能 5.1 5.1 资源管理功能资源管理功能 3. 实施资源分配 根据所确定的资源分配原则以及用户的要求， 执行资源分配。当资源使用完毕后，收回资源以 便重新分配给其他作业和进程使用。 4. 存取控制和安全保护 对资源的存取进行控制并对资源实施安全保护 措施。 （eg:文件的管理,任何一个用户对任一文件的存取 都要经过文件管理器系统中的存取控制验证模块 的检查） 5.1.1 资源管理功能 5.2 5.2 资源分配的机构资源分配的机构 1. 资源描述器 (1) 什么是资源描述器 描述各类资源的最小分配单位的数据结构称为 资源描述器 rd (resource

3、 descriptor)。 如：主存最小分配单位： 在分区分配中主存分区 磁盘最小分配单位： 磁盘面中的一个扇区 什么是资源描述器（resource descriptor？) 资源描述器的内容 资源名 资源类型 最小分配单位的大小 最小分配单位的地址 分配标志 描述器链接信息 存取权限 密级 最后一次存取时间 记账信息 2. 资源信息块 为了对每类资源实施有效的分配，我们设置相应的 资源信息块rib（resource information blcok）,这样一 个数据结构应能说明资源、请求者、实施分配所需 的必要信息。 对每一类可利用的资源，可将其组织成可利用资源 的队列。 5.2 资源分配

4、机构 2. 资源信息块 (1) 什么是资源信息块 描述某类资源的请求者、可用资源情况和该类资源 分配程序等必要信息的数据结构。 (2) 资源信息块的内容 等待队列头指针 可利用资源队列头指针 资源分配程序入口地址 pcb1pcb2pcbk rd1rd2rdn 5.2 资源分配机构 (3) 中央处理机资源信息块 ready-q-start running scheduler-addr pcb1pcb2pcbk pcb5 cpu - rib 5.2 资源分配机构 5.3资源分配策略 当资源可用时，满足哪一个请求者？ 常用的分配策略: a.先请求先服务（FIFO） b. 优先调度 c.针对设备特性的

5、调度 a.先请求先服务FIFO 先请求先服务FIFO (First In First Out) 排序原则：按请求的先后次序排序。 每一个新产生的请求均排在队尾，而当 资源可用时，资源分配程序则从队列中 选取第一个请求，并满足其需要。 先请求先服务的队列结构 a.先请求先服务FIFO 先请求先服务的队列结构 b.优先调度 在优先调度策略下，对于每一个进程要 指定一个优先级，优先级反映了进程要 求处理的紧迫程度。 排序原则：按优先级的高低排序。 每一个新产生的请求，按其优先级的 高低插到相应的位置上。而当资源可用 时，选取队列中第一个请求，并满足其 需要。 b.优先调度的队列结构 5.4 死锁的产

6、生 操作系统的基本特征是并发与共享。系统允许 多个进程并发执行，并且共享系统的软、硬件 资源。 为了最大限度的利用计算机系统的资源，操作 系统应采用动态分配系统各种资源的策略。 然而，采用这种策略时，当对某类资源的申请 数目超过这类资源的入口数目，若分配不当， 可能出现进程之间相互等资源又都不能向前推 进的情况。即造成进程相互封锁的危险。 5.4.1 死锁的概念 例子：死锁的生活中的影子 A B 假设有这么两个人A，B：地位平等且自私。 任务：每个人都独立去植树 器具：目前只有1把铲子和1个水桶 例子：死锁的生活中的影子 要求：每个人若想独立去 把植树完成，植树时必须 同时具备1把铲子和1个水

7、 桶 场景：现在，A手中有1把 铲子，B手中有1个水桶 问题：A、B两人能否分别 完成自己的任务呢？ A B 有铲子有水桶 缺水桶 缺铲子 WaitingWaiting Waiting for dead 分析 什么是死锁？ 死锁的定义： 一组进程中，每个进程都无限等待被 该组进程中另一进程所占有的资源，因 而无限期地僵持下去的局面 ，这种现象 称为进程死锁。 这一组进程就称为死锁进程 设S1=1，打印机可用。S2=1，读卡机可用。 OS中的例子 操作系统中的例子 有二个进程P1、P2，两个设备打印机R1，读卡机R2 。 P(S1)； P(S2)； P(S2)； P(S1)； V(S1)； V(

8、S2)； V(S2)； V(S1)； P1P2 P(S1)； P(S2)； V(S1)； V(S2)； P(S2)； P(S1)； V(S2)； V(S1)； P1P2 P1P2 P1P2 ？ 两种写法， 谁可能造 成死锁？ 申请R2 S2：1-1=0 占用R2 申请R1 S1：1-1=0 占用R1 申请R1，但 R1被P1占用 申请R2，但 R2被P2占用 等等等等 死锁 Hold and wait 2.银行家问题的例子 银行共有资金10万元，客户u1需贷款3万 ，客户u2需贷款8万，客户u3需贷款9万 。某一时刻： u2 u3 u1 已贷款还需资金 1万2万 2万6万 6万3万 银行只剩下

9、 一万元，造 成死锁。 5.4.1 死锁的概念行家的例子） 对于客户来说，只有所需要的所有贷 款全部得到满足，这样生意才能完成， 之后才能把所贷款项归还。 贷不到款，客户死 贷款得不到归还，银行家死 起因： 1）系统资源不足 系统资源数目 进程需求 结论与问题：死锁一定是系统资源不足 的，那么系统资源不足是不是一定造 成死锁呢 2）联合推进路线非法 （进程推进顺序不当） 5.4.2 产生死锁的起因和条件 A2 B2 C2 D2 申请r1 申请r2 释放r2 释放r1 A1B1C1D1 申请r1申请r2释放r1释放r2 两进程均占用r1两进程均占用r2 x y P2进展 P1进展 0 A 死锁点

10、 5.4.2 产生死锁的起因和条件 路线1 路线2 t t t2 t1 死锁产生的条件 1971年Coffman总结出了对于可再使用 资源，系统产生死锁必定同时保持四个 必要条件： 1. 互斥条件（mutual exclusion） 2. 占有和等待条件（hold and wait） 3. 不剥夺条件（no preemption） 4. 循环等待条件（circular wait） 死锁产生的条件 1. 互斥条件（mutual exclusion）：进程应 互斥使用资源，任一时刻一个资源仅为 一个进程独占，若另一个进程请求一个 已被占用的资源时，它被置成等待状态 ，直到占用者释放资源。 死锁产生

11、的条件 2.占有和等待条件（hold and wait）（或称 部分分配条件）：一个进程请求资源得 不到满足而等待时，不释放已占有的资 源。 死锁产生的条件 3. 不剥夺条件（no preemption）：任一进 程不能从另一进程那里抢夺资源，即已 被占用的资源，只能由占用进程自己来 释放。 4. 循环等待条件（circular wait）：存在一 个循环等待链，其中，每一个进程分别 等待它前一个进程所持有的资源，造成 永远等待。 死锁产生的条件 以上前三个条件 互斥条件（mutual exclusion） 占有和等待条件（hold and wait） 不剥夺条件（no preemption）

12、 是死锁存在的必要条件（necessary condition），但不是充分条件。 死锁产生的条件 第四个条件： 循环等待条件（circular wait） 是前三个条件同时存在时产生的结果，所以，这 些条件并不完全独立。 但单独考虑每个条件是有用的，只要能破坏 这四个必要条件之一，死锁就可防止。 5.4.3 解决死锁问题的策略-预防死锁 一、解决死锁问题的几个策略 为了不发生死锁，必须设法破坏产生死 锁的四个必要条件之一。 条件1（互斥条件）：难以否定，但可 采用相应的技术，如利用假脱机技术， 即用可共享使用的设备模拟非共享的设 备； 5.4.3 解决死锁问题的策略-预防死锁 条件2（占有和

13、等待条件）：容易否定 也容易实现，可制定相应的规则即可， 例如，当一个进程（程序）申请某资源 被拒绝，则必须释放已占用的资源，如 需要再与其它所需资源一起申请。 在资源分配策略上可以采取静态资源分 配的方式一次性的把所需资源全部分配 到位，否则就不分配。 5.4.3 解决死锁问题的策略-预防死锁 条件3（不剥夺条件）：也是很容易否定 的，只要分配策略上规定一个进程（或 程序）一次将所需资源一次申请到位。 用完后释放。可以全部用完后，统一释 放，也可使用完后立即释放，只要是一 次申请到的，系统就不会出现死锁。 5.4.3 解决死锁问题的策略-预防死锁 条件4（循环等待条件）：通过 有序资源分配法

14、，可以破坏环路 条件。 实际上系统还可以不采用部分分 配，也就破坏了环路等待条件。 死锁的解决策略 归纳起来，可以采用以下策略之一来解 决死锁问题： 忽略该问题 采用静态资源分配来预防死锁 采用有控分配方法来避免死锁 当死锁发生时检测死锁，并设法修复 鸵鸟算法 象鸵鸟一样对死锁视而不见是最简单的方法. 每个人对该方法的看法都不相同. 数学家认为要彻底防止死锁的产生,不论代价有 多大; 工程师们想要了解死锁发生的频率,系统因各种 原因崩溃的频率,以及死锁的严重程度. UNIX潜在地受到了一些死锁的威协,但是这些 死锁从来没有发生,甚至从来没有被检测到. 处理死锁的UNIX办法是忽略它,由于大多数

15、用 户宁可在极偶然的情况下产生死锁,也不愿被限 制只能创建一个进程,只能打开一个文件等等. 为了研究解决死锁的方法，可借助于有 向图这一强有力的工具。图中有两种节 点：方块和圆圈。圆圈代表进程，方块 代表资源。 从资源节点(方块)到进程节点(圆圈)的 有向弧表示资源已经分配给进程； 从进程到资源的有向弧表示进程当前正 处于阻塞状态，等待资源变为可用。 资源分配图 2.资源进程有向图 R2 P1 P2 R1 表示资源 表示进程 R2 P1 R1 分配请求 分配请求分配 分配请求 P2 5.4.2 产生死锁的起因和条件 R A S B T D U C (a)进程A 分配了 一个资源 (b)进程B 请求