内存分配算法

逃离我推掉我的手 2023-06-16 02:24 7阅读 0赞

首次适配算法，存储管理器沿着段链表进行搜索，找到第一个足够大的空闲块，将一部分分配给进程使用，另一部分作为空闲块，等待下一次分配。  
首次适配尽可能减少搜索链表节点。对首次适配进行很小的修改就能得到下次适配算法，他的工作方式和首次适配算法相同，不同点是每次找到空闲区的时候都记录当时的位置。以便下次从头开始搜索。  
最佳适配算法，最佳适配搜索会遍历整个链表，找到满足要求的最小空闲块，最佳适配分配的找到的空闲区最接近实际需要的空闲区大小，所以会避免拆分更大的空闲区。  
最佳适配算法相比于首次适配会产生更多的小的空闲块，这些空闲块以后很可能不会再用到。  
最差适配算法，总是分配最大的可用空闲区，是新的空闲区比较大并且可以继续使用。

释放内存并合并的时候需要考虑的相邻区域的四种组合：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70]

[FF、BF、WF算法的实现][FF_BF_WF]

[伙伴内存分配系统的实现][Link 1]

伙伴系统的思路：

> 伙伴系统是一种分离适配的特例，其中每个大小类都是2的整数次幂。基本思路是假设一个堆的大小是2的m次方个字节，我们为每个块大小为2的k次方维护一个分离空闲链表，其中0<=k<=m。请求块的大小向上舍入到最接近的2的幂，最开始只有2的m次方字节的空闲块。  
> 为了分配一个大小为2的k的块，我们找到第一个可用的、大小为2的j次方的块，其中k<=j<=m，如果我们j=k，那我们完成了，否则，我们递归二分割这个块，直到j=k，当我们进行这样的分割的时候，每个剩下的半块也叫作伙伴，被放置到相应的空闲链表中。要释放一个大小为2的k的块，我们继续合并空闲的伙伴，当遇到一个已经分配的伙伴时，我们就停止合并。  
> 伙伴系统的优点就是快速搜索，和快速合并。主要缺点就是要求快的大小是2的幂可能导致显著的内部碎片。因此伙伴系统分配器不适合通用目的的工作负载。然而，对于某些特定应用的工作负载，其中块的大小预先知道是2的幂次。

在我实现的伙伴系统中，并没有创建2的k次幂的空闲链表，最初空闲块的大小是是4096次方字节，存在空闲块容器中，当要求申请1000字节的内存的时候，我们将1024字节的内存空间分出去，下面要是需要100字节内存，我们就将128字节内存分出去，…根据下面需求，我们将初始时4096字节的内存块大小分完了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 1]  
内存分配完成，释放是一个寻找伙伴(与当前要释放的空闲块能连续，并且块的大小是相等的)的的过程。为了方便查找，我们将空闲块链表按照地址从小到大排序。当前空闲块容器中数量是0，当我们释放进程2的时候，会在空闲链表中找，有没有相等大小的空闲块，并且起始地址和当前要回收到内存块能组合成一个连续的空闲块。比如我们要释放的内存大小是128，该内存的起始地址为1024，没找到，就将要释放的内存块加到空闲链表中。否则，我们在空闲链表中找到大小为128的空闲块。  
并且不问需满足以下情况：

*  要是该空闲块的起始地址小于要释放的块的起始地址，并且起始地址+块大小等于要释放的内存块的起始地址，则将两个内存块合并。
 *  要是空闲块的起始地址大于要释放的内存块的大小，并且释放的内存块起始地址+块大小和空闲块的起始地址相等。则将两个内存块合并。
 *  否则将为要释放的内存块创建新的空闲块，并加到空闲链表。

最后，给容器按照地址再排序，检查空闲容器中是否还存在伙伴关系的块，有的话，就合并，检查到没有为止！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191126181803689.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70
[FF_BF_WF]: https://github.com/Request2609/ck_webServer/tree/master/memory_management
[Link 1]: https://github.com/Request2609/ck_webServer/tree/master/buddy
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191126180842796.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx,size_16,color_FFFFFF,t_70