操作系统的资源管理.ppt

1、1,第5章 操作系统的资源管理,5.1 资源管理的机制和策略 5.1.1 资源管理任务 1、资源的静态分配和动态分配 静态分配: 在作业运行前，将所需的资源一次性的分配给它，在作业运行完毕后释放所获得的全部资源。 动态分配：在进程运行过程中根据情况动态地分配、使用和释放资源。,2,2、资源管理的任务 （1）资源数据结构的描述 （2）确定资源的分配策略 （3）执行资源分配 （4）存取控制和安全保护,3,5.1.2 虚拟资源 虚拟资源：用户使用的逻辑资源，是操作系统将物理资源改造后，呈现给用户的可供使用的资源。 目的：一是提高资源的利用率；二是为了方便用户的使用。,4,5.1.3 资源分配机制 1

2、、资源描述器 资源描述器：描述各类资源的最小分配单位的数据结构。 2、资源信息块 资源信息块：描述某类资源的请求者、可利用的资源以及该类资源分配程序的地址的数据结构。,5,5.1.4 资源分配策略 1、先请求先服务（FIFO） 先请求先服务是一种最简单的资源分配策略，可用于对进程或作业的调度，也可用于对外部设备、主存储区的分配。 2、优先调度 优先调度策略调度是一种比较灵活的调度策略。进程调度队列按进程的优先级由高到低的顺序排列。 3、针对设备特性的调度 （1）移臂调度 （2）旋转调度,6,5.2 死锁及其解决方法,5.2.1 死锁的定义 可重用资源(reusable resource):各个

3、进程可以轮流使用，如处理机、内存、I/0外设、文件等都是可重用资源，在使用可重用资源时可能出现的死锁（Deadlock）。通常是由于各进程巳拥有部分资源，同时请求其他进程已占有的资源，从而造成永远等待。 可消耗资源(consumable resource):是指可以动态生成和动态消耗的资源，一般不限制数量，如中断、信号量、消息、缓冲区等都是可消耗资源。由于可消耗资源的生成和消耗存在依赖关系，因此他们的使用也可能因为双方都等待对方生成资源而形成死锁。(如图5-1所示）,7,图 5-1 进程之间通信时的死锁,8,死锁的定义:死锁是一组并发进程,它们共享系统的某些资源,该组进程中每个进程都已经占有了

4、部分资源,但都在不释放自己占有资源的情况下要求获得被其它进程已经占有的资源,从而造成它们相互等待,永远不能继续推进的状态. 说明： 参与死锁的进程最少是两个（两个以上进程才会出现死锁）。 参与死锁的进程至少有两个已经占有资源。 参与死锁的所有进程都在等待事件。 参与死锁的进程是当前系统中所有进程的子集。,9,5.2.2 资源分配图,(2) 凡属于E中的一个边eE，都连接着P中的一个结点和R中的一个结点，e=pi, rj是资源请求边，由进程pi指向资源rj， 它表示进程pi请求一个单位的rj资源。e=rj, pi是资源分配边，由资源rj指向进程pi, 它表示把一个单位的资源rj分配给进程pi。,

5、该图是由一组结点V和一组边E所组成的： G=（V，E），具有以下形式的定义和限制： （1）V被分为两个互斥的子集，一组进程结点P=p1,p2,pn,一组资源结点 R=r1,r2,rn,10,5.2.3 产生死锁的原因,产生死锁的根本原因是: 资源不足，引起资源竞争 进程推进顺序不合理,11,5.2.4 死锁产生的必要条件,互斥条件：进程要求对所分配的资源进行排他性使用，即在一段时间内某资源仅为一个进程所占用。 不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放。 占有并等待：进程每次申请所需要的一部分资源，在等待新资源的同时，进程继续占有已

6、分配到的资源。 循环等待条件：存在进程资源的循环等待链，链中的每一个进程已获得资源，同时被链中的下一个进程所请求。,12,5.2.5 预防死锁 解决死锁问题的基本方法有：预防死锁、避免死锁、检测死锁和解除死锁。除此之外还有鸵鸟算法和综合措施。 预防死锁是指通过某种策略来限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。 就是在设计操作系统时，通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁，使系统能预先排除死锁的可能性。,13,1、条件1（互斥条件） 互斥条件是由于设备本身特性所决定的,不能简单的把其打破;只有通过改造设备特性实现.具体办法采用Spooli

7、ng技术,把独占设备改造成共享设备来实现.,5.2.6 解决死锁问题的策略,14,2、条件2（不可剥夺条件） 为了破坏不可剥夺条件，我们采用这样的策略，一个已拥有资源的进程，若它再提出新资源要求而不能立即得到满足时，它必须释放已经拥有的所有资源，以后需要时再重新申请。拥有资源的进程在运行过程中其资源可能被剥夺，从而破坏了不可剥夺条件。 该方法实现复杂，被剥夺资源的进程前期工作失效，重复申请和释放资源给系统增加了开销，系统要付出很大的代价。,15,3、条件3（占有并等待） 采用设备的静态预先分配办法,具体做法:作业调度程序在选择作业时,只选择那些系统能满足其运行时所需的全部资源的作业投入运行,并

8、且在作业运行前,将其所需的全部资源一次性地分配给该作业. 该方法的优点和缺点如下： 简单、安全、易于实现。 程序在运行之前很难提出将要使用的全部设备。 直到所有资源满足才能运行，实际上某些资源可能要到运行后期才会用到。 一个进程运行期间，对某些设备的使用时间很短，甚至不会用到。 作业的周转时间被加长,系统资源的使用率被降低,16,4、条件4（环路条件） 为了破坏环路等待条件，采用有序资源分配策略。 对申请资源的进程规定：同类资源需一次申请，在获得资源后，只能申请较高级号的资源，无权申请低级号资源和同类资源。对于低级号资源和同类资源申请，必须先释放所有高级号的资源，然后再申请，否则不予分配。 优

9、点：同前两法相比，其资源利用率和系统吞吐量有较明显的改善。 缺点：进程实际需要资源的顺序不一定与资源的编号一致，因此仍会造成资源浪费，系统增加新设备较困难。,17,5.2.7 避免死锁,死锁的避免是动态的预防措施,系统允许进程动态地申请资源,如果措施得当,可以使系统获得较为满意的系统性能. 具体的办法是:系统为进程分配资源之前,首先对系统的安全性进行计算,如果为进程分配了所需资源后,系统仍处于安全状态,那么就把资源分配给该进程,反之则不为该进程分配资源. 银行家算法:该问题是研究一个银行家如何将其总数一定的现金,安全的借给若干个顾客,使这些顾客既能满足对资金的要求又能完成其交易,也使银行家可以

10、收回自己的资金不至于破产.,18,一、系统的安全状态和不安全状态 安全状态:是指系统能按某种进程推进顺序(p1,p2,pn),来为每个进程分配其所需资源,直至最大需求,使每个进程都能顺利完成其任务.只要系统存在这样的安全序列,则系统处于安全状态. 二、安全状态的例子 假定系统有三个进程p1,p2和p3,共有12台磁带机,进程p1、p2、p3分别要求10台、4台和9台，设在T0时刻p1、p2、p3已分别获得5台、2台和2台，尚有3台空闲磁带机未分配出去，分配情况如下所示：,19,经分析，在T0时刻系统是安全的，因为存在一个安全序列 向不安全状态的转换 若在T0时刻以后，p3请求1台磁带机，若满足

11、其要求，则系统进入不安全状态。,20,银行家算法中的数据结构 可利用资源向量Available(R1,R2Rm)。它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。 最大需求矩阵Max。这是个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi，jk，表示进程Pi需要Rj类资源的最大数目为k。 分配矩阵Allocation。这是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每个进程的资源数。如果Allocationi，jk，表示进程Pi当前已分得Rj类

12、资源的数目为k。,三、银行家算法避免死锁,21,需求矩阵：Need。它是一个nm的矩阵，用以表示每一个进程尚需的各类资源数，如果Needi，jk，表示进程Pi还需要Rj类资源k个，方能完成其任务。 上述三个矩阵间存在下述关系： Needi，j=Maxi，j-Allocationi，j,22,银行家算法 设Requesti（r1,r2,rm)是进程Pi的请求向量。如果Requestijk，表示进程Pi只需要k个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： 如果Requesti=Needi，则执行步骤；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。 如果Reques

13、ti，=Availablei，则执行步骤；否则，表示系统中尚无足够的资源，Pi等待。 系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值： Availablej=Availablej-Requestij； Allocationi，j=Allocationi，j+Requestij； Needi，j=Needi，j-Requestij；,23,系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,24,安全性算法 系统所执行的安全性算法可描述如下： 设置两个工作

14、向量，工作向量Work。它含有m个元素，它表示系统可提供给进程继续运行所需要的各类资源数目，初值Work=Available。 完成标志工作向量Finish。它含有n个元素，它表示系统是否有足够的资源分配给进程，使之运行完成，当有足够资源分配给进程时，Finishi=true，初值Finishi=false。 从进程集合中找到一个能满足下述条件的进程： Finishi=false； Needi=Work； 如找到，执行步骤；否则，执行步骤。,25,当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，系统回收这些资源，故修改下面数据结构中的数值： Workj=Workj+Allo

15、cationi，j； Finishi=true； 转步骤。 如果所有进程的Finishi=true ，则表示存在这样一个安全序列，系统处于安全状态；否则，系统处于不安全状态。,26,银行家算法之例,如表5-4所示T0时刻的资源分配表，假定系统中有五个进程P0，P1，P2，P3，P4和三种类型的资源A，B，C，每一种资源的数量分别为10、5、7。,27,如表5-5所示，对T0时刻进行安全性检查，可以找到一个安全序列P1，P3，P4，P2，P0，系统是安全的。,28,P1发出请求Request(1，0，2)，执行银行家算法。 如表5-6所示，进行安全性检查，通过第一步和第二步检查，并找到一个安全序

16、列P1，P3，P4，P2，P0，系统是安全的，可以分配P1的请求。,29,30,P4发出请求Request(3，3，0)，执行银行家算法。 Available=(2，3，0)，不能通过第二步检查（RequestiAvailable），所以P4等待。 P0请求资源，Request（0，2，0），执行银行家算法。 进行安全性检查，通过第一步和第二步检查，如表5-7所示，Available2，1，0已不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配。,31,作业：某系统中有10台打印机，有三个进程P1，P2，P3分别需要8台，7台和4台。若P1，P2，P3已申请到4台，2台和2台。试

17、问：按银行家算法能安全分配吗？请说明分配过程。,32,我们可把处理机调度分成宏观调度、中程调度和微观调度三个层次。 1、作业调度（宏观调度、高级调度） 任务：按一定的原则对处于外存输入井中的后备作业进行选择，给选出的作业分配内存、设备等必须资源，并建立相应的进程。在作业运行完毕后进行相应的善后工作。 2、交换调度（中程调度） 任务：按给定的原则和策略，将处于外存交换区的就绪状态或外存等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。,5.3 处理机管理5.3.1处理机的多级调度,33,3、进程调度（微观调度、低级调度） 任务：按照某种策略和方法选取一个处于就绪状

18、态的进程占用处理机，并进行相应的上下文切换以建立与处理机进程相适应的执行环境。,34,具有三级调度的调度队列模型,35,5.1.1 宏观调度,宏观调度在多道批处理系统中对应作业调度，就是按照系统所规定的调度算法从系统已接纳的一批作业中选取一个子集，做好运行前的准备工作，使其进入内存并运行。现代操作系统中一般不配备作业调度。作业调度完成以下几方面的工作： 按某种调度算法从后备队列中选取一个子集。 为选中的作业子集分配所需的资源，如内存、外设等。 为选中的作业子集创建相关进程。 填写修改被选中的作业的JCB及有关表格。 作业完成时的善后工作。,36,5.3.2 微观调度,微观调度也称低级调度，微观

19、调度才是真正的处理机调度，在实际系统中对应线程调度、进程调度或任务调度。 微观调度要解决的问题 WHAT：按什么原则分配CPU，即调度算法。 WHEN：何时分配CPU，即调度的时机。 HOW：如何分配CPU，即调度过程，进程的上下文切换。,37,进程调度器,操作系统为了对进程进行有效的监控，需要维护一些与进程相关的数据结构，记录所有进程的运行状况，并在进程出让处理机或调度程序剥夺执行状态进程占用的处理机时，选择适当的进程分派处理机，完成上下文切换。我们把操作系统内核中与进程调度相关代码称为进程调度器(dispatcher)。 调度方式 非剥夺方式：也叫非抢占方式，调度程序一旦把处理机分配给某进

20、程或线程后便让它一直执行下去，直到进程或线程完成或等待某事件而阻塞时，才把处理机分配给另一个进程或线程。 剥夺方式：也叫抢占方式，当一个进程或线程正在执行时，系统可以基于某种原则，剥夺已分配给它的处理机，将处理机分配给其他进程或线程。常用的剥夺原则有优先权原则和时间片原则。,38,动态查找就绪队列中的进程（线程）优先数和内存资源情况，以便确定分配对象。 根据确定的算法和进程（线程）的状态及占有内存情况选择一个进程（线程），使其从就绪状态转为执行状态。 执行分配CPU操作。 （5）进程调度的时机 正在执行的进程执行完毕 执行中的进程调用阻塞原语阻塞自己 使用P操作因资源不足被阻塞或使用V操作激活

21、了等待资源的进程队列 执行中进程提出I/O请求后被阻塞 分时系统中时间片已经用完 在执行完系统调用返回用户进程时 高优先级的进程到达,（4）进程调度的功能,39,5.3.3 调度算法,选择调度方式和算法的若干准则 调度算法的确定基于一定因素，我们希望好的调度算法是，系统运行尽能多的任务，使CPU保持忙，使I/O保持忙，对所有任务公平合理，也要有轻重缓急，重要的任务优先处理。 衡量操作系统及计算机系统的重要指标如下： 周转时间短。 响应时间快。 截止时间的保证。 优先权准则。 系统吞吐量高 处理机利用率好 各类资源的平衡利用 -是面向用户的指标，-是面向系统的指标。采用何种调度方法，是衡量操作系

22、统及计算机系统的重要指标之一。指标的好与差，对系统的使用直接产生影响。,40,调度性能评价指标,CPU的利用率：CPU是一个重要且昂贵的资源，人们需要使CPU尽可能忙，并希望它的利用率越高越好。 吞吐量：吞吐量是指单位时间内所完成任务的数量。 周转时间：将一个作业提交给计算机系统后到该作业的结果返回给用户所需的时间. 周转时间Ti：Ti=Tci-Tpi (Tpi-进程提交时间，Tci-进程完成时间)。 周转时间是以下所有时间段之和，包括等待进入内存、在就绪队列中等待、阻塞队列中的等待时间、在CPU上执行等。等待时间包括等待进入内存、在就绪队列中等待、阻塞队列中的等待时间。 故Ti=Twi+Ts

23、i (Twi-进程等待时间，Tsi-进程执行时间)。,41,为了去除进程本身因素的影响，在讨论处理机调度时也使用平均周转时间T和平均带权周转时间W作为衡量指标。 平均周转时间T 利用平均周转时间可衡量不同调度算法对相同任务流的调度性能。 带权周转时间W：带权周转时间是用周转时间除以进程的执行时间，能够合理反映任务长短差别的指标。 Wi=Ti/Tsi=（Twi+Tsi）/Tsi 平均带权周转时间： 利用平均带权周转时间可比较某种调度算法对不相同任务流的调度性能。 响应时间：指从用户发出一个命令到计算机系统把相应的执行结果返回给用户所需要的时间. 截止时间：在实时系统中，还使用截止时间来衡量系统的

24、实时性能，截止时间可分为开始截止时间和完成截止时间。,42,5.3.2 调度算法,先来先服务调度算法(FCFS) 基本思想：按作业（进程或线程）到达时间先后顺序依次使用处理机。 先来先服务调度算法的例子见表5-1。 该算法适合于进程调度、线程调度、任务调度、作业调度和其他资源调度等。,43,先来先服务调度算法例子,44,最短作业(进程）优先调度算法(SJF),基本思想：按作业（进程或线程）估计运行时间长短来组织短作业或短进程投入运行。目的是为了提高系统的吞吐率。 缺点：对长作业不利、未考虑作业的紧迫性、很难实现。 最短作业优先调度算法的例子如表5-2所示。,45,最高响应比优先算法(HRRN)

25、,基本思想：它同时兼顾每个作业等待时间和运行时间两个方面的因素，挑选响应比最高的作业投入运行。 响应比R=(等待时间+要求运行时间)要求运行时间。 它是FCFS和SJF的一种折中，比较好的满足了短作业用户和长作业用户的要求。采用响应比高者优先调度算法例子如表5-3所示。,46,优先权算法(HPF),挑选优先级最高的作业（进程）投入运行。 优先级分为静态优先级和动态优先级两种： 一、静态优先权法 （1）、基本思想：是指在创建进程时确定进程优先权，并一直保持到进程结束，即“终生”不变。 （2）、静态优先级确定原则： 作业优先级的确定： 根据用户要求或用户身份确定作业的优先级 根据作业类型确定作业的

26、优先级 I/O型作业和CPU型作业，原则上，I/O型作业的优先级高于CPU型作业的优先级 根据作业需要资源的多少确定作业的优先级，原则上资源需要多的作业其优先级低于资源需要少的作业的优先级,47,进程优先级的确定 按进程的属性确定把进程分为系统进程和用户进程，系统进程的优先级应高于用户进程的优先级 按进程的类型可把进程分为I/O型进程和CPU型进程及I/O与CPU均衡的进程，一般情况下，I/O型进程的优先级高，I/O与CPU均衡型进程优先级次之，CPU型进程优先级最低。 其它方法 2、动态优先级 进程动态优先级确定原则： 根据进程占有CPU的时间长短来决定，进程占有CPU时间越长其优先级越低； 根据进程等待CPU时间长度来决定，进程在就绪队列中等待时间越长，其优先级越高；,48,时间片轮转法(RR),基本思想：把CPU的处理时间分成固定大小的时间片，如果一个进程在调度中被选中后，用完系统规定的时间片仍然未完成要求的任务，则让出处理机并把它排到就绪队列的末尾，等待下一次调度。同时进程调度进程又去调度当前就绪队列队首的第一个进程或作业投入运行。 时间片的选取将影响系统开销和响应时间： t过短，处理机剥夺次数太多，进程上下文切换次数增加，导致系统开销增大； t过长，易使就绪进程在一个时间片内完成，调度蜕化为先来先服务； t值的确定：近似