本文已收录到：清华大学操作系统课程笔记 专题
虚拟存储（虚存）
在非连续内存分配之上实现将内存暂存到磁盘中，实现应用程序可使用更多的内存空间，有点像linux中的swap。
覆盖技术
dos系统，程序员自己写覆盖控制。开发难度增加。
交换技术
以进程为单位的交换技术：
局部性原理
操作系统决定什么东西换出，什么换入。与后面的页置换算法有关。
如果是在内存中，是没有变化的。但如果利用了虚拟存储，用后面的方法会提高程序的性能。
虚拟存储概念
什么是虚拟内存？简单地说是指程序员或CPU“看到”的内存。
- 虚拟内存单元不一定有实际的物理内存单元对应，即实际的物理内存单元可能不存在；
- 如果虚拟内存单元对应有实际的物理内存单元，那二者的地址一般是不相等的；
- 通过操作系统实现的某种内存映射可建立虚拟内存与物理内存的对应关系，使得程序员或CPU访问的虚拟内存地址会自动转换为一个物理内存地址。
首先，在有了分页机制后，程序员或CPU“看到”的地址已经不是实际的物理地址了，这已经有一层虚拟化，我们可简称为内存地址虚拟化。
有了内存地址虚拟化，我们就可以通过设置页表项来限定软件运行时的访问空间，确保软件运行不越界，完成内存访问保护的功能。
通过内存地址虚拟化，可以使得软件在没有访问某虚拟内存地址时不分配具体的物理内存，而只有在实际访问某虚拟内存地址时，操作系统再动态地分配物理内存，建立虚拟内存到物理内存的页映射关系，这种技术称为按需分页（demand paging）。
把不经常访问的数据所占的内存空间临时写到硬盘上，这样可以腾出更多的空闲内存空间给经常访问的数据；当CPU访问到不经常访问的数据时，再把这些数据从硬盘读入到内存中，这种技术称为页换入换出（page swap in/out）（分页机制）。这种内存管理技术给了程序员更大的内存“空间”，从而可以让更多的程序在内存中并发运行。
覆盖和交换前面讲过了。
虚拟页式存储：在页式存储之上把一部分放在外存（磁盘）。
为什么要做虚拟存储?——原因是快速增长的内存需求。
上图：操作系统这么做是为了方便上层用户。
到这，我们就可以实现虚拟存储了。
我们还需要：
虚拟页式存储（重点）
虚拟页式存储：在页式存储之上把一部分放在外存（磁盘）。
把交换的单位设置为页的时候，就是虚拟页式存储。
之前的：
操作系统要做的事情就是接管，找页，把这一个符号变为有效：
这一小点的变化会导致修改：
虚拟存储的话需要加一些标志位：
举个栗子：
执行MOV REG, 8192
可以找到页，访问没有问题。
缺页：
X86页表结构：
这一部分跟前面所讲的页是一样的，变化在下面：
缺页异常
发现这一页不在物理内存中。
能找到空闲页的情况:
实际代码中又要复杂一些。
虚拟页式存储中的外存管理
虚拟页式存储管理的性能
置换算法
置换算法的概念
功能：
进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区，其中选择调出页面的算法就称为页面置换算法。
核心点是：选择被置换的物理页面
设计目标：
页面锁定
有些页面不能被换出到外存。通过锁定位实现。
如何评价一种置换算法？
页面置换算法分类
局部页面置换算法
最优页面置换算法（OPT）——理想情况，实际无法实现
算法实例：
物理帧号表示当前物理内存中含有的页，即没有被置换出去的页，可以直接访问不会产生缺页异常。
当时间1时，访问c，c存在于物理帧号中，所以不会发生缺页异常，可正常访问。同理，访问后面的 a、d、b 也不会产生缺页问题。
当访问到e时，在物理帧中没有这个页，产生缺页异常。在本算法中，考虑将哪个页置换出去，这就是页置换算法，本质是研究将谁置换出去，换到硬盘中。
根据最优页面置换算法，得知下一次访问时间距离现在最长的页是d，所以将d页置换出去。Ps：实际上我们不知道下次访问的时间，这是一种上帝视角，能预测未来。
置换出去后，我们把e置换进来，即从硬盘换入到内存中。现在e页可以被访问。
接下来访问b页、a、b、c，都可以被正常访问到。
此算法中，最好的情况是缺页两次。这个算法的根本问题在于我们无法知道后面的执行顺序。
先进先出算法（FIFO）——会饥饿
既然未来的事情我们都不知道，那就按现在，截至目前谁在内存中留的时间最长，就把谁置换出去，就是先来后到。
实现思想：维护一个链表，链表头部的是留在内存时间最久的页，尾部是刚进来的页，出现缺页就把头部结点替换掉。
Ps：此算法有一种极端情况：刚换出的页在下一次又得被换入，他是经常使用的页。这样子就会导致巨多的缺页，产生belady现象。我们通常不会把它作为独立的算法，会与其他算法柔和在一起使用。
示例，使用链表实现FIFO算法：
前面都没有缺页，在访问e的时候缺页，于是把驻留时间最久的页a置换出去，e放在链表的尾部。
接下来a页缺页，把b换出：
此算法中，发生5次缺页。在Lab3的实验中，我们完成FIFO页替换算法。
最近最久未使用算法（LRU）——是一种折中的办法
此算法的思想是认为——在过去一段时间经常访问的页，在未来也会经常被访问。在过去很少访问的，在未来也很少被访问。
实现思路思想：
LRU（最近最久未使用）算法缺页三次。
方法一：使用链表实现LRU算法：
但是这样做有个巨大的缺点，每次访问我都需要动一下这个页面链表，把当前访问的页面添加到链表头部，并删除掉尾部的结点。
方法二：用栈实现LRU算法：
时间6，访问b的时候，虽然不会产生缺页异常，但是还是需要维护栈。——把b抽出来放在栈顶，与栈顶的e交换：
不管是方法一维护一个链表还是方法二维护一个栈，LRU这种算法都会导致平时的开销很大，接下来想办法改进。
时钟置换算法(clock)——不像LRU那样考虑那么长的时间
基本思想：粗略的统计过去访问页，只考虑过去访问过没，不考虑过去多久没访问过。大致统计：看过去的一段时间中页面是否被访问过，如果被访问过就留下，没有被访问过就置换出去。
发生缺页的时候开始找，注意这里的驻留位为1表示当前页在内存中，驻留位为0表示当前页不在内存中。
通过上面的方法可以使程序缺页的情况下置换，正常的情况下访问。
时钟置换算法示例：
初始时，都没被访问过，所以都置为0：
访问c，c的页表项置为1：
访问e的时候缺页：
访问b，置为1：
a缺页，同理，顺序找下面的访问位为0的元素。替换掉，并将访问位改为1：
下面同理。
改进的时钟算法（challenge部分实现）
改进：新增修改位，在修改的时候把他的修改位置为1。
基本思想：因为操作系统换入页到内存中可能会对页只读取并没有修改，也可能对页进行了修改。如果是只读取的页，这可以随时扔掉，但对于修改的页，它不能够随随便便抛弃，它必须在合适的时间换出。
- 我们想置换的页最好是既没有访问过，又没有被修改过，可以毫不犹豫的置换掉。
- 最不想被置换的是即被访问过也被修改过。
- 介于两只之间的，可以尝试再给他一次机会，所以当他的使用位或者修改位有一个为1时，就会把他置为0。然后他就会不断的“退化”下去。
可参考《现代操作系统》
示例：
访问e的时候发生缺页，开始置换，置换方法采用改进的时钟算法。蓝色的表示当前指针的位置，开始向下循环遍历。
将a的访问位置为0，a是01；将b置为01，将c置为00，将d置为00：
循环回到a，继续将01置为00。——不断“退化”
再次发生缺页：
d缺页：
最不常用算法（LFU）——从LRU的考虑时间改变为考虑次数
基本思想：
特征：算法开销大，后面有一种改进方法——计数定期右移
LRU与LFU区别：
统计时间，需要维护栈，但统计次数相对好处理点。
示例：
访问e时发生缺页：
以此类推：
… …
Belady现象
所谓Belady现象是指：在分页式虚拟存储器管理中，发生缺页时的置换算法采用FIFO（先进先出）算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。
FIFO是最早出现的页置换算法之一。Belady现象的原因是FIFO算法（先进先出算法）的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的，因而FIFO并不是一个好的置换算法。
Belady是人名，一般翻译为贝莱迪。一般来说，缓存越大，命中率越高，缺页率越低。但有一个计算机学者，名字叫Belady。在1969年研究FIFO算法时，发现了一个反例，使用4个页框时的缺页次数比3个页框时的缺页多，因此这种奇怪的情况称为Belady异常。
这种异常的原因是对于FIFO算法来说，在同一时刻，使用4个页框时缓存中保存的页面并不完全包含使用3个页框时保存的页面，二者不是超集子集关系，造成都某些特殊的页面请求序列，4个页框命中率反而低。
对LRU算法，任何时刻，缓存大的算法中保存的页面，都包含了缓存小的算法中的页面，所以缓存越大，命中率越高。
答：LRU（最近最久未使用算法）没有Belady现象。
算法比较
全局置换算法
为什么想到全局置换？——举个例子，如果物理页面数为3，会产生9次缺页。
如果我们再多加一个1物理页面，只出现了1次缺页：
工作集
工作集置换算法
再多缓存一页就可以很有效的避免缺页。
缺页率置换算法
目前我们能控制的是页面置换算法。
目的是让缺页率保持在某个范围。
缺页率比较低，相当于常驻集过大，需要把不用的页置换出去。
缺页率过高，需要增加常驻集。
举个例子：
把置换这种事放在缺页中断的时候完成。这时候开销会降下来。
抖动和负载控制
负载控制
参考文献：https://www.zhihu.com/question/278329594/answer/453578379
