一、管理系统概述：
1.1 存储管理目的和功能：
主存储器的分配和回收
提高主存储器的利用率，减少不可用的存储空间，允许多道程序动态共享主存
存储保护
内存扩充
地址重定位
~~~~~~ i. 名字空间、地址空间和存储空间：
~~~~~~ ~~~~~~ 1) 符号地址：在源程序中，通过符号名来访问子程序和数据，这些符号名实际代表了地址，称为符号地址
~~~~~~ ~~~~~~ ~~~~~~ a) 名字空间：程序中符号名的集合称为名字空间
~~~~~~ ~~~~~~ 2) 逻辑地址/程序地址/虚地址：程序中使用的从0开始进行编址的地址
~~~~~~ ~~~~~~ ~~~~~~ a) 地址空间/程序空间：程序中逻辑地址的集合
~~~~~~ ~~~~~~ 3) 内存地址/物理地址/绝对地址：内存单元的地址
~~~~~~ ~~~~~~ ~~~~~~ a) 物理空间/存储空间/内存空间：内存地址的集合，是一维线性空间
~~~~~~ ii. 地址重定位：要把它装入内存执行，就要确定装入内存的实际物理地址，并修改程序中与地址有关的代码，把逻辑地址变换为物理地址，这个过程称为地址重定位
~~~~~~ ~~~~~~ 1) 地址重定位完成把相对地址转换为内存中的绝对地址，这个过程称为地址映射（map）。按照重定位的时机，可分为静态重定位和动态重定位
~~~~~~ ~~~~~~ ~~~~~~ a) 静态重定位：在程序执行之前进行重定位；根据装配模块将要装入的内存起始地址，直接修改装配模块中的有关使用地址的指令
~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ i) 优点：无须硬件支持
~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ ii) 缺点：
~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ One. 程序重定位以后就不能在内存中移动
~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ Two. 要求程序的存储空间是连续的，不能把程序存储到若干个不连续的区域中
~~~~~~ ~~~~~~ ~~~~~~ b) 动态重定位：在程序执行过程中进行地址重定位，即在每次访问内存单元前才进行地址变换
~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ i) 优点：
~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ One. 目标程序装入内存时无需任何修改，所以装入之后再移动也不会影响其正确运行，这便于存储器用紧缩来解决存储器的碎片问题
~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ Two. 一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不相领接，只要各个模块有自己对应的重定位寄存器就可以了
~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ Three. 可以部分装入内存，程序就可以运行
~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ Four. 便于多个进程共享同一程序副本
~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ ii) 缺点：
~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ One. 需要硬件支持
~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ Two. 实现存储管理的算法较复杂
~~~~~~
二、程序装入和链接：
2.1 程序装入：
~~~~~~ i. 绝对装入：程序使用绝对地址编写，装入内存时装入到程序规定的地方，不需要进行地址变换
~~~~~~ ii. 静态重定位装入：程序使用逻辑地址编写，装入内存后在执行之前进行地址变换
~~~~~~ iii. 动态重定位装入：程序使用逻辑地址编写，装入内存后在执行每条指令存取内存前进行地址变换
2.2 程序链接：
~~~~~~ i. 静态链接：经编译/汇编之后，将目标模块在运行之前组合在一起形成一个独立运行模块（可执行文件）
~~~~~~ ii. 装入时动态链接：经编译后的模块在装入内存准备运行前进行链接
~~~~~~ ~~~~~~ 1) 优点：
~~~~~~ ~~~~~~ ~~~~~~ a) 便于修改和更新程序
~~~~~~ ~~~~~~ ~~~~~~ b) 便于共享，节省外存空间
~~~~~~ ~~~~~~ 2) 缺点：
~~~~~~ ~~~~~~ ~~~~~~ a) 共享模块并没有减少内存占用量
~~~~~~ iii. 运行时动态链接：在执行过程中若发现需要的某目标模块没有装入内存链接，则将它装入内存并链接
~~~~~~ ~~~~~~ 1) 优点：
~~~~~~ ~~~~~~ ~~~~~~ a) 模块共享
~~~~~~ ~~~~~~ ~~~~~~ b) 提高内存利用率
~~~~~~
三、连续分配存储方式：
3.1 单一连续分配：
~~~~~~ i. 思想：最简单的存储管理方式，但只能用于单用户、单任务的操作系统
~~~~~~ ii. 存储保护：设置基址界限寄存器对
~~~~~~ iii. 缺点：
~~~~~~ ~~~~~~ 1) 只支持单道程序运行
~~~~~~ ~~~~~~ 2) 不能充分利用内存空间
~~~~~~ ~~~~~~ 3) 不能实现虚拟存储
3.2 固定分区分配：
~~~~~~ i. 思想：固定式分区是在作业装入之前，内存就被划分成若干个分区；
~~~~~~ ~~~~~~ 1) 分区一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变；所以固定式分区又称为静态分区
~~~~~~ ~~~~~~ 2) 一般将内存的用户区域划分成大小不等的分区，以适应不同大小的作业的需要
~~~~~~ ii. 管理机构：系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志
~~~~~~ iii. 内存管理：分配算法和回收算法
~~~~~~ iv. 存储保护：设置基址界限寄存器对
~~~~~~ v. 优点：
~~~~~~ ~~~~~~ 1) 支持多道程序
~~~~~~ vi. 缺点：
~~~~~~ ~~~~~~ 1) 易产生碎片
~~~~~~ ~~~~~~ 2) 不支持虚拟存储
~~~~~~ ~~~~~~ 3) 不能充分利用内存，当空闲分区之和能满足某程序而单个不能满足时，程序不能运行
3.3 动态/可变式分区分配：
~~~~~~ i. 思想：在作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小
~~~~~~ ~~~~~~ 1) 可变式分区中分区的大小和分区的个数都是可变的，而且是根据作业的大小和多少动态地划分，因此又称为动态式分区
~~~~~~ ~~~~~~ 2) 是固定式分区的改进，既可以获得较大的灵活性，又能提高内存的利用率
~~~~~~ ii. 管理机构：
~~~~~~ ~~~~~~ 1) 空闲区表形式：空闲分区表为每个尚未分配的分区设置一个表项，包括分区的序号、大小、始址和状态
~~~~~~ ~~~~~~ 2) 空闲区链形式
~~~~~~ iii. 分区分配算法：
~~~~~~ ~~~~~~ 1) 最佳适应算法
~~~~~~ ~~~~~~ 2) 首次适应算法
~~~~~~ ~~~~~~ 3) 循环首次适应算法
~~~~~~ ~~~~~~ 4) 最坏适应法
~~~~~~ iv. 优点：
~~~~~~ ~~~~~~ 1) 支持多道程序
~~~~~~ ~~~~~~ 2) 相对于固定分区，在一定程度上减少了碎片
~~~~~~ v. 缺点：
~~~~~~ ~~~~~~ 1) 仍然存在碎片
~~~~~~ ~~~~~~ 2) 不支持虚拟存储
~~~~~~ ~~~~~~ 3) 不能充分利用内存，当空闲分区之和能满足某程序而单个不能满足时，程序不能运行
3.4 动态重定位分区分配：
~~~~~~ i. 思想：与动态分区一样，但分区可以移动以便把较小的空闲分区合并成一个较大的空闲分区，因而需要动态重定位的支持
~~~~~~ ii. 拼接/紧凑：向一个方向移动已分配的作业，使那些零散的小空闲区在另一方向连成一片
~~~~~~ iii. 动态重定位：只有具有动态重定位硬件机构的计算机系统，才有可能采取动态重定位可变分区多道管理技术，系统的硬件包括重定位寄存器和加法器
~~~~~~ iv. 动态重定位分区分配算法：
~~~~~~ ~~~~~~ 1) 某个分区被释放后立即进行紧缩，此法很花费机时
~~~~~~ ~~~~~~ 2) 当请求分配模块找不到足够大的自由分区分给用户时再进行紧缩
~~~~~~ v. 优点：
~~~~~~ ~~~~~~ 1) 支持多道程序
~~~~~~ ~~~~~~ 2) 比动态分区前进一步，当空闲分区之和能满足某程序而单个不能满足时可以通过合并空闲分区的办法让程序装入
~~~~~~ vi. 缺点：
~~~~~~ ~~~~~~ 1) 不能解决虚拟存储
~~~~~~ ~~~~~~ 2) 移动合并需要增加系统开销
~~~~~~ ~~~~~~ 3) 仍然存在碎片
~~~~~~
四、覆盖与交换：
覆盖技术：覆盖是指一个作业的若干程序段（或数据段）间，或者几个作业的某些程序段间共享某主存空间
~~~~~~
五、分页存储管理：
5.1 分页：
分页存储管理是将一个进程的地址空间划分成若干个大小相等的区域，称为页，相应地，将内存空间划分成与页相同大小的若干个物理块，称为块或页框。在为进程分配内存时，将进程中的若干页分别装入多个不相邻接的块中
5.2 地址结构：
分页系统的地址结构如下图所示，它由两部分组成：前一部分为页号P；后一部分为位移量W，即页内地址。图中的地址长度为32位，其中0～11位为页内地址（每页的大小为4K），12～31位为页号，所以允许地址空间的大小最多为1M个页
~~~~~~ i. K位页内偏移量：一个页面的大小是2^K
~~~~~~ ii. M位页号：一个进程最多允许有2^M个页面
5.3 页表：
在将进程的每一页离散地分配到内存的多个物理块中后，系统应能保证能在内存中找到每个页面所对应的物理块。为此，系统为每个进程建立了一张页面映射表，简称页表；每个页在页表中占一个表项，记录该页在内存中对应的物理块号。进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射
5.4 地址变化机构：
~~~~~~ i. 基本的地址变换机构：
~~~~~~ ~~~~~~ 1) 作用：基本任务是利用页表把用户程序中的逻辑地址变换成内存中的物理地址，实际上就要将用户程序中的页号变换成内存中的物理块号，为了实现地址变换功能，在系统中设置页表寄存器，用来存放页表的始址和页表的长度
~~~~~~ ~~~~~~ 2) 在进程未执行时，每个进程对应的页表的始址和长度存放在进程的PCB中，当该进程被调度时，就将它们装入页表寄存器。在进行地址变换时，系统将页号与页表长度进行比较，如果页号大于页表寄存器中的页表长度，则访问越界，产生越界中断。如未出现越界，则根据页表寄存器中的页表始址和页号计算出该页在页表项中的位置，得到该页的物理块号，将此物理块号装入物理地址寄存器中
~~~~~~ ~~~~~~ 3) 与此同时，将有效地址（逻辑地址）寄存器中页内地址直接装入物理地址寄存器的块内地址字段中，这样便完成了从逻辑地址到物理地址的变换
~~~~~~ ii. 具有快表的地址变换机构：
~~~~~~ ~~~~~~ 1) 如果页表存放在内存中，则每次访问内存时，都要先访问内存中的页表，然后根据所形成的物理地址再访问内存。这样CPU存一个数据必须访问两次内存，从而使计算机的处理速度降低了1/2
~~~~~~ ~~~~~~ 2) 为了提高地址变换的速度，在地址变换机构中增设了一个具有并行查询功能的特殊的高速缓冲存储器，称为“联想存储器”或“快表”，用以存放当前访问的那些页表项。此时地址变换过程为：在CPU给出有效地址后，地址变换机构自动地将页号送入高速缓存，确定所需要的页是否在快表中。若是，则直接读出该页所对应的物理块号，送入物理地址寄存器；若在快表中未找到对应的页表项，则需再访问内存中的页表，找到后，把从页表中读出的页表项存入快表中的一个寄存器单元中，以取代一个旧的页表项
~~~~~~ ~~~~~~ 3) 由于成本原因，快表不可能做得很大，通常只能存放16~512个页表项
~~~~~~ ~~~~~~ 4) 具有快表的地址变换机构：
5.5 两级页表机制：
~~~~~~ i. 在80386中，为了减少页表所占用的连续的内存空间，采用了两级页表机制：基本方法是将页表进行分页，每个页面的大小与内存物理块的大小相同，并为它们进行编号，可以离散地将各个页面分别存放在不同的物理块中，为此再建立一张页表，称为外层页表（页表目录），即第一级页表，其中的每个表目是存放某个页表的物理地址。第二级才是页表，其中的每个表目所存放的才是页的物理块号
~~~~~~ ii. 两级页表系统将32位逻辑地址空间的地址分成三段：其中，页表目录号和页号两项各占10位，偏移量占12位；每页的大小为4KB
~~~~~~ iii. 两级页表的逻辑地址结构和两级页表的地址变换机构：
~~~~~~ iv. 两级页表机制图：
5.6 存储管理算法：
~~~~~~ i. 数据结构：
~~~~~~ ~~~~~~ 1) 在PCB中记录页表的地址和长度
~~~~~~ ~~~~~~ 2) 设置内存块表，记录每个块的状态(已分配/空闲)，整个系统一张
~~~~~~ ~~~~~~ 3) 页表：每个进程一张
~~~~~~ ii. 分配算法：
iii. 释放算法
5.7 优点：
~~~~~~ i. 支持多道程序设计
~~~~~~ ii. 克服可重定位动态分区要移动合并的工作，程序不必连续存放
~~~~~~ iii. 大大减少碎片
5.8 缺点：
~~~~~~ i. 动态地址变换需要增加计算机的成本并降低处理机速度
~~~~~~ ii. 各种表格要占用一定空间，需要一些系统时间来维护
~~~~~~ iii. 不支持虚拟存储
~~~~~~ iv. 最后一页仍有碎片
~~~~~~
六、分段存储管理：
6.1 引入：
~~~~~~ i. 便于编程
~~~~~~ ii. 分段共享
~~~~~~ iii. 分段保护
~~~~~~ iv. 动态连接
~~~~~~ v. 动态增长
6.2 基本原理：
~~~~~~ i. 分段：分段存储管理方式中，作业的地址空间被划分为若干个段，每个段是一组完整的逻辑信息，如有主程序段、子程序段、数据段及堆栈段等，每个段都有自己的名字，都是从零开始编址的一段连续的地址空间，各段长度是不等的。分段系统的地址结构如下图所示，逻辑地址由段号（名）和段内地址两部分组成。在该地址结构中，允许一个作业最多有64 K个段，每个段的最大长度为64 KB
~~~~~~ ii. 段表：分段式存储管理系统中，为每个段分配一个连续的分区，而进程中的各个段可以离散地分配到内存中不同的分区中。在系统中为每个进程建立一张段映射表，简称为“段表”。每个段在表中占有一表项，在其中记录了该段在内存中的起始地址（又称为“基址”）和段的长度，如下图所示。进程在执行中，通过查段表来找到每个段所对应的内存区。可见，段表实现了从逻辑段到物理内存区的映射
~~~~~~ iii. 地址变换机构：为了实现从逻辑地址到物理地址的变换功能，系统中设置了段表寄存器，用于存放段表始址和段表长度。在进行地址变换时，系统将逻辑地址中的段号S与段表长度TL进行比较。若 S≥TL，表示段号太大，访问越界，于是产生越界中断信号；若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址，然后再检查段内地址d是否超过该段的段长SL。若超过，即 d≥SL，同样发出越界中断信号；若未越界，则将该段的基址与段内地址d相加，得要访问的内存物理地址
~~~~~~ iv. 分页和分段的比较：
6.3 共享：
段是信息的逻辑单位,因此分段系统的一个突出的优点是易于实现段的共享。
6.4 存储管理算法：
基本上同可重定位动态分区管理算法
6.5 优点：
~~~~~~ i. 支持多道程序设计
~~~~~~ ii. 程序不必连续存放
~~~~~~ iii. 便于实现存储保护，段的动态增长，动态连接
6.6 缺点：
~~~~~~ i. 不支持虚拟存储
~~~~~~ ii. 存在分区的移动合并操作，占用处理机时间
~~~~~~ iii. 段的最大长度受限制
~~~~~~ iv. 仍然存在碎片
~~~~~~
七、段页式存储管理方式：
7.1 基本原理：
先将整个主存划分成大小相等的存储块（页架），把用户程序按程序的逻辑关系分为若干个段，并为每个段赋予一个段名，再把每个段划分成若干页，以页架为单位离散分配。在段页式系统中，其地址结构由段号、段内页号和页内地址三部分组成，作业地址空间的结构如图下所示
7.2
为了实现从逻辑地址到物理地址的变换，系统中必需同时配置段表和页表。由于将段中的页进行离散地分配，段表中的内容不再是段的内存始址和段长，而是页表始址和页表长度。下图说明了利用段表和页表进行地址映射的过程
7.3 在段页式系统中，为了获得一条指令或数据，需三次访问内存：
~~~~~~ i. 第一次访问内存中的段表，从中取得页表始址
~~~~~~ ii. 第二次访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址
~~~~~~ iii. 第三次访问才是真正根据所得的物理地址取出指令或数据
7.4 段页式系统的地址变换机构：
7.5 存储管理算法：
基本上同可重定位动态分区管理算法
7.6 优点：
~~~~~~ i. 支持多道程序设计
~~~~~~ ii. 程序不必连续存放
~~~~~~ iii. 便于实现存储保护，段的动态增长，动态连接
7.7 缺点：
~~~~~~ i. 不支持虚拟存储
~~~~~~ ii. 段的最大长度受限制