当前位置: 首页 > Linux kernrl, 内存管理 > 正文

[原]内存管理器(三)使用边界标识法实现内存分配器

使用边界标识法实现简单分配器

前言

前一篇我们已经了解了边界标识算法和数据结构,其实边界标识法还是比较复杂的,它的难点在于对C的使用的淋漓尽致,以及复杂的逻辑关系。所以我们还需要多思考,多体会才能领悟个中精髓,其实我昨天在学习那个小例子的时候由一瞬间感觉如果用C++实现可能更方便,所以再此决定等这几篇完成,就使用C++实现一个小小的实例。
言归正传,我们今天需要看一个用C使用边界标识法实现的简单分配器,这个分配器主要是首先重内存申请一大片内存,然后根据程序的调用来分配空间的有点像实现一个malloc/free 函数。

学习目标

1.通过这个实例,加深边界标识法的理解。
2.对这个实例从效率,多线程等角度进行测试。
3.为后边伙伴算法打基础。

PS:个人还是觉得大学学习两件事:一个看天,一个看自己。
1.看天是根据自己的性格特点,兴趣爱好学习。
2.看自己处了努力学习外,还有练就总结的能力,大学的课废话太多。(又跑偏了)

__START

块的结构

malloc

如图所示
基本上一个堆块的大小就是这个样子的,并不陌生呢,我前边已经介绍过了,基本都是由头部,内存块,尾部组成的。

这里需要说明的是:
标志位已经不再是一个int了,而是3位,因为内存对齐的关系我们需要按照4/8字节对齐,假设这里按照4字节对齐,那么就是0~31个位,我们释放低3位来作为状态的标识。

举个例子:
假设我们有一个已经分配的块大小为24(0x18) 字节。那么它的头部是
0x00000018 | 0x1 = 0x00000019

再加设我们有一个没有分配的块大小为40字节。那么它的头部是
0x00000028 | 0x00 = 0x00000028

在有效载荷后边由一块填充块,这个块是不使用的,因为现在用不上不代表以后都用不上,所以我们要为可持续发展做长远的考虑。

安置已分配的块

放置策略

首次适配 :每一次都从头开始给它匹配一个可以使用的块。
下次适配 :每次从上次分配的块后+1 开始匹配一个块。
最佳适配 :每次遍历整个链表,然后找到一个我们认为合适的块给它。
这些和我们之前搞的东西很像。

申请额外的空间

当我们的预申请的对空间不够用时,我们就可以调用sbrk 函数来提升堆的大小。

基本思路纵向导图

malloc
我们使用系统调用mmap( )函数从内存中请求一片100MB 的大小的空间当作我们的对空间,初始化一个序言块这个主要是为了便与我们后边的边界计算。

分步解析内存管理系统

0.我们的变量和一些宏处理

1.内存空间申请

效果如图:
init_heap
成功从内存条申请了100MB 的空间

2.初始化我们的堆空间,建立序言块。

效果如图:
mem
现在我们可以看到各个位置已经初始化完毕。

4.堆扩展函数以及新增空闲块函数

5.分配函数malloc( )

6.释放函数free 以及合并函数coalesce

匹配算法这里主要是首次适配

这里都是简单的实现,我们也可以使用下次适配,和最佳适配。
下次适配很简单:
加上:

最佳适配:这里就是改一下for语句就好,读者可以自行实现。但是说明一点,最佳匹配在边界标识法体现的并不强烈,可以说它其实是伙伴算法的特性。

8.其他测试函数

测试与运行

1.测试

运行结果:
结果

可以看到,第一个序言块在分配前后都是1。
计算他们的大小:24 这是对的,首先我们需求10 但是按照8字节对齐,给他们分配16字节大小,然后再加上头和尾各4字节。所以一共:
16 + 8 = 24 字节
并且我们发现,在释放后,我们的程序已经他们合并了。

2.多线程测试

运行结果如图所示:
多线程测试
虽然看到这里在多线程的时候可以执行,但是确实线程极不安全的,最简单的来说多个线程一个锁都没有用到,这怎么可能支持多线程,所以不能支持多线程,后续我们还会对这个分配器进行改造,甚至是重构!

my_malloc VS sys_malloc 和系统的malloc函数对比

效果如图
测试结果
我被系统完爆。。。.。。.。.。。。。.。
当然这只是一个简单的实现,以后再做优化。

预告:

下来:
内核内存,伙伴算法。

作者:zmrlinux 发表于2015/10/16 17:29:54 原文链接
阅读:50 评论:0 查看评论
]]>

本文固定链接: http://zmrlinux.com/2015/10/17/%e5%8e%9f%e5%86%85%e5%ad%98%e7%ae%a1%e7%90%86%e5%99%a8%ef%bc%88%e4%b8%89%ef%bc%89%e4%bd%bf%e7%94%a8%e8%be%b9%e7%95%8c%e6%a0%87%e8%af%86%e6%b3%95%e5%ae%9e%e7%8e%b0%e5%86%85%e5%ad%98%e5%88%86%e9%85%8d/ | Kernel & Me

该日志由 root 于2015年10月17日发表在 Linux kernrl, 内存管理 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: [原]内存管理器(三)使用边界标识法实现内存分配器 | Kernel & Me