操作系统1:内存管理

正文索引 [隐藏]

1. 基础概念

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

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

image-20191213173821042

内存寻址:CPU 虚拟地址 => 物理地址image-20191213173311544

进程保护:检测地址范围

image-20191213172511789

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

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

image-20191213202200094

  • 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

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

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

image-20191213201348548

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

image-20191213201316239

3. 分页, Paging

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

I. 地址转换

image-20191213203343089
image-20191213225222459

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

例题

image-20191213234724779
image-20191213234801910
image-20191213234816408

II. 页表的存储

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

image-20191213230103186

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

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

III. 进阶版页表

多级页表

image-20191213235756679

Hash 页表

image-20191213235839200

4. 虚拟存储

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

image-20191214000332327

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

image-20191214001334741

I. 页框分配

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

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

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

II. 页替换

缺页:page fault,进程需要的程序段不在内存中(换种说法就是页号对应的页表项 valid 位为 0)

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

image-20191214092258654

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

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

FIFO

字面意思,替换最早的页

image-20191214092437667

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

最优页替换

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

image-20191214092912796

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

LRU

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

image-20191214093350222

CLOCK

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

image-20191214094354774

进阶版:使用两个比特位 (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,大幅度降低系统利用率:

image-20191214101224874

下面介绍解决 trashing 的思路:

局部置换策略

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

frame 需求评估

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

Locality Model

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

Working-Set Model

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

image-20191214102029381

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

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

PFF 控制策略

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

image-20191214102944354

5. 内核内存的分配

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

Buddy System

image-20191214104510364

Slab allocation

image-20191214104543988

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

6. 总结

来个流程图整理下思路:

image-20191214105408033