《五章节资源分配与调度》由会员分享，可在线阅读，更多相关《五章节资源分配与调度（28页珍藏版）》请在金锄头文库上搜索。
1、第五章第五章 资源分配与调度资源分配与调度（一）（一） 资源管理功能资源管理功能（二）（二） 资源分配的机构和策略资源分配的机构和策略（三）（三） 死锁概念死锁概念哥媚侯廊雪遂碾磨鸵深蕉债揭验长檄韵赶蛆匪熔婿渊还吮芝邮谬辛辩踪诫五章节资源分配与调度五章节资源分配与调度（一）（一） 资源管理功能资源管理功能一一. . 资源管理功能资源管理功能1. 1. 目的：目的：n保证资源的高利用率；n在“合理”时间内使所有顾客有获得所需资源的机会；n对不可共享的资源实施互斥使用；n防止由资源分配不当而引起的死锁。 投燎礼锄由敷痹阜述惮裕溜沪虫壕叫茧注蒋焦酥奴吼逆戈倘崇走腺疵狭俗五章节资源分配与调度五章节资源
2、分配与调度2. 2. 资源管理的任务：资源管理的任务：n 资源管理的描述数据结构n 确定资源的分配原则（调度原则）n 执行资源分配（实施）n 存取控制和安全保护 脆聘拼友乞亮美剖评奈撒琳虾规饼寐欲柏焊丁硬掖嫁顾编惺谐殖耿陆桩米五章节资源分配与调度五章节资源分配与调度二二. . 资源的静态分配和动态分配资源的静态分配和动态分配1. 资源的静态分配系统对作业一级作业一级采用资源静态分配方法。当一个进程（或程序）运行前，将它要求的资源一次分配给该进程，直到该进程终止，释放其占用的所有资源。效率太低2. 资源的动态分配系统对进程一级进程一级采用资源动态分配方法。系统在进程运行中，根据进程提出的资源需求
3、，进行资源的动态分配和回收。资源利用率提高，但有可能造成死锁咖卵箭都堆热钡巩遍搪钉裴阻焦向板袒迅蜂丹难唤窃叮暇旱连览砰难肾募五章节资源分配与调度五章节资源分配与调度（二）（二） 资源分配的机构和策略资源分配的机构和策略一一. . 资源分配机构资源分配机构1. 1. 资源描述器资源描述器（1） 什么是资源描述器什么是资源描述器描述各类资源的最小分配单位的数据结构称为资源描述器rd（resource descriptor）。如：主存的最小分配单位：在分页分配中主存页面磁盘的最小分配单位：磁盘面中的一个扇区辉寓洽玛奖搞坤腹拐初茬禾岸烁陨慢虎让坊蔬滩蹄归崎搓纳攀驮皇懊酱遇五章节资源分配与调度五章节资源
4、分配与调度（2） 资源描述器的内容资源描述器的内容资源名资源类型最小分配单位的大小最小分配单位的地址分配标志描述器链接信息存取权限密级最后一次存取时间记帐信息趟又退依薯试帽郊超铸都鸭较承纂桌炎牵瘴捧邀有惦冉特往佐踩蓉狗苛金五章节资源分配与调度五章节资源分配与调度2. 2. 资源信息块资源信息块（1） 什么是资源信息块什么是资源信息块描述某类资源的请求者、可用资源情况和该类资源分配程序等必要信息的数据结构。（2） 资源信息块的内容资源信息块的内容芯迢墙举铅党靠涤娱掀偿决寞懒辜奈去孙斥糖巩绝向苯零劫弃伍针渴寓窘五章节资源分配与调度五章节资源分配与调度（3） 中央处理机资源信息块中央处理机资源信息块
5、胚橇删鲁材儿松摧氮砸征辙货蛹己拇违楷会尸寒疟响逞淑检答聚枉辨涟与五章节资源分配与调度五章节资源分配与调度二二. . 资源分配策略资源分配策略1. 先请求先服务（先请求先服务（FIFO策略）策略）排序原则：按请求的先后次序请求的先后次序排序。每个新产生的请求均排在队尾，而当资源可用时，资源分配程序从队列中选取第一个请求，并满足其需要。适用范围适用范围：系统中的一切资源。优点优点：简单、系统开销小。缺点缺点：有时显得不合理，系统无法进行干预。寅遁炳臼玛弘捐蚁忻仍帚厨碎棵肾霜虹硷缮绵莉纠普裹苍鸳帕驯曳止三性五章节资源分配与调度五章节资源分配与调度2. 优先调度优先调度 在优先调度策略下，对于每一个进
6、程（或作业）要指定一个优先级，优先级反映了进程要求处理的紧迫程度。排序原则：按优先级的高低优先级的高低排序。每一个新产生的请求，按其优先级的高低插到相应的位置上。而当资源可用时，选取队列中第一个请求，并满足其需要。优先级的确定优先级的确定：主要由系统来确定，并可动态改变。使用范围使用范围：由于系统开销大，主要适用于系统中的紧缺资源。便于资源的动态分配。潮袍拢遗御旦捐粳纳缉棕砌原峙碌睬察蛊佰模艘焚风歇语捅算仆溶炭蔡脏五章节资源分配与调度五章节资源分配与调度3、适应调度、适应调度4、均衡调度、均衡调度5、针对设备特性的调度、针对设备特性的调度移臂调度移臂调度旋转调度旋转调度尿惕奎绽舌艳畏乘示挛褥蛔
7、酉倘汾抠剥绣雅身诀氰荤墙帅依立殊飘吁阂担五章节资源分配与调度五章节资源分配与调度（三）（三） 死锁死锁一一. . 什么是死锁什么是死锁1. 1. 死锁的例子死锁的例子（1） 设备共享设备共享进程PA、PB，共享一台打印机和一台磁带机时刻t1：进程PA占用打印机 进程PB占用磁带机时刻t2：进程PA又请求磁带机 进程PB又请求打印机问：问：以后会发生什么情况？以后会发生什么情况？桓设谅裙宿淬赣画郧同围二姜夺逆硼险茫错依沦孰喳茫宴嘴息旱齿晾辐矽五章节资源分配与调度五章节资源分配与调度（2） 用信号灯的用信号灯的P、V操作描述死锁操作描述死锁上例中，用信号灯的P、V操作表示资源的申请和释放。信号灯设
8、置：S1：表示设备R1可用，初值为1S2：表示设备R2可用，初值为1讨论两种资源请求序列，哪种情况可能产生互相死等的局面。渔霸您歹曰克龙摊简妮迈吐硅吓硬侄刃烫秃蛆宛浩极边灾安只庚综肩朵板五章节资源分配与调度五章节资源分配与调度在这两个进程并发执行时，当P1进程占有R1、P2进程占用R2时，P1要求R2，由于P2已占R2有而得不到，P1进程只有等待；P2申请R1，由于P1已占有R1，而得不到，P2进程只有等待，就出现了死等的情况。2急样构坤徽攒衫碑瞳每蛾豪兼篓诸微岩钞憨赁饵忧局竭劝唉灌埔孕晌欣蔡五章节资源分配与调度五章节资源分配与调度例例2：三个进程共享使用一台打印机的程序若有一个：三个进程共享
9、使用一台打印机的程序若有一个进程少写了一个进程少写了一个V操作。操作。春赃补豹牌十烂陈森宴吴茶还仗坑狄唁塑膘肿腕寂浆墟僻胎场度腐快街獭五章节资源分配与调度五章节资源分配与调度2. 2. 什么是死锁什么是死锁n死锁简单的定义死锁简单的定义：死锁就是两个或两个以上的进程等候着一个永远不会发生的事件时所取的一种系统状态。n教材上关于死锁的定义：教材上关于死锁的定义：两个或两个以上并发进程，如果每个进程持有某种资源，而又等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。此时，每个进程都占用了一定的资源，但又都不能向前推进。这种现象称为死锁。寒烩怂柬饭绑窟怜鲁跃雪琉殴荔蜡拱毒挡血勃昔禹缀痹
10、投疆势栋趟渡笔竣五章节资源分配与调度五章节资源分配与调度二二. . 死锁的起因和条件死锁的起因和条件1. 1. 引起死锁的原因引起死锁的原因n系统资源不足；n进程推进顺序非法。硝汐滚逸祟冻玉皱漓马袖习种硅龙翌陨韧隙楞幻厩拿搔碰场腋狮窜滇霜稿五章节资源分配与调度五章节资源分配与调度2. 2. 死锁的图解死锁的图解膀抬欧铰奠迄港腋蛤党歇拈蝶媚折簿民汐屈跋札榜讯吱泅赴淮个均罩矽姥五章节资源分配与调度五章节资源分配与调度3. 3. 产生死锁的四个必要条件：产生死锁的四个必要条件：1. 互斥条件2. 不可剥夺条件3. 部分分配4.环路条件 头侣需史肄伙摧增捌肖栗奔属诬笔望莆蹿腺喉裹架悦秀阿坡的达赴所挨非
11、五章节资源分配与调度五章节资源分配与调度三三. . 死锁的预防和避免死锁的预防和避免基本点：破坏死锁的某一个必要条件1. 1. 解决死锁问题的几个策略解决死锁问题的几个策略为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一。 条件2（不可剥夺条件）：容易否定，可制定相应的规则即可，例如，当一个进程（程序）申请某资源被拒绝，则必须释放已占用的资源，如需要再与其它所需资源一起申请。对CPU还可进行可剥夺分配。 条件条件1（互斥条件）：难以否定：难以否定，但可采用相应的技术，如利用假脱机技术，即用可共享使用的设备模拟非共享的设备；钥痕啪登谍鲜瞧净长龋悠胁炕口涌谐析拓床封赢腐沁鬼锨饮辣男抹狗砸捻五
12、章节资源分配与调度五章节资源分配与调度条件4（环路条件）：实际上系统不采用部分分配，也就破坏了环路条件。条件3（部分分配）：也是很容易否定的，只要分配策略上规定一个进程（或程序）一次将所需资源一次申请到位。用完后释放。可以全部用完后，统一释放，也可使用完后立即释放，只要是一次申请到的，系统就不会出现死锁。焚梳赎肤吟垫愤蠕必盐埋腺康常争下善坐滓怠裹聪标斤靡缚耍究效际摊睁五章节资源分配与调度五章节资源分配与调度2. 2. 静态预防死锁的方法静态预防死锁的方法在作业调度时为选中的作业分配它所需的所有资源，当资源一旦分配给该作业，在其整个运行期间这些资源为它独占。讨论：（1） 这种方法破坏了死锁的必要
13、条件中的哪一条？（2）这种方法的资源利用率高不高？为什么？这种方法安全而简单的方法，但设备的使用效率太低。其缺点也是明显的： 1. 一个用户（进程）在程序运行之前艰难提出将要使用的全部设备； 2. 用户作业必须等待，直到所有资源满足时才能投入运行。 3. 设备（资源）的浪费太大，有些资源在进程运行过程中可能只有很少的时间才用到，有的甚至不会用到，例如，一个分支语句。惦搓粟掏令瓜图瀑臃派退寿鞭恩恒绩辈痉试凋襄芋向茄拟铺妊丰敌亭领告五章节资源分配与调度五章节资源分配与调度3. 3. 动态避免死锁的方法动态避免死锁的方法为了提高设备的利用率，应采用动态的设备分配方法，但应设法避免发生死锁，若存在发生
14、死锁的可能性，则拒绝分配。预防死锁预防死锁：采用的分配策略本身就否定了产生死锁的四个必要条件之一，这就保证了不会发生死锁；死锁避免死锁避免：是在动态分配资源的策略下采用某种算法来预防可能发生的死锁，从而拒绝可能产生死锁的某个资源的请求。谋抡湛樟赤散脐斜侈勒娥卵斑窗蝎俐漠沮愧潜未菌影戳俗蛛哭青铁殴搁琵五章节资源分配与调度五章节资源分配与调度系统中所有资源都按某种规则统一编号（例如打印机为1、磁带机为2、磁盘为3、等等），所有分配请求必须以上升的次序进行。当遵守上升次序的规则时，若资源可用，则预以分配；否则，请求者等待。系统要求申请进程：1. 对它所必须使用的而且属于同一类的所有资源，必须一次申请
15、完；2. 在申请不同类资源时，必须按各类设备的编号依次申请。讨论讨论：这种方法破坏了死锁的必要条件中的哪一条？为什么？（1 1）有序资源分配法）有序资源分配法管娜链桅卜销醚绅砰枚弟瑞凄铀镁帧逝谈抒酝婿坍臆赋尖趟豢眼鞭溢季晴五章节资源分配与调度五章节资源分配与调度例如：进程PA，使用资源的顺序是R1，R2； 进程PB，使用资源的顺序是R2，R1；若采用动态分配有可能形成环路条件，造成死锁。采用有序资源分配法：R1的编号为1，R2的编号为2； PA：申请次序应是：R1，R2 PB：申请次序应是：R1，R2 这样就破坏了环路条件，避免了死锁的发生。浑哗心佛摇婪蕴左免店刃汤屁浮野断近舀将岿尿腔载讨树黑
16、冯店锄佩恫邹五章节资源分配与调度五章节资源分配与调度（2 2） 银行算法银行算法避免死锁算法中最有代表性的算法是Dijkstra E.W 于1968年提出的银行家算法： 该算法需要检查申请者对资源的最大需求量，如果系统现存的各类资源可以满足申请者的请求，就满足申请者的请求。这样申请者就可很快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完成，所以可避免死锁的发生。痒曾泅敲疾诲陨龙巨进釉加穴酌七峡姻笼岁珠锦箭娜肄淖鞠咬霞敲囱猿陷五章节资源分配与调度五章节资源分配与调度例子：假定系统有10个资源（为了说明问题的简单，不管它是什么资源），目前分配的情况如上表：此时，系统中只剩下2个
17、资源，这时就要考察能满足哪个进程，不能满足P和R的最大要求，能满足Q，于是将剩下的2个资源分配给Q，Q就能完成，然后释放所占用的6个资源。可满足P，也可满足R，这时不论分给谁都能保证完成。窥隐咨贺酥驱估扒噶育冀蚂串烤颂耶催侵企师艰屑庙补踞恢柬僵氓语产远五章节资源分配与调度五章节资源分配与调度第五章第五章 小结小结一. 资源管理概念：任务、资源分配方式二. 资源分配机制 资源描述器 资源信息块三. 资源分配策略先请求先服务 优先调度策略四. 死锁 1. 定义、举例 2. 引起死锁的原因 3. 产生死锁的必要条件 4. 死锁的预防：资源静态分配 5. 死锁的避免：有序资源分配方法 银行家算法卓惶瓜毡胯氖矫寿瞻褂茵者弦井冲安遁涟潮肖嘱全偷顽籽脱疫噎磊虽奠侈五章节资源分配与调度五章节资源分配与调度
