内存的分配与回收（笔记）

内存的分配与回收

     -- =（内存管理）分区的分配与回收

---

1. 固定分区时的分配与回收。

     关键点，需要一张描述不用分区使用情况的分区说明表。

     分配时，只要存储管理程序根据请求查询分区说明表（或链表），从中找出一个满足要求的空闲分区，将其分配给申请者。

     回收时，操作就更简单了，不需要内存资源了，管理程序只要将对应的分区状态置为为使用即可。

2. 动态分区时的分配与回收。

     不同于固定分区方案，该方案需主要解决三个问题：

     1）分配程序（算法），从分区表寻找（最）合适的空闲分配出去。

     2）分配之后，更新分区表。

     3）回收算法，回收（释放）分区时需和相邻的空闲区进行链接合并，更新分区表。

     分配算法有三种常用算法包括最先适应法（first fit algorithm），最佳适应法（best fit algorithm）和最坏适应法（worst fit algorithm）。

     a. 最先适应法，要求分区表（表或自由链表）按起始地址递增的次序排列。该算法的最大特点是一旦找到大于或等所要求内存长度的分区则结束搜索。接着，从找到的分区划分要求的长度分配出去，并把余下部分与相邻分区合并（若相邻空闲区存在的话），更新分区表。

          1. 搜索分区表空闲区大小大于或等于申请大小alloc_size，若找到则继续2，否则停止分配失败；

          2. 找到合适空闲区A，若其大小a_size==alloc_size，直接标记分区A为“使用区”完成。

          3. 若a_size > alloc_size，切分A为A1（alloc_size），A2（a_size-alloc_size），标记A1“使用区”，A2“空闲区”。

     b. 最佳适应法，从分区表寻找最合适的空闲区分配。这里的最合适标准可以认为是空闲区的大小与要求的大小相差最小。

          1. 遍历分区表找最接近于申请大小alloc_size空闲区B，若找到则继续2，否则停止分配失败；

          2. 找到最合适空闲区B，若其大小b_size==alloc_size，直接标记分区A为“使用区”完成。

          3. 若b_size> alloc_size，切分B为B1（alloc_size），B2（b_size-alloc_size），标记B1“使用区”，B2“空闲区”。

   c. 最坏适应法，从分区表寻找最大的空闲区分配。

          1. 遍历分区表找最大空闲区W，大小为w_size，若w_size >= alloc_size则继续2，否则停止分配失败；

          2. 找到最合适空闲区W，若其大小w_size==alloc_size，直接标记分区A为“使用区”完成。

          3. 若w_size> alloc_size，切分W为W1（alloc_size），W2（w_size-alloc_size），标记W1“使用区”，W2“空闲区”。

     （详细介绍可从网络搜索参考资料）

3. 几种分配算法的比较

     a. 从搜索速度上看，最先适应算法具有最佳性能。另一个有点就是尽可能地利用了低地址空间，从而保证高地址有较大的空闲区来放置要求内存较多的进程或作业。

     b. 最佳适应法找到的空闲区是最佳的，最合适用户要求的可用空闲区。但这样做在某些情况下并不一定提高内存的利用率。倒是可能导致内存碎片更多，因为分区表可能剩下越来越多的“小碎片”不能满足后续使用。

     c. 最坏适应算法正是基于不留碎片空闲区这点出发的，它选择最大空闲区来满足申请的要求，以期分配后的剩余部分仍能后续分配使用。

最后，总之三种算法各有特长，针对不同的请求队列，效率和功能不一样。实际项目开发使用，可以适度地多者结合一起使用。

……

（完）