操作系统第五章

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

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

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

4、者、可用资源情况和该类资源描述某类资源的请求者、可用资源情况和该类资源分配程序等必要信息的数据结构。分配程序等必要信息的数据结构。 (2) 资源信息块的内容资源信息块的内容等待队列头指针可利用资源队列头指针资源分配程序入口地址 pcb1pcb2pcbkrd1rd2rdn5.2 资源分配机构资源分配机构 (3) 中央处理机资源信息块中央处理机资源信息块 ready-q-startrunningscheduler-addr pcb1pcb2pcbkpcb5cpu - rib5.2 资源分配机构资源分配机构5.3资源分配策略当资源可用时，满足哪一个请求者？常用的分配策略:先请求先服务（FIFO）优先

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

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

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

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

9、来说，只有所需要的所有贷对于客户来说，只有所需要的所有贷款全部得到满足，这样生意才能完成，款全部得到满足，这样生意才能完成，之后才能把所贷款项归还。之后才能把所贷款项归还。贷不到款，客户死贷不到款，客户死贷款得不到归还，银行家死贷款得不到归还，银行家死起因：起因：1）系统资源不足）系统资源不足 系统资源数目系统资源数目 进程需求进程需求结论与问题：结论与问题：死锁一定是系统资源不足死锁一定是系统资源不足的，那么系统资源不足是不是一定造的，那么系统资源不足是不是一定造成死锁呢成死锁呢2）联合推进路线非法）联合推进路线非法（进程推进顺序不当）（进程推进顺序不当） 5.4.2产生死锁的起因和条件产生

10、死锁的起因和条件A2B2C2D2申请r1申请r2释放r2释放r1A1B1C1D1申请r1申请r2释放r1释放r2两进程均占用r1两进程均占用r2xyP2进展P1进展0A 死锁点 5.4.2产生死锁的起因和条件产生死锁的起因和条件路线1路线2ttt2t1死锁产生的条件 1971年Coffman总结出了对于可再使用资源，系统产生死锁必定同时保持四个必要条件：互斥条件（mutual exclusion）占有和等待条件（hold and wait）不剥夺条件（no preemption）1. 循环等待条件（circular wait）死锁产生的条件 互斥条件（mutual exclusion）：进程应

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

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

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

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

15、检测到.处理死锁的UNIX办法是忽略它,由于大多数用户宁可在极偶然的情况下产生死锁,也不愿被限制只能创建一个进程,只能打开一个文件等等.为了研究解决死锁的方法，可借助于有为了研究解决死锁的方法，可借助于有向图这一强有力的工具。图中有两种节向图这一强有力的工具。图中有两种节点：方块和圆圈。点：方块和圆圈。圆圈代表进程，方块圆圈代表进程，方块代表资源。代表资源。从资源节点从资源节点(方块方块)到进程节点到进程节点(圆圈圆圈)的的有向弧有向弧表示资源已经分配给进程表示资源已经分配给进程；从进程到资源的有向弧表示进程从进程到资源的有向弧表示进程当前正当前正处于阻塞状态，等待资源变为可用。处于阻塞状态，

16、等待资源变为可用。资源分配图资源分配图资源进程有向图 R2P1P2R1表示资源表示进程R2P1R1分配请求分配请求分配分配请求P2 5.4.2产生死锁的起因和条件产生死锁的起因和条件RASBTDUC(a)进程A 分配了一个资源(b)进程B 请求了一个资源(c)进程D和进程形成环路，已处于死锁状态资源分配图资源分配图5.4 死锁的预防死锁的预防静态分配策略静态分配策略 所谓所谓静态分配静态分配是指一个进程必须在执行前就申是指一个进程必须在执行前就申请它所要的全部资源，并且直到它所要的资源请它所要的全部资源，并且直到它所要的资源都得到满足后才开始执行。都得到满足后才开始执行。 采用静态分配后，进程

17、在执行中不再申请资源采用静态分配后，进程在执行中不再申请资源，因而，不会出现占有了某些资源再等待另一，因而，不会出现占有了某些资源再等待另一些资源的情况，即些资源的情况，即破坏了第二个条件（占有和破坏了第二个条件（占有和等待条件）等待条件）的出现。的出现。5.4 死锁的预防死锁的预防静态分配策略静态分配策略静态分配策略实现简单，被许多操作系统采静态分配策略实现简单，被许多操作系统采用。但这种策略严重地降低了资源利用率，用。但这种策略严重地降低了资源利用率，其缺点也是明显的：其缺点也是明显的：一个用户（进程）在程序运行之前很难提出一个用户（进程）在程序运行之前很难提出将要使用的全部设备；将要使用

18、的全部设备；用户的作业必须等待，直到所有的资源满足用户的作业必须等待，直到所有的资源满足时才能投入运行。实际上某些设备可能很晚时才能投入运行。实际上某些设备可能很晚的时候才使用的时候才使用5.4 死锁的预防死锁的预防静态分配策略静态分配策略设备（资源）的浪费太大，有些资源在进程运行过设备（资源）的浪费太大，有些资源在进程运行过程中可能只有很少的时间才用到，有的甚至不会用程中可能只有很少的时间才用到，有的甚至不会用到。到。 例如：一个分支语句，只有当程序出错的时候才将例如：一个分支语句，只有当程序出错的时候才将错误从打印机输出，但如果采用静态资源分配策略错误从打印机输出，但如果采用静态资源分配策

19、略的话，也要把打印机分配给这个程序，所以这种分的话，也要把打印机分配给这个程序，所以这种分配策略对系统来说是很浪费的。配策略对系统来说是很浪费的。5.4 死锁的预防死锁的预防层次分配层次分配 在层次分配策略下，资源被分成多个层次，一个进程得到某一层的一个资源后，它只能再申请在较高一层的资源；当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源。 层次分配层次分配策略将阻止第四个条件（循环等待条件）的出现。5.4 死锁的预防死锁的预防层次分配层次分配 这种策略的一个变种是按序分配策略。把系统的所有资源排列成一个顺序，例如，系统若共有n个进程，共有m个资源，用ri表示第i个资源，于是这

20、m个资源是：r1,r2,rm 规定如果进程不得在占用资源ri(1im)后再申请rj(ji)，即这种算法资源按申请多项资源时必须以上升的次序依次申请。5.4有序资源分配法 例如：进程P1，使用资源的顺序是R1，R2； 进程P2，使用资源的顺序是R2，R1； 若采用动态分配有可能形成环路条件，造成死锁。5.4有序资源分配法 采用有序资源分配法：R1的编号为1，R2的编号为2； P1：申请次序应是：R1，R2 P1：申请次序应是：R1，R2 这样就破坏了环路条件，避免了死锁的发生。5.4.5 死锁的避免 为了提高设备的利用率，应采用动态的设备分配方法，但应设法避免发生死锁，若存在发生死锁的可能性，则

21、拒绝分配。5.4.5 死锁的避免 预防死锁： 采用的分配策略本身就否定了产生死锁的四个必要条件之一，这就保证了不会发生死锁； 死锁避免： 与预防死锁相反，它允许系统中同时存在四个必要条件，如果能掌握并发进程中与每个进程有关的资源动态申请情况，做出明智和合理的选择，仍然可以避免死锁的发生。5.4.5 死锁的避免 死锁避免不是通过对进程随意强加一些规则，而是通过对每一次资源申请进行认真的分析来判断它是否能安全地分配。5.4.5 死锁的避免 问题是：是否存在一种算法总能做出正确的选择从而避免死锁？ 答案是肯定的，但条件是必须事先获得与进程有关的一些特定信息。本节将讨论使用银行家算法（银行家算法（ba

22、nkers algorithm）避免死锁的方法。银行家算法银行家算法 避免死锁算法中最有代表性的算法是Dijkstra E.W 于1968年提出的银行家算法：它的模型基于一个小城镇的银行家，现将该算法描述如下：假定一个银行家拥有资金，数量为，被N个客户共享。银行家对客户提出下列约束条件：银行家算法银行家算法 每个客户必须预先说明自己所要求的最大资金量； 每个客户每次提出部分资金量申请和获得分配； 如果银行满足了某客户对资金的最大需求量，那么，客户在资金运作后，应在有限时间内全部归还银行。银行家算法银行家算法 在银行家算法中，客户可看作进程，资金可看作资源，银行家可看作操作系统，这里叙述的是单资

23、源银行家算法，单资源的银行家算法单资源的银行家算法 在上图a中列出了4个客户，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以，他只保留10个单位的资金来为客户服务，而不是22个单位。 图（b）所示的状态是客户们各做自己的生意，在某些时刻需要贷款。客户已获得的贷款（已分配的资源）和可用的最大数额贷款称为与资源分配相关的系统状态。单资源的银行家算法 一个状态被称为是安全的，其条件是存在一个状态序列状态序列能够使所有的客户均得到其所有的贷款(即所有的进程得到所需的全部资源并终止)。单资源的银行家算法 图b所示的状态是安全的,why? 因为在有2个单位资金可用的情况下，银

24、行家可以延迟除Marvin之外的所有请求，这样便可以使Marvin运行结束，然后释放所有的4个单位资金。如此这样下去便可以满足Snganne或者Barbarn的请求，等等。 安全贷款序列：Marvin， Sugzanne， Barbarn ,Andy单资源的银行家算法 图c所示的状态，该状态是不安全的。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。 不安全状态并不一定导致死锁，因为顾客有可能不需要它的全部贷款额，但银行家不能指望这种情况发生，不敢抱这种侥幸心理。 单资源的银行家算法单资源的银行家算法总结 银行家算法就是对每一个请求进行检查，检查如

25、果满足它是否会导致不安全状态。 若是，则不满足该请求；否则便满足。 检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户满足一个距最大需求最近的客户。 如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。 单资源银行家算法总结 单资源银行家算法可陈述如下： 当一个进程提出资源请求时，当一个进程提出资源请求时，假定分配假定分配给它，给它，并检查并检查系统因此是否仍处于安全系统因此是否仍处于安全状态。状态。如果安全如果安全，则满足它的请求。，则满足它的请求。否否则，推迟它的请

26、求则，推迟它的请求。5.4.6 死锁的检测和恢复 死锁的检测： 死锁的检测代价很高； 通常的方法是程序员的经验，如UNIX系统中，可考察进程的运行时间。在UNIX系统中有命令PS可显示进程占用CPU的时间，若发现有一组进程在一段时间内没有占用CPU，就认为这类进程出现了死锁。5.4.6 死锁的检测和恢复 死锁排除的方法： 1、撤消陷于死锁的全部进程； 2、逐个撤消陷于死锁的进程，直到死锁不存在； 3、从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失。一道考研题一道考研题 下列关于银行家算法的叙述中，正确的是（ ）。 A. 银行家算法可以预防死锁 B. 当系统处于安全状态时，系统中一定无

27、死锁进程 C. 当系统处于不安全状态时，系统中一定会出现死锁进程 D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件一道考研题 某时刻进程的资源使用情况如下所示。进程已分配资源尚需资源可用资源R1R2R3R1R2R3R1 R2 R3P1200001021P2120132P3011131P4001200 此时的安全序列是（）。（11年联考） A. P1, P2, P3, P4 B. P1, P3, P2, P4 C. P1, P4, P3, P2 D. 不存在一道考研题 假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3，这些资源总数分别为18、6、22。T0时刻的资源分

28、配情况如下表所示，此时存在的一个安全序列是（）。（12年联考）进程已分配资源资源最大需求R1R2R3R1R2R3P03235510P1403536P24054011P3204425P4314424 A. P0, P1, P2, P3, P4 B. P1, P0, P3, P4, P2 C. P2, P1, P0, P3, P4 D. P3, P4, P2, P1, P0回顾：资源竞争产生死锁回顾：资源竞争产生死锁 m个资源被个资源被n个进程共享，每个进程要求个进程共享，每个进程要求k个资个资源，则当源，则当 m=n*(k-1) 时，如果分配不当就可能发时，如果分配不当就可能发生死锁。生死锁。

29、死锁的定义：在两个或多个并发进程中，如果死锁的定义：在两个或多个并发进程中，如果每个进程持有某种资源而又都等待着别的进程释放每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。它或它们现在保持着的资源，否则就不能向前推进。此时每个进程都占用了一定的资源但又都不能向前此时每个进程都占用了一定的资源但又都不能向前推进，称这一组进程产生可死锁。推进，称这一组进程产生可死锁。 某计算机系统中有8台打印机，有K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是（ ）。 A. 2B. 3C. 4D. 5死锁的避免死锁的避免 1. 1. 有序资源使用法有序资源使用法 系统中的所有资源类都分给一个唯一的序系统中的所有资源类都分给一个唯一的序号，并要求每个进程均应严格按照递增的次序号，并要求每个进程均应严格按照递增的次序请求资源。请求资源。 有序资源使用法破坏了产生死锁的环路条有序资源使用法破坏了产生死锁的环路条件，从而不可能产生死锁。件，从而不可能产生死锁。 缺点：对于实际资源使用顺序与资源序号缺点：对于实际资源使用顺序与资源序号不一致的作业仍存在着资源浪费现象。不一致的作业仍存在着资源浪费现象。 例如：例如：进程进程PA，使用资源的顺序是，使用资源的顺序是R1，R2； 进程进程PBPB，