操作系统——内存分区管理

本章主要讨论为什么要给内存进行划分和如何划分的问题。
为了给每一个进程都分配一个大小合适的内存块
以连续存储进程的程序和数据，使得各进程可以并发执行

一、内存的划分方法

1、固定分区法

2、动态分区法

3、动态分区的数据管理结构

二、分区的分配与回收

1、固定分区的分配与回收

2、动态分区的分配

1）最先适应算法

2）最佳适应算法

3）最坏适应算法

3、动态分区的回收与拼接

4、最先、最佳、最坏算法优缺点

5、分区管理优缺点

一、内存的划分方法

1、固定分区法

把内存固定的划分为让若干大小不等的内存块
划分主要由操作系统和管理员进行
一旦划分结束，整个内存分区个数以及各个分区大小将不会发生变化
如何对整个分区进行管理？
例如内存块有多大？地址范围是多少？哪些内存块被使用？哪些空闲？等等
上述的管理信息使用分区说明表
分区说明表记录信息：顺序分区号、各分区长度、分区起始地址、分区状态
如图所示：（操作系统占用低20K的地址）

上述固定分区法的先天缺陷是：分配效率低
因为有可能小进程也要占据大分区，导致浪费
于是有了动态法

2、动态分区法

在进程执行前不划分区域，而是在执行过程中进行
可以随着进程对内存的需求进行调整，效率更高
在系统开机初期，内存中只有一个操作系统进程
其余部分都是空闲，分配程序将该空闲部分依次划分给被调度的进程
如图所示：来一个，分配一个，要多少，给多少

但是，随着程序的运行，势必有些进程会结束
结束的进程就要被释放
那么被释放的这部分空间，如何处理？

如何释放？
进程结束后，所占用的内存资源就要被释放
该部分内存状态被标志为空闲

释放后如何管理？
被释放的空闲内存块可能是在中间（前后都被使用）
此时，如果后续如果新的进程需要调度
并且该空闲内存块正好大于 / 等于所需内存
则分配给新调度的进程

如果被回收的分区有邻接的空闲区，则合并
如图所示：

3、动态分区的数据管理结构

动态分区为了更好的管理分区，也需要有相应的数据结构支持
有：可用表、自由链、请求表

可用表：记录哪些分区可用（空闲）
自由链表：每个空闲内存区会记录本区的大小和下一个空闲区的开始地址
从而将整个空闲区连接起来
请求表：描述被调度进程所需要的内存资源大小

上述三个表的逻辑结构如下图所示：

现在我们将内存给划分好了
之后要做的是给进程分配合理的内存块
同时，对使用完了的进程要进行资源回收
那么，这个过程是如何进行的？

二、分区的分配与回收

（“与” 和 “和”的区别：前者书面，后者口语）

1、固定分区的分配与回收

分配：
1、当进程被调度时，通过请求表请求内存
2、从头开始遍历分区说明表
3、直到找到一个合适的分区，分配之
4、如果直到分区说明表结束都没有匹配，则无法分配

分配算法如图所示：

回收：进程资源使用完毕，直接将对应分区状态设置为空闲即可

2、动态分区的分配

动态分区主要解决三个问题：
1）对请求表的请求内存大小，要从可用表 / 自由链中找到合适的空闲空间
2）分配空闲区后，要更新可用表 / 自由链
3）进程或作业释放资源时，和相邻的空闲区进行合并，并更新可用表 / 自由链

一般的，从可用表 / 自由链中查找空闲区的方法有三种：
最先适应算法、最佳适应算法、最坏适应算法
算法的执行都是建立在特定的数据结构基础上的
例如，折半查找就是建立在数据集处于有序的基础上
上述三个算法，其本质就是不同的数据组织方式
因此，三种算法各自对应不同的数据结构

1）最先适应算法

要求：可用表 / 自由链按起地址递增方式排列
查找机制：
从头逐个查找，一旦找到大于 / 等于所要求内存长度的分区，则结束探索，分配

2）最佳适应算法

要求：可用表 / 自由链按空闲区从小到大的顺序排列
查找机制：
从头逐个查找，直到找到第一满足要求的空闲区，则结束探索，分配

3）最坏适应算法

要求：可用表 / 自由链按空闲区从大到小的顺序排列

查找机制：
从头逐个查找，如果第一个最大的空闲都不匹配，说明整个空间都不会匹配，分配失败，返回
如果匹配，直接给
每一次都找最大的一块给进程

3、动态分区的回收与拼接

被释放的分区需要重新插入可用表 / 自由链中
很好理解，因为资源被使用完后，需要被释放，以备复用
可是为什么非要拼接呢？
因为如果不进行拼接，而直接插入
会导致存在大量的、零碎的可用内存块
直接导致内存浪费，因为很有可能被分割的很小的内存块
可能永远都不会被使用
因此需要拼接
可是怎么拼接呢？
很简单，相邻就拼接
考虑到相邻，自然的会有4种状态：
这四种状态分别是：上下都空闲、上 / 下空闲、上下都不空闲
如图所示：

对四种情况进行拼接与插入处理：
一、上下都空闲
将3个空闲区合并
起始地址取上空闲区起始地址
大小为3块之和
取消后两块在可用表 / 自由链中的记录
修改上空闲去的相关数据

二、上 / 下空闲
将2个空闲区合并
大小为2块之和
修改相关空闲区的数据

三、上下都不空闲
自立为王，单干

4、最先、最佳、最坏算法优缺点

最先适应算法：
速度块，因为最佳/最坏算法都需要对空闲区进行排序，排序本身就需要检索操作
修改时，无需改变该空闲块在表 / 链表中的位置
只需要修改块的起始位置和长度

最佳适应算法：
最佳适应算法将空闲区从小到大排序
找到所允许的最小空闲块
看起来最佳，但是并不一定利用率最高
例如：
前面的部分块长度很小
于是很多进程没法用，只能用后面的块
分配后，剩余的部分又将成为一个小空闲块
这些小空闲块很小，可能永远都不会被使用
同时，增加查找的开销
最坏算法正是基于这种情况进行分配的
先用大的，
于是剩下的空闲块也大
避免被过于分割