操作系统教程Linux实例分析孟庆昌第4章存储器.ppt

第4章 存储器管理,4.1 引言 4.2 基本的内存管理技术 4.3 对换技术 4.4 分页技术 4.5 分段技术 4.6 虚拟存储器 4.7 请求分页技术,4.8 页面置换算法 4.9 内存块分配算法和抖动问题 4.10 段式虚拟存储器 4.11 段页式结合系统 4.12 Linux系统的存储管理 习题,4.1 引 言,内存(Main Memory或Primary Memory或Real Memory)也称主存，是指CPU能直接存取指令和数据的存储器。磁盘、磁鼓和磁带等存储器，一般称为外存或辅存（Secondary Storage）。内存是现代计算机系统进行操作的中心，如图4-1所示，CPU和I/O系统都要和内存打交道。,图4-1 内存在计算机系统中的地位,4.1.1 用户程序的主要处理阶段 我们用高级语言编程解决某个特定的任务时，通常先对它进行数学抽象，确定相应的数据结构和算法，然后用高级程序设计语言（如PASCAL、C语言等）或者汇编语言进行程序设计。这种用高级语言或汇编语言编写的程序就称为源程序。从用户的源程序进入系统到相应程序在机器上运行，要经历一系列步骤，主要处理阶段有：编辑、编译、连接、装入和运行。如图4-2所示。,图4-2 用户程序的主要处理阶段,1.编辑阶段 用户键入编辑命令，如vi，进入编辑方式。在编辑方式下用户将所编写的源程序输入到机器内，存放在相应的文件（如filel.c）中。这种存放源程序的文件叫做源文件。2.编译阶段 源程序并不能直接在机器上运行，因为CPU不能识别源程序，它仅仅认识由规定范围内的一系列二进制代码所组成的指令和数据，并按预定含义执行一系列动作。,3.连接阶段 用户程序可以分别进行编译，从而得到不同的目标模块。而且用户程序中往往要调用系统库程序和应用程序，这些程序是预先就编译好的。这些目标代码不能简单地合并在一起，因为各自分配的内存地址可能有冲突，并且调用者还不知道被调用模块放在什么地方，仅知道它的符号名称。,4.装入阶段 程序必须装到内存才能运行。这就需要装入程序根据内存的使用情况和分配策略，将上述装入模块放入分到的内存区中。,5.运行阶段 为了运行装入内存中的程序，需要键入运行命令。在UNIX/Linux环境中，可直接键入可执行文件的名称。此时，终端进程创建一个子进程。当这个进程被调度程序选中后，CPU就去执行该进程的可执行代码。就是说，该用户程序被执行了。,4.1.2 重定位 由于内存地址是从统一的一个基址0开始按序编号的，就像是一个大数组那样，因此，内存空间是一维的线性空间。用户程序和数据装入内存时，需要进行重定位。例如，图4-3表示程序A装入内存前后的情况。在地址空间100号单元处有一条指令“LOAD 1，500”，它实现把500号单元中的数据12345装到寄存器1中去。,图4-3 程序装入内存时的情况,1.静态重定位 静态重定位是在目标程序装入内存时，由装入程序对目标程序中的指令和数据的地址进行修改，即把程序的逻辑地址都改成实际的内存地址。对每个程序来说，这种地址变换只是在装入时一次完成，在程序运行期间不再进行重定位。按照静态重定位方式，图4-3所示的程序A装入内存时的情况就变成如图4-4所示的样子。,图4-4 静态重定位示意图,它的主要缺点是：（1）程序的存储空间只能是连续的一片区域，而且在重定位之后就不能再移动。这不利于内存空间的有效使用。（2）各个用户进程很难共享内存中的同一程序的副本。,2.动态重定位 动态重定位是在程序执行期间每次访问内存之前进行重定位。这种变换是靠硬件地址变换机构实现的。通常采用一个重定位寄存器，其中放有当前正在执行的程序在内存空间中的起始地址，而地址空间中的代码在装入过程中不发生变化。动态重定位的过程如图4-5所示。,图4-5 动态重定位示意图,如果用(BR)表示重定位寄存器中的内容，用addr表示操作对象的相对地址，则操作对象的绝对地址就是(BR)+addr的值。动态重定位的主要优点是：（1）程序占用的内存空间动态可变，不必连续存放在一处。（2）比较容易实现几个进程对同一程序副本的共享使用。,4.2 基本的内存管理技术,内存的一部分是固定分配给操作系统的，可以位于内存最低端的RAM（随机存取存储器）中，如图4-6(a)所示；也可位于内存最高端的ROM（只读存储器）中，如图4-6（b）所示；还可以让设备驱动程序位于内存高端的ROM中，而让操作系统的其他部分位于低端的RAM中，如图4-6(c)中所示。,图4-6 单一连续分配,4.2.2 分区法 分区分配是为支持多道程序开发、运行的一种最简单的存储管理方式。在这种方式下，要把内存划分成若干分区，每个分区里容纳一个作业。按照分区的划分方式，可归纳为两种常见的分配方法：固定分区法和可变分区法。,图4-7 固定分区,1.固定分区法“固定”包含两个意思：一个是内存中分区的个数固定，不能随机变动；另一个是各分区的大小固定。当然各个分区的大小可以不同。但是，一旦在系统启动时把内存的分区划分好，以后在使用过程中就不能更改了。所以，固定分区法是对内存的静态划分。固定分区的管理方法如图4-7所示。,图4-8 分区说明表,2.可变分区法 由于用户作业大小不可能预先规定好，作业到来的分布也无法确定，所以分区的大小不会总与作业大小相符。为了解决内存浪费问题，可以把分区大小改成可变的，就是说，各个分区是在相应作业处理过程中建立的，使其大小恰好适应作业的大小。这种技术称为可变分区法。IBM的OS/360 MVT（具有可变任务数的多道程序设计）操作系统就是采用这种技术：操作系统掌管一个表格，登记每个空闲区和已分配区，指出其大小、位置和对各个区的存取限制等。图4-9表示了MVT的内存分配和作业调度示例。,图4-9 MVT的内存分配和作业调度(a)内存初始情况和作业队列；(b)内存分配和作业调度,图4-9 MVT的内存分配和作业调度(a)内存初始情况和作业队列；(b)内存分配和作业调度,1）最先适应算法 最先适应算法也称为首次适配算法。在这种算法中，空闲表是按位置排列的（即空闲块地址小的，在表中的序号也小）。2）循环适应算法 循环适应算法也称作下次适配算法。它是对最先适应算法的修改：当每次找到合适的空闲块时，就同时记下当时的位置，下次查找空闭块时就从下一个空闲分区开始查找，而不是每次都从头开始查找。,3）最佳适应算法 最佳适应算法是在满足需要的前提下分配最小的那块。这种算法的空闲表是以空闲块的大小为序、按增量形式排列的，即小块在前，大块在后。这种算法的优点是：产生的剩余块是最小的，平均而言，只要查一半空闲表就能找到最佳适应的空闲块。但是其缺点是：不便于释放内存时与邻接区的合并，而且分割后所剩余的空闲区往往很小，几乎无法使用。,4）最坏适应算法 最坏适应算法是最佳适应算法的“逆”，即空闲表是以空闲块的大小为序，但大块在前、小块在后。,3.硬件支持 采用分区技术需要有硬件保护机构。通常用一对寄存器分别表示用户程序在内存中的上界地址值和下界地址值，如图4-10所示。,图4-10 分区的硬件保护,这一对寄存器也可用另一种方式设置值，一个表示用户程序的最小物理地址，称为基址寄存器；另一个表示用户程序逻辑地址的范围，称为限长寄存器。虽然这两种方式都用一对寄存器进行保护，但两者的重定位方式是不同的。前者采用静态重定位，在汇编或装入时进行，程序中的每个有效地址必须大于或等于下界值而小于上界值。而后者需采用动态重定位，每个有效地址必须小于限长寄存器值，而相应物理地址是有效地址加上基址寄存器的值，如图4-11所示。CDC 6600及其以后的机器都用这种方式。,图4-11 基址/限长寄存器的使用,4.分区分配的优点和缺点 总体来说，分区分配的优点主要是：有利于多道程序设计；所需硬件支持很少；管理算法简单，易于实现。但分区分配也存在很多缺点，主要有：碎片问题严重，有些作业序列可能使内存的利用率低于10%；不利于大作业运行，当空闲块只有一个，但装不下后面的作业时，内存仍造成浪费；为容纳多个作业，需要的内存容量更大；已被占用的分区中可能包括从未使用过的信息，且作业分区大小受到内存总量的限制。,虽然可变分区比固定分区的内存利用率要高一些，但是二者都存在碎片问题。怎样使这些分散的、较小的空闲区得到合理使用呢？最简单的办法是定时或在分配内存时把所有的碎片合并为一个连续区，如图4-12所示。,图4-12 可重定位分区的紧缩(a)初始状态；(b)移动之后；(c)分配作业5之后,图4-13“占两头、空中间”的分区方式,4.3 对 换 技 术,4.3.1 早期对换技术 对换技术是在早期分时系统中（如CTSS和Q-32）采用的基本内存管理方式。它的实现思想是：除操作系统空间之外剩余的全部内存都分给当前正在执行的用户进程使用，当调度转向下一个用户进程时，当前进程内存区中的内容要写到外存（如磁盘）中去，被选中用户进程的信息读到内存中来，如图4-14所示。,图4-14 利用磁盘对换两个进程,4.3.2 多道程序环境下的对换 图4-15示出多道程序环境下对换系统的工作情况。最初只有进程A在内存，随后创建进程B和C（或者二者从盘上换入内存）。在图4-15(d)中A换出。然后，D换入，B完成，最后A再次换入。由于A现在的位置不同于先前，因此必须重定位或者在换入时由软件完成，或者在程序执行时由硬件实现（这是常用方式）。,图4-15 进程对换时内存分配情况,4.4 分 页 技 术,4.4.1 分页存储管理的基本概念 分页存储管理的基本方法是：(1)逻辑空间分页：将一个进程的逻辑地址空间划分成若干个大小相等的部分，每一部分称为页面或页。每页都有一个编号，叫做页号，页号从0开始依次编排，如0，1，2，。,（2）内存空间分块：把内存也划分成与页面相同大小的若干个存储块，称为内存块或页框。（3）逻辑地址表示：在分页存储管理方式中，表示地址的结构如图4-16所示。,图4-16 分页技术的地址结构,31 12 11 0,它由两个部分组成：前一部分表示该地址所在页面的页号p；后一部分表示页内位移d，即页内地址。图4-16中所示两部分构成的地址长度为32位。其中011为页内地址，即每页的大小为4 KB；1231位为页号，表示地址空间中最多可容纳1 MB个页面。,对于特定机器来说，其地址结构是一定的。如果给定的逻辑地址是A，页面的大小为L，则页号p和页内地址d可按下式求得：p=INTA/L d=A MOD L,（4）内存分配原则：在分页情况下，系统以块为单位把内存分给进程，并且一个进程的若干页可分别装入物理上不相邻的内存块中。进程的每个页面对应一个内存块，如图4-17所示。,图4-17 分页存储管理系统,（5）页表：在分页系统中允许将进程的各页面离散地装入内存的任何空闲块中，这样一来就出现进程的页号连续、而块号不连续的情况。怎样找到每个页面在内存中对应的物理块呢？为此，系统又为每个进程设立一张页面映像表，简称页表。如图4-17中所示。从图4-17中的页表可知，页号3对应内存的10#块。（6）内存块表：操作系统管理整个内存，它必须知道物理存储的情况，即哪些块已经分出去了，哪些块还是空闲的，总共有多少块，等等。,4.4.2 分页系统中的地址映射 通常，页表都放在内存中。当进程要访问某个逻辑地址中的数据时，分页地址映像硬件自动按页面大小将CPU得到的有效地址（相对地址）分成两部分：页号和页内地址（p,d）。如图4-16所示。分页系统的地址转换机构如图4-18所示。,图4-18 分页中的地址转换过程,4.4.3 快表和页表构造 1.快表 在内存中放置页表也带来存取速度下降的矛盾。因为存取一个数据（或一条指令）至少要访问两次内存：一次是访问页表，确定存取对象的物理地址；另一次是根据这个物理地址存取数据（或指令）。,解决这个问题的常用办法是使用专用的、高速小容量的联想存储器（TLB，Translation Lookaside Buffer），每个联想存储器包括两个部分：键号和值，键号是当前进程正在使用的某个页面号，值是该页面所对应的物理块号。图4-19示出带有快表的分页系统中地址转换过程。,图4-19 利用快表实现地址转换,2.页表构造 1）多级页表 在上面介绍中每个进程只用一个页表来实现从逻辑地址到物理地址的转换。在逻辑地址空间较小的情况下这是可行的。但现代大多数计算机系统都支持非常大的地址空间，如232264，此时若只用一级页表的话，就使得页表很大。两级页表方式下逻辑地址结构如图4-20所示。,图4-20 两级页表的地址结构,具有两级页表结构的系统中地址转换的方法是：利用外层页号p1检索外层页表，从中找到相应内层页表的基址；再利用p2作为该内层页表的索引，找到该页面在内存的块号；用该块号和页内地址d拼接起来就形成访问内存的物理地址了，如图4-21所示。,图4-21 具有两级页表的地址转换机构,外层页表要有242项，即244字节。为此，把外层页表再分页，于是得到三级页表结构。三级页表的地址结构如图4-22所示。,图4-22 三级页表的地址结构,2）倒置页表 上述进程的页表都是以页号为索引去搜索页表，即页表是按虚拟地址排序的。随着64位虚拟地址空间在处理器上的应用，使得内存空间显得很小。在此情况下，按逻辑页号为序构造页表，则页表会非常大。为了减少页表占用过多内存空间，可以采用倒置页表（Inverted Page Table）。倒置页表的构造恰与普通页表相反，它是按内存块号排序，每个内存块占有一个表项。每个表项包括存放在该内存块中页面的虚拟页号和拥有该页面的进程标识符。这样，系统中只有一个页表，每个内存块对应惟一的表项。图4-23示出倒置页表的操作过程。,图4-23 倒置页表,4.4.4 页的共享和保护 在多道程序系统中，数据共享很重要。尤其在一个大型分时系统中，往往有若干用户同时运行相同的程序（如编辑程序、编译程序）。很显然，更有效的办法是共享页面，避免同时在内存中有同一页面的两个副本。共享的方法是使这些相关进程的逻辑空间中的页面指向相同的内存块（该块中放有共享程序或数据）。图4-24示出了三个进程共享5#内存块中文本数据的情况。,图4-24 页面的共享,4.5 分 段 技 术,4.5.1 分段存储管理的基本概念 1.分段 通常，一个用户程序是由若干相对独立的部分组成的，各自完成不同的功能。如上所述，为了编程和使用的方便，我们希望把自己的程序按照逻辑关系加以组织，即划分成若干段，并按照这些段来分配内存。所以，段是一组逻辑信息的集合。例如，有主程序段MAIN、子程序段P、数据段D和栈段S等。如图4-25所示。,图4-25 分段地址空间,2.程序的地址结构 由于整个作业的地址空间分成多个段，所以，逻辑地址要用两个成分来表示：段号s和段内地址d。就是说，在分段存储情况下，作业的逻辑地址空间是二维的。分段系统中所用的地址结构如图4-26所示。,图4-26 分段技术的地址结构,3.内存分配 在分段存储管理中内存以段为单位进行分配，每个段单独占用一块连续的内存分区。各分区的大小由对应段的大小决定。这有些类似于动态分区分配方式。但是二者是不同的：在分段存储管理系统中，一个作业或进程可以有多个段，这些段可以离散地放入内存的不同的分区中。,4.段表和段表地址寄存器 同分页一样，为了能找出每个逻辑段所对应的物理内存中分区的位置，系统为每个进程建立了一个段映射表，简称“段表”。每个段在段表中占有一项。段表项中一般应包含以下内容：段号、段的长度、段在内存中的起始地址（又称“基址”）等。,5.分页和分段的主要区别 分页和分段存储管理系统有很多相似之处，例如，二者在内存中都不是整体连续的，都要通过地址映射机构将逻辑地址映射到物理内存中。但二者在概念上完全不同，主要有以下几点：（1）页是信息的物理单位。(2)页的大小是由系统固定的，即由机器硬件把逻辑地址划分成页号和页内地址两部分。,(3)分页的作业地址空间是一维的，地址编号从0开始顺次递增，一直排到末尾。因而只需用一个地址编号(如10000）就可确定地址空间中的惟一地址。,4.5.2 地址转换 段地址转换与分页地址转换的过程基本相同，其大致过程如图4-27所示。(1)CPU计算出来的有效地址分成两个部分：段号s和段内地址d。(2)系统将该进程段表地址寄存器中的内容B(表示段表的内存地址)与段号s相加，得到查找该进程段表中相应表项的索引值。,图4-27 分段地址转换,(3)将段内地址d与段长m进行比较。如果d不小于m，则表示地址越界，系统发出地址越界中断，进而终止程序执行；如果d小于m，则表示地址合法，从而将段内地址d与该段的内存始址s相加，得到所要访问单元的内存地址。,4.5.3 段的共享和保护 分段管理的一个优点是提供了对代码或数据进行有效地共享。为了共享某个段，只需在各个作业的段表中登记一项，使它们的基地址都指向同一个物理单元，如图4-28所示。,图4-28 分段系统中段的共享,段的保护措施有以下几种：(1)存取控制。（2）段表本身可起保护作用。（3）段表地址寄存器中段表长L起保护作用。（4）保护环。,4.6 虚 拟 存 储 器,4.6.1 虚拟存储器概念 作业在执行之前要全部装入内存，这种限制往往是不合理的，会造成内存的浪费。因为：（1）程序中往往含有不会被执行的代码，如对不常见的错误进行处理的代码。,（2）一般为数组、队列、表格等数据结构分配的内存空间要大于它们的实际需要。（3）一个程序的某些任选功能和特殊性能很少被使用，例如把某些行中所有的字符都转换成大写字符的正文编辑命令。,这样做会带来很多好处，起码有以下两点：（1）用户编制程序时可不必考虑内存容量的限制，只要按照实际问题的需要来确定合适的算法和数据结构，从而简化了程序设计的任务。（2）由于每个进程只有一部分装入内存，因而占用的内存空间就较少，在一定容量的内存中就可同时装入更多的进程，也相应地增加了CPU的利用率和系统的吞吐量。,4.6.2 虚拟存储器特征 对于虚拟存储器这一基本概念我们应从以下几个方面进行理解，这些也是虚拟存储器所具有的基本特征。(1)虚拟扩充。虚拟存储器不是物理上扩大内存空间，而是逻辑上扩充了内存容量。(2)部分装入。每个进程不是全部一次性地装入内存，而是分成若干部分。(3)离散分配。一个进程分成多个部分，没有全部装入内存。,(4)多次对换。在一个进程运行期间，它所需的全部程序和数据要分成多次调入内存。,4.7 请求分页技术,4.7.1 请求分页的基本思想 在简单分页存储管理系统中，每个进程的地址空间是连续的，而映像到存储空间后就不一定连续。就是说，页号连续而相应的块号不连续。利用这种办法，有效地解决了内存碎片问题，从而更好地支持多道程序设计，提高了内存和CPU的利用率。,4.7.2 硬件支持及缺页处理 1.页表机制 如上所述，分页系统中地址映射是通过页表实现的。在请求分页系统中，页表项不仅要包含该页在内存的基址，还要含有下列信息：（1）页表的每一项增加一个状态位，用来指示该页面是否在内存中。,（2）页表项中还要记载该页面在外存的地址（又称文件地址），以便在发生缺页情况下，操作系统能很快地在外存上找到该页面，换入内存。（3）在页表中还要增加一些位，用于记录该页的使用情况（如最近被引用过没有，该页的内容在内存中修改过没有等），帮助操作系统做出页面替换的决定。,2.缺页中断机构 在硬件方面，还要增加对缺页中断进行响应的机构。一旦发现所访问的页面不在内存，能立即产生中断信号，随后转入缺页中断处理程序进行相应处理。缺页中断的处理过程是由硬件和软件共同实现的。其相互关系如图4-29所示。,图4-29 指令执行步骤与缺页中断处理过程,4.7.3 请求分页的优缺点 分页技术的一个非常重要的性质是把存储器的用户观点和实际的物理存储器清晰地区分开。用户编制程序时认为存储器是一片连续的空间，其中只包括这一个程序。而实际上，用户程序被分散到物理存储器中，其中还有其他程序。二者之间的差别是通过地址转换机构（即映像硬件）统一起来的。映像对用户来说是隐蔽的，它受操作系统控制。,请求分页除了具有简单分页的优点之外，还有下列优点：（1）提供多个大容量的虚拟存储器。（2）更有效地利用了内存。（3）多道程序度更高了。,它除了硬件成本增加，用于对换与置换的时间与空间的开销增大，以及有内部碎片等缺点外，还添加了以下缺点：（1）对缺页中断的处理要占用较多的存储空间和CPU时间；（2）如每个进程的地址空间过大，或进入系统的进程数过多，则会发生系统抖动。,4.7.4 请求分页的性能 请求分页对计算机系统的性能可能产生重要影响。为说明这个问题，我们计算一下请求分页系统的有效存取时间。对多数计算机系统来说，内存存取时间ma一般为10200 ns，只要不出现缺页中断，有效存取时间就等于内存存取时间。如果发生了缺页中断，则首先必须从外存中读入该页，然后才能进行内存存取。,令p表示缺页中断的概率（0p1），简称缺页率，它等于缺页次数与全部访问内存次数之比。我们希望p与0越接近越好，这样就仅有很少的缺页中断发生。有效存取时间是：有效存取时间=（1-p）ma+p缺页处理时间 为了算出有效存取时间，必须知道处理缺页中断所需的时间。缺页导致以下的一系列动作（设当前进程为A）：,（1）捕俘进入操作系统。（2）保存A的各寄存器和进程状态信息。（3）确定该中断是缺页引起的。（4）检查对该页的访问是合法的，并确定该页在磁盘上的地址。（5）将该页从磁盘读到空闲块中：在设备队列中等待，直至该请求得到服务；等待设备寻道和/或旋转延迟时间；开始传送该页到空闲块。,（6）在等待时间内，可把CPU分给其他进程（由CPU调度程序执行），例如B。（7）收到来自磁盘的中断（I/O完成）。（8）为正在运行的进程B保存寄存器和程序状态。（9）确定该中断是来自磁盘的I/O中断。（10）调整页表和其他表格，说明所需页面已在内存。（11）等待重新把CPU分给进程A。（12）恢复该进程各寄存器、进程状态和新的页表，然后重新开始被中断的指令。,并不是在所有情况下都需要上述各步，但以下三个主要工作是必须要做的：（1）处理缺页中断；（2）调入该页；（3）重新启动该进程。,如果把平均缺页服务时间取为25 ms，内存存取时间取为100 ns，那么 有效存取时间=（1-p）100+p25 ms=(1-p)100+25 000 000p=100+24 999 900p,可以看出，有效存取时间直接正比于缺页的比率。如果缺页率为千分之一，则有效存取时间是25 s，计算机速度因请页而降低到原来的1/250。如果期望下降率不超过10%，则有：110100+25 000 000p 10 25 000 000p p 0.000 000 4,4.7.5 页面置换 由图4-29可以看出，如果被访问的页不在内存时，则产生缺页中断。操作系统进行中断处理，把该页从外存调入内存。那么新调进的页到底放在什么地方呢？如果内存中有空闲块，则可把该页装入任何空闲块中，调整页表项及存储分块表。如果当前内存空间已装满，那么该页放到哪里去呢？此时必须先淘汰已在内存的一页，腾出空间，再把所需页面装入。其工作流程如图4-30所示。,它主要包括以下几个步骤：（1）在磁盘上寻找所需页面。（2）寻找空闲块：如果有空闲块，就用它；否则，就利用页面置换算法选择一个替换的块；把该块写到磁盘上，并相应地修改页表和存储块表。（3）把所需页面读入内存（刚刚得到的空闲块），修改页表和存储块表。（4）重新启动该用户进程。,图4-30 页面置换过程,4.8 页面置换算法,为减少数据的数量，我们要注意到下面两件事。第一，对于给定的页面大小（通常由硬件或者系统来确定），我们仅考虑其页号，不关心完整的地址。第二，如果对面页p进行了访问，那么随后立即进行的对p的访问不会缺页。这样，如果我们追踪特定程序，记下下述地址序列：,0100,0432,0101,0612,0102,0103,0104,0101,0611,0102,0103,0104,0101,0610,0102,0103,0104,0101,0609,0102,0105 若每页100个字节，则页面走向缩减为：1,4,1,6,1,6,1,6,1,6,1,图4-31 缺页量与块数的关系图,4.8.1 先入先出法（FIFO）对给定的页面走向，有三个内存块最初是空的（如图4-32所示）。前面三个页面访问（7，0，1）导致缺页，被放入这三块中。下面的访问（2）要置换页面7，因为它是最先进入的。接着是对页面0的访问，由于它已在内存，所以不发生缺页。这样顺次地做下去，就产生如图4-32所示的情况。每出现一次缺页，我们就示出置换后的情况，总共有15次缺页。,图4-32 FIFO页面置换,FIFO页面置换算法容易理解和进行程序设计。然而它的性能并非总是好的。这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。大家可分析一下页面走向是下述情况时（三个内存块可用）：1，2，3，4，1，2 5，1，2，3，4，5 页面置换的过程。,FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了，如图4-33所示。当然，导致这种异常现象的页面走向实际上是很少见的。,图4-33 关于一个页面走向的FIFO置换算法的缺页曲线,4.8.2 最优置换算法（OPT）最优置换（Optimal Replacement）是1966年由Belady在理论上提出的一种算法。其实质是：当调入新的一页而必须预先置换某个老页时，所选择的老页应是将来不再被使用，或者是在最远的将来才被访问。采用这种页面置换算法，保证有最少的缺页率。例如，对于上面给定的页面走向来说，最优页面置换算法仅出现9次缺页中断，如图4-34所示。,图4-34 最优页面置换,4.8.3 最久未使用算法（LRU）最优置换算法在实际中行不通，但可以找到与它接近的算法。回想一下，FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（LRU），如图4-35所示。,图4-35 LRU页面置换算法,LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。这就是OPT算法在时间上向后看，而不是向前看的情况。在图4-35的示例中，应用LRU算法产生12次缺页。其中前面5次缺页情况是与OPT算法一样的。,LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：（1）计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。,（2）栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页（如图4-36所示）。,图4-36 利用栈记录目前访问最多的页面,图4-37 LRU近似算法,4.8.4 第二次机会算法（SCR）第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0，如图4-38所示。,图4-38 第二次机会置换算法(a)开始时；(b)选中时,4.9 内存块分配算法和抖动问题,4.9.1 内存块分配算法 一旦选定了置换算法，我们就可以考虑内存管理的灵活性。带虚拟存储器的最简单的情况是单用户系统。整个内存，除操作系统占用的空间之外，余下部分全部给一个用户程序。,1.最少内存块数 分配给进程的内存块数目是受到限制的，分配的总块数不能超出可用块的总量（除非存在页共享的情况）。另一方面，每个进程也需要有起码最少的块数。,2.固定分配和可变分配 请求分页系统支持虚拟存储器。在这种系统中没有必要、也不可能在一个进程运行之前就把它的所有页面都装入内存。（1）固定分配策略是分配给进程的内存块数是固定的，并在最初装入时（即进程创建时）确定块数。（2）可变分配策略允许分给进程的内存块数随进程的活动而改变。,3.全局置换与局部置换 内存块分配的另一个重要问题是页面置换范围。多个进程竞争内存块时，可以把页面置换分成两种主要类型：全局置换和局部置换。全局置换允许一个进程从全体存储块的集合中选取置换块，尽管该块当前已分给其他进程，但还是能强行剥夺。而局部置换是每个进程只能从分给它的一组块中选择置换块。采用局部置换策略，分给进程的块数是不能变更的。,4.内存块分配算法 为每个进程分配内存块的算法主要有三种：等分法、比例法和优先权法。1）等分法 为每个进程分配存储块的最简单的办法是平分，即若有m块、n个进程，则每个进程分m/n块（其值向下取整）。,2）比例法 设进程pi的地址空间大小为si，则全部进程的总地址空间为 S=si 若可用块的总数是m，则分给进程pi的块数是ai,ai近似等于,当然，ai必须是整数，大于所需最少块数，且总 数不超过m。,3）优先权法 应注意到，在上面两种算法中没有考虑优先级问题，即把高优先级进程和低优先级进程一样对待。,4.9.2 抖动（Thrashing）问题 置换算法的优劣，直接影响到系统的效率。若选用算法不合适，可能会出现这种现象：刚被置换出去的页，很快又要访问它，因而要把它重新调入；可是调入不久又再次被置换出去，这样再访问、再调入，如此反复，使得整个系统的页面替换非常频繁，以致大部分的机器时间都花在来回进行的页面调度上，只有一小部分时间用于进程的实际运算。这种局面就称为系统“抖动”。,产生抖动的原因是系统中多道程序度过高，进程运行缺页率严重。一般情况下，在多道程序度较小时，随着它的增加，CPU利用率会缓慢增加。当到达最大值以后，多道程序度进一步增大，就出现了抖动，导致CPU利用率急剧下降，如图4-39所示。,图4-39 CPU利用率与多道程序度的关系,防止抖动发生或者限制抖动影响的方法有多种，但一般都基于调节多道程序度。（1）采用局部置换策略。（2）利用工作集策略防止抖动（详见4.9.3节）。（3）挂起某些进程。当出现CPU利用率很低、而磁盘I/O非常频繁的情况时，就可能因为多道程序度太高而造成抖动。（4）采用缺页频度法（PFF，Page Fault Frequency)。,4.9.3 工作集 局部化可分为两类：时间局部化和空间局部化。时间局部化是指一旦某条指令或数据被访问了，它常常很快又被再次访问。这是大多数程序所具有的性质，例如程序中的循环部分、常用的变量和函数等。空间局部化指的是一旦某个位置被访问到，那么它附近的位置也可能很快要用到。,Denning于1968年提出了工作集理论来研究和描述这种局部性。所谓工作集，就是一个进程在某一小段时间内访问页面的集合。如用WS(ti)表示在ti-ti之间所访问的不同页面，那么它就是进程在时间ti的工作集，如图4-40所示。,图4-40 工作集模型,工作集最重要的性质是它的大小。工作集越小，则程序局部性越好。如果我们计算出系统中每个进程的工作集大小WSSi，那么,4.10 段式虚拟存储器,4.10.1 基本工作过程 在段式虚存系统中，一个进程的所有分段的副本都保存在外存上。当它运行时，首先把当前需要的一段或几段装入内存，其他段仅在调用时才装入。其过程一般是：当所访问的段不在内存时，便产生缺段中断，操作系统接到中断信号后，进行相应处理，按类似于申请分区的方式，在内存中找到一块足够大的分区，以便放入所需分段。,采用段式虚存系统，可以便于动态连接，就是说只有用到某个分段时，才连接它，从而避免不必要的连接。为支持动态连接要附加两个硬件设施：间接编址和连接故障指示位。这是MULTICS系统中采用的方法。间接编址是指令中地址部分，它不是存取数据的直接地址，而是间接地址，即存放这个直接地址的那个单元的地址。包含该直接地址的字称为间接字。连接故障指示位设在间接字中，用于表示所访问的段号是否已连接上。间接编址与直接编址的区别如图4-41所示。,图4-41 直接编址与间接编址(a)直接编址；(b)间接编址,4.10.2 连接中断处理 如图4-42(a)所示，程序MAIN中有一条指令LOAD*1，3|100，这是间接编址形式，它从本段的100号单元中得到间接字。由于连接位置为1，因此产生连接中断信号。于是操作系统得到控制，执行连接中断处理程序，根据间接字中的地址3|108，找到段X。文件系统可以根据这个段名找到它的全部信息，然后为X段分配一个段号，例如4(按段表的序号)。,再根据Y找到它的位移量，例如200，然后修改间接 字，将连接位清0，其中地址部分改为连接后的直接地址，即4|200。这时连接工作完成。控制重新转向被中断的指令LOAD*1，3|100，继续执行下去。连接后的情况如图4-42(b)所示。,图4-42 段的动态连接(a)指令执行之前；(b)X段连接之后,4.10.3 段式虚拟存储的优点和缺点 从上面分析可以看出，采用分段技术有利于用户对程序地址空间的了解，便于对各个程序段的共享和保护。此外，段式虚拟存储系统还有下列优点：(1)允许用户地址空间大于实际内存空间，为多道程序运行提供了有力的支持。(2)便于动态连接，从而可避免静态连接所造成的某些时间和空间的浪费。,但段式虚拟存储仍有不少缺点，除具有与请页式系统相同的缺点(如提高硬件成本，增加软件的时间、空间开销以及系统复杂性等)外，还有以下缺点：(1)在外存中管理可变尺寸的分段有不少困难；(2)每个分段的大小受内存容量的限制；(3)对分段的置换，有可能造成系统抖动。,4.11 段页式结合系统,分页和分段方式各有优点和缺点，将二者结合起来可以取长补短，提高性能。最常用的方式是段页式，其基本思想是：（1）程序地址表示由三部分组成：段号s、页号p和页内位移d，即v=(s,p，d)。这样，面向用户的地址空间是段式划分,而面向物理实现的地址空间是页式划分。,(2)地址转换过程是：每个进程有一个段表，每段都有单独的一个页表。每段受段表项中段长度的限制，这样页表不必全部填满，实际需要多少就开辟多少表项。另外，每段的最后一页不一定是满的，平均起来每段有半页大小的内部碎片。利用段号去查段表，得到该段的页表的起始地址；利用这个地址和页号去查页表，得到相应的块号。最后，块号和页内位移拼接在一起，形成访问内存地址，如图4-43所示。,图4-43 段页式系统的地址转换机构,4.12 Linux系统的存储管理,4.12.1 Linux的多级页表 在x86平台的Linux系统中，地址码采用32位，因而每个进程的虚存空间可达4 GB。Linux内核将这4 GB的空间分为两部分：最高地址的1 GB是“系统空间”，供内核本身使用；而较低地址的3 GB是各个进程的“用户空间”。,系统空间由所有进程共享。虽然理论上每个进程的可用用户空间都是3 GB，但实际的存储空间大小要受到物理存储器(包括内存以及磁盘交换区或交换文件)的限制。进程的虚存空间如图4-44所示。,图4-44 Linux进程的虚存空间,由于Linux系统中页面的大小为4 KB，因此进程虚存空间要划分为1 M个页面。如果直接用页表描述这种映射关系，那么每个进程的页表就要有1 M个表项。很显然，用大量的内存资源来存放页表的办法是不可取的。为此，Linux系统采用三级页表的方式，如图4-45所示。,图4-45 三级页表地址映射示意图,把一个线性地址映射成物理地址就分为以下四步：(1)以线性地址中最高位段作为下标在PGD中找到相应的表项，该表项指向相应的PMD。(2)以线性