存储管理之内存分配与回收

1、序言

==早期计算机编程并不需要过多的存储管理==

==随着计算机和程序越来越复杂，存储管理称为必要==

• 确保计算机有足够的内存处理数据
• 确保程序可以从可用内存中获取一部分内存使用
• 确保程序可以归还使用后的内存以供其他程序使用

2、内存分配的过程

2.1、单一连续分配

• 单一连续分配是最简单的内存分配方式
• 只能在单用户、单进程的操作系统中使用

2.2、固定分区分配

• 固定分区分配是支持多到程序的最简单存储分配方式
• 内存空间被划分为若干个固定大小的区域
• 每个分区只提供给一个程序使用，互不干扰

2.3、动态分区分配

• 根据进程实际需要，动态分配内存空间
• 相关数据结构、分配算法

2.3.1、数据结构–动态分区空闲表数据结构

2.3.2、数据结构–动态分区空闲链数据结构

2.3.3、分配算法–首次适应算法（FF算法）

• 分配内存时从开始顺序查找大小适合的内存区
• 若没有合适的空闲区，则该次分配失败
• 每次都从头开始使得头部地址空间不断被划分

==改进==：循环适应算法，每次不在头部开始，而是在上一次结束的地方开始

2.3.4、分配算法–最佳适应算法（BF算法）

• 最佳适应算法要求空闲区链表按照容量大小排序
• 遍历空闲区链表找到最佳合适空闲区
• 可以避免大材小用的情况，从小到大匹配，第一个匹配到的一定是最适合且最小的空闲区

2.3.5、分配算法–快速适应算法（QF算法）

• 快速适应算法要求有多个空闲区链表
• 每个空闲区链表只存储一种容量的空闲区

3、内存回收的过程

==四种情况==

3.1、情况一：回收区在空闲区后面

• 不需要新建空闲链表节点
• 只需要把空闲区1的容量增大为空闲区即可

3.2、情况二：回收区在空闲区前面

• 将回收区与空闲区合并
• 新的空闲区使用原回收区的地址

3.3、情况三：回收区前后均有空闲区

• 将空闲区1、空闲区2和回收区合并
• 新的空闲区使用原空闲区1的地址

3.4、情况四：回收区前后均没有空闲区

• 为回收区创建新的空闲节点
• 插入到相应的空闲区链表中去