操作系统-内存管理2(连续内存分配)

内存分配分为连续内存分配和非连续内存分配。连续内存分配是指为进程分配的内存空间必须是一个连续的区间。

一、连续内存分配

连续内存分配分为单一连续分配、固定分区分配和动态分区分配。前两种分配方式会产生内部碎片，后一种会产生外部碎片。
内部碎片：
进程所属内存区域内产生的碎片
外部碎片：
内存中某些空闲区域太小而难以利用

1.1 单已连续分配：
同一时刻，用户区内存中只有一个进程，只支持单道程序。无外部碎片，有内部碎片(应为此时整个用户区都属于该进程)

1.2 固定分区分匹配：
支持多道进程，内存分为若干个大小固定的区域，每个进程只能分配一个区域。无外部碎片，有内部碎片。分区方式有2种：
1）分区大小相等
2）分区大小不等

1.3 动态分区分配:
支持多道分区，进程载入内存时，根据进程大小动态的分配内存。无内部碎片，有外部碎片。这种分配方式会产生空闲内存，空闲内存的表示方式有两种方式：
1）空闲分区表
分区表包括分区号，分区大小，起始地址，使用状态等信息。
2）空间分区链
分区链包括分区大小以及指向前一个空间分区的指针(内存起始地址)和后一个分区的指针。

外部碎片可以使用紧凑技术来解决。当进程运行完毕释放内存后，需要合并多个空间内存。

1.3.1 动态分区分配算法
当有一个进程要载入内存，如何从空闲分区表或者分区链中选择合适的分区给进程？有4中分配方式：
1）首次适应算法
空闲分区按照地址从小到大排列，找到第一个满足所需空间的分区分配给进程。(如果有剩余空间，只需要将链表中该分区的大小更新为剩余大小即可)

优点：算法开销小(不需要重排)
缺点：每次都要从头开始查找满足要求的分区，如果链表前面的分区基本使用殆尽，还是会查找一遍，有重复查找的消耗。

2）最佳适应算法
分区按照容量递增排序，找到第一个满足要求的分区。
优点：会有更多大的内存分区被保留下来，以满足大分区进程需求
缺点：会产生大量的小的、难以利用的内存碎片。算法开销大(需要对空闲内存分区进行重排)

3）最差适应算法
和最佳适应算法相反，将分区按照大小倒序排列，找到第一个最大的满足要求的分区。
优点：可以减少难以利用的小碎片
缺点：大分区在前面，容易被利用完，不利于大进程的分配。算法开销大(分区重排)

4）邻近适应算法
针对首次适应算法查找次数开销大的情况，邻近适应算法每次从上次查找的地方开始查找。(链表是循环链表)
优点：不用每次都从首部查找，将减少查询开销；算法开销小(不需要重排)
缺点：会使得高地址的大分区也会被用完。

整个连续分配小结如下图：