记笔记的过程,写出自己的问题,感想,边看边总结.
 
    
在看视频时,或者书籍学习时,有什么感想,疑问,可以停下来,记录好,或者有什么理解,什么启示,收获都可以记下来,笔记看不看不重要,重要的是记笔记的过程,眼过千遍不如手过一遍.
 
    
让学习以理解为主,而不是以记忆为主!
 
    
 
 
    
 
 
    
 程序为什么需要内存 
 
    
程序运行的目的是
 
    
的到一定结果,这个结果可以解决实际需求问题,新问题不断产生,程序也需要不断重新编写.得到不同结果.
 
    
 
 
    
计算机就是在计算数据,  那么 数据 的重要性不言而喻.
 
    
 
 
    
 
 
    
计算机程序 = 代码 + 数据
 
    
 
 
    
代码用来加工数据,改变数据得到我们想要的结果.
 
    
 
 
    
 
 
    
 
 
    
程序 运行的目的：    结果        过程（不在乎结果，主要是过程是否运行，凡是C语言函数返回值是Void的都不在乎结果）
 
    
 
 
    
函数：
 
    
int  add( int a, int b)
 
    
{
 
    
 return  a + b;
 
    
 
 
    
}
 
    
 
 
    
void add(int a, int b)
 
    
{
 
    
 int c;
 
    
 c = a + b;
 
    
 printf("c = %d.\n", c);
 
    
}//这个函数的执行重在过程（printf），返回值不重要。
 
    
 
 
    
  函数的返回问题
 
    
 
 
    
计算机程序运行其实就是很多函数的运行，程序的本质就是函数，函数的本质就是加工数据的动作。
 
    
 
 
    
 
 
    
 
 
    
冯诺依曼机构是数据和代码放在一起、
 
    
哈佛结构是数据和代码分开存放
 
    
 
 
    
什么是代码：  函数
 
    
什么是数据： 全局变量、局部变量。
 
    
 
 
    
在S5PV210中运行的linux系统上，运行程序时，应用程序的代码和数据都在DRAM，所以这种机构就是冯诺依曼机构；在单片机中，程序代码放在Flsah（Norflash）中，然后程序在Flash原地运行，程序中的数据（全局变量、局部变量）不能放在RAM，这种就叫哈佛结构
 
    
 
 
    
 
 
    
  DRAM 动态内存  ||  SRAM是静态内存
 
    
 
 
    
 
 
    
 
 
    
为什么需要内存？
 
    
内存用来存储可变数据，数据在程序中表现为全局变量、局部变量等（特殊的：gcc中，其实常量也是存储在内存中的）（大部分单片机中，常量是存储在flash中的，也就是代码段），   
 
    
 
 
    
  GCC编译
 
    
编程的关键几乎在于 内存管理   。  譬如  数据结构，数据如何组织、算法，为了更优秀的方法来加工数据，既然与数据有关就里离不开内存
 
    
 
 
    
那么如何管理内存？
 
    
 
 
    
问题在于 写程序时，如何对内存进行管理，尤其是在程序运行时，内存的消耗量，内存对程序来说是一种的资源，
 
    
 
 
    
操作系统掌握多有的硬件系统，因为内存很大，所以操作系统把内存分成一个个的页面（一块，4KB），然后以页面为单位管理。再细分到页里里面 以字节为单位管理。
 
    
操作系统管理内存的原理分厂复杂，但是我们不需要了解这些细节。操作系统给我们提供了内存管理的一些接口，我们只需要用API即可管理内存。
 
    
譬如C语言中使用 malloc free 这些接口 管理内存
 
    
 
 
    
 
 
    
没有操作系统时，其实就是裸机程序，程序需要操作内存，编程者需要自己计算内存使用和安排
 
    
 
 
    
从语言角度： 不同语言提供了不同的操作内存的接口。
 
    
譬如汇编 ： 根本没有任何内存管理，内存管理全靠自己，汇编中操作内存时直接使用内存地址譬如0xd0020010），很麻烦；
 
    
譬如C语言中，通过API（malloc free）来访问系统内存
 
    
譬如C++，用new来创建对象（其实就是为对象分配内存），如果此对象用完后忘记Delete，就会造成这个对象的内存不能释放，这就是内存泄露。
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 位、字节、半字、字的概念和内存位宽 
 
    
 
 
    
什么是内存？
 
    
从逻辑角度：内存可以随机访问（给一个地址，就可以访问这个内存地址）、并且可以读写（在裸机上可限制读写，但是一般都是可读写的）；内存在编程中天然用来存放变量的。一个变量对应内存中的一个单元。
 
    
 
 
    
内存位宽
 
    
从硬件角度讲：硬件内存实现本身是有宽度（内存芯片的实际数据总线数）的，也就是说有些内存条是8位的，而有些就是16位的，那么需要强调的是内存芯片之间是可以并联的。
 
    
 
 
    
位和字节
 
    
 
 
    
内存单元的大小：
 
    
位（1bit）
 
    
字节（8bit）
 
    
半字（一般是16bit）
 
    
字（一般是32bit）
 
    
 
 
    
bit就是计算机中信息的最基础单元，
 
    
 
 
    
字和半字
 
    
 
 
    
历史上曾经出现过16位、32位、64位系统三种，
 
    
平台不一样，子和半字的bit定义不一样，这些单位就提有多少bit 是依赖平台的
 
    
 
 
    
 
 
    
 
 
    
 
 
    
  有没有8位系统
 
    
 
 
    
 
 
    
 内存编址和寻址、内存对齐 
 
    
内存编址方法：
 
    
 
 
    
内存地址（一个数字）指向一个空间，一对一且永久不变
 
    
 
 
    
在程序运行时，计算机中CPU实际只通过内存地址，不需要找到这个空间在哪里？   
 
    
这个设定由硬件设计保证。
 
    
 
 
    
 关键：内存编址是以字节为单位的
 
    
 
 
    
随便给个内存地址，这个内存地址对应的空间的大小是固定的，就是一个字节（8bit）
 
    
如果把内存比为一栋大楼，楼里的一个个房间就是一个个内存空间，这个空间是固定大小 8bit ！
 
    
 
 
    
内存和数据类型的关系：
 
    
 
 
    
C语言中基本数据类型：  char short int long float double   
 
    
  
 
    
int 整形   （整数类型，整个整体现在它和CPU本身的数据位宽是一样的）譬如32位的CPU，整形就是32位，int就是32位（4个字节）的
 
    
数据类型和内存的关系：
 
    
数据类型是用来定义变量的，而这些变量需要存储、运算在内存中。所以数据类型必须和内存相匹配才能获得做好的性能，否则可能不工作或者效率低下。
 
    
 
 
    
在32位系统中定义变量做好用int，因为这样效率高。原因在于32位的系统本身配合内存等也是32位，这样的硬件配置天生适合定义32位的int类型变量，效率最高。也能定义8位的char类型变量或者16位的short类型变量，但是实际上访问效率不高。
 
    
 
 
    
在很多32位环境下，我们实际定义bool类型变量（实际只需要一个bit就够了）都是用int来实现bool的。
 
    
 
 
    
譬如   定义  bool b1;时，编译器实际帮我们32的内存来存储这个bool变量b1，编译器这个做实际浪费了31位的内存，但是好处是效率高。
 
    
 
 
    
问题：省内存和运行效率,二者需具体情况解决。
 
    
 
 
    
 
 
    
内存对齐
 
    
 
 
    
在C中 int a;   定义哟个int 类型变量，在内存中必须分配4个字节来存储这个a。  两种方式：
 
    
 
     
 
第一种：0 1 2 3        
 
 
对齐访问
 
 
第二种 1 2 3 4     或者 2 3 4 5 或者 3 4 5 6
 
 
非对齐访问
 
 
    
 
    
  
 
    
 
 
    
内存的对齐方式不是逻辑的问题，是硬件的问题。 从硬件角度，32位的内存它 0 1 2 3 四个单元本身裸机就有相关性，这四个字节组合起来当做一个int 硬件上就是合适的，效率就高。
 
    
 
 
    
对齐访问很配合硬件，所以效率很高；非对齐访问因为硬件本身不搭配，所以效率不高。
 
    
 
 
    
 
 
    
 
 
    
从内存编址看数组的意义
 
    
 
 
    
 C语言如何操作内存 
 
    
 
 
    
 
 
    
C语言对内存地址的封装
 
    
譬如C语言中   int a;   a = 5;  a += 4;       //  a == 9;
 
    
  
 
    
  
 
    
结合内存来解析C语言语句的本质：
 
    
int a;     // 编译器帮我们申请了 1 个int 类型 的内存格子（长度是4 字节。地址只有编译器知道。我们是不知道的，也不需要知道。）并且把符号 a 和这个格子绑定。
 
    
 
 
    
a = 5; // 编译器会把 5 放到 a 这个格子
 
    
 
 
    
C语言中数据类型的本质含义是： 表示一个内存格子的长度和解析方法。
 
    
数据类型决定长度的含义：以一个内存地址（一个字节的长度单位（固定的））开始，长度是多少，一次往后面延生多少连续长度
 
    
数据类型决定解析方法： 通过内存地址不同的类型指定这个内存地址（包括整个长度）指向的内存单元格子中二进制数的解析方法。
 
    
  强制类型转换
 
    
 
 
    
 
 
    
（int   *）0;
 
    
  
 
    
C语言中，函数就是一段代码的封装。函数名的实质就是这一段代码的首地址。所以说函数名的本质也是一个内存地址。
 
    
 
 
    
用指针来间接访问内存
 
    
 
 
    
关于类型（不管是普通变量类型int float 等，还是 指针类型int * float * 等），只要记住：
 
    
类型只是对后面数字或者符号（代表的是内存地址）  所表征的内存的一种长度规定和解析方法而已。
 
    
 
 
    
C语言中的指针，全名叫指针变量，指针变量其实很普通没有任何区别。譬如 int a 和int *p 其实没有任何区别，a 和p 都代表一个内存地址 （譬如是0x20000000）,但是这个内存地址（0x20000000）的长度和解析方法不同。a 是 int 型所以a 的长度是4字节，解析方法是按照int 的规定的；p是int * 规定的（0x2000000开头的连续4字节中存储了1个地址，这个地址所代表的内存单元中存放的是一个int类型的数）
 
    
 
 
    
 
 
    
用数组来管理内存
 
    
数组管理内存和变量其实没有本质区别，只是符号的解析方法不同。 （普通变量、数组、指针变量其实都没有本质差别，都是对内存地址的解析，只是解析方法不一样）
 
    
int a;        //编译器分配4字节长度，并且把首地址和符号a绑定起来
 
    
int b[10];  //编译器分配40字节长度，并且把首元素首地址和符号b 绑定起来
 
    
int *c;       //编译器分配4字节长度，并且把首地址和符号c绑定起来，而与c地址绑定的首地址开始，存放了一个地址，地址的内存单元存放的是一个int 类型的数
 
    
 
 
    
数组中第一个元素（a[0]）就称为首元素；每一个元素类型都是int，所以长度都是4，其中第一个字节的地址
 
    
就称为首地址；首元素a[0]的首地址就称为首元素首地址。
 
    
 
 
    
 
 
    
 
 
    
 内存管理之结构体 
      
 数据结构这门学问的意义 
        
数据结构就是研究数据如何组织(在内存中排布),如何加工的学问 
 
最简单的数据结构:数组 
        
为什么要有数组？ 
          
因为程序中有好多个类型相同、意义相关的变量需要管理，这时候需要管理，这时候如果用单独的变量来做程序看起来比较乱，用数组来管理会更好管理。 
 
 
 
 
    
譬如： int ages[20];
 
    
 数组的优势和缺陷 
      
优势：数组比较简单，访问用下标，可以随机访问。 
缺陷： 
        
数组所有元素类型必须相同 
数组的大小必须在定义时给出，而且一旦确定不能再改 
 
 
结构体隆重登场 
      
结构体发明出来就是为了解决数组的第一个缺陷：数组中多有元素类型必须相同 
 
 
    
譬如：我们要管理三个学生的年龄（int 类型），怎么办？
 
    
第一种解法：用数组   int age[3];
 
    
第二种解法：用结构体   
 
    
struct ages
 
    
 {
 
    
 int age1;
 
    
 int age2;
 
    
 int gae3;
 
    
 };
 
    
 struct ages age;
 
    
分析总结:在这个示例中，数组要比结构体好。但是不能得出结论说数组就比结构体好，在包中元素类型不同时就只能用结构体而不能用数组了；
 
    
 struct people
 
    
 {
 
    
 int age;
 
    
 char name[20];
 
    
 int height;
 
    
 };
 
    
 struct people people;
 
    
 题外话：结构体内嵌指针实现面向对象 
      
总的来说：C语言是面向过程的，但是C语言写出的linux系统是面向对象的。 
 
      
非面向对象的语言，不一定不能实现面向对象的代码。只是说用面向对象的语言来实现面向对象要更加简单一些、直观一些、无脑一些。 
用C++、java等面向对象的语言来实现面向对象简单一些，因为语言本身帮我们做了很多事情；但是用C来实现面向对象很麻烦，看起来也不容易理解，这就是为什么大多数人学过C语言却看不懂linux代码的原因。 
 
 
    
 struct s
 
    
 {
 
    
int age;                                 //普通变量
 
    
void (*pFunc)(void);          //函数指针，指向void func(void)这类的函数
 
    
}；
 
    
这样包含了函数指针的结构体就类似于面向对象的class，结构体中变量类似与class中的成员变量，结构体中的函数指针类似与class中的成员方法
 
    
 内存管理之栈 
      
 什么是栈 
        
栈是一种数据结构，C语言中使用栈来保存局部变量。 
栈是被发明出来管理内存的 
 
栈管理内存的特点 
        
先进后出   FILO    first in last out    栈 
先进先出   FIFO    first in first put    队列 
栈的特点是入口即出口，只有一个口，另一个是堵死的，所以先进去的必须后出来。 
 
栈的应用举例：局部变量 
        
我们在C中定义一个局部变量时（int a）,编译器会在栈中分配一段空间（4字节）给这个局部变量用（分配时栈顶指针会移动给出空间，给局部变量a用的意思就是，将这4字节的占的内存地址和我们定义的局部变量名a给关联起来 ），对应栈的操作是入栈。 
 
        
注意这里栈指针的移动和内存分配是自动（栈自己完成，不用我们写代码去操作）。 
然后等我们函数退出的时候，局部变量要灭亡。对应栈的操作时弹栈（出栈）。出栈时也是栈顶指针移动将栈空间中与a关联的那4个字节空间释放。这个动作也是自动的，也不用人写代码。 
 
 
 
    
栈的优点：栈管理内存，好处是方便，分配和最后回收都不用程序员操心，C语言自动完成。
 
    
定义局部变量，其实就是在栈中通过移动栈指针来给程序提供一个内存空间和这个局部变量名绑定。因为这段内存空间在栈上，而栈内存是反复使用的（脏的，上次用完没清零的），所以说使用栈来实现的局部变量定义时如果不显示初始化，值就是脏的。如果你显式初始化怎么样？
 
    
C语言是通过一个小手段来实现 局部变量 的初始化的。
 
    
int a = 15;//局部变量定义时初始化
 
    
//C语言编译器会自动把这行转为：
 
    
int a;                 //局部变量定义
 
    
a = 15;                    //普通的赋值语句
 
    
 栈的约束（预定栈大小不灵活，怕溢出） 
      
栈是有大小的，所以栈内存大小不好设置，如果太小怕溢出，太大怕浪费内存。 （这个缺点有点像数组） 
其次，栈的溢出危害很大，一定要避免。所以我们在C语言中定义局部变量时不能定义太多或者太大（譬如不能定义局部变量时int a[10000];使用递归来解决问题时一定要注意递归收敛）       
 
 
    
 内存管理之堆 
      
 什么是堆？ 
        
堆（heap）是一种内存管理方式。 内存管理对操作系统来说是一件非常复杂的事情 
          
内存容量很大 
内存需求在时间和大小块上没有规律(操作系统上运行着大量的进程随时都会申请或者释放内存,申请或者释放的内存块大小随意) 
 
堆 内存管理方式特点就是自由(随时申请、释放；大小块随意)。堆内存是操作系统划归给堆管理器（操作系统中的一段代码，属于操作系统中的一段代码，属于操作系统的内存管理单元）来管理的，然后向使用者（用户进程）提供API（malloc free）来使用堆内存 
什么时候使用堆内存？    需要内存容量比较大时，需要反复使用及释放时；很多数据结构（譬如链表，二叉树）的实现都要使用堆内存。 
 
堆内存的特点 
        
容量不限，常规使用的需求容量都能满足 
申请及释放都需要手工进行，需要程序员写代码明确进项申请malloc及释放free，如果程序员申请内存并使用后未释放，这段内存就丢失了（在对管理器的记录中，这段内存仍然属于你这个进程，但是进程自己又以为内存已经不用了，再用的时候又回去申请新的内存块，这就叫吃内存），称为内存泄露。在C/C++ 语言中，内存泄露是最严重的程序bug，这也是别人认为Java/C#优秀的地方。 
 
C语言操作堆内存的接口（malloc   free） 
        
堆内存释放时最简单，直接调用free释放即可。    void free(void *ptr)； 
堆内存申请时，有3个可选择的类似功能的函数：malloc，calloc, realloc 
          
 void *malloc(size_t size); 
void *calloc(size_t nmemb,size_t size);  //nmemb 个单元，每个单元size 个字节 
void *realloc (void *ptr, size_t size);  //改变原来申请的空间的大小的 
 
 
 
 
    
譬如要申请10个int 元素的内存：
 
    
 malloc(40);                    malloc(10*sizeof(int));
 
    
 calloc(10,4);                  calloc(10, sizeof(int));
 
    
数组定义时必须同时给出数组元素个数（数组大小），而且一旦定义再无法更改。 
 
    
语法技巧可以更改数组大小，但其实这只是一种障眼法。他的工作原理是：先重新创建一个新的数组大小为要更改后的数组，然后将原数组的所有元素复制进新的数组，然后释放原数组，最后返回新的数组给用户；
 
    
堆内存申请时给定大小，然后一旦申请完成大小不变，如果要变只能通过realloc接口（原理与上述语法技巧一致）
 
    
 优势与劣势（管理大块内存、灵活、容易内存泄露） 
 
    
优势：灵活
 
    
劣势：需要程序员去处理各种细节，所以容易出错，严重依赖程序员的水水平。
 
    
复杂数据结构 
      
 链表、哈希表、二叉树、图等 
        
链表是最简单且最重要的，链表在linux内核中使用非常多，驱动、应用编程很多时候都需要使用链表。所以对链表必须掌握，掌握到：  会自己定义结构体实现链表、会写链表的节点插入（前插、后插）、节点删除、节点查找、节点遍历等。 
哈希表不是很常用，一般不需要自己学实现，而直接使用别人实现的哈希表比较多。对我们来说最重要的是要明白哈希表的原理、从而知道哈希表的特点，从而知道什么时候该用哈希表，当看到别人用了哈希表的时候要明白别人为什么要用哈希表。合不合适？有没有好的选择？ 
          
哈希表类似于数组，但是在索引节点时是利用某种映射方式的 
 
二叉树、图等。在嵌入式开发中这些数据结构用的很少很少，且这些数据结构一般用来解决特定问题的。 
 
为什么需要更复杂的数据结构？ 
        
因为现实中的实际问题是多种多样的，问题的复杂度不同，所以需要解决问题的算法和数据结构也不同。 
所以在处理不同复杂度的问题，就去针对性解决的数据结构和算法 
 
数据结构和算法的关系 
        
数据结构的发明都是为了配合一定的算法 
算法是为了处理具体问题，算法的实现依赖于相应的数据结构。 
当前我们所的算法和纯数学是不同的（算法是基于数学的），因为计算机算法要求以数学算法为指导，并且结合计算机本身的特点来改进，最终实现一个在计算机上可以运行的算法（即代码可以表示的算法）。 
 
应该怎样学习这部分？ 
        
数据结构和算法是相辅相成的，要一起研究。 
数据结构和算法对嵌入式来说不全是重点，不要盲目去研究这个。 
一般在实际应用中实现数据结构和算法的人和使用数据结构和算法的人是分开的。实际中有一部分人的工作就是研究数据结构和算法，并且试图用代码来实现这些算法（表现为库）；其他真正做工作的人要做的就是理解明白这些算法和数据结构的意义、优劣、特征，然后在合适的时候选择合适的数据结构和算法来解决自己碰到的实际问题。 
 
 
 
    
举个例子：linux内核在字符设备驱动管理时，使用了哈希表（hash table,散列表）。所以字符驱动的很多特点都和哈希表的特点有关。
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
    
 
 
   
 
  
 
 
 

还是紧接着昨天的问题，很想明白到底在内存中堆的数据结构到底是怎么样的？究竟是不是别人回答的红黑树的结构？
 
在网上搜索了一番好像也鲜有答案。后来在《0day 安全 软件漏洞分析技术》一书里面找到了这个问题的部分答案。
 
不同平台操作系统对内存的管理机制是不一样的。
 
上面这本书里面主要讲了对windows2000 - windows xp1 平台的堆管理策略。
 
对于基本的操作系统中堆的一些特征，这里就不再讲了。这里主要说说内存中堆的数据结构。
 
自己画了张图给大家看看。。。
 
 
                                      (堆的内存组织)
 
 
现代操作系统的堆数据结构一般包括堆块和堆表两类。
 
堆块：堆区的内存按照不同大小组织成块，以堆块为单位进行标识，而不是按照字节标识。一个堆块包括两个部分：块首和块身。
 
块首是堆块头部的几个字节，用来标识这个堆块自身的信息，包括本块的大小、本块空闲还是占用等信息；
 
块身紧跟在块首后面的部分，是最终分配给用户使用的数据区。
 
我们在程序中很难感觉到块首的存在。但是正是由于这个块首的存在，解决了我上几天提出的为什么free的地址必须是malloc的地址 还有free的长度是确定的这两个问题。
 
因为这些信息全部包含在块首里面，释放的时候必须进行比对，如果比对结果失败，那么自然是无法进行free操作了.(个人猜测，求验证)
 

 
 
堆表：位于堆区的起始位置，用于索引堆区中堆块的重要信息。堆表的数据结构决定了整个堆区的组织方式。堆表在设计时可能会考虑采用平衡二叉树等高级数据结构用于优化查找效率。现代操作系统的堆表往往不止一种数据结构。
 
在windows中，占用态的堆块被使用它的程序索引，而堆表只索引所有空闲态的堆块。
 
重要的堆表有两种：空闲双向链表FreeList（空表） 和 快速单向链表Lookaside（快表）
 
 
空闲双向链表FreeList（空表）：
 
堆区一开始的堆表区中有一个128项的指针数组（看到有人说把它看成队列的），被称作空表索引。该数组的每一项包含两个指针，用于表示一条空表。
 
free[1] 标识了所有堆中所有大小为8字节的空闲堆块，之后每个索引指示的空闲堆块递增8个字节。即：
 
free[2]标识了16个字节的空闲堆块。
 
free[k] 标识了 k * 8 个字节的空闲堆块。
 
指示第1项空表索引比较特殊，从图中我们也可以看到：这条双向链表链入了所有大于等于1024字节的堆块（小于512KB），堆块按照升序排列。
 

 
 

 
 
快速单向链表Lookaside（快表）
 
 
 
为什么叫做快表呢？因为速度快。。。为什么速度快呢？。。因为这类单向链表中从来不会发生堆块合并。
 
结构组织和空表差不多，只是每条快表最多只有4个结点，故很快就会被填满。
 

 
 
未完待续，下次讲讲  堆块的分配，释放和合并操作。
 

网上有一篇很好的文章，我差不多直接搬运过来了。
 
 
 
来源：http://www.cleey.com/blog/single/id/776.html
 
 
原文如下：
 
可能很多同学在这个概念上有些模糊，其实堆栈分为数据结构和内存的。数据结构的堆栈我想很多同学学习过，今天介绍下数据结构的堆栈，但是重点是内存的堆栈整理。
 
数据结构的栈和堆
 
首先在数据结构上要知道堆栈，尽管我们这么称呼它，但实际上堆栈是两种数据结构：堆和栈。
 
堆和栈都是一种数据项按序排列的数据结构。
 
堆像一棵倒过来的树
 
而堆就不同了，堆是一种经过排序的树形数据结构，每个结点都有一个值。
通常我们所说的堆的数据结构，是指二叉堆。
堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。
 
由于堆的这个特性，常用来实现优先队列，堆的存取是随意，这就如同我们在图书馆的书架上取书，虽然书的摆放是有顺序的，但是我们想取任意一本时不必像栈一样，先取出前面所有的书，书架这种机制不同于箱子，我们可以直接取出我们想要的书。
 
内存分配中的栈和堆
 
先看百度百科中的内存堆栈介绍：
 
 
 
栈（操作系统）：由操作系统自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
堆（操作系统）： 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收，分配方式倒是类似于链表。
 
 
堆栈缓存方式
 
 
 
栈使用的是一级缓存， 他们通常都是被调用时处于存储空间中，调用完毕立即释放。
堆则是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）。所以调用这些对象的速度要相对来得低一些。
 
 
下面就说说C语言程序内存分配中的堆和栈，这里有必要把内存分配也提一下，大家不要嫌我啰嗦，一般情况下程序存放在Rom（只读内存，比如硬盘）或Flash中，运行时需要拷到RAM（随机存储器RAM）中执行，RAM会分别存储不同的信息，如下图所示：
 
 
内存中的栈区处于相对较高的地址以地址的增长方向为上的话，栈地址是向下增长的。
 
栈中分配局部变量空间，堆区是向上增长的用于分配程序员申请的内存空间。另外还有静态区是分配静态变量，全局变量空间的；只读区是分配常量和程序代码空间的；以及其他一些分区。
 
来看一个网上很流行的经典例子：
 
int a = 0; //全局初始化区 
char *p1; //全局未初始化区 
main() 
{ 
    int b; //栈 
    char s[] = "abc"; //栈 
    char *p2; //栈 
    char *p3 = "123456"; //123456\0在常量区，p3在栈上。 
    static int c =0； //全局（静态）初始化区 
    p1 = (char *)malloc(10); //堆 
    p2 = (char *)malloc(20);  //堆 
}
 
0.申请方式和回收方式不同
 
不知道你是否有点明白了。
 
堆和栈的第一个区别就是申请方式不同：栈（英文名称是stack）是系统自动分配空间的，例如我们定义一个 char a；系统会自动在栈上为其开辟空间。而堆（英文名称是heap）则是程序员根据需要自己申请的空间，例如malloc（10）；开辟十个字节的空间。
 
由于栈上的空间是自动分配自动回收的，所以栈上的数据的生存周期只是在函数的运行过程中，运行后就释放掉，不可以再访问。而堆上的数据只要程序员不释放空间，就一直可以访问到，不过缺点是一旦忘记释放会造成内存泄露。还有其他的一些区别我认为网上的朋友总结的不错这里转述一下：
 
 
 
我备注：解释下内存泄露？百度百科 内存泄露
 
 
1.申请后系统的响应
 
栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。 
 堆：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样，代码中的 delete语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部分重新放入空闲链表中。 
 
也就是说堆会在申请后还要做一些后续的工作这就会引出申请效率的问题。
 
2.申请效率的比较
 
根据第0点和第1点可知。
 
栈：由系统自动分配，速度较快。但程序员是无法控制的。
 
堆：是由new分配的内存，一般速度比较慢，而且容易产生内存碎片不过用起来最方便。
 
3.申请大小的限制
 
栈：在Windows下栈是向低地址扩展的数据结构，是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，在 WINDOWS下，栈的大小是2M（也有的说是1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。 
 
堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。
 
 
 
我备注：什么是虚拟内存？怕很多人不清楚什么是虚拟内存的概念，看下百度百科上的意思 虚拟内存
 
 
4.堆和栈中的存储内容
 
由于栈的大小有限，所以用子函数还是有物理意义的，而不仅仅是逻辑意义。
 
栈： 在函数调用时，第一个进栈的是主函数中函数调用后的下一条指令（函数调用语句的下一条可执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。 
 当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。 
 
堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。
 
5.存取效率的比较
 
char s1[] = "aaaaaaaaaaaaaaa"; 
char *s2 = "bbbbbbbbbbbbbbbbb"; 
 
aaaaaaaaaaa是在运行时刻赋值的；放在栈中。 
 而bbbbbbbbbbb是在编译时就确定的；放在堆中。 
 但是，在以后的存取中，在栈上的数组比指针所指向的字符串(例如堆)快。 
 
比如： 
 
#include 
void main() 
{ 
  char a = 1; 
  char c[] = "1234567890"; 
  char *p ="1234567890"; 
  a = c[1]; 
  a = p[1]; 
  return; 
} 
 
对应的汇编代码 :
 
10: a = c[1]; 
00401067 8A 4D F1 mov clbyte ptr [ebp-0Fh] 
0040106A 88 4D FC mov byte ptr [ebp-4]cl 
11: a = p[1]; 
0040106D 8B 55 EC mov edxdword ptr [ebp-14h] 
00401070 8A 42 01 mov albyte ptr [edx+1] 
00401073 88 45 FC mov byte ptr [ebp-4]al
 
关于堆和栈区别的比喻
 
堆和栈的区别可以引用一位前辈的比喻来看出： 
 
使用栈就象我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是自由度小。 
使用堆就象是自己动手做喜欢吃的菜肴，比较麻烦，但是比较符合自己的口味，而且自由度大。比喻很形象，说的很通俗易懂，不知道你是否有点收获。
 
网上还有篇文章分析的很好：内存中的堆和栈到底是什么
 
 
网上有篇文章关于「内存之栈和堆」的，我觉得贴在这可以结合起来一起看看：
 
 
 
来源：什么是堆和栈，它们在哪儿？ 
 译者：独酌逸醉 
 
 
原文如下：
 
问题描述（该问题来源  StackOverflow）
 
编程语言书籍中经常解释值类型被创建在栈上，引用类型被创建在堆上，但是并没有本质上解释这堆和栈是什么。我仅有高级语言编程经验，没有看过对此更清晰的解释。我的意思是我理解什么是栈，但是它们到底是什么，在哪儿呢（站在实际的计算机物理内存的角度上看）？
 
在通常情况下由操作系统（OS）和语言的运行时（runtime）控制吗？
它们的作用范围是什么？
它们的大小由什么决定？
哪个更快？
 
答案一：
 
栈是为执行线程留出的内存空间。当函数被调用的时候，栈顶为局部变量和一些 bookkeeping 数据预留块。当函数执行完毕，块就没有用了，可能在下次的函数调用的时候再被使用。栈通常用后进先出（LIFO）的方式预留空间；因此最近的保留块（reserved block）通常最先被释放。这么做可以使跟踪堆栈变的简单；从栈中释放块（free block）只不过是指针的偏移而已。
 
堆（heap）是为动态分配预留的内存空间。和栈不一样，从堆上分配和重新分配块没有固定模式；你可以在任何时候分配和释放它。这样使得跟踪哪部分堆已经被分配和被释放变的异常复杂；有许多定制的堆分配策略用来为不同的使用模式下调整堆的性能。
 
每一个线程都有一个栈，但是每一个应用程序通常都只有一个堆（尽管为不同类型分配内存使用多个堆的情况也是有的）。
 
直接回答你的问题： 1. 当线程创建的时候，操作系统（OS）为每一个系统级（system-level）的线程分配栈。通常情况下，操作系统通过调用语言的运行时（runtime）去为应用程序分配堆。 2. 栈附属于线程，因此当线程结束时栈被回收。堆通常通过运行时在应用程序启动时被分配，当应用程序（进程）退出时被回收。 3. 当线程被创建的时候，设置栈的大小。在应用程序启动的时候，设置堆的大小，但是可以在需要的时候扩展（分配器向操作系统申请更多的内存）。 4. 栈比堆要快，因为它存取模式使它可以轻松的分配和重新分配内存（指针/整型只是进行简单的递增或者递减运算），然而堆在分配和释放的时候有更多的复杂的 bookkeeping 参与。另外，在栈上的每个字节频繁的被复用也就意味着它可能映射到处理器缓存中，所以很快（译者注：局部性原理）。
 
答案二：
 
Stack: 
 
和堆一样存储在计算机 RAM 中。
在栈上创建变量的时候会扩展，并且会自动回收。
相比堆而言在栈上分配要快的多。
用数据结构中的栈实现。
存储局部数据，返回地址，用做参数传递。
当用栈过多时可导致栈溢出（无穷次（大量的）的递归调用，或者大量的内存分配）。
在栈上的数据可以直接访问（不是非要使用指针访问）。
如果你在编译之前精确的知道你需要分配数据的大小并且不是太大的时候，可以使用栈。
当你程序启动时决定栈的容量上限。
 
Heap:
 
和栈一样存储在计算机RAM。
在堆上的变量必须要手动释放，不存在作用域的问题。数据可用 delete, delete[] 或者 free 来释放。
相比在栈上分配内存要慢。
通过程序按需分配。
大量的分配和释放可造成内存碎片。
在 C++ 中，在堆上创建数的据使用指针访问，用 new 或者 malloc 分配内存。
如果申请的缓冲区过大的话，可能申请失败。
在运行期间你不知道会需要多大的数据或者你需要分配大量的内存的时候，建议你使用堆。
可能造成内存泄露。
 
举例：
 
int foo()
{
    char *pBuffer; //<--nothing allocated yet (excluding the pointer itself, which is allocated here on the stack).
    bool b = true; // Allocated on the stack.
    if(b)
    {
        //Create 500 bytes on the stack
        char buffer[500];

        //Create 500 bytes on the heap
        pBuffer = new char[500];

    }//<-- buffer is deallocated here, pBuffer is not
}//<--- oops there's a memory leak, I should have called delete[] pBuffer;
 
答案三：
 
堆和栈是两种内存分配的两个统称。可能有很多种不同的实现方式，但是实现要符合几个基本的概念：
 
对栈而言，栈中的新加数据项放在其他数据的顶部，移除时你也只能移除最顶部的数据（不能越位获取）。 
 
对堆而言，数据项位置没有固定的顺序。你可以以任何顺序插入和删除，因为他们没有“顶部”数据这一概念。 
 
 
上面上个图片很好的描述了堆和栈分配内存的方式。
 
在通常情况下由操作系统（OS）和语言的运行时（runtime）控制吗？
 
如前所述，堆和栈是一个统称，可以有很多的实现方式。计算机程序通常有一个栈叫做调用栈，用来存储当前函数调用相关的信息（比如：主调函数的地址，局部变量），因为函数调用之后需要返回给主调函数。栈通过扩展和收缩来承载信息。实际上，程序不是由运行时来控制的，它由编程语言、操作系统甚至是系统架构来决定。
 
堆是在任何内存中动态和随机分配的（内存的）统称；也就是无序的。内存通常由操作系统分配，通过应用程序调用 API 接口去实现分配。在管理动态分配内存上会有一些额外的开销，不过这由操作系统来处理。
 
它们的作用范围是什么？
 
调用栈是一个低层次的概念，就程序而言，它和“作用范围”没什么关系。如果你反汇编一些代码，你就会看到指针引用堆栈部分。就高级语言而言，语言有它自己的范围规则。一旦函数返回，函数中的局部变量会直接直接释放。你的编程语言就是依据这个工作的。
 
在堆中，也很难去定义。作用范围是由操作系统限定的，但是你的编程语言可能增加它自己的一些规则，去限定堆在应用程序中的范围。体系架构和操作系统是使用虚拟地址的，然后由处理器翻译到实际的物理地址中，还有页面错误等等。它们记录那个页面属于那个应用程序。不过你不用关心这些，因为你仅仅在你的编程语言中分配和释放内存，和一些错误检查（出现分配失败和释放失败的原因）。
 
它们的大小由什么决定？
 
依旧，依赖于语言，编译器，操作系统和架构。栈通常提前分配好了，因为栈必须是连续的内存块。语言的编译器或者操作系统决定它的大小。不要在栈上存储大块数据，这样可以保证有足够的空间不会溢出，除非出现了无限递归的情况（额，栈溢出了）或者其它不常见了编程决议。
 
堆是任何可以动态分配的内存的统称。这要看你怎么看待它了，它的大小是变动的。在现代处理器中和操作系统的工作方式是高度抽象的，因此你在正常情况下不需要担心它实际的大小，除非你必须要使用你还没有分配的内存或者已经释放了的内存。
 
哪个更快一些？
 
栈更快因为所有的空闲内存都是连续的，因此不需要对空闲内存块通过列表来维护。只是一个简单的指向当前栈顶的指针。编译器通常用一个专门的、快速的寄存器来实现。更重要的一点事是，随后的栈上操作通常集中在一个内存块的附近，这样的话有利于处理器的高速访问（译者注：局部性原理）。
 
答案四：
 
你问题的答案是依赖于实现的，根据不同的编译器和处理器架构而不同。下面简单的解释一下：
 
栈和堆都是用来从底层操作系统中获取内存的。
在多线程环境下每一个线程都可以有他自己完全的独立的栈，但是他们共享堆。并行存取被堆控制而不是栈。
 
堆:
 
堆包含一个链表来维护已用和空闲的内存块。在堆上新分配（用 new 或者 malloc）内存是从空闲的内存块中找到一些满足要求的合适块。这个操作会更新堆中的块链表。这些元信息也存储在堆上，经常在每个块的头部一个很小区域。
堆的增加新快通常从地地址向高地址扩展。因此你可以认为堆随着内存分配而不断的增加大小。如果申请的内存大小很小的话，通常从底层操作系统中得到比申请大小要多的内存。
申请和释放许多小的块可能会产生如下状态：在已用块之间存在很多小的空闲块。进而申请大块内存失败，虽然空闲块的总和足够，但是空闲的小块是零散的，不能满足申请的大小，。这叫做“堆碎片”。
当旁边有空闲块的已用块被释放时，新的空闲块可能会与相邻的空闲块合并为一个大的空闲块，这样可以有效的减少“堆碎片”的产生。
 
 
栈:
 
栈经常与 sp 寄存器（译者注：”stack pointer”，了解汇编的朋友应该都知道）一起工作，最初 sp 指向栈顶（栈的高地址）。
CPU 用 push 指令来将数据压栈，用 pop 指令来弹栈。当用 push 压栈时，sp 值减少（向低地址扩展）。当用 pop 弹栈时，sp 值增大。存储和获取数据都是 CPU 寄存器的值。
当函数被调用时，CPU使用特定的指令把当前的 IP （译者注：“instruction pointer”，是一个寄存器，用来记录 CPU 指令的位置）压栈。即执行代码的地址。CPU 接下来将调用函数地址赋给 IP ，进行调用。当函数返回时，旧的 IP 被弹栈，CPU 继续去函数调用之前的代码。
当进入函数时，sp 向下扩展，扩展到确保为函数的局部变量留足够大小的空间。如果函数中有一个 32-bit 的局部变量会在栈中留够四字节的空间。当函数返回时，sp 通过返回原来的位置来释放空间。
如果函数有参数的话，在函数调用之前，会将参数压栈。函数中的代码通过 sp 的当前位置来定位参数并访问它们。
函数嵌套调用和使用魔法一样，每一次新调用的函数都会分配函数参数，返回值地址、局部变量空间、嵌套调用的活动记录都要被压入栈中。函数返回时，按照正确方式的撤销。
栈要受到内存块的限制，不断的函数嵌套/为局部变量分配太多的空间，可能会导致栈溢出。当栈中的内存区域都已经被使用完之后继续向下写（低地址），会触发一个 CPU 异常。这个异常接下会通过语言的运行时转成各种类型的栈溢出异常。（译者注：“不同语言的异常提示不同，因此通过语言运行时来转换”我想他表达的是这个含义）
 
 
函数的分配可以用堆来代替栈吗？
 
不可以的，函数的活动记录（即局部或者自动变量）被分配在栈上， 这样做不但存储了这些变量，而且可以用来嵌套函数的追踪。
 
堆的管理依赖于运行时环境，C 使用 malloc ，C++ 使用 new ，但是很多语言有垃圾回收机制。
 
栈是更低层次的特性与处理器架构紧密的结合到一起。当堆不够时可以扩展空间，这不难做到，因为可以有库函数可以调用。但是，扩展栈通常来说是不可能的，因为在栈溢出的时候，执行线程就被操作系统关闭了，这已经太晚了。
 
译者注
 
关于堆栈的这个帖子，对我来说，收获非常多。我之前看过一些资料，自己写代码的时候也常常思考。就这方面，也和祥子（我的大学舍友，现在北京邮电读研，技术牛人）探讨过多次了。但是终究是一个一个的知识点，这个帖子看完之后，豁然开朗，把知识点终于连接成了一个网。这种感觉，经历过的一定懂得，期间的兴奋不言而喻。
 
这个帖子跟帖者不少，我选了评分最高的四个。这四个之间也有一些是重复的观点。个人钟爱第四个回答者，我看的时候，瞬间高潮了，有木有？不过需要一些汇编语言、操作系统、计算机组成原理的的基础，知道那几个寄存器是干什么的，要知道计算机的流水线指令工作机制，保护/恢复现场等概念。三个回复者都涉及到了操作系统中虚拟内存；在比较速度的时候，大家一定要在脑中对“局部性原理”和计算机高速缓存有一个概念。
 
如果你把这篇文章看懂了，我相信你收获的不只是堆和栈，你会理解的更多！
 
兴奋之余，有几点还是要强调的，翻译没有逐字逐词翻译，大部分是通过我个人的知识积累和对回帖者的意图揣测而来的。请大家不要咬文嚼字，逐个推敲，我们的目的在于技术交流，不是么？达到这一目的就够了。
 
下面是一些不确定点：
 
我没有听过 bookkeeping data 这种说法，故没有翻译。从上下文理解来看，可以想成是用来寄存器值？函数参数？返回地址？如果有了解具体含义的朋友，烦请告知。
栈和堆栈是一回事，英文表达是 stack，堆是 heap。
调用栈的概念，我是第一次听说，不太熟悉。大家可以去查查资料研究一下。
 
 
原文更新于 2018-01-15