下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第五章 资源分配与调度,5.1 资源管理概述 5.2 资源分配机制 5.3 资源分配策略 5.4 死锁,5.1 资源管理的目的和任务,资源管理的目的: 1、保证资源的高利用率; 2、在“合理”时间内使所有“顾客(client)”有获得所需资源的机会; 3、对不可共享的资源实施互斥使用; 4、防止由资源分配不当而引起的死锁。,5.1 资源管理功能,1. 资源数据结构的描述 构造资源分配所需的数据结构,应包含该资源的物理名、逻辑名、类型、地址、分配状态等信息。 2. 确定资源的分配原则 (调度原则) 确定资源分配原则,即决定资源应分给谁,何时分配,分配多少等问题。,5.1.1 资源管理功能,5.1
2、 资源管理功能,3. 实施资源分配 根据所确定的资源分配原则以及用户的要求,执行资源分配。当资源使用完毕后,收回资源以便重新分配给其他作业和进程使用。 4. 存取控制和安全保护 对资源的存取进行控制并对资源实施安全保护措施。 (eg:文件的管理,任何一个用户对任一文件的存取都要经过文件管理器系统中的存取控制验证模块的检查),5.1.1 资源管理功能,5.2 资源分配的机构,1. 资源描述器 (1) 什么是资源描述器 描述各类资源的最小分配单位的数据结构称为资源描述器 rd (resource descriptor)。 如:主存最小分配单位: 在分区分配中主存分区 磁盘最小分配单位: 磁盘面中的
3、一个扇区,什么是资源描述器(resource descriptor?),资源描述器的内容,2. 资源信息块 为了对每类资源实施有效的分配,我们设置相应的资源信息块rib(resource information blcok),这样一个数据结构应能说明资源、请求者、实施分配所需的必要信息。 对每一类可利用的资源,可将其组织成可利用资源的队列。,5.2 资源分配机构,2. 资源信息块 (1) 什么是资源信息块 描述某类资源的请求者、可用资源情况和该类资源分配程序等必要信息的数据结构。 (2) 资源信息块的内容,5.2 资源分配机构,(3) 中央处理机资源信息块,5.2 资源分配机构,5.3资源分配
4、策略,当资源可用时,满足哪一个请求者? 常用的分配策略: 先请求先服务(FIFO) 优先调度 针对设备特性的调度,a.先请求先服务FIFO,先请求先服务FIFO (First In First Out) 排序原则:按请求的先后次序排序。每一个新产生的请求均排在队尾,而当资源可用时,资源分配程序则从队列中选取第一个请求,并满足其需要。 先请求先服务的队列结构,a.先请求先服务FIFO,先请求先服务的队列结构,b.优先调度,在优先调度策略下,对于每一个进程要指定一个优先级,优先级反映了进程要求处理的紧迫程度。 排序原则:按优先级的高低排序。每一个新产生的请求,按其优先级的高低插到相应的位置上。而当
5、资源可用时,选取队列中第一个请求,并满足其需要。,b.优先调度的队列结构,5.4 死锁的产生,操作系统的基本特征是并发与共享。系统允许多个进程并发执行,并且共享系统的软、硬件资源。 为了最大限度的利用计算机系统的资源,操作系统应采用动态分配系统各种资源的策略。 然而,采用这种策略时,当对某类资源的申请数目超过这类资源的入口数目,若分配不当,可能出现进程之间相互等资源又都不能向前推进的情况。即造成进程相互封锁的危险。,5.4.1 死锁的概念,例子:死锁的生活中的影子,A,B,假设有这么两个人A,B:地位平等且自私。 任务:每个人都独立去植树 器具:目前只有1把铲子和1个水桶,例子:死锁的生活中的
6、影子,要求:每个人若想独立去把植树完成,植树时必须同时具备1把铲子和1个水桶 场景:现在,A手中有1把铲子,B手中有1个水桶 问题:A、B两人能否分别完成自己的任务呢?,A,B,有铲子,有水桶,缺水桶,缺铲子,Waiting,Waiting,Waiting for dead,分析,什么是死锁?,死锁的定义: 一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而无限期地僵持下去的局面 ,这种现象称为进程死锁。 这一组进程就称为死锁进程,OS中的例子,等,等,死锁,Hold and wait,银行家问题的例子 银行共有资金10万元,客户u1需贷款3万,客户u2需贷款8万,客户u3需
7、贷款9万 。某一时刻:,5.4.1 死锁的概念行家的例子),对于客户来说,只有所需要的所有贷款全部得到满足,这样生意才能完成,之后才能把所贷款项归还。 贷不到款,客户死 贷款得不到归还,银行家死,起因: 1)系统资源不足 系统资源数目 进程需求 结论与问题:死锁一定是系统资源不足的,那么系统资源不足是不是一定造成死锁呢 2)联合推进路线非法 (进程推进顺序不当),5.4.2产生死锁的起因和条件,A 死锁点,5.4.2产生死锁的起因和条件,路线1,路线2,t,t,t2,t1,死锁产生的条件,1971年Coffman总结出了对于可再使用资源,系统产生死锁必定同时保持四个必要条件: 互斥条件(mut
8、ual exclusion) 占有和等待条件(hold and wait) 不剥夺条件(no preemption) 循环等待条件(circular wait),死锁产生的条件,互斥条件(mutual exclusion):进程应互斥使用资源,任一时刻一个资源仅为一个进程独占,若另一个进程请求一个已被占用的资源时,它被置成等待状态,直到占用者释放资源。,死锁产生的条件,2.占有和等待条件(hold and wait)(或称部分分配条件):一个进程请求资源得不到满足而等待时,不释放已占有的资源。,死锁产生的条件,不剥夺条件(no preemption):任一进程不能从另一进程那里抢夺资源,即已被
9、占用的资源,只能由占用进程自己来释放。 循环等待条件(circular wait):存在一个循环等待链,其中,每一个进程分别等待它前一个进程所持有的资源,造成永远等待。,死锁产生的条件,以上前三个条件 互斥条件(mutual exclusion) 占有和等待条件(hold and wait) 不剥夺条件(no preemption) 是死锁存在的必要条件(necessary condition),但不是充分条件。,死锁产生的条件,第四个条件: 循环等待条件(circular wait) 是前三个条件同时存在时产生的结果,所以,这些条件并不完全独立。 但单独考虑每个条件是有用的,只要能破坏这四个
10、必要条件之一,死锁就可防止。,5.4.3 解决死锁问题的策略-预防死锁,一、解决死锁问题的几个策略 为了不发生死锁,必须设法破坏产生死锁的四个必要条件之一。 条件1(互斥条件):难以否定,但可采用相应的技术,如利用假脱机技术,即用可共享使用的设备模拟非共享的设备;,5.4.3 解决死锁问题的策略-预防死锁,条件2(占有和等待条件):容易否定也容易实现,可制定相应的规则即可,例如,当一个进程(程序)申请某资源被拒绝,则必须释放已占用的资源,如需要再与其它所需资源一起申请。 在资源分配策略上可以采取静态资源分配的方式一次性的把所需资源全部分配到位,否则就不分配。,5.4.3 解决死锁问题的策略-预
11、防死锁,条件3(不剥夺条件):也是很容易否定的,只要分配策略上规定一个进程(或程序)一次将所需资源一次申请到位。用完后释放。可以全部用完后,统一释放,也可使用完后立即释放,只要是一次申请到的,系统就不会出现死锁。,5.4.3 解决死锁问题的策略-预防死锁,条件4(循环等待条件):通过有序资源分配法,可以破坏环路条件。 实际上系统还可以不采用部分分配,也就破坏了环路等待条件。,死锁的解决策略,归纳起来,可以采用以下策略之一来解决死锁问题: 忽略该问题 采用静态资源分配来预防死锁 采用有控分配方法来避免死锁 当死锁发生时检测死锁,并设法修复,鸵鸟算法,象鸵鸟一样对死锁视而不见是最简单的方法. 每个
12、人对该方法的看法都不相同. 数学家认为要彻底防止死锁的产生,不论代价有多大; 工程师们想要了解死锁发生的频率,系统因各种原因崩溃的频率,以及死锁的严重程度. UNIX潜在地受到了一些死锁的威协,但是这些死锁从来没有发生,甚至从来没有被检测到.处理死锁的UNIX办法是忽略它,由于大多数用户宁可在极偶然的情况下产生死锁,也不愿被限制只能创建一个进程,只能打开一个文件等等.,为了研究解决死锁的方法,可借助于有向图这一强有力的工具。图中有两种节点:方块和圆圈。圆圈代表进程,方块代表资源。 从资源节点(方块)到进程节点(圆圈)的有向弧表示资源已经分配给进程; 从进程到资源的有向弧表示进程当前正处于阻塞状
13、态,等待资源变为可用。,资源分配图,资源进程有向图,5.4.2产生死锁的起因和条件,(a)进程A 分配了一个资源,(b)进程B 请求了一个资源,(c)进程D和进程形成环路,已处于死锁状态,资源分配图,5.4 死锁的预防静态分配策略,所谓静态分配是指一个进程必须在执行前就申请它所要的全部资源,并且直到它所要的资源都得到满足后才开始执行。 采用静态分配后,进程在执行中不再申请资源,因而,不会出现占有了某些资源再等待另一些资源的情况,即破坏了第二个条件(占有和等待条件)的出现。,5.4 死锁的预防静态分配策略,静态分配策略实现简单,被许多操作系统采用。但这种策略严重地降低了资源利用率,其缺点也是明显
14、的: 一个用户(进程)在程序运行之前很难提出将要使用的全部设备; 用户的作业必须等待,直到所有的资源满足时才能投入运行。实际上某些设备可能很晚的时候才使用,5.4 死锁的预防静态分配策略,设备(资源)的浪费太大,有些资源在进程运行过程中可能只有很少的时间才用到,有的甚至不会用到。 例如:一个分支语句,只有当程序出错的时候才将错误从打印机输出,但如果采用静态资源分配策略的话,也要把打印机分配给这个程序,所以这种分配策略对系统来说是很浪费的。,5.4 死锁的预防层次分配,在层次分配策略下,资源被分成多个层次,一个进程得到某一层的一个资源后,它只能再申请在较高一层的资源;当一个进程要释放某层的一个资
15、源时,必须先释放所占用的较高层的资源。 层次分配策略将阻止第四个条件(循环等待条件)的出现。,5.4 死锁的预防层次分配,这种策略的一个变种是按序分配策略。把系统的所有资源排列成一个顺序,例如,系统若共有n个进程,共有m个资源,用ri表示第i个资源,于是这m个资源是:r1,r2,rm 规定如果进程不得在占用资源ri(1im)后再申请rj(ji),即这种算法资源按申请多项资源时必须以上升的次序依次申请。,5.4有序资源分配法,例如:进程P1,使用资源的顺序是R1,R2; 进程P2,使用资源的顺序是R2,R1; 若采用动态分配有可能形成环路条件,造成死锁。,5.4有序资源分配法,采用有序资源分配法
16、:R1的编号为1,R2的编号为2; P1:申请次序应是:R1,R2 P1:申请次序应是:R1,R2 这样就破坏了环路条件,避免了死锁的发生。,5.4.5 死锁的避免,为了提高设备的利用率,应采用动态的设备分配方法,但应设法避免发生死锁,若存在发生死锁的可能性,则拒绝分配。,5.4.5 死锁的避免,预防死锁: 采用的分配策略本身就否定了产生死锁的四个必要条件之一,这就保证了不会发生死锁; 死锁避免: 与预防死锁相反,它允许系统中同时存在四个必要条件,如果能掌握并发进程中与每个进程有关的资源动态申请情况,做出明智和合理的选择,仍然可以避免死锁的发生。,5.4.5 死锁的避免,死锁避免不是通过对进程
17、随意强加一些规则,而是通过对每一次资源申请进行认真的分析来判断它是否能安全地分配。,5.4.5 死锁的避免,问题是:是否存在一种算法总能做出正确的选择从而避免死锁? 答案是肯定的,但条件是必须事先获得与进程有关的一些特定信息。本节将讨论使用银行家算法(bankers algorithm)避免死锁的方法。,银行家算法,避免死锁算法中最有代表性的算法是Dijkstra E.W 于1968年提出的银行家算法:它的模型基于一个小城镇的银行家,现将该算法描述如下:假定一个银行家拥有资金,数量为,被N个客户共享。银行家对客户提出下列约束条件:,银行家算法,每个客户必须预先说明自己所要求的最大资金量; 每个
18、客户每次提出部分资金量申请和获得分配; 如果银行满足了某客户对资金的最大需求量,那么,客户在资金运作后,应在有限时间内全部归还银行。,银行家算法,在银行家算法中,客户可看作进程,资金可看作资源,银行家可看作操作系统,这里叙述的是单资源银行家算法,,单资源的银行家算法,单资源的银行家算法,在上图a中列出了4个客户,每个客户都有一个贷款额度,银行家知道不可能所有客户同时都需要最大贷款额,所以,他只保留10个单位的资金来为客户服务,而不是22个单位。 图(b)所示的状态是客户们各做自己的生意,在某些时刻需要贷款。客户已获得的贷款(已分配的资源)和可用的最大数额贷款称为与资源分配相关的系统状态。,单资
19、源的银行家算法,一个状态被称为是安全的,其条件是存在一个状态序列能够使所有的客户均得到其所有的贷款(即所有的进程得到所需的全部资源并终止)。,单资源的银行家算法,图b所示的状态是安全的,why? 因为在有2个单位资金可用的情况下,银行家可以延迟除Marvin之外的所有请求,这样便可以使Marvin运行结束,然后释放所有的4个单位资金。如此这样下去便可以满足Snganne或者Barbarn的请求,等等。 安全贷款序列:Marvin, Sugzanne, Barbarn ,Andy,单资源的银行家算法,图c所示的状态,该状态是不安全的。如果忽然所有的客户都申请,希望得到最大贷款额,而银行家无法满足
20、其中任何一个的要求,则发生死锁。 不安全状态并不一定导致死锁,因为顾客有可能不需要它的全部贷款额,但银行家不能指望这种情况发生,不敢抱这种侥幸心理。,单资源的银行家算法,单资源的银行家算法总结,银行家算法就是对每一个请求进行检查,检查如果满足它是否会导致不安全状态。 若是,则不满足该请求;否则便满足。 检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。 如果可以,则这笔投资认为是能够收回的,然后接着检查下一个距最大需求最近的客户,如此反复下去。如果所有投资最终都被收回,则该状态是安全的,最初的请求可以批准。,单资源银行家算法总结,单资源银行家算法可陈述如下: 当一个进程
21、提出资源请求时,假定分配给它,并检查系统因此是否仍处于安全状态。如果安全,则满足它的请求。否则,推迟它的请求。,5.4.6 死锁的检测和恢复,死锁的检测: 死锁的检测代价很高; 通常的方法是程序员的经验,如UNIX系统中,可考察进程的运行时间。在UNIX系统中有命令PS可显示进程占用CPU的时间,若发现有一组进程在一段时间内没有占用CPU,就认为这类进程出现了死锁。,5.4.6 死锁的检测和恢复,死锁排除的方法: 1、撤消陷于死锁的全部进程; 2、逐个撤消陷于死锁的进程,直到死锁不存在; 3、从陷于死锁的进程中逐个强迫放弃所占用的资源,直至死锁消失。,一道考研题,下列关于银行家算法的叙述中,正
22、确的是( )。 A. 银行家算法可以预防死锁 B. 当系统处于安全状态时,系统中一定无死锁进程 C. 当系统处于不安全状态时,系统中一定会出现死锁进程 D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件,一道考研题,某时刻进程的资源使用情况如下所示。,此时的安全序列是()。(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时刻的资源分配情况如下表所示,此时存在的一个安全序列是()。(12年联考),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) 时,如果分配不当就可能发生死锁。 死锁的定义:在两个或多个并发进程中,如果每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源,否则就不能向前推进。此时每个进程都占用了一定的资源但又都不能向前推进,称这一组进程产生可死锁。,某计算机
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年道法课堂模拟试卷(含答案)
- 2026年手术室院感题库及参考答案
- 汽车财务面试题库及答案
- 2026年烟台保安考试题库及参考答案
- 2026年社工考试类型题库及答案
- 口腔颌面影像诊断学考核试题题库带答案
- 2026年宪法题库考试卷及参考答案
- 2026年乐理题型艺模拟试卷(含答案)
- 旋盘尾丝虫病复查模拟试卷(含答案)
- 控制总量考试题库及答案
- 描写河西走廊的古诗
- 文心雕龙课件
- 松下-GF2-相机说明书
- 专题18 传送带模型(学生版)新高一物理多维度导学与分层专练
- 布比卡因脂质体注射液-临床用药解读
- 统计学基础与应用课件
- 传感器的应用与调试高职全套教学课件
- 【影片中的非线性叙事结构的实例研究(论文)】
- 为孩子培养良好的习惯【一年级家长会】讲座用课件
- 2023学年完整公开课版孔子论孝
- JJG 452-2021黑白密度片
评论
0/150
提交评论