## 理解内存
明天就要回家过年了，回家之前翻译了一篇比较基础的文章，英文太烂，各位看官见笑了。[原文地址](http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/mem.html)

---

这篇文章讨论基于的环境是AICT Linux集群，运行64位的GNU / Linux的AMD Opteron处理器。
###内容
* 简介
* 程序和进程
* 存储类别和作用域
* 程序大小
* 内存映射
* 调用堆栈
* 页表
* 库
* 内存限制
* 内存分配
* 实现细节
* 参考文献

-----
###简介
在Linux下，所有的程序都在虚拟内存环境中运行。如果有某个C程序员将指针的值打印出来（在实践中从来没有必要），其结果将是一个虚拟内存地址。在Fortran里，虽然指针不是标准的特性，但虚拟内存寻址隐含在每个变量和每次子程序调用中。

当然，一个程序的代码和数据实际是驻留在物理内存当中的。因此，每一个虚拟内存地址都会被操作系统通过一个叫做```页表```（参看图1）的数据结构映射成物理内存地址。因此，比如取回或更新一个变量的值时，程序必须首先通过查找页表得到该变量的那个和虚拟内存地址关联的实际内存地址。幸运的是，对于用户来说，这个过程通过Linux的处理是透明的。高度优化的Linux内核和CPU中的专用电路使得这个过程合理而且高效。然而，你可能很像知道为什么这么做。

![图1 通过页表将虚拟内存映射成物理内存][1]

在一个通用的多用户计算环境中，例如Linux，所有的程序必定是共享有限的可用物理内存的。在没有虚拟内存的环境中，每个程序势必要了解其他程序的活动状况。例如，考虑在直接内存访问的情况下，两个相互独立的程序同时申请同一块可用的物理内存。为了避免冲突，两个程序之间必须进行同步协作，这会导致非常复杂的编码。相反，在虚拟内存的机制下，所有底层的内存管理都委托给了操作系统。从而，在Linux内核中**为每个程序维护了一个页表**，给人一种计算机上每个程序都是独立的假象。当两个并发的程序引用相同的虚拟内存地址的时候，内核保证了它们实际上解析的是不同的物理内存地址，如图2所示。

![图2 并发程序][2]

这个图也可以帮助我们理解虚拟内存作为一个抽象层，操作系统是如何用它来隔离作为硬件的存储器。
所有程序都是简单的运行在这个抽象的顶层而无需知道底层内存管理实现的细节。
我们将会在下面的章节渐渐熟悉虚拟内存相关的概念和术语。虽然我们关注的是AICT集群，但是所描述的原则在绝大多数其他的计算环境中都是适用的。

###程序和进程
一个程序的页表是其执行上下文的一个组成部分。其他部分包括当前的工作目录，打开的句柄列表，环境变量等等。所有部分在一起组成了我们所知道的```进程（process）```或```任务(Task)```。

通常“进程”和“程序”可以互换着使用。但是它们之间有很大的区别。“程序”这个术语通常结合着特定语言写的源码来用的，比如我们经常说的Fortran或C语言。也可以用来指存储在磁盘上的编译过后的源码或可执行文件。一个进程，从操作系统的角度是特指正在运行的程序。

内核给每个进程都赋予一个唯一的标识数字，```进程ID```，用来索引存储了进程相关信息的数据结构。程序可以通过编程接口获得它的进程ID以及其他相关的数据。这个接口在C语言里是标准，在Fortran是作为扩展来支持的。例如，```getuid()```会返回调用进程的用户ID（uid）[3]。

在shell命令行和程序进行交互是创建一个新进程的常用方法。新的进程是在字面上或通过forked（通过```fork()```这个系统调用）从shell进程催生的。通过这种方式，一个进程的继承层次便出现了，shell进程作为父进程，新产生的作为子进程。自然的，子进程从父进程那里继承了很多属性，像当前的工作目录，环境变量等。格外重要的是，内存资源上面的限制也会从父进程那里继承过来，后面会详细的说到这点。

###存储类别和作用域

程序的组成包括可执行的语句和数据申明。每一个数据单元都有其```存储类别（strage class）```这一属性用来反映它在程序执行期间的生命周期。与之相关联的另外一个属性叫做```作用域（scope）```，用来表征数据的可见性程度。存储类别和作用域是通过数据申明所在的位置来确定的，同时确定了它在虚拟内存中的位置。

在C语言中，任何函数体外申明的变量的作用域都是全局的，拥有静态（永久）的有效期。虽然初始化的时候可以赋值，但全局变量通常是未初始化的。同时，在方法体内包括```main()```，申明的变量拥有局部作用域和自动（临时）的有效期。一个局部的变量可以通过static修饰符申明为永久的，因此它可以保存方法调用过程中的值。

在Fortran中，所有的变量都只有局部作用域，除非申明在模块或命名的公共块中。

###程序的大小
编译器将程序的可执行语句翻译成CPU指令，将静态的数据翻译成特定机器的数据规格。为了产生一个可执行文件，系统链接器将指令和数据聚合在不同的段中。所有的CPU指令被放在一个叫做```text```段中，不幸的是，这个名字给人的感觉它包含的是程序的源代码，但其实不是。同时，数据被分成了两个段，一个叫做```data```，包括初始化的静态变量和字面常量，另外一个叫做```bss```，包括未初始化的静态变量。Bss曾经也用来表示“***block started from symbol***”，这是一种大型机汇编语言指令，这个术语在今天已经没有任何意义。

考虑下面这段C语言程序，与之相当的是用Fortran90/95版本写的，它主要的组成部分是一个200W的静态数组。

``` c
/**
  * simple.c
  */
#include 
#include 

#define NSIZE 200000000

char x[NSIZE];

int
main (void)
{
  for (int i=0; i<NSIZE; i++)
    x[i] = ‘x‘;

  printf ("done\n");
  
  exit (EXIT_SUCCESS);
}
```
```shell
$ pgcc -c9x -o simple simple.c
$ size simple
   text    data    bss         dec         hex       filename
   1226    560     200000032   200001818   bebc91a   simple
   
$ ls -l simple
-rwxr-xr-x  1 esumbar uofa 7114 Nov 15 14:12 simple
```

```Fortran
!
! simple.f90
!
module globals
  implicit none
  integer, parameter :: NMAX = 200000000
  character(1), save :: x(NMAX)
end module globals

program simple
  use globals
  implicit none
  integer :: i

  do i = 1, NMAX
     x(i) = ‘x‘
  end do
  print*, "done"
  stop
end program simple
```

```shell
$ pgf95 -o simple simple.f90
$ size simple
   text    data    bss         dec         hex       filename
   77727   1088772 200003752   201170251   bfd9d4b   simple
   
$ ls -l simple
-rwxr-xr-x  1 esumbar uofa 1201694 Nov 15 14:12 simple

$ file simple
simple: ELF 64-bit LSB executable, AMD x86-64, ...
```
编译（隐含链接的过程）产生如上图所示的```ELF```（Executable and Linking Format）可执行程序文件。运行```size```命令来查看ELF文件中```text```,```data```,```bss```段的大小。

在两种情况下，```bss```段的大小都的确有200万字节（加上一些额外的管理开销）。从源程序中看实际贡献给```data```段的只有两个字符字面常量和一个数值型常量，这跟上面打印出的结果都相去甚远，显然，这是编译器做的手脚。

此外，因为ELF包含了所有程序的指令和所有初始化的数据，所以```text```段和```data```段大小总和会很接近但绝不会超过它在磁盘上的文件的大小。而为```bss```段预留的空间在它存储实际数据之前是没有必要浪费磁盘空间的，这是可以通过实例来证实的。
>>>请注意，```data```和```bss```段经常统称为```data```，偶尔会导致混淆。

###内存映射
当ELF文件被执行后，```text```段和两个```data```段会被加载到虚拟内存中一片独立的区域内。按照惯例，```text```段占据着最低地址空间，```data```段在它上面。每个部分被分配了适当的权限。通常，```text```段是只读的，```data```段是可读写的。一个典型的进程```内存映射（memory map）```如图3所示。

![图3 进程中text,data,bsss段的内存映射情况][3]

如图虚拟内存的地址空间是从底部的0到顶部的512GB。512GB以上的地址空间是Linux内核保留的。这是特定于AMD64硬件的，其他的体系架构可能有不同的限制。

虽然一个进程的大小（text+data+bsss）在编译时候就已经确定了并且在执行期间可以保持不变。但是程序仍然可以在运行时从虚拟内存中未被占用的地方拓展自己的空间，在C中用```malloc()```函数，在Fortran 90/95中用```ALLOCATABLE arrays```。在Fortran 77可以通过扩展获得相似的特性。这些动态分配的内存位于```data```段之上的```heap```段。如图4所示。

![图4 包括heap段在内的内存映射，data和bss统称为data][4]

所有的三个段，```text```,```data```（data+bss），以及```heap```，都通过页表映射到物理内存。由图可知，随着内存的分配和释放，```heap```段会不断膨胀和收缩，所以意味着，页表项必须不断的新增和删除。

###调用堆栈
面向过程（相对面向对象来说）式的程序会被组织成子程序调用的逻辑层次结构。一般情况下，每次调用子程序涉及从调用者传递参数给被调用者。此外，被调用者可以声明临时的局部变量。子程序参数和局部变量（```automatic ```）位于从虚拟内存顶部开始向下生长的```stack```段或简称```stack```。如图5所示。

![图5 显示栈段的内存映射][5]

子程序的调用层次是开始于操作系统调用程序的主函数，在C中是```main()```，在Fortran中是```MAIN```，在正常的情况下，结束于主函数返回给操作系统。整个序列可以表示为如图6所示的调用图。

![图6 典型的子程序调用图][6]

 >1. 操作系统调用主函数main
 >2. main调用func1
 >3. func1调用func2
 >4. func2返回给func1
 >5. func1调用func3
 >6. func3返回给func1
 >7. func1返回给main
 >8. main调用func4
 >9. func4返回给main
> 10. main返回给操作系统

在调用主函数之前，操作系统会将用于调用程序的命令行参数推到初始空栈的"顶部"。在C中```main()```函数是通过```argc```和```argv```来访问这些参数的。

随着程序的执行，主函数将自己的局部变量推到栈的顶部。这会导致栈朝着低地址空间生长。然后，先顺序的执行函数func1，主函数将参数传递给func1。作为整体，主函数的局部变量和传递给函数func1的参数组成了一个```栈帧（statck frame）```。栈帧随着调用图不断往下而积累，往上而拆除。该过程如图7所示。

![图7 图6所示的调用层次中栈的不断演变的情形][7]

通常，当前活动的子程序只能引用到传递给自己的参数，自己的局部变量以及静态变量（包括任何全局可访问的数据）。举例来说，当函数func2执行的时候，它不能访问函数func1的局部变量，除非函数func1将自己变量的引用通过传参传给func2。

###页表
如图8所示，展示了页表，内存映射，物理内存之间的关系：页表的膨胀或收缩，映射或多或少的物理内存，堆栈和堆两个部分大小的改变。

![图8 内存映射、页表和物理内存][8]

假设每个页表项都用一个64位的数字表示一个虚拟内存地址，用另外一个64位数字表示物理地址，那么每个页表项的大小为16字节。为了映射一个200MB的进程空间，将需要3200MB的页表。显然这是不切实际的。为了取代映射单个字节，页表使用了一个叫做```页(page)```（页表因此而得名）的更大的虚拟内存块。实际内存中相应的一个增量空间称为```页帧（page frame）```。

页的大小是特定于具体的体系架构的，通常也是可配置的。这两方面都会有很多作用。 AICT Linux集群中的AMD处理器使用的4KB。从而，现在映射一个200MB的空间只需要800KB的页表。

超过1.28亿的页面涵盖了512GB的虚拟内存地址空间。它们以一个```虚拟页号（VPN）```进行顺序编号。每个页表项将进程的虚拟页映射到物理内存的页帧，即从一个```VPN```映射到一个```页帧号（PFN）```。```VPN```是通过将虚拟内存的地址除以页的大小得到的（将地址右移）。一个具体的字节是通过它在页中偏移量来定位的。

###库
链接一个静态库到程序中，将其```text```和```data```段整合到ELF文件中。结果，两个链接同一个静态库的程序都会将库数据映射到物理内存中。如图9所示。

![图9 两个程序链接相同的静态库][9]

静态库的ELF格式的文件以```.a（archive）```作为扩展名。ELF格式还支持动态共享库，以```.so（shared object）```作为扩展名。

从两个方面来看动态共享库和静态库的区别。第一，只有库的名称会被记录在ELF文件中，没有```text```和```data```，结果是更小的可执行文件。第二，始终只会有一份拷贝存在于物理内存中，这样更节省内存而且加速了其他需要链接相同动态库的程序的加载过程。这样的情形，如图10所示。

![图10 两个程序链接相同的动态共享库][10]

当第一个程序被执行，系统会找到库并更新进程的页表将库的```text```和```data```段映射到物理内存中。然后当第二个程序执行时，其页表项中对于库的```text```段的映射会被指向已经存在的物理内存。库的```text```段之所以可以被这样共享，是因为它有这样的权限，像所有其他程序的```text```段一样，它是可读的。

初始时，库的```data```段只有读的时候也是被共享的，可是，当另一个程序视图去更新这个部分的时候，一个私有备份操作将会发生，这个程序的页表将会映射这份副本。使用了一个广为认知的策略```COW（copy on write）```。上图展示的是每个程序拥有自己的库的```data```段副本。

###内存限制
在**程序和进程**那一节，我们提到一个进程会从它的父进程那里继承一些内存上的限制，父进程通常是shell进程。在AICT中这种情形，```bash```和```tcsh```会有一个限制栈段的大小不能超过10MB的```软限制（soft limit）```。其他一些内存参数，```data```段，总的虚拟内存，总的物理内存则没有限制。

虽然```text```，```data```，```heap```以及```stack```段已经被描述成有一定的大小。但是在一些典型的高性能应用场景中无论是```data```段还是```bss```或```heap```段都有可能有一个或多个的大数组。如果一个大数组是基于栈的，则很有可能会超过限制的大小。这种情况，进程会发生```"段违规（Segmentation violation）"```而终止。

为了避免这种结果。软限制可以使用内建的shell命令增加。例如，在```bash```下用``` ulimit -s 20480```，在```tcsh ```下```limit stacksize 20480```将栈的大小调整为20MB。软限制可以被提升到相应配置的```硬限制（hard limit）```。在AICT 集群中，栈段大小的硬限制是"```unlimited```"，意思是没有限制。值得注意的是，新的限制只对从调整限制的```shell```衍生的进程有效。

>要知道，对```shell```资源的软限制和硬限制在不同的系统中差别很大。

很多的AICT集群安装有10GB的内存。其中有接近1000MB是保留给操作系统用来维护进程信息的，包括页表在内。另外在较为缓慢的作为二级存储的磁盘上有一个1GB的空间（可配置）作为```交换空间（swap space）```，或者，更为准确的说叫做分页空间（```paging space```）。所有的可用的内存加上交换空间大约有9800MB（经验值），这个值代表总的虚拟的或实际的内存，一个节点上所有可以用来作为进程映射的空间，这个数量有一个术语叫做**```SWAP```**（也可以被称作为逻辑交换空间```logical swap space```）。

为了说明以交互方式运行的进程的栈空间软限制是如何运作的（AICT集群的头结点），参看图11。

![图11 一个交互进程上栈空间的软限制][11]

如图所示，软限制就像一个围在页表中栈段映射那部分周围一个边框。当软限制为"unlimited"的时候就好比移除这个边框。同时，堆段的空间大小只限制于可用的```SWAP```。

由于批处理是一个shell脚本，它可能包括一些适当的限制命令，在调用一些计算程序之前增加栈的大小限制。而且，批处理作业被分配有足够的```SWAP```用来满足请求进程的虚拟内存（```pvmem```）。为了保证作业不会超过它的```pvmem```规范，批处理系统会减少它关联的```shell```进程的虚拟内存的软限制以匹配```pvmem```的值，通常初始值为"unlimited"。每当一个软限制被修改，相应的硬限制也会被重新设置为相同的值。

此外，一个作业的大小（text+data+bsss）超过虚拟内存的限制是不允许被启动的。当一个作业试图在运行时将其虚拟内存扩展到限制的大小以外，它会因为"```Segmentation violation```信号异常中断"。要正常退出，在C语言中可以检查```malloc()```函数的返回值是否为空指针。

在AICT集群上，一个进程以批处理方式运行，它的内存限制如图12所示。

![图12 批处理进程上的栈空间和虚拟内存限制][12]

因为页表代表了一个进程虚拟内存的占用情况，所以虚拟内存的软限制被描述成页表周围的边框。注意在某些情况下，虚拟内存的限制可能会被基于栈的数据所侵犯，即使栈的大小并不会超过它的限制。

###内存分配
到目前为止，我们图形化的页表展示似乎暗示我们虚拟内存的页总是能够映射到实际的物理内存页帧。但是，实际上，因为有些页从来都没被用到，对于操作系统来说更有效的策略是推迟映射到确实需要的时候，这项技术被叫做```按需分页（demand paging）```。

例如，在Fortran 77中一个普遍做法是，用一个预估的最大的静态数组去编译一个程序，并使用相同的可执行文件配合各种数组的扩展来进行演算。在这种情况下，页表中会保留足够多的虚拟页来容纳那些大数组。但是，在实际内存中，只包含由程序实际引用数组元素的页被分配的页帧。那些从来没被引用的页不会分配页帧。所有被分配页帧的总和叫做```驻留集大小（resident set size,RSS）```。如图13所示，RSS小于或等于进程占用的虚拟内存。

![图13 对图12更为真实的一个描述，包括了驻留集大小][13]

当进程第一次引用一个虚拟页的时候，会发生一个```页错误（page fault）```。Linux负责从一个剩余页池中获取一个页帧，并将其分配给进程页表中对应的虚拟页。另外，页表中最近的512个页表项会被缓存在CPU的一个叫做"```translation lookaside buffer，TLB```"的缓存中。引用``TLB```中的页表项要比访问位于内核内存中的页表快。

对于高性能的应用，理想的情况是每个进程都有充足的可用内存（```RAM```）。如果非常多的内存被使用导致内存耗尽，这时一个页帧可以被另外一个进程“偷走”。偷走的页帧上的内容会被转移到磁盘上的交换空间中，同时被偷进程的页表会被更新。换句话说，页被换出，或者更准确，术语叫做```paged out```。位于交换空间的页帧是不能直接使用的。因此，如果一个进程引用了该页，被称作```主页错误（major page fault）```，它首先必须被换进，造成一个页从其它进程被换出，导致结果是需要更多的内存，更多交换空间的使用，从而又导致更多的```swapping```。因为磁盘的访问是相对缓慢的，结果是所有进程的性能受到严重的影响。最终，当交换空间都承受不住的时候，进程会被杀掉以回收内存。在这种情况，节点会快速的变成不可用。为了防止上面这种情况，批处理系统必须遵循```pvmem```规范以保证节点上总的SWAP不会被耗尽。

###实现细节
略。

###参考文献

 1. Understanding the Linux Kernel, by Daniel P. Bovet and Marco Cesati,
    ?2001 O‘Reilly
 2. Linkers and Loaders, by John R. Levine, ?2000 Morgan Kaufmann
 3. System V Application Binary Interface: AMD64 Architecture Processor
    Supplement, Draft Version 0.96, by Michael Matz, Jan Hubi?ka,
    Andreas Jaeger, and Mark Mitchell

  [1]: http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/images/mem/figure1.png
  [2]: http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/images/mem/figure2.png
  [3]: http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/images/mem/figure3.png
  [4]: http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/images/mem/figure4.png
  [5]: http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/images/mem/figure5.png
  [6]: http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/images/mem/figure6.png
  [7]: http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/images/mem/figure7.png
  [8]: http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/images/mem/figure8.png
  [9]: http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/images/mem/figure9.png
  [10]: http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/images/mem/figure10.png
  [11]: http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/images/mem/figure11.png
  [12]: http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/images/mem/figure12.png
  [13]: http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/images/mem/figure13.png

/**
  * simple.c
  */
#include 
#include 

#define NSIZE 200000000

char x[NSIZE];

int
main (void)
{
  for (int i=0; i<NSIZE; i++)
    x[i] = ‘x‘;

  printf ("done\n");

  exit (EXIT_SUCCESS);
}

$ pgcc -c9x -o simple simple.c
$ size simple
   text    data    bss         dec         hex       filename
   1226    560     200000032   200001818   bebc91a   simple

$ ls -l simple
-rwxr-xr-x  1 esumbar uofa 7114 Nov 15 14:12 simple

!
! simple.f90
!
module globals
  implicit none
  integer, parameter :: NMAX = 200000000
  character(1), save :: x(NMAX)
end module globals

program simple
  use globals
  implicit none
  integer :: i

  do i = 1, NMAX
     x(i) = ‘x‘
  end do
  print*, "done"
  stop
end program simple

$ pgf95 -o simple simple.f90
$ size simple
   text    data    bss         dec         hex       filename
   77727   1088772 200003752   201170251   bfd9d4b   simple

$ ls -l simple
-rwxr-xr-x  1 esumbar uofa 1201694 Nov 15 14:12 simple

$ file simple
simple: ELF 64-bit LSB executable, AMD x86-64, ...

【翻译】理解内存