【操作系统】内存管理

一、内存管理概述

创建进程首先要将程序和数据装入内存中。

1. 编译：将原代码编译成几个模块；
2. 链接：形成完整的 逻辑地址 ；
3. 装入：形成 物理地址 ；

解释一下逻辑地址和物理地址的区别：

比如有一支球队入住酒店，球员的号码是 1、2、 3、4；入住的酒店房间号分别是 5、 6、 7、 8；那么无需记住所有的房间号，只需要记住 1 号球员住的是 5 号房间即可，因为要想知道谁的房间号只需要 +1 即可。

这里有相对地址和绝对地址，相对地址就是别的球员相对于 1 号球员的位置，绝对地址是他们实际居住的房间号，相对地址就是内存中的逻辑地址，而绝对地址就是物理地址。

在执行装入的时候，也就是将逻辑地址转化为物理地址的时候，有 3 种方式：

• 绝对装入：事先知道 1 号球员的位置，对应的其他球员位置只需 +1 即可；
• 静态重定位：装入时进行地址转化，一旦装入 不能在内存中移动 ，因为装入只执行一次，移动了地址就变了；
• 动态重定位：在执行时进行地址转换，可以在内存中移动，需要一个重定位寄存器的支持；

内存分配方式有两大类：

• 连续分配管理方式；
• 非连续分配管理方式；

1、连续分配管理方式

• 单一连续分配：实现简单，无外部碎片，有内部碎片；
• 固定分区分配：无外部碎片，有内部碎片；
• 动态分区分配：不预先划分内存，在进程装入内存时，根据进程的大小动态的建立分区，没有内部碎片，有外部碎片；

解释一下什么是内部碎片和外部碎片：

总共有 10 颗糖，给张三分配了 5 颗，给李四分配了 4 颗，所以总共还剩下 1 颗，这一颗糖就是 外部碎片 ；给张三分配的 5 颗糖他没吃完，只吃了 3 颗糖，那么还剩下 2 颗糖，这两颗糖就是 内部碎片 。

动态分区分配算法：

1. 首次适应算法 First-Fit：按照 地址递增 的顺序排列，选第一个满足要求的空闲分区；
2. 最佳适应算法 Best-Fit：按照 容量递增 的顺序排列，选第一个满足要求的空闲分区；
3. 最坏适应算法 Worst-Fit：按照 容量递减 的顺序排列，选第一个满足要求的空闲分区；
4. 邻近适应算法 Next-Fit：由首次适应算法演变而来，不同的是分配内存时从上次查找结束的位置继续查找；

首次适应算法是最简单也是最好和最快的。

2、非连续分配管理方式

他和连续分配管理方式的区别就像是数组和链表的区别。

非连续的方式又分为两种：

• 分页存储管理；
  • 基本分页存储管理方式：一次性的将所有的页面装入内存；
  • 请求分页存储管理方式：动态的将页面装入内存中；
• 分段存储管理；

这是整个内存管理的重点，所以单独成章讲解。

二、基本分页存储管理方式

1、基本概念

分页技术就是将整个内存分为很多个 块 ，同时也将进程分为很多个 块，然后将这些块一一对应的塞进内存里去就可以了。

那为什么叫分页而不叫分块呢？

因为 块 在进程中被称为 页，在内存中被称为 页框 或者 物理块 ，在外存中直接成为 块。

页 的地址结构由 页号 和 页内偏移量 组成。

这两个都是可以直接求出来的：

偏移 = 逻辑地址 % 页长;
页号 = 逻辑地址 / 页长;

如果题目中用二进制给出了以上数据，每个页面大小是 2K B ，用二进制表示逻辑地址，则末尾 K 位是页内偏移量。

我们之前说了，内存中的块和进程的块是一一对应的，那么怎么知道这个对应关系呢，最简单的方式就是建立一张表，就像数据库中的数据表一样。

所有页表就诞生了，它的每一行都是一个页表项，左边是 页号 ，右边是 物理块号 。

这样就能根据页号知道物理块号了，进而算出物理地址。

现在总结一下求实际物理地址的步骤：

1. 算出逻辑地址的页号；
2. 查页表得到该页号对应页面在内存中的起始位置；
3. 算出逻辑地址在页面中的偏移量；
4. 物理地址 = 起始地址 + 偏移量；

2、地址变换机构 ?

将逻辑地址转化为物理地址需要用到一个很重要的机构——基本地址变换机构。

通过该机构将逻辑地址 A 转换为物理地址 E 的过程如下：

已知：
	页表长度 M
	页面大小 L
	逻辑地址 A

求：
	物理地址 E

1、计算页号 P 和页内偏移量 W ;
	P = A / L;
	W = A % L;
	
2、比较页号 P 和页表长度 M，如果 P >= M，则发生越界中断，否则继续执行；

3、通过查询页表可以根据页号 P 得到物理块号 b；

4、得到逻辑地址 E
   E = b * L + W；

以上过程都是由硬件自动完成的。

例子：

题目：
	页面大小 L 为 1KB ；
	已知页表中一行为页号 2 对应物理块号 b=8 ；
	逻辑地址是 2500；

求物理地址 E ：
	1、P = 2500 / 1K = 2; W = 2500 % 1K = 452;
	2、查询页表得到 2 号页对应的物理块号为 8;
	3、E = 8 * 1024 + 452 = 8644B。

3、快表

根据局部性原理，我们可以在此基础上引入快表。

局部性原理就是：时间局部性和空间局部性，前者指执行了该页面之后不久后还会执行，后者指执行了该页面之后它附近的也会执行。

引入块表之后的地址变换过程如下：

1. 得到逻辑地址，由硬件进行地址转换，将页号送入 高速缓存寄存器，并去块表查询；
2. 如果在快表中找到了，那么直接取出物理块号，算出物理地址，这样只需访问内存一次即可；
3. 如果在块表中没有找到，则需要访问主存中的页表，读出物理块后将该项放入块表，以便后面可能再次访问。

这部分内容经常会考察关于时间的计算，下面是一个例题：

假设一个页式存储系统具有快表，多数活动页表项都可以存在其中。若页表存放在内存中，内存访问时间是 1us 检索快表的时间为 0.2us 若快表的命中率是 85% ，则有效存取时间是多少? 若快表的命中率为 50% ，则有效存取时间是多少?

因为快表命中时只需访问内存一次，块表未命中时需访问内存两次，所以计算结果如下：

(0.2 + 1) * 85% + (0.2 + 1 + 1) * (1 - 85%) = 1.35 us;
(0.2 + 1) * 50% + (0.2 + 1 + 1) * (1 - 50%) = 1.7 us;

还有一块比较重要的内容是 多级页表 。

4、多级页表

我们之前的假设都是页表用一个页面就够了，也就是说一个页面可以装下所有的页表项，但是如果页表项太多了，我们 需要很多个页面才能装下所有的页表项 ，这些页面管理起来会很麻烦，就可以将这些页面作为 页目录表项 存放在一个最终的页面中，这个母页面就叫 页目录表 。

规定页目录表的大小只能是 1 页。

来看一道题目：

某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为 210 B，页表项大小为 2B，逻辑地址结构为： 页目录号-页号-页内偏移量 逻辑地址空间大小为 216 页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是多少？

一页可以有 2^10B / 2B  = 2^9 个页表项;
总共有 2^16 页,所以需要 2^16 / 2^9 = 2^7 个页面保存页表项;
这 2^7 个页面可以抽象为页目录表项保存在页目录表中;
所以至少为 128 个.

已知系统为 32 位实地址，采用 48 位虚拟地址，页面大小为 4KB ，页表项大小为 8B 。 1、假设系统使用纯页式存储，则要采用多少级页表?页内偏移多少位? 2、假设系统采用一级页表，TLB 命中率为 98%，TLB访问时间为 10ns ，内存访问时间为 100ns ，并假设当 TLB 访问失败时才开始访问内存，问平均页面访问时间是多少 ? 3、若是二级页表，页面平均访问时间是多少 ?

1、 页面大小: L = 4KB = 2^12 B; 页表项: 8B = 2^3 B;
	由此可得每一页可以放 2^12 / 2^3 = 2^9 个项;
	总共有 48 位虚地址，页偏移地址占了 12 位，还剩下 36 位是页号;
	36 / 9 = 4;
	所以需要 4 级页表.

2、 (10 + 100) * 98% + (10 + 100 + 100) * (1 - 98%) = 112ns;
3、 (10 + 100 + 100) * 98% + (10 + 100 + 100 + 100) * (1 - 98%) = 114ns;

三、请求分页存储管理方式 ?

1、虚拟存储器

请求分页存储管理是为了实现 虚拟存储器 而实现的，他和不同的分页存储最大的区别就是不会把相关页面一次性全部调入内存。

虚拟存储器容量的求法：

• 最大容量：CPU 的寻址范围；
• 实际容量：min(内存 + 外存，CPU 的寻址范围)

2、逻辑结构

在页表的基础上增加了 4 个字段：

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

• 状态位：是否已经调入内存；
• 访问字段：已有多长时间未被访问；
• 修改位：是否被修改过；
• 外存地址：该页在外存上的地址，通常是物理块号。

当我们访问的页面不在内存中时，会发生 缺页中断 。

3、地址变换机构

请求分页的地址变换较为复杂，这里大致的叙述一下：

先查询快表中有没有，没有则查内存，如果内存中也没有就发生缺页中断，缺页中断处理完成之后会将一个新的页面调入内存中，这时还会将这条记录写进快表中。

这里常考的时间计算，方法总结一下：

1. 快表中有：t快 + t内；
2. 快表中无：t快 + t内 + t内；
3. 缺页中断：t快 + t内 + t中断 + t快 + t内；

4、页面置换算法 ?

页面置换算法决定应该换入哪一页，换出哪一页。

常用的有四种：

• 最佳页面置换算法 OPT；
• 先进先出页面置换算法 FIFO；
• 最近最久未使用置换算法 LRU；
• 时钟置换算法 CLOCK；

OPT 几乎无法实现；
FIFO 性能差，实现简单；
LRU 性能好，但是实现困难；
CLOCK 想能接近 LRU，实现开销较小；

4.1、最佳页面置换算法 OPT

做题秘诀：当前位置往右数，最后一个首次出现的页号就是要淘汰的页面；

4.2、先进先出页面置换算法 FIFO

会发生贝拉迪异常；

做题秘诀：先进来的先淘汰；

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

需要硬件支持：寄存器和栈。

做题秘诀：逆向检查此时咋内存中的页面，最后一个首次出现的页号就是要淘汰的页面；

4.4、时钟置换算法 CLOCK ?

增加一个使用位，1 表示最近使用过，0 表示最近没使用。

1. 页面首次装入内存时，使用位设置成 1 ；
2. 第一轮扫描：扫描使用位是 0 的页面，每当遇到一个使用位为 1 的页面时，将它改为 0 ；
3. 如果扫描到了本来就是 0 的页面就替换它，没扫描到的话继续第二轮扫描；
4. 第二轮扫描：扫描为 0 的页面，这次肯定有了。

如果某一页被置换了，那么下一轮开始时指针指向下一个页面。

所以叫 CLOCK 算法，又称为最近未用算法，就找那些最近没使用的页面。

事实上，上述算法存在问题，只有当被淘汰的页面被修改过时才需要写回外存。

下面介绍改进型的时钟置换算法。

它引入一个新的状态叫修改位：修改位为 1 表示修改过，为 0 表示没修改过；

现在有一下几种情况：
（0,0）最近未被访问，未被修改
（0,1）最近未被访问，被修改了
（1,0）最近被访问了，未被修改
（1,1）最近被访问了，也被修改

优先级是递减的，即先淘汰上面的页面，没有才往下走。

1. 第一轮找 （0,0）
2. 第二轮 置使用位为零 并找 （0,1）
3. 第三轮找 （0,0）
4. 第四轮找 （0,1）

使用改进型的算法淘汰一个页面最多需要进行四次扫描。

例题：

参考答案：

四、基本分段存储管理方式

之前的分页是直接将整个内存划分成为相等大小的页面，而分段是按照程序的 逻辑功能 划分的。

它的逻辑地址结构如下：

段号		段内偏移量
 S			W

段号表示这个作业最多有多少段，段内偏移量表示该段的最大段长是多少。

和页表一样，也有段表：

段号		段长		本段在主存的始址

地址变换机构：

通过该机构将逻辑地址 A 转换为物理地址 E 的过程如下：

已知：
	段表长度 M
	逻辑地址 A

求：
	物理地址 E

1、从逻辑地址 A 中取出前几位为段号 S ，后几位就是段内偏移量 W ；

2、比较段号 S 和段表长度 M ：若 S >= M ，则发生越界中断，否则继续执行；

3、通过查询段表得到段长 C，如果 W >= C，则发生越界中断，否则继续执行；

4、	取出段表项中的始址 b；
	得到逻辑地址 E = b + W；

注意和页表不同的是查询段表之后还要在进行一次越界中断检测，即 偏移量不能大于段长。

最后提一嘴 段页式管理方式 ；?

他就是将两者结合了，先分段再分页 ?。