操作系统 虚拟内存技术
参考： https://www.bilibili.com/video/av31584226/?p=16
在此申明此文章全部截图来源于上面链接的视频，如有侵权，立即删除。
前面已经介绍过了操作系统的内存管理的基础知识，当时我们对内存扩充的覆盖和交换技术都做了详细的讲解，接下来我们对内存扩充的虚拟内存技术再进行详细的了解。
下面是讲解目录：
首先我们来回忆一下传统的存储管理方式：
上面的都已经讲过了，大家可以看着目录回忆一下：
传统存储管理有的一个缺点：很多用不到的数据也会长期地占用内存，导致内存利用率不高。
传统存储管理还有以下几个特征：
1.一次性：作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：
（1）作业很大时，不能全部装入内存，导致大作业无法运行：(比如大型的游戏)
（2）当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。
2.驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。
然后，可以使用虚拟存储技术来解决上面的问题。
虚拟存储技术是基于局部性原理提出来的，局部性原理前面已经在讲基本分页存储的逻辑地址转换时的快表机构中进行了详细的叙述，在这里再做简单的叙述。
局部性原理：
时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次被执行；如果某个数据被访问过，不就之后该数据很有可能再次被访问。（因为程序中存在大量的循环）
空间局部性：一旦程序访问了某个存户单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的）。
时间局部性和空间局部性统称为局部性原理。
比如下面这段代码：
大家可以从这里理解一下上面说的话。
然后就有了高速缓冲技术，高速缓冲技术的思想就是：将近期会频繁访问到的数据存放到更高速的存储器中，暂时用不到的数据放在更低速存储器中。
然后大家可以看下面这个图：
有点计算机基础知识的人应该一看就能懂这个阶梯图吧。通过这个图可以更加深刻地理解高速缓冲技术的意义。常用的数据一般都比较少，所以往高层放。不常用的数据往底层放，要用的时候再取出来。
前面文章说的快表机构就是将近期常访问的页表项副本放到更高速的联想寄存器中。
下面是虚拟内存的运行：
基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。
（看完这段话，我有了以下理解：比如你运行一个大型软件，如matlab或者vs，由于它们太过庞大，不可能把所有的功能都全部加载进我那小小的内存当中，所以这些软件应该是把常用的功能加载进内存当中，这样加载速度快，不会影响用户体验。而不常用的功能放置在外存中，但是在内存中有地址指向外存的地址。所以当使用不常用的功能时，加载速度会比较慢，因为它要从磁盘中读取到内存当中并且运行（论ssd的好处？）。我猜测这应该和虚拟内存技术类似吧，或者OS有更成熟的方案来处理这类事件？） 经过我的思考，发现我这段话没什么依据，所以就不要理它了，但是留在这里，以后学习相关内容时能产生联想和思考。
虚拟内存是操作系统虚拟性的一个体现，实际的物理内存大小没有变，只是在逻辑上进行了扩充。
虚拟内存的最大容量是由计算机的地址结构（cpu寻址范围）确定的
虚拟内存的实际容量=min(内存和外村容量之和，cpu寻址范围)
如：
某计算机地址结构为32位，按字节编址，内存大小为512MB，外存大小为2GB，则
虚拟内存的最大容量为2的32次方B=4GB
虚拟内存的实际容量=min(2的32次方B，512MB+2GB)=2GB+512MB
虚拟内存有以下三个主要特征：（和传统的差不多对应）
多次性：无需再作业运行时一次性全部装入内存，而是允许被多次调入内存。
对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出
虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际容量。
那讲了那么多虚拟内存技术的概念，我们肯定会想怎么实现这个虚拟内存技术啊？
虚拟内存技术，允许一个作业分多次调入内存。如果采用连续分配方式，会很不方便实现（进程的地址连续）。因此，虚拟内存的实现需要建立在离散分配的内存管理方式基础上。
回忆一下传统的离散分配存储管理：
1.基本分页存储 2.基本分段存储管理 3.基本段页式存储管理
其对应虚拟内存的实现就是：
1.请求分页存储管理 2.请求分段存储管理 3.请求段页式存储管理
上面两者的主要区别在于：
1.在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。（即操作系统要提供请求调页（或请求调段）功能）
2.若内存空间不够，由操作系统负责将内存中暂时用不到的信息换带外存。（即操作系统要提高页面置换（或段置换）功能）
接着，我们直接来看请求分页管理方式：
由前面的知识我们知道要在基本分页存储管理方式的基础上增加：请求调页和页面置换。
我们要关注的是请求分页管理方式中的
1.页表机制
2.缺页中断机构（对应请求调页功能）
3.地址变换机构
我们先来看页表机制：
1.与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是否已经掉入内存；如果还没调入，那么也需要知道该页面在外存中存放的位置。
2.当内存空间不够时，要实现“页面置换”，操作系统需要通过某些指标来决定到底换出哪个页面：有的页面没有被修改过，就不用再浪费时间写回外存（外存中有副本）。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息。
基于上述的理由，有了我们的请求页表：
对比一下和基本页表的区别，我们发现多了四个字段。
状态位：表示是否在内存当中
访问字段：表示记录最近的访问次数，或记录上次访问的时间（用于页面置换算法选择换出页面时参考）
修改位：表示页面调入内存后是否被修改（未被修改过的就不用写入外存，因为外村本来就有副本）
外存地址：此页在外存地址的位置
然后我们来看缺页中断机构：
在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。（由于要进行io操作，即页面从外村调入内存），此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。
如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外村。
缺页中断时因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断。
内中断的信号来源于cpu内部，外中断来源于cpu外部（比如io中断）。如果写过单片机就很好理解这个中断。
一条指令在执行期间，可能产生多次缺页中断。（如：copy A to B,即将逻辑地址A中的数据复制到逻辑地址B，而A、B属于不同的页面，则有可能产生两次中断）
所以，引入缺页中断机构后才能实现请求调页功能。
然后给个流程图大家自己领悟：
嗯，深知OS不易，还需努力。
然后我们来看页面置换算法：
页面的换入、换出需要磁盘io,会有较大的开销，因此好的页面置换算法应该追求更少的缺页率。（也就是让换进换出的次数尽可能少）
这里讲五种页面置换算法：
1.最佳置换算法（OPT）
2.先进先出置换算法(FIFO)
3.最近最久未使用置换算法（LRU）
4.时钟置换算法（CLOCK）
5.改进型的时钟置换算法
先来看最佳置换算法：
每次选择淘汰的页面将是以后用不使用，或者最长时间内不被访问的页面，这样可以保证较低的缺页率。
大家可以以下题进行理解：
也就是操作系统知道后面将要放入的序列之后，当内存满了之后，比如上面的意思就是：放入7，0，1页面进入内存块1，2，3.满了之后，要再放入页面2，发现内存满了，然后发现后面将要放入的序列中，先遇到0，后遇到1，最后遇到7.所以7是最长时间不使用的，所以把页面7置换出去。（前提：OS知道后面将要使用的序列顺序）
这个算法能保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面，操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。
然后我们来看先进先出置换算法：
每次选择淘汰的页面是最早进入内存的页面。
实现方法：把调入内存的页面根据带调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。
然后当使用先进先出置换算法时，由当增加内存块数，缺页次数会出现不减反增的异常现象，这就是Belady异常。
只有FIFO算法会出现Belady异常。虽然它实现简单，但是该算法与进程实际运行时的规律不适用，因为先进入的页面也有可能最经常被访问。因此，算法性能差。
嗯，后面的算法以后有机会再进行补充。
欢迎交流讨论。
文章被以下专栏收录
