写在前面：本文参考王道论坛的 操作系统考研复习指导单科书

下面的流程图很重要。
加入快表的基本分页

加入快表的二级页表！！

虚拟存储器：请求分页的流程图。

文章目录

• 第三章 内存管理
• • 3.1 内存管理概念
  • • 3.1.1 内存管理的基本原理和要求
    • • 1 程序装入和链接
      • 2 逻辑地址空间与物理地址空间
      • 3 内存保护
    • 3.1.2 覆盖与交换
    • • 1 覆盖
      • 2 交换
    • 3.1.3 连续分配管理方式
    • • 1 单一连续分配
      • 2 固定分区分配
      • 3 动态分区分配
    • 3.1.4 非连续分配管理方式
    • • 1 基本分页存储管理方式
      • • （1）分页存储的几个基本概念
        • （2） 基本地址变换机构
        • （3）具有快表的地址变换机构
        • （4）两级页表
      • 2 基本分段存储管理方式
      • 3 段页式管理方式
  • 王道习题（二级页表）
  • 3.2虚拟内存管理
  • • 3.2.1 虚拟内存的基本概念
    • 3.2.2 请求分页管理方式
    • 3.2.3 页面置换算法
    • • 1. 最佳（OPT）置换算法
      • 2. 先进先出（FIFO）置换算法
      • 3.最近最久未使用（LRU）置换算法
      • 4. 时钟（CLOCK）置换算法
    • 3.2.4 页面分配策略
    • 3.2.5 抖动
    • 3.2.6 工作集
    • 王道习题

第三章 内存管理

3.1 内存管理概念

3.1.1 内存管理的基本原理和要求

内存管理是操作系统设计中最重要和最复杂的内容之一。虽然计算机硬件技术一直在发展，内存容量也在不断增大，但是仍然不可能将所有的用户进程和系统所需要的全部程序与数据放入内存，因此操作系统必须对内存空间进行合理的划分和有效的动态分配。 操作系统对内存的划分和动态分配，就是内存管理的概念。

1 程序装入和链接

创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序，通常需要以下几个步骤：

• 编译。由编译程序将用户源代码编译成若干目标代码。就是.o文件，每个模块的编址相互独立，都从0开始。
• 链接。由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起，形成一个完整的装入模块。就是.exe文件。
• 装入。由装入程序将装入模块装入内存中运行。

程序的链接有以下三种方式

1）静态链接。在程序运行之前，先将各目标模块及它们所需要的库函数链接成一个可执行程序，以后不再拆开。

2）装入时动态链接。将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的方式。

3）运行时动态链接。对某些目标模块的链接，是在程序执行中需要该目标模块时才进行的。优点是便于修改和更新，便于实现对目标模块的共享。

内存的装入模块在装入内存时，同样有三种方式。

1）绝对装入。 在编译时，若知道程序将驻留在内存中的某个位置，则编译程序将产生绝地地址的目标代码。 绝对装入程序按照装入模块中的地址，将程序和数据装入内存。 由于程序中的逻辑地址与实际内存地址完全相同，因此不需要对程序和数据的地址进行修改。

绝对装入方式只适用于单道程序设计。另外，程序中所用的绝对地址，可在编译或汇编时给出，也可以由程序员直接赋予。而通常情况下在程序中采用的是符号地址，编译或汇编时再转换为绝对地址。

2）可重定位装入。在多道程序设计下，多个目标模块的起始地址（简称始址）通常都是从0开始，程序中的其他地址都是相对于始址的，此时应采用可重定位装入方式。 根据内存的当前情况，将装入模块装入内存的适当位置。装入时对目标程序中指令和数据的修改过程称为重定位。地址变换通常是在装入时一次完成的，所以又称静态重定位。

静态重定位的特点是，一个作业装入内存中，必须给它分配要求的全部内存空间，若没有足够的内存，则不能装入该作业。 此外，作业一旦进入内存，整个运行期间就不能在内存中移动，也不能再申请内存空间。

3） 动态运行时装入，也称动态重定位。 程序在内存中若发生移动，则需要采用动态的装入方式。装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换过程推迟到程序真正需要执行时进行。因此，装入内存后的所有地址均为相对地址。这种方式需要一个重定位寄存器。

重定位寄存器存放装入模块的起始内存地址。

动态重定位的特点是：可以将程序分配到不连续的存储区中；在程序运行之前可以只装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存； 便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。

2 逻辑地址空间与物理地址空间

编译后，每个目标模块都从0号单元开始编址，这称为该目标模块的相对地址（或逻辑地址）。当链接程序将各个模块链接成一个完整的可执行目标程序时，链接程序顺序依次按照各个模块的相对地址构成统一的从0号单元地址开始的逻辑地址空间，用户程序和程序员只需要知道逻辑地址，而内存管理的具体机制则是完全透明的，只有系统编程人员才会涉及内存管理的具体机制。 不同进程可以拥有相同的逻辑地址， 因为这些相同的逻辑地址可以映射到主存的不同位置。

物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指令和访问数据，最后都要通过物理地址从主存中存取。 当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换为物理地址， 这个过程称为地址重定位。

3 内存保护

内存分配前，需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。内存保护可以采取两种方法：

1） 在CPU中设置一对上下限寄存器，存放用户作业在主存中的下限和上限地址，每当CPU要访问一个地址时，分别和两个寄存器相比，判断有无越界。

2） 采用重定位寄存器（或称为基址寄存器） 和界地址寄存器（又称限长寄存器）来实现这种保护。 重定位寄存器含最小的物理地址值，界地址寄存器含逻辑地址的最大值。 每个逻辑地址值必须小于界地址寄存器；

内存管理机构动态地将逻辑地址与界地址寄存器比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送交到内存单元。

3.1.2 覆盖与交换

覆盖与交换技术是在多道程序环境中用来扩充内存的两种方法。

1 覆盖

早期的计算机系统中，主存容量很小，虽然主存中仅仅存放一道用户程序，但存储空间放不下用户进程的现象也时有发生，这一矛盾可以使用覆盖技术来解决。

覆盖的基本思想：将程序分为多个段，常用的段常驻内存，不常用的段在需要时调入内存。

把用户空间分为一个固定区和若干覆盖区。

2 交换

交换的基本思想：把处于等待状态（或在CPU调度原则下被剥夺运行权利）的程序从内存移到外存，把内存空间腾出来，这一过程称为换出；把准备好竞争CPU运行的程序从外存移到内存，这一过程称为换入。

交换技术主要用在不同进程（或者作业）之间，而覆盖则用于同一程序或进程中。由于覆盖技术要求给出程序段之间的覆盖结构，使得其对用户和程序员不透明，所以对于主存无法存放用户程序的矛盾， 现代操作系统是通过虚拟内存技术来解决的，覆盖技术则已经成为历史。

3.1.3 连续分配管理方式

连续分配方式是指为一个用户程序分配一个连续的内存空间，譬如某用户需要1GB的内存空间，连续分配方式就在内存空间中为用户分配一块连续的1GB空间。连续分配方式主要包括单一连续分配、固定分区分配和动态分区分配。

1 单一连续分配

内存在该种方式下分为系统区和用户区。系统区仅供操作系统使用，通常在低地址部分；用户区是为用户提供的、除系统区外的内存空间。

这种方式无需进行内存保护。因为内存中永远只有一道程序，因此肯定不会因为访问越界而干扰其他程序。

这种方式的优点：简单、无外部碎片，可以采用覆盖技术，不需要额外的技术支持。

缺点：只能用于单用户、单任务的操作系统，有内部碎片，存储器的利用率极低。

2 固定分区分配

固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可再从外存的后备作业队列中选择适当大小的作业装入该分区，如此循环。

固定分区分配在划分分区时有两种不同的方法。

• 分区大小相等。用于利用一台计算机去控制多个相同对象的场合，缺乏灵活性。
• 分区大小不等。 划分为多个较小的分区、适量的中等分区和少量大分区。

为了便于内存分配，通常将分区按照大小排队，并为之建立一张分区说明表，其中各表项包括每个分区的始址、大小及状态（是否已分配）。当有用户程序要装入时，便检索该表，以找到合适的分区给予分配并将其状态置为“已分配”； 未找到合适分区时，则拒绝为该用户程序分配内存。

这种分区方式存在两个问题：

1）程序可能太大而放不进任何一个分区中，这时用户不得不使用覆盖技术（常用的段常驻内存，不常用的段在需要时调入内存）来使用内存空间。

2）主存利用率低，当程序小于固定分区大小时，也占用一个完整的内存分区空间，这样分区内部就存在空间浪费，这种现象称为内部碎片。

固定分区是可用于多道程序设计的最简单的存储分配，无外部碎片，但不能实现多进程共享一个主存区，所以存储空间利用率低。 固定分区分配很少用于现在通用的操作系统中，但在某些用于控制多个相同对象的控制系统中仍发挥着一定的作用。

3 动态分区分配

动态分区分配又称可变分区分配，是一种动态划分内存的分区方法。这种分区方法不预先划分内存，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。 因此，系统中分区的大小和数目是可变的。

动态分区在开始分配时是很好的，但之后会导致内存中出现许多小的内存块。 随着时间的推移，内存中会产生越来越多的碎片，内存的利用率随之下降。这些小的内存块称为外部碎片，指在所有分区外的存储空间会变成越来越多的碎片，这些与固定分区中的内部碎片正好相对。

克服外部碎片可以通过紧凑（compaction）技术来解决，即操作系统不时地对进程进行移动和整理。但这需要动态重定位寄存器的支持，且相对费时。 紧凑的过程类似于Windows系统中的磁盘整理程序，只不过后者是对外存空间的紧凑。

3.1.4 非连续分配管理方式

非连续分配允许一个程序分散地装入不相邻的内存分区。在连续分配管理方式中，我们发现，即使内存中有超过1GB的空闲空间，但若没有连续的1GB空间，则需要1GB空间的作业仍然无法运行。 但若采用非连续分配管理方式，则作业所要求的1GB内存空间可以分散地分配在内存的各个区域，当然，这也需要额外的空间去存储它们(分散区域)的索引， 使得非连续分配方式的存储密度低于连续存储方式的。

非连续存储方式根据分区的大小是否固定，分为分页存储管理方式和分段存储管理方式。

再分页存储管理方式中，又根据运行作业时是否要把作业的所有页面都装入内存才能运行，分为基本分页存储管理方式和请求分页存储管理方式。

1 基本分页存储管理方式

固定分区会产生内部碎片，而动态分区会产生外部碎片，这两种技术对内存的利用率都比较低。

我们希望内存的使用能尽量避免碎片的产生，这就引入了分页的思想：把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。 每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。

分页的方法从形式上看，像分区相等的固定分区技术，分页管理不会产生外部碎片。

但它又有本质的区别： 块的大小相对分区要小得多，而且进程也按照块进行划分，进程运行时按块申请主存可用空间并执行。这样，进程只会在为最后一个不完整的块申请一个主存块空间时，才产生主存碎片，所以尽管会产生内部碎片，但这种碎片相对于进程来说也是很小的，每个进程平均产生半个块大小的内部碎片（也称业内碎片）。

（1）分页存储的几个基本概念

1）页面和页面大小。

将内存空间分为一个个大小相等的分区（比如每个分区4KB），每个分区就是一个“页框”。每个页框有一个编号，即页框号，页框号从0开始。

注：$页框=页帧=内存块=物理块=物理页面$
页框号=页帧号=内存块号=物理块号=物理页号

将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个“页”或者“页面”。每个页面也有一个编号，叫做页号，页号也是从0开始编号。

2）逻辑地址结构
\color{red}{}
$逻辑地址结构=页号P+页内偏移量W$

注意，地址结构决定了虚拟内存的寻址空间有多大。在实际问题中，页号、页内偏移、逻辑地址大都是用十进制给出的。

3）页表

为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表，页表记录页面在内存中对应的物理块号，页表一般存放在内存中。

页表是由页表项组成的.

$页表项=页号+内存块号$

页表的作用：实现页号到物理块号的地址映射。

操作系统以页框为单位为各个进程分配内存空间，进程的每个页面分别放入一个页框中。也就是说，进程的页面和内存的页框有一一对应的关系。

（2） 基本地址变换机构

地址变换机构的任务是将逻辑地址转换为内存中的物理地址。地址变换是借助于页表实现的。

设页面大小为L,逻辑地址A到物理地址E的变换过程如下图（逻辑地址、页号、每页的长度都是十进制给出的）

地址变换机构的地址变换过程：

根据逻辑地址算出页号和页内偏移量

检查页号是否越界

查询页表（根据页表始址+页号），找到相应的页表项，确定页面存放的内存块号

用内存块号和页内偏移量计算出物理地址

在系统中通常设置一个页表寄存器（PTR），存放页表在内存的起始地址F和页表长度M。 进程未执行时，页表的始址和长度存放在进程控制块PCB（在系统区中）中，当进程执行时，才将页表始址和长度存入页表寄存器。

（3）具有快表的地址变换机构

从上面的地址变换过程可以看出， 若页表全部放在内存中，则存取一个数据或者一条指令只要要访问内存两次：第一次是访问页表，确定所存取的数据或指令的物理地址；第二次是根据该地址存储数据或指令。 显然，这种方法比通常执行指令的速度慢了一半。

为此，在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器（Cache）-–快表，又称相联存储器(TLB),用来存放当前访问的若干页表项， 以加速地址变换过程。 与此对应，主存中的页表常称为慢表。
具有快表的地址变换机构如下图。

在有快表的分页机制中，地址转换的过程如下所示：

CPU给出逻辑地址后，由硬件进行地址转换，将页号送入cache，并将此页号与快表中的所有页号进行比较。

若找到匹配的页号，说明所要访问的页表项在快表中，则直接从中取出该页对应的页框号（内存块号），与页内偏移量拼接形成物理地址。 这样，存取数据仅一次访存便可以实现。

若未找到匹配的页号，则需要访问主存中的页表，在读出页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，需要按照一定的算法对旧的页表项进行替换。

注意：有些处理机设计为快表和慢表同时查找，若在快表中查找成功则终止慢表的查找。

一般快表的命中率在90%以上，这样分页带来的速度损失就可以降至10%以下。 快表的有效性基于局部性原理。

（4）两级页表

单级页表存在的问题
问题一：页表必须连续存放，因此当页表很大时，需要占用很多个连续的物理内存块（页框）。

问题二：没有必要让整个页表常驻内存，因为进程在一段时间内可能只访问几个特定的页面。

二级页表就是在原有页表结构上再加上一层页表。

如何实现地址转换？

1按照地址结构将逻辑地址拆分为3部分

2从PCB中读出页目录表始址，根据一级页号查页目录表，找到下一级页表在内存中的位置

3根据二级页号查表，找到最终想访问的内存号

4结合页内偏移量得到物理地址

需要注意的几个细节：

1 采用多级页表机制，则各级页表的大小不能超过一个页面。

2 两级页表的访存次数分析（假设没有快表机构）

第一次访存：访问内存中的页目录表；
第二次访存：访问内存中的二级页表；
第三次访存：访问目标内存单元；

2 基本分段存储管理方式

分页管理方式是从计算机的角度设计的，目的是提高内存的利用率，提高计算机的性能。分页通过硬件机制实现，对用户完全透明。

分段管理方式是从用户和程序员的角度出发的，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。

1）分段。 段式管理方式按照用户进程中的自然段划分逻辑空间。

例如，用户进程由主程序、两个子程序、栈和一段数据组成，于是可以把这个用户进程分为5段，每段从0开始编址，并分配一段连续的地址空间（段内要求连续，段间不要求连续，因此整个作业的地址空间是二维的），其逻辑地址由段号S与段内偏移量W两部分组成。

段号的位数：决定了每个进程最多可分为多少段。

段内地址的位数：决定了每个段的最大长度是多少。

在页式系统中，逻辑地址的页号和页内偏移量是对用户透明的；
在段式系统中，段号和段内偏移量必须是用户显示提供，在高级程序设计语言中，这个工作由编译程序完成。

2）段表。每个进程都有一张逻辑空间与内存空间映射的段表，其中每个段表项对应进程的一段，段表项记录该段在内存中的始址和长度。

配置段表后，执行中的进程可通过查找段表，找到每段对应的内存区。 可见，段表用于实现从逻辑段到物理内存区的映射。

3）地址变换机构。

为了实现进程从逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址F和段表长度M。

从逻辑地址A到实际物理地址E的地址转换如下：

1.根据逻辑地址得到段号S和段内地址W（即段内偏移量）
2.判断段号是否越界。如果S≥M，则产生越界中断，否则继续执行。
3.查询段表，找到对应的段表项，段表项的存放地址为F+S✖段表项长度。
4.检查段内地址是否超过段长（和页式管理不同）。如果W≥C（段内地址≥段长），则产生越界中断，否则继续执行。
5段基址b+段内地址W=实际物理地址。
6.访问目标内存单元。

4）段的共享与保护。

在分段系统中，段的共享是通过两个作业的段表中相应段表项指向被共享的段的同一个物理副本来实现的。当一个作业正从共享段中读取数据时，必须方式另一个作业修改此共享段中的数据。不能修改的代码称为纯代码或可重入代码（它不属于临界资源），这样不能修改的代码或数据可以共享，而可修改的代码或数据不能共享。

分段管理方式的保护主要有两种：一种是存储控制保护，另一种是地址越界保护。

分段管理的地址空间是二维的，因为段号和段内地址（即段内偏移量）必须要显式给出（段号，段内偏移）。

3 段页式管理方式

优点缺点

分页管理	内存空间利用率高，不会产生外部碎片，只会有少量内部碎片	不方便按照逻辑模块实现信息的共享和保护
分段管理	很方便按照逻辑模块实现信息的共享和保护	如果段长过大，为其分配很大的连续的内存空间不方便。另外，段式会产生外部碎片。

尽管段式管理的外部碎片可以通过紧缩技术来处理，但是需要付出较大的时间代价。

在段页式系统中，作业的地址空间首先被分成若干逻辑段，每段都有自己的段号，然后将每段份成若干大小固定的页。 对内存空间的管理仍然和分页存储管理一样，将其分成若干和页面大小相等的存储块，对内存的分配以存储块为单位。

在段页式系统中，作业的逻辑地址分为三部分：段号、页号和业内偏移量。

为了实现地址转换，系统为每个进程建立一张段表，每个分段有一张页表。段表表项中至少包含段号、页表长度和页表始址，页表表项中至少包括页号和块号。此外，系统还应有一个段表寄存器，指出作业的段表长度和段表始址。

注意：在一个进程中，段表只有一个，而页表可能有多个。

在进行地址转换时，首先通过段表查到页表始址，然后通过页表找到页框号，最后形成物理地址。

由逻辑地址得到段号、页号、页内偏移量
2.段号和段表寄存器的段长比较，检查是否越界
3.由段表始址和段号找到对应的段表项
4.根据段表中页表长度，检查页号是否越界
5.根据段表项中记录的页表始址和页号查询页表，得到相应的页表项
6.由页表项记录的块号和页内偏移量得到物理地址
7.访问目标单元

段页式进行查找一次逻辑地址需要三次访存（分别是查段表，查页表，访问实际内存）。这里同样可以使用快表进行加速。

程序员需要显示地给出（段号，段内地址），而各段进行“分页”对程序员是不可见的。 系统会根据段内地址自动划分为页号和页内偏移量。所以段页式管理的地址空间是二维的。

王道习题（二级页表）

答案：B 128
分析 ：在二级页表中，一页可以存放的页表项个数=$2^{10}/2=2^9个页表项$，逻辑地址空间需要$2^{16}$个页表项，则总共需要$2^{16}/2^9=2^7=128$个页面，二级页表供128个页面，则一级页表(又称页目录表)有128个表项。

本题选A
只需要将虚拟地址写成二进制形式，并且分块即可。

3.2虚拟内存管理

3.2.1 虚拟内存的基本概念

传统存储管理方式的特征

前面讨论的各种内存管理策略是为了同时将多个进程保存在内存中，以便允许多道程序设计。 它们都具有以下两个共同的特征：

1）一次性。作业必须一次性全部装入内存，才能开始运行。

2）驻留性。作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直到作业运行结束。运行中的进程会因等待I/O而被阻塞，可能处于长期等待状态。

2 局部性原理

局部性原理表现在以下两个方面：
1）时间局部性。 程序中的某条指令一旦执行，不久后该指令可能再次执行；某数据被访问过，不久后该数据可能再次被访问。 产生时间局部性的典型原因是程序中存在着大量的循环操作。

2）空间局部性。 一旦程序访问了某个存储单元，在不久后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围内，因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。

时间局部性通过将近来使用的指令和数据保存到高速缓存中，并使用高速缓存的层次结构实现。

空间局部性通常使用较大的高速缓存， 并将预取机制集成到高速缓存控制逻辑中实现。

虚拟内存技术实际上建立了“内存-外存”的两级存储器结构， 利用局部性原理实现高速缓存。

3 虚拟存储器的定义和特征

基于局部性原理，在程序装入时，将程序的一部分装入内存，而将其余部分留在外存，就可启动程序执行。 在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。 这样，操作系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。

之所以将其称为虚拟存储器，是因为这种存储器实际上并不存在，只是由于系统提供了部分装入、请求调入和置换功能后（对用户完全透明），给用户的感觉是好像存在一个比实际物理内存大得多的存储器。 虚拟存储器的大小由计算机的地址结构决定， 并不是内存和外存的简单相加。

虚拟存储器具有以下三个主要特征：

1）多次性。 多次性是指无需在作业运行时一次性地全部装入内存，而允许被分成多次调入内存运行。

2）对换性。 对换性是指无需在作业运行时一直常驻内存，而允许在作业的运行过程中，进行换出和换入。

3）虚拟性。 虚拟性是指从逻辑上扩充内存的容量， 使用户看到的内存容量远大于实际的内存容量。

4 虚拟内存技术的实现

虚拟内存技术允许将一个作业分多次调入内存。采用连续分配方式时，会使相当一部分内存空间都处于暂时或“永久”空闲状态，造成内存资源的严重浪费，而且也无法从逻辑上扩大内存容量。因此，虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。

虚拟内存的实现有以下三种方式：

• 请求分页存储管理
• 请求分段存储管理
• 请求段页式存储管理

不管哪一种实现方式，都需要一定的硬件支持。 一般需要的支持有以下几个方面：

1一定容量的内存和外存。
2页表机制（或段表机制)，作为主要的数据结构。

3 中断机构，当用户程序要访问的部分尚未调入内存时，则产生中断。
4地址变换机构，逻辑地址到物理地址的变换。

3.2.2 请求分页管理方式

请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页使目前最常用的一种实现虚拟存储器的方法。

再请求分页系统中，只要求将当前需要的一部分页面装入内存，便可以启动作业。 在作业执行过程中，当所访问的页面不在内存中时，再通过调页功能将其调入，同时还可以通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间。

1 页表机制

请求分页系统的页表机制不同于基本分页系统，请求分页系统在一个作业运行之前不要求全部一次性调入内存，因此在作业运行过程中，必然会存在要访问的页面不在内存中的情况，如何发现和处理这种情况是请求分页系统必须解决的两个基本问题。 为此，在请求页表项中增加了4个字段。

增加的4个字段说明如下：

状态位P。用于指示该页是否已经调入内存。供程序访问时参考。

访问字段A。 用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，共置换算法换出页面时参考。

修改位M。 标识该页在调入内存后是否被修改过。

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

2 缺页中断机构

在请求分页系统中，每当所要访问的页面不在内存时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。此时应将缺页的进程阻塞（调页完成唤醒），若内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中的相应页表项，若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存）。

缺页中断作为中断，同样要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序、恢复CPU环境等几个步骤。 但是和一般的中断相比，有两个明显的区别：

• 1.在指令执行期间而非一条指令执行完后产生和处理中断信号，属于内部中断。
• 2.一条指令在执行期间，可能产生多次中断。

3 地址变换机构

在地址变换时，先检索快表：
如果找到要访问的页，则修改页表项中的访问位（写指令还需要重置修改位），然后利用页表项中给出的物理块号和页内地址形成物理地址。

如果没有找到该页的页表项，则应到内存中去查找页表，再对比页表项中的状态位P，看是否已经调入内存，未调入则产生缺页中断，请求从外存把该页调入内存。

3.2.3 页面置换算法

1. 最佳（OPT）置换算法

最佳(OPT,optimal)置换算法选择的被淘汰页面是以后永不使用的页面，或是在最长时间内不再被访问的页面，以便保证获得最低的缺页率。

然而，由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的，因而该算法无法被实现。

最佳置换算法可以用来评价其他算法。

2. 先进先出（FIFO）置换算法

优先淘汰最早进入内存的页面，即在内存中驻留时间最久的页面。 该算法实现简单，只需要把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。 但该算法与进程实际运行时的规律不适应加粗样式，因为在进程中，有的页面经常被访问。

FIFO算法会产生所分配的物理块数增大而页故障数不减反增的异常现象，称为Belady异常。只有FIFO算法可能出现Belady异常，LRU和OPT算法永远不会出现Belady异常。

3.最近最久未使用（LRU）置换算法

最近最久未使用（LRU，Leat Recently Used）置换算法选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能亦不会被访问。 该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。

LRU算法的性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类算法。理论上可以证明，堆栈类算法不可能出现Belady异常。

4. 时钟（CLOCK）置换算法

LRU算法的性能接近于最佳置换算法，但是实现起来比较困难，且开销大；FIFO算法实现起来简单，但性能差。 因此，操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU算法的性能，这类算法都是CLOCK算法的变体。因为算法要循环扫描缓冲区，像时钟的指针一样转动，所以称为CLOCK算法，又称为最近未用（Not Recently Used，NRU）算法。

简单的CLOCK算法给每帧关联一个附加位，称为使用位。但某页首次装入内存时，将该帧的使用位设置为1；当该页最后再被访问到时，其使用位也被置为1.对于页替换算法，用于替换的候选帧集合可视为一个循环缓冲区，并有一个指针与之相关联。 当某一页被替换时，该指针被设置为指向缓冲区的下一帧。 当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。 每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0. 若在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换，并停留在最初的位置上，替换该帧中的页。

改进型CLOCK置换算法

在使用位u的基础上再增加一个修改位m，则得到改进型CLOCK置换算法。

这样每帧都处于以下四种情况之一

• 最近未被访问，也未被修改（0，0）
• 最近被访问，但未被修改（1，0）
• 最近未被访问，但被修改（0，1）
• 最近被访问，被修改（1，1）

算法执行过程如下

1）从指针的当前位置开始，扫描帧缓冲区。在这次扫描过程中，对使用位不做任何修改，选择遇到的第一个帧（0，0）进行替换。

2） 若第一步失败，则重新扫描，查找（0，1）的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中，对每个跳过的帧，把它的使用位设置为0.
3）若第二步失败， 则指针将回到它的最初位置，且集合中所有帧的使用位均为0.重复第一步，查找（0，0）帧，并且对使用位不做任何修改。

4）若第四步失败，则重复第二步。查找（0，1）的帧。这个过程中需要对遇到的帧就行使用位设置0.

改进型CLOCK优于简单CLOCK算法的地方在于替换时首选没有变化的页。由于修改过的页在替换之前必须写回，因而这样做会节省时间。

操作系统中任何优化而有效的页面置换算法都有一个原则，即尽可能保留曾经使用过的页面，而淘汰未使用过的页面，认为这样可以在总体上减少换页次数。CLOCK算法只考虑到是否被访问过，因此被访问过的当然尽可能留下来，未使用过的就淘汰。 而改进型CLOCK置换算法对任何使用过的页面又做了细分，分为使用过但未修改过和使用过且修改过。因此，若有未使用过的页面，实现把它换出，若全部页面都使用过，优先把未修改过的页面换出。

3.2.4 页面分配策略

页面分配策略
驻留集 指请求分页存储管理中给一个进程分配的内存块的集合。

固定分配vs 可变分配：区别在于进程运行期间驻留集大小是否可变
局部置换vs全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出

固定分配局部置换：进程运行前就分配一定数量物理块，缺页时只能换出进程自己的某一页

可变分配全局置换:只要缺页就分配新的物理块，可能来自空闲物理块，也可能换出别的进程的页

可变分配局部置换:频繁缺页的进程，多分配一些物理块；缺页率很低的进程，回收一些物理块；直到缺页率合适

何时调入页面？

• 预调页策略：一般用于进程运行前
• 请求调页策略：程序运行时，发生缺页再调页

从何处调页？
对换区：采用连续存储方式，速度快；
文件区：采用离散存储方式，速度慢

• 对换区足够大：运行前将数据从文件区复制到对换区，之后所有的页面调入调出都是内存和对换区之间进行
• 对换区不够大：不会修改的数据每次都从文件区调入；会修改的数据调入对换区，需要时再从对换区调入
• UNIX方式：第一次使用的页面都从文件区调入；调出的页面都写回到对换区，再次使用时从对换区调入。

3.2.5 抖动

抖动指页面频繁换入换出的现象。主要原因是分配给进程的物理块不够。

3.2.6 工作集

工作集指 在某段时间间隔内，进程实际访问页面的集合。
驻留集大小一般不能小于工作集。

王道习题

访问时间的计算

在没有快表的请求分页存储管理：如果缺页，需要访存三次（分别是：查页表1次（第一次），缺页之后调页（I/O）然后再查页表（第二次），之后访问目标单元（第三次））

在有快表的请求分页系统中：

分为三种线路；
1 ) 快表命中 ，访存1次
2 ）快表未命中，访问慢表，慢表命中，访存2次。

3）快表未命中，访问慢表，慢表缺页，需要调页I/O（很慢），然后查快表（肯定命中），访存2次。

本题正确答案如下

$0.8\ast 1us+0.2\ast 0.9\ast 2us+0.2\ast 0.1\ast (20ms+2us)=401.2us$

2021考研王道教材答案错误，错误答案给的是401.22us。

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的操作系统第三章-内存管理的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。