| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3710 人关注过本帖
标题:[原创]内存管理 - 动态开辟内存
只看楼主 加入收藏
jig
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
帖 子:530
专家分:242
注 册:2005-12-27
结帖率:100%
收藏
 问题点数:0 回复次数:14 
[原创]内存管理 - 动态开辟内存

内存管理 - 动态开辟内存
作者:孙靖(Jig) 时间:2006 - 12 - 26
若要转贴或使用本文章介绍的技术,请在你发布的文章或作品中注明出处。


关于内存管理,以前我在PC机上研究系统内核时接触过。那要求在把CPU设置为32位后统一给内存做影射,而我们今天要讨论的内存管理比那是要简单多了。
前两天拿朋友的51单片机开发板玩(用的Keil),突然萌发做个贪食蛇的想法,经过考虑我打算用链表来做(当然,结果证明用链表做很不值得)可在快完工的时候我傻眼啦,蛇在吃了食物后整个屏幕都花啦(用的LCD12864的液晶屏)。本来蛇每吃一个食物其实就是动态再开辟一段蛇身。这样看来显然是动态开辟内存失败,导致绘制蛇身函数在逐个查找链表的每个节点的时候有一环被破坏没有连接到下一环。
再追查下去,应该就是 malloc() 函数没有发挥作用,可是很纳闷 Keil 编译器并没有报告错误。现在问题找到了,可要解决这个问题那就必须自己能构造一个 malloc() 函数。后来我查看了 malloc() 函数,具体实现如下:

struct __mem__
{
struct __mem__ _MALLOC_MEM_ *next; /* single-linked list */
unsigned int len; /* length of following block */
};

typedef struct __mem__ __memt__;
typedef __memt__ _MALLOC_MEM_ *__memp__;
#define HLEN (sizeof(__memt__))
extern __memt__ _MALLOC_MEM_ __mem_avail__ [];
#define AVAIL (__mem_avail__[0])
#define MIN_BLOCK (HLEN * 4)

void _MALLOC_MEM_ *malloc (unsigned int size)
{
__memp__ q; /* ptr to free block */
__memp__ p; /* q->next */
unsigned int k; /* space remaining in the allocated block */

q = &AVAIL;
while (1)
{
if ((p = q->next) == NULL)
{
return (NULL); /* FAILURE */
}
if (p->len >= size)
break;
q = p;
}
k = p->len - size; /* calc. remaining bytes in block */
if (k < MIN_BLOCK) /* rem. bytes too small for new block */
{
q->next = p->next;
return (&p[1]); /* SUCCESS */
}
k -= HLEN;
p->len = k;
q = (__memp__ ) (((char _MALLOC_MEM_ *) (&p [1])) + k);
q->len = size;

return (&q[1]); /* SUCCESS */
}

在这我们可以看到其实他就是利用一个链表在内存中去搜索一段连续的空闲内存,并把首地址传回。可为什么他在我使用的51单片机开发板上没有发挥作用呢?经过分析,我恍然大悟。大家试想一下如果让你去分配一段内存,那么我们就必须有个纪录哪些内存在使用哪些内存空闲的机制。拿TC或VC在PC机上实验一下使用 malloc() 函数看看?它作用发挥良好,看来这个机制是由OS来完成的,而在我们那51单片机的裸机上有个毛的OS啊,也难怪 malloc() 函数不能成功的分配内存。现在找到问题的本质,那我们就来自己构造 malloc() 函数。


建立自己的数据类型:
文件名:MY_Type.h
内容:
/* 自定义类型,方便书写与在不同平台进行移植 */
typedef char INT8;
typedef int INT16;
long INT32;
/*typedef float F32;
typedef double F64;*/

typedef unsigned char UINT8;
typedef unsigned int UINT16;
typedef unsigned long UINT32;
/*typedef unsigned float UF32;
typedef unsigned double UF64;*/


总体具体分析:
为了能有效果的对内存进行管理,我们必须保证内存时时刻刻都能被指定并被纪录是否空闲,那么最好的做法就是先开辟好一定空间再统一管理。当然这段内存空间也必须是全局的。然后我们必须建立一个纪录列表,纪录下内存的使用状态,以便管理。


建立管理机制:
我们可以构造一个结构,将纪录列表和实际使用内存绑定起来。具体代码如下:

#define MEM_COUNT 40 /* 实际使用内存40个字节 */
#define MEM_LIST MEM_COUNT >> 3 /* 管理列表 40/8 = 5个字节 */

typedef struct
{
UINT8 list[MEM_LIST]; /* 管理列表共40位与实际使用内存一一对应,1表示使用中,0表示空闲 */
INT8 mem[MEM_COUNT]; /* 实际使用内存40个字节 */
}MEM; /* 管理机制结构 */
MEM Mem; /* 管理机制数据 */

到此我们就把内存管理机制的核心部分建立起来了,我们可以作这样一个表来说明他的工作方式:

Mem.list[0] ... ... Mem.list[5]
┏━┳━┳━┳┻┳━┳━┳━┓ ┏━┳━┳━┳┻┳━┳━┳━┓
位 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
Mem.mem[] 0 1 2 3 4 5 6 7 32 33 34 35 36 37 38 39 (表一)

从上表一可以很直观的理解 Mem.list 的5个字节共40位,与 Mem.mem 的40个字节一一对应,我们就是通过检查 Mem.list 各位的状态来确定哪些内存在使用哪些内存空闲。


初始化管理系统:
这个很简单,初始化即是内存全部可用,Mem.list 全部置0,具体实现函数:

void Init_mem(void);
void Init_mem()
{
UINT8 i;

for (i = 0; i < MEM_LIST; i++)
{
Mem.list[i] = 0; /* 管理列表共40位全部置0,表示内存可用 */
}
}
经过此函数,Mem.mem 的40个字节内存被标记为可使用。


动态开辟内存:
即像 malloc() 函数那样,分配指定字节的内存,具体实现函数:

void Set_bit(UINT8 Bit, UINT8 mode); /* 设置管理列表的第Bit位为mode */
void *Malloc(UINT8 Size); /* 分配Size字节大小的内存,返回首地址 */

void Set_bit(UINT8 Bit, UINT8 mode)
{
UINT8 Enter = 128;

Enter >>= (Bit % 8);
if (mode)
{
Mem.list[Bit >> 3] |= Enter; /* 将管理列表的第Bit位置1,表示已被使用 */
}
else
{
Mem.list[Bit >> 3] ^= Enter; /* 将管理列表的第Bit位置0,表示处于空闲 */
}
}

void *Malloc(UINT8 Size)
{
UINT8 i, j, k, Enter;


if (Size > MEM_COUNT || Size < 1)
{
return NULL; /* 内存开辟失败,返回空指针 */
}
/* i, j 两层for循环用于查找管理列表目前的空闲内存 */
for (i = 0; i < MEM_LIST; i++)
{
Enter = 128;
for (j = 0; j < 7; j++)
{
if ((Mem.list[i] & Enter) != Enter) /* 查找管理列表,直至查早到空闲内存 */
{
for (k = (i<<3)+j; k < (i<<3)+j+Size; k++)
{
Set_bit(k, 1); /* 从空闲内存首地址开始按Size大小设置被使用的内存 */
}
return &Mem.mem[(i << 3) + j]; /* 内存开辟成功,返回首地址 */
}
Enter >>= 1;
}
}

return NULL; /* 内存开辟失败,返回空指针 */
}

此函数通过检查管理列表,找到空闲内存的启始地址,并把管理列表对应的位置1,并返回空闲内存启始地址。


释放内存:

void Free(UINT8 *Mem1, UINT8 Size); /* 释放开辟的内存 */
void Free(UINT8 *Mem1, UINT8 Size)
{
UINT8 i;

/* Mem1 - &Mem.mem[0] 计算出Mem1指向的地址为Mem.mem的第几元素 */
for (i = (Mem1 - &Mem.mem[0]); i < (Mem1 - &Mem.mem[0] + Size); i++)
{
Set_bit(i, 0); /* 从指定内存首地址开始按Size大小设置被内存空闲 */
}
}

此函数可以“释放”掉被开辟的内存空间。当然,这个释放不是真正意义上的释放,只是把管理列表的相对应位设置为0,表示内存空闲。


好了,到此这个内存管理技术全部介绍完毕。他全部也就四个函数,我们可以做个小实验。

#include <stdio.h>
#include "MY_Mem.h"

int main()
{
INT32 *i;
UINT8 *j;

Init_mem(); /* 初始化内存管理机制 */
j = (UINT8 *)Malloc(sizeof(UINT8));
i = (INT32 *)Malloc(sizeof(INT32));

*j = 30;
*i = 6789324;

printf("%d %d\n", *j, j); /* 打印j所指向地址存放的元素和j */
printf("%d %d\n", Mem.mem[0], &Mem.mem[0]); /* 打印Mem.mem[0]和Mem.mem[0]的地址 */

printf("%ld %d\n", *i, i); /* 打印i所指向地址存放的元素和i */
printf("%d", &Mem.mem[1]); /* 打印Mem.mem[1]的地址 */

Free(j, sizeof(UINT8));
Free(i, sizeof(UINT8));

getch();
}

你可以用TC或VC编译,我用TC编译的结果是:
30 1121
30 1121
6789324 1122
1122

用不同的编译器结构可能有点不同,但 j = &Mem.mem[0], i = &Mem.mem[1];却是绝对成立的,这说明我们的内存管理机制起作用了,我们成功的实现内存的统一管理,并实现了动态开辟内存。


总结:
以上阐述的思路,其实很简单。也许大家在看到这时就觉得这个很小儿科了。我也承认这的确很小儿科。说到底,其实就是先开辟好内存然后再来使用,但作为一个思路我希望对您有一定启发和帮助,同时也希望和大家共同交流和探讨。当然,任何事物和方法都有两面性,这个内存管理也不列外。
缺点:由于要开辟一个列表来纪录内存的使用状态,所以增大了内存的开销,如上所示,40个字节的内存就需要5个字节的管理列表。
优点:这个方法简单方便,在单片机这样的平台上你想像在PC机上那样花大力气去做内存的影射吗?而且那样做内存的额外开销也不一定比此方法的少。并且是按字节大小以顺序方式开辟内存,不存在什么所谓的内存碎片。
当然,大家在使用着套方法的时候一定主要将Malloc()和Free()函数配套使用,并且要保证里面的Size参数一样。当然你也可以进一步改进此方法,让他使用的更合理更安全。

[此贴子已经被作者于2006-12-26 14:32:11编辑过]

搜索更多相关主题的帖子: 内存 动态开辟 单片机 链表 孙靖 
2006-12-26 14:23
一笔苍穹
Rank: 1
等 级:新手上路
帖 子:640
专家分:0
注 册:2006-5-25
收藏
得分:0 

很好,研究一下。

2006-12-26 15:23
ba_wang_mao
Rank: 2
来 自:成都理工大学
等 级:论坛游民
帖 子:297
专家分:27
注 册:2006-11-7
收藏
得分:0 

多年以来还在MSDOS、单片机下搞嵌入式编程,对WINDOWS编程一窍不通,很想了解WINDOWS下病毒编程技术。
2006-12-26 15:24
RockCarry
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:13
帖 子:662
专家分:58
注 册:2005-8-5
收藏
得分:0 
这样的程序我以前在学操作系统的时候也写过,拿出来和大家分享一下,是以前写的,所以不太好。
oIfzADPH.rar (2.61 KB) [原创]内存管理 - 动态开辟内存


2006-12-26 23:59
jig
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
帖 子:530
专家分:242
注 册:2005-12-27
收藏
得分:0 
RockCarry 兄的不错~

个人网站 -  http://.h001.
2006-12-27 11:08
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 

都支持一下


My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2006-12-27 20:42
RockCarry
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:13
帖 子:662
专家分:58
注 册:2005-8-5
收藏
得分:0 
这个根本谈不上内存管理
在现代化的操作系统中,都会利用 MMU 实现内存的分页和虚拟内存的管理。
内存分页和虚拟内存的引入为多任务的实现奠定了基础,
2007-06-08 16:39
RockCarry
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:13
帖 子:662
专家分:58
注 册:2005-8-5
收藏
得分:0 
不过x86的架构实在是太过复杂,ARM也很复杂。
如果真正想从头开始,可以自己设计一个简单的处理器架构,使用软件方式实现这个处理器架构的模拟器。当然一些外设也可以自己设计和模拟出来。然后再以此为基础,搭建自己的计算机系统。然后在这个系统上,自己就可以为所欲为了,先设计一门自己的语言,再通过交叉编译的方法设计并实现一个编译器。然后进行 BootLoader 的开发、OS 的开发,直到应用程序的开发。
由于是自己从头实现,思路会相当的清晰。并且是通过软件模拟各个器件,因此只需要考虑各个芯片的外特性。这会相当的有趣,不过难度也很大啊。
以前就见过有人实现过8086的虚拟机,但是只做了CPU,没有再继续定义其他的IC。
WinCE 中也有 Emulator,并且 WinCE 6.0 中已经支持了 device emulator。
如果是自己搭建看来还是可行的。做软件如果能做到这种地步,已经算是非常彻底了。剩下的就可以转向硬件,去搞搞 IC 的设计了。
这个也算是自己大学时代的一个梦想吧。不过现在看来仍然是遥不可及,甚至感觉有点妄想。

[此贴子已经被作者于2007-6-8 17:25:03编辑过]

2007-06-08 17:02
jig
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
帖 子:530
专家分:242
注 册:2005-12-27
收藏
得分:0 

RockCarry 说的不错,你说的又何尝不是我大学时期的梦想呢.记得开始还想自己写个操作系内核,想了想去结果还只能试着写个DOS内核.在制作过程中想自己定义磁盘格式实现文件管理系统,结果由于多种原因最终搁置了......

这些日子很想写写文章,可TMD毕业在即,郁闷哦.

前段日子到武汉工作,把董凯也拉了过去.结果在那把数据恢复研究了个地朝天,终于自己结合FAT系列和NTFS自己定义了个破磁盘格式,我已经用文件虚拟了这个磁盘管理系统.然后还是因为自己的想法,我把那工作辞了,董兄还在哟,现在在新疆出差过的不亦乐乎啊,哈哈

想想以前的激情真是无法比拟啊,通宵几天那是不在话下的事, RockCarry 兄说的事我们又何尝没有梦想去实现呢.只是在中国这样个大环境下,太多的事干扰了我们.我想要是我们能真的静下拉弄这些,少一些现实的干扰,呵呵也许出<自己动手写操作系统>那本书有可能就是我们写了,

哈哈,这个也是我的妄想吧

这段时间,正在实现一个RAD可视化的编译器IDE,等有时间忙在继续忙自己的也许那东东就能出来了,RockCarry兄可以关注关注我和董凯的网站 www.ds0101.com 0101部落.我正在拿别人现成的模板在改呢,呵呵到时候还要哥哥们来捧个场.

[此贴子已经被作者于2007-6-10 14:59:03编辑过]


个人网站 -  http://.h001.
2007-06-10 14:52
RockCarry
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:13
帖 子:662
专家分:58
注 册:2005-8-5
收藏
得分:0 

我现在的工作也很烦啊,WinCE 驱动开发,成天就是跟硬件和协议打交道。不过也学了很多东西,都是被逼出来的,我真的没有想到一年时间自己能提高得这么快。一年内就能独立设计和开发 WinCE 的 BootLoader,独立开发 SD 卡驱动,摄像头驱动。
虽然在学校里面自我感觉还是很厉害的,但是工作时接到这些任务的时候,都是完全不懂,不知道如何下手,甚至我们的软件组老大也不懂,公司新招的研究生也不懂。最后公司人都走光了,DEC 散伙了。不过自己却抓紧时间,把这些问题都解决了。总之,都是被逼出来的。
总之,我觉得不管怎样,要抓紧时间多学东西,否则就荒废了。如果是打算搞技术,就要坚持下去,哪怕是只停下来一年,人就废了。

目前的梦想,是希望自己能够从头编写2440的BSP,三星提供的BSP虽然已经不错,但是感觉仍然不够完美。不过公司是绝对不会给我时间搞这个的,况且公司管理上还是比较混乱,只有在业余时间做。

另外就是做 DOS 的图形程序,JPEG,H.264 什么的,以前的一些想法也是不会放弃的。
不过工作太累了,下了班就什么都不想干,而且还要陪女朋友,和朋友一起打游戏,和朋友聚餐什么的。

目前我正在做一个 JPEG 的 Codec,也不知道何时能够完成。

2007-06-10 16:59
快速回复:[原创]内存管理 - 动态开辟内存
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019728 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved