內(nèi)存管理 - 動(dòng)態(tài)開(kāi)辟內(nèi)存
作者：孫靖(Jig)  時(shí)間：2006 - 12 - 26 
若要轉(zhuǎn)貼或使用本文章介紹的技術(shù)，請(qǐng)?jiān)谀惆l(fā)布的文章或作品中注明出處。

    關(guān)于內(nèi)存管理，以前我在PC機(jī)上研究系統(tǒng)內(nèi)核時(shí)接觸過(guò)。那要求在把CPU設(shè)置為32位后統(tǒng)一給內(nèi)存做影射，而我們今天要討論的內(nèi)存管理比那是要簡(jiǎn)單多了。
    前兩天拿朋友的51單片機(jī)開(kāi)發(fā)板玩（用的Keil），突然萌發(fā)做個(gè)貪食蛇的想法，經(jīng)過(guò)考慮我打算用鏈表來(lái)做（當(dāng)然，結(jié)果證明用鏈表做很不值得）可在快完工的時(shí)候我傻眼啦，蛇在吃了食物后整個(gè)屏幕都花啦（用的LCD12864的液晶屏）。本來(lái)蛇每吃一個(gè)食物其實(shí)就是動(dòng)態(tài)再開(kāi)辟一段蛇身。這樣看來(lái)顯然是動(dòng)態(tài)開(kāi)辟內(nèi)存失敗，導(dǎo)致繪制蛇身函數(shù)在逐個(gè)查找鏈表的每個(gè)節(jié)點(diǎn)的時(shí)候有一環(huán)被破壞沒(méi)有連接到下一環(huán)。
    再追查下去，應(yīng)該就是 malloc() 函數(shù)沒(méi)有發(fā)揮作用，可是很納悶 Keil 編譯器并沒(méi)有報(bào)告錯(cuò)誤。現(xiàn)在問(wèn)題找到了，可要解決這個(gè)問(wèn)題那就必須自己能構(gòu)造一個(gè) malloc() 函數(shù)。后來(lái)我查看了 malloc() 函數(shù)，具體實(shí)現(xiàn)如下：
   
    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 */
    }

在這我們可以看到其實(shí)他就是利用一個(gè)鏈表在內(nèi)存中去搜索一段連續(xù)的空閑內(nèi)存，并把首地址傳回。可為什么他在我使用的51單片機(jī)開(kāi)發(fā)板上沒(méi)有發(fā)揮作用呢？經(jīng)過(guò)分析，我恍然大悟。大家試想一下如果讓你去分配一段內(nèi)存，那么我們就必須有個(gè)紀(jì)錄哪些內(nèi)存在使用哪些內(nèi)存空閑的機(jī)制。拿TC或VC在PC機(jī)上實(shí)驗(yàn)一下使用 malloc() 函數(shù)看看？它作用發(fā)揮良好，看來(lái)這個(gè)機(jī)制是由OS來(lái)完成的，而在我們那51單片機(jī)的裸機(jī)上有個(gè)毛的OS啊，也難怪 malloc() 函數(shù)不能成功的分配內(nèi)存。現(xiàn)在找到問(wèn)題的本質(zhì)，那我們就來(lái)自己構(gòu)造 malloc() 函數(shù)。

    建立自己的數(shù)據(jù)類型：
    文件名：MY_Type.h
    內(nèi)容：
 /* 自定義類型，方便書(shū)寫(xiě)與在不同平臺(tái)進(jìn)行移植 */
 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;*/

    總體具體分析：
    為了能有效果的對(duì)內(nèi)存進(jìn)行管理，我們必須保證內(nèi)存時(shí)時(shí)刻刻都能被指定并被紀(jì)錄是否空閑，那么最好的做法就是先開(kāi)辟好一定空間再統(tǒng)一管理。當(dāng)然這段內(nèi)存空間也必須是全局的。然后我們必須建立一個(gè)紀(jì)錄列表，紀(jì)錄下內(nèi)存的使用狀態(tài)，以便管理。

    建立管理機(jī)制：
    我們可以構(gòu)造一個(gè)結(jié)構(gòu)，將紀(jì)錄列表和實(shí)際使用內(nèi)存綁定起來(lái)。具體代碼如下：

    #define MEM_COUNT 40   /* 實(shí)際使用內(nèi)存40個(gè)字節(jié)      */
    #define MEM_LIST MEM_COUNT >> 3  /* 管理列表 40/8 = 5個(gè)字節(jié)     */

    typedef struct
    {
     UINT8 list[MEM_LIST];    /* 管理列表共40位與實(shí)際使用內(nèi)存一一對(duì)應(yīng)，1表示使用中，0表示空閑 */
     INT8 mem[MEM_COUNT];    /* 實(shí)際使用內(nèi)存40個(gè)字節(jié)      */
    }MEM;      /* 管理機(jī)制結(jié)構(gòu)       */
    MEM Mem;      /* 管理機(jī)制數(shù)據(jù)       */

到此我們就把內(nèi)存管理機(jī)制的核心部分建立起來(lái)了，我們可以作這樣一個(gè)表來(lái)說(shuō)明他的工作方式：

            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個(gè)字節(jié)共40位，與 Mem.mem 的40個(gè)字節(jié)一一對(duì)應(yīng)，我們就是通過(guò)檢查 Mem.list 各位的狀態(tài)來(lái)確定哪些內(nèi)存在使用哪些內(nèi)存空閑。

    初始化管理系統(tǒng)：
    這個(gè)很簡(jiǎn)單，初始化即是內(nèi)存全部可用，Mem.list 全部置0，具體實(shí)現(xiàn)函數(shù)：

    void Init_mem(void);
    void Init_mem()
    {
     UINT8 i;
   
     for (i = 0; i < MEM_LIST; i++)
     {
     Mem.list[i] = 0;    /* 管理列表共40位全部置0，表示內(nèi)存可用    */
        }
    }
經(jīng)過(guò)此函數(shù)，Mem.mem 的40個(gè)字節(jié)內(nèi)存被標(biāo)記為可使用。

    動(dòng)態(tài)開(kāi)辟內(nèi)存：
    即像 malloc() 函數(shù)那樣，分配指定字節(jié)的內(nèi)存，具體實(shí)現(xiàn)函數(shù)：
   
    void Set_bit(UINT8 Bit, UINT8 mode);  /* 設(shè)置管理列表的第Bit位為mode     */
    void *Malloc(UINT8 Size);    /* 分配Size字節(jié)大小的內(nèi)存，返回首地址    */

    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;    /* 內(nèi)存開(kāi)辟失敗，返回空指針     */
     }
       /* i, j 兩層for循環(huán)用于查找管理列表目前的空閑內(nèi)存   */
     for (i = 0; i < MEM_LIST; i++)
     {
     Enter = 128;
     for (j = 0; j < 7; j++)
     {
      if ((Mem.list[i] & Enter) != Enter) /* 查找管理列表，直至查早到空閑內(nèi)存    */
      {
      for (k = (i<<3)+j; k < (i<<3)+j+Size; k++)
      {
       Set_bit(k, 1);   /* 從空閑內(nèi)存首地址開(kāi)始按Size大小設(shè)置被使用的內(nèi)存  */
      }
      return &Mem.mem[(i << 3) + j]; /* 內(nèi)存開(kāi)辟成功，返回首地址     */
         }  
      Enter >>= 1;
     }
        }

     return NULL;     /* 內(nèi)存開(kāi)辟失敗，返回空指針     */
    }

此函數(shù)通過(guò)檢查管理列表，找到空閑內(nèi)存的啟始地址，并把管理列表對(duì)應(yīng)的位置1，并返回空閑內(nèi)存啟始地址。

    釋放內(nèi)存：

    void Free(UINT8 *Mem1, UINT8 Size);   /* 釋放開(kāi)辟的內(nèi)存      */
    void Free(UINT8 *Mem1, UINT8 Size)
    {
     UINT8 i;
   
       /* Mem1 - &Mem.mem[0] 計(jì)算出Mem1指向的地址為Mem.mem的第幾元素 */
     for (i = (Mem1 - &Mem.mem[0]); i < (Mem1 - &Mem.mem[0] + Size); i++)
     {
     Set_bit(i, 0);    /* 從指定內(nèi)存首地址開(kāi)始按Size大小設(shè)置被內(nèi)存空閑   */
     }
    }

此函數(shù)可以“釋放”掉被開(kāi)辟的內(nèi)存空間。當(dāng)然，這個(gè)釋放不是真正意義上的釋放，只是把管理列表的相對(duì)應(yīng)位設(shè)置為0，表示內(nèi)存空閑。

   
    好了，到此這個(gè)內(nèi)存管理技術(shù)全部介紹完畢。他全部也就四個(gè)函數(shù)，我們可以做個(gè)小實(shí)驗(yàn)。

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

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

    Init_mem();      /* 初始化內(nèi)存管理機(jī)制       */
    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編譯的結(jié)果是：
30 1121
30 1121
6789324 1122
1122

用不同的編譯器結(jié)構(gòu)可能有點(diǎn)不同，但 j = &Mem.mem[0], i = &Mem.mem[1];卻是絕對(duì)成立的，這說(shuō)明我們的內(nèi)存管理機(jī)制起作用了，我們成功的實(shí)現(xiàn)內(nèi)存的統(tǒng)一管理，并實(shí)現(xiàn)了動(dòng)態(tài)開(kāi)辟內(nèi)存。

    總結(jié)：
    以上闡述的思路，其實(shí)很簡(jiǎn)單。也許大家在看到這時(shí)就覺(jué)得這個(gè)很小兒科了。我也承認(rèn)這的確很小兒科。說(shuō)到底，其實(shí)就是先開(kāi)辟好內(nèi)存然后再來(lái)使用，但作為一個(gè)思路我希望對(duì)您有一定啟發(fā)和幫助，同時(shí)也希望和大家共同交流和探討。當(dāng)然，任何事物和方法都有兩面性，這個(gè)內(nèi)存管理也不列外。
    缺點(diǎn)：由于要開(kāi)辟一個(gè)列表來(lái)紀(jì)錄內(nèi)存的使用狀態(tài)，所以增大了內(nèi)存的開(kāi)銷，如上所示，40個(gè)字節(jié)的內(nèi)存就需要5個(gè)字節(jié)的管理列表。
    優(yōu)點(diǎn)：這個(gè)方法簡(jiǎn)單方便，在單片機(jī)這樣的平臺(tái)上你想像在PC機(jī)上那樣花大力氣去做內(nèi)存的影射嗎？而且那樣做內(nèi)存的額外開(kāi)銷也不一定比此方法的少。并且是按字節(jié)大小以順序方式開(kāi)辟內(nèi)存，不存在什么所謂的內(nèi)存碎片。
    當(dāng)然，大家在使用著套方法的時(shí)候一定主要將Malloc()和Free()函數(shù)配套使用，并且要保證里面的Size參數(shù)一樣。當(dāng)然你也可以進(jìn)一步改進(jìn)此方法，讓他使用的更合理更安全。