# 内存管理之二

# 虚拟内存管理

上文提到物理内存管理，但是物理内存管理有以下几个缺陷：

由于源程序直接使用物理内存地址，程序间容易访问冲突
由于程序必须全部装入内存才能运行，内存太小的话程序无法运行
由于程序占用连续一片内存，容易产生内存碎片
多程序同时运行容易互相干扰，因此不安全

相应介绍了几种改善物理内存管理的相关技术：

内存拼接
对换技术
覆盖技术

# 目标

使得大的程序在较小的内存中运行
使得多个程序能在较小的内存中运行
多个程序并发运行时地址不冲突
使得内存利用效率高，无碎片，易共享

# 实现思路

在程序运行时，只把当前必要的很小的一部分代码和数据装入内存中，其他代码当必要使用时再装入，不再运行的代码和数据及时从内存中删除。实际内存中很容易满足上述的内存需求

# 页式虚拟存储管理

# 基础概念

把进程空间和内存空间划分成等大小的小片，如1k、2k或4k等等。

页：进程的小片（虚拟页或页面）
页框：内存的小片（物理页）
内存以页框为单位来分配使用，进程以页为单位装入内存
- 只把程序的部分页装入内存便可运行
- 页在内存中占用的页框不必相邻
- 需要新页时，按需从硬盘调入内存
- 不再运行的页及时删除，腾出空间

# 页表和页式地址映射

虚拟地址（ $VA$ $V A$ ）可以分为页号 $P$ $P$ 和页内偏移 $W$ $W$
- 页号 $(P):VA$ 所处的页的编号 = $VA$ / 页的大小
- 页内偏移 $(W):VA$ % 页的大小

例子： $VA = 2500$ ；页面大小 $1K(10^{12})$

$P = 2500 / 1024 = 2$

$W = 2500 \% 1024 = 452$

实际计算机中，CPU运行乘除法很慢，因此真正计算的时候是（比如页的大小为 $2^n$ $2 n $ 单元）：
- 页号 $P = VA >> n$
- 页内偏移 $W =$ 低 $n$ 位 $={VA} \&\& (2^n - 1)$
页表记录页与页框之间的对应关系

页号	页框号	页面其他特性
0	5	……
1	65	……
2	13	……

页号：登记程序地址的页号
页框号：登记页所在的物理页号
页面其他特性：登记含存取权限在内的其他特性

# 页式地址映射

从一个虚拟地址（页式地址）——> 物理地址

分为三步：

从 $VA$ 分离页号 $P$ 和页内偏移 $W$
查页表：以 $P$ 为索引查页框号 $P^{'}$
计算物理地址 $MA$

$MA = P^{'} \times PageSize+ W$

# 快表技术（Cache）

快表：页表放在cache中；慢表：页表放在内存中

快表容量小，访问快，成本高。
快表是慢表的部分内容的复制。
地址映射时优先访问快表。

如果在快表中找到了所需的数据，就称为“命中”，没有命中时，需要访问慢表，同时更新快表。

合理的页面调度策略能使快表具有较高命中率。

# 页面共享技术

代码共享的例子：
文本编辑器占用多少内存？
文本编辑器代码占用150KB和数据占用50KB
有10进程并发执行该文本编辑器。

常规占用内存为

$10 \times(150 + 50) KB = 2M$

如果采用代码段共享，代码段在内存只有一份真实存储，占用内存为

$150 + 10 \times 50 = 650KB$

实现原理
- 在不同进程的页表中填入相同的页框号，多个进程就能访问相同的内存空间，从而实现页面共享。
- 共享页面在内存只有一份真实存储，节省内存。

# 缺页中断

现在操作系统中为三级存储体系，如果CPU所需的内容在Cache中，就称为命中，没有命中的话会从内存中进行获取，并将内容更新到cache中，如果主存中也不存在的话（因为只有一小部分程序会在内存中），则去辅存中寻找，这个过程称为缺页。

定义：在地址映射过程中，当所要访问的目的页不在内存中时，则系统产生异常中断——缺页中断。

缺页中断处理程序：中断处理程序把所缺的页草页表指出的辅存地址调入内存的某个页框中，并更新页表中该页对应的页框号以及修改中断位为0。

# 页表扩充——带中断位的页表

页号	页框号	中断位I	辅存地址
		0
		1

其中中断位I——表示该页是否在内存中。

如果 I = 1，不在内存
如果 I = 0，在内存中

辅存地址，该页在辅存中的地址

# 页表扩充——带中断位的页表

页号	页框号	访问位	修改位
		1	0
		0	1

访问位——标识该页是否最近被访问；修改位——标识该页是否已被修改。
641f2a63266fbad982f97d8e957bbc13

缺页率 $f$ = 缺页次数 $/$ 访问页面总次数

命中率 = $1 - f$

# 页面淘汰

选择淘汰哪一页的规则称淘汰策略。
一个页面在内存和辅存间频繁交换的现象称为页面抖动。
抖动会导致系统效率下降，因此应该避免。

# 最佳算法（OPT算法，Optimal）

思想：淘汰以后不再需要或最远的将来才会用到的页面

3dd0a8ae0c2ffd2814f765ffabeea7e7

理论上最佳，实际无法实现，不知道将来要访问什么页

# 先进先出算法（FIFO）

思想：淘汰在内存中停留时间最长的页

3a23b81c958deb8e43459dff9fd30d8c

进程只有按照顺序访问地址空间时页面命中率才最理想。
其次，对于一些特定的访问序列，随分配的页框增多，缺页率反而增加。
e9a2cc03fe9c646d51a35b68539324b6

# 最久未使用淘汰算法（LRU，Least Recently Used）

思想：淘汰最长时间未被使用的页面
745dfbb4d0b1f1220e1e9cb361613abd

LRU算法硬件实现：每个页面设置一个移位寄存器，当页面被访问时则将其重置为1，周期性地将所有页面的R左移1位，后面补0.选择R值最大的把它淘汰掉。
LRU软件实现：利用页表的访问位，当页被访问的时候值1，周期性地将所有访问位置0，当淘汰页面时根据访问位来判断淘汰，当访问位为1时，则说明在T时间内，该页被访问过，进行保留；当访问位为0时，则说明在T时间内，该页没有被访问过，淘汰该页。

# 最不经常使用算法（LFU）

思想：选择到当前为止被访问次数最少的页面，每页设置计数器，当被访问时加1，发生缺页中断，则淘汰数值最小的页面，将所有技术清零。

# 缺页因素分析和页式系统的缺点

# 缺页因素

淘汰算法
分配给系统的页框数
页面本身的大小
编程方法

# 页式系统的缺点

页面划分无逻辑含义（以固定大小被强行划分）
页面的共享不灵活（以页框为单位共享，有时候共享的代码仅仅是页框内的一部分）
页内碎片（如果代码没有充满页面，则有一部分被浪费）

# 段式虚拟存储管理

进程分段，把进程按照逻辑意义划分为多个段，每段有段名，长度不定，进程由多段组成

# 内存分配

段式系统的内存分配：

以段位单位装入，每段分配连续的内存
但是段和段不要求相邻

# 虚拟内存地址

段式虚拟地址 $VA$ 包含段号 $S$ 和段内偏移 $W$

# 段式地址的映射机制

需要用到段表，记录每段在内存中的映射位置。

段号	段长	基地址

S	L	B

段号：段的编号（唯一的）。
段长：该段的长度。
基地址：该段在内存中的首地址。

# 映射过程

逻辑地址 $VA$ 分离出 $S$ 、 $W$
查询段表：检索段号，查询该段基地址B和长度L
物理地址 $MA$ = $B$ + $W$

# 段表的扩充

类似页表，段表也可以进行扩充

# 段的共享

共享段在内存中只有一份存储
共享段被多个进程映射到各自的段表
需要共享的模块都可以设置为单独的段

# 段式系统的缺点

段需要连续的存储空间
段的最大尺寸收到内存大小的限制
在辅存中管理可变尺寸的段比较困难

# 段式系统VS页式系统

页式系统：一维地址空间
段式系统：二维地址空间

段与页的区别

段长可变/页长不可变
段的段分有意义/页面无意义
段方便共享/页面不方便共享
段用户可见/页面用户不可见
段偏移有溢出/页面偏移无溢出

# 段页式虚拟存储管理

在段式存储管理中结合页式存储管理（在段中划分页面）
段页式系统地址的构成：段号、页号、页内偏移。

# 段页式的映射机制

同时采用段表和页表实现映射

系统为每个进程建立一个段表
系统为每个段建立一个页表
段表给出每段的页表基地址及页表长度（段长）
页表给出每页对应的页框

← 内存管理之一内存管理之三 →