【C 数据结构-动态内存管理】3. 伙伴系统管理动态内存

2024-05-08 07:52

本文主要是介绍【C 数据结构-动态内存管理】3. 伙伴系统管理动态内存,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 【 1. 伙伴系统的结构设计 】
  • 【 2. 分配算法 】
  • 【 3. 回收算法 】

  • 伙伴系统 本身是一种动态管理内存的方法,和边界标识法的区别是:使用伙伴系统管理的存储空间,无论是空闲块还是占用块,大小都是 2 的 n 次幂(n 为正整数)。
    例如,系统中整个存储空间为 2 m 2^m 2m 个字。那么在进行若干次分配与回收后,可利用空间表中只可能包含空间大小为: 2 0 2^0 20 2 1 2^1 21 2 2 2^2 22、…、 2 m 2^m 2m 的空闲块。

【 1. 伙伴系统的结构设计 】

  • 伙伴系统中可利用空间表中的结点构成如下图所示:
    header 域表示为头部结点,由 4 部分构成:
    • llinkrlink 为结点类型的指针域,分别用于指向直接前驱和直接后继结点。
    • tag :用于标记内存块的状态,是占用块(用 1 表示)还是空闲块(用 0 表示)
    • kval :记录该存储块的容量。由于系统中各存储块都是 2 的 m 幂次方,所以 kval 记录 m 的值。
      在这里插入图片描述
  • 伙伴系统节点的 C 实现:
typedef struct WORD_b{struct WORD_b *llink;//指向直接前驱int tag;//记录该块是占用块还是空闲块int kval;//记录该存储块容量大小为2的多少次幂struct WORD_b *rlink;//指向直接后继OtherType other;//记录结点的其它信息
}WORD_b,head;
  • 在伙伴系统中,由于系统会不断地接受用户的内存申请的请求,所以会产生很多大小不同但是容量都是为 2 m 2^m 2m 的内存块,所以为了在分配的时候查找方便,系统将大小相同的内存块建立一个链表。对于初始容量为 2 m 2^m 2m 的一整块存储空间来说,形成的链表就有可能有 m+1 个,为了更好的对这些链表进行管理,系统将这 m+1 个链表的表头存储在数组中,就类似于邻接表的结构,如下图所示:
    在这里插入图片描述
  • 可利用空间表的 C 实现:
#define m 16//设定m的初始值
typedef struct HeadNode {int nodesize;//记录该链表中存储的空闲块的大小WORD_b * first;//相当于链表中的next指针的作用
}FreeList[m+1];//一维数组

【 2. 分配算法 】

  • 伙伴系统的分配算法很简单。假设用户向系统申请大小为 n 的存储空间,若 2 k − 1 < n ≤ 2 k 2^{k-1} < n \leq 2^k 2k1<n2k,此时就需要查看可利用空间表中大小为 2 k 2^k 2k 的链表中有没有可利用的空间结点:
    • 如果该链表不为 NULL,可以直接采用头插法从头部取出一个结点,提供给用户使用;
    • 如果大小为 2k 的链表为 NULL,就需要依次查看比 2 k 2^k 2k 大的链表,找到后从链表中删除,截取相应大小的空间给用户使用,剩余的空间,根据大小插入到相应的链表中。
  • 例如,用户向系统申请一块大小为 7 个字的空间,而系统总的内存为 24 个字,则此时按照伙伴系统的分配算法得出: 2 2 2^2 22 < 7 < 2 3 2^3 23,所以此时应查看可利用空间表中大小为 2 3 2^3 23 的链表中是否有空闲结点:
    • 如果有,则从该链表中摘除一个结点,直接分配给用户使用;
    • 如果没有,则需依次查看比 2 3 2^3 23 大的各个链表中是否有空闲结点。假设,在大小 2 4 2^4 24 的链表中有空闲块,则摘除该空闲块,分配给用户 2 3 2^3 23 个字的空间,剩余 2 3 2^3 23 个字,该剩余的空闲块添加到大小为 2 3 2^3 23 的链表中,如下图所示:
      在这里插入图片描述
  • 使用伙伴系统进行存储空间的管理过程中,在用户申请空间时,由于大小不同的空闲块处于不同的链表中,所以 分配完成的速度会更快,算法相对简单

【 3. 回收算法 】

  • 无论使用什么内存管理机制,在内存回收的问题上都会面临一个共同的问题:如何把回收的内存进行有效地整合,伙伴系统也不例外。
  • 当用户申请的内存块不再使用时,系统需要将这部分存储块回收,回收时需要判断是否可以和其它的空闲块进行合并。在寻找合并对象时,伙伴系统和边界标识法不同,在伙伴系统中每一个存储块都有各自的 伙伴当用户释放存储块时只需要判断该内存块的伙伴是否为空闲块,如果是则将其合并,然后合并的新的空闲块还需要同其伙伴进行判断整合,反之直接将存储块根据大小插入到可利用空间表中即可
  • 判断一个存储块的伙伴的位置时,采用的方法为:如果该存储块的起始地址为 p,大小为 2 k 2^k 2k,则其伙伴所在的起始地址为:
    { p + 2 k ,若 p 取余 2 k + 1 = 0 p − 2 k ,若 p 取余 2 k + 1 = 2 k \begin{cases} p+2^k,若p取余2^{k+1}=0\\\\ p-2^k,若p取余2^{k+1}=2^k\end{cases} p+2k,若p取余2k+1=0p2k,若p取余2k+1=2k
  • 例如,当大小为 2 8 2^8 28 ,起始地址为 512 的伙伴块的起始地址的计算方式为:
    由于 512 取余 2 9 2^9 29=0,所以,512+ 2 8 2^8 28=768,即如果该存储块回收时,只需要查看起始地址为 768 768 768 的存储块的状态,如果是空闲块则两者合并,反之直接将回收的释放块链接到大小为 2 8 2^8 28 的链表中。
  • 回收存储空间时,对于 空闲块的合并,不是取决于该空闲块的相邻位置的块的状态;而是 完全取决于其伙伴块。所以即使其相邻位置的存储块时空闲块,但是由于两者不是伙伴的关系,所以也不会合并。这也就是该系统的缺点之一:由于 在合并时只考虑伙伴,所以容易产生存储的碎片

这篇关于【C 数据结构-动态内存管理】3. 伙伴系统管理动态内存的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/969750

相关文章

nvm如何切换与管理node版本

《nvm如何切换与管理node版本》:本文主要介绍nvm如何切换与管理node版本问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录nvm切换与管理node版本nvm安装nvm常用命令总结nvm切换与管理node版本nvm适用于多项目同时开发,然后项目适配no

Redis实现RBAC权限管理

《Redis实现RBAC权限管理》本文主要介绍了Redis实现RBAC权限管理,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1. 什么是 RBAC?2. 为什么使用 Redis 实现 RBAC?3. 设计 RBAC 数据结构

mac安装nvm(node.js)多版本管理实践步骤

《mac安装nvm(node.js)多版本管理实践步骤》:本文主要介绍mac安装nvm(node.js)多版本管理的相关资料,NVM是一个用于管理多个Node.js版本的命令行工具,它允许开发者在... 目录NVM功能简介MAC安装实践一、下载nvm二、安装nvm三、安装node.js总结NVM功能简介N

SpringBoot中使用 ThreadLocal 进行多线程上下文管理及注意事项小结

《SpringBoot中使用ThreadLocal进行多线程上下文管理及注意事项小结》本文详细介绍了ThreadLocal的原理、使用场景和示例代码,并在SpringBoot中使用ThreadLo... 目录前言技术积累1.什么是 ThreadLocal2. ThreadLocal 的原理2.1 线程隔离2

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

Linux内存泄露的原因排查和解决方案(内存管理方法)

《Linux内存泄露的原因排查和解决方案(内存管理方法)》文章主要介绍了运维团队在Linux处理LB服务内存暴涨、内存报警问题的过程,从发现问题、排查原因到制定解决方案,并从中学习了Linux内存管理... 目录一、问题二、排查过程三、解决方案四、内存管理方法1)linux内存寻址2)Linux分页机制3)

高效管理你的Linux系统: Debian操作系统常用命令指南

《高效管理你的Linux系统:Debian操作系统常用命令指南》在Debian操作系统中,了解和掌握常用命令对于提高工作效率和系统管理至关重要,本文将详细介绍Debian的常用命令,帮助读者更好地使... Debian是一个流行的linux发行版,它以其稳定性、强大的软件包管理和丰富的社区资源而闻名。在使用

SpringBoot使用minio进行文件管理的流程步骤

《SpringBoot使用minio进行文件管理的流程步骤》MinIO是一个高性能的对象存储系统,兼容AmazonS3API,该软件设计用于处理非结构化数据,如图片、视频、日志文件以及备份数据等,本文... 目录一、拉取minio镜像二、创建配置文件和上传文件的目录三、启动容器四、浏览器登录 minio五、

IDEA中的Kafka管理神器详解

《IDEA中的Kafka管理神器详解》这款基于IDEA插件实现的Kafka管理工具,能够在本地IDE环境中直接运行,简化了设置流程,为开发者提供了更加紧密集成、高效且直观的Kafka操作体验... 目录免安装:IDEA中的Kafka管理神器!简介安装必要的插件创建 Kafka 连接第一步:创建连接第二步:选

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖