C++应用程序性能优化（五）——操作系统的内存管理(作,操作系统 内存管理,用,编程语言)

C++应用程序性能优化（五）——操作系统的内存管理

一、操作系统内存管理简介

长期以来，在计算机系统中，内存都是一种紧缺和宝贵的资源，应用程序必须在载入内存后才能执行。早期，在内存空间不够大时，同时运行的应用程序的数量会受到很大的限制，甚至当某个应用程序在某个运行时所需内存超过物理内存时，应用程序就会无法运行。现代操作系统（Windows、Linux）通过引入虚拟内存进行内存管理，解决了应用程序在内存不足时不能运行的问题。
本质上，虚拟内存就是要让一个程序的代码和数据在没有全部载入内存时即可运行。运行过程中，当执行到尚未载入内存的代码，或者要访问还没有载入到内存的数据时，虚拟内存管理器动态地将相应的代码或数据从硬盘载入到内存中。而且在通常情况下，虚拟内存管理器也会相应地先将内存中某些代码或数据置换到硬盘中，为即将载入的代码或数据腾出空间。
因为内存和硬盘间的数据传输相对于代码执行非常慢，因此虚拟内存管理器在保证工作正确的前提下还必须考虑效率因素，如需要优化置换算法，尽量避免将要被执行的代码或访问的数据刚被置换出内存，而很久没有访问的代码或数据却一直驻留在内存中。虚拟内存管理器还需要将驻留在内存中的各个进程的代码数据维持在一个合理的数量上，并且根据进程性能的表现动态调整，使得程序运行时将涉及的磁盘IO次数降到尽可能低，以提高程序的运行性能。

二、Windows内存管理

1、Windows虚拟内存管理系统简介

Win32虚拟内存管理器为每一个Win32进程提供了进程私有并且基于页的4GB（32bit）大小的线性虚拟地址空间。
进程私有即每个进程只能访问属于自己的内存空间，而无法访问属于其它进程的地址空间，也不用担心自己的地址空间被其它进程看到（父子进程例外，比如调试器利用父子进程关系来访问被被调试进程的地址空间）。进程运行时用到的dll并没有属于自己的地址空间，而是其所属进程的虚拟地址空间，dll的全局数据，以及通过dll函数申请的内存都是从调用其进程的虚拟地址空间开辟的。
基于页是指虚拟地址空间被划分为多个称为页的单元，页的大小由底层处理器决定，x86架构处理器中页的大小为4KB。页是Win32虚拟内存管理器处理的最小单元，相应的物理内存也被划分为多个页。虚拟内存地址空间的申请和释放，以及内存和磁盘的数据传输或置换都是以页为最小单位进行的。
4GB大小意味着进程中的地址取值范围可以从0x00000000到0xFFFFFFFF，Win32将低区的2GB留给进程使用，高区的2GB留给系统使用。
Win32中用来辅助实现虚拟内存的硬盘文件称为调页文件，可以有16个，调页文件用来存放被虚拟内存管理器置换出内存的数据。当调页文件的数据再次被进程访问时，虚拟内存管理器会将其从调页文件中置换进内存，进程可以正确对其访问。用户可以自己配置调页文件，出于空间利用效率和性能的考虑，程序代码不会被修改（包括exe和dll），所以当其所在页被置换出内存时，并不会被写进调页文件中，而是直接抛弃。当再次被需要时，虚拟内存管理器直接从存放程序代码的exe或dll文件中找到并调入内存。另外，对exe和dll文件中包含的只读数据的处理与程序代码处理相同，不会在调页文件中开辟空间存储。
当进程执行某段代码或访问某些数据，而代码或数据还不在内存中时，称为缺页错误。缺页错误的原因很多，最常见的是代码和数据被虚拟内存管理器置换出内存，虚拟内存管理器会在代码被执行或数据被访问前将其调入内存。内存置换对开发人员来说是透明的，大大简化了开发人员的工作。但调页错误涉及磁盘IO，大量的调页错误会大大降低程序的总体性能，因此需要了解缺页错误的主要原因和规避方法。

2、使用虚拟内存

Win32中分配内存分为两个步骤，预留和提交。因此在进程虚拟地址空间中的页有三种状态：自由free、预留reserved和提交committed。
自由表示此页尚未被分配，可以用来满足新的内存分配请求。
预留是指从虚拟地址空间划出一块区域（region，页的整数倍），划出后的内存空间不能用来满足新的内存分配请求，而是用来供要求预留此段内存的代码以后使用。预留时并没有分配物理内存，只是增加了一个描述进程虚拟地址空间使用状态的数据结构（VAD，虚拟地址描述符），用来记录此段内存空间已经被预留。预留操作相对较快，因为没有真正分配物理内存，因此预留的空间不能够直接访问，对预留页的访问会引起内存访问违例。
提交，如果想要得到真正的物理内存，必须对预留的内存进行提交。提交会从调页文件中开辟空间，并修改VAD中的相应项。提交时也并没有立刻从物理内存中分配空间，而是从磁盘的调页文件中开辟空间，作为置换的备份空间。当代码第一次访问提交内存中的数据时，系统发现并没由真正的物理内存，抛出缺页操作。虚拟内存管理器会处理缺页错误，直到此时才会真正分配物理内存，提交也可以在预留的同时进行。提交操作会从磁盘的调页文件中开辟空间，所以比预留操作耗时。
Win32虚拟内存管理中demand-paging策略要求不到真正访问时不会为某虚拟地址分配真正的物理内存。demand-paging策略一是处于性能考虑，将工作分段完成，提高总体性能；二是出于空间效率考虑，不到真正访问时，Win32总是假定认为进程不会访问大多数数据，因而不必要为其开辟存储空间或将其置换进物理内存，以提高存储空间的利用率。
如果某些程序对内存有很大的需求，但并不是立刻需要所有内存，则一次性从物理存储中开辟空间满足潜在的需求，从执行性能和存储空间效率上是一种浪费。由于需求只是潜在的，极有可能分配的内存中很大一部分最后都没有被真正利用。如果在申请时一次性为其分配所有物理存储，会极大降低空间的利用率。
但如果完全不用预留和提交机制，只是随需分配内存来满足每次的请求，则对一个会在不同时间点频繁请求内存的代码来说，因为在其请求内存的不同时间点的间隙极有可能会由其它代码请求内存，会导致在不同时间点频繁请求内存的代码得到的内存因为虚拟地址不连续，无法很好利用空间的locality特性，对其整体进行访问（如遍历）时就会增加缺页错误的数量，从而降低程序性能。
预留和提交在Win32程序中都使用VirtualAlloc函数完成，预留传入MEM_RESERVE参数，提交传入MEM_COMMIT参数。释放虚拟内存时使用VirtualFree函数，根据不同的传入参数，与VirtualAlloc函数对应，可以释放与虚拟地址区域相对应的物理内存，但虚拟地址区域还可以处于预留状态，也可以连同虚拟地址区域一同释放，则虚拟地址区域恢复为自由状态。
线程栈和进程堆的实现利用了预留和提交两步机制，Win32系统中，线程栈使用预留和提交两步机制如下：
创建线程栈时，只是预留一个虚拟的地址区域，默认为1M（可以在CreateThread或链接时通过链接选项修改），初始时只有前两页是提交的。当线程栈因为函数的嵌套调用需要更多的提交页时，虚拟内存管理器会动态地提交线程的虚拟地址区域中的后续页以满足其需求，直到到达1M的上限。当到达预留区域大小的上限（默认1M）时，虚拟内存管理器不会增加预留区域的大小，而是在提交最后一页时抛出一个栈溢出异常，抛出栈溢出异常时线程栈还有一页空间可以利用，程序仍可正常运行。当程序继续使用栈空间，用完最后一页时，还继续需要存储空间，此时超过上限，会直接导致进程退出。
为了防止线程栈溢出导致整个程序退出，应该尽量控制栈的使用大小。比如减少函数的嵌套层数，减少递归函数的使用，尽量不要在函数中使用较大的局部变量（大的对象可以从堆中开辟空间存放，因为堆会动态扩大，而线程栈的可用内存区域在线程创建时已经固定，在线程的整个生命期都无法扩展）。
为了防止一个线程栈的溢出导致整个程序退出，可以对可能产生线程栈溢出的线程体函数加异常处理，捕获在提交最后一页时抛出的溢出异常，并做相应处理。

3、访问虚拟内存时的处理流程

对某虚拟内存区域进行了预留并提交后，就可以对虚拟内存区域中数据进行访问。当程序对某段内存访问时处理流程如下：

如果数据已经在物理内存中，虚拟地址管理器只需要将指向数据的虚拟内存地址映射为物理地址，即可访问到物理内存中的数据。此时不会涉及磁盘IO，速度较快。
当第一次访问一段刚刚提交的内存中的数据时，因为并没有真正的物理内存分配，或者被访问数据以前已经被访问过，但已经被虚拟内存管理器置换出物理内存，此时会触发缺页错误。虚拟内存管理器会处理缺页错误，虚拟内存管理器会先检测数据是否在调页文件中已有备份空间（exe、dll的代码页和只读数据的备份空间不在调页文件，而是exe、dll文件），如果访问的数据在磁盘有备份空间，虚拟内存管理器需要在物理内存中找到合适的页，并将存放在磁盘的备份数据置换进物理内存。
虚拟内存管理器首先查询当前物理内存中是否有空闲页，虚拟内存管理器维护一个名称为页帧数据库（page-frame database）的数据结构，此数据结构是操作系统全局的，当Windows系统启动时被初始化，用来跟踪和记录物理内存中每一个页的状态，并用一个链表将所有空闲页连接起来，当需要空闲页时，直接查找此空闲页链表，如果有，直接使用某个空闲页；否则，根据调页算法首先选出某个页。虚拟内存管理器调页时并不是只调入一个页，为了利用局部特性，在调入包含所需数据页的同时，会将相邻的几个页一起调入内存，以提高程序效率。在选出某个内存页后，接着检查此页状态，如果此页自上次调入内存以来尚未被修改，则直接使用此页（代码页和只读页也可以直接使用）。如果此页已经被修改，则需要先将此页的内容写到磁盘的调页文件中相应的备份页，并随即将此页标记为空闲页。此时已经有一个空闲页用来存放即将要访问的数据。虚拟内存管理器会再次检测，此数据是否刚被申请的内存并且第一次被访问，如果是直接将此空闲页清0使用即可，不必从磁盘的调页文件中读取相应备份页；如果不是，则需要将磁盘调页文件中相应的备份页读到此空闲空间中，并随即将此页状态从空闲页改为活动页。
此时，数据已经在物理内存页中，通过虚拟地址映射到物理地址即可访问数据。
实际的数据访问中，情形会比较复杂，比如当用户定义了一个数组，而此数组刚好在其所在页的下边界，且此页的下一页是自由或者预留状态（非提交，没有真正的物理内存）。当程序不小心向下越界访问此数组，则首先引发缺页错误。随即虚拟内存管理器在处理缺页错误时检测到其不在调页文件中，即所谓的访问违例（access violation）。访问违例意味着要访问的地址所在的虚拟内存地址还没有被提交，即没有实际的物理存储地址与虚拟内存地址对应，访问违例会直接导致整个进程退出（crash）。
指针越界访问的后果根据运行时实际情况而有所不同，当数组并非处于其所在页的边界时，越界后还在同一页中，此时只会引起误访问（误读或误写，误读只会影响到正在执行的代码，误写则会影响其它处代码的执行），本页中的其它数据，而不会导致整个进程crash。即使数组真的存在于所在页的边界，且越界后指针值落在其相邻页，但如果此相邻页也为提交状态，此时仍然为误访问，也不会导致进程的crash。因此，同一程序的代码中存在数组指针访问越界错误，运行时有时会crash，有时不会。
MicroSoft提供了一个检测指针越界访问的工具pageheap，原理是强制使每次分配的内存都位于页的边界，同时强制页的相邻页为自由页，此时每次越界访问都会引起访问违例，导致程序crash，从而使得指针越界访问错误在开发阶段一定会暴露出来，而不会发生某个指针越界访问错误一直隐藏到发布版本，直到最终用户访问时才会被发现。

4、虚拟地址到物理地址的映射

在确保访问的数据已经在物理内存中后，还需要先将虚拟地址转换为物理地址，即地址映射，才能访问数据。
Win32通过一个两层表结构来实现地址映射，因为4GB虚拟地址空间为每个进程私有，每个进程都维护一套自己的层次结构用来实现其地址映射。第一层表为页目录（page directory），实际就是一个内存页（4KB=4096Byte），以4个字节为单元分为1024项，每一项称为页目录项（PDE，page directory entry）；第二层表为页表（page table），共有1024个页表。页目录中每一个页目录项对应一个页表，每一个页表也占一个内存页。页表的4KB也被分为1024项，每项4个字节，称为页表项（PTE，page table entry）。每一个页表项都指向物理内存中的某个页帧。

Win32提供了4GB（32bit）大小的虚拟地址空间，因此每个虚拟地址都是一个32位的整数值，由三部分组成，前10bit为页目录下标，用于定位在页目录的1024项的某一项，根据定位到的某一项的值可以找到第二层页表中的某一个页表；后续10bit为页表下标，用于定位页表的1024项中的某一项，其值可以找到物理内存中的某一个页，此页包含此虚拟地址所代表的数据；后12bit为字节下标，用于定位物理页中特定的字节位置，12位刚好可以定位一个页中的任意位置的字节。

假设在程序中访问一个指针（虚拟地址），指针值为0X2A8E317F，虚拟地址到物理地址的映射过程如下：

0X2A8E317F的二进制为0010 1010 1000 1110 0011 0001 0111 1111，将其分为三部分，前10bit为00 1010 1010，用于定位页目录中的页目录项，因为页目录项为4个字节，定位前将00 1010 1010左移2bit，得到10 1010 1000（0X2A8），使用0X2A8作为下标找到对应的页目录项，此页目录项指向一个页表。使用后续10bit即00 1110 0011定位此页表中的页表项，00 1110 0011左移2bit后为11 1000 1100（0X38B），使用0X38B作为下标找到此页表中对应的页表项。找到的页表项指向真正的内存。最后使用最后12bit即0001 0111 1111（0X17F），定位页内的数据，即为此指针指向的数据。
Win32总是假定数据已经在物理内存中，并进行地址映射。页表项中有一位用于标记包含此数据的页是否在物理内存页中，当取得页表项时，检测此位，如果在，进行地址映射；如果不在，抛出缺页错误，此时此页表项中包含了此数据是否在调页文件中，如果不在，则访问违例；如果在，此页表项可以查出此数据页是否在调页文件中，以及此数据页在调页文件中的起始位置，然后将此数据页从磁盘中调入物理内存中，再继续进行地址映射过程。为了实现虚拟地址空间各进程私有，每个进程都有自己的页目录项和页表结构，对不同进程而言，页目录中的页目录项，以及页表中的页表项都是不同的，因此相同的指针（虚拟地址）被不同的进程映射到的物理地址也是不同的，即不同进程间传递指针是没有意义的。

5、虚拟内存空间使用状态记录

Win32虚拟内存管理器使用另一个数据结构来记录和维护每个进程的4GB虚拟地址空间的使用及状态信息，即虚拟地址描述符树（VAD，Virtua Address Discriptor）。每一个进程都有自己的VAD集合，VAD集合被组织成一个自平衡二叉树，以提高查找的效率。另外由于只有预留或提交的内存块才会有VAD，自由的内存块没有VAD（即不在VAD树结构中的虚拟地址块就是自由的）。
（1）当程序申请一块新内存时，虚拟内存管理器执行访问VAD，找到两个相邻VAD，只要小的VAD的上限与大的VAD的下限之间的差值满足所申请的内存块的大小需求，即可使用二者之间的虚拟内存。
（2）当第一访问提交的内存时，虚拟内存管理器总是假定要访问的数据所在数据页已经在物理内存中，并进行虚拟地址到物理地址映射。当找到相应的页目录项后发现页目录项并没有指向一个合法的页表，虚拟内存管理器就会查找进程的VAD树，找到包含该地址的VAD，并根据VAD中的信息，比如内存块大小、范围，以及在调页文件中的起始位置，随需生成相应的页表项。然后从刚才发生缺页错误的位置继续进行地址映射。因此，一个虚拟内存页被提交时，除了在调页文件中开辟一个备份页外，不会生成指向它的页表项的页表，也不会填充指向它的页表项，更不会开辟真正的物理内存页，而是直到第一次访问提交页时才会随需地从VAD中取得包含该页的整个区域的信息，生成相应页表，并填充相应页的页表项。
（3）当能够访问预留的内存时，虚拟地址管理器进行虚拟地址到物理地址的映射，找到相应的页目录项后发现页目录项并没有指向一个合法的页表，虚拟地址管理器就会查找进程的VAD树，找到包含该地址的VAD，此时发现此段内存块只是预留的，而没有提交，即没有对应物理内存，直接抛出访问违例，进程退出。
（4）当访问自由的内存时，虚拟地址内存管理器进行虚拟地址到物理地址的映射，找到相应的页目录项后发现页目录项并没有指向一个合法的页表，虚拟地址管理器就会查找进程的VAD树，发现并没有VAD包含此虚拟地址，发现此虚拟地址所在的虚拟内存页是自由状态，直接抛出访问违例，进程退出。

6、进程工作集

因为频繁的调页操作引起的磁盘IO会大大降低程序的运行效率，因此对每一个进程，虚拟内存管理器都会将一定量的内存页驻留在物理内存中，并跟踪其执行的性能指标，并动态调整驻留的内存页数量。Win32中驻留在物理内存中的内存页称为进程的工作集（working set），进程的工作集可以通过任务管理器查看，内存使用列即为工作集大小。
工作集是会动态变化的，进程初始时只有很少的代码页和数据页被调入物理内存。当执行到未被调入内存的代码或访问到尚未调入内存的数据时，相应代码页或数据页会被调入物理内存，工作集也会随之增加。但工作集不能无限增加，系统为每个进程设定了一个最小工作集和最大工作集，当工作集达到最大工作集大小，进程需要再次调入新页到物理内存时，虚拟内存管理器会架构原来工作集中某些内存页先置换出物理内存，然后再将需要调入的新页调入内存。
因为工作集的页驻留在物理内存中，对工作集页的访问不会涉及磁盘IO，因此速度非常快。如果访问的代码或数据不在工作集中，会引发额外的磁盘IO，从而降低程序的执行效率。极端情况下会出现所谓的颠簸或抖动（thrashing），即程序的大部分执行时间都花在调页操作上，而不是执行代码上。
虚拟内存管理器在调页时，不仅仅只是调入需要的页，同时还将其附近的页一起调入内存中，对于开发人员，如果要提高程序的运行效率需要考虑如下：
（1）对代码李硕，尽量编写紧凑代码，最理想情形是工作集不会达到最大阈值，在每次调入新页时，就不需要置换已经载入的内存页，因为根据locality特性，以前执行的代码和访问的数据在后面有很大可能会被再次执行好访问，因此程序执行时，缺页错误会大大降低，即减少磁盘IO。从进程任务管理器也可以查看一个进程从开始时到当前时刻共发生的缺页错误次数。即使不能达到理想情形，紧凑的代码往往意味着接下来执行的代码更大可能就在当前页或相邻页。根据时间locality特性，程序80%的时间花费在20%代码上，如果能将耗时的20%代码尽量紧凑且排在一起，会大大提高程序的整体性能。
（2）对数据来说，尽量将那些会一起访问的数据（如链表）放在一起，当访问数据时，数据在同一页或相邻页，只需要一次调页操作就可以完成。如果数据分散在分散在多个页（多个页不相邻），每次对数据的整体访问都会引发大量的缺页错误，从而降低性能。利用Win32提供的预留和提交两步机制，可以为一同访问的数据预留一大块空间，此时并没有分配实际存储空间，而是在后续执行过程中生成数据时格局需要提交内存，既不浪费存储空间（物理内存和磁盘的调页文件存储空间），又能利用locality特性。

三、Linux内存管理

1、Linux内存管理机制简介

Linux的内存管理主要分为两部分，一部分负责物理内存的申请与释放，物理内存的申请与释放的最小单位为页，在IA32中，页的大小为4KB；另一部分负责处理虚拟内存，虚拟内存的主要操作包括虚拟地址空间与物理地址空间的映射，物理内存页与磁盘页之间的置换等。

2、Linux进程的内存布局

一个32位Linux进程的地址空间为4GB，其中高位1GB，即0XC0000000--0XFFFFFFFF，为内核空间，低位3GB，即0X00000000--0XBFFFFFFF为用户地址空间。用户地址空间进一步被分为程序代码区、数据区（包括初始化数据区DATA和未初始化数据区BSS）、堆和栈。程序代码区占据最低端，往上是初始化数据区DATA和未初始化数据区BSS。代码区存放应用程序的机器代码，运行过程中代码不能修改，因此代码区内存为只读，且大小固定。数据区中存放应用程序的全局数据，静态数据和常量字符串，数据区大小也是固定的。
堆从未初始化数据区开始，向上端动态增长，增长过程中虚拟地址值变大；栈从高位地址开始，向下动态增长，虚拟地址值变小。
堆是应用程序在运行过程中动态申请的内存空间，如通过malloc/new动态生成对象或开辟内存空间时，最终会调用系统调用brk来动态调整数据区的大小。当申请的动态内存区域使用完毕，需要开发者明确使用相应的free/delete对申请的动态内存空间进行释放，free/delete最终也会使用brk系统调用调整数据区的大小。
栈是用来存放函数的传入参数、临时变量以及返回地址等数据，不需要通过malloc/new开辟空间，栈的增长与缩减是因为函数的调用与返回，不需要开发人员操作，没有内存泄漏的危险。
初始化数据区存放的是编译期就能够知道由程序设定初始值的全局变量及静态变量等，其初始值必须保存在最终生成的二进制文件中，并且在程序运行时会原封不动地将此区域映射到进程的初始化数据区。如果一个全局变量或静态变量在源代码中没有被赋初始值，在程序启动后，在第一次被赋值前，其初始值为0，本质上是有初始值的，其初始值为0。但当最终生成二进制文件时，未初始化数据区不会占据对应变量总大小的区域，而是只用一个值进行标识其未初始化数据区的总大小。如一个程序的代码指令有100KB，所有初始化数据总大小为100KB，所有未初始化数据总大小为150KB，则在最终生成的二进制文件中代码区有100KB，接着是100KB的初始化数据区，然后是4字节的大小空间，用于标记未初始化数据区大小，其值为150X1024，用于节省磁盘空间。但在进程虚拟地址空间中，对应未初始化数据区的大小必须是150KB，因为在程序运行时，程序必须真正能够访问到变量中的每一个，即当程序启动时，当检测到二进制文件中未初始化数据区的值为150X1024，则系统会开辟出150KB大小的区域作为进程的未初始化数据区并同时使用0对其进行初始化。

3、Linux物理内存管理

物理内存是用来存放代码指令与供代码指令操作的数据的最终场所，因此物理内存的管理是内存管理系统极其重要的任务。Linux使用页分配器（page allocator）来管理物理内存，页分配器负责分配和回收所有的物理内存页（物理内存的分配与回收的最小单位为4KB大小的页）。
页分配器的核心算法称为兄弟堆算法（buddy-heap algorithm），算法思想是每个物理内存区域都会有一个与之相邻的所谓兄弟区域，当两个区域被回收后，会被合并成为一个区域。如果被合并区域的相邻区域也被回收后，会被进一步合并为更大的区域。当有物理内存请求到来时，页分配器会首先检测是否有大小与之一致的区域。如果有，直接使用找到的匹配区域满足请求；如果没有，则找到更大的一个区域，并继续划分，直到分出的区域能够满足请求。为了配合兄弟堆算法，必须有链表来记录自由的物理内存区域，对于每个相同大小的自由区域，会有一个链表将其连接，每种大小的区域都会有一个链表对其进行管理。自由区域的大小都是2的幂。
当有一个8KB大小的内存请求到来，当前最小可供分配的区域为64KB，此时64KB会被划分为两个32KB，继而将低位的32KB继续划分为两个16KB大小的区域，再将最低位的16KB大小区域划分为两个8KB大小的区域，然后分配高位的8KB区域满足请求。

4、Linux虚拟内存管理

虚拟内存管理器的主要任务是维护应用程序的虚拟地址空间使用信息，如哪些区域已经被使用（映射），是否有磁盘文件作为备份存储。如果有，每个区域对应在磁盘的哪个区域，另外一个重要功能就是调页，如程序访问某些尚未调至物理内存的数据时，虚拟内存管理器负责定位数据，并将其置换进物理内存。如果物理内存此时没有自由页，还需要将物理内存中的某些页先置换出去。
用来维护应用程序的虚拟地址空间使用信息的数据结构是vm_area_struct。每个vm_area_struct结构体都描述了一个进程虚拟地址空间中被分配的区域，当vm_area_struct个数不超过32个时，被连接成为一个链表；当超过32个时，所有的vm_area_struct会被组织为一棵自平衡二叉树，利于提高查询速度。当程序通过某个指针访问某个数据时，系统会查询vm_area_struct树，如果发现指针没有落在任何一个vm_area_struct所表示的区域内，则判定指针所代表的地址没有被分配，即非法的指针访问。

5、虚拟地址映射为物理地址

当通过程序的指针访问某个数据时，因为指针本质是一个虚拟地址值，因此虚拟地址值必须被转化为物理地址值，才能真正访问其所指代的数据。
Linux使用三层映射策略将一个虚拟地址映射为一个物理地址。与Windows相比，多了Middle层，当对于IA32体系，Middle层没有用，因此Linux与Windows相同。