从种地到内存管理的哲学原理

前言

在操作系统出现之前，程序曾经存放在卡片上，计算机每读一张卡片，就运行一条指令，这个时候程序是直接从卡片到执行；但这种从外部存储媒介上直接执行指令的做法效率极低，且灵活性很差，一次只能一个卡片来处理；因此人们发明了内存存储器，来将需要运行的程序先行加载，再自动执行，从而提高效率和灵活性。
由于内存的出现，出现了“存储的程序”概念的出现，而存储的程序概念又导致计算机及软件系统的革命性变化，此后人们对内存的要求越来越高。

背景

理想的情况下，程序员或用户对内存的要求是：大容量，高速度和持久性。但程序员面临的物理现实却是一个由缓存、主存、硬盘等组成的内存架构。
缓存的特点：低容量、高速度、高价格；
主存的特点：中容量、中速度、中价格；
硬盘的特点：大容量、低速度、低成本；
这样的存储架构和程序员、用户的期望相差较大；要以现在的架构为程序员所需的内存抽象，需要一个巧妙有效的内存管理机制。

内存管理相关

内存管理把缓存、主存、硬盘都当成一样的内存，因为不管用户的程序是在缓存还是在主存或者硬盘，反正运行计算输出结果都是一样的。
内存管理怎么把缓存、主存和硬盘当成是一样的呢？？？这个时候就需要抽象（就像人类喜欢把香蕉和桃子都叫做水果），缓存、主存和硬盘被抽象为“虚拟内存”；通过虚拟内存，程序员和用户不关心底层的实现，只知道程序存在虚拟内存中。
虚拟内存本身独立于物理内存，因此概念提出的瞬间，内存管理机制便天然拥有一个目标：地址独立。那内存管理机制还有没有其他目标了？？？
在当今的多道程序操作系统中，虚拟内存中会运行着大量的程序，程序与程序之间是要相互独立的，因此内存管理的另一个目标就在于地址保护：一个程序不能去访问另一个程序的内存地址。
由于虚拟内存屏蔽了缓存、主存、硬盘的差异性，因此虚拟内存可以看做是操作系统提供的大容量，高速度的内存。
本文从种地的角度来解释操作系统内存管理机制的演变以及演变中的哲学原理，知识来源于生活。

种地（本故事纯属虚构）

汉朝时期，老王出身贫寒，遂从军，历时十载，军功赫赫，国内一片繁荣；老王怕功高震主，遂请辞回家养老，由于老王的军功，皇帝赐了一块封地给他颐养天年；老王美滋滋的踏上了去封地的旅程~~
老王到了封地，果然是一片很大的封地，但是一片荒凉，啥都没有；老王把这块地叫做“物理内存”，给它标记了地址，一开始的地址为0，不停的增长到封地尽头N；

盖房子（操作系统内存位置）

老王决定先建一个房子住，不然都没地方住，他把自己的房子命名为“操作系统”；问题产生了：房子建在哪边（操作系统应该放在物理内存哪边）？可以是地址0~N的任何地址位置。
计算机中的清零操作很方便，并且开始地址0很容易索引，因此老王决定把操作系统建在地址0处。

老王未雨绸缪，怕将来有仇家寻上门，因此在房子下面建立了地下密室，用于藏身，命名为ROM；
计算机体系中分为RAM和ROM，物理内存就是RAM，RAM断电内容消失，因此操作系统一部分是放在ROM上，另一部分加载到RAM中。
最后，老王的房子分为了地上的部分和地下密室的部分。

单一作物（单道编程）

老王很喜欢吃土豆，因此老王决定挑选一块地种土豆；这个时候封地上除了房子只有一个农作物：土豆；相当于计算机中的单道编程，用户程序永远只有一个；这样老王可以随机挑选一个固定的地址T；每次在T地址上种植土豆；这种运行前即将物理地址计算好的方式叫做“静态地址翻译”。这种情况下，虚拟地址永远映射到固定的物理内存地址上；因此单道编程的情况下很容易达到内存管理机制的两个目标。

单道编程的缺点很多，只能运行一个程序，并行度很低；此外加载程序的大小不能超过物理内存空间；而且程序不能移植到不同的操作系统，因为不同操作系统的内存空间大小不一样。

多个作物（多道编程）

老王吃多了土豆，生病了，大夫让老王吃点其他蔬菜，营养均衡，因此老王想在土豆的基础上种植其他的蔬菜（青菜，番茄等。。。）；老王也不知道要吃多少中蔬菜才能补营养，因此老王不能很好的规划种植的地址；

因为多道编程的情况下，程序无法再加载到固定的内存地址上，这就无法使用静态地址翻译；计算机必须在程序加载完毕后才能计算物理地址，这种就叫做“动态地址翻译”。

固定分区

面对如此多的蔬菜作物，老王想了个办法，一批批的补充营养；老王将封地分为大小不同的分区（为啥大小不同，因为有些老王爱吃，多种点），分区数为M；不同的分区种上不同的蔬菜；这样封地有多少分区，老王就可以种多少蔬菜，等其中分区的蔬菜吃完就可以在分区种另一种蔬菜。

计算机系统将内存分为大小不同的多个分区；因为程序的大小不同，不同的程序分配到不同的分区；操作系统用一个队列保存了操作系统的程序，当有空白分区的时候，把程序加入空白分区里；
老王知道喜爱的菜多种些，让分区物尽其用；但是计算机如果把小程序分配到大分区里，会造成大量空间的浪费；因此可以每个分区都有自己独立的队列，把适合该分区的程序存放在队列中，当分区空白时，加载相应的程序，这样空间浪费率相对低点。
不管是单队列，还是分区多队列，都有很大的问题，但队列的话，会造成大量的空间浪费；多队列会造成有空白分区，但是其他队列的程序再等待，不能运行。

那固定分区的这种情况下，老王怎么统计农作物的地址；老王记录了每个分区在封地的起始地址；然后记录了农作物在分区里的虚拟地址；因此封地的物理地址=虚拟地址+分区的起始地址。

这就是固定分区，计算机的地址翻译；对于内存管理的两个目标，地址保护可以通过地址翻译来判断程序是否超出了分区的地址；因此计算机只需要保存一个基址和一个极限就可以达到地址保护的目的；可以通过基址寄存器和极限寄存器来保存；地址独立是虚拟内存自带的概念；因此固定分区完全符合内存管理的设计。

非固定分区

经过了固定分区的规划，老王美滋滋的幻想起了以后美好的生活；但是老王忽略了一点，就是自己的种植能力；大的分区全种植了自己爱吃的番茄，但由于自己种植不当，大部分番茄没长出来，今年造成了大量的土地浪费；老王很心痛，痛则思变；
老王想了很久，还是决定灵活处理，不固定分区，而是把封地除了操作系统房子外都当成一个整体；如果要种青菜，则分出一块地中青菜；如果又要种番茄，则在剩下的封地中再分出一块地种番茄；依次类推，当地不足时，就等其中的蔬菜成熟收割后，把地空出来后再种剩下的蔬菜。
老王一想，这样就不会有地浪费了，当种不出来的时候，老王就可以种其他蔬菜，充分利用封地；

老王的思想在操作系统中叫做非固定分区内存管理；当程序来的时候，会在空白内存中挑选一块给程序执行。
由于固定分区的时候我们知道，用基址和极限两个寄存器就可以表示每个程序的位置；因此在非固定分区下，为每个程序配置基址和极限寄存器就可以识别程序的物理地址。

乍一看，好像问题都解决了，但是老王忽略了一个很严重的问题；有些蔬菜有很强的侵略性，像蒲公英一样，种子会到处传播；导致其他土地上也长满这样的蔬菜，这样就不能很好的隔开种植，规划封地了。

计算机程序在运行过程中，会出现动态增长的情况；程序空间增值的主要来源：数据和栈。那么怎么处理程序的增长呢？？？
解决办法就是为增长的程序预留出增长的空间，因此数据和栈的增长就如图所示。
数据和栈增长的方向可以是相同，也可以是相反；诞生不同的策略。

预留空间是正常的做法，就像生活中不知道数量的情况下会多留点空间；但是这个有个致命的缺点，就是很难预测究竟需要预留多大的空间，预留多了是种浪费；预留少了没解决根本问题；老王苦思冥想，终于想出了个办法，参考家里的密室，横截面不能扩张，那就往高度上扩张；老王在土地上搭建一层架子，架子上也铺上土，当种菜溢出自己地盘的时候，就把蔬菜移植到架子上面，这样就便于管理了。

那类比到计算机系统中，内存地址不够了怎么办？？？我们不能在上面搭建一层架子；但是我们考虑搭建架子的本质是把蔬菜放到另一片内存中，相当于扩展了内存，因此我们想起来硬盘；我们可以把程序整个加载到硬盘上，当物理内存有足够的空间时，再把程序加载回内存运行，这就是所谓的“交换”。
交换的这种方式存在这很大的问题，一个程序被置换出去后，不知道要等多久才能等到足够的空间运行；效率低下；还有个问题，如果超出了整个物理内存，再怎么置换也没用。
如果可以把程序变成一个个可执行的单元，执行完一个单元，后面的单元就把前面单元地址覆盖掉；这样就不会出现程序空间不够的情况，这个办法就是所谓的“重叠”；但是程序的切分需要用户管控，相当于把内存管理机制暴露给了用户，这是很危险的，这个办法行不通。

闲置空间管理

老王是个追求完美的人，他种了很多蔬菜，但是封地依然有很多没有利用的空地，老王需要很好的统计，规划这些空地。老王想了良两种办法：
（1）位图法：
老王为每个种植蔬菜的地址单元分配一个字位，用1表示已占用；0表示空闲，这样就形成了一个位图；0表示所有的空闲地址；当空闲地址种植蔬菜时，由0改为1，变成已占用；当蔬菜生熟收割后，地址回收，相应的字位由1变为0，表示空闲。
（2）链表法：
老王将分配的地址用链表连接在一起；比如，青菜–>空地–>番茄–>空地；每个节点记录节点的地址；当需要种植蔬菜时，则遍历链表找到空闲的地址种植，链表进行相应的修改。

问题暴露

经历了一年的时光，老王也种植了一年蔬菜，老王决定做下总结，把经验分享给后来人；从固定分区到非固定分区到交换内存管理；固定分区用于单道编程，而非固定分区和交换等用于多道编程，实现方式都是基于基址和极限的做法。
老王总结了半天，根据统计：不管是固定分区，还是非固定分区；这些策略都存在着重大的问题；其中最重要的就是空间浪费和程序大小受限。随着不停的回收分配，内存中的碎片越来越多；很多小碎片无法满足种植的需求，浪费了；

由于这些碎片处于进程空间的外面，因此这种碎片化过程也叫做“外部碎片化”。随着进程的进进出出，外部碎片将浪费大量的内存空间；当然可以采取一定的策略降低外部碎片，比如每次分配新进程的时候，挑选最合适的空间分配，这可以在一定程度上减轻外部碎片。
还有种办法是可以进行碎片整理，通过交换，把碎片合并在一起；但交换效率非常低。

分页管理

上述整个的做法，都是把程序整个加载到内存里。老王把整个区域都种植一种蔬菜，但是每种蔬菜的种子数量不相同，这就会导致外部碎片的存在；老王想到了一种办法，为啥每次都要以蔬菜种子的数量来要求土地，而不是用土地来要求蔬菜种子的数量。

此外，上述程序增长的极限在于物理内存的大小；如果一部分一部分的加载程序，程序的增长极限就被扩大了。

想到这里，老王开始实施自己的想法，他把整个封地按照一定的大小，划分成很多块，每一小块叫做一个分页。

有了分页之后，老王的种植变的更加容易管理；他可以在每一页上种植任何自己想吃的蔬菜；比如在第1号页上种植土豆，在第2号页上种植番茄，如果老王需要土豆种植量增大，但又没有额外空间了，那么可以把2号页上的番茄移植成土豆。

在计算机操作系统中；程序被分成一页页的，每个程序都可以运行一部分页在内存中，当需要运行程序其他部分时，会把其他也加载到内存；如果没有额外的内存空间，则会把当前一些页置换到硬盘中，空出内存给运行的程序使用；这种方法下，程序可以超出物理内存实际的限制大小。

分页地址翻译

有了分页后，老王如果管理这些分页，并且知道每个分页上种植的蔬菜，而不是每天都要走一遍整个封地。老王对页面进行编号，从0开始；从上述的基址和极限，我们知道，分页的地址主要分为两块：页面号和页内偏移地址。

分页系统首先要知道的是该页面是否存在物理内存中，如果存在，对应的物理页面号是哪个？如果不存在，则产生缺页中断，并将虚页从磁盘加载到内存，然后将分配的物理页面号返回。
由于虚页和物理内存真实的页面是同样大小，因此地址翻译只需要把虚页转换到物理页，页内偏移地址无需改变。
分页内存管理中，不光需要知道页号，还需要知道该页面是否在物理内存中；此外页面有没有修改过，有没有被访问过，都需要保存这些信息；因此诞生了页表的概念；
页表在内存管理的地位十分重要，根本功能是提供从虚拟页面到物理页面的映射。比如32位寻址的虚拟地址，如果页面大小为4KB，则虚拟页面最多可以达到$ 2^{20} $，也就是页表记录条数最大为：$ 2^{20} $。

现在老王有了自己的页表，页表里记录了虚拟页面号到物理页面号的映射，并且记录了页面的偏移地址；比如老王的页面上记载了虚拟页面0种植了土豆，并且土豆的偏移地址为页面的一半；这条记录就代表了物理页面a上面种植了土豆，并且整个页面从起始地址到页面一半处种植了土豆，剩余的一半页面空闲着；

通过这个案例，可以看出，分页管理把外部的碎片转移到了页内，由于分页的粒度比分区的更细，从数学上看，平均浪费空间为半个分页，因此浪费的空间比分区要好很多。

那分页系统还有其他缺点吗？？？
有，缺点就是页表很大，占用了大量的内存空间。汉朝没有纸张，都是通过竹简和绵帛来记录的，老王一穷二白，只有封地，因此只能把页表记录在土地上；因此页表太大也会占用大量的内存空间。

页表

老王参考分页的做法，把页表也进行了分页；就是“多级页表”的概念。

操作系统中，顶级页表映射到一级页表，然后一级页表映射到二级页表，依次映射；这样当加载页表时，可以先加载顶级页表，根据一层层映射把需要的页表加载到内存，不用的页表放在硬盘上，这样就可以支持多级页表；
但是多级页表增加了地址翻译的次数，每次操作数据，都需要进行多级的地址翻译；内存访问的速度明显下降。
多级页表通过增加级数来降低页表的内存空间；有办法不增加级数来降低页表的内存空间吗？？？使用反转页表，正常页表存储的是虚拟内存到物理内存的映射，但是虚拟内存空间要远远大于物理内存；这个时候反转页表，保存物理内存到虚拟内存的映射，由于物理内存较小，这样空间大大减少；但是CPU发出的地址是虚拟地址，反转列表造成了查询的困难；这时候可以通过虚拟页面到物理页面的散列来提升查询效率。
页表的形式也是不断的演变，针对不同的系统需求页表会有不同的演变需求。

翻译快表

在多级页表的情况下，地址翻译的速度大大降低，影响了内存的访问速度；由于程序的时空局限性，我们可以将页表的翻译结果存在缓存中，缓存的速度要高于内存的速度，在缓存命中的情况下，内存的读写速度将会提高；这种将翻译结果放在缓存的结果，就叫“翻译快表”。在翻译快表的情况下，如果快速的查找到虚拟页面是否存在翻译快表中；这个时候只能一个记录一个记录的按顺序查询，如果翻译快表中不存在页面，则每次都需要按顺序查询；时间消耗巨大。
基于这种情况，软件已经无法解决根本问题，只能把问题交给硬件；硬件为每条记录配备一套电路，当翻译快表比对时，是同一时间比对所有记录；这样会在第一时间获得比对结果。

页面更换算法

老王现在已经有了页表，有了页面内存管理；老王又出现了一个问题：土地有了，房子有了，蔬菜也有了，但是没有钱，买不了衣服等生活用品；为了赚更多的钱满足生活需要，老王决定把种的蔬菜卖掉；为了利益最大化，老王需要卖掉当季流行的蔬菜，但当季流行的蔬菜变化很快；老王需要一种策略可以很快的替换页面，种植流行的蔬菜。

老王的问题就涉及到了页面置换算法，页面置换算法的根本目的，是要增加页面的命中率；从人类哲学的层次来看，页面置换算法主要分为两类：公平算法和非公平算法。
公平算法：

随机算法
先来先出算法
第二次机会算法
时钟算法

非公平算法：
最有算法
NRU算法
LRU算法
工作集算法

这些算法就不一一解释了。

段式内存管理

老王把封地管理的有条不紊；分页内存管理被老王用的炉火纯青；一切都很顺利，但是这个时候问题又来了；老王又病了，大夫说长期不吃肉，抵抗力下降。老王寻思着大夫的话，决定在封地上养写鸡鸭。
于是，老王划了两块连在一起的地来养鸡鸭；鸡鸭各占一块；由于缺少养家禽的经验，鸡鸭繁殖的速度很快，导致划分的土地不够鸡鸭生存，鸡鸭把周围的蔬菜都糟蹋了。

在操作系统中，编译器的工作过程经常需要保持多个数据结构：常数表，语法分析树，代码段，调用栈等；每个数据结构都是独立的增长，从而造成了内存空间的变化。如果编译器只在一个虚拟空间中活动，那么所有数据结构的增长可能会相互碰撞，导致无法增长，编译失败。
这就是分页系统的缺点；虚拟空间的大小受寻址宽度的限制而无法增长；那剩下的办法就是让一个程序使用多个虚拟空间。

老王把封地参考分区的做法，分为多个段；一个段占用一个虚拟地址空间；把一个程序分为多个段，不同的段运行在不同的虚拟内存中；为了区分不同的段，我们有了段号和段内偏移地址。段的个数非常少，因此段表的尺寸非常小。