动态存储管理
动态分区分配中数据结构分为：空闲分区表(起始位置、空闲块大小、使用情况(空闲或使用))和空闲分区链表
可利用空间表分为3种不同的形式：
- 链表：系统运行期间，所有用户请求分配存储量大小相同，分配时无需查找，将第一个节点分配给用户，释放时，系统将用户释放的空闲块插入表头。
- 分类若干可利用空间表。将空间分区分区根据容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设定一个空闲分区链表。
- 空闲块大小随意。系统运行期间，分配给用户的内存块大小不固定，可随需求改变。
可利用空间表的4种分配策略：
- 首次拟合法：每次均从表头查找可利用空间表，将找到第一个>=需求的内存块分配给用户
- 循环首次拟合法：不再每次均从表头而是从上次找到的空闲分区的下一个分区查找，将找到的第一个>=需求的内存块分配给用户
- 最佳拟合法：遍历可利用空间表，从中找出全表最接近满足需求的内存块分配给用户
- 最差拟合法：可利用空间表中最大空闲块分配给用户，此时结点应当从大到小排序，分配时只需从链表中删除第一个结点，并分配一部分给用户，剩余部分插
首次拟合法、最佳拟合法及最差拟合法对比
最佳拟合法适用于请求分配的内存大小范围较广的系统，最差拟合法最终使得链表中的结点大小趋于均匀，适用于请求分配的内存大小范围较窄的系统，首次拟合法适用于系统事先不掌握运行期间可能出现的请求分配和释放的信息情况。
时间考虑：首次拟合分配时需查找可利用空间表，回收时插入到表头；最佳拟合无论分配回收都需要查找可利用空间表；最差拟合分配时直接表头分配，回收时查找
基于索引搜索的动态分区分配算法
- 分类搜索法
根据进程长度，从索引表中寻找容纳它最小的空闲区链表，从链表中取下第一块进行分配 - 伙伴系统
整个内存容量为2^m个字，将所有大小相同的空闲块建于一张子表中，每个子表是一个双重链表(包括link(前驱结点)、tag(块标志：0空闲，1占用)、kval(块大小，值为2的幂次k)，rlink(后继结点))。
可利用空间表寻找与需求相匹配的子表，若此子表为非空，则将子表的任意一个结点分配。若此子表为空，则需寻找结点更大的非空子表去寻找，将其中一部分分配给用户，剩余部分分割成若干结点分别插入相应的子表。
回收：伙伴回收。“伙伴”：在分配时经常需要将一个大的空闲块分裂成两个大小相等的存储区，这两个由同一块分裂出来的小块就称之为伙伴。在回收空闲块时，首先判断其伙伴是否为空闲块，若否，则只要将释放的空闲块简单插入相应子表中即可。若是，则需在相应的子表中找到其伙伴并删除之，然后再判断合并后的空闲块伙伴是否为空闲块。依次重复，直至归并所得空闲块的伙伴不是空闲块时，再插入到相应的子表中。 - 哈希算法
以空闲分区大小为关键字的哈希表，该表每一个表记录了一个对应的空闲分区链表表头指针
无用单元收集
可利用空间表应用户需求进行动态存储分配和回收，有时因为用户疏忽导致系统产生内存泄漏。
两种方案解决无用单元：
- 使用访问计数器
- 广义表中添加标志位，扫描可利用空间表，将所有标志为0的结点链接成一个新的可利用空间表。重点在标志算法。
标志算法分为： - 递归算法：需要一个较大的实现递归调用栈的辅助内存
- 非递归算法：二叉树非递归遍历算法，同样需要容量不定的辅助内存
- 利用表自身的指针域遍历路径的算法
存储紧缩
堆：不管哪个时刻，可利用空间表都是一个连续的存储区，每次分配均从这个可利用空间中划出一块。实现方法：设立堆指针，始终指向堆的最高位(或最低位)，当用户申请N个单元的存储块时，堆指针向高地址移动N个存储单元。
存储紧缩的具体流程：
- 计算占用块的新地址
- 修改用户的初始变量表
- 检查每个占用块的存储数据
- 将所有的占用块迁移到新地址去
分段存储管理、分页存储管理、段页式存储管理
段页式存储管理(分页系统以页面作为内存分配的基本单元，能有效提高内存利用率、防止外部碎片问题，会产生内部碎片(一页没用完情况)，分段系统便于实现、可共享、可动态链接，容易产生外部碎片(原本5k逻辑段仅使用4k))：
段表寄存器分为段表始址+段表长度；
逻辑地址分为段号+页号+页内地址；
地址变换利用段表始址和段号求该段所对应的段表，段表+页号得到页表，页表+页内地址得物理地址。
段页式系统中，为获得一条指令或数据，需三次访问内存：
- 访问内存中的段表，从中获得页表始址
- 访问内存中的页表，从中获得该页所在的物理块号，与页内地址一起形成指令或数据的物理地址
- 依据第二次访问获得的物理地址取指令或数据
为提高多次访问内存的速度，在地址变换机构中增设一个高速缓存寄存器
数据存储分数据段、代码段、堆栈段、BSS段。段下引用页表，页表为两级页表，两级页表分外部页表和页表，实现地址变换。
分段和分页的主要区别：
- 页是信息的物理单位，段是信息的逻辑单位
- 页大小固定，段长度不一
- 页用户程序地址空间是一维(页表---->1,4,6排序)，分段系统中，用户存储空间是二维的(段表—>基址+段长)
分段和分页的信息共享：分段易于实现段的共享
样例：程序共160kb代码和40kb的数据区，代码区共享，假设每个页面大小4kb，则代码区40个页面共享，10个数据区不共享
如下为分页存储：
如下为分段存储