一、概述
1.1 地址映射（地址重定位）
内存中每个存储单元都有一个编号，这个编号称为内存地址（物理地址、绝对地址）。内存地址的集合称为内存空间（物理地址空间）。
用户编程所用的地址称为逻辑地址（程序地址、虚地址），由逻辑地址组成的空间称为逻辑地址空间。
地址映射：把用户程序装入内存时对有关指令的地址部分的修改。其分为静态地址映射和动态地址映射。
- 静态地址映射：假设程序装入内存的首地址为BR，程序地址为VR，内存地址为MR，则由地址映射得MR=BR+VR。例如：程序装入内存的首地址为1000，则装配程序就按MR=1000+VR对程序中所有地址部分进行修改，修改后指令Load A，200（将200单元的数据取至寄存器A中）就变为Load A，1200。
- 动态地址映射：执行时，访问内存之前，将逻辑地址转换为物理地址。（由专门的硬件完成，例如：重定位寄存器）
1.2 主存分配与回收
完成内存的分配和回收，要求确定以下几种策略和结构： 调入策略、放置策略、置换策略、分配结构。
- 调入策略：用户程序在何时调入内存的策略，策略：请调和预调。
- 放置策略：用户程序调入内存时，确定将其放置在何处的策略。
- 置换策略：当需要将某个用户程序调入内存而内存空间又不够时，就要确定哪个或哪些程序可以从内存中移走。
- 分配结构：分配结构是用来登记内存使用情况的数据结构。如空闲区表、空闲区队列等。
1.3 存储保护
内存中的多道程序在给定的存储区域内活动，互不产生干扰。 包括： 防止地址越界、防止越权(对共享区有访问权）。
防止地址越界的硬件支持：界地址寄存器：访问主存时，硬件自动地将被访问的主存地址与界限存储器的内容进行比较，以判断是否越界。若未越界，继续访问主存地址，否则将产生程序中断——越界中断。
二、分区存储管理
把整个内存划分为若干大小不等的区域，操作系统占用一个区域，其它区域供系统中的多个进程共享，这种方法称为分区存储管理。这是最简单的一种存储管理，按分区划分的时机可分为固定分区和动态分区。
- 固定分区：把内存固定地划分为若干个大小不等的区域。适用于作业大小和出现频率均已知的情况。此时可以直接将区域分配给作业。若作业大小和出现频率未知，造成存储空间的浪费，影响整个系统的效率。
- 动态分区：运行的过程中建立分区，并使分区的大小刚好与作业的大小相等。
2.1 动态分区分配中的数据结构
常用的数据结构有两种形式：空闲分区表和空闲分区链
等待分区队列：无满足要求的空闲区时，申请者进入等待队列中，等待被唤醒。
2.2 动态分区的分配
根据用户的请求，在空闲区表或空闲区队列中找一个满足要求的空闲区，把它分配给用户。
分配时的三种情况：
- 无满足要求的空闲区：分配失败；
- 空闲区等于请求：修改空闲区表，返回该空闲区首址；
- 空闲区大于请求：从上（或下）部划分空闲区（通常采用从下部开始，空闲分区表只修改大小）。
2.3 动态分区的回收
检查相邻空闲区，若相邻则与之合并，否则插入到适当位置（根据不同算法）。
回收时的四种情况：
- 与前空闲区相邻：合并，首址为前空闲区首址，大小为两者之和；
- 与前后两空闲区相邻：将这三个区合并，首址为前区首址，大小为这三者之和，并取消原后空闲区表目；
- 与后空闲区相邻：合并，首地址为释放区首地址，大小为二者之和；
- 不与任何空闲区相邻：将其大小和首址插入到空闲区表的适当位置。
2.4 基于顺序搜索的动态分区分配算法（动态分区链）
1、首次适应算法（first fit，FF）
首次适应算法是根据地址递增的顺序对空闲分区链进行链接。然后按照作业的大小从前到后依次匹配空闲分区，若空闲分区大小>=作业大小，将空闲分区分配给作业，并修改空闲分区的大小（由于按照地址递增顺序，空闲分区链整体结构无需改变）；若找不到这样的空闲区，分配失败。优点：尽可能地利用低地址空间，从而保证高地址空间有较大的空闲区。缺点：容易产生碎片。
2、循环首次适应算法（next fit，NF）
循环首次适应算法也是根据地址递增的顺序对空闲分区链进行链接。与首次适应算法不同的是每次查找不是从链首开始查找，而是从上一次查找到的空闲分区的下一个分区开始查找，直到找到目标空闲区。由此需要设置一起始查寻指针，用于指示下一次起始查询的空闲分区，并采用循环查找方式。
3、最佳适应算法（best fit，BF）
最佳适应算法是按照空闲分区容量从小到大的顺序对空闲分区链进行链接。然后按照作业的大小从前到后依次匹配空闲分区，若空闲分区大小>=作业大小，将空闲分区分配给作业，并修改空闲分区的大小（由于按照地址递增顺序，空闲分区链整体结构无需改变）；若找不到这样的空闲区，分配失败。每次分配一个作业都是从头开始进行分配。
4、最坏适应算法（worst fit，WF）
最坏适应算法是按照空闲分区容量从大到小的顺序对空闲分区链进行链接。然后按照作业的大小从前到后依次匹配空闲分区，若空闲分区大小>=作业大小，将空闲分区分配给作业，并修改空闲分区的大小（由于按照地址递增顺序，空闲分区链整体结构无需改变）；若找不到这样的空闲区，分配失败。每次分配一个作业都是从头开始进行分配。优点：可使剩下的空闲区不至于太小，产生碎片的可能性小。
三、分页存储管理方式
3.1 基本思想
- 分区存储管理：存碎片问题，从而降低了内存的利用率。采用压缩存储区的方法可以解决碎片问题，但系统开销太大，而无实用价值。
- 用户程序划分：把用户程序按逻辑页划分成大小相等的部分，称为页（page）。从0开始编制页号，页内地址是相对于0编址。
- 逻辑地址：用户程序的划分是由系统自动完成的，对用户是透明的。一般，一页的大小为2的整数次幂，因此，地址的高位部分为页号，低位部分为页内地址。如下图所示：
- 内存空间：按页的大小划分为大小相等的区域，称为块或内存块（物理页面，页框）。
- 内存分配：以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻。
3.2 页地址映射
1、页表
页表：登记页号和块的对应关系，每个进程建立一个页表，页表的长度和首地址存放在PCB中，运行进程的页表必须驻留在内存。页号是不保存的，本身就有顺序，页表是按照顺序存储的。页表的作用是实现从页号到物理块号的地址映射。
其具体结构如下表所示：
2、页大小：页的大小是2K，k： 9-12。
3、页地址映射：首先根据页找到其页号和页内地址，判断页号是否越界，然后查询页表中对应的块号，将块号和页内地址进行拼接即可得到物理地址。如下图：
4、快表
由于页表存在，需要访存2次，运行速度要下降一半。由此引入快表。
快表：把页表中部分内容放入Cache中。快表表项：页号；内存块号；标识位；淘汰位。使用快表类似访问内存时使用cache，每次先在快表中找当前页号和页号对应的块号，若找到，直接访问内存；若没找到，再访问页表。使用快表过程如下图：
5、两级页表和多级页表
当页表项很多时，难以找到大的连续的内存空间存放页表时，考虑将页表分页（页号仍然是按顺序排列），每次先找到当前页表，再在页表里找块号，最后得出物理地址。其结构如下：
四、分段存储管理方式
4.1 基本思想
- 用户程序划分：按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段段内也从0开始编址，段内地址是连续的。其逻辑地址如下：
- 内存划分：内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定。（注：分配的地址空间一样大，有效地址范围不一样大）。
- 内存分配：以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放。
4.2 段地址映射
1、地址映射数据结构：段地址映射的数据结构有段号、段表首址指针和段表的长度。段表首址指针和段表长度存放在进程自己的PCB中。段表一般包括有段的长度、段的首址和存取状态等信息。每一进程有个段表，程序的每一个段在段表中占用一个表目。其结构如下：
2、内存的分配：与动态分区管理相同，初始：一个大的空闲区。工作过程中：根据请求，在空闲区表或空闲区队列中找一个满足要求的空闲区，把它分配给用户。有首次适应法、循环首次适应法、最佳适应法、最坏适应法这些基于顺序搜索的算法。
3、段地址变换：首先根据段找到其段号和段内地址，判断段号是否越界，然后查询段表中对应的段长和基址，此时，对段内地址和段长进行检查，没问题再将基址和段内地址进行相加即可得到物理地址。其过程如下：
4、快表：与分页存储管理方式中的快表作用类似。每次先访问快表。其过程如下：
5、分页与分段的比较：
- 段是依据程序的逻辑结构划分的，页是按固定大小划分的。
- 段式技术中程序地址空间是二维的，分页技术中程序地址空间是一维的。
- 段是面向用户的，页对用户而言是透明的。
- 段长由用户决定，大小一般不相等，限制最大长度。页长是由系统决定的，各页的长度必须相等。
- 段的共享比页的共享更容易。
五、段页式存储管理方式
5.1 基本思想
1、用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）。其逻辑地址如下：
2、内存划分：按页式存储管理方案；内存分配：以页为单位进行分配。
3、同二级页表、段表类似，只是外层是段表，内层是页表，按照页表进行分配。
5.2 地址映射
- 段表：记录了每一段的页表始址和页表长度。
- 页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多个页表）。
- 内存分配管理：同页式管理。
5.3 地址变换结构
首先根据段号找到段表中的页表长度和页表始址（要进行越界判断），然后根据页表始址和页号在页表中找到块号（同样要判断越界），然后对页内地址和块号进行拼接即可得到物理地址。如下图：
