堆分配算法

内存空间时的大小却是不一定的,从数个字到数个GB都是有可能的。于是我们必须将堆空间管理起来,将它分块地按照用户需求出售给最终的程序,并且还可以按照一定的方式收回内存。其实这个问题可以归结为:如何管理一大块连续的内存空间,能够按照需求分配、释放其中的空间,这就是堆分配的算法。堆的分配算法有很多种,有很简单的(比如这里要介绍的几种方法),也有些很复杂、适用于某些高性能或者有其他特殊要求的场合.

1. 空闲链表

空闲链表( Free List)的方法实际上就是把堆中各个空闲的块按照链表的方式连接起来,当用户请求一块空间时,可以遍历整个列表,直到找到合适大小的块并且将它拆分;当用户释放空间时将它合并到空闲链表中。

我们首先需要一个数据结构来登记堆空间里所有的空闲空间,这样才能知道程序请求空间的时候该分配给它哪一块内存。这样的结构有很多种,这里介绍最简单的一种空闲链表空闲链表是这样一种结构,在堆里的每一个空闲空间的开头(或结尾)有一个头( header),头结构里记录了上一个(prev)和下一个(next)空闲块的地址,也就是说,所有的空闲块形成了一个链表。如图10-15所示

在这样结构下如何分配空间呢?

首先在空闲链表中查找足够容纳大小的一个空闲块,然后将这个块分为两个部分,一部分为程序请求的空间,另一部分为剩余的空闲空间。下面将链表里对应的原来的空闲块的结构更新为新的剩下来的空闲块,如果剩下的空闲块大小为0,则直接将这个结构从链表里删除。图10-16演示了用户请求了一块和空闲块2恰好相等的内存空间的堆的状态

这样的空闲链表实现尽管简单,但在释放空间的时候,给定一个已分配块的指针,堆无法确定这个块的大小。一个简单的解决方法是当用户请求k个字节空间的时候,我们实际分配k+4个字节,这4个字节用于存储该分配的大小,即k+4。这样释放该内存的时候只要看看这4个字节的值,就能知道该内存块的大小,然后将其插入到空闲链表里就可以了。

当然这仅仅是最简单的一种分配策略,这样的思路存在很多问题。例如,一旦链表被破坏,或者记录长度的那4字节被破坏,整个堆就无法正常工作,而这些数据恰恰很容易被越界读写所接触到

2. 位图

针对空闲链表的弊端,另一种分配方式显得更加稳健。这种方式称为位图( Bitmap),其核心思想是将整个堆划分为大量的块( block),每个块的大小相同。当用户请求内存的时候,总是分配整数个块的空间给用户,第一个块我们称为已分配区域的头(Head),其余的称为己分配区域的主体(Body)。而我们可以使用一个整数数组来记录块的使用情况,由于每个块只有头/主体空闲三种状态,因此仅仅需要两位即可表示一个块,因此称为位图。

Q&A

假设堆的大小为1MB,那么我们让一个块大小为128字节,那么总共就有1M/128=8k个块,可以用8k/(32/2)=512个int来存储。这有512个int的数组就是一个位图,其中每两位代表一个块。当用户请求300字节的内存时,堆分配给用户3个块,并将位图的相应位置 标记为头或躯体。 图10-17为一个这样的堆的实例

这个堆分配了3片内存,分别有2/4/1个块,用虚线框标出。其对应的位图将是:

(HIGH) 11 00 00 10 10 10 11 00 00 00 00 00 00 00 10 11 (LOW)

其中11表示H(HEAD),10表示主体(Body),00表示空闲(Free)

这样的实现方式有几个优点:

  • 速度快:由于整个堆的空闲信息存储在一个数组内,因此访问该数组时cache容易命中;
  • 稳定性好:为了避免用户越界读写破坏数据,我们只须简单备份一下位图即可,而且即使部分数据被破坏,也不会导致整个堆无法工作
  • 块也不需要额外信息,易于管理

当然缺点也是显而易见的

  • 分配内存的时候容易产生碎片。例如分配300字节的时候,实际分配了3块即384个字节,浪费了84个字节
  • 如果堆很大,或者设定的一个块很小(这样可以减少碎片),那么位图将会很大,可能会失去cache命中率很高的优势,而且也会浪费一定的空间。针对这种情况,我们可以使用多级的位图。

3. 对象池

以上介绍的堆管理方法是最为基本的两种,实际上在一些场合,被分配对象的大小是较为固定的几个值,这时候我们可以针对这样的特征设计一个更为高效的堆算法,称为对象池。

对象池的思路很简单,如果每一次分配的空间大小都一样,那么就可以按照这个每次请求分配的大小作为一个单位,把整个堆空间划分为大量的小块,每次请求的时候只需要找到个小块就可以了

对象池的管理方法可以采用空闲链表,也可以采用位图,与它们的区别仅仅在于它假定了每次请求的都是一个固定的大小,因此实现起来很容易。由于每次总是只请求一个单位的内存,因此请求得到满足的速度非常快,无须查找一个足够大的空间。

实际上很多现实应用中,堆的分配算法往往是采取多种算法复合而成的。比如对于 glibc来说,它对于小于64字节的空间申请是采用类似于对象池的方法;而对于大于512字节的空间申请采用的是最佳适配算法:对于大于64字节而小于512字节的,它会根据情况采取上述方法中的最佳折中策略:对于大于128KB的申请,它会使用mmap机制直接向操作系统申请空间。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 首次适应算法、最佳适应算法和最差适应算法

    关于首次适应算法、最佳适应算法和最差适应算法,先看一下百度百科的解释,已经说出了三者的最大区别。

    233333
  • Android音频系统

    stream type, strategy, device, output, profile, module : policy

    233333
  • sysfs_create_group创建sysfs接口

    在调试驱动,可能需要对驱动里的某些变量进行读写,或函数调用。可通过sysfs接口创建驱动对应的属性,使得可以在用户空间通过sysfs接口的show和store函...

    233333
  • 无人机软件架构知多少?

    AIAA的会议论文(Infotech@Aerospace 2012),从计算机角度阐述了无人机软件架构,由易科机器人实验室(ExBot.net)分享。 文献信息...

    机器人网
  • Memcached对比Redis

    Memcached Redis 持久化 否(MemcachedDB可以实现) 是(RDB快照和AOF日志) 内存利用率 使用简单的key-...

    Clive
  • 【快报】全自动驾驶汽车上路时间再提前 | 芯片市场激战,英特尔遭围攻

    1 Delphi与Mobileye合作开发全自动驾驶汽车技术 ? 汽车配件供应商Delphi Automotive和Mobileye于23日宣布,将合作开发全自...

    新智元
  • 关于“吴亦凡入伍”H5背后的技术—兼容android【 前端篇】

    作者:nicky, 腾讯Tgideas 前端开发工程师 在“吴亦凡入伍”H5刷爆朋友圈之后,看到网上有较多同学对背后的技术感兴趣,正好借着机会跟大家分享一下。如...

    腾讯大讲堂
  • 如何备份Kubernetes和Docker

    用户的容器基础设施需要某种类型的备份。Kubernetes和Docker在灾难之后不会自己构建。用户无需备份每个容器的运行状态,但是需要备份用于运行和管理容器的...

    静一
  • Android WiFi热点开发的示例代码

    上次写了Android连接匿名WiFi的内容。WiFI开发对于应用层开发是比较小众的知识点,不过既然用到了就在此记录下。

    砸漏
  • 「数据分析」精选数据挖掘和机器学习软件列表

    数据挖掘通常与计算机科学有关,并通过统计、在线分析处理、情报检索、机器学习、专家系统(依靠过去的经验法则)和模式识别等诸多方法来实现上述目标。

    首席架构师智库

扫码关注云+社区

领取腾讯云代金券