动态内存分配的原理是什么?

Chenxg

rt

zcllom

我所理解的动态内存分配[转]

    本文的内容大部分来自《C++Primer第三版中文版》，是我学习C++的一个笔记，写出来主要是作为初学者的一个参考，希望对大家有所帮助。

    全局对象和局部对象的生命期是严格定义的，程序员不能够以任何方式改变它们的生命期。但是，有时候需要创建一些生命期能被程序员控制的对象，它们的分配和释放可以根据程序运行中的操作来决定。这种对象被称为动态分配的对象(dynamicaily allocated object)。动态分配的对象被分配在内存的堆中（有些资料称为自由空间(free store)，其实就是堆）。关于堆的具体含义大家可以参考《数据结构》教程和文章《明晰C++内存分配的五种方法的区别》。

    程序员用new表达式创建动态分配的对象，用delete表达式结束此类对象的生命期。动态分配的对象可以是单个对象，也可以是对象的数组，动态分配的数组的长度可以在运行时计算。

    在本文中，我将向大家介绍我所理解的两种形式的new的表达式：一种支持单个对象的动态分配，另一种支持数组的动态分配。并详细分析一种智能指针auto_ptr。

一　单个对象的动态分配与释放
    new表达式由关键字new及其后面的类型指示符构成。该类型指示符可以是内置类型或class类型。例如：new int ;　从堆中分配了一个int型的对象。
　　类似地　new Student ;　分配了一个Student类对象。
　　需要注意的是堆中分配的对象没有名字。new表达式没有返回实际分配的对象，而是返回了一个指向该对象的指针，对该对象的全部操作都要通过这个指针间接完成。例如：
　　int *pi = new int ;
　　该new表达式创建了一个int型的对象，由pi指向它。
　　堆的特点是分配的内存是未初始化的。堆的内存包含随机的位模式，它是程序运行前该内存上次被使用留下的结果。
　　测试if(*pi == 0) 总是会失败，因为由pi指向的对象含有随机的位。因此我们要对用new表达式创建的对象进行初始化。例如
　　int *pi = new int (0) ;
　　该语句表示pi指向一个int型的对象，该对象的初始值为0。括号中的表达式被称作初始化式(initializer)。初始化式的值不一定是常量，在该例中，任意的能够被转换成int型结果的表达式都是有效的初始化式。
　　类似地，如下语句：
　　Student *ps = new Student(“Tom”) ;
　　创建了一个Student类的对象。在类对象的情况下，括号中的值被传递给该类相关的构造函数，它在该对象被成功分配之后才被调用。

　　new表达式的操作顺序如下：从堆中分配对象，然后用括号内的值初始化该对象，并返回一个指向该对象的指针。如果分配内存失败（通常是因为没有足够的内存），通常会抛出一个bad_alloc异常。

　　动态分配内存的对象与静态分配内存的对象不同，编译器不会自动释放它们所占的内存-----除非整个程序结束。所以当动态分配内存的对象完成它的使命，需要被销毁的时候不能依赖编译器，而要靠程序员自己亲自来操刀。

　　当指针pi所指对象的内存被释放时，它的生命期也随之结束。例如：delete  pi;
　　释放了pi指向的内存，结束了int型对象的生命期。通过delete表达式，我们可以在任何时候结束对象的生命期（当然是在new表达式之后），把内存还给堆。因为堆是有限的资源，所以我们不再需要已分配的内存时，就应该马上将其返还给堆，否则将造成内存泄漏。
　　看过前面的delete表达式，你可能会问，如果pi因为某种原因被设置为NULL，又会怎样呢？是不是应该写成
　　if (pi != NULL)  //这样做有必要吗?
　　delete pi;
　　答案是不。如果指针操作数被设置为NULL，则C++会保证delete表达式不会调用操作符delete；没有必要测试其是否为NULL。实际上在多数实现下，如果增加了指针的显式测试，那么该测试实际上会被执行两次。
　　在这里，搞清楚pi的生命期和pi指向的对象的生命期之间的区别是很重要的。指针pi本身是个在全局域中声明的全局对象，它的生命期由编译器控制。结果pi的存储区在程序开始之前就被分配，一直保持到程序结束。而pi指向的对象的生命期是由程序员控制的，它是在程序执行过程中遇到new表达式时才被创建，遇到delete表达式时被销毁并收回存储区。因此，当程序执行delete pi;语句时，pi指向对象的内存被释放，但指针pi本身的内存并没有受到delete表达式的影响。在delete pi;之后，pi被称作空悬指针（俗称野指针），即指向无效内存的指针。空悬指针是错误的根源，它很难被检测到，如果对它进行操作将会产生无法预测的结果。一个比较好的办法是在指针所指的对象被释放后，马上将该指针设置为NULL，这样可以清楚地表明该指针不再指向任何对象。

　　此外，需要注意的是，delete表达式只能应用在指向内存是用new表达式动态分配的指针上，将delete表达式应用在指向堆以外内存的指针上，会使程序运行期间出现未定义的行为。唯一的例外是，当指针指向NULL时，不管指针指向的对象是如何分配内存的，使用delete都不会引发麻烦。下面的例子给出了安全的和不安全的delete表达式：
　　
void f()
{
　　int i;
　　char *str = "asdd";
　　int *pi = &i;
　　short *ps = NULL;
　　double *pd = new double(123.3);
　　delete str;       //危险！str指向的不是动态对象
　　delete pi;  //危险！pi指向的对象i是一个局部对象
　　delete ps; //安全！ps指向NULL
　　delete pd; //安全！pd指向一个动态分配的对象
}

注意：下面三个常见的程序错误都与动态内存分配有关：

1．应用delete表达式失败，使内存无法返回堆，这被称做内存泄漏(memory leak)。

2．对同一内存区应用了多次delete表达式。这通常发生在多个指针指向同一个动态分配对象的时候。若多个指针指向同一对象，当通过某一个指针释放该对象时就会发生这种情况。

3．在对象被释放后读写该对象。这常常会发生，原因是没有及时把该指针设置为NULL

　　这些操纵动态内存分配的错误比较容易出现，而且难于跟踪和修正。为了帮助程序员更好地管理动态分配的内存，C++库提供了auto_ptr类类型的支持。关于这个话题我将在后面做详细地介绍。

二　数组的动态分配与释放

　　new表达式也可以在堆中分配数组。在这种情况下，new表达式中的类型指示符后面必须有一对方括号，里面的数值代表数组的长度，而且该数值可以是一个复杂的表达式。New表达式返回指向数组第一个元素的指针。例如：

//分配单个int型的对象，用1024初始化
int *pi = new int (1024) ;

//分配一个含有1024个元素的int型数组，未被初始化
int *pia = new int [1024] ;

//分配一个含有4 * 1024个元素的int型二维数组，未被初始化
int (*pia2)[1024] = new int [4][1024] ;

　　pi指向一个int型的单个对象，初始值为1024。pia指向数组的第一个元素，该数组有1024个元素。pia2是一个数组指针，它指向一个由具有1024个元素的数组构成的二维数组的第一个元素，即pia2指向一个二维数组，该数组的每个元素都是一个数组-----有1024个元素的数组。

　　一般地，在堆上分配的数组不能给出初始化值集。我们不可能在前面的new表达式中通过指定初始值来初始化数组的元素。在堆中创建的数组必须在for循环中被初始化，即数组的元素一个接一个地初始化。例如：
　　for (int i=0; i<1024; ++i)
　　　　pia = 0;
　　动态分配数组的主要好处是，它的第一维不必是常量值。我们可以在程序执行期间根据需要给数组分配合适的空间，以避免不必要的浪费。例如：
　　char *str = new char[strlen(errorTxt) + 1];
　　注意此处对strlen(errorTxt)返回的值加1是必需的，这样才能容纳C风格字符串的结尾空字符。避免此类错误的一个较好选择是使用C++标准库string代替C风格字符串。

　　注意，对于用new表达式分配的数组，只有第一维可以用运行时计算的表达式来指定，其他维必须是在编译时刻已知的常量值。例如：
　　int GetDim();   //返回一个长度

　　//分配一个二维数组
　　int (*pia3)[1024] = new int [GetDim()][1024] ;   //OK

　　//错误：数组的第二维不是常量
　　int **pia4 = new int [4][GetDim()] ;   //WRONG

　　用来释放数组的delete表达式形式如下：
　　delete[] pia;
　　空的方括号是必需的，它表明指针指向堆中的数组而非单个对象。因为pia是int型的指针，所以如果编译器没有看到空方括号对，它就无法判断需要被删除的存储区是否为数组。
　　如果不小心忘了该空括号对，会怎么样呢？编译器不会捕捉到这样的错误，并且不保证程序会正确执行。


=================================
小可再附加一个“动态分配并销毁、回收二维数组”的例子

分配一个m个长度为n的字符串二维数组   
  char   **ch;   
  ch   =   new   char*[m];   
  for   (int   i   =   0;   i   <   m;   i++)   
  {   
        ch   =   new   char[n];   
  }   

  程序结束时进行逐个销毁：   
  for   (i   =   0;   i   <   m;   i++)   
  {   
        delete[]   char;   
  }   
  delete[]   char;

zcllom

今天又想做终结者了，终结“动态内存分配”

两种动态内存分配的方式的异同malloc and new：

函数声明(函数原型)：  

void *malloc(int size);  

说明：malloc 向系统申请分配指定size个字节的内存空间。返回类型是 void* 类型。void* 表示未确定类型的指针。C,C++规定，void* 类型可以强制转换为任何其它类型的指针。  
从函数声明上可以看出。malloc 和 new 至少有两个不同：
new 返回指定类型的指针，并且可以自动计算所需要大小。比如：  

int *p;  
p = new int; //返回类型为int* 类型(整数型指针)，分配大小为 sizeof(int);  
或：  
int* parr;  
parr = new int [100]; //返回类型为 int* 类型(整数型指针)，分配大小为 sizeof(int) * 100;  

而 malloc 则必须由我们计算要字节数，并且在返回后强行转换为实际类型的指针。  
int* p;  
p = (int *) malloc (sizeof(int));  

第一、malloc 函数返回的是 void * 类型，如果你写成：p = malloc (sizeof(int)); 则程序无法通过编译，报错：“不能将 void* 赋值给 int * 类型变量”。所以必须通过 (int *) 来将强制转换。  

第二、函数的实参为 sizeof(int) ，用于指明一个整型数据需要的大小。如果你写成：int* p = (int *) malloc (1); 代码也能通过编译，但事实上只分配了1个字节大小的内存空间，当你往里头存入一个整数，就会有3个字节无家可归，而直接“住进邻居家”！造成的结果是后面的内存中原有数据内容全部被清空。  

malloc 也可以达到 new [] 的效果，申请出一段连续的内存，方法无非是指定你所需要内存大小。  

比如想分配100个int类型的空间：  
int* p = (int *) malloc ( sizeof(int) * 100 ); //分配可以放得下100个整数的内存空间。  

    另外有一点不能直接看出的区别是：malloc 只管分配内存，并不能对所得的内存进行初始化，所以得到的一片新内存中，其值将是随机的。
    除了分配及最后释放的方法不一样以外，通过malloc或new得到指针，在其它操作上保持一致。

Chenxg

我想知道底层是怎么实现的?比如malloc函数,翻译成汇编的原理是什么样子?


这个问题老是想不通,觉得动态内存分配很神奇.......

zcllom

我是就着你的问题，贴给自己作备忘录的，先彻底搞清楚用法，然后，我看下我收集的资料里有没有讲到原理的部分。我的资料虽然汗牛充栋，但我本人却不是学富五车、才高八斗类型。

yin66

MARK
下次来看看

eduhf_123

帖上Keil C51自带的动态内存分配库，供楼主参考。
.\Keil\C51\lib\INIT_MEN.C

---

/*-----------------------------------------------------------------------------
INIT_MEM.C is part of the C51 Compiler package from Keil Software.
Copyright (c) 1995-2002 Keil Software.  All rights reserved.
-----------------------------------------------------------------------------*/
#include <stdlib.h>

/*-----------------------------------------------
Memory pool block structure and typedefs.
Memory is laid out as follows:

{[NXT|LEN][BLK (LEN bytes)]}{[NXT|LEN][BLK]}...

Note that the size of a node is:
          __mem__.len + sizeof (__mem__)
-----------------------------------------------*/
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__))

/*-----------------------------------------------
Memory pool headers.  AVAIL points to the first
available block or is NULL if there are no free
blocks.  ROVER is a roving header that points to
a block somewhere in the list.

Note that the list is maintained in address
order.  AVAIL points to the block with the
lowest address.  That block points to the block
with the next higher address and so on.
-----------------------------------------------*/
__memt__ _MALLOC_MEM_ __mem_avail__[2] =
{
        {NULL, 0},        /* HEAD for the available block list */
        {NULL, 0},        /* UNUSED but necessary so free doesn't join HEAD or ROVER with the pool */
};

#define        AVAIL                (__mem_avail__[0])

#define        MIN_POOL_SIZE        (HLEN * 10)

/*-----------------------------------------------------------------------------
int init_mempool (
  void _MALLOC_MEM_ *pool,        address of the memory pool
  unsigned int size);           size of the pool in bytes

Return Value
------------
     0                FAILURE:  Memory pool is not large enough
     NZ                SUCCESS:  Memory pool management initialized.
-----------------------------------------------------------------------------*/
int init_mempool(
                void        _MALLOC_MEM_        *pool,
                unsigned        int        size)
{
/*-----------------------------------------------
Verify that the pool is large enough to actually
do something.  If it is too small, exit with 0.
-----------------------------------------------*/
        if(size < MIN_POOL_SIZE)
        {
                return (0);                                         /* FAILURE */
        }

/*-----------------------------------------------
If the pool points to the beginning of a memory
area (NULL), change it to point to 1 and decrease
the pool size by 1 byte.
-----------------------------------------------*/
        if(pool == NULL)
        {
                pool = 1;
                size--;
        }

/*-----------------------------------------------
Set the AVAIL header to point to the beginning
of the pool and set the pool size.
-----------------------------------------------*/
        AVAIL.next        = pool;
        AVAIL.len        = size;

/*-----------------------------------------------
Set the link of the block in the pool to NULL
(since it's the only block) and initialize the
size of its data area.
-----------------------------------------------*/
        (AVAIL.next)->next        = NULL;
        (AVAIL.next)->len        = size - HLEN;

        return (-1);                                           /* SUCCESS */
}

eduhf_123

.\Keil\C51\lib\MALLOC.C

---

/*-----------------------------------------------------------------------------
MALLOC.C is part of the C51 Compiler package from Keil Software.
Copyright (c) 1995-2002 Keil Software.  All rights reserved.
-----------------------------------------------------------------------------*/
#include <stdlib.h>

/*-----------------------------------------------
Memory pool block structure and typedefs.
Memory is laid out as follows:

{[NXT|LEN][BLK (LEN bytes)]}{[NXT|LEN][BLK]}...

Note that the size of a node is:
          __mem__.len + sizeof (__mem__)
-----------------------------------------------*/
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__))

/*-----------------------------------------------
Memory pool headers.  AVAIL points to the first
available block or is NULL if there are no free
blocks.

Note that the list is maintained in address
order.  AVAIL points to the block with the
lowest address.  That block points to the block
with the next higher address and so on.
-----------------------------------------------*/
extern        __memt__        _MALLOC_MEM_        __mem_avail__[];

#define        AVAIL        (__mem_avail__[0])

#define        MIN_BLOCK        (HLEN * 4)

/*-----------------------------------------------------------------------------
void _MALLOC_MEM_ *malloc (
  unsigned int size);                        number of bytes to allocate

Return Value
------------
    NULL        FAILURE:  No free blocks of size are available
  NON-NULL        SUCCESS:  Address of block returned
-----------------------------------------------------------------------------*/
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 */

/*-----------------------------------------------
Initialization:  Q is the pointer to the next
available block.
-----------------------------------------------*/
        q = &AVAIL;

/*-----------------------------------------------
End-Of-List:  P points to the next block.  If
that block DNE (P==NULL), we are at the end of
the list.
-----------------------------------------------*/
        while (1)
        {
                if((p = q->next) == NULL)
                {
                        return (NULL);                /* FAILURE */
                }

/*-----------------------------------------------
Found Space:  If block is large enough, reserve
if.  Otherwise, copy P to Q and try the next
free block.
-----------------------------------------------*/
                if(p->len >= size)
                {
                        break;
                }
               
                q = p;
        }

/*-----------------------------------------------
Reserve P:  Use at least part of the P block to
satisfy the allocation request.  At this time,
the following pointers are setup:

P points to the block from which we allocate
Q->next points to 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 */
        }

/*-----------------------------------------------
Split P Block:  If P is larger than we need, we
split P into two blocks:  the leftover space and
the allocated space.  That means, we need to
create a header in the allocated space.
-----------------------------------------------*/
        k -= HLEN;
        p->len = k;
       
        q = (__memp__ ) (((char _MALLOC_MEM_ *) (&p[1])) + k);
        q->len = size;
       
        return (&q[1]);                                /* SUCCESS */
}

zcllom

楼上的帖子有诸多参考价值，大家继续来终结。。

ifree64

在《C程序设计语言》一书中有较详细的讲解，可参考。
http://www.china-pub.com/14975&ref=ps
这种原理性的知识只有仔细读书并认真思考才能理解。

n104391455

mark

cxbing001

mark，留着慢慢消化

catx

简单的说，动态内存是分配在堆空间的，
静态内存分配在栈空间上，
一个程序有多少堆空间和栈空间可用是操作系统给的，
编译器有相应的库封装了对这部分内存管理的功能

XL_J

一会来看

Achin

标记一下，拷贝备份

lovelywwei

MARK

Pony279

Keil51上的动态内存分配就是,
在编译前拿出一个大的数组(空间)
在运行的时候, 谁需要空间, 就分配一部分给他, 不用了就把空间还给系统
在分配空间出去的时候会利用一些方法给分配出去的空间做个标记, 比如标记分配出去的空间的大小, 通常如果malloc(xxx)返回个指针*p, 那么标记就在这个指针指向的地址之前(具体位置看实现而定), 所以如果你要把那部分内存还给系统, 你直接给个指针他就知道是哪部分空间了
动态内存分配用的比较多的链表的数据结构, 这个你可以去参考数据结构的书籍

打个比方:
你跟地主租一块地, 告诉他你要多大的地, 地主就会从他空出来的地中划出一块给你, 这块地在你心里有数, 在地主心里当然也有数, 地主可能是给你租的地划了个界, 给你租的那块地分配一个号(地址), 也可能在他还在手上的地图上做了标记(映射到你那块地, 也记录了大小), 还是会给你个地址
你要还的时候, 直接给个地址给他, 他就知道你租的是哪一片地, 然后地主就可以取消块地的边界, 和周围空闲的地合并起来, 以后有人要租的时候, 他又可以重新划分了

Pony279

还有一种更高级的动态内存分配就是, 你不需要自己去归还你申请的内存, 在你不需要使用的时候, 系统就会自动处理,
就好像你有个助理一样, 你要管的只是申请空间, 你不需要那部分空间的时候你的助理会帮你归还那部分

这种方式对指针做了进一步的封装(好像是叫句柄吧...handle?), 可以大大的减少程序员的错误和负担, 不过代价就是牺牲了代码的效率, 不过总体上来讲, 性能会有所提高
这种方式的好处不仅仅再于减少出错,
比如说, 系统现在有6块空闲的空间
||||||||||||||||||||||||||||||||
||   ||   ||   ||   ||   ||   ||
|| 1 || 2 || 3 || 4 || 5 || 6 ||
||   ||   ||   ||   ||   ||   ||
||||||||||||||||||||||||||||||||
可能会在某个时刻 第1 , 第3 , 第5块已经分别被借给3个人了
如果这个时候又有一个人要申请一个大小为2块连续的空间, 这个时候就需要系统对这些分配的空间重新整理(似乎是叫垃圾收集)
腾出一个大小为2块的连续空间给那个人
如果每个人手上拿到的是被分配的空间的绝对地址(指针), 那个系统是没办法重新整理的
但是, 如果如果每个人手上拿的只是一个系统给的标识(句柄), 你要访问那部分空间的时候, 要先用这个标识(通过某种方法, 实现方式被封装起来了, 用户是不需要知道的) 找到地址, 再进行访问. 如果是这种方式, 系统可以在整理空间的时候, 重新把你手上的标识映射到一个新的空间.
有些编程语言是没有指针的, 差不多就是这个道理

我的理解就是这样, 建议去看算法和数据结构的书籍, C/C++只不过是编程语言, 工具而已, 核心还是在算法和数据结构上

techbaby

标记一下，不错的帖子！

catch2000

关于动态内存分配，
在系统上比较清楚，
调用后由libc来处理，系统这里已经做了处理，有内存管理的算法，
这些操作系统都会来处理，

但是在单片机上的裸机编程，
是由谁来处理的呢？
这里没有系统来管理这些，
但是我们也没有自己写过内存管理的code，
那么是谁在这个时候，为我们做了内存管理呢？