[操作系统笔记]连续分配管理方式

内容系听课复习所做笔记，图例多来自课程截图

连续分配管理方式

连续分配：指为用户进程分配的必须是一个连续的内存空间

相应地，非连续分配可以是离散的

---

对于固定分区分配，需要有一个分区说明表，类似下表：

当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表，从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状态为“已分配”。

动态分区分配的诸多问题

1. 使用什么样的数据结构记录内存使用情况
2. 当多个空闲分区都能满足需求时，应该选择哪个分区进行分配
3. 如何进行分区的分配与回收操作

记录内存使用情况的数据结构

分为两种：

• 空闲分区表（长得跟上面那个表挺像，有分区号、分区大小、分区起始位置等）
• 空闲分区链（是双向链表）

动态分区分配算法

把一个新作业装入内存时，须按照一定的动态分区分配算法，从空闲分区表（或空闲分区链）中选出一个分区分配给该作业。由于分配算法算法对系统性能有很大的影响，因此人们对它进行了广泛的研究。

首次适应算法

实现方式：空闲分区以地址递增的次序排列。每次分配内存时按顺序查找（从地址最小的空闲分区开始）空闲分区链（或空闲分区表），找到首个大小能满足要求的空闲分区。

当然，分配完之后肯定要修改原空闲分区表（链）的数据，比如把第二个分区（大小4MB）分配给一个需要3MB空间的进程，那么分区表就得把第二个分区大小改为1MB。

最佳适应算法

算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区

原则就是：优先使用更小的空闲区

如何实现：空闲分区按容量递增次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

找到的必然是满足需要的最小的空闲分区

---

缺点：每次都选最小的分区进行分配会留下越来越多的、很小的、难以利用的内存块（因为用来分配的空闲分区大小不总是和需要的空间大小相同，因此总会留下空余的、更小的新的空闲空间）。因此这种方法会产生很多的外部碎片。

最坏适应算法

又称：最大适应算法（Largest Fit）

算法思想：为了解决最佳适应算法的问题――即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。

如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表）,找到大小能满足要求的第一个空闲分区。

如果分配时第一个空闲分区都不能满足需要，那后面的也不用看了，肯定不行

缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大、更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。

邻近适应算法

算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

如何实现：空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表)，找到大小能满足要求的第一个空闲分区。

---

首次适应算法每次都要从头查找，每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来（最佳适应算法的优点）

邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用（划分为小分区），最后导致无大分区可用（最大适应算法的缺点)

总结

最佳适应和最坏适应是有额外开销的，即对空闲空间的按大小进行排序；但是首次适应和邻近适应没有。

如何进行分区的分配与回收

分配：如果采用分区表，就得修改其中条目（分区大小和起始地址），如果一整条记录对应的分区都被分配了，那么就删掉这条记录（因为记录是要记录空闲的）

回收：如果回收的空间挨着（分为前边挨着、后边挨着和前后两边都挨着）已记录的空闲空间，就得在记录中将之合并；如果回收区的前后均未邻接空闲分区，则应增加（新建）记录

看好了啊，回收一共是四种情况：前边挨着、后边挨着、前后两边都挨着和前后两边都不挨着空闲空间

总而言之的原则就是相邻的空闲区间要合并

---

分区表各表项的顺序不一定按照地址递增顺序排列，具体的排列方式需要依据动态分区分配算法来确定。

内部碎片和外部碎片

内部碎片：分配给某进程的内存区域中，如果有些部分没有用上。
外部碎片：是指内存中的某些空闲分区由于太小而难以利用。

如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。

可以通过紧凑技术（或称拼凑技术, Compaction）来解决外部碎片