计算机系统学习4:虚拟内存

一.概述

计算机系统中，CPU是绝对的核心，主要负责执行指令，从而实现计算机的功能。CPU的执行速度极快，有多快呢？以ns为单位。相比而言，内存比CPU慢100倍，硬盘比CPU慢100多万倍。但是，CPU有个很大的缺点，就是它的脑容量极小，不能保存指令，因此指令都保存在硬盘中。CPU每次执行指令的时候，都会将硬盘中的指令加载到内存中，然后执行加载到内存中的指令。那么为什么用硬盘存储指令呢？因为CPU和内存在断电的时候，全部都会清零，而硬盘则不会。

CPU每次执行命令的时候，都需要存内存中读取指令，尽管内存只比CPU慢100多倍，但是当指令多了之后，内存的速度仍然不足。而程序的局部性原理的出现则能够比较好的解决这个问题。

程序的局部性原理有2个,分别是时间局部性原理和空间局部性原理。

时间局部性原理：如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。
空间局部性原理：一旦程序访问了某个存储单元，则不久之后，其附近的存储单元也将被访问。

由于局部性原理的存在，因此可以将CPU经常访问的同一块区域的东西都缓存到CPU中，CPU每次读写命令和数据的时候，先找缓存，如果缓存没有，再找内存，这样就可以大大提高执行速度。

但是这种方法也有缺点，那就是当操作系统在做程序切换的时候，缓存就会失效，因为2个程序之间没有什么联系，局部性原理不起作用，所以需要重建缓存。

二.虚拟内存

CPU所在的系统是一个批处理的计算机系统，操作系统收集了一批任务之后，就会把这一批任务都逐个加载到内存中（注意一个新装入的程序会完全覆盖老的程序），让CPU去顺序执行，但是，有时候CPU不止会在内存中取指令去执行，有时候也会有IO相关的操作，这时候内存和硬盘都在疯狂的Load数据，但是这个时候CPU就会空闲下来了，这样的话，CPU的利用效率就不高，因此，操作系统就得有一套机制，能够在内存中多加载几个程序，保证CPU执行一个程序被IO堵塞的时候，可以运行另外的程序，这个机制就称为分时系统，它的特点是多个程序并发执行，内存中一次存入尽可能多的程序，同时程序在内存中是独立可区分的。

那么，内存中加载多个程序的时候，内存如何分配呢？举个例子：

图1 内存紧缩

如图1所示，具体的内存分配的过程是这样的：

(1) 内存一共90k, 一开始有三个程序运行，占据了80k的空间，剩余10k

(2) 然后第二个程序运行完了，空闲出来20k , 现在总空闲是30K, 但这两块空闲内存是不连续的。

(3) 第4个程序需要25k, 没办法只好把第三个程序往下移动，腾出空间让第四个程序来使用了。

注意，在这个分配过程中，我们分配的是实际的物理地址，我们再举个例子，具体分析一下使用直接分配物理地址会不会出现什么问题？

图2 内存加载2个程序

如图2所示，第一个程序被装载到了内存的开始处，也就是地址０，运行了一会，遇到了一个IO指令，在等待数据的时候，操作系统立刻让CPU开始运行第二个程序，这个程序被装载到了地址1000处，刚开始运行的好好的，突然就来了这么一条指令：

MOV eax [100] //把寄存器eax中的数据加载到地址100中

但是，我们会看到，在程序1中也有同样的一条命令：

MOV eax [100] //把寄存器eax中的数据加载到地址100中

这2个程序操作了同一个地址，数据会被覆盖掉，为什么呢？这个系统的程序引用的都是物理的内存地址，在批处理系统中，所有的程序都是从地址0开始装载，现在是多道程序在内存中，第二个程序被装载到了10000这个地址，但是程序没有变化啊，还是假定从0开始，自然就出错了。

那么如何处理这个问题呢？静态重定位。静态重定位是指：操作系统在装载的时候修改一下第二个程序的指令，把每个地址都加上1000（即第二个程序的开始处），原来的指令就会变成MOV eax [1100]。

但是，内存紧缩的时候，执行静态重定位的话，会非常的麻烦，因此，我们考虑是不是能在运行时进行地址重定位呢？

首先得记录下每个程序的起始地址，可以让阿甘再增加一个寄存器，专门用来保存初始地址。例如对第一个程序，这个地址是 0 ，对第二个程序，这个地址是1000，运行第一个程序的时候，把寄存器的值置为0 ，当切换到第二个程序的时候，寄存器的值也应该切换成10000。只要遇到了地址有关的指令，都需要把地址加上寄存器的值，这样才得到真正的内存地址，然后去访问。这个过程就是动态重定位。

其实，CPU将地址都抽象成了逻辑地址，在CPU内部有一个封装的模块，叫内存管理单元（MMU）,不仅有记程序开始的地址的寄存器，记录程序偏移量的寄存器，还有计算内存地址的方法。如图3所示：

图3 内存管理单元

注意，这个内存管理单元是属于CPU的，而不是属于内存的。

内存分配和内存紧缩的问题解决了，多个程序可以良好的在内存中运行，但是如果程序太大怎么办呢？
分块装入程序。

分块装入程序是指：对每个程序，不要全部装入内存，把一个程序分成一个个小块，然后按块来装载到内存中，例如先把最重要的代码指令装载进来，在运行中按需装载别的东西。由于程序局部性原理的存在，程序会倾向于在这一块或几块上执行，性能上应该不会有太大的损失。这一个个小块叫页框（page frame） ，每个4k大小，装载程序的时候也按照页框大小来，这些页框对应的就是一块块的程序。

既然一个程序可以用分块的技术逐步调入内存，而不太影响其性能，那么一个程序就可以做的比实际的内存大。我们可以给每个程序都提供一个超级大的空间，例如4G，只不过这个空间是虚拟的，程序中的指令使用的就是这些虚拟的地址，然后MMU把它们映射到真实的物理的内存地址上（这就是增加一个中间层来解决问题的思想）。同时，将虚拟的地址也得分块，就叫做页（page）, 大小和物理内存的页框一样，这样好映射。虚拟页和物理页构成了页表（注意，页表在内存中）。在分配的时候，操作系统要记录哪些页已经被装载到了物理内存，哪些没有被装载，如果程序访问了这些没被装载的页面，操作系统要从内存中找到一块空闲的地方，如果内存已满，只好把现有的页框置换一个到硬盘上。这个机制就是虚拟内存机制中分页的基本原理，其结构如图4所示：

图4 虚拟内存：分页

在图4中，虚拟地址的#4页，在物理内存中不存在，如果程序访问第4页，就会产生缺页的中断，由操作系统去硬盘调取。

在CPU处理的指令或者程序中，有的指令是代码段，有的指令是堆栈段，有的是共享段，如果将其分开，那么处理起来就会很方便，同时也有利于保护这些程序。因此操作系统将每个程序进行标准化，分成代码段、数据段和堆栈段等等，同时记录下每个段的开始地址和结束地址，每个段的保护位。而在每个段的内部，仍然按照分页系统来处理。这就是段页结合，如图5所示。程序员在写程序的时候，面向的是分段；而硬件处理的时候，面向的是分页。

图5 段页结合

在图5中，一个虚拟的内存地址来了以后，首先根据地址中的段号先找到相应的段描述表，其中有页表的地址，然后再从页表中找到物理内存，再从内存中读取指令。如果有程序想非法的访问内存，例如一个不属于他的段，操作系统就立刻给他一个警告：Segmentation Fault !

三.页面置换算法

内存是有限的，不可能把所有的页面都装进来，缺页时需要进行页面置换。页面置换的背后是一个通用的问题，例如Web服务器的缓存，Redis ，memcached 的缓存等。
以下谈谈3个页面置换算法。

FIFO(先进先出)
如图6所示，假设只有3个物理页面，逻辑页面的访问次序是：7 0 1 2 0 3 0 4

图6 FIFO算法示例

很明显，按照FIFO算法，虽然一个页面（页面0）被频繁访问，他还是很有可能被置换出去，因此实现效果不是很好。
LRU算法（最近最少使用）
如图7所示，假设只有3个物理页面，逻辑页面的访问次序是：7 0 1 2 0 3 0 4

图7 LRU算法示例

虽然这种方法实现页面置换的效果非常好，但是需要维护一个页面的栈，并且需要把某一个页面从栈中提到栈顶，用硬件实现开销大，因此，引入它的一种近似算法：Clock算法
LRU算法的近似实现：Clock算法
算法：
（1）每个页加一个引用位, 默认值为0，无论读还是写，都置为1
（2）把所有的页组成一个循环队列
（3）选择淘汰页的时候，扫描引用位，如果是1则改为0（相当于再给该页面一次存活的机会），并扫描下一个；如果该引用位是0，则淘汰该页，换入新的页面
如图8所示：假设只有3个物理页面，逻辑页面的访问次序是：3 4 2 6 4 3

图8 Clock算法
这种方法实现页面置换的效果虽然没有LRU算法好，但是近似于LRU算法，同时硬件实现大大简化，因此多用这种方法。