内存管理

远古时代,整个系统只有一个地址空间,即物理地址空间。无论操作系统还是应用程序看到的都是这个地址空间，它们共同来使用它。

这对于单任务的OS没有什么问题。OS占据其中的一部分，把其余的部分留给应用程序，编译器或链接器负责把应用程序的入口地址设定为固定位置，把其它段，如Data段，Stack段等等根据程序本身的规模放到应用程序可使用空间的某个位置。在执行的时候，Loader把这些段放到相应的位置，如果实际的物理内存不足以容纳当前的Application，OS就直接给出错误信息．否则，执行它就是了。

但对于多任务的OS，其Application的Link/Loader模型就不是那么简单了。由于多个Application共享供应用程序使用的地址空间，那么每个Application在每次执行时被装入内存的位置可能是不同的。那么这个Application里面的地址访问指令——如果不是明确的想访问某个绝对地址的话——就绝对不能将绝对地址明确的指出来。否则，运行时一定会出问题。

这些地址只能是相对地址。解决运行时问题的方法之一是：编译器／链接器对于每个非程序员明确指出的地址都编译为一个未赋值地址加上一个相对地址。在执行的时候，Loader根据当前Application被装入的实际地址对这个未赋值基地址进行赋值。这样，Application的每一个地址访问指令给出的就都是正确的绝对地址了。

这种方法肯定可以工作，但却存在着一个很大的性能问题，由于Application对于每个内存的访问都要先进行地址运算，而内存访问在一个程序的执行过程中是非常频繁的，其性能可想而知。

所以，硬件设计者根据这个问题提出了分段模式．分段模式允许程序在指定了某个段的基地址之后，随后程序给出的地址都是相对于这个段基地址的相对地址．对于绝对地址的运算由硬件完成，性能自然高多了。编译器／链接器在编译链接的时候，只需要认为自己所使用的地址是从０开始的。Loader在装载程序的时候，只需要把OS分配给当前Application的内存设定为一个段就可以了。

本质上，分段模型将一维的地址空间变成了二维．因为在同一物理地址空间内可以有任意数量的段，每个段内的地址都是［0，limit_of_segment-1]。这样，无论是OS，还是Application在给出一个地址的时候，这个地址都不是绝对的物理地址，而是其在某个段内的地址。硬件会负责把这些段内的相对地址转化为物理绝对地址。

段模型曾经让我感到困惑的一点是段与段之间可以重叠．所以可以重叠，使指两个段空间对应的物理地址有交集。当时我觉得，如果段与段之间可以重叠的话，你对于一个段的访问可能会修改另外一个段的数据。我之所以感到困惑，是因为我没有完全理解段模型的真正意义．段模型提供给OS和Application一种访问内存的方式，让程序员可以在一个段空间任意直接指定地址。在两个段空间内访问到共同的绝对物理地址与段模型本身的意义完全没有任何矛盾和冲突。

尽管有了分段机制，但所有的段内相对地址都会被直接映射为绝对物理地址。所有的Application的所有代码和数据，在运行时刻都被装载在物理内存内。

另外，尽管分段机制允许段与段之间可以重叠，但如果不是为了某些特殊目的，比如进程间共享数据，不同Application之间的段是不应该重叠的。

所以，Application程序员在写程序时，需要考虑对内存的使用，因为总体的内存是非常有限的，如果其占用的内存过多，留给系统中别的Application自然就少。有时候，某个Application甚至因为其自身的大小已经超过了物理内存的容量，这种情况下，这个Application是根本无法得到运行的。

为了解决这个问题，有人提出了交换的概念。

所谓交换，就是当系统内存不够时，将已经在内存中的一部分数据暂时移出内存，将这部分空出来的内存用做当前的内存请求。

对于单一内存空间来讲，多个进程共享这个内存空间，所以交换的时候，必须将整个进程换入换出。这是因为，由于进程内部的地址都是相对于某一地址的相对地址，如果把进程的不同的部分放在不同的位置，根本没有办法寻址。除非，一个进程的一部分被换出时，下一次换入时仍然被换到相同的位置，否则，部分换出策略是不可行的。

在带有段模式的平台上，则必须将进程中一个段的内容完全换出，因为段内的地址都是在当前段空间的。不可能将一个段内的内容分布在不同的段内。由于一个进程一般会有多个段，所以看起来或许可以避免将整个进程换出。但由于在一个进程内部：

1）段与段之间很有可能重叠；
2）必须考虑段与段之间互相访问的地址问题；
3）交换程序必须知道这些段的存在，并知道这些段之间的关系。
4）由于段与段之间的交互，换出某些段而保留其他段是没有意义的。

所以，即使在带有段模式的平台上，也都是将整个进程换入换出。

物理内存是昂贵的，最起码在上个世纪是昂贵的。即使这些年来摩尔定律一直是正确的断言，当前物理内存已经比以前便宜的多，但对于绝大多数计算机而言，物理内存数量仍然没有达到满配。比如，对于32位计算机，最大的寻址空间为4G，但即使在今天，内存配置达到4G的PC有几台呢？

更何况，这些内存不能被某个Application单独使用。单任务的DOS在大约10年前就开始寿终正寝。当前的PC机上运行的OS都是多任务的。机器上有限的物理内存被OS和不确定数量的Application共享。这样，即使物理内存达到满配，分配给每个Application的内存数量仍然是非常有限的。程序员在编写程序的时候，必须考虑自己程序对内存的使用问题。

人是由有欲望的。程序员也是人，在多用户多任务的系统上，每个程序员都希望自己独占当前系统的所有资源。即拥有CPU的运行权，拥有整个内存空间，拥有对IO的访问权，等等。否则，如果想让大家和睦的共处一室，大家必须互相照顾，收敛自己的个性，遵守某些共同的行为规范。但每个人都希望自己可以不受任何限制的挥洒个性。如果你在郊外拥有一座自己的别墅，你尽可以在凌晨去弹钢琴。但如果你和别人合住，或有楼上楼下的关系，你只能在不打扰别人正常生活的时候去弹。所以，如果有可能，谁都希望自己可以拥有自己不受别人约束的空间。与别人共享实在是迫不得已。

多任务的系统通过分时机制，让每个用户，每个程序都以位自己占有整台计算机的CPU，因为每个程序运行的时间是如此的短，给每个用户，每个程序造成了独占CPU的错觉。对于IO设备的访问也是如此，多任务的OS平衡各个用户程序对于IO的请求，让每个程序都以为自己在使用这些资源。由于CPU，IO等设备都是Application程序员不需要关心的，他们只需要感觉到自己需要CPU的时候就有CPU，需要IO的时候就有IO，它们就满足了。

但对于内存却不是如此，程序员知道自己正在编写程序的平台的最大内存限制，于是他希望自己全部拥有它们。这样程序员就真正的得到了一台虚拟机了。

虚拟内存的概念应运而生——

虚拟内存让每个任务都拥有整个平台所允许拥有的最大内存数量。对于32位平台，每个任务都拥有4G的内存空间。这个空间是被Task独占的，系统中有多少个Task，就有多少个4G内存空间。这个空间的范围为[0，4G-1]。本文所有给出的例子，如果不作出特殊说明，都是指32位平台。

在支持虚拟内存的平台上，地址空间至少有2种：

1）物理地址空间；
物理内存在[0，4G-1]的空间内被编址。注意，物理地址中间可能有空洞，即物理内存的编制可能是不连续的。一个平台只能有一个物理地址空间。

2）虚拟地址空间。
虚拟地址空间是一个连续的线性空间。一个平台可以有任意多个虚拟地址空间。虚拟地址空间内的地址被称作虚拟地址。

在支持虚拟内存的平台上，任意时刻给出的地址都是虚拟地址。但由于需要访问的是真正的物理内存，所以硬件会将虚拟地址转化为物理地址。

从虚拟地址到物理地址的转换关系被定义在一张表内。硬件进行地址转化是通过查这张表来完成的。从数学上讲，这是一个一元函数f(x)，其中x是虚拟地址，f(x)是物理地址。而表中的内容则是一个二元组（虚拟内存地址，物理内存地址）的集合。

这张映射表被放在物理内存中。由于整个虚拟地址空间存在4G个地址，那么如果每个地址在这张表中都有一个表项的话，需要4G的内存才能放得下这张表。所以，需要把内存分为粒度更大的单元，每一个单元被称作页，所以这张表被称作"页表"。

每个任务都有4G的虚拟内存空间，但每个任务在运行时真正占用的物理内存却要少的多。如下几个原因导致这个结果：

1）每个任务都有4G的虚拟内存空间，但所有任务却要共享不超过4G的物理内存。绝大多数情况下，物理内存的数量都远小于4G。

当有很多任务同时运行时，由于物理内存及其有限，每一个任务所能够分配到的物理内存资源就更加有限了。

2）很少有任务能够将4G的虚拟内存空间完全使用。绝大多数任务占用的空间都很小。

虚拟内存机制为每个任务都提供了全额的虚拟内存空间，但现实中存在的程序很少有这么大的内存耗用的。对于没有使用的虚拟内存空间，根本就不需要为其分配物理内存建立映射。

3）根据局部性原理，程序在绝大多数时间内，都运行在很少的代码上。

这是很重要的一点，因为它是虚拟内存方案之所以可行的理论基础。

局部性原理是一个根据经验得出的结论。它包含时间和空间的局部性。根据局部性原理，计算机设计者使用速度更快，数量较少的存储器来保存速度较慢，数量较大存储器的局部数据，当需要访问的数据不在高性能内存中时，软硬件会通过某种算法将高性能内存中的一部分数据替换为需要访问的数据。这样就做到了价格和性能的折衷，得到最好的性价比。

当虚拟内存方案被提出之后，一部分人由于性能方面的考虑，对其可行性提出质疑，但经过大量的测试之后，测试结果让这些人闭上了嘴。如今，几乎所有的PC机以上机型都支持虚拟内存，很多嵌入式芯片也是这样。

根据虚拟内存机制的理论基础，物理内存不再是传统意义上的物理内存，而是做为外部存储设备的缓存（cache）。基于这个观点，虚拟内存管理的算法则会表现出不同于传统MM的逻辑。这一点我们以后再讨论。

页面大小的选择并不是随意指定的。

1）如果一个页面太大，则会造成更多的内存浪费；

由于内存的分配都是以"页"为单位的，假如一个进程段的大小9K。如果页面大小为4K，则需要分配3个页面，其中有3K空间是浪费掉的。如果页面大小为8K，则需要分配两个页面，其中有7K空间是浪费掉的。

2）如果一个页面太小，则需要更多的页表空间；

对于32位平台，有4G的虚存空间。在使用一级页表的情况下，如果页面大小为4K，则存在4G/4K=1M个表项。如果页面大小为1K，则需要4G/1K=4M个表项。每个表项占用4个字节，4K页需要4M物理内存来存放页表，1K也则需要16M物理内存来存放页表。要知道，页表是必须存在于物理内存中的，绝对不能被交换出去（这是鸡和蛋的问题）。所以这些内存占用是非常可观的，更何况，在多任务系统上，每个Task都有自己的页表。所以，使用过小的页造成的过大页表占用几乎是不可接受的。

所以，必须在二者之间做出平衡，有人曾经给出一个公式计算出合理的页面大小，但这个公式的模型未必非常合理，因为在不同用途的平台上，其设计者会根据其上Application的特点的不同而选取相应的页面大小，一般来说，设计者会以较多的内存碎片（浪费）率来换取较小的页表空间。常见的页面大小为2K到8K。

但即使使用较大的页面，页表对于物理内存的占用仍然显得非常庞大。在一个8K页面大小的平台上，一个页表需要的2M的内存，如果当前有10个Task，仅仅页表就要占用20M内存。对于稀有的物理内存资源而言，这是一笔昂贵的开销。

基于这样一个事实——

绝大多数程序对内存空间的需求远远小于全部虚拟内存空间。

在当前的页表方案中，页表中的很多表项都是闲置不用的，这些开销无疑是不必要的浪费。另外，由于一个进程经常会不连续的使用内存空间，比如，一个进程可以使用4G空间中的0~1M，1G~1G+1M，4G-1M~4G作为它的3个段。这样，又不能采用根据实际需要来设定页表大小的方案。

于是，有人提出了多级页表的方案。我们以二级页表为例，假如页的大小为4K，那么整个虚存空间应该存在1M个映射表项，现在把这1M个映射表项平均分成1K份，每一个份称为一个子页表。然后建立一张新的表来保存对这1K个页表的映射，这张表被称为页目录。

当CPU需要访问一个虚拟地址时，它先到页目录中查找相应的页表的地址，然后再从页表中查到相应的映射，以将此虚拟地址转化为物理地址。

对于那些没有被使用的虚拟内存空间，其所处的子页表根本就不需要创建。这样就可以节省大量的内存。比如，一个进程，其占用的虚拟内存空间为0~1M，2G~2G+1M，在上面的例子中，则其二级页表占用的空间为1个4K大小的页目录+2张4K大小的页表=12K。如果使用1级页表方案，则需要4M的内存。

有一点必须说明的是，页目录和页表表项中保存的地址都必须是物理地址。而保存在页目录寄存器中的页目录地址也必须是物理地址。因为整个页表架构就是为了实现从虚拟地址到物理地址的转化，如果其自身保存的就是虚拟地址，就又陷入一个不可跳出的逻辑怪圈了。

在一个支持虚拟内存的平台上，任意时刻，都有唯一的一个页表在起作用，在这个页表中定义了整个虚拟地址空间和物理内存之间的映射关系。

另外，在任意时刻，OS Kernel都存在于内存中，所以，OS Kernel自身一定会占用一部分虚拟内存空间，这部分空间被称为内核空间。其余的虚拟地址空间则留给用户进程使用，被称为用户空间。

因此，在任意时刻，整个虚拟内存空间都会被分为两部分，内核空间和用户空间。从页表的角度看，所有页表对于内核空间的定义都是一致的，而对于用户空间的定义则根据用户进程的需要而不同。所以，可以这么认为，每个进程都有自己的用户空间，而共享内核空间。

在32位Linux系统上，内核占据每个虚拟地址空间的3G-4G部分，不同的进程则使用自己虚拟地址空间的0-3G部分。

把内核空间放在整个虚拟地址空间的顶部或底部，各有利弊。

1）如果把内核空间放在底部，即[0, size of kernel space)，内核可以建立虚拟地址和物理地址的相等映射，即虚拟地址等于物理地址。这种情况下，内核可以不用关心一个给出的地址是一个虚拟地址还是物理地址。否则，内核必须明确这一点，并在必要的时候在两者之间进行转换。

2）如果把内核空间放在顶部，即[Start of kernel space, 4G)，则用户空间为[0, Start of kernel space)，这样则为用户空间提供了一种自然的方式。为了理解这一点，我们先看一个用户进程空间是如何安排的。

   |------------------| <-- Top of User Space
   |    User Stack    |
   |                  |
         ... ... 
   |                  |
   |       Heap       |
   |------------------|
   |                  |
   |  Data, Text, BSS |
   |  Other Sects,    |
   |  & Unused space  |
         ... ...      
   |                  |
   |------------------| <-- Bottom of User Space

User Stack是被Loader按照当前系统的用户空间设置在装载程序映像时设置的，而Data, Text, BSS, 以及其它段的虚拟地址则是在编译时就确定了。

这样，如果内核被空间放在整个虚拟地址空间的顶部，无论内核空间大小如何变化，Loader总能根据变化后的情况来正确设置Stack的起始位置。而其它段的地址总是为相对于0的固定地址，所以无需重新对这些用户程序进行编译。

但如果把内核放在进程空间的底部，当内核空间的大小进行调整时，则会对用户进程模型产生影响。如果变大，则内核空间就侵占了用户地址空间，由于那些静态段的地址都是固定的，所以，必须重新编译用户程序，才能保证用户进程的正确性。如果变小，则原有的用户程序就会浪费这部分被内核让出的内存空间。

所以，一般来讲，为了让系统有更好的可维护性，OS设计者一般都会把内核放在虚存空间的顶部，尽管这会让OS的编写者付出一些附加的effort，但相对于所得到的而言，这是完全值得的。

在支持虚拟内存的架构上，物理内存被用作3种目的：

1）被内核映像占用一部分；

包括内核text段，Data段，bss段，以及其它内核静态段。

2）内核进行管理时，所需要的动态内存；

这些往往是根据实际的数据结构来分配的动态内存。其大小是不规则的。

3）作为用户进程的cache。

这些物理内存的分配和释放都是以page为单位的。

我们从启动开始，来看看一个OS应该如果来管理物理内存的。

在OS的启动过程中，Boot程序会通过调用硬件平台所提供的接口，比如BIOS，或者其它手段来获取整个物理内存的大小，以及分布状况。并将这些信息保存在物理内存的某个位置，将来OS Kernel可以来这里读取这些信息。

随后，Boot程序将OS Kernel装入物理内存的某个位置，并将运行权转交给OS Kernel。

OS Kernel可以通过Linker插入的符号start和end知道自己占用的物理内存位置和大小。其位置[start,end]，其大小为end-start。然后OS读取Boot所探测到的物理内存的分布状况及容量信息，除去自己已经占用的部分，其余的均为可使用物理内存资源，这些物理内存被用作上述的后两个目的。

这个过程中有一点需要注意：如果内核空间被放在整个虚存空间的顶部，则物理内存和虚拟内存是不一致的，它们之间存在着一个偏移。比如，如果内核空间被放在[3G, 4G)的范围，则虚拟内存=物理内存+3G。所以在Link OS kernel时，已经告诉链接器OS Kernel的起始虚拟地址。因此OS Kernel内部对符号地址的访问都被设置为相对于起始虚拟地址的偏移量。当OS Kernel被Loader入内存时，为了让CPU能够正确的访问到OS Kernel的指令和数据，在分页模式被enable之前，OS Kernel对所有符号的访问一定要自行进行虚拟地址到物理地址的转化。直到OS Kernel将分页模式enable为止。

另外，为了尽快的启动分页模式，OS Kernel中会静态设置一个页表，但此时OS Kernel并不知道究竟有多少物理内存，所以在静态页表中，会预先映射少量物理内存，比如8M。等分页模式被启动之后，再读取由Boot程序探测到的物理内存大小及分布来完全设置页表。