操作系统第5章-第9章(华中科技大学版).ppt

1,5.1 资源管理概述,OS的资源：包括各种硬件资源和软件资源。根据对资源的使用方式，可将资源分为：共享资源。如：CPU、内存空间、磁头、可重入的程序等使用方式：只让用，不让占,独占资源。如：打印机、卡片输入机 互斥的变量、队列、表格、文件等会修改的数据使用方式：只要不释放，系统不能强行收回,2,一、资源管理的一般功能 1、构造描述资源的数据结构 操作系统通过这些数据结构而 感知到资源的存在，并对资源进行管理,这些数据结构，应包含描述资源的：物理名(内部标识)、逻辑名(用户定义的名称)分配状态 类型、地址、等所有信息,3,3.实施资源的分配(及回收)根据分配原则，将资源分配给请求的用户 并完成相应操作。如:CPU：恢复现场 内存：将程序调入内存、改内存分配标志 独占资源：上锁,2.制定资源的分配原则 决定资源应先分给谁(当有多个进程请求时)何时分配，分配多少等问题,当资源使用完毕后，收回资源,4,4.存取控制和安全保护 对资源的存取进行控制 并对资源实施安全保护措施(如：内存、文件的保护),5.其他的特殊功能,5,三.资源的分配方式(接受者)1.静态分配(接受者是作业)系统在调度一个作业运行时：根据作业的需求进行资源的分配 在作业运行完毕后，才收回所分配的全部资源,2.动态分配(接受者是进程)在进程的运行过程中，根据进程提出的请求 进行资源的分配 资源使用完毕(共享)、或被进程释放(独占)后 回收该资源,6,四.资源的分类 为了简化系统的设计，对不同的资源，可采用不同的方式进行分类。常用的分类方式有：,1.硬件资源和软件资源 硬件：如处理机、主存、外部设备 软件：如文件、消息、数据结构,2.同类资源 如：打印机类、显示器类、内存区域等,.虚拟资源和实际资源,虚拟资源和实际资源,实际资源,虚拟资源,目的：提高独占资源的利用率,5.3 资源分配的策略,资源的分配策略 指获得资源的先后次序,通常的实现方法是：将资源的请求者按某种原则 形成一个具有先后次序的请求队列,当资源可用时，按队列的次序分配资源,9,1.先请求先服务(FIFO First In First Out)排序原则：按请求的先后排序。即：新产生的请求均排在队尾，分配时在队首,表头,适用范围：系统中的一切资源优点：简单、次序不会改变，因此系统开销小 缺点：有时显得不合理、系统无法进行干预,10,2.优先调度 系统对每个进程(或作业)，都指定一个优先级 以反映请求资源的紧迫程度,排序原则：按优先级的高低排序 即：新产生的请求，按其优先级的高低 插入到队列中相应的位置,11,优点：系统可进行干预，以优化资源的使用方式,优先级的确定：主要由系统定，并可动态改变。如：进程时间片到：收回CPU，优先级降低 自动放弃CPU：优先级升高,问题：优先级相同的多个请求，如何排序？,缺点：插入时要搜索队列、有时无法用队列实现,适用的资源：由于系统开销较大，主要用于 系统中的紧缺资源(如处理机),12,多优先级队列 适用于：每个优先级上，有很多进程 排序：优先级不同，所排的队列不同 优先级相同，在同一队列中按FIFO排序,分配方式：仅当高优先级队列为空时 才考虑低优先级队列 优点：减少了系统的排序开销,3.针对设备特性的调度 思想：分配策略制定的资源访问次序 应与资源的实际使用次序相一致 目的：提高资源访问的平均速度,如：读、写磁盘上的多个扇区时,对数据的访问，涉及到磁头定位的：柱面(磁道)：由磁头的直线运动得到 耗时较长 扇区：通过磁盘的旋转得到，耗时较短 盘面：由不同的磁头的得到，不耗时,故要根据耗时的长短，依次决定访问次序,例：不好的访问次序,好的访问次序：应在磁头的一次移动或磁盘的一周旋转中完成,磁头,16,5.4 死锁的概念,一.什么是死锁 1.死锁的例子(1)交通堵塞,17,(2)不恰当的 P 操作 当：mutex=1 full=0 empty=n 时 p1()p2()while(生产未完成)while(还要继续消费)p(mutex)生产一个产品；p(full)；p(empty)；从缓冲区中取产品；p(mutex)；v(mutex)；送一个产品到缓冲区；v(empty)；v(mutex)；v(full)；消费一个产品；,18,(3)设备的共享 例：设系统只有一台打印机(R1)，和一台光标 记阅读机(R2)，由进程p1、p2 共享。用信号灯的P、V操作，控制资源的申请和释放,其信号灯的设置为：s1：表示R1是否可用，初值为1 s2：表示R2是否可用，初值为1,讨论资源分配的各个环节，看什么情况是安全的 先看资源的请求方式：,19,进程P1 进程P2 p(s1)；p(s2)；申请R1 申请R2 释放R1 释放R2 v(s1)；v(s2)；p(s2)；p(s1)；申请R2 申请R1 释放R2 释放R1 v(s2)；v(s1)；,原因：会同时封锁二个资源,进程P1 进程P2p(s1)；p(s2)；申请R1 申请R2p(s2)；p(s1)；申请R2 申请R1,释放R1释放R2 v(s1)；v(s2)；释放R2释放R1 v(s2)；v(s1)；,安全！不足：对同一个进程来说 资源的使用没有并发,不安全！,20,进 程 P1 进 程 P2p(s1)；p(s2)；申请R1 申请R2p(s2)；p(s1)；又申请R2 又申请R1 释放R1 释放R2 v(s1)；v(s2)；释放R2 释放R1v(s2)；v(s1)；,思考：若二进程顺序执行，是否安全呢？二进程如何执行，才会发生死锁？,由于系统已没有它们所等待的资源 而占有资源的进程本身也在等待(无法释放资源)从而造成一种永久的相互等待死锁,21,发生死锁的进程执行序列:时刻t1：进程 p1占用打印机 时刻t2：进程 p2占用光标记阅读机 时刻t3：进程 p1又请求光标记阅读机，等待 时刻t4：进程 p2又请求打印机，等待,思考：从资源的使用角度来看 对死锁问题应如何进行一般性的描述呢？,22,2.什么是死锁 在两个或多个并发进程中，如果每个进程都持有某种资源，而又都同时等待着 别的进程释放它们保持着的资源,即：在两个或多个并发进程中，所有的进程 都相互等待着其他的进程释放它们所持有的 某种资源，否则就不能向前推进,否则就不能向前推进 称这一组进程产生了死锁,(它们中),23,强调：(1)死锁是在n(n 2)个进程(不一定是所有进程)之间发生的一种状态 这种状态一旦发生，就永远无法改变?,(2)系统中已没有死锁进程所等待的资源了(已被它们自己全占用了，或即使有也不够),(3)平常说系统会死锁，是指：系统存在着死锁的可能(由资源得请求序列定)(但不一定会出现，由资源的实际使用定),探讨：出现死锁的原因到底是什么呢？,24,二.死锁的起因和条件(对设备的共享例),阴影区：资源被共享，进程的执行轨迹不可能进入,从图中可看出：1、死锁的原因(1)系统的资源总数各进程的资源总需求,能进行一般性的表述吗?因此：死锁没有充分条件!,(2)进程推进的顺序不合理(对资源的申请次序、使用方式、占有方式),26,(1)避开危险区（一个进程同时得到全部的资源）(2)将危险区变为阴影区(二进程申请资源次序一致)(3)从危险区回退(强行收回某进程占有的资源),2、解决死锁的方法：至少可看出三种,3.死锁的示意表示,占有边,占有边,申请边或等待边,申请边或等待边,用途：可描述资源的分配过程，若死锁则构成有向环,可用资源 进程有向图描述资源的使用状态,问题：若同一类型的资源有多个怎么表示？能否找到死锁的某些判别方法呢？判别,(1)资源次序图的一般形式 当同一资源有多个时,死锁的判别方法,资源的占有和申请可表示为：,4、死锁的判别方法,(a)若资源分配图中无环，则不存在死锁(b)若资源分配图中有环，且环内每类资源只有一个个体，则死锁发生(此时环是充分条件)(c)若资源分配图中有环，且环内有的资源有多个个体，则无法判定死锁是否发生(此时环不是充分条件)(d)对资源分配图可进行化简，若化简后的图中仍有环(无法化简)，则环中的进程被死锁,(2)死锁的判别方法,例1:,？,？,环？,例:,化简后的状态：,死锁？,(a)若节点只有占有边，则可去掉占有边并释放资源(b)当有了空闲的资源后，等待边可变为占有边,化 简 的 方 法,33,(1)互斥条件 涉及的资源为临界资源,5、死锁的必要条件,(2)不剥夺条件 进程占有的资源 不能被其他进程强行剥夺,(3)部分分配 每次仅申请一部分资源。在占有资源以后，还会继续申请新资源。只有不满足才等待,(4)环路条件 在进程与资源有向图中，存在有向环,意义：只要其中一条不成立，死锁就不会发生,34,三.死锁的预防和避免 基本点：破坏死锁的某一个必要条件(1)互斥条件(2)不剥夺条件(3)部分分配(4)环路条件,问题：破坏哪些必要条件是可行的呢？,35,降低了设备的利用率(只用很短时间，或根本不用)造成不必要的等待(一开始，可能并不用)用户可能提不出所需的全部资源,1.静态预防死锁(死锁不会发生)在作业调度时，为选中的作业 分配它所需要的所有临界资源 在作业的整个运行期间，这些资源都为它独占,缺点:,思考：(1)破坏了死锁必要条件中的哪一条？(2)资源利用率高不高？为什么？,2.有序资源分配法(不让死锁出现)按资源类对资源进行排序(每一类给定一个唯一的序号)分配请求必须以上升的次序进行；而且同一类型的资源必须一次申请完,思考：破坏了死锁的哪一个必要条件？如何破坏的？,37,5,假定n个进程(不妨设为P1Pn)被死锁 而且 Pi占有的资源序号最高(如5号),P1,Pi,Pn,4,5,5,则Pi等待的资源已被死锁的进程占有,而根据分配原则：分配请求必须以上升的次序进行 而且同一类的资源必须一次申请完,5,矛盾！,38,若：资源的使用次序与资源类的排序不一致时 低序号资源必须预先申请，降低了资源的利用率(用户很难做到与资源类的排序相一致),例如一个进程的资源请求次序为：p(S2)占住R2 p(S5)使用R5 使用R2,不足的地方？,能否做到：使用资源前才申请，而又不出现死锁呢？,基本思想：当系统现有的资源可保证申请进程完成时，才进行分配。否则，申请进程等待,3.银行家算法,不 进 行 分 配,进 行 分 配,Pi：,Pj：,银行家靠什么来积累财富呢？,说明：每次分配前都要进行相应的验证,P 0 8,Q 0 4,R 0 9,系统资源数：10,P 4 4,系统资源数：8,R 2 7,Q 2 2,系统资源数：4,系统资源数：2,思考：这种方法破坏了哪一个必要条件?它是如何避免死锁的呢？,Q 4 0,Q,系统资源数：0,系统资源数：4,P 8 0,P,系统资源数：0,系统资源数：8,例:某系统有三个进程共享同类型的10个资源进程已占资源数 还需资源数,基本原理：采用部分分配，且允许环存在。但任何时候 都有一个占有资源的进程是可完成的,进程的完成序列为：Q P R.,该进程完成后，释放资源 则又有另一个进程是可完成的如此重复，直到系统中所有的进程完成,即：系统的资源分配图，在任何时候 都是可化简的(没有发生死锁),如上例中：进程的申请序列为：.R P Q,P 0 8,Q 0 4,R 0 9,系统资源数：10,P 4 4,系统资源数：8,R 2 7,Q 2 2,系统资源数：4,系统资源数：2,Q 4 0,Q,系统资源数：0,系统资源数：4,P 8 0,P,系统资源数：0,系统资源数：8,进程已占资源数 还需资源数,R,P,Q,.,.,要点：(1)每次分配前都进行检测(2)确保死锁不会发生(3)对进程的资源申请方式不进行任何限制,不足：(1)还不够大胆。为什么？有些还需要的资源，以后可能不会再申请(2)对每类资源都要检测，开销较大 银行家算法的深入讨论,银行家算法的深入讨论,进程请求资源时可分三种情况进行处理：(1)每类资源还需数都 系统的拥有数：分配(2)每类资源还需数都 系统的拥有数：不分配,(3)仅部分资源类的还需数 系统的拥有数：则需判别系统的状态是否安全,若安全：不会死锁，分配 若不安全：可能会死锁，不分配,问题：如何对系统状态的安全进行判别呢？,系统状态的图论判别方法 将进程的还需资源也作为申请边：化简资源分配图 化简后，若图中所有的进程都是孤立节点：则系统是安全的 否则，系统是不安全的(可能会死锁),系统状态的程序判别算法所需的数据结构(t为时间参数，参考P 113)进程向量：P(t)=(p1、ppn),系统拥有的资源向量:W(t)=(r1、rrm)初值：系统对每类资源的最大拥有数,所有进程占有资源矩阵：A(t)=(行:进程；列:资源)初值：全为0,所有进程还需资源矩阵：R(t)=(行:进程；列:资源)初值：各进程对各类资源的最大需求数,可完成的进程向量：L(t)初值为空,算法的描述：对任一时刻 tWhile（存在 pi P(t)R(i,t)W(t)P(t)=P(t)-pi L(t)=L(t)+pi W(t)=W(t)+A(i,t),If P(t)=系统是安全的，不会死锁 else 系统是不安全的，其中的进程可能会死锁,对预防和避免死锁的评价 死锁出现的概率很小，而各种避免死锁的策略 都不同程度地降低了资源的利用率 因此一般的小系统，只对用户频繁使用的临界资源 才进行环路检测,问题：如果系统已出现死锁怎么办？,如写文件：若已上锁，进行环路检测，有环则收回CPU,四、死锁的检测和恢复,基本思想：允许死锁发生在适当的时机进行检测 若发现死锁，则进行恢复,1、死锁检测的方法(1)限定进程等待的时间(2)由系统管理员，观测进程的运行情况(3)定期执行检测算法(类似系统状态的判别，但仅用等待边进行),2、死锁恢复的方法(解开环)(1)逐个撤销死锁的进程，直到死锁打开优点：简单、可行性较强缺点：部分进程重新执行，代价较高,(2)逐个收回死锁进程占有的资源，直到 死锁打开(进程回退，要记住所有的分配点),(3)从上次未发现死锁的检测点处，重新执行(要保存上个检测点现场)为什么可行？,51,6.1 处理机的多级调度,一、处理机调度的功能 从资源管理的角度看，处理机调度的功包括：维护有关的数据结构 制订调度策略(谁能优先得到处理机)设计调度算法(实现调度策略)实施处理机的分配(保护、恢复现场；修改PCB、及有关的队列),问题：实现处理机的分配要经过那些过程呢？,52,另外，有些系统在内存紧张时，会将某些进程的程序在内、外存之间进行交换,只有内存的程序(进程)才能在CPU上运行,二、处理机调度的分层,就绪态的进程有多个，CPU分配给谁？,？,？,53,因此，处理机的调度可分为二层(或三层)(1)宏观调度 对象为作业，故又称为作业调度 任务：在已进入系统的作业中，按某种原则 挑选一个、或一批作业到内存执行,完成的工作：为选中作业的执行程序建立进程 为其分配内存 分配其他需静态分配的资源,54,(2)微观调度 对象为进程，故又称为进程调度 任务：确定哪个进程、在什么时候 获得处理机，以及使用多长时间,完成的工作：选择一个在内存就绪的进程 将其状态改为运行 若分时，给出运行的时间片 恢复该进程的现场,55,（3）中级调度 用于某些分时系统(如Unix)中 对象为进程 任务：确定哪些进程被允许参与处理机的竞争 短期内(如进程太多时)调整系统内存的负荷,完成的工作：,56,换出：在内存中最不可能得到CPU的进程 首先:等待态的就绪进程 其次：优先级低且驻留内存时间长的就绪进程,换入：在进程调度程序挑选运行进程前 换入在外存驻留时间较长的就绪进程,说明：对处理机的调度，不同的操作系统 往往采用不同的实现方式,57,6.2 作业调度,一个作业，是一个用户的一次上机过程。因此(1)最基本的作业：执行一个可执行程序(2)复杂的作业：执行一组可执行程序：如编译、连接、执行等,作业的表现形式：(1)批处理：用户提出的作业申请 完成内容：在操作说明书中所包含的所有执行语句(2)分时系统：用户登录后的活动(注销后结束)完成内容：通过终端输入的一组命令(可执行的程序),58,二、作业控制块 操作系统对作业进行管理的数据结构，称为作业控制块(JCB)，它是一个作业存在的标志。,JCB的主要内容包括：作 业 名 对资源的要求 估计执行时间 最迟完成时间 要求的主存量 要求外设的类型及台数 要求文件量和输出量,59,资 源 使 用 情况 进入系统的时间 开始执行的时间 已执行的时间 程序在主存的地址 占有的外部设备,状 态 优 先 级 作业类型(如：多CPU、多IO、或均衡等)控制方式(如脱机、联机),60,(1)设 作业 i 的周转时间为 ti，则 ti=完成时间提交时间=tci tsi 或：ti=运行时间等待时间,t=,四、作业调度性能的衡量,(2)平均周转时间,1.周转时间 从作业提交给系统，到完成所需的时间,意义：描述了作业 i 在系统中停留时间的长短,61,例：作业 运行时间 等待时间周转时间(分钟)1 5 25 30 2 20 20 40 调度算法对哪个作业有利呢？,(3)如何用于评价 对用户：周转时间越小越好(更方便)对系统：平均周转时间越小越好(吞吐量大、利用率高),原因？因为周转时间中包含了运行时间，使评价出现误差 平均周转时间同样也有类似的问题 如何衡量更准确呢？,10 15,问题：不够准确,62,2.带权周转时间(1)带权周转时间，指：一个作业的周转时间与其运行时间的比值 wi=？,(2)平均带权周转时间 t=精确度：二者都高于周转时间、平均周转时间,周转时间运行时间,等待时间运行时间,3.其他的衡量方法 可用CPU利用率、或系统吞吐量直接衡量(无满意度),意义：说明作业 i 在系统中的相对等待时间,=1+,63,五、作业调度算法 1.先来先服务调度算法(FCFS)特点：简单，易实现,8.00 9.10 1.10 1 9.10 9.60 1.10 2.2 9.60 9.90 0.90 3 9.90 10.00 0.50 5,1 8.00 1.10 2 8.50 0.50 3 9.00 0.30 4 9.50 0.10,平均周转时间 t=0.95 平均带权周转时间 w=2.8,提交 执行 开始 完成 周转 带权周转 作业 时间 时间 时间 时间 时间 时间,例：求周转时间与带权周转时间(单位：十进制小时),(4)评价：性能较差。原因：当短作业排在长作业后面时，由于 等待时间变长(而运行时间不变)，造成：平均周转时间、平均带权周转时间变长,例：运行时间 周转时间,而且短作业的相对等待时间较长，不满意,改进：短作业排在长作业前面,2.短作业优先调度算法(1)策略 按作业运行的时间长短进行调度(2)优点 易实现 系统吞吐量高,(3)缺点 只照顾短作业 而没有考虑长作业的利益,66,例：求周转时间与带权周转时间 提交 执行 开始 完成 周转 带权周转 作业 时间 时间 时间 时间 时间 时间,8.00 9.10 1.10 1 9.10 9.40 0.40 1.33,问题：长作业可能会饿死。如何解决呢？希望：,平均周转时间 t=0.825 平均带权周转时间 w=2.5,9.40 9.90 1.40 2.8,9.90 10.00 0.50 5,1 8.00 1.10 2 8.50 0.50 3 9.00 0.30 4 9.50 0.10,3.相应比高(带权周转时间长)者优先调度算法,相应比,调度策略：既短作业优先，以提高效率 又适当考虑长作业(一个原则),相应比,4.其他的优先数调度算法，如：优先数(等待时间分)2执行时间(秒)16*输出行 思考：上述二种策略，用队列排序是否有意义？,改进：,思考：上述公式中，调度策略是否得到完整的实现？,其实质是长作业优先、还是短作业优先？,如第二种调度策略中，有二个作业 按优先数当前排序如下：（4210）（5220）,但1分钟后，按优先数排序变为：（6220）（5210）,5.均衡调度目的：使系统中的所有资源都保持忙碌 以达到负载均衡，提高系统的资源利用率适用范围：批处理中的作业调度,方法：(1)将作业按对CPU的使用量进行分类：多CPU的(计算量大)多I/O的(输入、输出量大)均衡的(2)将各类作业均衡搭配起来进行调度,70,6.3 进程调度,一.进程调度、及CPU的分派 1.进程调度按一定的策略，在就绪状态的进程中 决定处理机分配的先后次序(通常是形成一个有序的就绪队列),71,二.进程调度的功能 1.记录进程的有关情况和状态特征(在PCB中),2.制定调度策略 优先调度原则：就绪队列按进程优先级高低排序 先来先服务原则：就绪队列按进程到来的先后次序(或等待时间的长短)排序,3.实施处理机的分配和回收,72,三.进程调度的方式指处理机是否可剥夺 可从广义(如分时)或狭义的角度讨论,狭义的是否可剥夺是指：采用优先级调度；一个进程正在处理机上运行；若出现优先级更高的的就绪进程：系统是否强行收回运行进程的处理机,73,.非剥夺方式 让执行进程继续执行，直到放弃CPU 后 才把处理机分配给优先级更高的进程 即：只在分配CPU时，才考虑优先级,.剥夺方式 立即把CPU分配给优先级更高的进程 即：总是优先级最高的进程占有CPU。,问题：二者都有片面性解决：采取有条件的剥夺，怎么表述呢？,74,3.选择可抢占策略 每个进程给出一对标志(U，V)根据高优先就绪进程和运行进程二者的标志，决定是否进行抢夺：U=1：表示可抢夺运行进程的CPU U=0：表示不可抢夺运行进程的CPU V=1：表示(运行进程)允许被其他进程抢夺 V=0：表示不允许被其他进程抢夺,75,进一步的问题：(1)一个系统的进程调度策略如何来描述？(2)与进程调度有关的各个模块 在什么条件下被激活执行？(3)这些模块之间有什么联系呢？,76,四.调度用的进程状态变迁图 例：某系统的进程状态变迁图如下所示,(一)通过进程状态变迁图 可反映系统进程调度的各种特征,77,1.队列的结构 一个I/O等待队列：进程如果请求I/O，则进入I/O等待队列,一个低优先就绪队列：运行进程用完了分配给它的时间片 就进入低优先就绪列 一个高优先就绪队列：当等待态的进程被唤醒后 则进入高优先就绪队列,78,2.CPU的分配(当CPU空闲时)(1)若高优先就绪队列非空：则从高优先就绪队列中 选择一个进程运行，分配时间片为100ms,3.调度策略(1)方式：采用非剥夺方式、优先级与时间片相结合(2)排序：IO量大的进程优先 对计算量大的进程也进行一定的补偿,(2)若高优先就绪队列为空、低优先就绪队列非空：则从低优先就绪队列选择一个进程，时间片500ms,79,CPU空闲、高优先就绪为空、低优先就绪非空,4.进程状态变迁的原因,变迁1：变迁2：变迁3：变迁4：变迁5：,运行进程时间片到或被抢占(剥夺方式),例：,运行进程请求IO后，等待IO的完成因 IO而等待的进程，所等待的IO已完成CPU空闲、高优先就绪非空,可用来描述、或了解 系统相关模块的 执行条件,80,5.因果变迁 所谓的因果变迁是指：一个状态的变迁发生后，是否也会引起其他的状态变迁发生?若可以，需要什么附加的前提条件？,用途：用来描述、或了解系统相关模块之间的联系 即：哪些模块，在什么条件下会相互调用？,81,变迁3 变迁5:变迁1 变迁3:变迁4 变迁5:变迁2 变迁4:变迁3 变迁2:,不可能，原因：理论：实际：理解：,无因果关系 可能，条件：,可能，条件：,关键是看：前一变迁的结果，对产生后一变迁的条件的影响(变少、不成立、不改变),(二)画进程状态变迁图 根据调度策略(或效果)，画进程状态变迁图,83,五.进程调度算法 基本要求：(1)若有作业调度，应与作业调度算法尽可能一致(批处理中)(2)算法应尽可能简单，以减少系统的开销(3)不能让进程长久地等待,1.进程优先数调度算法预先确定各进程的优先级(通常用一个优先数来表示)将处理机分配给优先级最高的就绪进程,84,()优先数的形式 可分为二种:静态优先数在进程被创建时按某种策略确定 而且在整个进程的运行期间不再改变,动态优先数在进程被创建时先给出一个初始的优先数(也称为基本优先级)在进程的运行中，再按某种策略进行调整,85,(2)优先数的确定基本的策略：占用CPU时间少的进程优先,静态优先数的确定 根据作业的运行时间来估计 根据作业所需使用的非CPU资源来估计(通常使用多者优先，为什么?)由用户提出优点：简单，系统开销小 问题：不准确、不灵活,86,动态优先数的确定 在进程运行期间，优先数可改变。基本的策略是：对预计的CPU时间进行估算，占用少的优先,一种最常用的估算方法是根据上一轮的 估计时间、实际占用时间来定，用公式表示为：k n+1=a*t n+(1-a)*k n k n：上一次估计的CPU占用时间 t n：上一次实际占用的CPU时间,通过系数 a 确定权值，常见的取值可为：a=1：k n+1=t n 用当前的实际占用时间 作为下一次估计时间(简单、较合理、最常用)a=0：k n+1=k n 估计时间为常数(时间片固定)a=1/2:k n+1=(k n+t n)/2 取平均值(综合考虑),87,(a)因等待而放弃CPU的进程：优先级提高，以提高设备的利用率,(b)进程使用CPU超过一定时间(如时间片)后：降低优先级,优先调度存在的问题：有的进程可能会长时间地等待(尽管可补偿)怎么解决？,由于CPU的切换非常频繁，根据前面的思想 能否不通过运算，就确定优先级呢？,88,2.按时间片循环轮转调度算法 策略：就绪队列按FIFO排序 目的：让所有的进程，均衡地使用CPU 问题：时间片如何定？,t i,t i+1,当前响应时间:t i=q*n i(n i为当前进程数),p1,p1,p4,(1)简单循环轮转调度(时间片 q 固定)就绪队列中的所有进程，等速度向前推进。,89,为有一个合理的平均响应时间 时间片 q 应固定为多长才合适呢？,如：q=200ms=0.2秒 当n j=60时：t j=12秒，响应时间长，用户不满意 当n k=4时：t k=0.8秒？,设 t max为用户容忍的响应时间，n为进程数，则有：q=t max/n=3000 ms/(6 60)=50 500 ms,浪费切换时间。如何解决？,存在的问题：q 固定后，响应时间随当前的进程数而变化,90,(2)可变时间片循环轮转调度 响应时间T固定(为用户所能接受的时间，如3秒)每一轮开始前，根据当前的就绪进程数Ni 决定该轮的时间片Qi(即Qi=T/Ni),进一步的问题：能否同时又考虑进程的优先级呢？,P4 P1 P2 P3,P4(等下一轮),效果：不同轮的时间片可能不同 同一轮中，各进程的时间片相同,3、多重时间片循环轮转调度算法 根据优先级的分布，采用多个就绪队列 进程按优先级，在相应就绪队列按FIFO排序,问题：如何避免、或补偿某些进程 经常的、长久的等待呢？,(1)Windows NT 采用类似的就绪队列结构 因等待而放弃CPU，提高优先级,(2)UNIX 优先数相同的就绪进程:可认为是排在同一个优先级的队列中 因等待而放弃CPU：置为较高的优先级,说明：二个系统中，用户都可:指定一个优先级的底线 进程调度实例,93,7.1 主存共享的特征,问题：执行程序在主存中是如何存放的？,一、主存共享的特征主存以分片的方式(按区域)实现共享。,问题：指令和数据的地址是如何表示的？,根据每个区域的大小是否相等，可分为：分区、分段存储管理：片的大小不等 页式存储管理：片的大小相等 段页式存储管理：两者结合,94,二、编址的基本概念 1.逻辑地址(程序地址、相对地址、虚地址)指：程序中(指令或数据)使用的地址,即：用户是在逻辑空间中，编写自己的程序 问题：逻辑地址就是程序在 内存中的地址 码？,2.逻辑空间(程序空间、作业的地址空间)逻辑地址的集合所对应的空间(整个程序),95,5.区域 由一组连续、递增的物理地址：n、n+1、nm 所对应的主存空间的一个子集 内存是以区域为单位进行分配的,3.物理地址(绝对地址、实地址)物理地址是计算机主存单元的地址 又称为绝对地址或实地址,4.物理空间（主存空间）物理地址的集合所对应的空间 用户程序是在物理空间中执行,96,主存管理的功能，可分为四个方面：(1)地址的映射(2)主存分配(3)存储保护(4)主存扩充,7.2 主存管理的功能,97,一、地址映射 1.为什么要进行地址映射 进程运行时，程序中所要访问的逻辑地址 通常与主存空间中的物理地址是不同的,这种情况可用图来说明,98,2.什么是地址映射 将程序空间中使用的逻辑地址，变换成主存中物理地址的过程，称为地址映射,.地址映射的方式(1)在程序中使用物理地址 用物理地址编写程序(机器语言)或：在连接时完成逻辑地址、物理地址间的变换,Mov r1,1500,优点：访问速度快缺点：程序只能在确定的机器、确定的装入点运行 在多道环境下无法实现为什么？,99,(2)静态地址映射 在作业装入过程中，随即进行的地址变换。称为静态重定位、或静态地址映射,优点：访问速度快；可在任意装入点和其他的机器上运行。不足：程序装入后不能在内存浮动(难于内、外存交换),100,(3)动态地址映射 在进程的执行期间，随着每条指令或数据的访问，进行地址映射,101,优点：通过改变重定位寄存器内容，可以实现：程序在内存可移动 一个程序可放在，多个不连续的内存区域 一个程序仅装入部分内容，就可运行 多个进程共享同一个程序的内存付本,102,二、主存扩充 计算机一出现，主存的容量就显得十分紧张 表现为二种形式：1、用户程序的空间 主存空间,解决方案：进程的整个程序在内外存之间交换(分区),103,2、某个用户程序的空间 主存空间(1)解决问题的思路 例如在Word中进行编辑时：只有在屏幕的窗口中 才能进行编辑 因此可将该窗口看作是一个编辑器,这个可滚动的窗口就是一个虚拟编辑器,当文档比窗口大时：我们是如何进行编辑的呢？,104,(2)实现方法(a)采用覆盖技术无调用关系的部分程序段，在内、外存之间交换,程序执行时：一段时间内频繁使用的仅是程序的一部分因此只需装入部分内容，程序也能正确地执行,不足：只是局部改善,105,(b)采用虚拟存储器 程序的全部代码和数据，存放在外存中 将当前执行的那部分代码和数据放入主存中 在程序的执行过程中，当所需信息不在主存时 从辅存调入到主存中,106,(3)什么是虚拟存储器 由操作系统和硬件相配合，完成信息在主存和辅存之间的交换 从而提供了一个存储容量比实际主存大得多的存储器 由于这个存储器在物理上并不存在，故称为 虚拟存储器，简称为虚存(是一种技术),思考：虚拟存储器的容量是有限的吗？虚存的最大容量，本质上由什么来决定？,107,三、主存分配 主存的分配涉及到：1、构造分配用的数据结构,2、制定各种策略(1)主存分配策略(2)放置策略 即当有多个满足要求的空闲区时：选择哪个空闲区进行分配,108,3、实施主存的分配(及回收)申请：提出所需主存的大小 返回：已分配主存的首地址,(3)调入策略 决定信息装入主存的时机，可分为 预调：在访问前将信息调入主存 请调：当需要信息时，才将信息调入主存,(4)淘汰策略 当主存中没有可用的空闲区时：决定将哪些信息从主存中移走,109,2、存储保护的方法 通常的可分为二个层次：(1)界地址保护：让不让访问(2)存储控制保护：让不让、及允许如何访问,四、存储保护 1、什么是存储保护 在多用户环境中，必须保证：每道程序只能在指定的存储区域内、进行指定的活动，这种措施叫做存储保护,110,3、界地址保护,保护方式：每次进行地址访问时，进行越界检测 若：下界寄存器 访问地址D 上界寄存器 则允许访问；否则：发生越界中断,思考：适用于那种地址映射？,(1)上、下界保护 设置 上、下界 寄存器,111,()基址、限长保护 设置基址、限长 寄存器,保护方式：每次进行地址访问时，进行越界检测 若：0 访问地址D 限长寄存器 允许访问；否则：发生越界中断,4、存储控制保护,关键是建立：进程存储区,允许的访问,PSW,Write(),113,程序的大小通常是不同的，这些区域怎么划分呢？早期是固定分区，以后发展为动态分区。,7.3 分区存储管理,基本思想：内存划分成多个区域，每个程序完整地装入到某一个区域中(提不提供虚存？)。,一、动态分区 1、什么是动态分区 在每个作业的装入过程中，依作业的大小，在空闲主存中建立一个分区，将作业的程序装入该分区中特点：分区的位置、分区数及大小都是不固定的,114,2.动态分区的过程(1)动态分区的分配,220KB,180KB,130KB,60KB,115,(2)动态分区的回收,问题：每个分区的属性应如何描述？如何尽快地找到满足要求的空闲区呢？,116,五、碎片问题 1、什么是碎片问题 在已分配区之间存在着的一些不能被利用的极小空闲区，浪费了内存,os 作业1 作业3 作业4,主存,2、如何解决碎片问题(1)规定剩余分区的阀值(2)采用拼接技术：移动某些已分配区中的信息将多个空闲区连成一个大空闲区,(1)进程的程序空间大小不同，形成的分区也大小不同(由程序所决定，无法解决),4、分区存在的问题 某些程序无法装入。可分为二种情况：(1)存在碎片，使得本可装入的程序无法装入(降低了内存利用率，而拼接的开销大)(2)没有足够的空闲内存时，作业无法装入 如何解决呢？,(2)每个作业都要求一片连续的内存区域,3、产生碎片的原因是什么呢？,5.解决办法(1)允许将一个程序放在多个不连续的区域中（没有不能利用的区域，消除了碎片）,(3)允许只装入一个作业的部分内容（用来提供虚存）,(2)将内存划分成多个大小相等的单位区域（便于管理）,119,7.4 页式存储管理,一、基本概念 1.主存块 主存被等分成大小相等的片 称为主存块(简称块)，又称为实页 2.页面 程序的地址空间也被等分成与块相等的片 称为页面(简称页)，又称为虚页,120,.内存的分配 以页为单位，分配主存块 块与块之间，可以不连续 思考：内存有没有未被利用的区域？,平均浪费率？(但不能称为碎片),121,4.作业的页面与主存块的关系,问题：块的大小应该如何来定呢？,0,2KB,254KB,0,2KB,4KB,6KB,主 存,作业地址空间,5.页长页(或块)的大小称为页长。页长通常为：512B(1000000000)4kB(1000000000000)1kB(10000000000)8kB(10000000000000)2kB(100000000000),思考：(1)页长值有何特点？为什么？(2)能否太大、太小？,太大：类似于固定分区；太小：页面交换频繁另外，也是为了提高内存的利用率。例如：当程序的平均长度为512k时，若页长为1k 则内存的利用率最高(99.8%)。确定页长,123,二、页式存储管理的地址变换 思考：分区存储管理是如何实现地址变换的？,物理地址分区首址(基址寄存器)逻辑地址,124,1.页表 记录一个进程中，每一个页面与内存块对应关系的地址变换机构，称为页面映像表。简称为页表,0,2KB,4KB,254KB,256KB,0,2KB,4KB,6KB,作业地址空间,页式系统只保留程序的首地址行不行？,100KB,102KB,内 存,必须保留每一页的首地址,125,2.分页存储映像的例子,思考：如何由逻辑地址，得到页号、页内位移？再得到块号、块内位移(页内位移？),126,3、逻辑地址结构 设逻辑地址的长度为16位，页面大小为 1KB(10位)。若给出以下的逻辑地址：,0000000000000010 0000110000000010 其对应的页号、页内位移各是多少呢？,127,因为页长是2的整数次方 所以页号和页内位移 是系统根据逻辑地址的结构自动形成的 注意：用户在程序中使用的逻辑地址 仍是一维地址 即：分页对用户是不可见(透明)的,128,4.页的地址变换,逻辑地址寄存器,物理地址寄存器,129,页式地址变换的步骤 将访问地址(2500)送逻辑地址寄存器 由分页机构把逻辑地址自动