408操作系统—3.内存管理

内存管理
- 内存管理的概念
  - 内存管理概述
    - 什么是内存管理
    - 内存管理的功能
      - 内存分配回收
      - 地址转换
      - 内存空间扩充
      - 内存共享
      - 存储保护
  - 程序的链接与装入过程
    - 地址的区分
      - 物理地址
      - 逻辑地址
      - 相对地址
      - 绝对地址
    - 编译
    - 链接
      - 静态链接
      - 装入时动态链接
      - 运行时动态链接
    - 装入
      - 绝对装入
      - 可重定位装入
      - 动态运行时装入
  - 进程的内存映像
  - 内存保护
  - 内存共享
  - 内存分配与回收
    - 分配分类
    - 回收合并方法
- 内存管理方法
  - 连续分配
    - 单一连续分配
    - 固定分区分配
    - 动态分区分配
      - 基于顺序搜索
        
        首次适应算法
        
        临近适应算法
        
        最佳适应算法
        
        最坏适应算法
      - 基于索引搜索
        
        快速适应算法
        
        伙伴系统
        
        哈希算法
  - 基本分段存储管理
    - 概念
      - 分段
      - 逻辑地址结构
      - 段表
    - 地址转换
    - 段的保护和共享
  - 基本分页存储管理
    - 概念
      - 分页
      - 页面
      - 逻辑地址结构
      - 页表
    - 地址转换
      - 基本地址转换
      - 两级页表地址变换
      - 具有快表的地址变换
  - 段页式存储管理
    - 空间划分概念
    - 组成
      - 段表
      - 页表
      - 页表寄存器
      - 逻辑地址
    - 地址变换
    ‍
虚拟内存管理
- 虚拟内存基本概念
  - 传统存储管理方式特征
    - 一次性
    - 驻留性
  - 局部性原理
    - 时间局部性
    - 空间局部性
  - 虚拟存储器
    - 概念
    - 特征
      - 多次性
      - 对换性
      - 虚拟性
  - 虚拟内存实现
- 请求分页管理方式
  - 增加功能
    - 请求调页
    - 页面置换
  - 页表机制
    - 状态位
    - 访问字段
    - 修改位
    - 外存地址
  - 缺页中断
  - 地址变换机构
- 驻留集与页框分配
  - 驻留集大小的影响
  - 内存分配策略
    - 固定分配局部置换
    - 可变分配全局置换
    - 可变分配局部置换
  - 物理块调入算法
    - 平均分配算法
    - 按比例分配算法
    - 优先权分配算法
  - 请求分页系统外存组成
  - 调入页面时机
    - 预调页策略
    - 请求调页策略
  - 从何处调入页面
    - 对换区空间足够
    - 对换区空间不足
    - unix方式
- 页面置换算法
  - 最佳置换算法OPT
  - 先进先出置换算法LRU
  - 时钟置换算法
  - 改进型时钟置换算法
- 抖动和工作集
  - 抖动
    - 产生原因
  - 工作集
    - 如何确定工作集
    - 作用
- 内存映射文件
- 虚拟存储器性能影响因素
  - 页面
  - 物理块
  - 页面置换算法
  - 程序局部化程度
  - 内存映射文件
  - 存储访问方式

内存管理

内存管理的概念

内存管理概述

什么是内存管理

操作系统对内存的划分和动态分配
内存管理的功能
1. 内存空间的分配与回收
  
  由 OS 完成主存储器空间的分配和管理
2. 地址转换
  
  将程序的逻辑地址转换为内存种的物理地址
3. 内存空间的扩充
  
  利用虚拟存储技术从逻辑上扩充内存
4. 内存共享
  
  允许多个进程访问内存同一部分
5. 存储保护
  
  保证多道作业在各自存储空间运行，互不干扰

程序的链接与装入过程

物理地址：实际的硬件内存地址，由内存芯片直接访问
逻辑地址：程序员在编写程序时使用的地址，由 CPU 生成，并通过 MMU 转换为物理地址
相对地址：基于某个基准点的偏移量，需要与基准点结合来表示实际绝对地址
绝对地址：内存中的一个固定位置，是一个具体的固定数值，直接指向内存的一个存储单元

创建进程首先需要将程序和数据装入内存，将用户源程序变为可以在内存中执行的程序

编译

由编译程序将用户源代码编译成若干目标模块

目标模块：由源代码编译而来，还未被链接为最终可执行文件的**中间文件**，通常为机器代码的二进制表示
链接

由链接程序将目标模块和所需库函数链接，形成完整装入模块

装入模块：已经经过编译和链接处理，可以被操作系统装入内存并执行的**可执行文件**。装入模块通常包含了所有必要的代码、数据和资源，以便在运行时正确执行
1. 静态链接
  
  链接成完整装入模块后不再拆开
  
  由于编译后的目标模块都是相对地址，链接为装入模块时相对地址需要修改
  
  每个目标模块的外部调用符号也变化为相对地址
2. 装入时动态链接
  
  一组目标模块在装入内存时进行的链接操作，目标模块包含对动态链接库（DLL 或共享库）的引用，操作系统在加载程序时解析这些引用并加载相应的库
  
  便于修改和更新，可以实现目标模块（库文件）的共享，但增加加载时间
3. 运行时动态链接
  
  程序运行中需要用到某目标模块时再链接，未使用的目标模块都不会调入内存和形成装入模块
  
  能够加快程序装入过程，节省内存，需要额外代码管理库的加载和卸载
装入

装入程序将装入模块装入内存运行
1. 绝对装入
  
  只适用于单道程序环境
  
  编程时就将物理地址计算好，程序中的逻辑地址和实际内存地址完全相同
2. 可重定位装入
  
  也称为静态重定位装入，装入时根据实际情况调整程序的地址，将程序加载到合适的内存位置，把程序中的相对地址转换为物理地址
  
  必须一次分配所有所需内存，运行期间不能移动也不能再次申请内存空间，避免地址冲突
3. 动态运行时装入
  
  也称为动态重定位装入
  
  可以装入部分需要执行的代码分配相应内存地址，在程序运行期间根据动态需要申请内存，且申请的内存区可以不连续
  
  因此每分配一段内存地址都需要一个重定位寄存器，其中存放装入模块的起始位置
  
  通常与运行时动态链接结合发生

进程的内存映像

程序调入内存运行时，构成进程的内存映像

代码段

程序的二进制代码，只读，共享
数据段

包含全局变量和静态变量
bss 段

包含未初始化的全局变量和静态变量
进程控制块（见2️⃣进程与线程）
堆

动态内存分配，存放动态分配变量，通过调用 malloc 函数动态向高地址分配空间
栈

实现函数调用和存储局部变量，从用户空间最大地址往低地址方向增长

int global_var = 10;  // 数据段

int main() {
    static int static_var = 20;  // 数据段
    int local_var = 30;  // 栈
    int *heap_var = (int *)malloc(sizeof(int));  // 堆
    *heap_var = 40;
}

内存保护

确保每个进程都拥有单独的内存空间，有以下两种方法：

在 CPU 中设置⼀对上下限存储器，存放用户进程在主存中的下限和上限地址，判断 CPU 访问的地址是否越界
重定位寄存器（基地址寄存器）和界地址寄存器（限长寄存器）进行越界检查

前者存放进程起始物理地址

后者存放进程最大逻辑地址，即进程的内存段的长度（或界限）。它定义了进程可以访问的内存范围的大小。
1. 逻辑地址生成：进程生成一个逻辑地址用于访问内存
2. 越界检查：在将逻辑地址转换为物理地址之前，系统会进行越界检查：
  - 检查逻辑地址是否小于界地址寄存器的值（即逻辑地址是否在合法范围内）
  - 如果逻辑地址大于或等于界地址寄存器的值，则发生越界访问，系统会触发异常或错误处理机制
3. 地址转换：如果逻辑地址通过了越界检查，系统会将逻辑地址加上重定位寄存器的值，生成实际的物理地址
4. 内存访问：使用生成的物理地址进行内存访问
仅操作系统可以加载以上两个寄存器，不允许用户更改

内存共享

只有只读区域才可以共享，

纯代码/可重入代码=不能修改的代码，不属于临界资源

实际执行时，每个进程配有局部数据区，可能改变的部分将复制到数据区，只对各自的私有数据区内存进行修改，共享代码不改变

内存分配与回收

连续分配
1. 单一连续分配
  
  单道发展到多道 OS↓
2. 固定分区分配
  
  为了适应大小不同的程序 ↓
3. 动态分区分配
  
  更好提高内存利用率 ↓
不连续分配
1. 分段存储管理
  
  为了满足用户在编程和使用方面的要求
2. 分页存储管理
3. 段页存储管理

内存回收方法
1. 回收区与插入点的前一空闲分区相邻，此时将这两个分区合并，并修改前一分区表项的大小为两者之和
2. 回收区与插入点的后一空闲分区相邻，此时将这两个分区合并，并修改后一分区表项的始址和大小
3. 回收区同时与插入点的前、后两个分区相邻，此时将这三个分区合并，修改前一分区表项的大小为三者之和，并取消后一分区表项
4. 回收区没有相邻的空闲分区，此时应该为回收区新建一个表项，填写始址和大小，并插入空闲分区链

内存管理方法

连续分配

为用户分配一个连续的内存空间

内部碎片：当程序小于固定分区大小时，也要占用一个完整的内存分区，这样分区内部就存在空间浪费

单一连续分配

定义

内存分为系统区和用户区

系统区仅 OS 使用，用户区由一道程序独占
优点
1. 简单，无外部碎片
2. 无需进行内存保护
缺点
1. 只能用于单用户单任务系统
2. 存在内部碎片，存储器利用率极低

固定分区分配

定义

内存划分为若干固定大小分区，每个分区只有一道作业
优点
- 简单
缺点
1. 程序太大可能放不进任何分区，存在内部碎片
2. 不能实现多进程共享一个主存区，存储空间利用率低

动态分区分配

概念

可变分区分配

动态分区在作业装入时动态建立，装入使用的大小即分区大小

随时间推移容易出现外部碎片

外部碎片：存在于所有内存分区的外部，区别于内部碎片
基于顺序搜索的分配算法
1. 首次适应算法
  
  按地址递增的次序排列，分配第一个能满足大小的空闲分区
  
  保留了高地址部分大空闲分区
  
  低地址部分产生大量碎片，增加查找开销
2. 邻近适应算法(循环首次适应算法)
  
  与前者相比，从上次查找结束的位置继续开始查找
  
  导致高地址部分无大空闲分区，比前者适应性更差
3. 最佳适应算法
  
  按**容量递增**次序排列，分配第一个能满足大小的空闲分区
  
  将留下越来越多难以利用的内存碎片，产生外部碎片最多
4. 最坏适应算法
  
  按容量递减次序排列，分配当前最大的空闲分区
  
  将导致没有大分区可用，性能也很差
基于索引搜索的分配算法

根据大小对空闲分区分类，每个分类设立一个空闲分区链，用一个索引表管理空闲分区链
1. 快速适应算法
  
  找到能容纳的最小空闲分区链表，取出链表第一块空间
  
  查找效率高，不产生内部碎片
  
  回收分区需要有效合并分区，系统开销大，复杂
2. 伙伴系统
  
  所有分区大小均为 $2^k$，需要分配大小为 n 的分区时 $(2^{i-1}<n\leqslant2^{i})$，在大小为 $2^i$ 的空闲分区链中分配
  
  耗尽则在 $2^{i+1}$ 中分配，若有，拆分该分区为两个 $2^i$ 大小分区，一个分配，另一个加入前一空闲分区连，称为一对伙伴
  
  以此类推，回收时，也可能需要对伙伴分区合并
3. 哈希算法
  
  构建以空闲分区大小为关键字的哈希表，记录空闲分区链的头指针
  
  由所需分区大小，在哈希表中由哈希函数查找到头指针位置，得到空闲分区链表

只要没有连续的足够大小的空间即无法分配

因此有非连续分配方式，由分区大小是否固定分为分页与分段

分页中由是否需要整个作业装入内存中分为基本分页和请求分页

基本分段存储管理

概念
1. 分段
  
  将用户进程分隔为若干个带有属性的逻辑分段，段内地址连续，段间地址不连续
2. 逻辑地址结构
  
  逻辑地址由 段号S 与 段内偏移量W 两部分构成，前 16 位表示段号，后 16 位表示偏移量，因此进程最多 $2^{16}$ 段，最大段长 64KB
  - 段号
    
    用于在段表中查找对应表项
  - 段内偏移量
    
    用于与基地址配合计算对应物理地址
3. 段表
  
  一张逻辑空间与内存空间的映射表，一个段对应一个段表项，一个进程通常只拥有一个段表
  
  段表记录段在内存中的 基地址b 和 段长C
  - 基地址
    
    用于与段内偏移量计算对应物理地址的基准地址
  - 段长
    
    防止偏移量越界的限制
  段号段长在主存的始址
  
  段表存储于段表寄存器中，段表寄存器存储了 段表始址F 与 段表长度M
4. 地址变换
  
  见下图 2，将逻辑地址 A 映射为物理地址 E
  1. 取出 逻辑地址A 的 段号S 和 偏移量W
  2. 判断段号是否越界，若 S>=M，则越界中断，否则执行
  3. 查询段号对应段表项，段表项地址=F + S * 段表项长度
  4. 取出 段长C，若 W>=C，则产生越界中断，否则继续执行
  5. 取出 始址b，计算物理地址 E=b+W
段的共享和保护
- 共享
  
  两个作业的段表中相应表项指向被共享段，共享段应只读
- 保护
  - 存储控制保护
    
    如地址变换过程 2
  - 地址越界保护
    
    如地址变换过程 4
优点
1. 有利于反映程序的逻辑结构，利于动态链接及编程
2. 分段保护，分段共享
3. 段的大小可以动态调整
缺点
1. 产生外部碎片
2. 内存交换效率低

基本分页存储管理

概念

分页

将整个虚拟和物理内存空间切成一段段固定尺寸的分区称为页框、页帧或物理块
页面

进程逻辑地址空间由与物理块大小相等的页面组成

也即页面和物理块是大小相等的

页大小为页的字节数，2的幂次方，通常4KB

页面大———内部碎片变多，降低利用率

页面小———页面数变大，页表长，增加地址转换开销
逻辑地址结构

地址结构包含 页号P 和 页内偏移量W
- 页号
  
  用于在页表中查找对应的物理块号
- 页内偏移量
  
  用于与页号结合在内存的一个物理块中查找实际的地址
  
  标识逻辑地址在特定页内的位置
  
  页内偏移量的位数等于页大小的对数$log_2(Page Size)$
以 2 的整数次幂划分页面大小时，物理块大小通常为4KB，$\log_2{4KB}=12位$，即一个页内偏移量需要用12位表示

假设逻辑地址由32位组成

则低12位 $0\sim11$ 为页内偏移量，高$31-12=19$位12~31 为页号，即一个进程最多可以分配 $2^{20}$ 页

以下为24位逻辑地址计算例子
```
逻辑地址: 0x1234AB
二进制表示: 0001 0010 0011 0100 1010 1011
逻辑地址由24位组成
+-------------------+--------------------+
|     页号 (高8位)   |  页内偏移量 (低16位) |
+-------------------+--------------------+
|    0001 0010      | 0011 0100 1010 1011|
+-------------------+--------------------+

页号: 0x12 (18)
页内偏移量: 0x34AB (13483)
```
页表

实现从页号到物理块号的映射

页表项由页号和块号组成

页表的起始地址和页表长度放在页表寄存器 PTR 中
进程未执行时，存放于PCB中，进程调度时，存入PTR中

页表存储于内存中，内存管理单元 MMU 负责将虚拟地址转换为实际物理地址
- 页号
  
  不存储于页表中，页表项连续存放，页号可以隐含，不占存储空间
- 页表项
  - 物理块号
    
    指示逻辑页在物理内存中的位置
  - 额外信息
    
    通常占用4位
1B = 8位，逻辑地址空间大小$=2^{逻辑地址位数}B$

假设一个逻辑地址空间32位表示，一页面4KB，1B表示一个地址

则逻辑地址空间大小为：$2^{32}B=4GB$

逻辑地址空间内页数：$\frac{2^{32}B}{4KB}=\frac{2^{32}}{2^{12}}=2^{20}=1048576页$，也即该系统内一个进程最多$2^{20}$页，页面号需要20位表示

则页表项大小至少为$20+4=24位=3B$

页表大小：$页数\times页表项大小=1048576\times3=3145728B=4GB$

地址转换

基本地址转换

由逻辑地址A转换物理地址E

由A计算出页号P和页内偏移量W
在页表中查找P对应的物理块号F，若P>页表长度M则越界中断
将F与W组合生成物理地址

页号: 0x12 (18)
页内偏移量: 0x34AB (13483)

页号 18 对应的物理块号: 7

物理地址计算:
物理页框号起始地址: 7 * 4KB = 28672 (0x7000)
物理地址: 28672 + 13483 = 42155 (0xA4AB)

两级页表地址变换

单级页表处理大地址空间时，需要占用大量连续的内存地址空间来保存页表，解决办法如下：

页表所需内存空间，离散分配，用一个新的页表记录离散分配的页表位置
需要页表的部分存入内存，其余驻留硬盘

新的页表称为**外层页表（页目录）：**记录二级页表的基地址

**外层页表寄存器（页目录基址寄存器）：**存放外层页表起始地址

32位的虚拟地址可以分解为三个部分：

一级页表索引：用于索引一级页表（页目录表）
二级页表索引：用于索引二级页表（页表）
页内偏移

通常将原页表按照每一部分刚好能用一物理块存储拆分为二级页表，此时每个二级页表都为4KB，页表项1024个，需要10位表示二级页表索引

32位地址需要12位表示偏移，一二级页表索引都为10位

虚拟地址: 0x12345678(0001 0010 0011 0100 0101 0110 0111 1000)

虚拟地址一级页表索引 (10位) 二级页表索引 (10位) 页内偏移 (12位)

0x12345678 0001 0010 00 11 0100 0101 0110 0111 1000

一级页表索引查找一级页表，得到二级页表的基地址，例如 0x2000

二级页表索引查找二级页表，得到物理页框的基地址，例如 0x3000

页内偏移0110 0111 1000 0x678

计算得物理地址 = 0x3000 + 0x678 = 0x3678

虚拟地址	一级页表索引 (10位)	二级页表索引 (10位)	页内偏移 (12位)
0x12345678	0001 0010 00	11 0100 0101	0110 0111 1000

对于64位地址空间，两级分页时，页面大小设为4kb，页表项大小4B

则逻辑地址空间内页数为$64-12页内偏移-10二级页表索引=42$

则外层页表需要占用16384GB连续内存空间

因此更大的逻辑地址空间必须使用多级页表

具有快表的地址变换

地址变换机构中增设能够并行查找的高速缓冲存储器——快表（TLB,相联存储器）

TLB存储最近使用的虚拟地址到物理地址的映射

存在TLB时，首先查找TLB，有则使用，无则查找页表并将映射添加进TLB

段页式存储管理

如何划分空间

结合分段与分页
1. 程序划分为多个有逻辑意义的段
2. 分段出来的连续空间再分页
组成
- 段表
  
  每个进程都有一张段表，段表包含段号、页表长度、页表始址
  
  每个段表项都用于找到一个页表
- 页表
  
  页表中包含页号和块号
- 段表寄存器
  
  指出进程的段表始址和段表长度，兼具判断逻辑地址段号是否越界的功能
- 逻辑地址
  
  逻辑地址由段号、页号、页内偏移量组成
地址变换
1. 逻辑地址段号S，配合段表寄存器中的段表始址，确定段表项，同时判断段号是否越界
2. 通过段表得到对应页表始址，配合逻辑地址页号，得到物理块号
3. 物理块号，配合逻辑地址页内偏移量，得到具体物理地址

虚拟内存管理

虚拟内存概念

传统存储管理方式特征

一次性

作业必须一次全部装入才能开始运行
驻留性

作业被装入内存后，就一直驻留在内存中，直到作业结束

运行中的进程会因等待I/O而被阻塞，可能处于长期等待状态

局部性原理

时间局部性

程序中的某条指令一旦执行，不久后该指令可能再次运行;出现的原因是程序中存在着大量的循环结构
空间局部性

程序在一段时间内所访问的地址，可能集中在一定的范围内

虚拟存储器

定义

系统为用户提供的比实际内存容量大得多的存储器，虚拟存储器位于外存
特征
1. 多次性（最重要特征）
  
  当前正在运行的部分程序和数据装入内存即可运行，无需完全装入
  
  每运行到还没有调入的部分数据时，再调入
2. 对换性
  
  作业无需常驻内存，需要使用时换入，不需要使用时换出
3. 虚拟性（目标）
  
  从逻辑上扩充内存容量

虚拟内存实现

必须建立在离散分配的内存管理方式上，不能用于连续分配

方式
- 请求分页存储管理
- 请求分段存储管理
- 请求段页式存储管理
所需
1. 一定容量的内外存
2. 页表/段表机制
3. 中断机构，访问未调入内存部分时，产生中断
4. 地址变换机构，逻辑地址到物理地址的变换

请求分页管理方式

相比分页增加的功能

请求调页功能

将需要的页面调入内存
页面置换功能

将不用的页面换出外存

页表机制

状态位

标记是否已调入内存
访问字段

记录本页在一段时间内被访问次数，或记录未被访问时间
修改位

标记进入内存后是否被修改，决定换出时是否写回外存
外存地址

记录在外存的存放地址，通常为物理块号

页号	物理块号	状态位P	访问字段A	修改位M	外存地址

缺页中断

定义

CPU取指令或读写数据时发生，属于异常
产生时间
1. 访问页面不在内存中，请求OS将缺页调入内存
2. 缺页进程阻塞，调页完成唤醒，唤醒后
3. 调页时若有空闲则装入，修改页表对应表项；若无空闲则选择一页淘汰并存入外存
特点
1. 发生于一条指令执行的过程中
2. 一条指令过程中可能发生多次缺页中断

地址变换机构

在基本分页基础上，增加产生和处理缺页中断以及从内存中唤出一页的功能

地址变换过程

驻留集与页框分配

驻留集概念

给一个进程分配的物理块的集合
驻留集大小
1. 驻留集越小，驻留内存中进程越多，提高并发度，但导致缺页率较高，CPU耗费大量时间来处理缺页
2. 驻留集过大，对缺页率的改善是不明显的，浪费内存空间，导致多道程序并发度的下降
内存分配策略
1. 固定分配局部置换
  
  物理块固定，缺页时先换出自身一个页再调入所缺页
2. 可变分配全局置换
  
  物理块可变，缺页时增加物理块再调入所缺页
3. 可变分配局部置换
  
  物理块可变，若不频繁缺页则用局部置换，频繁缺页再用全局置换
物理块调入算法
- 平均分配算法
- 按比例分配算法
- 优先权分配算法
请求分页系统外存组成

存放文件的文件区，存放对换页面的对换区（交换区）

对换区的磁盘读写速度更快
调入页面时机
- 预调页策略
  
  运行前的调入
  
  主要用于进程的首次调入，由程序员指定
- 请求调页策略
  
  运行时的调入
  
  调入的页一定会被访问，每次仅调入一页，将增加开销
从何处调入页面
1. 对换区空间足够
  
  全部从对换区调入所需页面，提高调页速度
2. 对换区空间不足
  
  不会被修改的文件由文件区调入
  
  可能会被修改的文件换出到对换区，需要时由对换区调入
3. UNIX方式
  
  未运行过的页面都应从文件区调入
  
  曾经运行过但又被换出的页面，放在对换区，因此在下次调入时应从对换区调入
  
  共享页面若被其他进程调入内存，则不需要再调入
如何调入页面
- 情况1
  
  访问页面不在内存—>缺页中断—>无空闲物理块—>决定淘汰页—>调出页面—>调入所缺页面
- 情况2
  
  访问页面不在内存—>缺页中断—>有空闲物理块—>调入所缺页面

页面置换算法

选择调出页面的算法——页面置换算法，追求更低的缺页率

最佳置换算法OPT

置换时，淘汰未来最长时间内未被访问的页面，或以后永不使用的页面

基于队列算法实现

由于无法判断，无法实现该算法，只能用于评价其他算法

先进先出置换FIFO

淘汰当前最早进入内存页面

没有利用局部性原理性能差，会出现Belady异常，实现简单

Belady异常

为进程分配的物理块增多，缺页次数不减反增

最近最久未使用置换算法LRU

淘汰最近最长时间未使用页面

使用堆栈算法，需要对所有页排序

性能好，实现复杂，需要寄存器和栈道硬件支持

时钟（CLOCK）置换算法

循环检查访问位A，需要置换页面时，检查当前指向的页面，为1置0检查下一个，为0换出指向下一个页面

首次进入内存或被访问时置为1

也称为最近未用（NRU）算法

改进型CLOCK置换算法

换出被修改过的页面需要存回硬盘中，代价较大

增加一个置换代价——修改位M，换出页面时优先考虑未使用又未修改的页面

A=0,M=0:最近未被访问，且未被修改，是最佳的淘汰页
A=0,M=1:最近未被访问，但已被修改，是次佳的淘汰页
A=1,M=0:最近已被访问，但未被修改，可能再被访问
A=1,M=1:最近已被访问，且已被修改，可能再被访问

算法执行时扫描流程如下：

从当前位置扫描0,0，将遇到的第一个淘汰，不改变A
扫描0,1，淘汰，将扫描过的A都置0
再次进行第一步，若仍无，进行第二步，此时一定有符合页面

改进型能够减少磁盘I/O，但是增加算法本身开销

系统中页面置换算法的原则，尽可能保留访问过的页面，淘汰未访问页面

抖动和工作集

抖动
1. 定义
  
  页面置换中，出现频繁调度行为，刚换出就换入，刚换入就换出，称为抖动或颠簸
2. 产生原因
  
  系统中同时运行的进程太多一>分配给每个进程的物理块太少一>进程在运行时频繁出现缺页一>频繁的调动页面
  
  主要原因是系统置换算法不合理
工作集
1. 定义
  
  在某段时间间隔内，进程要访问的页面集合
2. 如何确定工作集
  
  基于局部性原理，用最近访问过的页面来确定
3. 作用
  - 反映了接下来一段时间内很有可能会频繁访问的页面集合
  - 防止抖动现象，驻留集大小必须大于工作集大小

内存映射文件

定义

与虚拟内存相似，将磁盘文件的全部或部分内容与进程虚拟地址空间的某区域建立映射关系
作用

直接访问被映射的文件，不需要进行文件读写操作

不实际读入文件内容，只在访问时每次一页读入

退出或关闭映射时，将文件修改一次写回磁盘
优点

便于多进程共享同一磁盘文件

共享存储，实际上是通过映射相同文件到通信进程的虚拟地址空间实现的，同一个文件在不同虚拟地址空间中独立

虚拟存储器性能影响因素

页面
1. 页面较大->缺页率较低->可以减少页表长度，但使得页内碎片增大
2. 页面较小
  
  ->缺页率较高
  
  ->可以减少内存碎片，提高内存利用率
  
  ->使得页表过长，占用大量内存
物理块
1. 分配给进程的物理块数越多，缺页率就越低
2. 分配给进程的物理块数超过某个值时，对缺页率的改善并不明显
页面置换算法
1. 好的页面置换算法可以使进程在运行过程中具有较低的缺页率
2. LRU，CLOCK将未来可能要用到的进程保存在内存中，可以提高页面的访问速度
编写程序的局部化程度越高，执行时的缺页率越低
使用内存映射文件暂存文件修改，减少磁盘读写次数
存储和访问尽量使用系统的访问方式(如都按行存储就按行访问)