操作系统的资源管理.pptx

1第5章 操作系统的资源管理5.1 5.1 资源管理的机制和策略资源管理的机制和策略5.1.1 5.1.1 资源管理任务资源管理任务1 1、资源的静态分配和动态分配、资源的静态分配和动态分配静态分配静态分配:在作业运行前，将所需的资源一次性的分配给它，在作业运行完毕后释放所获得的全部资源。动态分配：动态分配：在进程运行过程中根据情况动态地分配、使用和释放资源。22 2、资源管理的任务、资源管理的任务（1 1）资源数据结构的描述）资源数据结构的描述（2 2）确定资源的分配策略）确定资源的分配策略（3 3）执行资源分配）执行资源分配（4 4）存取控制和安全保护）存取控制和安全保护35.1.2 5.1.2 虚拟资源虚拟资源虚拟资源：虚拟资源：用户使用的逻辑资源，是操作系统将物理资源改造后，呈现给用户的可供使用的资源。目的：目的：一是提高资源的利用率；二是为了方便用户的使用。45.1.3 5.1.3 资源分配机制资源分配机制1 1、资源描述器、资源描述器资源描述器：资源描述器：描述各类资源的最小分配单位的数据结构。2 2、资源信息块、资源信息块资源信息块：资源信息块：描述某类资源的请求者、可利用的资源以及该类资源分配程序的地址的数据结构。55.1.4 5.1.4 资源分配策略资源分配策略1 1、先请求先服务（、先请求先服务（FIFOFIFO）先请求先服务是一种最简单的资源分配策略，可用于对进程或作业的调度，也可用于对外部设备、主存储区的分配。2 2、优先调度、优先调度 优先调度策略调度是一种比较灵活的调度策略。进程调度队列按进程的优先级由高到低的顺序排列。3 3、针对设备特性的调度、针对设备特性的调度（1）移臂调度（2）旋转调度65.2 死锁及其解决方法5.2.1 死锁的定义n可重用资源可重用资源(reusable resource)(reusable resource):各个进程可以轮流使用，如处理机、内存、I/0外设、文件等都是可重用资源，在使用可重用资源时可能出现的死锁（Deadlock）。通常是由于各进程巳拥有部分资源，同时请求其他进程已占有的资源，从而造成永远等待。n可消耗资源可消耗资源(consumable resource)(consumable resource):是指可以动态生成和动态消耗的资源，一般不限制数量，如中断、信号量、消息、缓冲区等都是可消耗资源。由于可消耗资源的生成和消耗存在依赖关系，因此他们的使用也可能因为双方都等待对方生成资源而形成死锁。(如图5-1所示）7图 5-1 进程之间通信时的死锁 8n死锁的定义死锁的定义:死锁是一组并发进程,它们共享系统的某些资源,该组进程中每个进程都已经占有了部分资源,但都在不释放自己占有资源的情况下要求获得被其它进程已经占有的资源,从而造成它们相互等待,永远不能继续推进的状态.n说明：说明：n参与死锁的进程最少是两个（两个以上进程才会出现死锁）。n参与死锁的进程至少有两个已经占有资源。n参与死锁的所有进程都在等待事件。n参与死锁的进程是当前系统中所有进程的子集。95.2.2 资源分配图(2)凡属于E中的一个边eE，都连接着P中的一个结点和R中的一个结点，e=pi,rj是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。e=rj,pi是资源分配边，由资源rj指向进程pi,它表示把一个单位的资源rj分配给进程pi。该图是由一组结点V和一组边E所组成的：G=（V，E），具有以下形式的定义和限制：（1）V被分为两个互斥的子集，一组进程结点P=p1,p2,pn,一组资源结点R=r1,r2,rn,105.2.3 产生死锁的原因 产生死锁的根本原因是:n资源不足，引起资源竞争n进程推进顺序不合理115.2.4 死锁产生的必要条件n互斥条件：互斥条件：进程要求对所分配的资源进行排他性使用，即在一段时间内某资源仅为一个进程所占用。n不剥夺条件：不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放。n占有并等待：占有并等待：进程每次申请所需要的一部分资源，在等待新资源的同时，进程继续占有已分配到的资源。n循环等待条件：循环等待条件：存在进程资源的循环等待链，链中的每一个进程已获得资源，同时被链中的下一个进程所请求。125.2.5 预防死锁n解决死锁问题的基本方法有：预防死锁、避免死锁、检测死锁和解除死锁。除此之外还有鸵鸟算法和综合措施。n预防死锁预防死锁是指通过某种策略来限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。n就是在设计操作系统时，通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁，使系统能预先排除死锁的可能性。131、条件、条件1（互斥条件）（互斥条件）n互斥条件是由于设备本身特性所决定的,不能简单的把其打破;只有通过改造设备特性实现.具体办法采用Spooling技术,把独占设备改造成共享设备来实现.5.2.6 解决死锁问题的策略142、条件、条件2（不可剥夺条件）（不可剥夺条件）n为了破坏不可剥夺条件，我们采用这样的策略，一个已拥有资源的进程，若它再提出新资源要求而不能立即得到满足时，它必须释放已经拥有的所有资源，以后需要时再重新申请。拥有资源的进程在运行过程中其资源可能被剥夺，从而破坏了不可剥夺条件。n该方法实现复杂，被剥夺资源的进程前期工作失效，重复申请和释放资源给系统增加了开销，系统要付出很大的代价。153 3、条件、条件3 3（占有并等待）（占有并等待）n采用设备的静态预先分配办法,具体做法:作业调度程序在选择作业时,只选择那些系统能满足其运行时所需的全部资源的作业投入运行,并且在作业运行前,将其所需的全部资源一次性地分配给该作业.n该方法的优点和缺点如下：n简单、安全、易于实现。n程序在运行之前很难提出将要使用的全部设备。n直到所有资源满足才能运行，实际上某些资源可能要到运行后期才会用到。n一个进程运行期间，对某些设备的使用时间很短，甚至不会用到。n作业的周转时间被加长,系统资源的使用率被降低164、条件、条件4（环路条件）（环路条件）n为了破坏环路等待条件，采用有序资源分配策略。n对申请资源的进程规定：同类资源需一次申请，在获得资源后，只能申请较高级号的资源，无权申请低级号资源和同类资源。对于低级号资源和同类资源申请，必须先释放所有高级号的资源，然后再申请，否则不予分配。n优点：同前两法相比，其资源利用率和系统吞吐量有较明显的改善。n缺点：进程实际需要资源的顺序不一定与资源的编号一致，因此仍会造成资源浪费，系统增加新设备较困难。175.2.7 避免死锁n死锁的避免是动态的预防措施,系统允许进程动态地申请资源,如果措施得当,可以使系统获得较为满意的系统性能.n具体的办法是具体的办法是:系统为进程分配资源之前,首先对系统的安全性进行计算,如果为进程分配了所需资源后,系统仍处于安全状态,那么就把资源分配给该进程,反之则不为该进程分配资源.n银行家算法银行家算法:该问题是研究一个银行家如何将其总数一定的现金,安全的借给若干个顾客,使这些顾客既能满足对资金的要求又能完成其交易,也使银行家可以收回自己的资金不至于破产.18一、系统的安全状态和不安全状态一、系统的安全状态和不安全状态 n安全状态安全状态:是指系统能按某种进程推进顺序(p1,p2,pn),来为每个进程分配其所需资源,直至最大需求,使每个进程都能顺利完成其任务.只要系统存在这样的安全序列,则系统处于安全状态.二、安全状态的例子二、安全状态的例子 n假定系统有三个进程p1,p2和p3,共有12台磁带机,进程p1、p2、p3分别要求10台、4台和9台，设在T0时刻p1、p2、p3已分别获得5台、2台和2台，尚有3台空闲磁带机未分配出去，分配情况如下所示：19进程最大需求已分配可用磁带机P11053P242P392n经分析，在T0时刻系统是安全的，因为存在一个安全序列n向不安全状态的转换n若在T0时刻以后，p3请求1台磁带机，若满足其要求，则系统进入不安全状态。20n银行家算法中的数据结构银行家算法中的数据结构n可利用资源向量Available(R1,R2Rm)。它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。n最大需求矩阵Max。这是个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi，jk，表示进程Pi需要Rj类资源的最大数目为k。n分配矩阵Allocation。这是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每个进程的资源数。如果Allocationi，jk，表示进程Pi当前已分得Rj类资源的数目为k。三、银行家算法避免死锁21n需求矩阵：Need。它是一个nm的矩阵，用以表示每一个进程尚需的各类资源数，如果Needi，jk，表示进程Pi还需要Rj类资源k个，方能完成其任务。n上述三个矩阵间存在下述关系：nNeedi，j=Maxi，j-Allocationi，j22n银行家算法银行家算法n设Requesti（r1,r2,rm)是进程Pi的请求向量。如果Requestijk，表示进程Pi只需要k个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：n如果Requesti=Needi，则执行步骤；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。n如果Requesti，=Availablei，则执行步骤；否则，表示系统中尚无足够的资源，Pi等待。n系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值：nAvailablej=Availablej-Requestij；nAllocationi，j=Allocationi，j+Requestij；nNeedi，j=Needi，j-Requestij；23n系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。24n安全性算法安全性算法n系统所执行的安全性算法可描述如下：n设置两个工作向量，工作向量Work。它含有m个元素，它表示系统可提供给进程继续运行所需要的各类资源数目，初值Work=Available。n完成标志工作向量Finish。它含有n个元素，它表示系统是否有足够的资源分配给进程，使之运行完成，当有足够资源分配给进程时，Finishi=true，初值Finishi=false。n从进程集合中找到一个能满足下述条件的进程：nFinishi=false；nNeedi=Work；n如找到，执行步骤；否则，执行步骤。25当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，系统回收这些资源，故修改下面数据结构中的数值：nWorkj=Workj+Allocationi，j；nFinishi=true；n转步骤。n如果所有进程的Finishi=true，则表示存在这样一个安全序列，系统处于安全状态；否则，系统处于不安全状态。26银行家算法之例n如表5-4所示T0时刻的资源分配表，假定系统中有五个进程P0，P1，P2，P3，P4和三种类型的资源A，B，C，每一种资源的数量分别为10、5、7。27如表5-5所示，对T0时刻进行安全性检查，可以找到一个安全序列P1，P3，P4，P2，P0，系统是安全的。28nP1发出请求Request(1，0，2)，执行银行家算法。n如表5-6所示，进行安全性检查，通过第一步和第二步检查，并找到一个安全序列P1，P3，P4，P2，P0，系统是安全的，可以分配P1的请求。2930nP4发出请求Request(3，3，0)，执行银行家算法。nAvailable=(2，3，0)，不能通过第二步检查（RequestiAvailable），所以P4等待。nP0请求资源，Request（0，2，0），执行银行家算法。n进行安全性检查，通过第一步和第二步检查，如表5-7所示，Available2，1，0已不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配。31作业：作业：某系统中有10台打印机，有三个进程P1，P2，P3分别需要8台，7台和4台。若P1，P2，P3已申请到4台，2台和2台。试问：按银行家算法能安全分配吗？请说明分配过程。32n我们可把处理机调度分成宏观调度、中程调度和微观调度三个层次。1、作业调度（宏观调度、高级调度）任务：任务：按一定的原则对处于外存输入井中的后备作业进行选择，给选出的作业分配内存、设备等必须资源，并建立相应的进程。在作业运行完毕后进行相应的善后工作。2、交换调度（中程调度）任务：任务：按给定的原则和策略，将处于外存交换区的就绪状态或外存等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。5.3 处理机管理5.3.1处理机的多级调度333、进程调度（微观调度、低级调度）任务：任务：按照某种策略和方法选取一个处于就绪状态的进程占用处理机，并进行相应的上下文切换以建立与处理机进程相适应的执行环境。34具有三级调度的调度队列模型355.1.1 宏观调度n宏观调度在多道批处理系统中对应作业调度，就是按照系统所规定的调度算法从系统已接纳的一批作业中选取一个子集，做好运行前的准备工作，使其进入内存并运行。现代操作系统中一般不配备作业调度。作业调度完成以下几方面的工作：n按某种调度算法从后备队列中选取一个子集。n为选中的作业子集分配所需的资源，如内存、外设等。n为选中的作业子集创建相关进程。n填写修改被选中的作业的JCB及有关表格。n作业完成时的善后工作。365.3.2 微观调度n微观调度也称低级调度，微观调度才是真正的处理机调度，在实际系统中对应线程调度、进程调度或任务调度。微观调度要解决的问题微观调度要解决的问题nWHAT：按什么原则分配CPU，即调度算法。nWHEN：何时分配CPU，即调度的时机。nHOW：如何分配CPU，即调度过程，进程的上下文切换。37进程调度器进程调度器 n操作系统为了对进程进行有效的监控，需要维护一些与进程相关的数据结构，记录所有进程的运行状况，并在进程出让处理机或调度程序剥夺执行状态进程占用的处理机时，选择适当的进程分派处理机，完成上下文切换。我们把操作系统内核中与进程调度相关代码称为进程调度器(dispatcher)。调度方式调度方式n非剥夺方式：非剥夺方式：也叫非抢占方式，调度程序一旦把处理机分配给某进程或线程后便让它一直执行下去，直到进程或线程完成或等待某事件而阻塞时，才把处理机分配给另一个进程或线程。n剥夺方式：剥夺方式：也叫抢占方式，当一个进程或线程正在执行时，系统可以基于某种原则，剥夺已分配给它的处理机，将处理机分配给其他进程或线程。常用的剥夺原则有优先权原则和时间片原则。38n动态查找就绪队列中的进程（线程）优先数和内存资源情况，以便确定分配对象。n根据确定的算法和进程（线程）的状态及占有内存情况选择一个进程（线程），使其从就绪状态转为执行状态。n执行分配CPU操作。（5）进程调度的时机）进程调度的时机n正在执行的进程执行完毕n执行中的进程调用阻塞原语阻塞自己n使用P操作因资源不足被阻塞或使用V操作激活了等待资源的进程队列n执行中进程提出I/O请求后被阻塞n分时系统中时间片已经用完n在执行完系统调用返回用户进程时n高优先级的进程到达（4）进程调度的功能）进程调度的功能395.3.3 调度算法n选择调度方式和算法的若干准则选择调度方式和算法的若干准则n调度算法的确定基于一定因素，我们希望好的调度算法是，系统运行尽能多的任务，使CPU保持忙，使I/O保持忙，对所有任务公平合理，也要有轻重缓急，重要的任务优先处理。n衡量操作系统及计算机系统的重要指标如下：n周转时间短。n响应时间快。n截止时间的保证。n优先权准则。n系统吞吐量高n处理机利用率好n各类资源的平衡利用n-是面向用户的指标，-是面向系统的指标。采用何种调度方法，是衡量操作系统及计算机系统的重要指标之一。指标的好与差，对系统的使用直接产生影响。40调度性能评价指标调度性能评价指标nCPU的利用率：CPU是一个重要且昂贵的资源，人们需要使CPU尽可能忙，并希望它的利用率越高越好。n吞吐量：吞吐量是指单位时间内所完成任务的数量。n周转时间：将一个作业提交给计算机系统后到该作业的结果返回给用户所需的时间.n周转时间Ti：Ti=Tci-Tpi(Tpi-进程提交时间，Tci-进程完成时间)。n周转时间是以下所有时间段之和，包括等待进入内存、在就绪队列中等待、阻塞队列中的等待时间、在CPU上执行等。等待时间包括等待进入内存、在就绪队列中等待、阻塞队列中的等待时间。n故Ti=Twi+Tsi(Twi-进程等待时间，Tsi-进程执行时间)。41 为了去除进程本身因素的影响，在讨论处理机调度时也使用平均周转时间T和平均带权周转时间W作为衡量指标。n平均周转时间Tn利用平均周转时间可衡量不同调度算法对相同任务流的调度性能。n带权周转时间W：带权周转时间是用周转时间除以进程的执行时间，能够合理反映任务长短差别的指标。nWi=Ti/Tsi=（Twi+Tsi）/Tsin平均带权周转时间：n利用平均带权周转时间可比较某种调度算法对不相同任务流的调度性能。n响应时间：指从用户发出一个命令到计算机系统把相应的执行结果返回给用户所需要的时间.n截止时间：在实时系统中，还使用截止时间来衡量系统的实时性能，截止时间可分为开始截止时间和完成截止时间。425.3.2 调度算法n先来先服务调度算法(FCFS)n基本思想：基本思想：按作业（进程或线程）到达时间先后顺序依次使用处理机。n先来先服务调度算法的例子见表5-1。n该算法适合于进程调度、线程调度、任务调度、作业调度和其他资源调度等。43先来先服务调度算法例子先来先服务调度算法例子 44最短作业(进程）优先调度算法(SJF)n基本思想：基本思想：按作业（进程或线程）估计运行时间长短来组织短作业或短进程投入运行。目的是为了提高系统的吞吐率。n缺点：缺点：对长作业不利、未考虑作业的紧迫性、很难实现。n最短作业优先调度算法的例子如表5-2所示。45最高响应比优先算法(HRRN)n基本思想：基本思想：它同时兼顾每个作业等待时间和运行时间两个方面的因素，挑选响应比最高的作业投入运行。n响应比R=(等待时间+要求运行时间)要求运行时间。n它是FCFS和SJF的一种折中，比较好的满足了短作业用户和长作业用户的要求。采用响应比高者优先调度算法例子如表5-3所示。46优先权算法(HPF)n挑选优先级最高的作业（进程）投入运行。n优先级分为静态优先级和动态优先级两种：一、静态优先权法一、静态优先权法（1）、基本思想：是指在创建进程时确定进程优先权，并一直保持到进程结束，即“终生”不变。（2）、静态优先级确定原则：n作业优先级的确定：根据用户要求或用户身份确定作业的优先级根据作业类型确定作业的优先级I/O型作业和CPU型作业，原则上，I/O型作业的优先级高于CPU型作业的优先级根据作业需要资源的多少确定作业的优先级，原则上资源需要多的作业其优先级低于资源需要少的作业的优先级47n进程优先级的确定进程优先级的确定按进程的属性确定把进程分为系统进程和用户进程，系统进程的优先级应高于用户进程的优先级按进程的类型可把进程分为I/O型进程和CPU型进程及I/O与CPU均衡的进程，一般情况下，I/O型进程的优先级高，I/O与CPU均衡型进程优先级次之，CPU型进程优先级最低。其它方法2 2、动态优先级、动态优先级进程动态优先级确定原则：根据进程占有CPU的时间长短来决定，进程占有CPU时间越长其优先级越低；根据进程等待CPU时间长度来决定，进程在就绪队列中等待时间越长，其优先级越高；48时间片轮转法(RR)n基本思想：基本思想：把CPU的处理时间分成固定大小的时间片，如果一个进程在调度中被选中后，用完系统规定的时间片仍然未完成要求的任务，则让出处理机并把它排到就绪队列的末尾，等待下一次调度。同时进程调度进程又去调度当前就绪队列队首的第一个进程或作业投入运行。n时间片的选取将影响系统开销和响应时间：nt过短，处理机剥夺次数太多，进程上下文切换次数增加，导致系统开销增大；nt过长，易使就绪进程在一个时间片内完成，调度蜕化为先来先服务；nt值的确定：近似为：t=R/Nmax,其中Nmax为就绪队列所允许的最大进程数，R为响应时间。49多级队列算法(MLQ)n多级队列算法是先来先服务算法、时间片轮转算法和优先权算法的综合。其基本思想是将就绪队列分成多个独立队列，相同优先权的进程按FIFO原则排成一个队列，按时间片轮转算法分派CPU。不同队列可有不同的优先权、不同的时间片长度。在多级队列算法中，优先调度优先权高的队列，当优先权高的队列为空时，才可以调度下一级队列，依次类推，同一队列按时间片轮转算法分派CPU。n此算法的性能好，适合于线程调度、进程调度或任务调度。且比较容易实现，实用性好，被目前流行的操作系统采用，如NT、UNIX等。50 多级反馈队列算法是先来先服务算法、时间片轮转算法和优先权算法的综合和发展。该算法可以动态调整进程优先权和时间片大小。多级反馈队列调度法实现的基本思想和方法如下：n（1）系统中有多个就绪队列，每个队列对应一个调度级别，各级有不同的优先级别。第一队列优先级最高，以下各级队列优先级逐次减低；n(2)各级队列中的进程具有不同的时间片.优先级最高队列中进程时间片最小,随着队列级别增加其进程的时间片增加;n(3)各级队列均FCFS服务原则排序;多级反馈队列法(MFQ)51n(4)同一队列中进程调度方法:新进入的进程加入到第一级就绪队列的末尾.每级队列中的进程按FCFS方法分给处理机,并运行一个相应于该队列的时间片.如果该进程在这个时间片中完成了全部工作或因等待时间或等待I/O操作而放弃处理机,则该进程撤离系统(完成任务)或进入相应的阻塞队列,从而离开就绪队列.若进程使用完时间片后仍然要求运行(也没有I/O请求),则该进程被抢占处理机,同时将它放入下一级(优先级降低)就绪队列的末尾;n(5)不同队列调度方法:只有高优先级队列为空才调度下一级就绪队列;最低优先级队列采用时间片轮转法调度;n(6)当比运行进程更高级别的队列中到来一新进程时,它将抢占运行进程的处理机.被抢占的进程回到原队列的末尾.n该算法对终端用户、短作业和长作业都能获得较好的响应.5253作业：作业：P132 5-10题