计算机操作系统第六章课件

主要内容基础知识请求分页存储管理请求分段存储管理第6章虚拟存储器

16.1基础知识6.1.1覆盖技术

覆盖技术，是程序运行过程中，在不同时刻把同一存储区分配给不同程序段或数据段，实现存储区共享的一种内存分配技术。覆盖技术通常与单一连续区分配、固定分区分配和动态分区分配等存储管理技术配合使用。每一个用户程序都被分为若干程序段，一部分是经常要用的基本部分，作为常驻程序；另一部分不经常使用，可以让它们在需要时临时装入。当一段在内存中的程序运行完毕（或者暂时不运行）时，可以令它们放弃驻留权，让另一段程序占用它在内存中的位置。2例如，某进程的程序段由A、B、C、D、E、F、G和H等8个程序段组成。它们之间的调用关系如图（a）所示。3操作系统管理下磁盘空间被划分为两部分：文件区和交换区。二者的区别主要有3点：存储方式不同。文件区中的信息是以文件形式存放的，为了提高空间利用率，一般采取离散存储方式；而交换区是按字符流方式存放，多采用连续存储形式。

访问速度不同。文件区的存储空间特别大，为了提高检索效率一般通过建立目录对文件实现访问，也就是间接地址访问；而交换区空间较小，可按外存地址直接访问，因此速度快。存储时间不同。文件区的存储适合于较长久的数据存储；而交换区作为临时数据的存放处，只存放短期的数据。

5二、进程调出进程调出操作，需要选择一个近期无运行要求的进程调出内存。这里，处于阻塞状态的进程是首选的，其次是就绪状态的进程，一个正在共享的程序不在考虑之列。选择过程中的另一个参数是进程的优先级或响应比。三、进程调入进程调入操作需要选择一个具有运行条件且最迫切的进程，将它调入。一般来说，选择过程就是前面所讲的“中级调度”，选出的进程可通过“进程激活”装入内存。一般来讲，系统选择的对象是处于“挂起就绪”状态的进程，处于“挂起阻塞”状态的进程不在考虑之列。66.1.3局部性原理

从程序对操作数的访问来看，一般情况下，一段程序访问的操作数也都局部于某个数据块中。因此在一个较短的时间内，程序执行中对内存地址的访问往往局限于一个较小的空间上。1968年，P.Denning提出了一个著名的“局部性原理”，并通过一幅运行图予以说明（见图所示）。76.2请求分页存储管理

请求分页（DemandPaging）存储管理是在普通的分页管理基础上，采用了虚拟技术发展起来的。由于分页管理中的页面长度是固定的，调出调入比较容易实现，因此目前许多操作系统中都支持这种管理方式。

6.2.1地址变换

硬件上除了支持请求分页管理的内存和外存外，还要有相应的页表和地址变换机制，以及出现缺页（即某个需要运行的页面不在内存）时的中断响应机制等。91．页表虚拟分页系统与普通分页系统的区别是，进程只有一部分页面进入内存。因此页表需要记录哪些页面在内存，哪些不在内存。并且，页表中还要记录页面的外存位置，以便当某个需要运行的页面不在内存时，系统能够立即找到它，将它装载进来。

2．地址变换机制当调度一个进程时，系统将其页表首址装入CPU中的页表控制寄存器。运行中用相对地址的高端部分作为页号去检索页表，看该页是否已在内存。若已在内存就按普通分页机制的方式直接生成物理地址，并将访问标志和修改标志设置好。如果该页不在内存，则产生缺页中断信号，通过中断处理过程将缺页装入。103．中断处理机制缺页中断是指令执行过程中产生的中断，而非（一般的中断）在一条指令执行完成后产生的。当CPU执行指令希望访问一个不在内存的页面时，将产生缺页中断，系统开始运行中断处理程序。此时指令计数器（PC）的值尚未来得及增加就被压入堆栈，因此压入的断点必然是本次被中断的指令地址，而非下一条指令的地址。11地址变换流程13

虚拟分页系统中的页面分配应当以减少缺页率为目标。实践证明，进程占用的存储容量越小，缺页中断率就越高。Madnick曾经描述了一个真正的System360系统中的程序缺页中断曲线（称为下降曲线），见图所示。

14

分配算法有以下3种：

l

平均分配法——系统的可用空间平均分配给所有进程，让它们都占有相等数量的帧。这样分配对短作业来说是很有利的。而对于一些较大的进程，缺页率必然居高不下。l

优先权分配法——考虑进程的优先运行权，给高优先的进程分配较多的帧，使它的缺页率相对少一些。这里，我们可把优先权理解为高响应比、高优先级、最短剩余时间优先等。l

比例分配法——这种分配方法比较公平，小进程分配小空间，大进程分配大空间。当可用空间为M个帧，系统当前的进程数为n，每个进程的页面数量为si，那么按比例分配法，应当分配给进程i的页数pi为：

15

3．LRU（最近最久未使用）算法

被置换的页面是最长时间未访问的页面。这种算法所依据的原理是程序执行时所具有的局部性，即那些刚被使用过的页面可能马上再次被使用，而那些最久未使用的页面一般不会马上被用到。4．Clock（钟表算法）算法

这是一个建立在循环检测基础上的LRU近似算法，试图以较小的开销获得接近LRU的性能。该算法中将被置换的候选帧集合构成一个环状缓冲区，并设一个循环移动指针。初始时，该指针指向缓冲区的头部。当某页被选择置换后，指针将顺序指向缓冲区的下一个帧。环状缓冲区中的每个候选帧关联一个“访问位”，记作A，当某帧的A=0时，说明该帧最近未被访问。显然，一个刚刚调入页面的帧，以及刚刚访问过的帧，其A=1。175．改进的Clock算法

一个提高Clock算法效率的方法是，为每个帧增设一个关联的“修改位”，记作M。如果M=1表示该帧中的页面被修改了，置换之前必须写到外存上。若将访问情况与修改情况一起考虑，每一帧可处于4种情况之一。l

A=0且M=0：该帧中所存的页面最近没有访问，也没有修改。l

A=1且M=0：该帧中所存的页面最近访问过，但没有修改。l

A=0且M=1：该帧中所存的页面最近没有访问，但修改了。l

A=1且M=1：该帧中所存的页面最近访问过，也修改过。18据此给出改进的Clock算法的处理过程：（1）从指针当前位置开始，循环扫描候选帧，遇到的第1个A=0且M=0的帧，将该帧中的页面置换后返回。（2）若循环一周后没有找到可置换的帧，则继续循环扫描，遇到的第1个A=0且M=1的帧，将该帧中的页面置换后返回。在这个过程中，每跳过一个帧就将它的访问位A设置为0。（3）若第（2）步仍没有找到可置换的帧，则重复（1）和（2）必将能够找到一个可置换的帧。19

6．几种算法的性能比较

置换算法的选择，将直接影响到内存的利用率和系统效率。对于上述四种算法，计算机学者Baer曾于己于1980年做过一个实验，选取的页面尺寸为256个字，分别实验了6、8、10、12、14帧的情况。当分配的帧数比较多时，四种算法的区别不太明显；而当分配的比较少时，它们的区别就相当显著了。特别是，当进程只有6个帧时，FIFO算法比OPT算法的缺页次数提高1倍还多。21实验结果如图所示。其中，横坐标是帧数，纵坐标是缺页次数。22

一、页面调入策略

在调页过程中有两个策略：一个是“随用随调”策略，另一个是“预调页”策略。“预调页”策略的好处是：一次读多个连续的页面，可以减少磁头移动的时间，对系统效率提高有很大好处。另一个好处是，当发现缺页已在内存时，当前进程不必让出控制权，仅仅将缺页转移到用户区，修改页表后就可继续运行。6.2.3驻留集和工作集

23

三、工作集

工作集（workingset）的概念是Denning提出来的，对虚拟存储器的设计产生过重大影响。一个进程的工作集W（t,）表示在时间t-到t之间进程引用的一串页面；工作集的尺寸记作w（t,），指的是W（t,）中的页面数。w（t,）是的单调函数，也就是说，时间段越长，引用的页面越多，直到接近实际所需的页面总数（实际操作中，时间段长度往往用执行指令的数量来度量，而不是实际经历的时间）。在进程执行期间可以容易地确定该进程对存储空间的需求，也就是它的工作集尺寸。操作系统可以用这种方法决定给谁分配更多的帧，以及哪个进程应当让出一些帧来。25下面是按照工作集决定驻留集的策略——工作集策略

(1)

监视各进程的工作集。(2)

周期性地从一个进程中调出那些不在它的工作集中的页，令其释放部分帧。(3)

当一个进程的驻留集包含了它的工作集时，才可以执行该进程。否则为进程增加新帧或者暂缓调度该进程。26一、抖动的产生及应对措施产生抖动的原因归根到底是内存驻留的进程太多，下图是处理机利用率与多道程序度（即进程数量）之间的关系曲线。

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

1．段表

为了实现段的动态管理，我们要为每个进程设置一个段表ST，并在ST中设立一些“控制位”记录该段的控制信息

322．地址变换33

3．缺段中断机制

与缺页中断类似，缺段中断也是指令执行过程中产生的中断，而不是产生在一条指令执行完成后。也就是说，进程执行一条指令产生缺段中断时，压入堆栈的断点是当前指令的地址。当缺段被装入内存后，该段变成了“实段”。进程再次恢复运行时，CPU将重新执行这条指令。

4．中断处理程序当第i#段是一个缺段，则缺段中断处理过程为：(1)阻塞进程。(2) LengthSTi(长度)。(3)检索“内存分配表”，若存在一个独立的内存块长度Length，则：(3)-1将该内存块分配给进程。34(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)结束。356.3.2分段共享

1．共享段表SST

为了实现段的共享，系统设一个“共享段表”（SST，SharingSegmentTable），记载各个共享段的使用情况。任何一个进程调用共享段时，系统都将访问该表。2．共享段的分配

共享段的空间分配与一般段的分配有所不同，共享段在内存中只驻留一个备份，所有共享该段的进程都通过自己的逻辑段号映射到该共享段上。36分配过程为：（1）当系统为一个进程分配地址空间并创建段表ST时，若发现该进程调用了某个共享段，比如说，Sqrt段，系统检查内存中的共享段表SST。（2）若SST中已包含Sqrt段，则系统就将Sqrt段的内存基地址拷贝到进程的ST中，并将SST中关于Sqrt段的共享计数字段加1，转第（4）步。（3）若SST中未包含Sqrt段，说明该进程是第一个使用该共享段Sqrt的进程。系统需要为该共享段分配存储空间，将该段加载到内存中。此外，还要在SST中增加一个表项，将共享段的信息填入，并将共享计数字段加1。（4）将进程的信息填入SST的相关字段中。3