内存碎片及伙伴算法

时间:2022-08-16 14:26:28
今天学习到 Linux 内存分配问题,有些不明白,什么是内存碎片问题?以及为什么maloc()等函数每次分配内存后都会用 free()释放资源,为什么还会产生碎片问题?内存碎片问题如何产生 及 如何解决呢?
以下是自己今天学习心得:
内存碎片概念:
内存碎片问题分为内部碎片和外部碎片两种。
   1.内部碎片是由于采用固定大小的内存分区,当一个进程不能完全使用分给它的固定内存区域时,就将该进程分配后剩余的部分称为内碎片。通常内碎片难以避免;
   2.外部碎片是由于某些未分配的连续区域太小,不足以为任意进程分配内存资源的内存块大小,此时称这些不可用的内存块大小为外部碎片


对于malloc()等函数,每次申请完内存后都会释放,但每次释放的内存大小及释放时间的不同就会产生内存碎片。比如:在内存单元100的起始地址到内存单元200之间,共申请了100个1字节的空间。在free()时,释放了内存地址为奇数的内存单元(如101,103,105……)而偶数单元不释放,释放了50个1字节空间,虽然总空间数为50字节,但由于这50个1字节空间不连续。当下次要申请2字节的内存单元时,却无法在100到200的内存地址单元中申请到空间,于是就产生内存碎片问题。


为什么会产生内存碎片?
对于内存的分配方法有:连续地址分配、分页机制和分段机制以及段页式(网上有很多关于内存地址分配的文章,都很不错,可以了解一下)
连续地址分配:固定分区分配会产生内碎片问题,动态分区分配会产生外碎片问题

分页机制:相比较固定分配分区,内碎片问题已经明显减少

分段机制:消除内碎片问题,但会产生外碎片问题



伙伴算法可以解决外碎片问题,其算法思想如下:

无论已经分配的分区还是空闲分区,其大小均为2的k次幂,k为整数,1<=k<=m,其中2^1表示分配的最小分区大小,2^m 表示分配的最大分区的大小。在系统开始运行时,整个内存区是一个大小为2^m的空闲分区,随着系统运行,空闲区的不断划分会形成若干不连续的空闲分区,将这些空闲分区按照分区的大小进行分类,对于每一类具有相同大小的所有空闲分区,单独成立一个空闲分区双向链表。这样,不同大小的空闲分区就形成了k(0<=k<=m)个空闲分区链表。

当需要为进程分配一个长度为n 的存储空间时,首先计算i 的值,使2^(i-1)< n < 2^ i ,然后在空闲分区大小为i 的空闲区链表中查找。若找到,则把该空闲分区分配给该进程。否则,表明长度为2^ i 的空闲分区已经耗尽,则在长度为2^(i+1)的空闲分区链表中查找。若存在大小为2^(i+1)的空闲分区,则将该分区分为连个大小均为2^ i 的块,一个块分配给该进程,一个块挂载在长度大小为2^ i 的空闲分区链表中。若大小为2^(i+1)的空闲分区也已经耗尽,则寻找大小为2^(i+2)的空闲分区,若找到,则对该分区进行两次划分,第一次划分,将大小为2^(i+2)的分区分为两个大小为2^(i+1)的空闲分区,一个挂载在大小为2^(i+1)的空闲分区上,一个再次分割为两个大小为2^ i 的分区,一个挂载在大小为2^ i 的空闲分区上,一个用于分配给该进程;如果未找到大小为2^ ( i+2 ) 的空闲分区,则在2^( i+3) 的空闲分区上寻找,一次重复以上步骤,指导找到空闲区


在Linux中将这内存分为10个空闲分区链表,0-9,大小范围是:2^0 - 2^9

内存碎片及伙伴算法

以上过程的逆过程就是伙伴算法的释放过程,释放过程需要满足两个条件:1.两个块具有相同的大小  2.它们的物理地址是连续的

也正是基于以上两个条件才称该算法为伙伴算法



Linux伙伴算法中涉及到的数据结构:

free_area_t    free_area[MAX_ORDER];

我们再次对free_area_t  给予较详细的描述。

#difine   MAX_ORDER  10

type struct free_area_struct {

           struct list_head   free_list

                 unsigned  int    *map

 } free_area_t

内存碎片及伙伴算法

 其中list_head域是一个通用的双向链表结构,链表中元素的类型将为mem_map_t(struct page结构)Map域指向一个位图,其大小取决于现有的页面数。free_areak项位图的每一位,描述的就是大小为2k页面的两个伙伴块的状态。如果位图的某位为0,表示一对兄弟块中或者两个都空闲,或者两个都被分配,如果为1,肯定有一块已被分配。当兄弟块都空闲时,内核把它们当作一个大小为2k+1的单独快来处理