操作系统原理第五章-资源分配与调度

5.1资源管理概述1.资源管理的目的和任务资源的静态支配和动态支配资源的静态支配系统对作业一级接受资源静态支配方法。系统在调度作业时，依据作业所需资源进行支配；并在作业运行完毕时，收回所支配的全部资源。称为资源的静态支配。资源的动态支配系统对进程一级接受资源动态支配方法。系统在进程运行中，依据进程提出的资源需求，进行资源的动态支配和回收。称为资源的动态支配。15.1资源管理概述资源管理的目的目的：为用户供应一种简洁而有效地运用资源的方法，充分发挥各资源的作用。应达到的目标：保证资源的高利用率；在“合理”时间内使全部顾客有获得所需资源的机会；对不行共享的资源实施互斥运用；防止由资源支配不当而引起死锁。25.1资源管理概述资源管理的任务任务：解决资源支配问题，防止死锁；解决对资源的存取、运用方法问题资源管理的功能资源数据结构的描述确定资源的支配原则和调度原则执行资源支配存取限制和平安疼惜35.1资源管理概述2.资源的分类方法物理资源和程序资源(处理器、外设等；消息或文件等)单一访问入口资源（不行重入，只能为一个进程运用）和多访问入口资源（可以为多个进程共享运用）等同资源（多个完全相同的设备）虚拟资源（cpu、确定容量的主存、数量有限的外设），如虚拟存储器3.资源管理的机构和策略机构：进行资源支配的必需的基本设施和部件，它包括描述资源状态的数据结构、保证资源互斥的同步机构及资源恳求排队的手段。策略：这些机构所运用的方法，资源支配的原则45.2资源支配机制1.资源描述器什么是资源描述器描述各类资源的最小支配单位的数据结构称为资源描述器RD(resourcedescriptor)。如：主存最小支配单位：在分区支配中——主存分区磁盘最小支配单位：磁盘面中的一个扇区描述器的组织方式取决于资源支配单位的数量和这一数量是固定不变的、还是可以变更的这一特征。5资源描述器的内容资源名 资源类型 最小支配单位的大小 最小支配单位的地址 支配标记 描述器链接信息 存取权限 密级 最终一次存取时间 记账信息 20KB

0

os

作业1

作业3

作业4

52KB66KB130KB230KB256KB1主存5.2资源支配机制62.资源信息块什么是资源信息块（rib）描述某类资源的恳求者、可用资源和该类资源支配程序等必要信息的数据结构。对于每一类可利用的资源，可将其组织成可利用资源队列。在资源信息块中有指向这两个队列的队列指针，另外还有一项为该类资源支配程序的入口地址。资源支配程序是接收支配叮嘱把资源支配给恳求者的例程。资源支配程序包括：支配程序和回收程序。5.2资源支配机制7等待队列头指针可利用资源队列头指针资源分配程序入口地址┅pcb1pcb2pcbkrd1rd2rdn资源分配程序┅5.2资源支配机制资源信息块的内容85.3资源支配策略资源支配的方式取决于设计者所选择的目标，以及与应用每一类资源相联系的特定限制。目的是使吞吐率尽可能地高，响应时间尽可能地短，即既要充分地利用系统各种资源，又要尽可能地满足用户要求。一个资源进行支配的问题，在一般状况下，是由这样两个方面组成的：管理恳求的排队站（支配策略）与在等同资源间选择资源。支配程序可以用不同的策略选择进程恳求；依据恳求来到的次序进行查看；将进程恳求者的优先权结合到每一个恳求中；满足能更合理地应用这一资源的那个恳求。91.常用的资源支配策略(1)先恳求先服务(FIFO(FirstInFirstOut)策略)排序原则：按恳求的先后次序排序。每一个新产生的恳求均排在队尾，而当资源可用时，资源支配程序则从队列中选取第一个恳求，并满足其须要。这种策略可用于对进程或作业的调度，或外设、主存支配

┅表头按请求的先后次序先后按自然顺序排列的队列5.3资源支配策略10(2)优先调度在优先调度策略下，对于每一个进程要指定一个优先级，优先级反映了进程要求处理的紧迫程度。排序原则：按优先级的凹凸排序。每一个新产生的恳求，按其优先级的凹凸插到相应的位置上。而当资源可用时，选取队列中第一个恳求，并满足其须要。

┅表头按优先级的高低排序高低按优先级高低排列的就绪队列5.3资源支配策略11一.死锁的概念1.死锁的例子（1）同类资源的死锁（2）非同类资源的死锁进程p1、p2共享一台打印机和一台光标记阅读机时刻t1，进程p1——占用打印机进程p2——占用光标记阅读机。时刻t2，进程p1——又恳求光标记阅读机进程p2——又恳求打印机5.3死锁125.3死锁(2)用信号灯的P、V操作描述死锁设进程A与进程B共享一台打印机(R1)和一台光标记阅读机(R2)。用信号灯的P、V操作表示资源的申请和释放。信号灯设置——s1：表示R1可用，初值为1。s2：表示R2可用，初值为1。探讨两种资源恳求序列，哪种状况可能产生相互死等的局面。13

进程A进程BA进程进程B

┆┆┆┆p(s1)；p(s2)；p(s1)p(s2)；占用R1占用R2占用R1占用R2v(s1)；v(s2)；p(s2)；p(s1)；

┆┆又占用R2又占用R1p(s2)；p(s1)；┆┆占用R2占用R1v(s1)v(s2)；v(s2)；v(s1)；┆┆

┆┆v(s2)；v(s1)；

┆┆

┆┆5.3死锁142.什么是死锁在两个或多个并发进程中，假如每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推动，称这一组进程产生了死锁。死锁是两个或多个进程被无限期地堵塞、相互等待的一种状态。二.死锁的起因和条件1.引起死锁的缘由系统资源不足；进程推动依次非法。5.3死锁152.死锁图解

A1：p1request(r1)A2：p2request(r2)B1：p1request(r2)B2：p2request(r1)C1：p1release(r1)C2：p2release(r2)D1：p1release(r2)D2：p2release(r1)N0A1B1C1D1A2B2C2D2P1进程P2进程•5.3死锁163.产生死锁的必要条件(1)互斥条件涉及的资源是非共享的，即为临界资源。(2)不剥夺条件（非抢夺）进程所获得的资源在未运用完毕之前，不能被其他进程强行夺走。(3)占用并等待（部分支配）进程每次申请它所须要的一部分资源。在等待一新资源的同时，进程接着占用已支配到的资源。(4)环路条件（循环等待）存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中下一个进程所恳求。5.3死锁17三.解决死锁问题的策略破坏产生死锁的四个必要条件之一互斥条件、不剥夺条件、占用并等待、循环等待解决死锁的策略接受静态资源支配方法——预防死锁接受资源动态支配、有控支配方法——动态避开死锁当死锁发生时检测出死锁，并设法修复；忽视死锁，认为死锁不会发生。（大多数操作系统接受）5.3死锁18四.死锁的预防预防死锁的方法分为静态预防和动态避开。静态预防死锁的方法其方法是预先支配全部共享的资源。（批处理）缺点：①一个用户在作业运行之前可能提不出他的作业将要运用的全部设备。②用户作业必需等待，直到全部资源满足时才能投入运行。事实上某些资源可能要到运行后期才会用到。③一个作业运行期间，对某些设备的运用时间很少，甚至不会用到。5.3死锁195.3死锁五、死锁的避开（动态预防死锁的方法）预防死锁和避开死锁的区分：前者所接受的支配策略本身就否定了必要条件之一，这样来保证死锁不行能发生；而后者是在动态支配资源的策略下接受某种算法来预防可能发生的死锁，从而拒绝可能引起死锁的某个资源恳求。(1)有序资源支配法系统中全部资源都给定一个唯一的编号，全部支配恳求必需以上升的次序进行。当遵守上升次序的规则时，若资源可用，支配程序则予以支配；否则，恳求者等待。（线性方式破坏了死锁的环路条件）缺点：进程实际须要资源的依次不确定与资源的编号相一样，因而照旧会造成资源的奢侈。对资源进行合理的排序，这种方法是有确定好用价值的。205.3死锁(2)银行家算法避开死锁的方法是否有效与接受的算法有很大的关系。它能在死锁发生前察觉它们的存在，代表算法是DijkstraEW于1968年提出的银行家算法（可用于银行系统）。申请者事先说明对各类资源的最大需求量。在进程活动期间动态申请某类资源时，由系统审查系统现有该类资源的数目是否能满足当前进程的最大需求量，如能满足就予以支配，否则进程等待。按银行算法来支配资源是不会产生死锁的。因为，按该算支配资源时，每次支配后总存在着一个进程，假如让它单独进行下去，必定可以获得它所需的全部资源。这种算法的主要问题是，要求每个进程必需先知道资源的最大需求量，过于谨慎及所花费的开销较大是运用银行算法的主要障碍。215.3死锁例：系统拥有某类资源10个。现有进程P、Q、R共享该类资源。它们申请该类资源的最大需求量如下，当这些进程动态申请资源