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

[原]内存管理器(二)边界标识法

边界标识算法

前言

这个算法是什么

这个算法的特点

图解这个算法

数据结构

这就是抽象的链表节点,分别由头head,空间(内存块),尾tail ,组成。
其中表头由4个部分组成。
llink : 这个数据结构主体是循环链表,所以这个指针指向前一个节点。
tag : 标示位:1标示为已分配块,0标示未分配块。
size : 标示这个节点的大小(包括头部和尾部)。
rlink : 由于是双向循环链表,这个指针指向后一个节点。

表尾由2个部分组成:
uplink : 指向本节点的头部。
tag : 同上标示分配情况。

边界标示法

其中这些节点的链接形式如图所示,基础是双向循环链表并且包含上述结构体。

节点数据结构

这个算法其他一些要注意的地方

  1. 假设每次需要找m 个大小,但是我们每次都分配n 给它,那么久而久之,就会有很多的m-n 个空间散落于链表中,所以我们需要设置一个标准值e,当m-n <= e 的时候,就将m 的空闲整块分配给它,反之,我们就分配想当需求大小的空间。
  2. 如果收每一次都从头开始寻找就是首次匹配,由于已经进行多次,必然前边会聚集较多的小块,所以我们应当每次分配一次就将,表头指向它已经分配的后边的一个节点,这样就能基本保证每一次的进行首次匹配的效果了。

回收算法:

回收的思想很简单,根据它前后块的不同,总共有4中情况。
1.前后都已经占用
直接将内存块插入。
2.前一个已经被占用,后一个没有被占用。
我们直接将后一个,和待回收的块合并成一个完整的块。
3前一个没有被占用,后一个已经被占用。
我们将前一个和待回收的块合并成一个完整的块。
4前一个与后一个都没有被占用。
我们将三个块全部合并成一个完整的未分配块。

下面就来看一个使用边界标识法的空间管理简例

参考资料:
《CSAPP》
《数据结构(严尉敏)》
http://blog.csdn.net/fuming0210sc/

作者:zmrlinux 发表于2015/10/12 22:54:06 原文链接
阅读:32 评论:0 查看评论
]]>

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

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