nightmorning的博客

1. 基础概念

内存：Memory，一级存储设备，与 CPU 进行高速交互，所有程序都得先从磁盘读取到内存才能运行

swap：一个程序从二级存储调入内存、调出内存的过程称

内存寻址：CPU 虚拟地址 => 物理地址

进程保护：检测地址范围

为了避免程序指针飘走，CPU 每次向 memory 操作数据之前都要确认地址是否“合法”，即满足该进程相应的 base 和 limit

分段寻址：先通过段号查表得到 limit 和 base，通过后物理地址就为 base + 段偏移量

• s：segment number，段号
• d：offset，段偏移量

2. 内存分配

Memory Allocation

I. 分配方法

Single-partition 方法

• 将内存分为若干 长度固定 的 partition
• 选择将进程装入空闲的 partition 中去（每个分区容纳一个进程）

Multiple-partition 方法

• 将内存分为若干 长度固定 的 partition
• 选择将进程装入空闲的 partition 中去（多个分区容纳一个进程）

Variable-partition 方法

• 用一张表记录空闲内存、占用内存
• 使用 动态存储分配算法，分配合适长度的 partition 给相应进程

II. 动态存储分配算法

• Fist Fit 算法：空闲分区以地址递增的次序连接，分配时沿该链搜索，找到大小满足要求的第一个空闲分区
• Best Fit 算法：空闲分区以大小递增的次序连接，分配时沿该链搜索，找到大小满足要求的第一个空闲分区
• Worst Fit 算法：空闲分区以大小递减的次序连接，分配时沿该链搜索，找到大小满足要求的第一个空闲分区

III. 存储碎片, Fragment

就是因为分配算法问题导致的存储空间浪费

外部碎片：夹杂在已分配内存中的不可利用内存

内部碎片：已分配内存中用不完浪费的内存

3. 分页, Paging

为了解决外部碎片的问题，采用分页技术，每个进程分为很多页置入内存

I. 地址转换

• 页：page，进程的逻辑地址空间分成若干等长部分
• 页框：frame，内存物理空间分成若干与页面大小相同的块（这个大小一般由计算机架构决定，保证可容纳任何单一指令）
• 页表：存储了页-帧的对应关系（即逻辑地址和物理地址的关系），通常还会有一个 valid 位，用于记录这个映射关系是否还有效
• 逻辑地址 = 页号 * 页大小 + 偏移量
• 物理地址 = 块号 * 页大小 + 偏移量

例题

II. 页表的存储

• 用一组专用寄存器存
• 将页表放到主存中，用 PTBR（page-table base rigister）指出页表的存放处
• 快表，TLB，Translation look-aside Buffer

由于页表存放在主存中，因此程序每次访存至少需要两次：一次访存获取物理地址，第二次访存才获得数据，于是 TLB 就诞生了。

TLB是一种高速缓存，访问速度远高于主存，用于缓存经常访问的页，因此，通过 TLB 访问的速度大约是一般访存的两倍

III. 进阶版页表

多级页表

Hash 页表

4. 虚拟存储

之前的内存管理都是将整个程序所有的页全部塞到内存里去，虚拟存储则是将部分程序放入内存，需要的时候再从磁盘中加载

可以预见的是虚拟存储是一个动态性很强的过程，将会发生大量页的置换

I. 页框分配

现在研究一下给进程分配 frame 的多少，假设有 n 个进程，内存中有 m 个页框

• 平均分配：每个进程 m/n 个页框
• 成比例分配：按照进程大小成比例分配
• 优先级分配：按照进程优先级先后分配

还有一种头铁的方法就是不分配，即 Pure Demand Paging，哪个进程需要用就用就直接从磁盘里往内存里薅

II. 页替换

缺页：page fault，进程需要的程序段不在内存中（换种说法就是页号对应的页表项 valid 位为 0）

发生缺页时，要求内存的不断从磁盘中取新的数据，当内存已经满了的时候，就需要将内存中的部分数据写回磁盘，再从磁盘中读取新的数据，这个替换过程就是页替换：

而这个替换分为 Global 替换和 Local 替换：

• Global：进程间没有边界，进程 A 可从进程 B 中抢 frame
• Local：进程间有边界，进程 A 的页替换只能发生在给自己分配的 frames 中

FIFO

字面意思，替换最早的页

这个策略可能会引起 Belady‘s anomaly，就是给每个进程分配的 frame 越多，缺页率反而上升的诡异现象，所以 FIFO 这个算法太粗暴了，不好

最优页替换

展望未来，将未来长一段时间不使用的页替换掉，理论上是最优的算法

显然这是个理想化的算法，因为不可能预知未来，所以这个算法经常作为一个标杆评价其他算法的性能

LRU

Least Recently Usage，回首过去，将没有使用时间最长的页替换掉

CLOCK

又叫做 Second-Chance 页替换算法，具体来说就是 FIFO + reference bit，每次引用页的时候将该页的 reference bit 置为 1，每次通过 FIFO 轮换到这个页时，如果 reference bit 为 1 可 ”豁免“ 一次替换

进阶版：使用两个比特位 (r, m)：

• r 表示 referred，该页面才被引用过
• m 表示 modified，该页面才被修改过

替换最好选择 (0, 0) 的这种页进行替换

LFU

Least Frequently Usage, 将最近使用频率最低的页替换出去

每个设置一个计数器，比如：硬件个每个页设置一个 8 位的历史位记录在 8 个间隔内页的使用情况：

• 00000000: 没用过
• 11111111: 每个间隔内至少使用一次
• 11000100: 在倒数 1，2，6 个间隔内至少使用一次
• 01110111: 在倒数 2，3，4，6，7，8 个间隔内至少使用一次

MFU

Most Frequently Usage，将最近使用频率最高的页替换出去，乍一看不太科学，但是仔细想想，刚被频繁使用的页是不是有可能已经完成了它的作用？所以还是有一定道理的~

III. Thrashing

评价一个页替换算法的好坏主要看是看缺页率，而缺页率会影响 CPU 访存时间：

effective access time = (1 - p) × 内存访问时间 + p × 缺页访问时间

而当一个进程没有足够多的页的时候，缺页率会变得非常高，这种现象就是 Thrashing，大幅度降低系统利用率：

下面介绍解决 trashing 的思路：

局部置换策略

当一个进程开始 trashing，如果采用的还是 global 替换，就会影响其他进程的运行，造成

frame 需求评估

如何评估 “有没有足够多的页” 呢?

Locality Model

所谓 locality，是指一堆互相关联的连续使用 pages，比如当一个函数被调用，它的一堆本地变量肯定会被连续使用，如果分配的 frames 数量不足以存储这些 page，就会发生 thrashing

Working-Set Model

为了找出这些 “互相关联使用的 pages”，使用 Working-set

• Δ：Working-set window 的大小
• WS：Working Set
• D：所有 Woring Set 大小的总和

当 D > 可分配的 frames 数量时，就会发生 Thrashing，所以应设一个 monitor，当检测到这种情况时，直接挂起一个进程，另外，woking-set 中的 frame 可以记录在 TLB 中去提升效率

PFF 控制策略

这个简单粗暴，直接监测缺页率，动态调整正在运行的进程数量，超过界限就对应的 挂起/开始 进程：

5. 内核内存的分配

内核内存分配的特征是：连续内存分配、变长分配

Buddy System

Slab allocation

• slab: 连续的页，cache 里一半会有数个 slabs

6. 总结

来个流程图整理下思路：