- 存储器的层次结构
- 程序的装入和连接
- 连续分配方式
- 基本分页存储管理方式
- 基本分段存储管理方式
- 虚拟存储器的基本概念
- 请求分页存储管理方式
- 页面置换算法 Page-Replacement Algorithms
- 请求分段存储管理方式
本节主要讨论计算机系统的存储器中内存管理的部分。包括程序的装入链接，连续分配，基本分页/分段存储管理方式，虚拟存储器的概念，请求分页存储管理方式，页面置换算法，请求分段存储管理方式等。
存储器的层次结构
- CPU 寄存器（寄存器）->主存（高速缓存->主存->磁盘缓存）->(磁盘->可移动存储介质)。
程序的装入和连接
程序装入的步骤：编译， 链接， 装入程序。
程序的装入
- 绝对装入方式：程序中使用绝对地址，即在编译或汇编时给出，也可以由程序员直接赋予（这需要了解内存使用情况）。多道程序环境难以实现。
- 可重定位装入方式：装入后需要对指令地址和数据地址均进行重定位（装入时，对目标程序中指令和数据地址的修改过程）。这种方法通常仅在装入时需要进行地址变换，所以称为静态重定位。
- 动态运行时装入方式：装入程序时不把相对地址换成绝对地址，而是在程序真正执行时才转换地址。
程序的链接
程序的链接：将程序的各个目标模块和库等链接形成装入模块。
- 静态链接方式：需要解决两个问题：对相对地址进行修改（排列），变换外部调用符号。
- 装入时动态链接：边装入边链接。装入的模块，发生外部调用，则入查找相应外部模块，将器装入内存，并进行链接。便于修改和更新，便于实现对目标模块的共享。
- 运行时动态链接：对某些模块推迟到程序执行时才装入内存并链接。
连续分配方式
单一连续分配
- 分为系统区和用户区两部分。只能用于单用户、单任务操作系统。
固定分区分配
- 分区大小固定，不随程序变化。
- 划分分区方法：分区大小相等和分区大小不等两种
- 内存分配：建立分区使用表，按照分区大小排列，使用时检索有无满足大小的未使用分区，有则分配。
动态分区分配
- 根据进程实际需要动态为之分配内存空间。
动态分配的数据结构
- 空闲分区表：记录每个空闲分区情况。包括空闲分区号，分区始地址和分区大小。
- 空闲分区链：双链表，每个结点的前部和后部分别保持向前和向后的指针，空闲链结点的大小（重复），状态位（重复）。
分区分配算法
- 首次适应算法 FF, first fit：留下更大的空闲分区。
- 循环首次适应算法 next fit：上次找到空闲分区的下一个分区开始查找。空闲分区更均匀。
- 最佳适应算法 best fit:分配满足要求的最小空闲分区。要求空闲分区以大小排序。
- 最坏适应算法 worst fit：挑选最大空闲分区给作业使用。
- 快速适应算法 quick fit：根据分区大小划分不同的空闲分区链，建索引表用于查找所需空闲分区链表，不在分割空闲分区。以空间换时间的做法，划分越细资源浪费越严重。
分区分配操作
- 分区分配流程
- 回收内存：有邻接则合并不分配新表项，无邻接则分配新表项插入空闲链的适当位置。
可重定位分区分配
- 引入：因为内存需要，在程序运行前，需要紧凑形成连续空闲区，导致地址错误。
- 动态重定位实现：装入时任然时相对地址，执行时才进行地址转换（硬件支持，重定位寄存器）。
对换swapping
- 将内存中暂时不运行的程序和数据，调到外存上。提高内存利用率。
- 对换空间管理：类似空闲分区表或空闲分区链，不过记录的时对换区的地址与大小，单位是盘块号和盘块数。
- 进程的换出与换入：换出阻塞状态且优先级最低进程（传送到磁盘对换区，并修改 PCB），换入已换出最久“就绪”状态进程。
基本分页存储管理方式
- “紧凑”会有较高的开销。减少紧凑操作，所以有离散分配方式。离散分配方式的基本单位不同分成：分页存储管理方式和分段存储管理方式。
页面和页表
- 页面：将程序的逻辑地址分成若干大小相等的片，称为页面或页，将页进行编号。每页对应内存空间中大小相等的块或页框。分别加以编号。页面大小要适中，否则会页表过大或者，页内碎片过大。
- 地址结构：程序的逻辑地址：$<页号 31-12, 位移量 11-0>$。所以每页大小最大为 4KB，最多有 1M 页。
- 页表：内存中记录页号和块号对应关系的表。$<块号>$ 按照页号排序。
地址变换机构
- 地址变换机构，将逻辑地址变换到内存的物理地址。
- 块表：具有并行查找能力的高速缓冲寄存器，又称为“联想寄存器”。存放当前访问过的哪些页表项。
两级和多级页表
- 解决页表需要大的连续内存空间和页表本身需要内存过大的问题
- 采用离散分配方式解决需要连续大内存空间的问题；
- 仅将当前需要的部分页表项调入内存，其余存储在磁盘上。
- 两级页表结构：逻辑地址记录为 $<外层页号 31-22, 外层页内地址， 页内地址>$ 的形式。多级页表类似方式。
- 增加状态位来表征该页表是否导入内存。不在则产生中断，请求调入内存。
基本分段存储管理方式
- 为了满足用户在编程和使用上多方面的要求。
分段存储管理方式的引入
- 方便编程：用户可按照逻辑关系划分若干段，每段地址从 0 开始编址。
- 信息共享：存放信息的段是逻辑单位（而页仅有物理地址的含义，没有完整意义），便于共享。
- 信息保护：对信息的逻辑单位进行保护。
- 动态增长：段（特别是数据段）的长度可以不断增加。
- 动态链接：动态链接也是以段为管理单位的。
分段系统的基本原理
- 逻辑地址：$<段号 31-16, 段内地址 15-0>$
- 段表：每个段获得一个连续的内存空间，段表建立每个逻辑段对应的内存位置。段表项：$<段长， 基址>$ 段表存放在段表寄存器中，按照段号排序。
- 地址变换机构也类似分页系统：但检测越界有两个：段号越界，段长越界（段长是不定的）。对于段表在内存的情况，也配置联想寄存器，改善计算速率。
- 分页和分段的主要区别：
- 页是物理单位，目的是提高内存利用率。段是信息的逻辑单位，具有相对的完整的信息，目的是方便用户需求。
- 页大小固定且由系统决定，页号和页内地址的长度划分也是是机器硬件实现的。段长度却不固定，取决于用户的程序长度。
- 分页的地址空间是一维的，单一线性空间（因为页面大小是固定的）。段内的空间是二维的，由段号和段内地址共同决定（段长大小不固定）。
- 可重入代码：允许多个进程同时访问的代码。各进程所执行的代码完全相同，所以不允许执行过程中，对该代码进行任何修改。将数据和程序区进行分离，数据区可改，程序区不可改，使得代码程序区不改动称为可重入代码。
段页式存储管理方式
- 基本原理：将程序分成若干段，段则分为若干页，每个段赋予一个段名。逻辑结构：$<段号， 段内页号， 页内地址>$。
- 段页式存储地址变换过程：
- 段号<段表长度，则段号+段表始址得到段表中的段表项位置
- 页号<段表项内页表长度，页表始址+页号获得页表中的页表项位置
- 页表项内的块号+页内地址，获得内存中的物理地址。
- 高速缓冲寄存器，同时利用段号和页号检索高速缓存。
虚拟存储器的基本概念
- 引入原因：内存不足存放过大的作业或作业过多无法存储。而且无法增加内存。
虚拟内存的引入
- 常规存储器管理方式特征：一次性和驻留性。
- 局部性原理：短时间内，程序的执行局限于某个部分，访问的数据也局限于某个区域。表现在时间局限性（程序和数据的连续访问）和空间局限性（连续访问往往访问被访问单元附近的单元，例如顺序执行）。
- 虚拟存储器：指具有请求调入功能和置换功能， 能从逻辑上对内存容量加以扩充的一种存储器系统。
虚拟存储器的实现方法
- 分页请求系统：增加页面请求功能和页面置换功能的页式虚拟存储系统。置换和调入均以页面为单位。
- 硬件支持：
- 请求分页的页表机制：在纯分页的页表机制上增加若干项形成。
- 缺页中断机构：程序访问尚未调入内存的页面，则产生中断，将缺页调入内存。
- 地址变换机构：在村分页地址变换机构的基础上发展。
- 请求分页的软件：实现所需页面的调入和暂时不用的页面的置换。
- 硬件支持：
- 请求分段系统：增加请求调段及分段置换功能的段式虚拟存储系统。
- 硬件支持：与虚拟分页类似：请求分段的段表机制，缺段中断机构，地址变换机构。
- 部分芯片支持段页式虚拟存储器。
虚拟存储器的特征
- 多次性：多次调入内存。
- 对换性：占不使用的程序和数据（甚至进程亦可）对换出内存。
- 虚拟性：逻辑上扩充内存容量。
请求分页存储管理方式
由于分页长度固定，所以比请求分段系统简单，所以是最常用的实现虚拟存储器的方式。
请求分页的硬件支持
- 页表机制：页表项 $<页号， 物理块号， 状态位 P, 访问字段 A, 修改位 M, 外存地址>$
- 状态位 P：显示程序是否已在内存。
- 访问字段 A：记录这段时间，被访问次数或多长时间未被访问。
- 修改位 M：调入内存后是否被修改过。(未修改，则换出时无需写入外存)
- 外存地址：通常是外存上的物理块号。
- 缺页中断机构：经历保护 CPU 环境，分析中断原因，转入缺页中断处理程序、恢复 CPU 环境等几个步骤。与一般中断有两个区别：
- 指令执行期间产生和处理中断信号。在执行指令期间，发现指令或数据不在内存时所产生和处理的。
- 一条指令在执行期间，可能产生多次缺页中断。
- 地址变换机构：实现地址变换或缺页请求终端，或越界中断。注意修改快表，访问位/修改位，修改页表，外存等。
内存分配策略和分配算法
- 最小物理块数的确定：保证系统正常运行的最小物理块数。与硬件结构、指令的格式、功能和寻址方式有关。
- 物理块的分配策略：
- 固定分配局部置换：分配的物理块数在分配后不再改变，该进程所需的置换仅在该进程分配到的 n 个块中发生。
- 可变分配全局置换：空物理块队列由系统维护，缺页时使用该队列的空物理块，没有空物理块则选择一页调出（可为系统中任一进程的页）。
- 可变分配局部置换：换出仅从该进程的内存页中换出，不影响其他进程。如果该进程频繁缺页中断，则再为其分配若干附加物理块。缺页率低则适当减少物理块。
- 物理块分配算法：
- 平均分配算法
- 按比例分配算法
- 考虑优先权的分配算法
调页策略
- 调入页面时机：
- 预调页策略：预测不久会被访问的页面，预先调入。但一般仅使用与首次调入，由程序员指出先调入哪些页。
- 请求调页策略：访问到某些程序或数据时，发现不在内存，发起请求，由 OS 将其调入。
- 确定从何调入页面：
- 对换区充足，则完全从对换区调入所需页面。(提前将文件区与该进程相关文件拷贝到对换区)
- 对换区不足，则不会修改文件从文件区调入，需要修改文件从对换区调入（或对换到对换区）。
- UNIX 方式：未运行过文件从文件区调入，曾经运行过但被换出页面放入对换区（下次则从对换区换入，允许不同程序页面共享）。
- 页面调入过程
页面置换算法 Page-Replacement Algorithms
最佳置换算法和先进先出置换算法
- 最佳置换算法：仅是理想中能实现，实际无法预知最佳置换块，所以仅能作为参考用。
- 先进先出 FIFO 页面置换算法：淘汰最先进入内存的页面。
最近最久未使用(LRU)置换算法
- 最近的过去作为最近的将来的近似。使用到了页表项中的访问字段 A，淘汰最久未访问的页面。
- 需要硬件支持（二者选其一即可）：
- 寄存器：为每一个在内存的页面配置移位寄存器，通过移位寄存器值最小则为最久未使用的页面的寄存器。
- 栈：特殊的栈（不是上进上出），访问存在页时：出被访问的页，从顶部入（保证每次被访问页都在栈顶）。未满时新加入则在栈顶。对换则换出栈底。
Clock置换算法
- 近似的 LRU 算法
- 简单的 Clock 置换算法：一位访问位，被访问则置为 1，当需要换出时，检测访问位，为 1 则不换出，置为 0。为 0 则换出。这种算法成为最近未用算法 NRU(Not Recently Used)。
- 改进的 Clock 置换算法：在简单的 Clock 置换算法基础上考虑置换的代价，有限置换未被修改的页面。减少了 I/O 操作。
其他置换算法
- 最少使用（LFU：Least Frequently Used）置换算法：采用移位寄存器计数，$\sum{R_i}$ 最小的页是最近一段时间使用最少的页。使用将最高位寄存器置为 1，但每隔一段时间会右移动一次（这个时间可以较长）。
- 页面缓冲算法：将需要置换出去的已修改的链表放到一个链表的末尾，当达到一定数目的页面时，一次性写回磁盘，减少磁盘的 I/O 操作。
请求分段存储管理方式
- 硬件支持：
- 段表机制；
- 缺断中断机制
- 地址变换机构
- 分段的共享和保护