连续内存分配-shichang

### 内存碎片：
 - 外碎片：内存中两个进程之间的小空闲块，一段时间内任何需要分配的进程的内存需求都大于这个空闲块。
 - 内碎片：因为OS内存的分配只能是2的整数幂，一个程序的内存需求可能刚好小于某一个2的整数幂。例如需求为510字节，但OS只能分配512字节。
<br>
### 动态分区分配：
当程序被加载执行时，分配一个进程指定大小可变的内存块，分区的地址是连续的。其中某些进程可能结束，中间某些内存块空闲。
OS需要维护两个数据结构，一个已占用的内存表，一个未分配的内存表。
<br>
#### 分配策略：
1. `最先匹配：`查找内存分区表，分配第一个可用的空闲分区。空闲分区表按地址顺序排列，释放分区时检查是否可以与临近的空闲分区合并。在高地址空间会有大块的空闲分区。
`缺点：`会造成外部碎片，分配大块是可能需要查询很久空闲分区表。

2. `最佳匹配：`查找分区表时，找出其中最合适的，浪费最少的空闲分区。空闲分区表按从小到大排列，查找时按表查找找到第一个。可以避免大的内存空间被拆分，减小外部碎片的大小
`缺点:` 会造成非常多的外碎片无法被利用，外碎片越是小就越是难被利用起来。进程结束了，需要查找周围的空闲分区看能不能合并，如果可以合并，还需要将合并后的大小重新插入空闲分区表中。所以释放较慢。

3. `最差匹配：`查找分区表时，选择空闲块最大的分区。
分区表按从大到小排序，查询分区表的时间短，分配迅速，如果多个进程需要中等大小的内存大小，则这种方式是最优的，不会造成太多的内存碎片。
`缺点:`容易破坏大的内存空间，进程结束时也需要和周围的空闲空间合并，合并后再将新的大小重新插入空闲分区表中，所以释放较慢

<br>
### 碎片整理：
1. `紧凑(压缩)`:
将散开排布的进程占用的内存位置全部挪动到连续的空间，合并这之间所有的外部碎片。这是在程序运行时挪动地址，所以需要上面的程序全部支持动态重定位，否则压缩之后程序会崩溃。一般选择的挪动时机是当前运行的进程处于等待状态时

2. `分区对换`：
通过抢占并回收处于等待状态的进程的分区，来增大可用的内存空间，将其分配给更需要的进程。被抢占的进程的状态保存在外存中。在linux系统中有一个分区叫做swap交换分区，该分区就是用来存储被抢占的进程的状态信息的分区。通过换入和换出实现，但是从内存到外存的IO开销非常大，所以需要权衡。