第五章存储管理

第5章存储管理

存储管理是指计算机的主存管理。主存是计算机硬件中除CPU之外的又一个宝贵的资源。存储管理要具备下列功能（见1.2.2节P6）内存分配

地址映射：把程序中的逻辑地址映射为物理地址

内存保护：使多道程序间互不干扰内存扩充：用辅存扩充主存，实现“虚拟存贮器”

本章内容提要5.1引言5.2分区法5.3分页技术5.4分段技术5.5段页式技术5.6虚拟存储器5.7请求分页技术5.8页面置换算法5.9内存块的分配和抖动问题5.10请求分段技术5.11Linux系统的存储管理内存储器（简称内存、主存、物理存储器）处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。外存储器（简称外存、辅助存储器）处理机不能直接访问的存储器。用来存放用户的各种信息，存取速度相对内存而言要慢得多，但它可用来长期保存用户信息。在文件系统中介绍。复习：存储器管理的相关概念5.1引言内存（MainMemory或PrimaryMemory或RealMemory）也称主存，是指CPU能直接存取指令和数据的存储器。图5-1内存在计算机系统中的地位用户程序的主要处理阶段 （见下页图）

1．编辑阶段4．装入阶段

2．编译阶段5．运行阶段

3．连接阶段

连接就是将编译或汇编后得到的一组目标模块及它们所需的库函数装配成一个完整的装入模块的过程。

5.1.1用户程序的地址空间4．装入阶段用户程序经编译之后的每个目标模块都以0为基地址顺序编址，这种地址称为相对地址或逻辑地址；内存中各物理存储单元的地址是从统一的基地址开始顺序编址的，这种地址称为绝对地址或物理地址。程序装入内存的方式有以下三种：①绝对装入方式②可重定位装入方式③动态运行时装入方式5．运行阶段

建立进程并执行，得到运行结果5.1.2重定位由程序中逻辑地址组成的地址范围叫做逻辑地址空间，或简称为地址空间；由内存中一系列存储单元所限定的地址范围称做内存空间，也称物理空间或绝对空间。程序和数据装入内存时，需对目标程序中的地址进行修改。这种把逻辑地址转变为内存物理地址的过程称做重定位

按重定位的时机，重定位技术可分为静态重定位和动态重定位。1．静态重定位静态重定位是在目标程序装入内存时，由装入程序对目标程序中的指令和数据的地址进行修改，即把程序的逻辑地址都改成实际的内存地址。图5-4静态重定位示意图2．动态重定位：

现在的计算机系统都采用动态重定位方法动态重定位是在程序执行期间，每次访问内存之前进行重定位。这种变换是靠硬件地址转换机构实现的。图5-5动态重定位示意图5.1.3对换技术对换的定义把内存中暂时不能运行的进程或暂时不用的程序和数据，换出到外存上，以便腾出足够的内存空间，把已具备运行条件的进程或进程所需要的程序和数据，换入内存。若对换是以整个进程为单位，称为整体对换（进程对换），用于分时系统中；对换以“页”或“段”为单位，称为页面对换（分段对换，部分对换），用于虚拟存储系统。图5-6对换两个进程示意图图5-7多道程序对换技术示例5.2分区法分区分配是为支持多道程序运行而设计的一种最简单的存储管理方式。按照分区的划分方式，可分为：固定分区法可变分区法5.2.1固定分区法固定分区就是内存中分区的个数固定不变，各个分区的大小也固定不变，每个分区只可装入一个进程。1．分区的大小划分分区大小有两种方式：各分区大小相同——等分方式不同分区大小不同——差分方式固定分区(大小相同)固定分区(多种大小)2．内存分配为便于内存分配，系统建立一张分区说明表。内存的申请和释放都根据分区说明表进行。最简单的多道程序存储管理方式分区大小和个数在系统生成时确定内存利用率不高，已很少使用，主要应用于控制系统中5.2.2动态分区法即可变分区分配1．分区的分配各分区在进程进入内存时建立，使其大小适应进程的大小。这种技术称为动态分区法。如IBM的OS/360MVT内存分配与回收图5-7表示MVT的内存分配和进程调度示例图5-10MVT的内存分配和进程调度情况2．数据结构为实现分区分配，系统要设置相应的数据结构记录内存的使用情况，常用的数据结构有：（1）空闲分区表为内存中每个空闲分区设置一个表项，包含分区序号、分区始址、分区大小、状态等数据项。（2）空闲分区链利用前、后指针将所有分区链成一个双向链，在每个分区尾部重复设置状态位、分区大小表目。3．分配算法（1）最先适应算法（First-fit）空闲分区以地址递增的次序排列特点：（1）优先利用低址区，保留了高址部分的大空闲区。（2）低址部分不断被划分，留下许多难以利用的小空闲区（3）因每次都从低址部分查起，故查询开销大。空闲区按地址递增的次序链接（2）最佳适应算法（Best-fit）空闲表是以空闲块的大小为序、按增量形式排列的，即小块在前，大块在后。特点：（1）避免“大材小用”（2）分配后切割下的剩余部分难以再次利用以容量大小递增的次序链接（3）循环适应算法（Next-fit）最先适应算法的变种。它不从空闲表的开头查找，而从上次找到的可用分区的下一个空闲分区开始查找，从中选择满足大小要求的第一个空闲分区。特点：（1）为循环查找方法设置一起始查找指针。（2）使空闲分区分布得更均匀。（3）缺乏大的空闲分区。分配16KB内存块之前和之后的内存配置内存中这种容量太小、无法利用的小分区称做“碎片”或“零头”。在一个分区内部出现的碎片（即被浪费的空间）称做内部碎片，如固定分区法会产生内部碎片。在所有分区之外新增的碎片称做外部碎片.—依据碎片出现的位置4.碎片问题5.2.3可重定位分区分配1、紧缩解决碎片问题移动某些已分配区的内容，使所有进程的分区紧挨在一起，而把空闲区留在另一端。这种技术称为紧缩（或拼凑）。小空闲分区拼接成大分区的方法紧凑后程序、数据须进行重定位（采用动态重定位技术）。采用紧缩法消除碎片，要花费大量CPU时间图5-13可重定位分区的紧缩什么时候进行紧缩呢？有两种不同的方案。第1种方案是当进程结束、释放所占用的分区时如果它不与空闲区邻接，就立即执行紧缩。第2种方案是在分配进程的分区时进行，各个空闲分区都不能满足该进程的需要时进行紧缩。2.动态重定位的实现过程动态重定位经常用硬件实现。硬件支持

基址寄存器：存放用户程序在内存中的起始地址限长寄存器：存放用户程序逻辑地址的最大范围动态重定位的实现过程如图5-11所示动态重定位的实现过程3.可重定位分区法的优缺点优点是可以消除碎片，能够分配更多的分区，有助于多道程序设计，提高内存的利用率。它的缺点是：紧缩花费了大量CPU时间；当进程大于整个空闲区时，仍要浪费一定的内存；进程的存储区内可能放有从未使用的信息；进程之间无法对信息共享。5.3分页技术连续分配方式会形成许多“碎片”，“紧凑”操作的开销又较大。采用离散分配方式可以将一个进程直接分散地装入到许多不相邻接的分区中而不必再进行“紧凑”，解决碎片问题，提高了内存利用率。根据离散分配时所用基本单位的不同，可将其分为以下三种：

１、分页存储管理

用户的地址空间被划分为若干个固定大小

的区域，称为“页”。将内存空间分成若干个物理块，页和块的

大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配，每个用户程序在内存中的碎片大小不会超过一页2、分段存储管理

把用户程序的地址空间分成若干个大小不等的段，每段定义一组相对完整的逻辑信息，进行存储分配时，以段为单位，这些段在内存中可以不邻接3、段页式存储管理

分页、分段两种管理方式的结合，同时具备两者的优点。既提高了存储器的利用率，又满足用户要求，是目前使用较多的存储管理方式。5.3.1分页存储管理的基本概念（1）逻辑空间分页将一个进程的逻辑地址空间分成若干大小相等的部分，每个部分称作页面或页。编号从0开始（2）内存空间分块将内存空间分成与页相同大小的若干个存储块，称为内存块或页框页面（或块）的大小是由硬件（系统）确定。（3）逻辑地址表示由页号和页内地址组成页号p页内地址d0111231其中:0～11位为页内地址，表示每页的大小为212，即4KB；12～31位为页号，表示地址空间中最多可容纳220=1M个页面。地址计算已知逻辑地址A，计算页号p和页内地址dp=INT(A/L),d=AMODL，L为页面大小

若逻辑地址Ａ＝2170Ｂ页面大小Ｌ＝１KB

则p＝INT［Ａ／Ｌ］＝２

d＝［Ａ］MODL＝122（4）内存分配原则系统以块为单位把内存分给各个进程进程的每个页面对应一个内存块，并且一个进程的若干页可以分别装入物理上不连续的内存块中。离散分配系统为每个进程建立一张页面映射表，简称页表。A、在进程地址空间内的所有页（0~N），依次在页表中有一页表项，记录了相应页在内存中对应的物理块号。B、进程执行时，通过查找页表，可找到每页在内存中的物理块号，实现了从页号到物理块号的地址映射。页表的作用（5）页表（6）内存块表整个系统有一个内存块表。每个内存块在内存块表中占一项，表明该块当前空闲还是已分出去了。如果已分出去，是分给哪个进程的哪个页面了。进程访问某个逻辑地址中的数据时，分页地址变换机构自动地将逻辑地址分为页号和页内地址（p,d）。借助于页表，将逻辑地址中的页号转换为内存中的物理块号物理块号和页内地址送入物理地址寄存器中，拼接成实际内存地址5.3.2分页系统中的地址映射图5-17分页系统的地址转换机构分页技术不存在外部碎片，只存在内部碎片每个进程平均有半个页面的内部碎片

页面的大小由机器的地址结构决定。选择页面较小：内存碎片小，减少碎片的总空间，提高了内存的利用率。每个进程要求的页面多，导致页表过长，占用内存多，降低页面对换的效率。选择页面较大：减少页表长度，提高对换效率，页内碎片增大。页面的大小是2的幂，常在29~212之间，即在512字节~4KB之间。5.3.3页面尺寸页表功能的实现：2种方法①使用一组专门的寄存器：一个页表项用一个寄存器，可通过高速寄存器提高地址变换的速度。寄存器成本较高，适于较小系统中②将页表驻留在内存：由一个页表基址寄存器PTBR指向该页表。整个系统只有一个PTBR。进程未执行时，指向页表的指针存放在本进程的PCB中，进程执行时将其装入到PTBR中。5.3.4硬件支持内存中放置页表带来存取速度下降的矛盾。利用页表存取数据时要两次访问内存：第一次：访问页表，完成地址转换。第二次：利用地址获取数据。这样，使计算机的处理速度降低1/2。快表（或TranslationLookasideBuffer,TLB）。快表每项包括键号和值两部分，键号是当前进程正在使用的某个页面号，值是该页面所对应的物理块号。图5-18利用快表实现地址转换示例转换过程：在CPU给出有效地址后，由地址变换机构自动地将页号p送入高速缓冲寄存器，并将此页号与高速缓冲存储器中的所有页号进行比较，若其中有与此相匹配的页号，则表示要访问的页表项在快表中。这样，可直接读出该页所对应的物理块号，并送到物理地址寄存器中。若在快表中未找到对应的页表项，还需再访问内存中的页表，找到后，把从页表项中读出的物理块号送地址寄存器；同时，还将此页表项存入快表中的一个寄存器单元中，即重新修改快表。若快表存已满，则OS淘汰最老且已被认为不再需要的页表项。

反映快表使用效果的概念——命中率。命中率：反映了在快表中的进程页表占该进程总页表数的百分比。对于大型作业而言，不可能把全部页表放入快表中例：检索快表的时间为20ns，访问内存的时间为100ns。①若能在快表中找到CPU给出的页号，则存 取一个数据所需时间：t1=100+20=120ns

②若不能在快表中找到该页号，则存取一个数据所 需时间：t2=100+20+100=220ns5.3.5保护方式分页系统提供的存储保护方式有三种：（1）利用页表本身进行保护页表基址信息放在进程PCB中页表长度寄存器PTLR（2）设置存取控制位R、RW、RX（3）设置合法标志在页表的每项中设置合法/非法位。5.3.6页表的构造多级页表散列页表倒置页表1．多级页表问题提出：一个具有32位逻辑地址空间的分页系统，规定页面大小为4KB，则每个进程页表项可达1M个，且每个页表项占用4个字节。因此每个进程仅页表就要占4MB的内存空间，而且还要求是连续的。解决方法：（1）对页表所需内存空间采用离散分配方式，来解决难以找到一块连续的大内存空间的问题。（2）只将当前需要的部分页表项调入内存，其余的页表项放在磁盘上，需要时再调入内存。页号p页内地址d0111231图5-19两级页表地址结构示意图

采用页表分页的方法，使每个页面的大小与内存物理块的大小相同，并为它们编号，这样可离散地将各个页面分别存放在不同的物理块中；同样为离散分配的页表再建立一张页表（称外层页表—

OuterPageTable），在每个页表项中记录了页表页面的物理块号。图5-20两级页表结构示意图图5-21两级页表结构的地址转换图5-22三级页表地址结构示意图32位的机器：两级页表结构

64位的机器：四级页表2．散列页表处理32位地址空间的通用方式是使用散列页表HashedPageTable，以页号作为参数形成散列值。散列表中每一项有一个链表，它把有相同散列值的元素链接起来。每个链表元素由三部分组成：①页号；②对应的内存块号；③指向链表中下一个元素的指针。

图5-23散列页表构成及地址转换过程它是按内存块号排序的，每个内存块占有一个表项。每个表项包括存放在该内存块中页面的页号和拥有该页面的进程标识符。倒置页表减少页表占用的内存，增加了检索页表时消耗的时间3．倒置页表图5-24倒置页表构成及地址转换过程共享页面，有效节省内存空间。(见下页图)相关进程的逻辑空间中的页指向相同的内存块(该块中放有共享程序或数据)要求可共享的代码必须是可再入代码（或纯码，在其执行过程中本身不做任何修改的代码，通常由指令和常数组成）。数据页面往往不能共享。5.3.7页面共享图5-25页面共享示例分页系统中实现页的共享比较困难，因为分页系统中把作业或进程的地址空间划分成页面的做法对用户是屏蔽的。（用户不知道作业分了多少页和每页的界限）引入原因：为了满足用户（程序员）在编程和使用上的多种要求,有些要求是其它几种存储管理方式难以满足的。用户在编程和使用上的五种要求方便编程信息共享信息保护动态链接动态增长5.4分段技术5.4.1分段存储管理的基本概念1．分段用户的逻辑地址空间划分为若干段，每个段定义了一组逻辑信息，每个段都有自己的名字——段名（通常用一个段号代替），段的长度由相应的逻辑信息组的长度决定。每个段都从0开始编址，并采用一段连续的地址空间。图5-26分段地址空间示例作业的逻辑地址空间：分段情况下要求每个作业的地址空间按照程序的自然逻辑关系分成若干段，每个段有自己的段名。2．程序的地址结构逻辑地址要用两个成分来表示：段号s和段内地址d。在分段存储情况下，进程的逻辑地址空间是二维的。以上结构允许一个作业最多有216(64K)个段，每段最大长度为216=64KB。3．内存分配内存以段为单位进行分配，每段单独占用一块连续的内存分区。各分区的大小由对应段的大小决定。各段是离散分配于不同的区域4．段表和段表地址寄存器系统为每个进程建立一个段映射表，简称“段表”。每个段在段表中占有一项，段表项中包含段号、段长和段起始地址（又称“基址”）等段表实现了逻辑段到物理内存区的映射系统还要建立一个段表地址寄存器，它有两部分：一部分指出该段表在内存的起始地址；另一部分指出该段表的长度。5．分页和分段的主要区别相同之处：都采用离散分配方式；都要通过地址映射机构来实现地址变换。

不同之处：①页是信息的物理单位，段是信息的逻辑单位。②页的大小是由系统确定的，段的长度因段而异，由用户决定③分页的进程地址空间是一维的，分段的进程地址空间是二维的。④分页系统很难实现过程和数据的分离，分段系统却可以很容易实现这些功能。5.4.2地址转换图5-28分段地址转换过程与分页系统一样，通过段表访问一个数据需两次访问内存为提高访问速度，亦可增设一个快表，用于保存最近常用的段表项5.4.3段的共享和保护1．段的共享分段管理的一个优点是提供对代码或数据的有效共享。共享是在段一级实现的，任何共享信息可以单独成为一段。也可以只共享部分程序。图5-29分段系统中段的共享2．段的保护：分段管理的另一个优点段的保护措施包括以下三种：①存取控制在段表表项中设置存取控制字②段表本身可起保护作用。表项中设置该段的长度限制－段长段表地址寄存器中有段表长度的信息。③保护环（一种较完善的存取控制机制）低编号的环具有高优先权（１）一个程序可以访问驻留在相同或较低特权环中的数据。（２）一个程序可以调用驻留在相同或较高特权环中的服务。

程序间的控制传输数据访问程序调用和数据访问的关系：

5.5段页式技术

集中了分页、分段系统的优点。既有分段系统便于实现、分段可共享、易于保护、可动态链接等优点，又能象分页系统可很好地解决内存碎片问题，并可为各段离散地分配内存。5.5.1段页式存储管理的基本原理将用户程序先分段，每段赋予一个段名，再将每个段分页内存分成大小相等的块逻辑地址由段号s、页号p和页内地址d组成。为实现地址变换，系统为每个进程设置段表和页表。段表的内容为：页表始址和页表长度段表地址寄存器：指出进程的段表长度和段表始址5.5.2地址转换过程图5-31段页式系统的地址转换机构段页式系统中，为了获得一条指令或数据，需三次访问内存：1）访问内存中的段表，取得页表始址；2）访问内存中的页表，取得该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；3）从第二次访问所得地址中，取出指令或数据。为了提高速度，可在地址变换机构中设置一高速缓冲寄存器（快表）前面讲的各种存储管理方式，都要求将一个作业全部装入内存方能运行，因此可能出现这样的情况:第一、有的作业很大，不能一次性全部装入内存；第二、大量作业需运行，不能同时装入内存，只能将少数作业先装入，多数作业留在外存上。如何解决？5.6虚拟存储器进程在执行之前要全部装入内存，这种限制不合理：①程序中往往含有不会被执行的代码。②分配的内存空间会大于它们的实际需要。③一个程序的某些选项和特性可能很少使用。程序的执行过程也显示出局部性。分别调入内存。至少会带来如下两点好处： ①用户编制程序时不必考虑内存容量的限制 ②在一定容量的内存中就可同时装入更多的进程5.6.1虚拟存储器的概念VirtualMemory是用户能作为可编址内存对待的虚拟存储空间，它使用户逻辑存储器与物理存储器分离，是操作系统给用户提供的一个比真实内存空间大得多的地址空间。物质基础是二级存储器结构和动态地址转换机构（DAT）。虚拟存储器实质上是把用户地址空间和实际的存储空间区分开来。虚拟存储器的容量主要受到两方面的限制：①指令中表示地址的字长。②外存的容量。１、请求分页系统：在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统

置换时以页面为单位。虚拟存储器的实现方法

——均建立在离散分配的基础上2、请求分段系统：在分段系统的基础上，增加了请求调段及分段置换功能后形成的段式虚拟存储系统。置换是以段为单位进行的。

5.6.2虚拟存储器的特征①虚拟扩充：从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量②部分装入：进程执行时，只需将当前要运行的那部分程序和数据装入内存，以后运行到其它部分时再从外存调入。③离散分配：在内存分配时采用离散分配方式④多次对换：即在进程运行期间，允许将那些暂不使用的程序和数据，从内存调至外存的对换区，待以后需要时再将它们从外存调至内存，也允许将暂不运行的进程调至外存，待它们重新具有运行条件时再调入内存。有效地提高了内存的利用率。虚拟存储：以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术。5.7请求分页技术5.7.1请求分页存储管理的基本思想请求分页存储管理技术是在单纯分页技术基础上发展起来的，二者的根本区别在于请求分页提供虚拟存储器。它的基本思想是：当一个进程的部分页面在内存时就可调度它运行；在运行过程中若用到的页面尚未在内存，则把它们动态换入内存。为了标示进程的页面是否已在内存，在每个页表项中增加一个标志位。

5.7.2硬件支持及缺页处理1．页表机制页表项通常包含下列5种信息：①内存块号。②标志位。这一位用来标示对应的页面是否已装入内存。如果该位是1，表示该表项是有效的，可以使用，即该页在内存中；如果该位是0，则表示该表项对应的页面目前不在内存中，访问该页会引起缺页中断。③保护位：规定该页的访问权限。④修改位和引用位。这两位用来记录该页的使用状况。⑤禁止缓存位：禁止该页被缓存。2．缺页中断机构图：指令执行步骤与缺页中断处理过程5.7.3请求分页技术的性能以有效存取时间说明令p表示缺页中断的概率（0≤p≤1），简称缺页率，它等于缺页次数与全部访问内存次数之比。有效存取时间可表示为：

(1-p)×ma+p×缺页处理时间

ma为内存存取时间，一般为10～200ns为了算出有效存取时间，必须知道处理缺页中断所需的时间。缺页导致以下一系列动作（设当前进程为A）：(1)捕俘进入操作系统。(2)保存进程A的各个寄存器和进程状态信息。(3)确定该中断是缺页引起的。(4)检查对该页的访问是合法的，并确定该页在磁盘上的地址。(5)把该页从盘上读到空闲内存块中。(6)在等待盘I/O完成时，把CPU分给其他进程（如进程B）。(7)盘I/O完成，发出盘中断。(8)保存进程B的用户寄存器和进程状态。(9)确定该中断来自磁盘。(10)调整页表和其他表格，标明所需页已放入内存。(11)进程A就绪，等待分配CPU。(12)调度到进程A，则恢复它的各寄存器、进程状态和新的页表，然后重新执行前面被中断的指令。并不是在任何情况下都要执行以上各步。在任何情况下，缺页中断处理所花费的时间主要有：①处理缺页中断的时间。②调入该页的时间。③重新启动该进程的时间。②项是将页面从盘上读到内存，花费的时间包括三部分：磁盘寻道时间（即磁头从当前磁道移至指定磁道所用的时间）旋转延迟时间（磁头从当前位置落到指定扇区开头所用的时间）数据传输时间典型磁盘的旋转延迟时间约为8ms，寻道时间约为15ms，传输时间是1ms。全部换页时间将近25ms。

如果把平均缺页服务时间取为25ms，内存存取时间取为100ns，那么有效存取时间

=(1-p)×100+p×25000000=100+24999900×p有效存取时间正比于缺页率，如果期望计算机性能下降率不超过10％，则有：

110＞100+25000000×p10＞25000000×pp＜0.0000004即缺页率不能超过千万分之四在请求分页系统中使缺页率保持在很低水平非常重要虚存管理的核心把选择换出页面的算法称为页面置换算法。一个进程在运行过程中，频繁地更换页面，将系统大部分时间花费在页面置换上，则称该进程发生了“抖动”（颠簸）不适当的算法可能会导致进程发生“抖动”。一个好的页面算法应避免“抖动”发生，即具有较低的页面更换频率。

5.8页面置换算法参见图：指令执行步骤与缺页中断处理过程5.8.1页面置换1．页面置换过程2．页面走向存储访问序列也叫页面走向。为减少算法计算量，进行如下简化：①对于给定的页面大小，仅考虑其页号，不关心完整的地址。②如果当前对页面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对特定的访问序列来说，为确定缺页数量和页面置换算法，还要知道可用的内存块数一般来说，随着可用块数的增加，缺页数将减少。图5-35缺页量与内存块数关系图为了说明下面的页面置换算法，统一采用下述页面走向：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

并且假定每个作业只有三个内存块可供使用。5.8.2先进先出法（FIFO）出现最早的算法总是淘汰在内存中停留时间最长（年龄最老）的一页，即先进入内存的页，先被换出。图5-36FIFO页面置换序列共发生12次页面置换（15次缺页中断）FIFO页面置换算法的优点是容易理解且方便程序设计。然而，它的性能并不很好。FIFO页面置换算法的另一个缺点是存在Belady异常现象，即缺页率随内存块增加而增加。图5-37关于一个页面走向的FIFO淘汰算法的缺页曲线5.8.3最佳置换法（OPT）最佳置换算法（OptimalReplacement,OPT）其实质是：为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应在将来不被使用，或者是在最远的将来才被访问。因以上限定的页面无法预知，故算法无法实现。但可作为标准去评价其他算法图5-38最佳页面置换产生第一次页面置换：因0将于第5次访问，1将于第14次访问，而7在第18次才需访问，故将7换出，调入2。共发生6次页面置换，9次缺页中断。

OPT算法示例：FIFO算法的依据是各个页面调入内存的时间，故性能较差。OPT算法依据今后使用页面的时间，性能最好，难于实现。LRU算法以“最近的过去”作为“不久将来”的近似实质是：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰。5.8.4最近最少使用置换法（LRU）LRU算法示例

共发生9次页面置换，12次缺页中断。最佳置换算法：向后看，依据以后各页的使用情况。最近最久未用算法：向前看，依据以前各页的使用情况页面的过去与未来的走向之间并无必然的联系，故两种算法并无实质性的关联。

LRU算法需要实际硬件的支持。实现时的问题是：怎样确定最后访问以来所经历时间的顺序。有以下两种可行的办法：①计数器每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器，每进行一次访问，该时钟加1。每当访问一个页面时，时钟寄存器的内容被复制到相应页表项的使用字段中。选择时间值最小的页面为淘汰页。②栈：保存当前使用的各页面的页面号。

A、

系统为每个进程配置一个页面使用栈。

B、当进程访问某页时，将该页面的页面号从栈中移出，压入栈顶。这样栈顶始终是最新被访问页面的编号，而栈底所存的页号即是最近最久未使用的。图5-40利用栈记录目前访问最多的页面示例5.8.5第二次机会置换法（SCR）第二次机会置换法（SecondChancePageReplacement,SCR）是对FIFO算法的改进——

避免把经常使用的页面置换出去。当选择某一页面置换时，就检查最老页面的引用位：如果是0，就立即淘汰该页；如果该引用位是1，就给它第二次机会，将引用位清0，并放入页面链表末尾，并把它的装入时间重置为当前时间，然后选择下一个FIFO页面。图5-41第二次机会法示例如果所有的页面先前都被访问过，即它们的引用位都为1，那么，该算法就降为FIFO算法。5.8.6时钟置换法（Clock）1．简单时钟置换法将所有页面都链成一个环状链表，用一个指针指向最老的页面。当缺页时，检查指针指向的页面，若引用位是0则淘汰该页，若为1，则清0，把指针前移一个位置。图5-42时钟置换法示意图该算法又称最近未使用置换法（NotRecentlyUsed,NRU）2．改进的时钟置换法首选淘汰页的条件

未使用过的页面未被修改过的页面四种类型的页面（由页表中页面引用位、修改位）

00：最近既未被访问，也未被修改，是最佳淘汰页；01：最近未被访问，已修改，并不是很好的淘汰页；10：最近访问过，未修改，有可能再被访问的页；11：最近访问过，已修改，有可能再被访问的页。改进型Clock算法的执行过程从指针所指示的当前位置开始，扫描循环队列，寻找00的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。注意：第一次扫描期间不改变引用位。

若第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找01的第二类页面，将所遇到的第一个这类页面作为淘汰页。注意：在第二轮扫描期间将所有经过的页面的引用位置为0。若第二步也失败，即未找到第二类页面，则将指针返回到开始位置，并将所有的访问位置0。然后，重复第一步，若仍然失败，必要时再重复第二步，此时必能找到被淘汰的页。5.8.7最少使用置换法（LFU）

LeastFrequentlyUsed，LFU为每个页面设置一个软件计数器，用于记载该页被访问的次数，初值为0。发生缺页时，淘汰其计数值最小的页。LRU：时间LFU：次数5.8.8页面缓冲算法（PageBuffering）

基本思想：

按照FIFO算法选择需要淘汰的页面，该被淘汰的页面将放入两个链表中的一个：若页面未被修改过，则将它放入空闲页链表，否则放入修改页链表。当修改页链表中被修改页面达一定数量时，再将它们一起（即成簇）写回到磁盘，以减少磁盘的I/O的操作次数，从而减少磁盘访问时间。自由页表和修改页表相当于页的Cache。被替换的页仍然保留在主存中。淘汰页不是在主存中发生物理移动，而只是将页表中的表项移动到空闲页链表和修改页链表。5.9内存块的分配和抖动问题5.9.1内存块的分配1．最少内存块数分给每个进程的最少内存块数是指保证进程正常运行所需的最少内存块数，它是由指令集结构决定的。2．内存块的分配①固定分配策略分配给进程的内存块数是固定的，且在最初装入时（即进程创建时）确定块数。②可变分配策略允许分给进程的内存块数随进程的活动而改变。页面置换范围全局置换允许一个进程从全体存储块的集合中选取淘汰块，尽管该块当前分配给其他进程，还是能强行占用。局部置换是每个进程只能从分给它的一组内存块中选择淘汰块。

可组合出以下三种适用的策略：

A、固定分配、局部置换

分配：为每个进程分配一固定数目的物理块，整个运行期间不再改变。置换：从该进程在内存的几个页面中选出一页换出。为每个进程分配多少个页面的内存难以确定：

太少：缺页中断增多，系统吞吐量小。

太多：驻留内存的进程数目减少，资源利用率低，对换时花费时间较多。

B、可变分配、局部置换

分配：系统为每个进程分配一定数目的物理块。置换：缺页时，从该进程内存页面中换出一页。若进程运行中频繁发生缺页中断，系统再为其增加若干附加的物理块，直至其缺页率减少到适当程度为止；若进程在运行过程中缺页率特别低，系统会适当减少分配给其的物理块，但不应引起其缺页率的明显增加。

C、可变分配、全局置换分配：系统为每个进程分配一定数目的物理块，OS