最新操作系统第五章分析课件PPT.ppt 91页

'操作系统第五章分析 5.1资源管理的目的和任务资源管理的目的：1、保证资源的高利用率；2、在“合理”时间内使所有“顾客(client)”有获得所需资源的机会；3、对不可共享的资源实施互斥使用；4、防止由资源分配不当而引起的死锁。 5.1资源管理功能1.资源数据结构的描述构造资源分配所需的数据结构，应包含该资源的物理名、逻辑名、类型、地址、分配状态等信息。2.确定资源的分配原则(调度原则)确定资源分配原则，即决定资源应分给谁，何时分配，分配多少等问题。5.1.1资源管理功能 资源描述器的内容资源名资源类型最小分配单位的大小最小分配单位的地址分配标志描述器链接信息存取权限密级最后一次存取时间记账信息 2.资源信息块为了对每类资源实施有效的分配，我们设置相应的资源信息块rib（resourceinformationblcok）,这样一个数据结构应能说明资源、请求者、实施分配所需的必要信息。对每一类可利用的资源，可将其组织成可利用资源的队列。5.2资源分配机构 2.资源信息块(1)什么是资源信息块描述某类资源的请求者、可用资源情况和该类资源分配程序等必要信息的数据结构。(2)资源信息块的内容等待队列头指针可利用资源队列头指针资源分配程序入口地址pcb1pcb2pcbkrd1rd2rdn5.2资源分配机构 (3)中央处理机资源信息块ready-q-startrunningscheduler-addrpcb1pcb2pcbkpcb5cpu-rib5.2资源分配机构 5.3资源分配策略当资源可用时，满足哪一个请求者？常用的分配策略:先请求先服务（FIFO）优先调度针对设备特性的调度 a.先请求先服务FIFO先请求先服务FIFO(FirstInFirstOut)排序原则：按请求的先后次序排序。  每一个新产生的请求均排在队尾，而当资源可用时，资源分配程序则从队列中选取第一个请求，并满足其需要。先请求先服务的队列结构 a.先请求先服务FIFO先请求先服务的队列结构 b.优先调度在优先调度策略下，对于每一个进程要指定一个优先级，优先级反映了进程要求处理的紧迫程度。排序原则：按优先级的高低排序。每一个新产生的请求，按其优先级的高低插到相应的位置上。而当资源可用时，选取队列中第一个请求，并满足其需要。 b.优先调度的队列结构 5.4死锁的产生操作系统的基本特征是并发与共享。系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计算机系统的资源，操作系统应采用动态分配系统各种资源的策略。然而，采用这种策略时，当对某类资源的申请数目超过这类资源的入口数目，若分配不当，可能出现进程之间相互等资源又都不能向前推进的情况。即造成进程相互封锁的危险。 5.4.1死锁的概念 例子：死锁的生活中的影子AB假设有这么两个人A，B：地位平等且自私。任务：每个人都独立去植树器具：目前只有1把铲子和1个水桶 例子：死锁的生活中的影子要求：每个人若想独立去把植树完成，植树时必须同时具备1把铲子和1个水桶场景：现在，A手中有1把铲子，B手中有1个水桶问题：A、B两人能否分别完成自己的任务呢？ AB有铲子有水桶缺水桶缺铲子Waiting…Waiting…Waitingfordead…分析… 什么是死锁？死锁的定义：   一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而无限期地僵持下去的局面，这种现象称为进程死锁。这一组进程就称为死锁进程 设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)；P1P2P(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占用等等死锁Holdandwait 银行家问题的例子银行共有资金10万元，客户u1需贷款3万，客户u2需贷款8万，客户u3需贷款9万。某一时刻：u2u3u1已贷款还需资金1万2万2万6万6万3万银行只剩下一万元，造成死锁。5.4.1死锁的概念行家的例子）对于客户来说，只有所需要的所有贷款全部得到满足，这样生意才能完成，之后才能把所贷款项归还。贷不到款，客户死贷款得不到归还，银行家死 起因：1）系统资源不足系统资源数目<进程需求结论与问题：死锁一定是系统资源不足的，那么系统资源不足是不是一定造成死锁呢2）联合推进路线非法（进程推进顺序不当）5.4.2产生死锁的起因和条件 A2B2C2D2申请r1申请r2释放r2释放r1A1B1C1D1申请r1申请r2释放r1释放r2两进程均占用r1两进程均占用r2xyP2进展P1进展0A死锁点5.4.2产生死锁的起因和条件路线1路线2ttt2t1 死锁产生的条件1971年Coffman总结出了对于可再使用资源，系统产生死锁必定同时保持四个必要条件：互斥条件（mutualexclusion）占有和等待条件（holdandwait）不剥夺条件（nopreemption）循环等待条件（circularwait） 死锁产生的条件互斥条件（mutualexclusion）：进程应互斥使用资源，任一时刻一个资源仅为一个进程独占，若另一个进程请求一个已被占用的资源时，它被置成等待状态，直到占用者释放资源。 死锁产生的条件2.占有和等待条件（holdandwait）（或称部分分配条件）：一个进程请求资源得不到满足而等待时，不释放已占有的资源。 死锁产生的条件不剥夺条件（nopreemption）：任一进程不能从另一进程那里抢夺资源，即已被占用的资源，只能由占用进程自己来释放。循环等待条件（circularwait）：存在一个循环等待链，其中，每一个进程分别等待它前一个进程所持有的资源，造成永远等待。 死锁产生的条件以上前三个条件互斥条件（mutualexclusion）占有和等待条件（holdandwait）不剥夺条件（nopreemption）是死锁存在的必要条件（necessarycondition），但不是充分条件。 死锁产生的条件第四个条件：循环等待条件（circularwait）是前三个条件同时存在时产生的结果，所以，这些条件并不完全独立。但单独考虑每个条件是有用的，只要能破坏这四个必要条件之一，死锁就可防止。 5.4.3解决死锁问题的策略---预防死锁一、解决死锁问题的几个策略为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一。条件1（互斥条件）：难以否定，但可采用相应的技术，如利用假脱机技术，即用可共享使用的设备模拟非共享的设备； 5.4.3解决死锁问题的策略---预防死锁条件2（占有和等待条件）：容易否定也容易实现，可制定相应的规则即可，例如，当一个进程（程序）申请某资源被拒绝，则必须释放已占用的资源，如需要再与其它所需资源一起申请。在资源分配策略上可以采取静态资源分配的方式一次性的把所需资源全部分配到位，否则就不分配。 5.4.3解决死锁问题的策略---预防死锁条件3（不剥夺条件）：也是很容易否定的，只要分配策略上规定一个进程（或程序）一次将所需资源一次申请到位。用完后释放。可以全部用完后，统一释放，也可使用完后立即释放，只要是一次申请到的，系统就不会出现死锁。 5.4.3解决死锁问题的策略---预防死锁条件4（循环等待条件）：通过有序资源分配法，可以破坏环路条件。实际上系统还可以不采用部分分配，也就破坏了环路等待条件。 死锁的解决策略归纳起来，可以采用以下策略之一来解决死锁问题：忽略该问题采用静态资源分配来预防死锁采用有控分配方法来避免死锁当死锁发生时检测死锁，并设法修复 鸵鸟算法象鸵鸟一样对死锁视而不见是最简单的方法.每个人对该方法的看法都不相同.数学家认为要彻底防止死锁的产生,不论代价有多大;工程师们想要了解死锁发生的频率,系统因各种原因崩溃的频率,以及死锁的严重程度.UNIX潜在地受到了一些死锁的威协,但是这些死锁从来没有发生,甚至从来没有被检测到.处理死锁的UNIX办法是忽略它,由于大多数用户宁可在极偶然的情况下产生死锁,也不愿被限制只能创建一个进程,只能打开一个文件等等. 为了研究解决死锁的方法，可借助于有向图这一强有力的工具。图中有两种节点：方块和圆圈。圆圈代表进程，方块代表资源。从资源节点(方块)到进程节点(圆圈)的有向弧表示资源已经分配给进程；从进程到资源的有向弧表示进程当前正处于阻塞状态，等待资源变为可用。资源分配图 资源——进程有向图R2P1P2R1表示资源表示进程R2P1R1分配请求分配请求分配分配请求P25.4.2产生死锁的起因和条件 RASBTDUC(a)进程A分配了一个资源(b)进程B请求了一个资源(c)进程D和进程形成环路，已处于死锁状态资源分配图 5.4死锁的预防——静态分配策略所谓静态分配是指一个进程必须在执行前就申请它所要的全部资源，并且直到它所要的资源都得到满足后才开始执行。采用静态分配后，进程在执行中不再申请资源，因而，不会出现占有了某些资源再等待另一些资源的情况，即破坏了第二个条件（占有和等待条件）的出现。 5.4死锁的预防——静态分配策略静态分配策略实现简单，被许多操作系统采用。但这种策略严重地降低了资源利用率，其缺点也是明显的：一个用户（进程）在程序运行之前很难提出将要使用的全部设备；用户的作业必须等待，直到所有的资源满足时才能投入运行。实际上某些设备可能很晚的时候才使用 5.4死锁的预防——静态分配策略设备（资源）的浪费太大，有些资源在进程运行过程中可能只有很少的时间才用到，有的甚至不会用到。例如：一个分支语句，只有当程序出错的时候才将错误从打印机输出，但如果采用静态资源分配策略的话，也要把打印机分配给这个程序，所以这种分配策略对系统来说是很浪费的。 5.4死锁的预防——层次分配在层次分配策略下，资源被分成多个层次，一个进程得到某一层的一个资源后，它只能再申请在较高一层的资源；当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源。层次分配策略将阻止第四个条件（循环等待条件）的出现。 5.4死锁的预防——层次分配这种策略的一个变种是按序分配策略。把系统的所有资源排列成一个顺序，例如，系统若共有n个进程，共有m个资源，用ri表示第i个资源，于是这m个资源是：r1,r2……,rm规定如果进程不得在占用资源ri(1≤i≤m)后再申请rj(j