4.2 存储管理
存储管理是操作系统中最核心的功能之一，它直接影响系统的性能和效率。在计算机系统中，如何有效地管理内存资源，让多个程序并发运行而不相互干扰，是操作系统设计者必须解决的重要问题。今天，我们将深入探讨操作系统存储管理的各个方面。
一、存储管理的基本概念
逻辑地址与物理地址
在计算机系统中，我们需要区分两种不同的地址概念：
逻辑地址（也称虚拟地址或相对地址）：这是程序员编写代码时使用的地址，它只是一个符号名地址，并不是主存中真实存在的地址。程序员不需要关心程序最终会存储在内存的哪个位置。
物理地址（也称绝对地址）：这是主存中真实存在的地址，是实际的内存单元地址。
地址重定位
程序通常存储在外存中，当程序需要运行时，必须被装载到内存中。这时就需要把程序中的指令和数据的逻辑地址转换为对应的物理地址，这个过程称为地址重定位。
地址重定位有两种方式：
静态重定位：在程序装入主存时就完成了逻辑地址到物理地址的转换，在程序执行期间不会再发生变化。这种方式简单但缺乏灵活性。
动态重定位：在程序运行期间动态地完成逻辑地址到物理地址的转换。这种方式更加灵活，有利于内存的有效利用。
二、分区存储管理
分区存储管理是最简单的内存管理方式，它将主存划分成若干个区域，每个区域分配给一个作业使用。
三种分区方式
固定分区：系统生成时就已经分好区，每个分区的大小和位置是固定的。这种方式实现简单，但容易产生内部碎片，内存利用率不高。
可变分区：这是一种动态分区方式，存储空间的划分是在作业装入时进行的，分区的个数可变，分区的大小刚好等于作业的大小。这种方式提高了内存利用率，但会产生外部碎片。
可重定位分区：分配好的区域可以移动，通过移动内存中的分区来合并空闲空间，解决外部碎片问题。
三、分页存储管理
分页原理
分页存储管理突破了分区管理的限制，允许一个作业的地址空间分散地存储在内存中不连续的物理块中。其基本原理是：
- 将进程的地址空间划分成若干个大小相等的区域，称为页
- 将主存空间也划分成与页相同大小的若干个物理块，称为块或页框
- 在为进程分配主存时，将进程中若干页分别装入多个不相邻接的块中
地址结构
在分页系统中，逻辑地址被分为两部分：页号和页内地址。系统通过页表来建立页号与物理块号之间的映射关系。
页表机制
每个进程都有一张页表，用于记录逻辑页号与物理块号的对应关系。页表是实现地址映射的关键数据结构，它保证了程序在执行时能够正确地访问内存中的数据和指令。
地址变换过程：当程序访问某个逻辑地址时，硬件会自动根据页号查找页表，得到对应的物理块号，然后将物理块号与页内地址拼接，形成最终的物理地址。
四、分段存储管理
分段原理
分段存储管理是根据程序的逻辑结构来划分地址空间的。在分段系统中，将用户程序按内容划分为若干段，比如主程序段、子程序段、数据段等。每个段的长度不等，但每个段占用一个连续的分区。
段表机制
系统为每个进程建立一张段表，记录每个段的基址（在内存中的起始地址）和段长（段的长度）。段表是实现分段存储管理的核心数据结构。
分段与分页的区别
- 分页是为了满足系统的内存管理需求，对用户是不可见的
- 分段是为了满足用户的逻辑需求，对用户是可见的
- 分页中页的大小是固定的，而分段中段的大小是可变的
- 分页消除了外部碎片，但会产生内部碎片；分段消除了内部碎片，但会产生外部碎片
五、段页式存储管理
段页式存储管理结合了分段和分页的优点，是现代操作系统广泛采用的内存管理方式。
实现原理
在段页式系统中：
- 先将用户程序按逻辑关系划分为若干个段
- 然后将每个段再划分为若干个页
- 主存被划分成大小相等的物理块（页框）
- 系统同时维护段表和页表
地址变换过程
逻辑地址由三部分组成：段号、段内页号和页内地址。地址变换需要两次查表：
- 首先根据段号查找段表，得到该段对应的页表始址
- 然后根据页号查找页表，得到对应的物理块号
- 最后将物理块号与页内地址拼接，形成物理地址
六、虚拟存储管理
程序局部性原理
虚拟存储器的理论基础是程序的局部性原理，包括两个方面：
时间局部性：程序中的某条指令一旦执行，则在不久的将来很有可能再次被访问；某个存储单元如果被访问，不久的将来它很可能再次被访问。
空间局部性：一旦程序访问了某个存储单元，则不久的将来，其附近的存储单元也最有可能被访问。
虚拟存储器的实现
基于局部性原理，虚拟存储器允许将作业的一部分装入主存即可运行程序，其余部分可以暂时留在磁盘上，等需要的时候再装入主存。这样一来，一个小的主存空间就可以运行比它大的作业。
从用户角度看，系统具有的主存容量比实际的主存容量要大得多，这就是"虚拟"的含义。
请求分页系统
请求分页系统是在纯分页的基础上增加了请求调页功能和页面置换功能。每当所要访问的页面不在主存时，便产生一个缺页中断，系统将该页面从磁盘调入内存。
七、页面置换算法
当内存已满而又需要调入新页面时，必须选择一个页面将之换出到磁盘上。选择哪个页面换出，直接影响系统的性能。以下是几种常见的页面置换算法：
1. 最佳置换算法（OPT）
这是一种理想化的算法，选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。虽然理论性能最好，但实际上无法实现，因为无法预知未来的访问模式，只能作为评价其他算法的基准。
2. 先进先出算法（FIFO）
优先淘汰最先进入主存的页面，也就是在内存中停留时间最长的页面。实现简单，但性能不佳，可能出现Belady异常现象（分配的内存增多，缺页次数反而增加）。
3. 最近最少使用算法（LRU）
优先淘汰最近这段时间用得最少的页面。系统为每个页面设置一个访问字段，记录该页面自上次被访问以来所经历的时间T，当要淘汰一个页面时，选择T最大的页面。LRU算法性能接近OPT，是实际应用中最常用的算法。
4. 最近未用算法（NRU）
优先淘汰最近一段时间未引用过的页面。系统为每个页面设置一个访问位，访问位为1表示访问过，为0表示没有被访问过。置换页面时选择访问位为0的页面。这是一个简化版的LRU算法，实现更简单，性能也相对较好。
八、实际应用与优化
转换检测缓冲区（TLB）
为了加速地址变换过程，现代计算机系统引入了TLB（Translation Lookaside Buffer），这是一个高速缓存，用于存储最近使用的页表项。TLB使得大多数地址变换不需要访问主存中的页表，大大提高了地址变换的速度。
多级页表
为了减少页表占用的内存空间，现代系统采用多级页表技术。多级页表允许只有实际需要的页表项才占用内存，虚一级页表中未使用的部分不需要分配物理内存。