关于堆内存管理?

jinry

在C中,很熟悉的一种的用法就是malloc和free 的方法使用堆内存,但是OS如何实现这些内存的管理,比如,我malloc一块100 bytes的内存, 我free的话,他怎么知道是要free掉多大一块内存

同时又怎么样保证不会太多的碎片导致实际有很多内存,但是不能分配一大块内存的情况?,所说是以bitmap的方式来实现的,但是具体怎么样我还是不是太清楚

有没有人熟悉这块的东西,给讲讲?

iptton

操作系统原理课程的内容

问题一：我的猜测是（好像有看过书说过），指针并非仅仅一个数字，而是一个包含数据类型长度的结构体
问题二：内存回收算法很多，不过我没背熟。。

[ 本帖最后由 iptton 于 2008-5-14 00:31 编辑 ]

jinry

探讨一下咯.多了解一些的知识,是一些很实在的不太理论的东西,而且可能这算法以后也会可以有参考的地方.....

iptton

当时做操作系统作业时有实现过内存回收算法，不过现在都忘了。。。

刚刚查下书：

内存使用是有一张表来唯护的。。系统通过这张表来查明某块内存是否空闲

[ 本帖最后由 iptton 于 2008-5-14 00:37 编辑 ]

jinry

今天在论坛上有人建议看一本书,但是书名忘了,否则可以回来搜.

其实是有关一个接口的问题,我做的一个组件是有一个接口是要供查询信息的,但是这信息中有一些是不定长的,例如是字符串,所以不能由外面分配内存,我在这块内存填充; 也不能直接把我内部的指针返回给他,防止他误操作之后,我维护的信息不可控,因为我的是做成一个动态数组来维护N多个的信息,如果我返回某一个信息的地址给他,然后他给free掉了,天知道我里面的那段动态数组的内存会是什么样子.所以现在是内部再分配内存,然后把这块新分配的保存一个信息的内存块的地址返回给用户,同时提供另外一个配套接口给释放这块内存,但是用户嫌这样内存copy他又再copy一次,速度会慢很多....


由这个争论,我就想了解一下,OS对堆内存的管理方式...

iptton

好像OS对内存的管理和你说的场景不大同，OS一样是提供一个地址，然后，用户如果要进行非法的操作的话（通过该地址加偏移获取或修改他不应该获取的信息），除非是系统不允许操作的内存地址（比如 0x00001）系统都不会干涉的。
而你的要求好像是要求使用者不应当对系统返回的数据进行free操作。

iptton

找下linux源代码看。。
图书馆有本书说 linux内存管理 的

jinry

原帖由 iptton 于 2008-5-14 00:53 发表
好像OS对内存的管理和你说的场景不大同，OS一样是提供一个地址，然后，用户如果要进行非法的操作的话（通过该地址加偏移获取或修改他不应该获取的信息），除非是系统不允许操作的内存地址（比如 0x00001）系统都不会 ...

是的,就是因为这个,所以我不知道不同的系统会是怎么样的一个处理,也就是说我的动态数组是一个不可知的状态,这是很该死的一种状态

所以我想到,哦,我真的不知道这个会怎么样处理哦,所以就想了解一下,和做的东西没有关系...

hjack

<linux内核完全剖析>里提到:
用户的应用程序动态申请的内存容量由高层次的C库函数malloc管理,内核本身不会插手进行管理.内核已为每个进程在4GB的线性空间中分配了64MB的空间, 内核会为进程使用的代码和数据空间维护一个位置值brk,它指出了进程代码和数据在进程地址空间中的末端位置,当malloc分配内存时,会通过系统调用brk()把要求新增的空间长度通知内核更新brk值,当程序寻址到某个不存在对应物理页面的地址时内核才进行相关的物理内存页面映射.
内核以页面为单位分配和映射物理内存,malloc记录用户程序使用了一页内存的多少字节,剩余的容量将保留给程序再申请内存时使用.
free时,会把所释放的内存块标记为空闲,以备程序再次申请时用.但内核并不分释放掉为这个进程分配的物理内存,直到进程结束.

hjack

惭愧,买了这本书却没怎么看...

hjack

使用的是空闲存储桶描述符链表进行管理 .

iptton

LS这么早...

hjack

对不同清求的内存块大小使用存储桶目录分别进行处理.
----------
|size(16)|
|chain     |  ----->桶描述符
-----------
|size(32)|
|chain     |  ----->
-----------
|size(64)|
|chain     |  ----->
-----------
如,要请求64或大于32小于64的内存时,就从存储桶目录的第三项对应的桶描述符进行分配.

fengogo

指针不会是结构体. 我觉得, 数据类型主要提供给编译器用, 而操作多少字节由编译器帮你完成了. 例如int a = 5 与char c = 'k' , 分别告诉编译器要操作4个字节与操作1个字节内存.  一般malloc返回的void*指针转为你的类型的指针如int* , 则在free的时候就是释放int 个字节. 突然想到个问题, 如果在free之前将该指针转为了其他类型, 是否会导致释放错误?

zaijzhgh

原帖由 fengogo 于 2008-8-7 00:12 发表
指针不会是结构体. 我觉得, 数据类型主要提供给编译器用, 而操作多少字节由编译器帮你完成了. 例如int a = 5 与char c = 'k' , 分别告诉编译器要操作4个字节与操作1个字节内存.  一般malloc返回的void*指针转为你的类 ...

测试一下,不会的说...

gyCai

用malloc分配100K的内存其实不止100K，还有头部空间，包含内存起始地址，内存大小，内存闲置标志等信息，还有尾部空间，标志内存结束等信息。中间一块儿才是那100K的可用空间。

fengogo

刚才试了一下. 虽然我是一个很懒的程序员.
调试进了malloc函数, 不断Next, 来到这个函数:  HeapAlloc(_crtheap, 0, size ? size : 1) , crtheap应该是CRT库自己创建的一个堆.   但是返回值是一个 _CrtMemBlockHeader  结构的指针, 查一下MSDN , 发现调试堆的概念.   .
在调试进free 函数, 找到关键函数 HeapFree , 看看MSDN, 只需要传一个heap handle 与一个指针就可, 再联想几年前学的操作系统,  猜测堆应该是一个链表结构. 将指针传给操作系统的HeapFree, 则操作系统就作一个删除链表结点的动作.  证明了我上面的想法是错误的,   . free(p) 无论p是什么类型, 都不影响free的结果. 本想在release版下看看内存释放里面的内容是否会被擦除, 在VC下无法调试进去 . 下载了个OllyICE的工具, 暂时还不怎么会用 . 一想到这么麻烦,  算了, 还是简单的MFC好啦.
另外在free函数有以下这句 :
if (pUserData == NULL)
            return;
所以 free(NULL) 是没有问题的.  但是重复释放有效的堆内存是会引起错误的, MSDN上说:  Calling HeapFree twice with the same pointer can cause heap corruption, resulting in subsequent calls to HeapAlloc returning the same pointer twice.  前面一句看懂了一点, 后面一句没怎么明白  . 总之, 在free(p)之后, 将 p = NULL 是一个好习惯.

fengogo

据说C是自己管理堆的. 进去malloc发现很乱. 也不知道它怎么把自己加到链表里.

powerwind

原帖由 fengogo 于 2008-8-7 10:16 发表
在free(p)之后, 将 p = NULL 是一个好习惯

就对这句话记忆犹新！！

楼上各位继续讨论

gyCai

每块由malloc分配的内存块都在自己的前面表明自己的大小。有些人用arena这个术语来描述......

以上摘自C专家编程第七章：对内存的思考。