内存分配和管理学习总结

内存分配

以c语言为例，在堆上手动分配内存时候主要是调用malloc函数，malloc函数只是c语言提供的函数，实际上堆内存分配调用的是brk和mmap这两种系统调用方式。但是brk和mmap系统调用申请的是虚拟的内存（地址）空间，并没有拿到真正的物理内存空间。但是在第一次访问该内存的时候，程序会发现虚拟内存地址没有映射到物理内存地址，于是触发一个触发一个缺页中断(异常)

当进程发生缺页中断的时候，进程就会陷入内核态，执行以下的操作。

1. 检查要访问的虚拟地址是否合法
2. 查找分配一个物理页
3. 填充物理内容（读取磁盘，或者直接置0，或者啥也不干）。需要读取磁盘，那么这次缺页中断就是majflt，否则就是minflt。这两个不懂。
4. 建立映射关系（虚拟地址到物理地址）

为什么要有逻辑地址

逻辑地址，或称虚拟的内存地址空间。程序无法知道可用的物理地址，因为os是多进程的，所以内存条的物理地址的占用情况是时刻变化的，程序无法预知哪些可用哪些不可用，所以出现了一种解决的方式就是逻辑空间地址，逻辑地址空间被使用的时候，然后去页表寻找有没有映射，没有映射触发缺页中断。

虚拟内存作用是什么

原文

我们都知道一个进程是与其他进程共享CPU和内存资源的。正因如此，操作系统需要有一套完善的内存管理机制才能防止进程之间内存泄漏的问题.
为了更加有效地管理内存并减少出错，现代操作系统提供了一种对主存的抽象概念，即是虚拟内存（Virtual Memory）。虚拟内存为每个进程提供了一个一致的、私有的地址空间，它让每个进程产生了一种自己在独享主存的错觉（每个进程拥有一片连续完整的内存空间）。
虚拟内存的重要意义是它定义了一个连续的虚拟地址空间，使得程序的编写难度降低。并且，把内存扩展到硬盘空间只是使用虚拟内存的必然结果，虚拟内存空间会存在硬盘中，并且会被内存缓存（按需），有的操作系统还会在内存不够的情况下，将某一进程的内存全部放入硬盘空间中，并在切换到该进程时再从硬盘读取.

虚拟内存主要提供了如下三个重要的能力：

• 它把主存看作为一个存储在硬盘上的虚拟地址空间的高速缓存，并且只在主存中缓存活动区域（按需缓存）。
• 它为每个进程提供了一个一致的地址空间，从而降低了程序员对内存管理的复杂性。
• 它还保护了每个进程的地址空间不会被其他进程破坏。

逻辑地址和物理地址如何映射

固定偏移量：
简单的方式，但存在很多问题。
程序A和B采用不同的偏移量，假设A偏移量为0，B偏移量为200。A就使用0-200内存，B使用200-xxx的内存。存在弊端：①程序A未必只占200个空间，不够用；②内碎片：程序A内部用不了200个，造成内部浪费。外碎片：程序A结束后，这200个空间，无法被正好偏移量是200的程序使用，造成外部浪费。

分页机制：

程序或操作系统逻辑地址分为多个页（page），将物理地址分为多个帧（page frame 也叫页，这里方便区分称为帧）。

逻辑地址页到物理地址帧的映射称为 页表（page table）。页号和帧号进行映射，其实页表不仅仅存了映射关系，还存当前页、帧的状态（例如是否可用，权限是否足够等）。

每一个进程都有一个自己的页表来完成地址映射。。

一个32位的程序，它会认为它的的虚拟地址空间是2^32=4G。所以当多个32位或64的程序运行的时候，必然会存在多个程序的内存总和大于物理内存的情况，此时就会借助磁盘内存。这时候page table 对应的帧号只显示磁盘

分页内存寻址过程小例子
机器：32位操作系统 256MB内存 页大小4KB
程序：32位
4K=12bit
逻辑地址 32bit=20bit页号+12bit偏移
物理地址 28bit=16bit帧号+12bit偏移
对于地址0x000011a3 页号00001 偏移 1a3。根据页号找到帧号，帧号+偏移=物理地址。

1. 如果查表后发现帧号是磁盘会发生什么？

这时候会触发缺页中断，切换到内核态，内核从磁盘读取数据加载到内存中，然后把物理地址在page table进行更新，然后重新进行内存寻址的过程。

1. 如果从磁盘加载进内存时，内存帧满了怎么办？

这时候会触发页面置换（页面置换算法），将不太常用的帧 从RAM中逐出到磁盘中，让出位置来存储。

分页总结

• 分页的时候，每一个32位、64位的程序都认为自己有2^32Byte个逻辑地址空间。多个程序内存不够就会存储到磁盘中。通过映射磁盘和高效的页面置换算法，使内存无限大。
• 分页使不同的进程的内存隔离，保证了安全
• 分页降低了内存碎片化问题

分页中的时间和空间优化

• 分页过程中，缺页中断和页面置换，会涉及两次内存读取时间上待优化。（将最常访问的存储到访问更快的硬件中，一般是在MMU（cpu内存管理单元）中。这个小表称为快表，能存8-128个，先查快表再查页表。快表的命中率很高，因为程序最常访问的页没几个（局部性原理））；
• 页表占用空间较大空间上待优化。（采用多级页表或者分段），段页结合的模式旨在x86intelcpu等少数cpu支持，新的x64不在支持。

程序内部的内存管理-分段

• 分段管理（分为了堆取、栈区等），这里的分段不同于页表分段

Kernel space：内核区是共享的。
Stack：栈是向下增长的
Heap堆是向上增长的
Libraries：可能是进程共享的，函数库.dll .so。mmap其实就是在堆和栈之间分配
Data：存储静态变量等
Text：存储程序二进制码等

分段分页的内存碎片问题

内存碎片：页式存储管理的优点是没有外碎片（因为页的大小固定），但会产生内碎片（一个页可能填充不满）；而段式管理的优点是没有内碎片（因为段大小可变，改变段大小来消除内碎片）。但段换入换出时，会产生外碎片（比如4k的段换5k的段，会产生1k的外碎片）。

内碎片和外碎片区别和产生

内部碎片
内部碎片是指已经被分配给某个进程、但是该进程却使用不到的内存空间，只有当该进程运行完毕后才能释放这块内存空间给其他进程使用。

外部碎片
外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。
外部碎片是处于任何两个已分配区域或页面之间的空闲存储块。这些存储块的总和可以满足当前申请的长度要求，但是由于它们的地址不连续或其他原因，使得系统无法满足当前申请。

内部碎片的产生：因为所有的内存分配必须起始于可被 4、8 或 16 整除（视处理器体系结构而定）的地址或者因为MMU的分页机制的限制，决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个 43 字节的内存块时，因为没有适合大小的内存，所以它可能会获得 44字节、48字节等稍大一点的字节，因此由所需大小四舍五入而产生的多余空间就叫内部碎片。

外部碎片的产生： 频繁的分配与回收物理页面会导致大量的、连续且小的页面块夹杂在已分配的页面中间，就会产生外部碎片。假设有一块一共有100个单位的连续空闲内存空间，范围是099。如果你从中申请一块内存，如10个单位，那么申请出来的内存块就为09区间。这时候你继续申请一块内存，比如说5个单位大，第二块得到的内存块就应该为1014区间。如果你把第一块内存块释放，然后再申请一块大于10个单位的内存块，比如说20个单位。因为刚被释放的内存块不能满足新的请求，所以只能从15开始分配出20个单位的内存块。现在整个内存空间的状态是09空闲，1014被占用，1524被占用，2599空闲。其中09就是一个内存碎片了。如果1014一直被占用，而以后申请的空间都大于10个单位，那么09就永远用不上了，变成外部碎片。

brk和mmap内存分配的原理

从操作系统角度来看，进程分配内存有两种方式，分别由两个系统调用完成：brk和mmap（不考虑共享内存）。一般小内存由brk分配，大内存用mmap。

• brk是将数据段(.data)的最高地址指针_edata往高地址推。
• mmap是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存。

这两种方式分配的都是虚拟内存，没有分配物理内存。

在标准C库中，提供了malloc/free函数分配释放内存，这两个函数底层是由brk，mmap，munmap（释放），这些系统调用实现的。

情况1：

malloc小于128k的内存，使用brk分配内存，将_edata往高地址推，

1. 进程启动的时候，其（虚拟）内存空间的初始布局如图1所示。
   其中，mmap内存映射文件是在堆和栈的中间，为了简单起见， 省略了内存映射文件。_edata指针（glibc里面定义）指向数据段的最高地址。
2. 进程调用A=malloc(30K)以后，内存空间如图2：
   malloc函数会调用brk系统调用，将_edata指针往高地址推30K，就完成虚拟内存分配。

只要把_edata+30K就完成内存分配了？ 事实是这样的，_edata+30K只是完成虚拟地址的分配， A这块内存现在还是没有物理页与之对应的， 等到进程第一次读写A这块内存的时候，发生缺页中断，这个时候，内核才分配A这块内存对应的物理页。 也就是说，如果用malloc分配了A这块内容，然后从来不访问它，那么，A对应的物理页是不会被分配的。

1. 进程调用B=malloc(40K)以后，内存空间如图3。

情况2：

malloc大于128k的内存，使用mmap分配内存，在堆和栈之间找一块空闲内存分配(对应独立内存，而且初始化为0)。

1. 进程调用C=malloc(200K)以后，内存空间如图4：
   默认情况下，malloc函数分配内存，如果请求内存大于128K（可由M_MMAP_THRESHOLD选项调节），那就不是去推_edata指针了，而是利用mmap系统调用，从堆和栈的中间分配一块虚拟内存。

这样子做主要是因为 brk分配的内存需要等到高地址内存释放以后才能释放（例如，在B释放之前，A是不可能释放的，这就是内存碎片产生的原因，当然brk分配的内存可以通过内存紧缩什么时候紧缩看下面），而mmap分配的内存可以单独释放。

1. 进程调用D=malloc(100K)以后，内存空间如图5；
2. 进程调用free(C)以后，C对应的虚拟内存和物理内存一起释放。

1. 进程调用free(B)以后，如图7所示：

B对应的虚拟内存和物理内存都没有释放，因为只有一个_edata指针。如果往回推，那么D这块内存怎么办呢？ 当然，B这块内存，是可以重用的，如果这个时候再来一个40K的请求，那么malloc很可能就把B这块内存返回回去了

1. 进程调用free(D)以后，如图8所示： B和D连接起来，变成一块140K的空闲内存。

2. 默认情况下：

   当最高地址空间的空闲内存超过128K（可由M_TRIM_THRESHOLD选项调节）时，执行内存紧缩操作（trim）。在上一个步骤free的时候，发现最高地址空闲内存140k超过128K，于是内存紧缩，变成图9所示。