每当我们安心的使用LINUX系统或者在编写C语言的时候，安心的使用malloc或者free的时候，我们很少关注过其底层的内存是怎么工作的，CPU是如何获取从主存中获取数据的，我们的寻址是不是可以直接寻找到对应的数据，还是通过某种转化机制。实际上，对于每一个进程，它所能接触到的地址都不是实际的物理地址，而是通过虚拟地址进行映射而来的。那么，这篇博客就要讲述一下虚拟存储器是一个什么东西。
第一篇会从硬件和操作系统的角度来说明虚拟存储器是个什么东西。
第二篇会从动态存储器，从程序应用的角度重点讲述(malloc和free的相关机制)。
闲话少说，你将在这篇博客里面看到如下内容： 
1.1 什么是虚拟地址和物理地址：
首先，要说虚拟地址就要先说一下物理地址。可以理解我们的主存被组织成一个由M个连续的字节大小的单元组成的数组。而每一个字节都有一个对应的地址，这样的地址就被称作是物理地址。那么，我们的程序是不是可以直接可以接触到物理地址，就是是不是可以直接从物理地址当中获取数据。答案明显是不是的，我们先来分析一下如果所有的进程直接访问同一块连续的物理地址有什么弊端呢？
1. 主存的容量有限。虽然我们现在的主存容量在不断上升，4G，8G，16G的主存都出现在市面上。但是我们的进程是无限，如果计算机上的每一个进程都独占一块物理存储器(即物理地址空间)。那么，主存就会很快被用完。但是，实际上，每个进程在不同的时刻都是只会用同一块主存的数据，这就说明了其实只要在进程想要主存数据的时候我们把需要的主存加载上就好，换进换出。针对这样的需求，直接提供一整块主存的物理地址就明显不符合。
2. 进程间通信的需求。如果每个进程都 独占一块物理地址，这样就只能通过socket这样的手段进行进程通信，但如果进程间能使用同一块物理地址就可以解决这个问题。
3. 主存的保护问题。对于主存来说，需要说明这段内存是可读的，可写的，还是可执行的。针对这点，光用物理地址也是很难做到的。
针对物理地址的直接映射的许多弊端，计算机的设计中就采取了一个虚拟化设计，就是虚拟内存。CPU通过发出虚拟地址，虚拟地址再通过MMU翻译成物理地址，最后获得数据，具体的操作如下所示： 
利用了虚拟内存就可以比较有效的解决以上三个问题，在每一个进程开始创建的时候，都会分配一个虚拟存储器（就是一段虚拟地址）然后通过虚拟地址和物理地址的映射来获取真实数据，这样进程就不会直接接触到物理地址，甚至不知道自己调用的那块物理地址的数据。
1.2 地址空间的概念
为了能更好的理解下面的所说的地址翻译等知识点，这里说一下地址空间的概念。首先，对于32位的计算机，每一个地址所对应的数据空间是32位，也就是四个字节。那么如果一个地址可以用32位表示，那么对于这32位地址的所有可能就是:2
下面补充一下几个常见的单位： 
.
1.3 地址分页的概念
对于一整块连续的内存，直接连续使用也是不太符合实际的。于是，就有分页的概念。将1024个地址分成一页，通过访问页来访问数据。那么有了页就要有如何寻找页的概念了。我们通过每一页的首地址作为页入口，即(PTE)来检索页。那么，对于这些PTE，我们也需要一个专门的数据结构来进行管理，这样的数据结构就是页表(page table)。
1.4 虚拟存储器的缓存作用
这里先说明一下DRAM,SRAM和磁盘的速度区别，对于速度：
SRAM>DRAM>>磁盘
SRAM的速度是DRAM的10倍，DRAM是磁盘速度的百来倍，所以SRAM常作为CPU上L1，L2，L3缓存的材料，DRAM作为主存，针对于SRAM和DRAM，cache MISS的惩罚而言，DRAM的惩罚更大，因为DRAM的读写速度是磁盘的几百倍，所以利用在DRAM的缓存的作用就更大了，针对于虚拟存储器的缓存作用可以用下图所示： 
虚拟存储器中的块分为：未分配的，缓存的，未缓存的。
未分配的：顾名思义，这一块的虚拟存储器不映射于任何块。
缓存的：这一块的虚拟存储器映射于已经存在于DRAM中的物理页。
未缓存的：这一块的虚拟存储器映射于存在于磁盘中的虚拟页。（也就是要使用就要把磁盘中的虚拟页替换到DRAM中的物理页，会发生Page Fault ）
有效和无效通过一个valid bit(有效位)来进行判断 
这里就要再重复说明一下了：页表，PTE,物理存储器，虚拟存储器分别放在什么地方。
DRAM里面有：页表，PTE，物理存储器
磁盘里面：虚拟页表
那么对于缓存来说：就有页命中，和页不命中两种情况
页命中：在图中就类似于VP1,VP2,这类的页表，直接缓存在DRAM中的物理存储器中，可以直接从DRAM中获取速度就快了。
页不命中：就是访问页表中未缓存的PTE，如VP3,VP6之类，如下图所说明的情况 
虚拟地址想访问VP3的时候，发现VP3未在缓存中，发生page fault.利用替换算法(替换算法可能是FIFO，或者LRU)将物理存储器中的一个VP3从物理存储器中导出，VP4从磁盘导入DRAM中。此时,PTE3就变成了已缓存，PTE4变成了未缓存。这时候在进行地址翻译，就变成页命中了。
可见，page fault从磁盘导入的效率是非常低的，但是由于局部性原理，进程往往更多的在较小的活动页面上工作，很少有大跨度的访问内存，使得page fault产生的可能性降低。页命中的可能性提高。
获取数据的效率就快了很多。
1.5虚拟存储器的其它作用：
正如上面所说的只使用物理地址的弊端，虚拟存储器可以解决部分的问题。
1.简化共享：利用虚拟地址来映射物理地址，使得可以让多个进程的不同虚拟地址映射同一块物理地址，比如类似于printf，这一类常用的库，不会把printf的代码拷贝到每一个进程，而是让不同进程都使用同一块printf.
2. 虚拟存储器作为存储器保护的工具，在虚拟存储器里面可以设计该PTE是可读，可写，还是可执行的。如果一旦出现只读的PTE被写入了，CPU就会发送出现segmentation fault(段错误)但并不会影响到实际存放数据的物理内存， 
地址翻译
地址翻译作为虚拟存储器中最难的一块也不为过，本人也是花了好大的功夫才这块东西吃透。
1.首先先来了解地址翻译的目的是什么，地址翻译的目的是通过MMU将虚拟地址翻译成物理地址。
那么虚拟地址的那么多个地址位又分成那些部分呢？，我先放上一张符号说明图来为后面的地址翻译提供便利： 
下面以只有一级页表为例：
下面的转化图将说明虚拟地址到物理地址的一个过程 
无论是虚拟地址还是物理地址都被分成两个部分，一个页号(PN)，用来寻找对应的存储页，还有一个偏移量(PO)用来寻找在对应页中的偏移量。对于偏移量来说，虚拟页的偏移量和物理页的偏移量是相同的。那么，说明我们所需要的转化就是从虚拟页号转化到物理页号。
这也就意味着我们可以使用一个小trick加速翻译的速度，分别将v*n,VPO分开传输，v*n传输到MMU进行翻译，VPO直接传输到L1 cache进行偏移检索，而不是等到v*n翻译成PPN再进行翻译，这个称作是优化地址翻译
什么下就是翻译页号了，翻译页号的步骤就是通过v*n在页表中进行寻找找到对应的PTE,如果发现PTE的有效位为0,说明页面不存在，就出现缺页错误，重新加载页面到物理存储器中，然后设有效位为1（上面的缺页错误说的就是这个问题）。反之，有效位为1，说明页命中，取出PPN和VPO一合，得到物理地址，下图分别说明了，缺页错误和页命中两种情况的翻译情况： 
- 但是通过DRAM中的页表来进行地址翻译的速度有可能太慢了，无法满足速度的需求。这个时候就要TLB中派上用场了，TLB作为SRAM的一部分，速度是快于页表查询的。TLB的实际作用，做一个映射，将v*n在TLB中寻找，找到对应的PPN。那么问题来了，TLB是怎么做的映射的呢？这时候就要说明一下v*n对于TLB来说可以分成那几块，请看下图：
可以看见v*n被分为(TLBT:TLB标记，TLBI:TLB索引)
这时候再来看看TLB构成是什么样的呢？
这里展示的是一个四路组相连的一个TLB 
TLBI的两位就说明该选TLB的那一组，前面的6位TLBT说明标记位。
3.二级或者多级页表怎么处理
二级页表或者多级页表都是为了更快的检索和更节约空间，请先看下面一个二级页表的例子： 
首先二级页表并不复杂，就相当于多了一次映射，我们做一个简单的计算来说明二级页表容量关系，在二级页表中，一个PTE指向的是二级页表中，1024个PTE的一页，那么二级页表中的一个PTE也就指向虚拟存储器中的一页，也就是1KB的地址空间，一个地址中有32位，也就是4个字节，那么在二级页表中的一个PTE所包含的容量就为4KB字节。对于一级页表而言，一个PTE就代表着4MB字节的空间，1K的一级页表就代表了4GB字节的空间，4GB已经是现在很多内存条的容量了。
那么对于多级页表，一个v*n又是怎么分配和映射的呢。相信下面的一张图就可以说明清楚。 
- 物理地址怎么处理
那么，现在我们得到了物理地址，那么通过物理地址又怎么在物理存储器中寻找到我们想要的数据呢？
先来看一下我们的物理地址分成那几个部分
可以看到物理地址被分成了三个部分：CO(块偏移)，CI（索引），CT（标签）三个部分
那么物理存储器又长什么样子呢？请看下图： 
物理地址先找到CI索引，找到对应的set集合，然后判断这个集合的valid bit是否等于一并且tag是否与CT一致。如果这些条件都符合，在通过CO偏移找到想要的数据。
最后：
翻译实例：
首先，我们的翻译实例是基于一级页表之间的转换，关于虚拟地址以及物理地址的长度及位置如下图所示： 
好了，信息完全。
接下来，我们就来实际翻译的虚拟地址。
我们翻译的地址为:0x03d4 
我们得到了VPO，只需要翻译出PPN就好。
接下来我们通过TLBI,TLBT来寻找对应的PPN。首先，可以知道TLBI为0x3，在TLB可以找到3为这个位，对应的标签TLBT也为0x3,很高兴我们找到TLBT为0x3的位，并且里面的PPN有值，值为0D,这个0D就是我们先要的PPN了，
这时候我们就可以得到物理地址为PPN=0x0d,PPO=0x14,物理地址为：0x354
如下图： 
我们得到了CO=0x0,CI=0x5,CT=0x0d
我们先通过CI找索引，然后再通过CT对照，很高兴，我们发现标记位相同，都为0x0D,且有效位为1，于是乎我们再通过CO=0的偏移，取出了数据0x36。嘻嘻嘻。
这个就是翻译的全过程。
当然针对于，不同的操作系统中，在通过虚拟地址进行页面通信的时候还有特性使用：例如写时拷贝这个特性，在这里就不赘述了，需要了解的人可以查找资料来了解。
虚拟存储器的概念与工作原理就到这了。
下一篇我们将讲述动态存储器的特点（即malloc和free的实际原理）。
Reference:《深入理解计算机系统》