略谈OS存储管理-白红宇

存储管理是OS的重要组成部分，负责管理计算机系统的重要资源——内存存储器。任何程序和数据都需要一个载体存储，以在计算机中执行或处理。

1. 存储器体系层次

一系列硬件被研发出来以存储信息，我们希望它具有以下属性：

稳定性：不受外界影响正确地存储数据（SRAM就具有易失性，断电则数据丢失）

容量大：可以存储更多的信息

读写速度快：以配合CPU的处理能力，提升效率（外存等存储器IO速度慢）

便携且便宜：站在消费者的角度

目前，满足以上所有性质的存储器并没有发明出来，例如：

SRAM,DRAM: 具有良好的读写速度，但是具有易失性且价格昂贵

磁盘等: 稳定容量大且便宜，但是读写速度很慢，即使是SSD亦是如此

因此我们需要通过建立良好的存储体系以克服高速RAM容量小且昂贵、容量大便宜的磁盘外存访问速度低等缺陷，从而充分发挥CPU的计算能力。

Question 高速缓存的存储容量有限，需要自顶向下进行交互读入数据，因而速度瓶颈出现在读入磁盘信息到主存环节，设计多级缓存也无法解决这一瓶颈，那么这个存储器层次结构有何意义？

局部性原理：CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中

由局部性原理，所访问的存储单元趋于聚集在较小的连续区域，可以通过存储器的层次结构，将访问频率高的信息放在高速缓存中，访问频率低的信息放在外存，从而提高访问效率。

2. 分页存储管理

设计存储器的目的是将其存储空间分配给进程，更好的存储体系能帮助我们更快更高效地运行程序。在拥有了合适高效的存储器后，需要制定策略来进行存储空间的分配。

2.1 固定分区(fixed partition)存储管理

很容易的可以想到这样简单粗暴的策略：

将内存分割为大小固定的多个分区

设计数据结构作为内存分配表，记录固定分区的起始位置、长度与占用标志

当进程申请存储空间时，访问内存分配表，选择最合适的内存块，分配给进程。但是这种分配方法受限于分区长度的固定，往往内存利用率低。

2.2 可变分区(variable partition)存储管理

为了提高空间利用率，我们可以根据作业大小动态分配内存空间，设计数据结构已分配区表与未分配区表以及一系列回收空间、合并空间的算法，管理内存空间。

但是这种方式的缺点是，容易形成内存碎片。

2.3 分页存储管理

以上两种分配方式都要求内存空间是连续的，由此会产生空间利用率低、产生碎片等问题。

为了解决这些问题，我们为内存空间划分最小分配单元，在物理地址空间之上增加一层抽象层称为逻辑地址空间，通过地址映射函数 $f(LA) \rightarrow PA$ 将逻辑地址映射到物理地址，达到以下效果：

进程角度：分配了连续的逻辑地址空间

系统角度：连续逻辑地址可能映射到非连续的物理地址，避免了连续物理内存分配导致的碎片化，提高内存利用率

引入一些术语

页面：进程逻辑地址空间分为大小相等的区，称为页

页框：又称页帧，内存物理空间划分为与页面大小相等的区域

逻辑地址：可被划分为页号+页内位移

内存页框表：每个表项Entry给出了物理块的使用情况

页表：以页框为单位分配，采用动态地址重定位，每个页面设立一个重定位寄存器，其集合为页表

由此：

物理地址 = 页框号 $\times$ 块长 + 页内位移

在此基础上，加入了TLB(Translation Look-aside Buffer, 翻译快表)、多级页表等结构提高内存分配的效率，并且通过页框共享实现了存储共享，在Entry中设立标志位进行存储保护。

3. 分段存储管理

虽然分页式存储管理在系统管理的角度，实现了离散分配物理内存，提高了内存利用率且消除了内存碎片；但是，站在用户需求角度，在编程过程中，程序员往往希望以模块化的方式组织内存，赋予一段内存空间意义，以更好的管理内存（可类比到程序设计中变量名符号表设计的初衷就是赋予一段地址含义，以增加可读性等）。

分页式存储管理仅在物理空间上管理内存，并没有提供逻辑上组织内存的方式，由此提出了分段式存储管理的方式，允许用户自由的在逻辑空间组织内存，赋予内存空间意义，通过模块化的方式更好的组织内存。

所谓段，即将作业的地址空间划分为长度不定的若干区域，每个区域定义了一组逻辑信息，每段从0开始编址，从而地址空间被分割为多个具有不同意义的独立空间，是二维的。

4. 虚拟存储管理

分段式存储管理提供了赋予地址空间意义、模块化组织存储空间的能力，但停留在用户的语义层面，对系统提高效率并无太大帮助。

分页式存储管理通过划分地址空间，以地址映射机制将逻辑地址转为物理地址，从而解决连续存储分配分配机制内存碎片化的问题，提高了内存利用率。但这仅在为进程分配内存的粒度下，提高了内存利用率：

Question 进程一次性申请所需要的内存，并不能保证进程本身充分利用了所分配的内存

进程申请内存空间的部分，可能仅访问一次便不再使用。那么，是否可以在进程使用时分配给它，在一段时间内不使用时保存原有内容到外存，将内存交给其他进程使用，以提高内存利用率呢？为了达到这个效果，需要解决若干问题：

实现动态分配，动态回收

保存计算结果

......

由此，我们提出了虚拟存储管理的方式，将磁盘扩展为内存缓存，部分装入内存，空间不足时部分替换，从而在逻辑上提供一个大容量可寻址的内存储器。

4.1 请求分页虚拟存储管理器

依靠支持完成任务——MMU，提供地址转换和存储保护，并支持虚拟内存管理和多任务管理等功能：

管理硬件页表基地址寄存器，进程上下文切换时存储

分解逻辑地址

管理快表

访问页表

为了在分页式存储管理中实现虚拟内存，需要扩充页表项，增加驻留标志位跟踪页面使用情况：

若为1，说明在内存中，返回页框号

若为0，产生缺页异

$MMU(Logical\ Address) \ \rightarrow \ Physical\ Address$ 过程如下

当然，实际运用中过程复杂得多，需要考虑各种页面替换策略降低缺页中断率等。

最后当然需要结合分段式存储管理，形成段页式虚拟存储管理，这是比较接近实际使用的方式。