夏萱萱大人
堆和栈的区别(内存和数据结构)在计算机领域，堆栈是一个不容忽视的概念，我们编写的C语言程序基本上都要用到。但对于很多的初学着来说，堆栈是一个很模糊的概念。堆栈：一种数据结构、一个在程序运行时用于存放的地方，这可能是很多初学者的认识，因为我曾经就是这么想的和汇编语言中的堆栈一词混为一谈。我身边的一些编程的朋友以及在网上看帖遇到的朋友中有好多也说不清堆栈，所以我想有必要给大家分享一下我对堆栈的看法，有说的不对的地方请朋友们不吝赐教，这对于大家学习会有很大帮助。数据结构的栈和堆首先在数据结构上要知道堆栈，尽管我们这么称呼它，但实际上堆栈是两种数据结构：堆和栈。堆和栈都是一种数据项按序排列的数据结构。栈就像装数据的桶或箱子我们先从大家比较熟悉的栈说起吧，它是一种具有后进先出性质的数据结构，也就是说后存放的先取，先存放的后取。这就如同我们要取出放在箱子里面底下的东西（放入的比较早的物体），我们首先要移开压在它上面的物体（放入的比较晚的物体）。堆像一棵倒过来的树而堆就不同了，堆是一种经过排序的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。由于堆的这个特性，常用来实现优先队列，堆的存取是随意，这就如同我们在图书馆的书架上取书，虽然书的摆放是有顺序的，但是我们想取任意一本时不必像栈一样，先取出前面所有的书，书架这种机制不同于箱子，我们可以直接取出我们想要的书。内存分配中的栈和堆然而我要说的重点并不在这，我要说的堆和栈并不是数据结构的堆和栈，之所以要说数据结构的堆和栈是为了和后面我要说的堆区和栈区区别开来，请大家一定要注意。下面就说说C语言程序内存分配中的堆和栈，这里有必要把内存分配也提一下，大家不要嫌我啰嗦，一般情况下程序存放在Rom或Flash中，运行时需要拷到内存中执行，内存会分别存储不同的信息，如下图所示：内存中的栈区处于相对较高的地址以地址的增长方向为上的话，栈地址是向下增长的。栈中分配局部变量空间，堆区是向上增长的用于分配程序员申请的内存空间。另外还有静态区是分配静态变量，全局变量空间的；只读区是分配常量和程序代码空间的；以及其他一些分区。来看一个网上很流行的经典例子：main.cpp 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 cl,byte ptr [ebp-0Fh] 0040106A 88 4D FC mov byte ptr [ebp-4],cl 11: a = p[1]; 0040106D 8B 55 EC mov edx,dword ptr [ebp-14h] 00401070 8A 42 01 mov al,byte ptr [edx+1] 00401073 88 45 FC mov byte ptr [ebp-4],al关于堆和栈区别的比喻堆和栈的区别可以引用一位前辈的比喻来看出： 使用栈就象我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是自由度小。 使用堆就象是自己动手做喜欢吃的菜肴，比较麻烦，但是比较符合自己的口味，而且自由度大。比喻很形象，说的很通俗易懂，不知道你是否有点收获。
海派小小甜心
在一段时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域。
局部性原理的 分类 ：
将编译后的目标模块装配成一个可执行程序。
可执行程序以 二进制可执行文件 的形式存储在磁盘上。
链接程序的 任务 ：
程序的链接，可划分为：
重定位 ：将逻辑地址（相对地址）转换为物理地址（绝对地址）的过程。
物理地址 = 逻辑地址 + 程序在内存中的起始地址
程序的装入，可划分为：
任何时刻主存储器 最多只有一个作业 。
每个分区 大小固定不变 ：分区大小相等、分区大小不等。
每个分区可以且 仅可以装入一个作业 。
使用 下限寄存器 和 上限寄存器 来保存当前作业的起始位置和结束位置。
使用 固定分区说明表 区分各分区的状态。
分区 大小不是预先固定的 ，而是按作业（进程）的实际需求来划分的。
分区 个数也不是预先固定的 ，而是由装入的作业数决定的。
使用 空闲分区表 说明空闲分区的位置。
使用 空闲分区链 说明空闲分区的位置。
首次适应算法的 过程 ：
外部碎片：空闲内存 没有在 分配的 进程 中。
内部碎片：空闲内存 在 分配的 进程 中。
从 上次找到的 空闲分区的 下一个 空闲分区开始查找。
优点：空闲区分布均匀、查找开销较小。
缺点：缺乏大空闲区。
最佳适应算法的 过程 ：
优点：提高内存利用率。
注意点：每次在进行空闲区的修改前，需要先进行 分区大小递增 的排序。
页 ：将一个 进程 的 逻辑地址空间 分成若干个 大小相等 的 片 。
页框 ：将 物理内存空间 分成与页大小相同的若干个 存储块 。
分页存储 ：将进程的若干 页 分别装入多个 可以不相邻 的 页框 中。
页内碎片 ：进程 最后一页 一般装不满一个页框，形成 页内碎片 。
页表 ：记录描述页的各种数据，实现从 页号 到 页框号 的映射。
注意： 页内偏移量 的单位是 字节 。
分页地址变换指是： 逻辑地址 通过 地址变换机构 变换为 物理地址 。
分页地址变换的 过程 ：
操作系统在修改或装入页表寄存器的值时，使用的是 特权级 指令。
页大小：512B ~ 4KB，目前的计算机系统中，大多选择 4KB 大小的页。
页大小的 选择因素 ：
快表也称为“转换后援缓冲”，是为了提高CPU访问速度而采用的专用缓存，用来存放 最近被访问过的页表项 。
英文缩写：TLB。
组成： 键和值 。
在TLB中找到某一个页号对应的页表项的百分比称为 TLB命中率 。
当 能 在TLB中找到所需要的页表项时：
有效访问时间 = 一次访问TLB 的时间 + 一次访问内存 的时间（访问内存读写数据或指令）
当 不能 在TLB中找到所需要的页表项时：
有效访问时间 = 一次访问TLB 的时间 + 两次访问内存 的时间（一次访问内存页表，一次访问内存读写数据或指令）
将页表再分页，形成两级或多级页表，将页表离散地存放在物理内存中。
在进程切换时，要运行的进程的页目录表歧视地址被写入 页表寄存器 。
在二级分页系统中，为页表再建立一个页目录表的目的是为了能在地址映射时得到页表在物理内存中的地址，在页目录表的表项中存放了每一个 页表 在物理内存中所在的 页框号 。
虚拟存储器 ：是指具有 请求调入功能 和 置换功能 ，能 从逻辑上对内存容量进行扩充 的一种存储系统。
请求调入 ：就是说，先将进程一部分装入内存，其余的部分什么时候需要，什么时候请求系统装入。
置换 ：如果请求调入时，没有足够的内存，则由操作系统选择一部分内存中的进程内容移到外存，以腾出空间把当前需要装入的内存调入。
为了实现请求分页，需要：
保证进程正常运行的所需要的最小页框数。
最小页框数与进程的大小没有关系，它与计算机的 硬件结构 有关，取决于 指令的格式、功能和寻址方式 。
内存不够时，从进程本身选择淘汰页，还是从系统中所有进程中选择？：
采用什么样的算法为不同进程分配页框？：
常用的两种 置换策略 ： 局部置换 和 全局置换 。
从分配给进程的页框数量上看，常使用的两种 分配策略 ： 固定分配 和 可变分配 。
用新调入的页替换 最长时间没有访问 的页面。
找到 未来最晚被访问 的那个页换出。
，P为缺页率。
有效访问时间与缺页率成 正比 ，缺页率越高，有效访问时间越长，访问效率越低。
工作集 ：某段时间间隔里，进程实际要访问的页的集合。
引入工作集的 目的 ：降低缺页率，提高访问内存效率。
抖动 ：运行进程的大部分时间都用于页的换入换出，几乎不能完成任何有效果工作的状态。
抖动的 产生原因 ：
抖动的 预防方法 ：
在分段存储管理的系统中，程序使用 二维 的逻辑地址，一个数用来表示 段 ，另一个数用来表示 段内偏移量 。
引入分段的 目的 ：
引入分段的 优点 ：
进程的地址空间被划分成 若干个段 。
每个段定义了一组逻辑信息，每个段的大小由相应的逻辑信息组的长度确定， 段的大小不一样 ，每个段的逻辑地址从0开始，采用一段 连续的地址空间 。
系统为每个段分配一个 连续的物理内存区域 ，各个 不同的段可以离散 地放入物理内存不同的区域。
系统为 每个进程建立一张段表 ，段表的每一个表项记录的信息包括： 段号、段长和该段的基址 ，段表存放在内存中。
分段的 逻辑地址结构 ：
段表是由操作系统维护的用于支持分段存储管理 地址映射 的数据结构。
每个进程有一个段表，段表由段表项构成。每个段表项包括： 段号、段长（段的大小）和该段的基址（段的起始地址） 。
若已知逻辑单元的地址为 S:D （段号:段内偏移量），求相应物理地址的步骤如下：
相同点 ：分页和分段都属于 离散 分配方式，都要通过数据结构与硬件的配合来实现 逻辑地址到物理地址 的映射。
不同点 ：
将用户进程的逻辑空间 先划分为若干个段 ， 每个段再划分成若干个页 。
进程以页为单位在物理内存中 离散 存放，每个段中被离散存放的页具有 逻辑相关性 。
为了实现地址映射，操作系统为 每个进程建立一个段表 ，再为 每个段建立一个页表 。
进程段表的段表项组成：
满足以下条件的两个块称为 伙伴 ：
vincent'sir
Virtual memory of computer即页面文件。虚拟内存是文件数据交叉链接的活动文件。是WINDOWS目录下的一个"WIN386.SWP"文件，这个文件会不断地扩大和自动缩小。 就速度方面而言，CPU的L1和L2缓存速度最快，内存次之，硬盘再次之。但是虚拟内存使用的是硬盘的空间，为什么我们要使用速度最慢的硬盘来做为虚拟内存呢？因为电脑中所有运行的程序都需要经过内存来执行，如果执行的程序很大或很多，就会导致我们只有可怜的256M/512M内存消耗殆尽。而硬盘空间动辄几十G上百G，为了解决这个问题，Windows中运用了虚拟内存技术，即拿出一部分硬盘空间来充当内存使用
