虚拟存储器作为现代操作系统中存储器管理的一项重要技术，实现了内存扩充功能。但该功能并非是从物理上实际地扩大内存的容量，而是从逻辑上实现对内存容量的扩充，让用户所感觉到的内存容量比实际内存容量大得多。于是便可以让比内存空间更大的程序运行，或者让更多的用户程序并发运行。这样既满足了用户的需要，又改善了系统的性能。
虚拟内存是操作系统物理内存和进程之间的中间层，它为进程隐藏了物理内存这一概念，为进程提供了更加简洁和易用的接口以及更加复杂的功能。
虚拟内存作为中间层
我们可以将虚拟内存看作是在磁盘上一片空间，当这片空间中的一部分访问比较频繁时，该部分数据会以页为单位被缓存到主存中以加速 CPU 访问数据的性
能，虚拟内存利用空间较大的磁盘存储作为『内存』并使用主存储缓存进行加速，让上层认为操作系统的内存很大而且很快，然而区域很大的磁盘并不快，而很快的内存也并不大。
虚拟内存
Linux为什么需要虚拟内存:
- 为应用程序提供看起来容量足够大且访问足够快的存储。
- 通过共享代码库以减少物理内存的开销。让改动尽可能的少。
- 通过分配连续的虚拟内存（物理内存上不一定连续） 简化内存的连接、分配过程。
- 通过给各个进程分配不同的虚拟内存空间实现内存访问上的隔离，提供了一定的安全性。
拓展：
当我们在 Linux 中调用
fork创建子进程时，实际上只复制了父进程的页表。
问题:question:
- 当有一个作业很大，超过了内存的总容量，作业不能全部装入内存怎么办？
- 有大量作业需要运行，但是由于内存容量不足以容纳这些所有的作业怎么办？(先执行一部分)
解决办法：
- 增加物理内存容量
- 逻辑上扩充内存容量(虚拟内存方法)
局部性原理:1st_place_medal:
程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。
- 时间局部性：访问最近访问过的空间的可能性较大。
- 空间局部性：访问当前空间周围的空间的可能较大。
局部性原理使得虚拟存储技术的实现成为可能。
基于局部性原理可知，应用程序在运行之前没有必要将之全部装入内存，而仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。程序在运行时，如果它所要访问的页(段)已调入内存，便可继续执行下去；但如果程序所要访问的页(段)尚未调入内存(称为缺页或缺段)，便发出缺页(段)中断请求，此时 OS 将利用请求调页(段)功能将它们调入内存，以使进程能继续执行下去。如果此时内存已满，无法再装入新的页(段)，OS 还须再利用页(段)的置换功能，将内存中暂时不用的页(段)调至盘上，腾出足够的内存空间后，再将要访问的页(段)调入内存，使程序继续执行下去。这样，便可使一个大的用户程序在较小的内存空间中运行，也可在内存中同时装入更多的进程，使它们并发执行。
虚拟存储器:memo:
定义
所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。
当用户看到自己的程序能在系统中正常运行时，他会认为，该系统所具有的内存容量一定比自己的程序大，或者说，用户所感觉到的内存容量会比实际内存容量大得多。但用户所看到的大容量只是一种错觉，是虚的，故人们把这样的存储器称为虚拟存储器。
虚拟存储器并非可以无限大，其容量受外存大小和指令中地址长度两方面的限制。
特征
- 多次性
- 对换性
- 虚拟性
实现方法
所有的虚拟存储器都是采用下述方式之一实现的：
- 请求分页系统
- 请求分段系统
请求分页存储管理方式
请求分页系统是建立在基本分页基础上的，为了能支持虚拟存储器功能，而增加了请求调页功能和页面置换功能。相应地，每次调入和换出的基本单位都是长度固定的页面，这使得请求分页系统在实现上要比请求分段系统简单(后者在换进和换出时是可变长度的段)。因此，请求分页便成为目前最常用的一种实现虚拟存储器的方式。
请求页表机制(基本原理)
在请求分页系统中需要的主要数据结构是请求页表，其基本作用仍然是将用户地址空间中的逻辑地址映射为内存空间中的物理地址。为了满足页面换进换出的需要，在请求页表中又增加了四个字段。这样，在请求分页系统中的每个页表应含以下诸项(配合clock置换算法)：
请求页表结构
字段说明：
- 状态位(P)：用于指示该页是否已调入内存，供程序访问时参考。
- 访问字段(A)：记录本页在一段时间内被访问的次数，或者记录本页最近已有多久时间未被访问，供置换算法在选择换出页面时参考。
- 修改位(M)：表示该页在调入内存之后有没有被修改。供置换页面时参考。未修改则无需写入外存。
- 外存地址：用于指出该页在外存上的地址，通常是物理块号地址，供调入该页时参考。
缺页中断机构
在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求 OS将缺的页调入内存。
缺页中断作为中断，它们同样需要经历诸如保护 CPU 环境、分析中断原因、转入缺页中断处理程序进行处理，以及在中断处理完成后再恢复 CPU 环境等几个步骤。但缺页中断又是一种特殊的中断，它与一般的中断相比有着明显的区别，主要表现在下面两个方面：
- 在指令执行期间产生和处理中断信号。
- 一条指令在执行期间可能产生多次缺页中断。
地址变换机构
请求分页系统中的地址变换机构是在分页系统地址变换机构的基础上，为实现虚拟存储器，再增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。下图示出了请求分页系统中的地址变换过程：
请求分页的地址变换过程
在进行地址变换时，首先检索快表，试图从中找出所要访问的页。若找到，便修改页表项中的访问位，供置换算法选换出页面时参考。对于写指令，还须将修改位置成“1”,表示该页在调入内存后已被修改。然后利用页表项中给出的物理块号和页内地址形成物理地址。地址变换过程到此结束。
如果在快表中未找到该页的页表项，则应到内存中去查找页表，再从找到的页表项中的状态位 P 来了解该页是否已调入内存。若该页已调入内存，这时应将该页的页表项写入快表。当快表已满时，则应先调出按某种算法所确定的页的页表项，然后再写入该页的页表项；若该页尚未调入内存，这时应产生缺页中断，请求 OS 从外存把该页调入内存。
请求分页的内存分配
三个问题：
-
最小物理块数的确定。先分配给进程多少物理空间它才能先正常运行。
-
内存分配策略。
-
固定分配局部置换
所谓固定分配，是指为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。所谓局部置换，是指如果进程在运行中发现缺页，则只能从分配给该进程的 n 个页而中选出一页换出，然后再调入一页，以保证分配给该进程的内存空间不变。
-
可变分配全局置换
所谓可变分配，是指先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。所谓全局置换，是指如果进程在运行中发现缺页，则将 OS 所保留的空闲物理块(一般组织为一个空闲物理块队列)取出一块分配给该进程，或者以所有进程的全部物理块为标的，选择一块换出，然后将所缺之页调入。这样，分配给该进程的内存空间就随之增加。
-
可变分配局部置换
该策略同样是基于进程的类型或根据程序员的要求，为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选择一页换出，这样就不会影响其它进程的运行。如果进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到适当程度为止。反之，若一个进程在运行过程中的缺页率特别低，则此时可适当减少分配给该进程的物理块数，但不应引起其缺页率的明显增加。
-
-
物理块分配算法
- 平均分配算法
- 比例分配算法
- 考虑优先权的分配算法
页面调入策略
问题：
-
何时调入页面
- 预调页策略，一次调入若干个相邻的页面。
- 请求调页机制，当请求的页面不存在内存，由OS将所需页面调入内存。
-
何处调入页面
将请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页而的对换区。通常，由于对换区是采用连续分配方式，而文件区是采用离散分配方式，所以对换区的数据存取(磁盘 I/O)速度比文件区的高。
- 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件从文件区拷贝到对换区。
- 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改，则不必再将它们重写到磁盘(换出)，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时便须调到对换区，以后需要时再从对换区调入。
- UNIX 方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时应从对换区调入。由于 UNIX 系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无需再从对换区调入。
-
页面调入过程
每当程序所要访问的页面未在内存时(存在位为“0”)，便向 CPU 发出一缺页中断，中断处理程序首先保留 CPU 环境，分析中断原因后转入缺页中断处理程序。该程序通过杳找页表得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘 I/O，将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法，从内存中选出一页准备换出；如果该页未被修改过(修改位为“0”)，可不必将该页写回磁盘；但如果此页已被修改(修改位为“1”)，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。
页面置换算法
不适当的算法可能会导致进程发生“抖动”(Thrashing)，即刚被换出的页很快又要被访问，需要将它重新调入，此时又需要再选一页调出；而此刚被调出的页很快又被访问,又需将它调入，如此频繁地更换页面，以致一个进程在运行中把大部分时间都花费在页面置换工作上，我们称该进程发生了“抖动”。
假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
最佳置换算法
是一种理想化的算法，具有最好的性能，但是实际上是实现不了的，但是可以作为评估其他算法的优劣。采用这种算法可以获取最低的缺页率。
最佳置换算法
先进先出置换算法
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。用链表就能够很容易的实现。
FIFO置换算法
最近最久未使用置换算法(LRU)
FIFO 置换算法的性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法是根据页面调入内存后的使用情况做出决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU 置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页而自上次被访问以来所经历的时间 t。当需淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最久未使用的页面予以淘汰。
LRU算法
算法实现(硬件支持)：
-
寄存器
为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为：
当进程访问某物理块时，要将相应寄存器的位置成 1。此时，定时信号将每隔一定时间(例如 100 ms)将寄存器右移一位。如果我们把 n 位寄存器的数看作是一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。下图中第三个内存页面的R值最小，缺页时因该被换出：
寄存器LRU实现
-
特殊的栈
可利用一个特殊的栈保存当前使用的各个页面的页面号。每当进程访问某页而时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号,而栈底则是最近最久未使用页面的页面号。
栈实现LRU
-
map + 双向链表实现LRU算法
struct MyNode { int k, v; MyNode(int tk = 0, int tv = 0) { k = tk; v = tv; } }; // @lc code=start class LRUCache { private: map<int, int> hashtable; list<MyNode *> cache; unsigned int capacity; public: LRUCache(int capacity) { this->capacity = capacity; } int get(int key) { if (hashtable.find(key) != hashtable.end()) { MyNode *node = new MyNode(key, hashtable[key]); for (list<MyNode *>::iterator it = cache.begin(); it != cache.end(); it++) { if ((*it)->k == key) { cache.erase(it); break; } } cache.push_front(node); return hashtable[key]; } return -1; } void put(int key, int value) { MyNode *node = new MyNode(key, value); if (hashtable.find(key) == hashtable.end()) { // 不存在这个Key if (hashtable.size() >= capacity) { // 超过容量，移除队尾元素 MyNode *rnode = cache.back(); cache.pop_back(); hashtable.erase(rnode->k); } hashtable[key] = value; cache.push_front(node); } else { // 存在这个key // 移除 for (list<MyNode *>::iterator it = cache.begin(); it != cache.end(); it++) { if ((*it)->k == key) { cache.erase(it); break; } } cache.push_front(node); hashtable[key] = value; } } };
最少使用置换算法(LFU)
LFU（Least Frequently Used）最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。
注意LFU和LRU算法的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。举个简单的例子：
LFU置换算法
为了能够淘汰最少使用的数据，因此LFU算法最简单的一种设计思路就是 利用一个数组存储 数据项，用hashmap存储每个数据项在数组中对应的位置，然后为每个数据项设计一个访问频次，当数据项被命中时，访问频次自增，在淘汰的时候淘汰访问频次最少的数据。这样一来的话，在插入数据和访问数据的时候都能达到O(1)的时间复杂度，在淘汰数据的时候，通过选择算法得到应该淘汰的数据项在数组中的索引，并将该索引位置的内容替换为新来的数据内容即可，这样的话，淘汰数据的操作时间复杂度为O(n)。
Clock置换算法
简单Clock置换算法
每页设置一个访问位，取值为0和1，当该页被访问时，访问位置为1。
当利用简单 Clock 算法时，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置 1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是 O，就选择该页换出；若为 1，则重新将它置 O，暂不换出，给予该页第二次驻留内存的机会，再按照 FIFO 算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为 1，则再返回到队首去检查第一个页面。
<img src="https://i.loli.net/2020/08/23/cILkHYjUCDt9K1E.png" alt="clock置换算法" style="zoom:67%;" />
改进Clock置换算法
设置两个关键位，一个为访问位，一个为修改位。
页面。由访问位 A 和修改位 M 可以组合成下面四种类型的页面：
1 类(A=0，M=0)：表示该页最近既未被访问，又未被修改，是最佳淘汰页。
2 类(A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。
3 类(A=1，M=O)：表示最近已被访问，但未被修改，该页有可能再被访问。
4 类(A=1，M=1)：表示最近已被访问且被修改，该页可能再被访问。
面中的哪一种。其执行过程可分成以下三步:
- 从指针所指示的当前位置开始，扫描循环队列，寻找 A=0 且 M=0 的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位 A。
- 如果第一步失败，即查找一轮后未遇到第一类页面，则开始第二轮扫描，寻找且 M=1 的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置 0。
- 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复 0。然后重复第一步，即寻找 A=O 且 M=O 的第一类页面，如果仍失败，必要时再重复第二步，寻找 A=0 且 M=1 的第二类页面，此时就一定能找到被淘汰的页。
该算法与简单 Clock 算法比较，可减少磁盘的 I/O 操作次数。但为了找到一个可置换的页，可能须经过几轮扫描。换言之，实现该算法本身的开销将有所增加。
参考链接：
- 为什么 Linux 需要虚拟内存
- 《操作系统》- 第四版
网友评论