Memory Management

（1）要求理解的内容包括：程序处理与内存管理，分区存储管理及相关技术（拼凑、覆盖、对换、伙伴系统），分页/分段/段页式存储管理，虚拟存储技术，请求分页/分段存储管理，多级页表和反置页表，内存保护机制； （2）要求掌握的内容包括：分页/分段地址变换，页面淘汰算法设计实现及应用，请求分页/分段地址变换，动态分区存储管理设计与实现。

4.1 程序处理与内存管理

1. 程序处理

• 编译：由编译程序对用户源程序进行编译，形成若干个目标模块；

【2011】什么是链接？主要解决了什么问题？简述链接的主要类型及其优缺点。

【2020】什么是程序链接？解决了什么问题？

• 链接：由链接程序将编译后的一组目标模块以及他们所需要的库链接在一起，形成一个完整的装入模块；

• 静态链接方式：在程序运行之前，先将各目标模块及他们所需的库函数链接成一个完整的装配模块，以后不再拆开；

• 装入时动态链接方式：编译后的目标模块，在装入内存时，采用边装入边链接的链接方式；

• 运行时动态链接方式：对某些模块的链接推迟到程序执行时才执行。

• 装入：由装入程序将装入模块装入内存

• 绝对装入方式：产生绝对地址，可在编译或汇编时给出，或由程序员赋予；

• 可重定位装入方式：起始地址从0开始，其他地址相对于起始地址计算，逻辑地址与装入内存后的实际物理地址不同，需要修改；

• 动态运行时的装入方式：装入内存后，不立即把装入模块中的逻辑地址转换为物理地址，而是把这种地址转换推迟到程序真正要执行时才进行。

【2011】什么是重定位？为什么要重定位？ 装入时对目标程序中指令和数据的修改过程称为重定位，把逻辑地址转变为内存物理地址的过程。多道程序环境下，多个目标模块的起始地址通常从G开始，程序中其他地址都是相对于起始地址的，此时应采用可重定位方式，根据内存的当前情况，将装入模块装入到内存合适位置。

地址重定位的结果，是得到执行程序

1. 内存管理

存储管理的目的为以下5点：

• 主存分配与管理。当用户需要内存时，系统为之分配相应的存储空间，不需要时，及时回收内存以供其他用户使用。

• 提高主存储器的利用率。不仅能使多道程序动态地共享主存，提高主存利用率，最好还能共享主存中某个区域的信息。

• 扩充主存容量。为用户提供比主存物理空间大得多的地址空间，使用户感觉他的作业是在这样一个大的存储器中运行的。

• 存储保护。确保多道程序都在各自分配到的存储区域内操作，互不干扰，防止一道程序破坏其他作业或系统文件的信息。 基址寄存器：该作业所在分区的起始地址； 界限寄存器：分区的长度。 每个进程都有自己的地址空间，若进程运行过程中访问到了其地址空间之外的空间，则发生越界，需要界地址保护，通过硬件完成。

• 方便用户。

内存管理

物理内存管理

连续分配存储管理方式

单一连续

分区式

固定分区

动态分区

基于顺序搜索

基于索引搜索

动态可重定位

覆盖技术

对换技术

离散分配存储管理方式

分页存储

分段存储

段页式存储

虚拟内存管理

请求分页存储管理方式

页面置换算法

4.2 分区存储管理及相关技术

固定分区分配

将整个用户空间划分为若干个固定大小的区域（分区大小相等/不等） 缺点：造成存储空间的浪费

动态分区分配

分配内存和回收内存

【2011】名词解释：颠簸 被调出的页面又立刻调入所形成的频繁调入调出的现象

1. 基于顺序搜索的动态分区分配算法 首次适应算法的低地址部分被使用的概率更大，高地址部分被使用的概率更小，可能会形成大的空闲区。

1. 基于索引的动态分区分配算法

1. 动态可重定位分区分配

通过移动内存中作业的位置，把原来多个分散的小分区拼接成一个大分区的方法。称为**“拼接”或“紧凑”**。 紧凑后的用户程序在内存中的位置发生了变化，若不对程序和数据的地址加以修改和变换，程序必然无法执行。

静态重定位是指在装入时一次集中地把程序指令中所有要转换的地址全部加以转换；而动态重定位则是每执行一条指令时，对其地址加以转换。实行静态重定位，原来的指令地址部分被修改了；实行动态重定位，只是按照所形成的地址去执行这条指令，并不对指令本身做任何修改。

为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，即在系统中增设一个重定位寄存器，用来存放程序在内存中的起始地址。程序在执行时，真正访问的内存是相对地址与重定位寄存器中的地址相加而形成的。

动态可重定位的优点：

• 程序可在内存中移动，当程序移动后，只要将新的内存区域的首地址放在基址寄存器中就可以了

• 易实现程序共享

• 有可能提供虚拟存储空间

• 支持程序浮动（静态重定位不支持程序浮动）

1. 对换技术（Swapping)

对换指把内存中暂时不能运行或者暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据换入内存。对换是改善内存利用率的有效措施，可以直接提高处理机的利用率和系统的吞吐量。 整体对换：以整个进程为单位。 页面（分段）对换：以进程的一个“页面”或“分段”为单位，以请求分页和请求分段式管理为基础。

1. 对换空间管理的主要目标 文件区采用离散分配方式 对换区采用连续分配方式

2. 对换区空闲盘块管理中的数据结构 对换区的首址及其大小，分别用盘块号和盘块数表示

3. 对换空间的分配与回收 与动态分区方式时的内存分配与回收方式类似

• 进程的换出 选择被换出的进程（进程状态+优先级+内存驻留时间） 进程换出过程：先申请对换空间，若申请成功，就启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。还有可换出进程，则继续，直至内存中再无阻塞进程为止。

• 进程的换入 首先查看PCB集合中所有进程的状态，从中找出“就绪”状态但已换出的进程； 如有多个，选择已换出到磁盘上时间最久的进程，为它申请空间； 如果申请成功，可直接将进程从外存调入内存； 如果失败，则需要将内存中某些进程换出，腾出足够空间，再将内存调入。

1. 覆盖技术

程序需要按照自身的逻辑划分出多个功能上独立的模块，把那些不会同时运行的模块共享同一个内存空间。 通常一个作业由若干个功能上独立的程序段组成，作业在一次运行时，也只用到其中的几段，利用这样一个事实，我们就可以让那些不会同时执行的程序段共用同一个主存区。

交换技术和覆盖技术的区别：

1.交换主要是在不同进程或作业之间进行。 2.覆盖主要在同一个作业或进程内进行，只能对与覆盖程序段无关的程序段进行覆盖。

1. 伙伴系统

整个可分配分区大小为2的幂次方，当需要的内存空间大于当前块的一半的时候就将整个分区分配给进程，如果小于当前分区的一半，就将当前分区对半分开，将其中一半继续与需要的内存大小进行比较，递归进行下去，直到满足所需内存大小大于分区一半。

4.3 分页/分段/段页式存储管理

分页存储管理方式

将用户的地址空间分为若干个固定大小的区域，称为“页”或者“页面”。相应地，也将内存空间分为若干个物理块或页框，页和块的大小相同。这样将用户程序的任一页放入任一物理块中，实现离散分配。

1. 页面：分页存储管理将进程的逻辑地址空间分为若干个页，并为各页加以编号。

【2012】主流微型计算机分页存储系统中页面大小通常设定为1KB、2KB、4KB等。如果页面大小设置为更大或更小，会带来哪些好处和问题？ 页面大，页表小，节省页表空间，而且查找快，缺页中断发生的次数相对而言少了一些。但一次换页的时间长，页内碎片导致的浪费比较大。页表小的则相反。 页表小了可以节省存储空间，减少内部碎片带来的浪费。进程调页的速度也比较快。 考虑的角度：①页表项少/多 ②查找速度快/慢 ③存储空间浪费/节省 ④换页速度慢/长

【2020】分页存储管理若增加分页大小，带来的好处与坏处。

1. 物理块：把内存的物理地址空间分为若干个块，也为各页加以编号。

2. 页面大小：过小的页面可以减少内存碎片的作用，但也会造成每个进程占用较多的页面，从而导致进程的页表过长；过大的页面，可以减少页表长度，提高页表换进换出的速度，但又会使页内碎片增大。

内部碎片🧩：指已经被分配出去却不能利用的内存空间。内部碎片是处于区域内部或页面内部的存储块，占有这些区域或页面的进程并不使用这些存储块。进程占有这些存储块，系统无法利用他们，直到进程释放他们或进程结束时，才有可能利用这些存储块。 外部碎片🧩：指的是还没有被分配出去，但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。外部碎片是位于已分配区域或页面外部的空闲存储块。这些存储块的总和可以满足当前申请的长度请求，但是由于他们的地址不连续或其他原因，使得系统无法满足当前申请。

1. 地址结构

若给定一个逻辑地址空间中的地址为A，页面大小为L

则页号P和页内地址d：

$$P=\operatorname{INT}[A/L]，d=[A] \operatorname{MOD} L$$

1. 页表

逻辑地址到物理地址的变换过程

1. 地址变换机构

分页系统的地址变换机构

1. 快表机制

为了提高地址变换速度，可在地址变换机构中增设一个具有并行查询能力的特殊高速缓冲寄存器，又称为“联想寄存器”，或称为“快表”

分段存储管理方式

引入分段存储管理方式的目的，主要是为了满足用户在编程和使用上多方面的要求

1. 满足需要

• 方便编程

• 信息共享

可重入代码是一种允许多个进程同时访问的代码。为使各个进程所执行的代码完全相同，绝对不允许可重入代码在执行过程中有任何改变

• 信息保护

• 动态增长

• 动态链接

1. 分段系统的基本原理

分段系统存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。

1. 段表

段表可以存放在一组寄存器之中，以利于提高地址的转换速度；但更常见的是将段表放在内存中。

段表的地址变换机构

1. 地址变换机构

在系统中设置段表寄存器，用于存放段表始址和段表长度

分段系统的地址变换过程

1. 分页和分段的主要区别

段页式存储管理方式

分页系统以页面作为内存分配的基本单位，能够有效提高内存利用率； 分段系统以段作为内存分配的基本单位，能够更好地满足用户多方面的需要；

1. 基本原理

利用段表和页表实现地址映射

1. 地址变换过程

段页式系统中的地址变换机构

4.4 虚拟存储技术

常规存储方式的特征和局部性原理

特征：

1. 一次性：作业必须一次性地全部装入内存后才能开始运行

2. 驻留性：作业被装入内存后，整个作业都一直驻留在内存中，任何部分都不会被换出，直至作业运行结束

局部性原理：

1. 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访问过，不久之后该数据很可能再次被访问。( 因为程序中存在大量的循环)

2. 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放的)

没有必要将应用程序全部装入内存，仅将当前要运行的少数页面或段先装入内存便可运行，其余暂留在盘上。

1. 如果需要访问的页或段尚未调入内存，便发出缺页请求

2. 如果内存已满，无法再装入新的页或段，再利用页或段的置换功能，将暂时不用的调至盘上，腾出足够的内存空间

【2012】虚拟内存的容量可以比物理内存大很多，但是访问速度和物理内存相近，为什么？ 虚拟内存是从硬盘里划出来的，本来虚拟内存出来的意义是因为之前内存太贵，虚拟内存作为内存的扩展，把部分不常用的内容从硬盘读取到虚拟内存中作为备用，以及内存溢出时作为缓冲避免死机，还有核心转储文件需要使用。但因为硬盘的IO速度和内存相比差了4-5个数量级，虚拟内存的访问速度巨慢无比，访问速度接近这是不可能的。

定义和特征

1. 定义：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器技术

2. 特征：多次性；对换性；虚拟性

实现方法

1. 分页请求系统

2. 请求分段系统

4.5 请求分页存储管理

请求分页系统是建立在基本分页基础上的，为了能支持虚拟存储器功能，而增加了请求调页功能和页面置换功能。

【2017】在虚拟页式存储系统中，为什么要引入缺页中断？缺页中断由哪几部分组成，试简述其实现方法。 在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。此时应将缺页的进程阻塞，如果内存中中有空闲块，则分配一块，将调入的页装入该块，并修改页表中的相应表项；若此时内存中没有空闲块，则要淘汰某页。所以在一定程度上增加了内存的逻辑块数。 实现： ①缺页中断作为中断同样要经历：保护CPU环境，分析中断原因，转入缺页中断程序、恢复CPU环境等几个步骤； ②进行地址变换，先检索快表： 若找到要访问的页，便修改页表项中的访问位，然后利用页表项中给出的物理块号和页内地址形成物理地址。 若未找到要访问的页表项，应到内存中去查找页表，再对比页表项中的状态位P，看该页是否已调入内存，未调入则产生缺页中断，请求外存把该页调入内存。

硬件支持

1. 请求页表支持

• 状态位P：指示该页是否调入内存

• 访问字段A：记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问。

• 修改位M：标识该页在调入内存后是否被修改过。已被修改，需要将该页重写到外存上，以保证外存中所保留的副本始终是最新的。

• 外存地址：指出该页在外存上的地址，通常是物理块号，供调入该页时参考。

【2018】对于请求分页虚拟存储系统，进程页表的页表项应当包括哪些字段，并请简明扼要描述有关逻辑地址到物理地址的转换。 请求分页系统中进程页表的页表项包括以下字段：页号、物理块号、状态位、访问字段、修改位、外存地址 进行地址变换时，先检索快表，如果在快表中，找到要访问的页，便修改快表中的访问位，然后利用页表项给出的物理块号和页内地址形成物理地址。如果在快表中未找到该页的页表项，应到内存中去查找页表，再比对页表中的状态位P，看该页是否调入内存，未调入则产生缺页中断，请求外存把该页调入。

1. 缺页中断机制

在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。

与一般的中断有所区别：

• 在指令执行期间产生和处理中断信号（一般是在一条指令执行完之后，才检查是否有中断请求到达）

• 一条指令在执行期间可能产生多次缺页中断

【2020】名词解释：缺页中断 在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。

涉及6次缺页中断的指令

1. 地址变换机构

• 首先检索快表

• 快表未找到，内存中查找页表

请求分页中的地址变换过程

内存分配

1. 最小物理块数的确定

最小物理块数：指能保证进程正常运行所需的最小物理块数，当系统为进程分配的物理块数少于此值时，进程将无法运行

1. 内存分配策略

内存分配：固定、可变 置换策略：全局、局部

• 固定分配局部置换 固定：指为每个进程分配一定数目的物理块，在进程运行期间不再改变 局部：如果在进程运行中发现缺页，只能从已分配的页面中换出一页，然后再调入一页

• 可变分配全局置换 可变：指先为每个进程分配一定数目的物理块，运行期间可以适当增加或减少 全局：如果在进程运行中发现缺页，则将OS保留的空闲物理块取出一块分配给该进程，或者以所有进程的全部物理块为标的，选择一块换出，然后将所缺之页调入

• 可变分配局部置换

1. 物理块分配算法

• 平均分配算法

• 按比例分配算法

• 考虑优先权的分配算法

页面调入策略

1. 何时调入

• 预调页策略：预计在不久后便会访问的页面预先调入内存

• 请求调页策略：若发现其所在的页面不在内存，便立即提出请求（每次仅调入一页，花费较大系统开销）

1. 何处调入

请求分页系统的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区； 通常文件区采用离散分配方式，对换区采用连续分配方式

发生缺页请求时，从何处调入，分为三种情况：

• 系统拥有足够的对换区空间。可以全部从对换区调入所需页面

• 系统缺少足够的对换区空间。凡是不会被修改的文件，直接从文件区调入；可能被修改的部分，将他们换出时须调到对换区，以后需要时再从对换区调入

• UNIX方式。凡是为运行过的页面，都从文件区调入；曾经运行过但又被换出的页面，被放在对换区

1. 如何调入

• 每当程序所要访问的页面未在内存（存在位为：“0”），便向CPU发出一缺页中断

• 中断处理程序首先保留CPU环境，分析中断原因后转入缺页中断处理程序

• 该程序通过查找页表得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘I/O，将该页调入内存，然后修改页表

• 如果内存满了，按照某种置换算法，从内存中选出一页换出，若该页未被修改过（修改位为“0”），可不必再写回磁盘，否则必须把它写回磁盘，再把所需的页面调入内存，并修改页表中对应的页表项，置存在位为“1”，并将此页表项写入快表

1. 缺页率

假设逻辑空间n页，系统分配物理块数m（m≤n）。访问页面成功次数为S，访问页面失败次数为F，则总访问次数A=S+F。 缺页率 f=F/A 缺页率受到以下因素影响：

• 页面大小：页面大，缺页率较低

• 页面所分配物理块数：物理块数多，缺页率较低

• 页面置换算法

• 程序固有特性：程序编制的局部化程度高，缺页程度较低

假设被置换页面的被修改概率为β，其缺页中断处理时间为$t_a$；未被修改的概率为1-β，处理时间为$t_b$，则缺页中断处理时间计算公式：

$$t=\beta\times t_a +(1-\beta)\times t_b$$

4.6 请求分段存储管理

硬件支持

1. 请求段表机制

[2008]说明请求段式存储管理系统各字段的作用

存取方式:标识存取属性只执行、只读或允许读/写 访问字段A:记录该段被访问的频繁程度 修改位M:该段在进入内存后是否被修改过 存在位P：指示本段是否调入内存。 增补位：表示本段在运行过程中是否做过动态增长 外存始址：本段在外存中的起始地址，即起始盘块号

1. 缺段中断机制

请求分段系统中的中断处理过程

1. 地址变换机构

请求分段系统的地址变化过程

分段的共享与保护

1. 共享段表

共享段的分配

• 对第一个请求使用该共享段的进程: 由系统为该共享段分配一物理区，并将共享段调入; 将该区始址填入请求进程的段表的相应项中; 在共享段表中增加一表项，填写有关数据，并置count值为1

• 对其他调用该共享段的进程: 在调用进程的段表中增加一表项， 填入该共享段的物理地址; 在共享段表的对应表项中填入调用进程的相关信息，并执行count=count+1

共享段的回收

• 当进程不再需要共享段时:撤消共享段的表项;执行count=count-1 仅当count=0时，由系统回收共享段的物理内存

1. 分段保护

• 越界检查 比较：段号与段表长度、段内地址与段长; 若越界，则发出越界中断信号。

• 存取控制检查 存取控制字段 只读、只执行、读/写

• 环保护机构: 低编号的环具有高优先权 一个程序可以访问驻留在相同环或较低特权环（外环）中的数据 一个程序可以调用驻留在相同环或较高特权环（外环）中的服务

4.7 多级页表和反置页表

多级页表

针对难以找到大的连续的内存空间来存放页表的问题，可以利用将页表进行分页的方法，使每个页面的大小与内存物理块的大小相同，然后离散地将各个页面分别存放在不同的物理块中。同样也要为离散分配的页表，再建立一张页表，称为“外层页表”。

具有两级页表的地址变换机构

反置页表

所有进程共同使用一张页表，这张页表中的条目的数量和内存中物理的页框的数量是一样的。反置页表中的每个条目拥有以下字段：

页号

进程ID

控制位——包括valid位，dirty位，reference位，protection位和locking位。

链接指针——如果出现进程共享内存的情况，就会用到链接指针。

4.8 内存保护机制

内存分配前，需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。

通过釆用重定位寄存器和界地址寄存器来实现这种保护。重定位寄存器含最小的物理地址值，界地址寄存器含逻辑地址值。每个逻辑地址值必须小于界地址寄存器；内存管理机构动态地将逻辑地址与界地址寄存器进行比较，如果未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送交内存单元。每一个逻辑地址都需要与这两个寄存器进行核对，以保证操作系统和其他用户程序及数据不被该进程的运行所影响。

4.9 页面淘汰算法设计实现及应用

当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。 不适当的算法可能造成进程发生“抖动”，刚被换出的页很快又要被访问，需要将它重新调入，此时又需要再选一页调出；而此刚被调出的页很快又被访问，又需要将它调入。

最佳置换算法（Optimal）

从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。

$$7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1$$

先进先出页面置换算法（FIFO）

这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。

$$7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1$$

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

【2015】LRU算法的基本思想是什么，有什么特点？ LRU即最近最少使用，在操作系统中，LRU可以作为页面置换策略，其基本思想是已经很时间没有使用的页面很可能在未来也不会被使用，因此，LRU算法在置换页面时总是淘汰最近最少使用的页面。 特点： （1）总是淘汰最近最少使用的页面。 （2）LRU算法完全实现的代价很高。

利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。

$$7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1$$

最少使用置换算法（LFU）

选择最近时期使用最少的页面作为淘汰页

Clock置换算法

    > 简单的CLOCK算法是给每一帧关联一个附加位，称为**使用位**。当某一页首次装入主存时，该帧的使用位设置为1;当该页随后再被访问到时，它的使用位也被置为1。对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为**最近未用(Not Recently Used, NRU)算法**。

在使用位的基础上再增加一个修改位，则得到改进型的CLOCK置换算法。这样，每一帧都处于以下四种情况之一：

最近未被访问，也未被修改(u=0, m=0)。最佳淘汰页 最近被访问，但未被修改(u=1, m=0)。不是很好的淘汰页 最近未被访问，但被修改(u=0, m=1)。该页有可能再被访问 最近被访问，被修改(u=1, m=1)。该页可能再被访问

1. 从指针的当前位置开始，扫描帧缓冲区。在这次扫描过程中，对使用位不做任何修改。选择遇到的第一个帧(u=0, m=0)用于替换。

2. 如果第1步失败，则重新扫描，查找(u=0, m=1)的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中，对每个跳过的帧，把它的使用位设置成0。

3. 如果第2步失败，指针将回到它的最初位置，并且集合中所有帧的使用位均为0。重复第1步，并且如果有必要，重复第2步。这样将可以找到供替换的帧。

页面缓冲算法（PBA）

影响页面换进换出效率的因素

• 页面置换算法

• 写回磁盘的频率

• 读入内存的频率

空闲页面链表：当有一个未被修改的页要换出时，实际上并不将它换出到外存，而是把他们所在的物理块挂在空闲链表末尾

修改页面链表：当有一个已被修改的页要换出时，并不立即将它换出到外存，而是把他们所在的物理块挂在修改页面链表末尾。这样做的目的是：降低将已修改页面写回磁盘的频率，降低将磁盘内容读入内存的频率。