<原创> 8051 内存动态分配源码 by David

david · 发表于 2008-10-13 17:37:01

使用过很多51的开发工具, 但在使用内存分配上，总是不尽人意，要么需要很多的XRAM，要么就是List结构占用太多的空间（至少4Bytes以上), 要么就是效率和速度让人受不了，有些还存在不可知的问题（Google一下就知道了)．
因此，不得不自己写一个，来满足目前针对比较少资源的单片机系统的要求，下面的动态内存分配代码, 使用了一个虚拟的List结构, 使得仅用一个Byte就可以维护一块内存, 大大少于商用软件使用的至少4字节以上来维护List.
正如其名SmallMemory, 是针对小内存块来操作的, 对于RAM比较少的8051系统, 非常合适, 至少目前来说，这是最简洁和最有效及利用率最高的算法了．现分与大家共享:

仅三个函数:

<<SmallMem.h>>

void small_init() ;  初始化, 在使用之前先执行的, 将会把SmallMemory[] 全部初始化为空闲的内存块.

void small_alloc(unsigned char size); 分配一个内存块, 注意, 只能取值为 1-127, 此函数会自动对相邻的空闲内存块合并来满足申请内存的要求.
                                                                  分配成功则返回地址，否则返回NULL.

void small_free(void*mem); 释放内存块.

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
<<SmallMmem.c >>

/***************************************************************************************************
   Small Memory Managment ....
Copyright 2008  by David Xie

Last Change: 2008-10-10

ListHead Byte: Bit7  = 1          Free Block
               Bit7 = 0          Used Block

               Bit[6..0] = 1 - 127    number of bytes of memory block
               Bit[6..0] = 0             end of memory block
******************************************************************************************************/

#define SMALL_MEM_SIZE 1024                   // 依你的系统来定.
#define SMALL_MEM __xdata                         // XRAM

//#define SMALL_MEM_SIZE 256
//#define SMALL_MEM __pdata                      // 也可以支持 pdata类型, 但最多256Byte可用.

SMALL_MEM unsigned char SmallMemory[SMALL_MEM_SIZE];

void small_init()
{
unsigned int i, n, len;
i = 0;
n = SMALL_MEM_SIZE;

if( &SmallMemory[0] == NULL ){       /* if SmallMemory at (0x00), need reserved 2 byte to used, becase 0 is NULL */
      SmallMemory[0] = 0x01;
      i += 2;
      n -= 2;
}

while(n>1){                      /* Init Empty Small List */
      len = (128 < n)? 127 : n-2;
      SmallMemory[ i ] = 0x80 | len;
      len++;
      i += len;
      n -= len;
}
SmallMemory[ i ] = 0x80;          /* End Of Small List */
}

void * small_alloc(unsigned char size)
{
register SMALL_MEM unsigned char *p1, *p2;
register unsigned char len;

if( size > 127 || size == 0) return NULL;

p1 = SmallMemory;
while( *p1 != 0x80 ){
         len = *p1 & 0x7f;
         if( *p1 & 0x80 ){       /* 找到空的内存块 */
         while( len < size ){       /* 如果空间不够, 则再找相邻的下一个空间来合并 */
            p2 = p1+len+1;
            if( *p2 > 0x80 ){       /* 只能合并空闲的内存块 */
                  len += (*p2 & 0x7f) + 1;
            }else{
                  break;
            }
         }
         if( len >= size ){          /* 找到一个足够的内存块 */
            if( len - size >= 2 ){ /* 多余超过2Bytes以上的，放回空闲内存块列表中 */
                  *p1 = size;
                  p2 = p1+size+1;
                  *p2 = (len-size-1) | 0x80;
                  return p1+1;
            }else{                      /* 多出的不超2Bytes的，则也分配使用了，无法再放回空闲表中了 */
                  *p1 = len;
                  return p1+1;
            }
         }
      }
      p1 += len+1;          /* 找下一内存块  */
}
return NULL;          /* 没有可用的, 返回 NULL */
}

void small_free(void *mem)
{
*((SMALL_MEM unsigned char* )mem - 1) |= 0x80;       /* 简单地设置为空块即可 */
}
" Y, ]- m( v8 L: m% y. c# p

xtdumpling · 发表于 2008-10-14 12:48:22

有个小建议,ListHead可以定义成下面这样定义吗?
typedef struct{
unsigned size:7; /* 0: indecate end of list; otherwise Size of this memory block*/
unsigned status:1; /* Memory Block status 0: used ; 1: free */
}ListHead;
我觉得比较好理解点

[ 本帖最后由 xtdumpling 于 2008-10-14 12:58 编辑 ]

david · 发表于 2008-10-14 14:56:30

原帖由 xtdumpling 于 2008-10-14 12:48 发表 6 @& u' S3 ?  o
有个小建议,ListHead可以定义成下面这样定义吗?
* i' u/ M( e: u( }& Ltypedef struct{
9 t# O6 X  f% l$ o3 x$ T unsigned size:7; /* 0: indecate end of list; otherwise Size of this memory block*/
( A2 f- v' f& B unsigned status:1;  /* Memory Block status 0: ...

这个当然可以,不过要写成
typedef struct{
unsigned char size:7; /* 0: indecate end of list; otherwise Size of this memory block*/
unsigned char status:1; /* Memory Block status 0: used ; 1: free */
}ListHead;

这样做可以大大增加程序可读性, 我有这样做过, 但发现生的代码优化方面差些

dinjee · 发表于 2008-10-20 18:41:26

这个动态内存分配很危险。因为8051没有MMU无法进行内存整理。

1.如果内存分配过多会造成浪费内存。如果要最差情况下也可以申请到，需要正常内存的N倍。

2.如果内存分配比较临界的时候会因为内存碎片造成碎片过多后面的程序无法申请内存。这样会造成程序在最差的情况下后续程序无法正常分配内存。一旦程序完全依赖这个内存分配程序来分配内存，就会造成程序无法得到内存。（如果再考虑无法申请内存的情况下程序的顺利运行，对于C51这种小程序来说复杂度变得很大，很大。）

xtdumpling · 发表于 2008-10-21 13:28:08

...
我觉得楼上的说得严重了!
8051没有MMU,不代表它就不能管理内存吧,难道是8051设计的失误!!!

这个small memory内存管理程序的应用情况应该是:
内存大小在几K到几十KByte,一般内存申请大小在几个到几十个Byte,(最大127个Byte)

这个程序的特点是在以字节为单位节省内存!!!
所以将内存管理节点做在一个字节内.
而且最小的空闲内存块是2个字节,合并相邻内存块来分配这些可以有效的防止内存浪费.
在内存申请在几个,几十个Byte时,是基本没有浪费!!

dinjee · 发表于 2008-10-22 12:04:06

主要问题是在反复申请释放内存的情况下。会产生碎片。
造成内存池碎片过多，后续的程序无法申请较大的内存。
并且你无法控制碎片的分布。它是和操作次序有密切相关的。

写程序不能仅仅考虑最好情况，必须考虑最坏情况。否则就会有很大的隐患。
特别是作为模块，必须考虑的慎之又慎。

如果是void * small_alloc(unsigned char size) size永远等于1的情况下我没有意见
但是size是变量那就很危险了。

不是说这个CPU的设计失误，而是它使用内存的方式不一样。

[ 本帖最后由 dinjee 于 2008-10-22 12:08 编辑 ]

david · 发表于 2008-10-22 13:18:50

大家都不要争了, 都是我没有说清楚, 事实上, 受限于51资源, 这个代码没有作任何的容错功能, 需要由调用者来小心地调用, 的确正如楼上说的, 频繁地随机申请/释放, 是有可能最后全是碎片, 而使整个系统崩溃!!
   我在使用过程中, 均是按照以下方式进行, 这样可以避免此问题, 付出的代价就是不能对随机空间随机申请/释放:
1.  多任务中, 每一个进程因未知要使用的空间需求(堆), 因此在第一次运行时请求空间,  之后不再释放.
2.  对于动态的申请/释放, 都是按照一个固定长度(一般是LIST结构)来进行申请/释放, 并且整个系统只有一种长度．
3.  可以申请临时的任意空间，但在要进入另一个进程或任务转换之前释放,

　我也一直在找新的算法，能在8051架构上, 较少的内存(通常不超过几K)环境，可以做到随机地申请任意空间和随机释放而不会引起碎片! 但还是没有找到

.
哪一位同学如果有很好的算法, 别望告诉我一声

．

		自动登录	找回密码
密码			加入计匠网

<原创> 8051 内存动态分配源码 by David

回复 4# 的帖子