一.概述
计算机系统中，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个程序如图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
图3 内存管理单元注意，这个内存管理单元是属于CPU的，而不是属于内存的。
内存分配和内存紧缩的问题解决了，多个程序可以良好的在内存中运行，但是如果程序太大怎么办呢？ 分块装入程序。
分块装入程序是指：对每个程序，不要全部装入内存，把一个程序分成一个个小块，然后按块来装载到内存中，例如先把最重要的代码指令装载进来，在运行中按需装载别的东西。由于程序局部性原理的存在， 程序会倾向于在这一块或几块上执行， 性能上应该不会有太大的损失。这一个个小块叫页框（page frame） ，每个4k大小， 装载程序的时候也按照页框大小来，这些页框对应的就是一块块的程序。
既然一个程序可以用分块的技术逐步调入内存，而不太影响其性能，那么一个程序就可以做的比实际的内存大。我们可以给每个程序都提供一个超级大的空间，例如4G，只不过这个空间是虚拟的， 程序中的指令使用的就是这些虚拟的地址，然后MMU把它们映射到真实的物理的内存地址上（这就是增加一个中间层来解决问题的思想）。同时，将虚拟的地址也得分块，就叫做页（page）, 大小和物理内存的页框一样， 这样好映射。虚拟页和物理页构成了页表（注意，页表在内存中）。在分配的时候，操作系统要记录哪些页已经被装载到了物理内存， 哪些没有被装载，如果程序访问了这些没被装载的页面，操作系统要从内存中找到一块空闲的地方， 如果内存已满， 只好把现有的页框置换一个到硬盘上。这个机制就是虚拟内存机制中分页的基本原理，其结构如图4所示：
图4
图4 虚拟内存：分页在图4中，虚拟地址的#4页， 在物理内存中不存在，如果程序访问第4页，就会产生缺页的中断，由操作系统去硬盘调取。
在CPU处理的指令或者程序中，有的指令是代码段，有的指令是堆栈段，有的是共享段，如果将其分开，那么处理起来就会很方便，同时也有利于保护这些程序。因此操作系统将每个程序进行标准化，分成代码段、数据段和堆栈段等等，同时记录下每个段的开始地址和结束地址，每个段的保护位。而在每个段的内部，仍然按照分页系统来处理。这就是段页结合，如图5所示。程序员在写程序的时候，面向的是分段；而硬件处理的时候，面向的是分页。
图5
图5 段页结合在图5中，一个虚拟的内存地址来了以后，首先根据地址中的段号先找到相应的段描述表， 其中有页表的地址， 然后再从页表中找到物理内存，再从内存中读取指令。如果有程序想非法的访问内存，例如一个不属于他的段， 操作系统就立刻给他一个警告：Segmentation Fault !
三.页面置换算法
内存是有限的，不可能把所有的页面都装进来，缺页时需要进行页面置换。页面置换的背后是一个通用的问题，例如Web服务器的缓存，Redis ，memcached 的缓存等。 以下谈谈3个页面置换算法。
FIFO(先进先出) 如图6所示，假设只有3个物理页面，逻辑页面的访问次序是：7 0 1 2 0 3 0 4
图6
图6 FIFO算法示例很明显， 按照FIFO算法， 虽然一个页面（页面0）被频繁访问， 他还是很有可能被置换出去，因此实现效果不是很好。 LRU算法 （最近最少使用） 如图7所示，假设只有3个物理页面，逻辑页面的访问次序是：7 0 1 2 0 3 0 4
图7
图7 LRU算法示例
虽然这种方法实现页面置换的效果非常好，但是需要维护一个页面的栈， 并且需要把某一个页面从栈中提到栈顶，用硬件实现开销大，因此，引入它的一种近似算法：Clock算法
图8
图8 Clock算法 这种方法实现页面置换的效果虽然没有LRU算法好，但是近似于LRU算法，同时硬件实现大大简化，因此多用这种方法。
总结：
本文主要阐述了以下几个问题：
CPU执行指令的过程
批处理系统
地址重定位
分块
分页
分段
虚拟内存
页面置换算法
参考资料
刘欣，码农翻身，CPU阿甘
刘欣，码农翻身，CPU阿甘之烦恼
水平有限，错误和不妥之处请指出，谢谢~
网友评论