计算机操作系统基础 (八)--- 存储管理之内存分配与回收

引言

本文为第八篇，存储管理之内存分配与回收，早期计算机编程并不需要过多的存储管理，随着计算机和程序越来越复杂，存储管理成为必要。本篇主要是了解内存分配的过程和*内存回收的过程*

存储管理的意义

• 确保计算机有足够的内存处理数据

• 确保程序可以从可用内存中获取一部分内存使用

• 确保程序可以归还使用后的内存以供其它程序使用

内存分配的过程

单一连续分配

• 单一连续分配是最简单的内存分配方式

• 只能在单用户、*单进程*的操作系统中使用

它分配的过程就是把内存分为系统区和*用户区*

系统区指的是系统区所有的内存都给操作系统区使用，用户区指的是用户区所有的内存都给用户区的程序使用(这种已经是过时的方法)

固定分区分配

• 固定分区分配是支持多道程序的最简单存储分配方式

• 内存空间被划分为若干固定大小的区域

• 每一个分区只提供给一个程序所使用，互不干扰

将主存分为若干个分区，每一个分区提供给某一个进程所使用，这就是固定分区的分配方法

动态分区分配

• 根据进程实际需要，动态分配内存空间

• 涉及到相关数据结构和具体的一些算法

动态分区空闲表数据结构

假设主存中有若干个分区，有些被使用而有些未被使用，这样就需要一个数据结构去存储某一个分区它是否被使用了，此时就需要空闲表数据结构

在表中有若干个分区，每一个分区都有一个标记，0 或 1，0 表示未被使用，1 表示被使用。这就是动态分区空闲表数据结构

动态分区空闲链数据结构

这个是使用双向链表来保存动态分区中的空闲区域。将所有分散的空闲区域，通过链表进行首尾相连，组成一个空闲链表，但是，会存在像下图中空闲区 2 和 3 是连续的，因此可以将节点 2 和节点 3 给合并起来，这样就可以减少空闲链表的节点。因此，每个节点的大小不一样，所以需要在每个节点里边存储记录这个节点可存储的容量。这个就是动态分区空闲链数据结构

动态分区分配算法

• 首次适应算法(FF 算法)

• 最佳适应算法(BF 算法)

• 快速适应算法(QF 算法)

这些算法是实际进行动态内存分配所使用的算法

首次适应算法(FF 算法)

每一次进行内存分配时，从开始顺序查找适合内存区(主要使用空闲链的数据结构)

若没有合适的空闲区，则该次分配失败，如果找到了，就将该空闲区划分给这个进程使用。每次都是从头部开始，使得头部地址空间不断被划分

最佳适应算法(BF 算法)

• 最佳适应算法要求空闲区链表按照容量大小排序

• 遍历空闲区链表找到最佳空闲区

将空闲区按照大小进行排序，在需要内存的时候，从节点头部开始遍历，寻找最佳的空闲区节点。这种算法的好处就是可以避免一种大材小用的情况，因为它是从小到大遍历这个空闲链表的，所以它匹配到的第一个合适的空闲区，一定是最佳的。

快速适应算法(QF 算法)

• 快速适应算法要求有多个空闲区链表

• 每个空闲区链表存储一种容量的空闲区

将拥有一个空闲区节点的和拥有两个空闲区节点，分成两个链表。当需要内存分配时，就可以快速的找到适合某一个进程的内存区域。

内存回收的过程

内存回收过程，可能有以下几种情况：

• 回收区和一块空闲区相邻，且回收区在空闲区下边

• 回收区和一块空闲区相邻，且空闲区在回收区下边

• 回收区在两块空闲区中间

• 单独的回收区

每种情况的回收过程

回收区在空闲区下边

使用空闲链表的数据结构来保存空闲区，不需要新建空闲链表节点、只需要将空闲区 1 的容量增大为空闲区即可(也就是将回收区包含进来)

回收区在空闲区上边

• 将回收区与空闲区合并

• 新的空闲区使用回收区的地址

回收区位于两个空闲区中间

• 将空闲区 1、空闲区 2 和回收区合并

• 新的空闲区使用空闲区 1 的地址

单独的回收区

• 为回收区创建新的空闲节点

• 插入到相应的空闲区链表中去

在快速变化的技术中寻找不变，才是一个技术人的核心竞争力。知行合一，理论结合实践