Linux 内存管理

计算机系统中有几类存储设备：cache、内存、外存。

      程序到运行主要经过程序（外存）编译，链接，装入(内存)。《程序如何运行：编译、链接、装》:

      外存，如硬盘、软盘、光盘等，其容量大、成本低，但存取速度更低，对硬盘的存取速度至少比对内存的存取速度慢4个数量级，而且，CPU不能直接访问外存，对外存的访问必须通过内存。就一般的计算机系统而言，其存储设备是一个塔型结构，高速cache最少、内存次之、外存最大。在计算机的整个存储系统中，内存起到了承上启下的作用。 

      内存，又称主存或物理内存，是可以随机访问的存储器，其存取速度比高速cache低，对内存的访问需要几倍的CPU周期，因此其代价也比cache低，容量也可以做得比较大（从M到G） 。

       cache的存取速度最高，可以和CPU匹配，因此其代价最高，容量也最小。

      操作系统内存管理包括物理内存管理和虚拟内存管理：

      我们这篇主要介绍Linux的虚拟内存管理。物理内存管理在另外一篇：《操作系统内存管理(思维导图详解)》

      1、程序的进程在内存的数据结构

 一.Linux 进程在内存数据结构

1、存储（没有调入内存）阶段：

      可以看到一个可执行程序在存储（没有调入内存）时分为代码段，数据段，未初始化数据段三部分：

   1) 代码段：存放CPU执行的机器指令。通常代码区是共享的，即其它执行程序可调用它。假如机器中有数个进程运行相同的一个程序，那么它们就可以使用同一个代码段。

   2) 数据段：存放已初始化的全局变量，静态变量（包括全局和局部的），常量。static全局变量和static函数只能在当前文件中被调用。

    3) 未初始化数据区（uninitializeddata segment,BSS)：存放全局未初始化的变量。BSS的数据在程序开始执行之前被初始化为0或NULL。

      代码区所在的地址空间最低，往上依次是数据区和BSS区，并且数据区和BSS区在内存中是紧挨着的。。

2、运行阶段：

     可执行程序在运行时又多出了两个区域：栈段（Stack）和堆段(Heap)。

4) 栈区:由编译器自动释放，存放函数的参数值，局部变量等。每当一个函数被调用时，该函数的返回类型和一些调用的信息被存储到栈中。然后这个被调用的函数再为它的自动变量和临时变量在栈上分配空间。每调用一个函数一个新的栈就会被使用。栈区是从高地址位向低地址位增长的，是一块连续的内在区域，最大容量是由系统预先定义好的，申请的栈空间超过这个界限时会提示溢出，用户能从栈中获取的空间较小。

 5) 堆段:用于存放进程运行中被动态分配的内存段，位于BSS和栈中间的地址位。由程序员申请分配（malloc)和释放（free）。堆是从低地址位向高地址位增长，采用链式存储结构。频繁地malloc/free造成内存空间的不连续，产生碎片。当申请堆空间时库函数按照一定的算法搜索可用的足够大的空间。因此堆的效率比栈要低的多。

      这个5中内存区域中数据段、BSS和堆通常是被连续存储的——内存位置上是连续的，而代码段和栈往往会被独立存放。有趣的是堆和栈两个区域关系很“暧昧”，他们一个向下“长”（i386体系结构中栈向下、堆向上），一个向上“长”，相对而生。但你不必担心他们会碰头，因为他们之间间隔很大（到底大到多少，你可以从下面的例子程序计算一下），绝少有机会能碰到一起。

下图简要描述了进程内存区域的分布：

二. 地址相关概念

在讲地址转换之前，我们先介绍地址相关概念：

1. 物理地址(physical address)

物理内存，真实存在的插在主板内存槽上的内存条的容量的大小.

      内存是由若干个存储单元组成的，每个存储单元有一个编号，这种编号可唯一标识一个存储单元，称为内存地址（或物理地址）。我们可以把内存看成一个从0字节一直到内存最大容量逐字节编号的存储单元数组，即每个存储单元与内存地址的编号相对应。

2. 虚拟内存(Virtual memory)(也叫虚拟存储器)

虚拟内存地址就是每个进程可以直接寻址的地址空间，不受其他进程干扰。每个指令或数据单元都在这个虚拟空间中拥有确定的地址。      

虚拟内存就是进程中的目标代码，数据等虚拟地址组成的虚拟空间     

      虚拟内存不考虑物理内存的大小和信息存放的实际位置，只规定进程中相互关联信息的相对位置。每个进程都拥有自己的虚拟内存，且虚拟内存的大小由处理机的地址结构和寻址方式决定。

       如直接寻址，如果cpu的有效地址长度为16位，则其寻址范围0 -64k。

       再比如32位机器可以直接寻址4G空间，意思是每个应用程序都有4G内存空间可用。但是显然机器内存罕有如此之大，可以支持每个程序使用4G内存的。

虚拟内存与物理内存的区别：虚拟内存就与物理内存相反，是指根据系统需要从硬盘虚拟地匀出来的内存空间，是一种计算机系统内存管理技术，属于计算机程序，而物理内存为硬件。因为有时候当你处理大的程序时候系统内存不够用，此时就会把硬盘当内存来使用，来交换数据做缓存区，不过物理内存的处理速度是虚拟内存的30倍以上。

3. 逻辑地址(logical address)

        源程序经过汇编或编译后，形成目标代码，每个目标代码都是以0为基址顺序进行编址的，原来用符号名访问的单元用具体的数据——单元号取代。这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。

       在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。即应用程序中使用的地址。要经过寻址方式的计算或变换才得到内存中的物理地址。

       很简单，逻辑地址就是你源程序里使用的地址，或者源代码经过编译以后编译器将一些标号，变量转换成的地址，或者相对于当前段的偏移地址。

逻辑地址是指由程序产生的与段相关的偏移地址部分。例如，你在进行C语言指针编程中，可以读取指针变量本身值(&操作)，实际上这个值就是逻辑地址，它是相对于你当前进程数据段的地址，不和绝对物理地址相干。只有在Intel实模式下，逻辑地址才和物理地址相等（因为实模式没有分段或分页机制,Cpu不进行自动地址转换）；逻辑也就是在Intel保护模式下程序执行代码段限长内的偏移地址（假定代码段、数据段如果完全一样）。应用程序员仅需与逻辑地址打交道，而分段和分页机制对您来说是完全透明的，仅由系统编程人员涉及。应用程序员虽然自己可以直接操作内存，那也只能在操作系统给你分配的内存段操作。

不过有些资料是直接把逻辑地址当成虚拟地址，两者并没有明确的界限。

    在linux内核，虚拟地址是3G－4G这段地址，它与物理地址通过页表来映射，逻辑地址是指3G－3G＋main_memory_size这段虚拟地址，它与物理地址的映射是线性的，当然也可以通过页表映射。所以逻辑地址是虚拟地址的一部分。

        逻辑地址的组成：是由一个段标识符加上一个指定段内相对地址的偏移量，表示为 段标识符：段内偏移量

                      图4.1  作业的名空间、逻辑地址空间和装入后的物理空间

4. 线性地址或Linux下也叫虚拟地址(virtual address)

这个地址很重要，也很不容易理解。分段机制下CPU寻址是二维的地址即，段地址：偏移地址，CPU不可能认识二维地址，因此需要转化成一维地址即，段地址*16+偏移地址，这样得到的地址便是线性地址（在未开启分页机制的情况下也是物理地址）。这样有什么意义呢？或者说这个一维地址的计算方法随便一个学计算机的人都知道，但是你真的理解它的意思吗？要想理解它的意思，必须要知道什么是地址空间，下文详述。

       线性地址是逻辑地址到物理地址变换之间的中间层。程序代码会产生逻辑地址，或者说是段中的偏移地址，加上相应段的基地址就生成了一个线性地址。如果启用了分页机制，那么线性地址可以再经变换以产生一个物理地址。若没有启用分页机制，那么线性地址直接就是物理地址。Intel 80386的线性地址空间容量为4G（2的32次方即32根地址总线寻址）。

       跟逻辑地址类似，它也是一个不真实的地址，如果逻辑地址是对应的硬件平台段式管理转换前地址的话，那么线性地址则对应了硬件页式内存的转换前地址。

       CPU将一个虚拟内存空间中的地址转换为物理地址，需要进行两步：首先将给定一个逻辑地址（其实是段内偏移量=），CPU要利用其段式内存管理单元，先将为个逻辑地址转换成一个线程地址，再利用其页式内存管理单元，转换为最终物理地址。

三.地址映射

          由 I NTEL公 司 推 出 的 32 位 80386 芯 片 的 工 作 模 式 包 括  实地址模式和虚地址模式 。 实地址模式与8086 完全兼容 ． 它的  寻址范围是1 MB的地址空间． 分段功能受到限制 ．不能区分 特权级 ． 当然分页机制也不能启用 。 在虚地址模式下． 分段机  制得到加强 ． 段最大可达4GB． 并且提供段 内分页管理机制 ．   为 Linux虚拟内存管理机制提供了支持 。  

     80386 的虚拟地址模式使用了如下分段和分页两级地址  转换机制来实现虚拟地址向物理地址的转换 。

3 .1   虚拟地址向线性地址的转换 

        用户进程要访问的虚拟地址包括一个1 6 位的段选择器和 一个32 位的段 内偏移 ． 80386 的分段机制将段寄存器中所装的 

段选择器和32 位段 内偏移量相加． 得到32位的线性地址 ， 如图1所示 ， 16 位的段选择器最低两位表示请求者的特权级 ， 那么 

最多可以有16k个段 ， 每段的最大尺寸为4GB。 但是它们都必 须被映射到4GB的线性地址空间。 

                                  图1

3 .2 线性地址向物理地址的转换 

       Linux的每个用 户进 程都可 以访 问4 GB的线 性地址空间， 而实际的物理 内存可能远 远少于4GB． 采用分页机制 。   Linux仅把可执行映像的一小部分 装入物理 内存． 当需要访问未装入的页面时 ． 系统产生一个缺页中断 ， 把需要的页读入 物理内存。 

图2

       Linux采用两级页表结构—— 页目录表和页表实现地址 映射． 当前正在运行进程的页 目录表的地址被保存在控制寄 

存器 CR3 中。  由上面转换机制所得到的线性地址可以分为3 部分 ， 高 10位是 DI R域—— 页 目录表的索引值 ． 它与 CR3 中的地址一起 计算得到页表的物理地址 ． 中间1O位保 存相对于页表的索引 值 ． 通过它得到所需的物理页号。 物理页号与低1 2 位页内偏移 组合得到物理地址 。 其结构如图2 所示 。  

四.虚拟地址管理

每个用户进程都可以有4 GB的虚存空 间． 为了更好地管 理这部分虚存空间．Linux主要定义了如下三个数据结构 ：  

struct   vm_area_struct ，

struct   vm_operations_struct

struct    vmm_struct  

       虚存段( vm_area_struct ) ． 简称 vma是某个进程的一段 连续的虚存空间． 一个进程通常占用几个vma段 ． 例如代码段 、 数据段、 堆栈段等 。 vma不仅可以代表一段内存区间， 也可 以对应于一个文件、 共享内存或者对换设备。 

       每一个进程的所有vma由一个双向链表管理。 为了提高对vma的查询、 插入、 删除等操作的效率 ．Linux把系统中所 有进程的 vma组成了一棵 AVL树。 这是一棵平衡二叉树 ． 当 vma数量特别 大时。 利用这棵 AVL树查找 v ma的效率得到 明显提 高 。  

        不同的 vma可能需要不同的操作处理方式 ． 但同时考虑到统接口的统 一 性 ． Linux采 用vm_operations_struct结 构和面向对象的思想来定义操作方式 ． 一个vm_operations_struct结构体是一组 函数指针 ， 对于不同的 vma ． 它可能指向 不同的处理 函数．例如当发生缺页错误时 ． 共 享内存和代码 段 的 readpage所 指 向的页面读入函数可能就不同 。  

        内存管理中另外 一个 非 常重要的数 据 结 构是vmm_struct 结构体 ．进程 的 task_struct中的mm成员指向 它． 当前运行进程的整个虚拟空间都 由它来管理和描述 ． 它不仅包含该进程的映像信 息． 而且它的 mma p成员项指向该进 程所有vma组成的链 表 。 它的 mmap_avl 成 员 项 指 向整个系统 的 AVL树 。  

        这三个数据结构之间相互关联． 共同管理虚拟内存 ． 它们之 间的 关 系如图 3所 示 。  

图 3

        这部分相关的系统调用主要有如下两个 ：  

do_mmap( 
struct   file *file,
unsigned   long   addr
unsigned   long   len , 
unsigned   long   prot ,
unsigned   long   flags ,
unsigned   long   off 
);  
find_vma ( 
struct   mm_struct mm ,
unsigned   long   addr
)； 

      do _mmap函数实现了 内存映射 。 find_vma函数的功能 是找到包含参数 addr指定的虚拟地址所属的 vma 。  当要运行一个可执行映像时 ． 调用   do _mmap将其装入 到该进程 的虚拟地址空间 ． 并且产生一组 vma结构 ． 如前所 述该进程的整个虚拟空间由  vm m_struct  结构管理 ． 但是此时 可执行文件仅仅被连接到进程的虚拟空间中． 只有一小部分 页面被装入到物理 内存 ． 其余大部分并没有被真正装入到物 理内存 ． 在进程的运行过程 中． 产生缺页错误 ． 操作 系统首先调用 find_vma． 找到该虚拟地 址所在的 vma ． 然后根据该 vma的成员变量 vm_ops指向的 vm_ operations_struct结构 中的缺页操作 函数。 把页装入物理内存。   ·  

五.swap对换空间

     32位Linux系统的每个进程可以有4 GB的虚拟 内存空间 ． 而且系统中还要同时存在多个进程 ，但是 ，事实上大多数计算机都没有这么多物理内存空间 ， 当系统中的物理内存紧缺时 ． 就需要利用对换空间把一部分未来可能不用的页面从物理内存中移 到对换设备或对换文件中。  

       Linux采用两种方式保存换出的页面 ：

       一种是利用整个块设备 ， 如硬盘的一个分区 ． 即对换设备， 

       另一种是利用文件系统中固定长度的文件 ． 即对换文件。 它们统称为对换空间。 

       这两种方式的相同之处是它们的内部格式一致． 但是在执行效率方面 ． 对换设备要好一些． 这是因为对换设备上同一页面 的数据块是连续存放的 ． 故而可以顺序存取 ， 而在对换文件中 。 同一页面的数据块实际的物理位置可能是不连续的 ． 需要通过对换文件的 inode检索． 这就降低了存取效率 。  

        每个对换文件或对换设备 由 struct   swap — info — struct 结构来描述。 有关对换设备的 函数主要是 get — swap — page ( …) ．    当内存中的页面需要被换出时 ． 调用 get — swap —page函数 申请得到一个对换空间中的物理页面 。 如果成功， 就返 回一个非零代 码 ． 否则返 回0。  

六.分页机制管理

         Linux使用分页管理机制来更加有效地利用物理内存．当创建一个进程时．仅仅把当前进程的一小部分真正装入内

存．其余部分需要访问时．处理器产生一个页故障．由缺页中断服务程序根据缺页虚拟地址和出错码调用写拷贝函数do—wp—page、此地址所属的vma的vm—ops指向的nopage、do—swap—page．swap—in等函数将需要的页换入物理内存。随着可执行映像的运行和页面的换入．系统中的内存有可能变得不足．这时Linux核心就必须调用kswapd守护进程释放部分物理内存。kswapd在系统启动时由init进程建立。在系统的运行过程中。它被定期唤醒。检查系统中的空闲物理内存是否很少。如果是．则释放一部分内存．或者将一些页面换出到对换空间。然后继续睡眠。

kswapd 守护进程负责确保内存保持可用空闲空间。它监测内核中的 pages_high 和pages_low 标记，如果空闲内存空间值小于 pages_low 值， kswwapd 进程开始扫描并尝试每次回收 32 个页面，如此重复直至空闲内存空间大于 pages_high 值。
        kswapd 进程履行以下操作：
        * 假如页面未改变，它将该页面放入 free list。
        * 假如页面发生改变且被文件系统回写，它将页面内容写入磁盘。
        * 假如页面发生改变且未被文件系统回写（无名页） ，它将页面内容写入 swap 设备。

缺页中断和页面换入

      页面换入主要由缺页中断服务入口函数do—page—fault来实现。当系统中产生页面故障时．如果虚拟内存地址有效．则产生错误的原因有如下两种：

         虚拟内存地址对应的物理页不在内存中。那么它必然在磁盘或对换空间中．如果在磁盘上．那么我们调用do—nO—

page函数．而do—no—page调用vma一>vm—ops一>nopage()函数建立页面映射．从对换空间或磁盘中调入页面．或者通过do—swap—page()函数调用swap—in()来换入页面。

·

          该虚拟地址对应的物理页在内存。但是被写保护．如果这种情况发生在一个共享页面上．则需要“写拷贝“函数do—

wp—page来换入页面．do—wp—page函数首先调用一get—free—page获得一新页面．然后调用copy—COW—page拷贝页面的内容．当然还要调用相应的刷新函数刷新TLB和缓存等。

页交换进程和页面换出

            正如我们上面所描述的．系统使用kswapd守护进程来定期地换出页面。使系统中有足够的空闲物理内存页。

kswapd进程定期地检查系统中的空闲页面数．如果少于一定值．则按照以下三中途径获得空闲页面：

           ①减少缓冲区和页面高速缓存的大小；

           ②把共享内存占用的页面置换到对换空间；

           ③换出或丢弃物理内存页。

七、缺页中断具体说明

1、缺页中断定义：

现代操作系统通过虚拟内存技术来扩大物理内存，虚拟内存每一页都映射在物理内存或磁盘上所以虚拟内存会比物理内存大，程序里访问的是虚拟地址，当程序访问页映射在磁盘上时，就会发生缺页中断，调用中断处理程序将页载入物理内存。例如：32位Linux的每个用户进程都可以访问4GB的线性地址空间， 而实际的物理内存可能远远少于4GB． 采用分页机制 ，Linux仅把可执行映像的一小部分装入物理内存． 当需要访问未装入的页面时 ． 系统产生一个缺页中断， 把需要的页读入物理内存。

缺页中断：即指的是当应用程序试图访问已映射在虚拟地址空间中，但是并未被加载在物理内存中的一个分页时，产生一个页不存在的中断，需要操作系统将其调入物理内存后再进行访问。在这个时候，被内存映射的文件（映像）实际上成了一个分页交换文件。

名为“缺页中断”或者“页缺失”错误，但实际上这并不一定是一种错误。而且这一机制对于利用虚拟内存来增加程序可用内存空间的操作系统。

2、缺页中断的次数

中断次数=进程的物理块数+页面置换次数。

缺页中断率=（缺页中断次数 / 总访问页数 ）

3、页面置换算法

当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

几种缺页中断算法（FIFO，LRU与LFU）的实现过程：

在分页虚拟存储管理的系统中，有一用户进程，它依次要访问的页面序列是序列7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1。 假定分配给该进程的页数（物理块）为3且进程初始时未装载页面（意思就是进程只能使用三块内存）。计算缺页次数和缺页率？那么采用FIFO、LRU、OPT调度算法产生的缺页中断数各为多少？缺页中断率各为多少？ 

1)、先进先出（FIFO）

优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

利用FIFO置换算法时的置换图：

进程访问页面2时，把最早进入内存的页面7换出。然后访问页面3时，再把2, 0, 1中最先进入内存的页换出。由图可以看出，利用FIFO算法时进行了 12次页面置换。发生缺页中断的次数为15。

2)、最近最久未使用(LRU)置换算法

选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。

对上面的实例釆用LRU算法进行页面置换，如图所示。进程第一次对页面2访问时，将最近最久未被访问的页面7置换出去。然后访问页面3时，将最近最久未使用的页面1换出。

3). 最佳置换算法(OPT)

最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。

对上面的实例釆用OPT算法进行页面置换，如图所示：

进程运行时，先将7, 0, 1三个页面依次装入内存。进程要访问页面2时，产生缺页中断，根据最佳置换算法，选择第18次访问才需调入的页面7予以淘汰。然后，访问页面0时，因为已在内存中所以不必产生缺页中断。访问页面3时又会根据最佳置换算法将页面1淘汰……依此类推，如图所示。从图中可以看出釆用最佳置换算法时的情况。

可以看到，发生缺页中断的次数为9，页面置换的次数为6。