linux内存片

① linux内存系统

维基网络——虚拟内存定义

All about Linux swap space

Linux将物理RAM （Random Access Memory） 划分为称为页面的内存块。交换是将一页内存复制到硬盘上的预配置空间（称为交换空间）以释放改内存页面上的过程。物理内存和交换空间的组合就是可用的虚拟内存量。

虚拟内存的那点事儿

进程是与其他进程共享CPU和内存资源的。为了有效的管理内存并减少出错，现代操作系统提供了一种对主存的抽象概念，即：虚拟内存（ Virtual Memory ）。 虚拟内存为每个进程提供一个一致的，私有的地址空间，每个进程拥有一片连续完整的内存空间。

正如 维基网络 所说，虚拟内存不只是“使用硬盘空间来扩展内存”的技术。 虚拟内存的重要意义是它定义了一个连续的虚拟地址空间， 使得程序编写难度降低。并且， 把内存扩展到硬盘空间只是使用虚拟内存的必然结果，虚拟内存空间会存在硬盘中，并且会被全部放入内存中缓冲（按需），有的操作系统还会在内存不够的情况下，将一进程的内存全部放入硬盘空间中，并在切换到进程时再从硬盘读取 （这也是Windows会经常假死的原因...）。

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

内存通常被组织为一个由M个连续的字节大小的单元组成的数组。每个字节都有一个唯一的物理地址 （Physical Address PA） ，作为到数组的索引。

CPU访问内存最简单直接的方法就是使用物理地址，这种寻址方式称为 物理寻址 。

现代计算机使用的是一种被称为虚拟寻址 （Virtual Addressing） 的寻址方式。 使用虚拟寻址，CPU需要将虚拟地址翻译成物理地址，这样才能访问到真实的物理内存。

虚拟寻址需要硬件与操作系统之间相互合作。 CPU中含有一个被称为内存管理单元 （Memory Management Unit，MMU） 的硬件，它的功能是将虚拟地址转换称为物理地址，MMU需要借助存放在内存中的 页表 来动态翻译虚拟地址，该页表由操作系统管理。

分页表是一种数据结构，它用于计算机操作系统中虚拟内存系统，其存储了虚拟地址到物理地址之间的映射。虚拟地址在访问进程中是唯一的，而物理地址在硬件（比如内存）中是唯一的。

在操作系统中使用 虚拟内存 ，每个进程会认为使用一块大的连续的内存，事实上，每个进程的内存散布在 物理内存 的不同区域。或者可能被调出到备份存储中（一般是硬盘）。当一个进程请求自己的内存，操作系统负责把程序生成的虚拟地址，映射到实际存储的物理内存上。操作系统在 分页表 中存储虚拟地址到物理地址的映射。每个映射被称为 分页表项（page table entry ,PTE） 。

在一个简单的地址空间方案中，由虚拟地址寻址的页与物理内存中的帧之间的关系。物理内存可以包含属于许多进程的页。如果不经常使用，或者物理内存已满，可以将页面分页到磁盘。在上图中，并非所有页面都在物理内存中。

虚拟地址到物理地址的转换（即虚拟内存的管理）、内存保护、CPU高速缓存的控制。

现代的内存管理单元是以 页 的方式，分割虚拟地址空间（处理器使用的地址范围）的；页的大小是2的n次方，通常为几KB（字节）。地址尾部的n位（页大小的2的次方数）作为页内的偏移量保持不变。其余的地址位（address）为（虚拟）页号。

内存管理单元通常借助一种叫做转译旁观缓冲器（Translation Lookaside Buffer，TLB）和相联高速缓存来将虚拟页号转换为物理页号。当后备缓冲器中没有转换记录时，则使用一种较慢的机制，其中包括专用硬件的数据结构或软件辅助手段。这个数据结构称为 分页表 ，页表中的数据叫做 分页表项 （page table entry PTE）。物理页号结合页偏移量便提供了完整的物理地址。

页表 或 转换后备缓冲器数据项应该包括的信息有：

有时候，TLB和PTE会 禁止对虚拟页访问 ，这可能是因为没有RAM与虚拟页相关联。如果是这种情况，MMU将向CPU发出页错误的信号，操作系统将进行处理，也许会寻找RAM的空白帧，同时建立一个新的PTE将之映射到所请求的虚拟地址。如果没有空闲的RAM，可能必须关闭一个已经存在的页面，使用一些替换算法，将之保存到磁盘中（这被称为页面调度）。

当需要将虚拟地址转换为物理地址时，首先搜索TLB，如果找到匹配（TLB）命中，则返回物理地址并继续存储器访问。然而，如果没有匹配（称为TLB未命中），则MMU或操作系统TLB未命中处理器通常会查找 页表 中的地址映射以查看是否存在映射（页面遍历），如果存在，则将其写回TLB（这必须完成，因为硬件通过虚拟存储器系统中的TLB访问存储器），并且重启错误指令（这也可以并行发生）。此后续转换找到TLB命中，并且内存访问将继续。

虚拟地址到物理地址的转换过程，如果虚拟内存不存在与TLB，转换会被重置并通过分页表和硬件寻找。

通常情况下，用于处理此中断的程序是操作系统的一部分。如果操作系统判断此次访问有效，那么 操作系统会尝试将相关的分页从硬盘上的虚拟内存文件调入内存。 而如果访问是不被允许的，那么操作系统通常会结束相关的进程。

虽然叫做“页缺失”错误，但实际上这并不一定是一种错误。而且这一机制是利用虚拟内存来增加程序可用内存空间。

发生这种情况的可能性：

当原程序再次需要该页内的数据时，如果这一页确实没有被分配出去，那么系统只需要重新为该页在MMU内注册映射即可。

操作系统需要：

硬性页缺失导致的性能损失是很大的。
另外，有些操作系统会将程序的一部分延迟到需要使用的时候再加载入内存执行，以此提升性能。这一特性也是通过捕获硬性页缺失达到的。

当硬性页缺失过于频繁发生时，称发生 系统颠簸。

具体动作与所使用的操作系统有关，比如Windows会使用异常机制向程序报告，而类Unix系统则使用信号机制。

尽管在整个运行过程中，程序引用不同的页面总数（也就是虚拟内存大小）可能超出了物理存储器（DRAM）总大小，但是程序常常在较小的活动页面上活动，这个集合叫做工作集或者常驻集。在工作集被缓存后，对它的反复调用会使程序命中提高，从而提高性能。

大部分的程序都可以在存储器获取数据和读取中达到稳定的状态，当程序达到稳定状态时，存储器的使用量通常都不会太大。虚拟内存虽然可以有效率控制存储器的使用， 但是大量的页缺失还是造成了系统迟缓的主要因素。 当工作集的大小超过物理存储器大小，程序将会发生一种不幸的情况，这种情况称为 “颠簸” ，页面将不停的写入、释放、读取，由于大量的丢失（而非命中）而损失极大性能。用户可以增加随机存取存储器的大小或是减少同时在系统里运行程序的数量来降低系统颠簸的记录。

推荐阅读：

操作系统--分页(一)

操作系统实现（二）：分页和物理内存管理

② linux中使用了什么内存管理方法,为什么

“事实胜于雄辩”，我们用一个小例子（原形取自《User-Level Memory Management》）来展示上面所讲的各种内存区的差别与位置。

进程的地址空间对应的描述结构是“内存描述符结构”,它表示进程的全部地址空间，——包含了和进程地址空间有关的全部信息，其中当然包含进程的内存区域。

进程内存的分配与回收

创建进程fork()、程序载入execve()、映射文件mmap()、动态内存分配malloc()/brk()等进程相关操作都需要分配内存给进程。不过这时进程申请和获得的还不是实际内存，而是虚拟内存，准确的说是“内存区域”。进程对内存区域的分配最终都会归结到do_mmap（）函数上来（brk调用被单独以系统调用实现，不用do_mmap()），

内核使用do_mmap()函数创建一个新的线性地址区间。但是说该函数创建了一个新VMA并不非常准确，因为如果创建的地址区间和一个已经存在的地址区间相邻，并且它们具有相同的访问权限的话，那么两个区间将合并为一个。如果不能合并，那么就确实需要创建一个新的VMA了。但无论哪种情况，do_mmap()函数都会将一个地址区间加入到进程的地址空间中－－无论是扩展已存在的内存区域还是创建一个新的区域。

同样，释放一个内存区域应使用函数do_ummap()，它会销毁对应的内存区域。

如何由虚变实！

从上面已经看到进程所能直接操作的地址都为虚拟地址。当进程需要内存时，从内核获得的仅仅是虚拟的内存区域，而不是实际的物理地址，进程并没有获得物理内存（物理页面——页的概念请大家参考硬件基础一章），获得的仅仅是对一个新的线性地址区间的使用权。实际的物理内存只有当进程真的去访问新获取的虚拟地址时，才会由“请求页机制”产生“缺页”异常，从而进入分配实际页面的例程。

该异常是虚拟内存机制赖以存在的基本保证——它会告诉内核去真正为进程分配物理页，并建立对应的页表，这之后虚拟地址才实实在在地映射到了系统的物理内存上。（当然，如果页被换出到磁盘，也会产生缺页异常，不过这时不用再建立页表了）

这种请求页机制把页面的分配推迟到不能再推迟为止，并不急于把所有的事情都一次做完（这种思想有点像设计模式中的代理模式（proxy））。之所以能这么做是利用了内存访问的“局部性原理”，请求页带来的好处是节约了空闲内存，提高了系统的吞吐率。要想更清楚地了解请求页机制，可以看看《深入理解linux内核》一书。

这里我们需要说明在内存区域结构上的nopage操作。当访问的进程虚拟内存并未真正分配页面时，该操作便被调用来分配实际的物理页，并为该页建立页表项。在最后的例子中我们会演示如何使用该方法。

系统物理内存管理

虽然应用程序操作的对象是映射到物理内存之上的虚拟内存，但是处理器直接操作的却是物理内存。所以当应用程序访问一个虚拟地址时，首先必须将虚拟地址转化成物理地址，然后处理器才能解析地址访问请求。地址的转换工作需要通过查询页表才能完成，概括地讲，地址转换需要将虚拟地址分段，使每段虚地址都作为一个索引指向页表，而页表项则指向下一级别的页表或者指向最终的物理页面。

每个进程都有自己的页表。进程描述符的pgd域指向的就是进程的页全局目录。下面我们借用《linux设备驱动程序》中的一幅图大致看看进程地址空间到物理页之间的转换关系。

上面的过程说起来简单，做起来难呀。因为在虚拟地址映射到页之前必须先分配物理页——也就是说必须先从内核中获取空闲页，并建立页表。下面我们介绍一下内核管理物理内存的机制。

物理内存管理（页管理）

Linux内核管理物理内存是通过分页机制实现的，它将整个内存划分成无数个4k（在i386体系结构中）大小的页，从而分配和回收内存的基本单位便是内存页了。利用分页管理有助于灵活分配内存地址，因为分配时不必要求必须有大块的连续内存[3]，系统可以东一页、西一页的凑出所需要的内存供进程使用。虽然如此，但是实际上系统使用内存时还是倾向于分配连续的内存块，因为分配连续内存时，页表不需要更改，因此能降低TLB的刷新率（频繁刷新会在很大程度上降低访问速度）。

鉴于上述需求，内核分配物理页面时为了尽量减少不连续情况，采用了“伙伴”关系来管理空闲页面。伙伴关系分配算法大家应该不陌生——几乎所有操作系统方面的书都会提到,我们不去详细说它了，如果不明白可以参看有关资料。这里只需要大家明白Linux中空闲页面的组织和管理利用了伙伴关系，因此空闲页面分配时也需要遵循伙伴关系，最小单位只能是2的幂倍页面大小。内核中分配空闲页面的基本函数是get_free_page/get_free_pages，它们或是分配单页或是分配指定的页面（2、4、8…512页）。

注意：get_free_page是在内核中分配内存，不同于malloc在用户空间中分配，malloc利用堆动态分配，实际上是调用brk()系统调用，该调用的作用是扩大或缩小进程堆空间（它会修改进程的brk域）。如果现有的内存区域不够容纳堆空间，则会以页面大小的倍数为单位，扩张或收缩对应的内存区域，但brk值并非以页面大小为倍数修改，而是按实际请求修改。因此Malloc在用户空间分配内存可以以字节为单位分配,但内核在内部仍然会是以页为单位分配的。

另外,需要提及的是，物理页在系统中由页结构structpage描述，系统中所有的页面都存储在数组mem_map[]中，可以通过该数组找到系统中的每一页（空闲或非空闲）。而其中的空闲页面则可由上述提到的以伙伴关系组织的空闲页链表（free_area[MAX_ORDER]）来索引。

内核内存使用

Slab

所谓尺有所长，寸有所短。以页为最小单位分配内存对于内核管理系统中的物理内存来说的确比较方便，但内核自身最常使用的内存却往往是很小（远远小于一页）的内存块——比如存放文件描述符、进程描述符、虚拟内存区域描述符等行为所需的内存都不足一页。这些用来存放描述符的内存相比页面而言，就好比是面包屑与面包。一个整页中可以聚集多个这些小块内存；而且这些小块内存块也和面包屑一样频繁地生成/销毁。

为了满足内核对这种小内存块的需要，Linux系统采用了一种被称为slab分配器的技术。Slab分配器的实现相当复杂，但原理不难，其核心思想就是“存储池[4]”的运用。内存片段（小块内存）被看作对象，当被使用完后，并不直接释放而是被缓存到“存储池”里，留做下次使用，这无疑避免了频繁创建与销毁对象所带来的额外负载。

Slab技术不但避免了内存内部分片（下文将解释）带来的不便（引入Slab分配器的主要目的是为了减少对伙伴系统分配算法的调用次数——频繁分配和回收必然会导致内存碎片——难以找到大块连续的可用内存），而且可以很好地利用硬件缓存提高访问速度。

Slab并非是脱离伙伴关系而独立存在的一种内存分配方式，slab仍然是建立在页面基础之上，换句话说，Slab将页面（来自于伙伴关系管理的空闲页面链表）撕碎成众多小内存块以供分配，slab中的对象分配和销毁使用kmem_cache_alloc与kmem_cache_free。

Kmalloc

Slab分配器不仅仅只用来存放内核专用的结构体，它还被用来处理内核对小块内存的请求。当然鉴于Slab分配器的特点，一般来说内核程序中对小于一页的小块内存的请求才通过Slab分配器提供的接口Kmalloc来完成（虽然它可分配32到131072字节的内存）。从内核内存分配的角度来讲，kmalloc可被看成是get_free_page（s）的一个有效补充，内存分配粒度更灵活了。

有兴趣的话，可以到/proc/slabinfo中找到内核执行现场使用的各种slab信息统计，其中你会看到系统中所有slab的使用信息。从信息中可以看到系统中除了专用结构体使用的slab外，还存在大量为Kmalloc而准备的Slab（其中有些为dma准备的）。

内核非连续内存分配（Vmalloc）

伙伴关系也好、slab技术也好，从内存管理理论角度而言目的基本是一致的，它们都是为了防止“分片”，不过分片又分为外部分片和内部分片之说，所谓内部分片是说系统为了满足一小段内存区（连续）的需要，不得不分配了一大区域连续内存给它，从而造成了空间浪费；外部分片是指系统虽有足够的内存，但却是分散的碎片，无法满足对大块“连续内存”的需求。无论何种分片都是系统有效利用内存的障碍。slab分配器使得一个页面内包含的众多小块内存可独立被分配使用，避免了内部分片，节约了空闲内存。伙伴关系把内存块按大小分组管理，一定程度上减轻了外部分片的危害，因为页框分配不在盲目，而是按照大小依次有序进行，不过伙伴关系只是减轻了外部分片，但并未彻底消除。你自己比划一下多次分配页面后，空闲内存的剩余情况吧。

所以避免外部分片的最终思路还是落到了如何利用不连续的内存块组合成“看起来很大的内存块”——这里的情况很类似于用户空间分配虚拟内存，内存逻辑上连续，其实映射到并不一定连续的物理内存上。Linux内核借用了这个技术，允许内核程序在内核地址空间中分配虚拟地址，同样也利用页表（内核页表）将虚拟地址映射到分散的内存页上。以此完美地解决了内核内存使用中的外部分片问题。内核提供vmalloc函数分配内核虚拟内存，该函数不同于kmalloc，它可以分配较Kmalloc大得多的内存空间（可远大于128K，但必须是页大小的倍数），但相比Kmalloc来说,Vmalloc需要对内核虚拟地址进行重映射，必须更新内核页表，因此分配效率上要低一些（用空间换时间）

与用户进程相似,内核也有一个名为init_mm的mm_strcut结构来描述内核地址空间，其中页表项pdg=swapper_pg_dir包含了系统内核空间（3G-4G）的映射关系。因此vmalloc分配内核虚拟地址必须更新内核页表，而kmalloc或get_free_page由于分配的连续内存，所以不需要更新内核页表。

vmalloc分配的内核虚拟内存与kmalloc/get_free_page分配的内核虚拟内存位于不同的区间，不会重叠。因为内核虚拟空间被分区管理，各司其职。进程空间地址分布从0到3G(其实是到PAGE_OFFSET,在0x86中它等于0xC0000000)，从3G到vmalloc_start这段地址是物理内存映射区域（该区域中包含了内核镜像、物理页面表mem_map等等）比如我使用的系统内存是64M(可以用free看到)，那么(3G——3G+64M)这片内存就应该映射到物理内存，而vmalloc_start位置应在3G+64M附近（说"附近"因为是在物理内存映射区与vmalloc_start期间还会存在一个8M大小的gap来防止跃界）,vmalloc_end的位置接近4G(说"接近"是因为最后位置系统会保留一片128k大小的区域用于专用页面映射，还有可能会有高端内存映射区，这些都是细节，这里我们不做纠缠)。

上图是内存分布的模糊轮廓

由get_free_page或Kmalloc函数所分配的连续内存都陷于物理映射区域，所以它们返回的内核虚拟地址和实际物理地址仅仅是相差一个偏移量（PAGE_OFFSET），你可以很方便的将其转化为物理内存地址，同时内核也提供了virt_to_phys（）函数将内核虚拟空间中的物理映射区地址转化为物理地址。要知道，物理内存映射区中的地址与内核页表是有序对应的，系统中的每个物理页面都可以找到它对应的内核虚拟地址（在物理内存映射区中的）。

而vmalloc分配的地址则限于vmalloc_start与vmalloc_end之间。每一块vmalloc分配的内核虚拟内存都对应一个vm_struct结构体（可别和vm_area_struct搞混，那可是进程虚拟内存区域的结构），不同的内核虚拟地址被4k大小的空闲区间隔，以防止越界——见下图）。与进程虚拟地址的特性一样，这些虚拟地址与物理内存没有简单的位移关系，必须通过内核页表才可转换为物理地址或物理页。它们有可能尚未被映射，在发生缺页时才真正分配物理页面。

这里给出一个小程序帮助大家认清上面几种分配函数所对应的区域。

#include<linux/mole.h>

#include<linux/slab.h>

#include<linux/vmalloc.h>

unsignedchar*pagemem;

unsignedchar*kmallocmem;

unsignedchar*vmallocmem;

intinit_mole(void)

{

pagemem = get_free_page(0);

printk("<1>pagemem=%s",pagemem);

kmallocmem = kmalloc(100,0);

printk("<1>kmallocmem=%s",kmallocmem);

vmallocmem = vmalloc(1000000);

printk("<1>vmallocmem=%s",vmallocmem);

}

voidcleanup_mole(void)

{

free_page(pagemem);

kfree(kmallocmem);

vfree(vmallocmem);

}

实例

内存映射(mmap)是Linux操作系统的一个很大特色，它可以将系统内存映射到一个文件（设备）上，以便可以通过访问文件内容来达到访问内存的目的。这样做的最大好处是提高了内存访问速度，并且可以利用文件系统的接口编程（设备在Linux中作为特殊文件处理）访问内存，降低了开发难度。许多设备驱动程序便是利用内存映射功能将用户空间的一段地址关联到设备内存上，无论何时，只要内存在分配的地址范围内进行读写，实际上就是对设备内存的访问。同时对设备文件的访问也等同于对内存区域的访问，也就是说，通过文件操作接口可以访问内存。Linux中的X服务器就是一个利用内存映射达到直接高速访问视频卡内存的例子。

熟悉文件操作的朋友一定会知道file_operations结构中有mmap方法，在用户执行mmap系统调用时，便会调用该方法来通过文件访问内存——不过在调用文件系统mmap方法前，内核还需要处理分配内存区域（vma_struct）、建立页表等工作。对于具体映射细节不作介绍了，需要强调的是,建立页表可以采用remap_page_range方法一次建立起所有映射区的页表，或利用vma_struct的nopage方法在缺页时现场一页一页的建立页表。第一种方法相比第二种方法简单方便、速度快，但是灵活性不高。一次调用所有页表便定型了，不适用于那些需要现场建立页表的场合——比如映射区需要扩展或下面我们例子中的情况。

我们这里的实例希望利用内存映射，将系统内核中的一部分虚拟内存映射到用户空间，以供应用程序读取——你可利用它进行内核空间到用户空间的大规模信息传输。因此我们将试图写一个虚拟字符设备驱动程序，通过它将系统内核空间映射到用户空间——将内核虚拟内存映射到用户虚拟地址。从上一节已经看到Linux内核空间中包含两种虚拟地址：一种是物理和逻辑都连续的物理内存映射虚拟地址；另一种是逻辑连续但非物理连续的vmalloc分配的内存虚拟地址。我们的例子程序将演示把vmalloc分配的内核虚拟地址映射到用户地址空间的全过程。

程序里主要应解决两个问题：

第一是如何将vmalloc分配的内核虚拟内存正确地转化成物理地址？

因为内存映射先要获得被映射的物理地址，然后才能将其映射到要求的用户虚拟地址上。我们已经看到内核物理内存映射区域中的地址可以被内核函数virt_to_phys转换成实际的物理内存地址，但对于vmalloc分配的内核虚拟地址无法直接转化成物理地址，所以我们必须对这部分虚拟内存格外“照顾”——先将其转化成内核物理内存映射区域中的地址，然后在用virt_to_phys变为物理地址。

转化工作需要进行如下步骤：

找到vmalloc虚拟内存对应的页表，并寻找到对应的页表项。

获取页表项对应的页面指针

通过页面得到对应的内核物理内存映射区域地址。

如下图所示：

第二是当访问vmalloc分配区时，如果发现虚拟内存尚未被映射到物理页，则需要处理“缺页异常”。因此需要我们实现内存区域中的nopaga操作，以能返回被映射的物理页面指针，在我们的实例中就是返回上面过程中的内核物理内存映射区域中的地址。由于vmalloc分配的虚拟地址与物理地址的对应关系并非分配时就可确定，必须在缺页现场建立页表，因此这里不能使用remap_page_range方法，只能用vma的nopage方法一页一页的建立。

程序组成

map_driver.c，它是以模块形式加载的虚拟字符驱动程序。该驱动负责将一定长的内核虚拟地址(vmalloc分配的)映射到设备文件上。其中主要的函数有——vaddress_to_kaddress（）负责对vmalloc分配的地址进行页表解析,以找到对应的内核物理映射地址（kmalloc分配的地址）；map_nopage()负责在进程访问一个当前并不存在的VMA页时，寻找该地址对应的物理页，并返回该页的指针。

test.c它利用上述驱动模块对应的设备文件在用户空间读取读取内核内存。结果可以看到内核虚拟地址的内容（ok!），被显示在了屏幕上。

执行步骤

编译map_driver.c为map_driver.o模块,具体参数见Makefile

加载模块：insmodmap_driver.o

生成对应的设备文件

1在/proc/devices下找到map_driver对应的设备命和设备号：grepmapdrv/proc/devices

2建立设备文件mknodmapfilec 254 0（在我的系统里设备号为254）

利用maptest读取mapfile文件，将取自内核的信息打印到屏幕上。

③ 内存管理：一文读懂Linux内存组织结构及页面布局

1、内存是什么？

1) 内存又称主存，是 CPU 能直接寻址的存储森郑空间，由半导体器件制成；

2) 内存的特点是存取速率快，断电一般不保存数据，非持久化设备；

2、内存的作用

1) 暂时存放 cpu 的运算数据

2) 硬盘等外部存储器交换的数据

3) 保障 cpu 计算机的稳定性和高性能

1、linux 内存地址空间 Linux 内存管理全貌

2、内存地址——用户态&内核态

3、内存地址——MMU 地址转换

4、内存地址——分段机制

1) 段选择符

更多Linux内核视频教程文档资料免费领取后台私信【 内核 】自行获取。

内核学习网站：

Linux内核源码/内存调优/文件系统/进程管理/设备驱动/网络协议栈-学习视频教程-腾讯课堂

2) 分段实现

5、内存地址——分页机制（32 位）

6、用户态地址空间

7、内核态地址空间

8、进程内存空间

内存管理算法 ——对讨厌自己管理内存的人来说是天赐的礼物

1、内存碎片

1) 基本原理

2) 如何避免内存碎片

2、伙伴系统算法——组织结构

1) 概念

2) 外部碎片

3、伙伴系统算法——申请和回收

1) 申请算法

2) 回收算法

3) 条件

4、如何分配 4M 以上内存？

1) 为何限制大旦春盯块内存分配

2) 内核中获取 4M 以上大内存的方法

5、伙伴系统——反碎片机制

1) 不可移动页

2) 可回收页

6、slab 算法——基本原理

1) 基本概念

2) 内部碎片

7、slab 分配器的结构

详细参考：

经典|图解Linux内存性能优化核心思想

8、slab 高速缓存

1) 普通高速缓存

2) 专用高速缓存

9、内核态内存池

1) 基本原理

2) 内核 API

10、用户态内存池

1) C++ 实例

11、DMA 内存

1) 什么是 DMA

2) DMA 信号

out of memory 的时代过去了吗？no，内存再充足也不可任性使用。

1、内存的使用场景

2、用户态内存分配函数

a) 如果当前连续内存块足够 realloc 的话，只是将 p 所指向的空间扩大，并返回模和 p 的指针地址。这个时候 q 和 p 指向的地址是一样的

b) 如果当前连续内存块不够长度，再找一个足够长的地方，分配一块新的内存，q，并将 p 指向的内容 到 q，返回 q。并将 p 所指向的内存空间删除

3、内核态内存分配函数

4、malloc 申请内存

5、缺页异常

6、用户进程访问内存分析

7、共享内存

1) 原理

2) shm 接口

1、C 内存泄露

2、C 野指针

3、C 资源访问冲突

4、STL 迭代器失效

错误示例：删除当前迭代器，迭代器会失效

正确示例：迭代器 erase 时，需保存下一个迭代器

5、C++ 11 智能指针

（1）原理分析：

（2）数据结构：

（3）使用方法：

6、C++ 11 更小更快更安全

六、 如何查看内存

可以通过 cat /proc/slabinfo 命令查看

可以通过 /proc/sys/vm/drop_caches来释放

④ linux进程内存相关

3种地址：虚拟地址、物理地址、逻辑地址
物理宽坦地址：内存的电路地址，对应内存地址线上的高低电平，物理可见的。
虚拟地址： 分页机制 的产物，也叫线性地址，是进程能看见的地址。
逻辑地址： 分段机制 的产物，属于inter cpu的历史遗留问判巧李题，linux可以当做不存在。
3种地址的转换：进程访问逻辑地址，linux内核根据分段机制装换成虚拟地址，然后把进程的页表和虚拟地址都告诉cpu，cpu就可以根据分页机制将虚拟地址装换成物理地址，然后访问内存。
linux内核中巧妙地屏蔽里分段机制，就是逻辑地址等于虚拟地址，访问内存只需要利用分页机制把虚拟地址转换成物理地址。

linux会为每个进程创建自己的虚拟地址空间，就是进程地址空间，64位系统就是128T的内存空间。需要注意的是，虚拟地址就是假的，一开始不和物理地址对应，也就是说不占用物理内存，只有当虚拟地址有写入操作是，内核会触发缺页，分配真实的物理地址给虚拟地址。物理地址的管理可参考 内核内存管理

从进程空间看，用户态闲置内存有3块，Stack、Memory Mapping Region、Heap，Stack是程序函数调用运行时需要的，不可控，能自由分配的内存就剩Memory Mapping Region、Heap了，linux系统提供的内存分配函数就是针对这两个区域的。
Heap操作函数：int brk(void *addr)、void *sbrk(intptr_t increment)
Memory Mapping Region操作函数：mmap()、munmap()

当然进程可以直接使用系统调用去申请内存，但是如果不管理的话，经过大量的申请和释放，会把进程空间切割的乱七八糟，导致不能申请大块的连续空间，为此就出现了内存管理模块，封装了系统调用，对进程提供malloc和free等高级函数。实际上，除了一些特殊程序，我们也很少用系统调用，一般都是使用内存管理模块提供的malloc和free，关系如下图：

内存管理模块用各种好处，例如不会每次操作都去执行系统调用，减少内存碎片的产生等等。
当然也有很多实现方式，例如常用的glibc的Ptmalloc，google的tcmalloc，facebook的jemalloc等。各有各的应用场景，blablabla....
使用时，gcc默认会链接glibc的，如果想使用其他lib，gcc链接时指定就能覆掘迟盖掉glibc的。

我们重点讲Ptmalloc，从而启发程序员在写程序时多考虑下内存分配情况，可以选择或自己实现适合自己程序的内存管理lib。
Ptmalloc的历史发展，blablabla......，Ptmalloc采取内存池管理，进程malloc时，通过brk（小于128K的内存）、mmap（大内存）从系统获取地址空间，给进程使用，进程free时，不会立即通过brk、munmap将地址空间还给系统，会自己维护起来，叫做空闲内存，这些空闲内存在进程再次malloc时，还会被分出去，并且空闲内存会在特定条件下合并起来还给系统。

内存分配区，管理了一片内存，对外分发和回收，可以理解为一个内存池，分main arena和non main arena。
main arena：最早的分配区，管理着所有可分配的内存，通过brk，mmap等系统调用向系统申请内存。注意只有main arena可以操作Heap。
non main arena：由于多线程的出现，如果多有线程都操作main arena就会有竞争，需要加锁控制，所以出现了non main arena，通过mmap向main arena申请一大块内存，然后自己管理，可以理解为内存分销商。
只有主线程在main arena上申请内存，子线程在non main arena上，non main arena的个数是有上限的，所以non main arena允许多个子线程共用，这样就涉及到加锁，所以程序涉及应避免子线程个数太多。

进程申请到的一块内存叫做一个内存片，arena内部使用chunk数据结构来描述内存片，包括进程正在使用的内存片，和进程free掉的空闲内存片

A：是否main arena内存
M：使用mmap内存
P：上一块是否被使用
size of previous chunk：上一块没有被使用时，表示上块长度，被使用时是上块用来存User data的。
Size of chunk：就是下一块的size of previous chunk，释放时填上本块长度，供下块合并用。

分给进程的内存片arena可以不管，但是进程free回来的，arena需要通过一定方式组织起来，方便进程再次使用。组织方式有下面几种：

bins是个数组，包含128个bin，每个bin是个链表，分small bin和large bin两种，各64个，small bin中chunk大小固定，两个相邻的small bin中的chunk大小相差8bytes，large bin中chunk大小是一定范围内的，其中的chunk按大小排列。
空闲chunk按大小选择合适的bin，按新旧顺序挂到链表上，优先分配旧的chunk。

不大于max_fast （默认值为64B）的chunk被释放后，首先会被放到fast bins 中，fast bins中的chunk并不改变它的使用标志P。这样也就无法将它们合并，当需要给用户分配的chunk小于或等于max_fast时，ptmalloc首先会在fast bins中查找相应的空闲块。在特定的时候，ptmalloc会遍历fast bins中的chunk，将相邻的空闲chunk进行合并，并将合并后的chunk加入unsorted bin中。

进行malloc时，如果在fast bins中没有找到合适的chunk，则ptmalloc会先在unsorted bin中查找合适的空闲chunk，如果unsorted bin不能满足分配要求。malloc便会将unsorted bin中的chunk加入bins中。然后再从bins中继续进行查找和分配过程。从这个过程可以看出来，unsorted bin可以看做是bins的一个缓冲区，增加它只是为了加快分配的速度。

前面的bin中都是回收回来的内存，top chunk才是内存的初始来源，每个arena都有一个top chunk，用来管理Heap的，Heap会在arena第一次分配内存时初始化，会分配一块(chunk_size + 128K) align 4K的空间（132K）作为初始的Heap，top chunk占据整个空间，每次分配会在低地址出切出一片，如下图：

回收时，只有和top chunk相连的内存才能和top chunk合并，才能进而还给系统。

子线程Heap：在main arena中mmap出64M的空间，叫做sub-heap，再在sub-heap上初始化Heap。
主线程的Heap才是真Heap，使用进程Heap，使用brk申请内存。

子线程的heap不够用时，会在申请新的sub-heap，和老的sub-heap单向链表连起来，top chunk会搬到新sub-heap上。

描述mmap出来的内存，单独管理，free时按阈值来决定是否munmap，有动态调整阈值功能，防止太频繁的mmap和munmap。本文不关注。

即最后一次small request中因分割而得到的剩余部分，它有利于改进引用局部性，也即后续对 small chunk 的 malloc 请求可能最终被分配得彼此靠近。
当用户请求 small chunk而无法从small bin和unsorted bin得到时，会在large bin中找最合适的chunk，然后做切割，返回给用户的User chunk，剩下的是Remainder chunk添加到unsorted bin中。这一Remainder chunk就将成为last remainder chunk。

下一块为高地址，前一块为低地址。

Glibc内存管理 华庭（庄明强）

⑤ 详解Linux系统内存知识及调优方案

内存是计算机中重要的部件之一，它是与CPU进行沟通的桥梁。计算机中所有程序的运行都是在内存中进行的，因此内存的性能对计算机的影响非常大。内存作用是用于暂时存放CPU中的运算数据，以及与硬盘等外部存储器交换的数据。只要计算机在运行中，CPU就会把需要运算的数据调到内存中进行运算，当运算完成后CPU再将结果传送出来，内存的运行也决定了计算机的稳定运行。对于整个操作系统来说，内存可能是最麻烦的的设备。而其性能的好坏直接影响着整个操作系统。

我们知道CPU是不能与硬盘打交道的，只有数据被载入到内存中才可以被CPU调用。cpu在访问内存的时候需要先像内存监控程序请求，由监控程序控制和分配内存的读写请求，这个监控程序叫做MMU(内存管理单元)。下面以32位系统来说明内存的访问过程：

32位的系统上每一个进程在访问内存的时候，每一个进程都当做自己有4个G的内存空间可用，这叫虚拟内存(地址)，虚拟内存转化成物理内存是通过MMU来完成的。为了能够从线性地址转换成物理地址，需要page table(页表)的内存空间,page table要载入到MMU上。为了完成线性地址到物理地址的映射，如果按照1个字节1个字节映射的话，需要一张非常大的表，这种转换关系会非常的复杂。因此把内存空间又划分成了另外一种存储单元格式，通常为4K。在不同的硬件平台上，它们的大小一般是不一样的，像x86 32位的有4k的页;而64位的有4k页，2M页，4M页，8M页等等，默认都是4k的。每一个进程一般而言都有自己的页路径和页表映射机制，不管那一个页表都是由内核加载的。每一个进程只能看到自己的线性地址空间，想要增加新的内存的时候，只能在自己的线性地址空间中申请，并且申请后一定是通过操作系统的内核映射到物理地址空间中去找那么一段空间，并且告诉线性地址空间准备好了，可以访问，并且在page table中增加一条映射关系，于是就可以访问物理内存了，这种叫做内存分配。但是新的申请一定是通过操作的内核到物理内存中去找那么一段空间，并且告诉线性地址空间好了，可以建设映射关系，最终page table建立映射关系。

这反映了上述描述过程的大体情况。可以看到每一个用户程序都会有自己的页表，并且映射到对应的主存储器上去。

根据上述文字和图表的描述可以发现2个问题：

1.每个进程如果需要访问内存的时候都需要去查找page table的话，势必会造成服务器的性能底下

2.如果主存储器的内存满了以后，应用程序还需要调用内存的时候怎么办

对于第一个问题，我们就需要借助TLB(Translation Lookaside Buffer)翻译后备缓冲器。TLB是一个内存管理单元，它可以用于改进虚拟地址到物理地址转换速度的缓存。这样每次在查找page table的时候就可以先去TLB中查找相应的页表数据，如果有就直接返回，没有再去查找page table，并把查找到的结果缓存中TLB中。TLB虽然解决了缓存的功能，但是在那么page table中查找映射关系仍然很慢，所以又有了page table的分级目录。page table可以分为1级目录，2级目录和偏移量

但是一个进程在运行的时候要频繁的打开文件，关闭文件。这就意味着要频繁的申请内存和释放内存。有些能够在内存中缓存数据的那些进程，他们对内存的分配和回收更多，那么每一次分配都会在页表中建立一个对应项。所以，就算内存的速度很快，大量频繁的同一时间分配和释放内存，依然会降低服务器的整体性能。当然内存空间不够用的时候，我们称为oom(out of memory,内存耗尽)。当内存耗尽的时候，，整个操作系统挂了。这种情况下我们可以考虑交换分区，交换分区毕竟是由硬盘虚拟出来的内存，所以其性能与真正的内存相比，差了很多，所以要尽力避免使用交换分区。有物理内存空间的时候尽量保证全部使用物理内存。cpu无论如何是不能给交换内存打交道的，它也只能给物理内存打交道，能寻址的空间也只能是物理内存。所以当真正物理内存空间不够用的时候，会通过LRU算法把其中最近最少使用的内存放到交换内存中去，这样物理内存中的那段空间就可以供新的程序使用了。但是这样会引发另外的一个问题，即原来的进程通过page table寻找的时候，那一段空间的数据已经不属于它了。所以此刻cpu发送通知或者异常告诉这个程序，这个地址空间已不属于它，这个时候可能会出现2种情况：

1.物理内存有可用的空间可用：这个时候cpu会根据以前的转换策略会把交换分区中的那段内存重新送到物理内存中去，但是转换过来的空间地址不一定会是以前的那一段空间地址，因为以前的那一段空间地址可能已经被别人使用了。

2.物理内存没有可用的空间可用：这个时候依然会使用LRU算发把当前物理地址空间上最近最少使用的空间地址转换到交换内存中去，并把当前进程需要的这断在交换空间中的内存送到物理内存空间中去，并且重新建立映射关系。

上述通知或者异常出现的情况，通常叫做缺页异常。缺页异常也分为大异常和小异常两种。大异常就是访问的数据内存中没有，不的不去硬盘上加载，无论是从交换内存中还是直接从磁盘的某个文件系统上，反正需要从硬盘上去加载，这种异常加载需要很长时间。小异常就是进程之间通过共享内存，第二个进程访问的时候，查看本地的内存映射表没有，但是其它进程已经拥有了这个内存页，所以可以直接映射，这种异常加载需要的时间一般很短。

在操作系统开机的时候，每一个io设备都会像cpu申请一些列的随机端口，这种端口叫做io端口。在IBM PC体系结构中，I/O地址空间一共提供了65,536个8位的I/O端口。正是这些io端口的存在，cpu可以与io设备进行读写交互的过程。在执行读写操作时，CPU使用地址总线选择所请求的I/O端口，使用数据总线在CPU寄存器和端口之间传送数据。I/O端口还可以被映射到物理地址空间：因此，处理器和I/O设备之间的通信就可以直接使用对内存进行操作的汇编语言指令(例如，mov、and、or等等)。现代的硬件设备更倾向于映射I/O，因为这样处理的速度较快，并可以和DMA结合起来使用。这样io在和内存传数据的时候就不需要通过cpu，cpu把总线的控制权交给DMA，每次io传数据的时候就调用DMA一次，就把cpu给解放了出来。当数据传输完了以后，DMA通知给cpu中断一次。DMA在运行的时候对整个总线有控制权限，当cpu发现有其它进程需要使用总线的时候，二者就会产生争用。这个时候，在总线控制权的使用上，CPU和DMA具有相等的权限。只要CPU委托给了DMA，就不能随意的收回这个委托，就要等待DMA的用完。

如果没有其它进程可以运行，或者其它进程运行的时间非常短，这个时候CPU发现我们的IO仍然没有完成，那就意味着，CPU只能等待IO了。CPU在时间分配里面有个iowait的值，就是CPU在等待IO花费的时间。有些是在同步调用过程中，CPU必须要等待IO的完成;否者CPU可以释放IO的传输在背后自动完成，CPU自己去处理其它的事情。等硬盘数据传输完成以后，硬盘只需要像CPU发起一个通知即可。CPU外围有一种设备，这个设备叫做可编程中断控制器。每一个硬件设备为了给CPU通信，在刚开机的时候，在BIOS实现检测的时候，这个设备就要到可编程中断控制器上去注册一个所谓的中断号。那么这个号码就归这个硬件使用了。当前主机上可能有多个硬件，每一个硬件都有自己的号码，CPU在收到中断号以后，就能够通过中断相量表查找到那个硬件设备进行中断。并且就由对应的IO端口过来处理了。

CPU正在运行其它进程，当一个中断请求发过来的时候，CPU会立即终止当前正在处理的进程，而去处理中断。当前CPU挂起当前正在处理的进程，转而去执行中断的过程，也叫做中断切换。只不过，这种切换在量级别上比进程切换要低一些，而且任何中断的优先级通常比任何进程也要高，因为我们指的是硬件中断。中断还分为上半部和下半部，一般而言，上半部就是CPU在处理的时候，把它接进来，放到内存中，如果这个事情不是特别紧急(CPU或者内核会自己判断)，因此在这种情况下，CPU回到现场继续执行刚才挂起的进程，当这个进程处理完了，再回过头来执行中断的下半部分。

在32位系统中，我们的内存(线性地址)地址空间中，一般而言，低地址空间有一个G是给内核使用的，上面3个G是给进程使用的。但是应该明白，其实在内核内存当中，再往下，不是直接这样划分的。32位系统和64位系统可能不一样(物理地址)，在32位系统中，最低端有那么10多M的空间是给DMA使用的。DNA的总线宽度是很小的，可能只有几位，所以寻址能力很有限，访问的内存空间也就很有限。如果DMA需要复制数据，而且自己能够寻址物理内存，还可以把数据直接壮哉进内存中去，那么就必须保证DMA能够寻址那段内存才行。寻址的前提就是把最低地址断M，DA的寻址范围内的那一段给了DMA。所以站在这个角度来说，我们的内存管理是分区域的。

在32位系统上，16M的内存空间给了ZONE_DMA(DMA使用的物理地址空间);从16M到896M给了ZONE_NORMAL(正常物理地址空间)，对于Linux操作系统来说，是内核可以直接访问的地址空间;从896M到1G这断空间叫做"Reserved"(预留的物理地址空间);从1G到4G的这段物理地址空间中，我们的内核是不能直接访问的，要想访问必须把其中的一段内容映射到Reserved来，在Reserved中保留出那一段内存的地址编码，我们内核才能上去访问，所以内核不直接访问大于1G的物理地址空间。所以在32位系统上，它访问内存当中的数据，中间是需要一个额外步骤的。

在64位系统上，ZONE_DAM给了低端的1G地址空间，这个时候DMA的寻址能力被大大加强了;ZONE_DAM32可以使用4G的空间;而大于1G以上给划分了ZONE_NORMAL,这段空间都可以被内核直接访问。所以在64位上，内核访问大于1G的内存地址，就不需要额外的步骤了，效率和性能上也大大增加，这也就是为什么要使用64位系统的原因。

在现在的PC架构上，AMD,INTER都支持一种机制，叫做PEA(物理地址扩展)。所谓PAE。指的是在32位系统的地址总线上，又扩展了4位，使得32位系统上的地址空间可以达到64G。当然在32为系统上，不管你的物理内存有多大，单个进程所使用的空间是无法扩展的。因为在32位的系统上，线性地址空间只有4个G，而单个进程能够识别的访问也只有3个G。

linux的虚拟内存子系统包含了以下几个功能模块：

slab allocator,zoned buddy allocator,MMU,kswapd,bdflush

slab allocator叫做slab分配器

buddy allocator又叫做buddy system，叫做伙伴系统，也是一种内存分配器

buddy system是工作在MMU之上的，而slab allocator又是工作在buddy system之上的。

设置为小于等于1G，在数据库服务器应该劲量避免使用交换内存

3.在应用服务器上，可以设置为RAM*0.5，当然这个是理论值

如果不的不使用交换内存，应该把交换内存放到最靠外的磁道分区上，因为最外边的磁盘的访问速度最快。所以如果有多块硬盘，可以把每块硬盘的最外层的磁道拿一小部分出来作为交换分区。交换分区可以定义优先级，因此把这些硬盘的交换内存的优先级设置为一样，可以实现负载均衡的效果。定义交换分区优先级的方法为编辑/etc/fstab：

/dev/sda1 swap swap pri=5 0 0

/dev/sdb1 swap swap pri=5 0 0

/dev/sdc1 swap swap pri=5 0 0

/dev/sdd1 swap swap pri=5 0 0

四.内存耗尽时候的相关调优参数

当Linux内存耗尽的时候，它会杀死那些占用内存最多的进程，以下三种情况会杀死进程：

1.所有的进程都是活动进程，这个时候想交换出去都没有空闲的进程

2.没有可用的page页在ZONE_NORMAL中

3.有其它新进程启动，申请内存空间的时候，要找一个空闲内存给做映射，但是这个时候找不到了

一旦内存耗尽的时候，操作系统就会启用oom-kill机制。

在/proc/PID/目录下有一个文件叫做oom_score,就是用来指定oom的评分的，就是坏蛋指数。

如果要手动启用oom-kill机制的话，只需要执行echo f>/proc/sysrq-trigger即可，它会自动杀掉我们指定的坏蛋指数评分最高的那个进程

可以通过echo n > /proc/PID/oom_adj来调整一个进程的坏蛋评分指数。最终的评分指数就是2的oom_adj的值的N次方。假如我们的一个进程的oom_adj的值是5，那么它的坏蛋评分指数就是2的5次方。

如果想禁止oom-kill功能的使用可以使用vm.panic_on_oom=1即可。

五.与容量有关的内存调优参数：

overcommit_memory,可用参数有3个，规定是否能够过量使用内存：

0：默认设置，内核执行启发式的过量使用处理

1：内核执行无内存的过量使用处理。使用这个值会增大内存超载的可能性

2：内存的使用量等于swap的大小+RAM*overcommit_ratio的值。如果希望减小内存的过度使用，这个值是最安全的

overcommit_ratio:将overcommit_memory指定为2时候，提供的物理RAM比例，默认为50

六.与通信相关的调优参数

常见在同一个主机中进行进程间通信的方式：

1.通过消息message;2.通过signal信号量进行通信;3.通过共享内存进行通信，跨主机常见的通信方式是rpc

以消息的方式实现进程通信的调优方案：

msgmax:以字节为单位规定消息队列中任意消息的最大允许大小。这个值一定不能超过该队列的大小(msgmnb)，默认值为65536

msgmnb:以字节为单位规定单一消息队列的最大值(最大长度)。默认为65536字节

msgmni:规定消息队列识别符的最大数量(及队列的最大数量)。64位架构机器的默认值为1985;32位架构机器的默认值为1736

以共享内存方式实现进程通信的调优方案：

shmall:以字节为单位规定一次在该系统中可以使用的共享内存总量(单次申请的上限)

shmmax:以字节为单位规定每一个共享内存片段的最大大小

shmmni:规定系统范围内最大共享内存片段。在64和32位的系统上默认值都是4096

七.与容量相关的文件系统可调优参数：

file-max:列出内核分配的文件句柄的最大值

dirty_ratio:规定百分比值，当脏数据达到系统内存总数的这个百分比值后开始执行pdflush,默认为20

dirty_background_ratio:规定百分比值，当某一个进程自己所占用的脏页比例达到系统内存总数的这个百分比值后开始在后台执行pdflush，默认为10

dirty_expire_centisecs:pdlush每隔百分之一秒的时间开启起来刷新脏页，默认值为3000，所以每隔30秒起来开始刷新脏页

dirty_writeback_centisecs:每隔百分之一秒开始刷新单个脏页。默认值为500，所以一个脏页的存在时间达到了5秒，就开始刷新脏

八.linux内存常用的观察指标命令：

Memory activity

vmstat [interval] [count]

sar -r [interval] [count]

Rate of change in memory

sar -R [interval] [count]

frmpg/s:每秒释放或者分配的内存页，如果为正数，则为释放的内存页;如果为负数，则为分配的内存页

bufpg/s:每秒buffer中获得或者释放的内存页。如果为正数则为获得的内存页，为负数。则为释放的内存页

campg/s:每秒cache中获得或者释放的内存页。如果为正数则为获得的内存页，为负数。则为释放的内存页

Swap activity

sar -W [interval] [count]

ALL IO

sar -B [interval] [count]

pgpgin/s:每秒从磁盘写入到内核的块数量

pgpgout/s:每秒从内核写入到磁盘的块数量

fault/s:每秒钟出现的缺页异常的个数

majflt/s:每秒钟出现的大页异常的个数

pgfree/s:每秒回收回来的页面个数