计算机操作系统第六章.ppt

《计算机操作系统第六章.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统第六章.ppt（41页珍藏版）》请在三一文库上搜索。

1、主要内容,基础知识 请求分页存储管理 请求分段存储管理,第6章 虚拟存储器,6.1 基础知识,6.1.1 覆盖技术 覆盖技术，是程序运行过程中，在不同时刻把同一存储区分配给不同程序段或数据段，实现存储区共享的一种内存分配技术。 覆盖技术通常与单一连续区分配、固定分区分配和动态分区分配等存储管理技术配合使用。每一个用户程序都被分为若干程序段，一部分是经常要用的基本部分，作为常驻程序；另一部分不经常使用，可以让它们在需要时临时装入。当一段在内存中的程序运行完毕（或者暂时不运行）时，可以令它们放弃驻留权，让另一段程序占用它在内存中的位置。,例如，某进程的程序段由A、B、C、D、E、F、G和H等8个程

2、序段组成。它们之间的调用关系如图（a）所示。,交换(Swap)技术，是指将内存中某进程的程序和数据（全部或部分）写入外存交换区中，腾出来的内存空间供其它进程使用。待内存有空闲空间后再将它从外存交换区装入内存。 一、磁盘交换区管理 磁盘交换区是一个数据的暂存处。系统可根据内存的“拥挤”程度将信息调往交换区或者从交换区调入。,6.1.2 交换技术,操作系统管理下磁盘空间被划分为两部分：文件区和交换区。二者的区别主要有3点：,存储方式不同。文件区中的信息是以文件形式存放的，为了提高空间利用率，一般采取离散存储方式；而交换区是按字符流方式存放，多采用连续存储形式。 访问速度不同。文件区的存储空间特别大

3、，为了提高检索效率一般通过建立目录对文件实现访问，也就是间接地址访问；而交换区空间较小，可按外存地址直接访问，因此速度快。 存储时间不同。文件区的存储适合于较长久的数据存储；而交换区作为临时数据的存放处，只存放短期的数据。,二、进程调出 进程调出操作，需要选择一个近期无运行要求的进程调出内存。这里，处于阻塞状态的进程是首选的，其次是就绪状态的进程，一个正在共享的程序不在考虑之列。选择过程中的另一个参数是进程的优先级或响应比。 三、进程调入 进程调入操作需要选择一个具有运行条件且最迫切的进程，将它调入。一般来说，选择过程就是前面所讲的“中级调度”，选出的进程可通过“进程激活”装入内存。一般来讲，

4、系统选择的对象是处于“挂起就绪”状态的进程，处于“挂起阻塞”状态的进程不在考虑之列。,6.1.3 局部性原理,从程序对操作数的访问来看，一般情况下，一段程序访问的操作数也都局部于某个数据块中。因此在一个较短的时间内，程序执行中对内存地址的访问往往局限于一个较小的空间上。1968年，P.Denning提出了一个著名的“局部性原理”，并通过一幅运行图予以说明（见图所示）。,虚拟存储器（Virtual Memory）,一个进程运行时，可不必将其全部装载到内存中，只须把当前运行的部分程序和可能访问的数据块装入内存即可。随着进程运行的不断推进，其余部分程序和数据可随时装入。这样做可实现小内存运行大程序的

5、设想。从逻辑上说，系统拥有一个容量很大的存储器，这就是人们常说的虚拟存储器。 l 多次性 l 虚拟性 l 离散性 l 对换性,6.2 请求分页存储管理,请求分页（Demand Paging）存储管理是在普通的分页管理基础上，采用了虚拟技术发展起来的。由于分页管理中的页面长度是固定的，调出调入比较容易实现，因此目前许多操作系统中都支持这种管理方式。 6.2.1 地址变换 硬件上除了支持请求分页管理的内存和外存外，还要有相应的页表和地址变换机制，以及出现缺页（即某个需要运行的页面不在内存）时的中断响应机制等。,1页表 虚拟分页系统与普通分页系统的区别是，进程只有一部分页面进入内存。因此页表需要记录

6、哪些页面在内存，哪些不在内存。并且，页表中还要记录页面的外存位置，以便当某个需要运行的页面不在内存时，系统能够立即找到它，将它装载进来。 2地址变换机制 当调度一个进程时，系统将其页表首址装入CPU中的页表控制寄存器。运行中用相对地址的高端部分作为页号去检索页表，看该页是否已在内存。若已在内存就按普通分页机制的方式直接生成物理地址，并将访问标志和修改标志设置好。如果该页不在内存，则产生缺页中断信号，通过中断处理过程将缺页装入。,3中断处理机制 缺页中断是指令执行过程中产生的中断，而非（一般的中断）在一条指令执行完成后产生的。当CPU执行指令希望访问一个不在内存的页面时，将产生缺页中断，系统开始

7、运行中断处理程序。此时指令计数器（PC）的值尚未来得及增加就被压入堆栈，因此压入的断点必然是本次被中断的指令地址，而非下一条指令的地址。,中断处理过程如下： (1) 保留进程上下文。 (2) 判断内存是否有空闲帧？若有，则获取一个帧号No，转（4）。 (3) 腾出一个空闲帧，即： (3)-1 调用置换算法，选择一个淘汰页PTj。 (3)-2 PTj (S)=0； (3)-3 No =PTj (F);。 (3)-4 若该页曾修改过，则： (3)-4-1 请求外存交换区上一个空闲块B。 (3)-4-2 PTj (D)=B的外存地址。 (3)-4-3 启动I/O管理程序，将该页写到外存上。 (4)

8、按页表中提供的缺页外存位置，启动I/O，将缺页装入空闲帧中。 (5) 修改页表的状态字段。PTi(F)=No；PTi(S)=1。 (6) 结束。,地 址 变 换 流 程,虚拟分页系统中的页面分配应当以减少缺页率为目标。实践证明，进程占用的存储容量越小，缺页中断率就越高。Madnick曾经描述了一个真正的System 360系统中的程序缺页中断曲线（称为下降曲线），见图所示。,分配算法有以下3种： l平均分配法系统的可用空间平均分配给所 有进程，让它们都占有相等数量 的帧。这样分配对短作业来说是很有利的。而对于一些较大的进程，缺页率必然居高不下。 l优先权分配法考虑进程的优先运行权，给高优先的进

9、程分配较多的帧，使它的缺页率相对少一些。这里，我们可把优先权理解为高响应比、高优先级、最短剩余时间优先等。 l 比例分配法这种分配方法比较公平，小进程分配小空间，大进程分配大空间。当可用空间为M个帧，系统当前的进程数为n，每个进程的页面数量为si，那么按比例分配法，应当分配给进程i的页数pi为：,页面置换，是指在内存空间已被装满而又要装入新页 时，必须按某种算法将内存中的某页置换为一个新页。 下面介绍几种比较典型的页面置换算法。 1OPT（最佳置换）算法 OPT算法是一种理想化了的页面置换算法。该算法每次选择的淘汰页总是不再使用的，或者最长时间不再使用的页面，尽量避免刚调出去又要立即调入。 2

10、FIFO（先进先出）算法 这种算法的出发点是“先装入内存者先被置换”。系统总是把驻留在内存中时间最长的页面（常驻的除外）作为被淘汰的对象。,6.2.2 置换算法,3LRU（最近最久未使用）算法 被置换的页面是最长时间未访问的页面。这种算法所依据的原理是程序执行时所具有的局部性，即那些刚被使用过的页面可能马上再次被使用，而那些最久未使用的页面一般不会马上被用到。 4Clock（钟表算法）算法 这是一个建立在循环检测基础上的LRU近似算法，试图以较小的开销获得接近LRU的性能。该算法中将被置换的候选帧集合构成一个环状缓冲区，并设一个循环移动指针。初始时，该指针指向缓冲区的头部。当某页被选择置换后，

11、指针将顺序指向缓冲区的下一个帧。环状缓冲区中的每个候选帧关联一个“访问位”，记作A，当某帧的A=0时，说明该帧最近未被访问。显然，一个刚刚调入页面的帧，以及刚刚访问过的帧，其A=1。,5改进的Clock算法 一个提高Clock算法效率的方法是，为每个帧增设一个关联的“修改位”，记作M。如果M=1表示该帧中的页面被修改了，置换之前必须写到外存上。若将访问情况与修改情况一起考虑，每一帧可处于4种情况之一。 lA=0且M=0：该帧中所存的页面最近没有访问，也没有修改。 lA=1且M=0：该帧中所存的页面最近访问过，但没有修改。 lA=0且M=1：该帧中所存的页面最近没有访问，但修改了。 lA=1且M

12、=1：该帧中所存的页面最近访问过，也修改过。,据此给出改进的Clock算法的处理过程： （1）从指针当前位置开始，循环扫描候选帧，遇到的第1个A=0且M=0的帧，将该帧中的页面置换后返回。 （2）若循环一周后没有找到可置换的帧，则继续循环扫描，遇到的第1个A=0且M=1的帧，将该帧中的页面置换后返回。在这个过程中，每跳过一个帧就将它的访问位A设置为0。 （3）若第（2）步仍没有找到可置换的帧，则重复（1）和（2）必将能够找到一个可置换的帧。,6几种算法的性能比较 置换算法的选择，将直接影响到内存的利用率和系统效率。对于上述四种算法，计算机学者Baer曾于己于1980年做过一个实验，选取的页面尺

13、寸为256个字，分别实验了6、8、10、12、14帧的情况。当分配的帧数比较多时，四种算法的区别不太明显；而当分配的比较少时，它们的区别就相当显著了。特别是，当进程只有6个帧时，FIFO算法比OPT算法的缺页次数提高1倍还多。,实验结果如图所示。 其中，横坐标是帧数，纵坐标是缺页次数。,一、页面调入策略 在调页过程中有两个策略：一个是“随用随调”策略，另一个是“预调页”策略。 “预调页”策略的好处是：一次读多个连续的页面，可以减少磁头移动的时间，对系统效率提高有很大好处。另一个好处是，当发现缺页已在内存时，当前进程不必让出控制权，仅仅将缺页转移到用户区，修改页表后就可继续运行。,6.2.3 驻

14、留集和工作集,二、驻留集管理 驻留集，是进程在内存中的页面集合，驻留集尺寸是驻留在内存中的页面数量。 管理驻留集的方式有以下3种： （1）固定分配局部置换 （2）可变分配全局置换 （3）可变分配局部置换,三、工作集 工作集（working set）的概念是Denning提出来的，对虚拟存储器的设计产生过重大影响。一个进程的工作集W（t,）表示在时间t-到t之间 进程引用的一串页面；工作集的尺寸记作w（t,），指的是W（t,）中的页面数。w（t,）是的单调函数，也就是说，时间段越长，引用的页面越多，直到接近实际所需的页面总数（实际操作中，时间段长度往往用执行指令的数量来度量，而不是实际经历的时间

15、）。 在进程执行期间可以容易地确定该进程对存储空间的需求，也就是它的工作集尺寸。操作系统可以用这种方法决定给谁分配更多的帧，以及哪个进程应当让出一些帧来。,下面是按照工作集决定驻留集的策略 工作集策略 (1) 监视各进程的工作集。 (2) 周期性地从一个进程中调出那些不在它的工作集中的页，令其释放部分帧。 (3)当一个进程的驻留集包含了它的工作集时，才可以执行该进程。否则为进程增加新帧或者暂 缓调度该进程。,四、一种怪现象 在谈到驻留集时，有一种怪现象不得不提，那就是Belaly于1969年指出的，在FIFO算法中，有时增加更多的物理存储块后反倒导致利用率下降。 导致这种怪现象的页面走向虽然是

16、罕见的，然而必然还和其它因素有关。这说明，不能将“进程的可用帧越多缺页率就越低”这一结论绝对化。,6.2.4 抖动的产生和预防 抖动（Thrashing）又称颠簸，是指刚被调出去的页需要马上被调回，刚调回不久又要马上被调出。频繁调入调出，使系统的大部分时间都花费在内存和外存之间的来回折腾上。抖动主要表现为磁盘I/O极度繁忙，而处理机大量时间空闲。,一、抖动的产生及应对措施 产生抖动的原因归根到底是内存驻留的进程太多，下图是处理机利用率与多道程序度（即进程数量）之间的关系曲线。,从图中可以看出，当多道程序度达到M点时，处理机利用率最大。当系统处于M点左边的位置，也就是说驻留在内存的进程数量较少时

17、，处理机的利用率不高是因为负荷太轻所致。此时应当增加内存的进程数量方可提高利用率。如果系统处于M点的右边位置，也就是说内存的驻留进程较多时，处理机的利用率不高是因为系统过载而致。此种情况下，减少内存的进程数量是提高处理机利用率的当务之急。,二、抖动预防 下面的方法可以预防抖动的发生。 1在处理机调度中引入工作集策略 2采用局部置换策略防止抖动扩散 3挂起部分进程 一般选择缺页进程、最后被激活的进程、最大进程驻留集最小的进程、剩余执行时间最多的进程等。 4L=S准则 这一准则中，L是产生缺页的平均时间，S是系统处理缺页的平均时间。理论证明，当L=S是，处理机的利用率最高。该理论也得到实践的检验。

18、,6.3 请求分段存储管理,1段表 为了实现段的动态管理，我们要为每个进程设置一个段表ST，并在ST中设立一些“控制位”记录该段的控制信息,2地址变换,3缺段中断机制 与缺页中断类似，缺段中断也是指令执行过程中产生的中断，而不是产生在一条指令执行完成后。也就是说，进程执行一条指令产生缺段中断时，压入堆栈的断点是当前指令的地址。当缺段被装入内存后，该段变成了“实段”。进程再次恢复运行时，CPU将重新执行这条指令。 4中断处理程序 当第i#段是一个缺段，则缺段中断处理过程为： (1) 阻塞进程。 (2)Length STi(长度)。 (3) 检索“内存分配表”，若存在一个独立的内存块长度Lengt

19、h，则： (3)-1 将该内存块分配给进程。,(3)-2 首址B0；转(6)。 (4) 若内存可用空间总和Length，则： (4)-1 调用某种置换算法，选择一个内存中的段。 (4)-2 若该段被修改过，则，将它写回外存。 (4)-3 修改“内存分配表”。 (4)-4 转(3)。 (5) 内存各进程浮动，拼接出一个足够大的内存空间； 将该内存块分配给进程；首址B0。 (6) 从外存读入缺段，存入B0处。 (7) STi(B) B0；STi(S) 1。 (8) 修改内存分配表。 (9) 唤醒进程。 (10) 结束。,6.3.2 分段共享,1共享段表SST 为了实现段的共享，系统设一个“共享段表

20、”（SST，Sharing Segment Table），记载各个共享段的使用情况。任何一个进程调用共享段时，系统都将访问该表。 2共享段的分配 共享段的空间分配与一般段的分配有所不同，共享段在内存中只驻留一个备份，所有共享该段的进程都通过自己的逻辑段号映射到该共享段上。,分配过程为： （1）当系统为一个进程分配地址空间并创建段表ST时，若发现该进程调用了某个共享段，比如说，Sqrt段，系统检查内存中的共享段表SST。 （2）若SST中已包含Sqrt段，则系统就将Sqrt段的内存基地址拷贝到进程的ST中，并将SST中关于Sqrt段的共享计数字段加1，转第（4）步。 （3）若SST中未包含Sqr

21、t段，说明该进程是第一个使用该共享段Sqrt的进程。系统需要为该共享段分配存储空间，将该段加载到内存中。此外，还要在SST中增加一个表项，将共享段的信息填入，并将共享计数字段加1。 （4）将进程的信息填入SST的相关字段中。,3共享段的回收 当一个进程被撤消时，其地址空间需要回收。此时系统需要扫描它的段表ST，当发现该进程使用了某个共享段，比如Sqrt段，则： （1）系统扫描内存中的共享段表SST，查找共享段Sqrt。 （2）将共享段Sqrt的共享计数字段减1。若其值不为0，说明当前尚有其它进程正在使用该段，撤消SST中关于该进程情况的记载，返回。 （3）若共享计数字段的值为0，说明当前已没有

22、进程使用该共享段Sqrt了。应当立即将它从内存中撤消，同时将该段信息从SST中删除。,6.3.3 请求段页式存储管理,原理： 也称分段加请求分页的存储管理方式。把段划分为若干个页面进行离散存储。系统将一个段的当前页面调入内存，其余的仍驻留在外存上，随时需要随时通过缺页中断装入。 硬件支持：处理机中设有段表控制寄存器参与地址映射，存放的内容是段表起始地址和段表长度。在地址结构方面，页面长度和分段长度由系统对控制寄存器的安排来决定。 软件支持：在请求段页式管理系统中，缺页置换算法是必须的，而且与纯粹请求分页管理机制中采用的算法相同。,请求段页式存储管理,优点：请求段页式管理系统的主要是具有虚拟存储器的功能，并保持了段页式管理的优点：既体现段的独立性，又纳入了页的离散分配，使系统更加灵活。 缺点：增加了硬件的成本，系统复杂性提高，而且段表和页表的存储与检索问题突出，对处理机的运行速度影响较大。,本章结束,