1.分页
大部分虚拟内存系统中都使用一种称为分页的技术。
在任何一台计算机上，程序引用了一组内存地址，由程序产生的这些地址称为虚拟地址，他们构成了一个虚拟地址空间。
- 在没有虚拟内存的计算机上，系统直接将虚拟地址送到内存总线上，读写操作使用具有同样地址的物理内存字；
- 在使用虚拟内存的情况下，虚拟地址不是直接被送到内存总线上，而是被送到内存管理单元(Memeory Management Unit,MMU)，MMU把虚拟地址映射为物理内存地址。
虚拟地址空间按照固定大小划分成称为页面的若干单元。在物理内存中对应的单元称为页框。页面和页框大小是一样的，这里假设都为4KB。他们之间的映射关系如下图：
注：在上图中，我们假设有一台可以产生16位地址的计算机，地址范围从0到64K，且这些地址是虚拟地址。
然而，这台计算机只有32K的物理内存，因此，虽然可以编写64KB的程序，但它们却不能被完全调入内存运行。
在磁盘上必须有一个可以大到64KB的程序核心映像的完整副本，以保证程序片段在需要时能被调入内存。 内存和磁盘之间的交换总是以整个页面为单元进行的。
在图中，对应于64KB虚拟地址空间和32KB的物理内存，我们得到16个虚拟页面和8个页框。
图中的标记符号如下：标记0-4K的范围表示该页的虚拟地址或物理地址是0-4095；4K-8K的范围表示地址4096-8191，等等，每一页包含了4096个地址。 当程序试图访问地址8203时，例如执行下面这条指令
MOV REG 8203通过恰当地设置MMU，可以把16个页面映射到8个页框中的任何一个。
但是这样并没有解决虚拟地址空间比物理内存大的问题。在上图中只有8个物理页框，于是只有8个虚拟页面被映射到了物理内存中（图中的×表示页面没有被映射。）在实际的硬件中，用一个“在/不在”位来记录页面是否在内存中。
当程序访问一个未映射的页面时，例如执行如下指令
MOV REG 32780将虚拟地址32870送到MMU，MMU看到虚拟地址落在页面8（32768-36863），但是该页面并没有被映射到内存中，于是发生缺页中断，操作系统调用适当的页面置换算法，找到某个页框将它的内容写入磁盘（如果它不在磁盘），随后把页面8读到刚才回收的页框，修改映射关系，然后重新启动引起陷阱的指令。
2.分页管理
2.1.页表
分页系统中，允许将进程的每一页离散地存储在内存的任一物理块中。
为了能在内存中找到每个页面对应的物理块，系统为每个进程建立一张页表，用于记录进程逻辑页面与内存物理页面之间的对应关系。页表的作用是实现从页号到物理块号的地址映射，地址空间有多少页，该页表里就登记多少行，且按逻辑页的顺序排列，形如：
虚拟地址到物理地址的映射可以概括如下：
- 虚拟地址被分成虚拟页号（高位部分）和偏移量（低位部分）。
- 例如，对于16位地址和4KB的页面大小，高4位可以指定16个虚拟页面，而低12位接着确定了页内偏移量。
- 虚拟页号可用作页表的索引，以找到该虚拟页面所对应的页表项。由页表项可以找到页框号（如果有的话）。
- 然后把页框号拼接到偏移量的高位端，以替换掉虚拟页号，形成送往内存的物理地址。
2.2 页表项
一个典型的页表项如下：
页表项的结构是与机器密切相关的，但不同机器的页表项存储的信息都大致相同。
- 页表项中最重要的域是 页框号。
- 其次是 “在/不在”位，
- 这一位为1时表示该表项是有效的，可以使用；
- 如果是0，则表示该表项对应的虚拟页现在不在内存中，访问该页面会引起缺页中断。
- “保护”位指出一个页面允许什么类型的访问。
- 最简单的形式是这个域只有一位
- 0表示读/写
- 1表示只读。
- 一个更先进的方法是使用三位
- 各位分别对应是否启用读、写、执行该页面。
- 最简单的形式是这个域只有一位
- “修改”位和“访问”位用于记录页面的使用情况。
- 这两位在操作系统重新分配页框和发生缺页中断选择淘汰的页时非常有用。
- ““高速缓存禁止”位用于禁止该页面被高速缓存。
2.3.加速分页过程
在任何分页式系统中，都需要考虑两个主要问题：
- 虚拟地址到物理地址的映射必须非常快——使用“转换检测缓冲区（Translation Lookaside Buffer,TLB）“解决。
- 如果虚拟地址空间很大，页表也会很大——使用多级页表或倒排页表解决。
2.3.1 转换检测缓冲区
TLB这种方案的建立是基于这样一种现象：大多数程序总是对少量的页面进行多次的访问，而不是相反的。
因此，只有很少的页表会被反复读取，而其他的页表项很少被访问；
通过这个方案为计算机设置了一个小型的硬件设备，将虚拟地址直接映射到物理地址，而不是在访问页表。这种设备称为”转换检测缓冲区“。
工作原理：
将一个虚拟地址放入MMU中进行转换时，硬件首先通过将该虚拟页号与TLB中所有表项同时（即并行）进行匹配，判断虚拟页面是否在其中。
- 如果发现了一个有效的匹配并且要进行的访问操纵并不违反保护位，则将页框号直接从TLB中取出而不必再访问页表。
- 如果虚拟页面号确实是在TLB中，但指令试图在一个只读页面上进行写操作，则会产生一个保护错误，就像对页表项的非法访问一样。
- 如果MMU检测到没有有效地匹配项时，就会进行正常的页表查询。
- 接着从TLB中淘汰一个表项，然后用新找到的页表项代替它。这样，如果这一页面很快再被访问，第二次访问TLB时自然将会命中而不是不命中。
- 当一个表项被清除出TLB时，将修改位复制到内存中的页表项，而除了访问位，其他的值不变。当页表项中从页表装入到TLB中时，所有的值都会来自内存。
2.3.2多级页表
32位的虚拟地址被划分为10位的PT1域，10位PT2域和12位的Offset（偏移量）域。
- 偏移量是12位，所以页面长度是4KB（2^12=4*2^10=4KB），
- PT域是20位，共有2^20个页面。
引入原因：避免把全部页表一直保存在内存中。特别是那些从不需要的页表就不应该保留。
工作原理：
在左边是*页表，它具有1024个表项，对应于10位的pT1 域。
当一个虚拟地址被送到MMU时，MMU首先提取PT1域并把该值作为访问*页表的索引。
- 因为整个4GB（(2^2)*(2^10)*(2^10)*(2^10)=2^32，整个虚拟地址）虚拟地址空间已经被分为1024个4MB的块（按PT1来说，总共是1024个表项，划分整个虚拟地址空间，就是每个表项是4MB），所以这1024个表项中的每一个都表示4MB的虚拟地址空间。
由*页表得到的表项中含有二级页表的地址或页表框号。
- *页表中
- 表项0指向程序正文的页表
- 表项1指向数据的页表
- 表项1023指向的堆栈的页表
- 其他的表项未用
现在把PT2域作为访问选定的二级页表的索引，以便找到该虚拟页表的对应页框号。
举例：
考虑虚拟地址0x00403004（十进制4206596）位于数据部分12292字节处。
0x00403004二进制表示为：0000 0000 0100 0000 0011 0000 0000 0100
它的虚拟地址对应PT1=1， PT2=3, Offset=4。
MMU首先用PT1作为索引访问*页表得到表项1（符合前文所说的数据部分，1对应数据的页表），它对应的地址范围是4-8M；
然后，它用PT2作为索引访问刚刚找到的二级页表（*页表项1指的二级页表项）并得到表项3（由PT2得到的3），它对应的虚拟地址范围是在它的4M块内的12288-16383（即绝对地址4106592-4210687）。这个表项是否含有虚拟地址0x00403004所在页面的页框号：
- 如果页面不在内存中，页表中的”在/不在“位将是0，引发一次缺页中断。
- 如果该页面在内存中，从二级页表中得到的页框号将与偏移量结合形成物理地址。
2.3.3倒排也法
对于32位虚拟地址空间，多级页表可以发挥的很好，但对于64位的计算机情况发生了彻底的变化，因而64位分页的虚拟地址空间的系统需要一个不同的解决方案。
倒排页表的方法可以节省大量的空间，但也存在不足，主要在机器的运行效率上。
走出这种两难的局面的办法是使用TLB。
- 如果TLB能够记录所有频繁使用的页面，地址转换就可能变得像通常的页表一样快。
- 但是，当发生TLB失效时，需要用软件搜索整个倒排页表。
一个可行的实现该搜索的方法是建立一张散列表，用虚拟地址来散列，当前所有在内存中的具有相同散列值的虚拟页表被链接在一起。
如果散列表中的槽数与机器中物理页面数一样多，那么散列表的冲突链的平均长度将会是1个表项，这将会大大提高映射的速度。
一旦也框号被找到，新的（虚拟页号、物理页框号）对就会被装载到TLB中。
3.置换策略理论
3.1 最佳置换算法(OPT)
最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面。这样可以保证获得最低的缺页率。
但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。
3.2 先进先出(FIFO)页面置换算法
优先淘汰最早进入内存的页面，即在内存中驻留时间最久的页面。
该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。
但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。
3.3. 最近最久未使用(LRU)置换算法
选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。
该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。
3.4对比
| 算法 | 优点 | 缺点 | 适用情况 |
|---|---|---|---|
| OPT | 可保证获得最低的缺页率，并且可以用来评价其他算法 | 理论上的算法，目前该算法是无法实现的 | 以进行模拟实验分析或理论分析 |
| FIFO | 实现简单，要求的硬件支持较少 | 所依据的条件是各个页面调入内存的时间，而页面调入内存的先后并不能反映页面的使用情况 | 在按线性顺序访问地址空间时使用；当硬件水平不足时，FIFO算法也可作为首选 |
| LRU | 利用“最近的过去”代替“最近的将来”，以此模拟Optimal算法，是实际应用中缺页率最低的算法 |
根据各页以前的使用情况，来代替各页面将来的使用情况，进而判断要替换出去的页面，而页面过去和将来的走向之间并无必然的联系； 其实际应用时要求较多的硬件支持，因而多采用近似算法 |
当系统有寄存器或栈的硬件支持时，利用LRU算法可以获得最低缺页率 |
3.5举例
假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串： 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
3.5.1 OPT
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |
| 访问页面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
| 块1 | 7 | 7 | 7(18) | 2 | 2(9) | 2 | 2(9) | 2 | 2 | 2(13) | 2 | 2 | 2(15) | 2 | 2 | 2 | 2(-) | 7 | 7 | 7 |
| 块1 | 0 | 0(5) | 0 | 0(7) | 0 | 0(11) | 4 | 4 | 4(-) | 0 | 0 | 0(16) | 0 | 0 | 0 | 0(19) | 0 | 0 | 0 | |
| 块1 | 1(14) | 1 | 1(14) | 3 | 3(10) | 3 | 3 | 3(12) | 3 | 3 | 3(-) | 1 | 1 | 1 | 1(20) | 1 | 1 | 1 | ||
| 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ | √ |
缺次数：9
换页次数：6
3.5.2FIFO
| 访问页面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
| 块1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 7 | 7 |
| 块1 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | |
| 块1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 1 | ||
| 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
缺页次数：15
换页次数：12，比最佳置换算法正好多一倍。
FIFO算法基于队列实现，不是堆栈类算法。
FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象，这是由 Belady于1969年发现，故称为Belady异常。只有FIFO算法可能出现Belady 异常，而LRU和OPT算法永远不会出现Belady异常。
| 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 块1 | 1 | 1 | 1 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 5 |
| 块2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | |
| 块3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | ||
| 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | |||
| 块1* | 1 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 4 | 4 |
| 块2* | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 5 | |
| 块3* | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | ||
| 块4* | 4 | 4 | 4 | 4 | 4 | 4 | 3 | 3 | 3 | |||
| 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
3.5.3 LRU
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |
| 访问页面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
| 块1 | 7 | 7 | 7(1) | 2 | 2(4) | 2 | 2(4) | 4(8) | 4(8) | 4(8) | 0 | 0 | 0(11) | 1 | 1(14) | 1 | 1(17) | 1 | 1 | 1 |
| 块1 | 0 | 0(2) | 0 | 0(5) | 0 | 0(7) | 0(7) | 0(7) | 3(10) | 3 | 3 | 3(12) | 3 | 3(12) | 0 | 0(16) | 0 | 0 | 0 | |
| 块1 | 1(3) | 1 | 1(3) | 3 | 3(6) | 3(6) | 2(9) | 2(9) | 2 | 2 | 2(13) | 2 | 2(15) | 2 | 2(15) | 7 | 7 | 7 | ||
| 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
缺页次数：12
换页次数：9
前5次置换的情况与最佳置换算法相同，但两种算法并无必然联系。
- LRU算法根据各页以前的情况，是“向前看”的，
- 最佳置换算法则根据各页以后的使用情况，是“向后看”的。
LRU性能较好，但需要寄存器和栈的硬件支持。
LRU是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现Belady异常。
3.5.1堆栈类算法
基本思想：随着分配给程序的主存页面数增加，主存的命中率会提高，至少不下降。
LFU和LRU算法中，由于在主存中保留的是最近使用过的页面。
如果先给某一个程序分配n个主存页面，那么在t时刻，这n个主存页面都是最近使用过的页面。
如果再给程序多分配一个主存页面，那么在t时刻，这n+1个主存页面也都是最近使用过的页面。
因此，在这n+1个主存页面中必然包含了前面的n个主存页面。
所以LFU和LRU算法都是堆栈型算法。
3.6 最近未使用页面置换算法(NRU)
找到最久没有使用的页面置换出去，页面被访问时设置R位，修改时设置M位，R位定期清0；
把页面分四类：
- 0类：未被访问，未被修改的 R=M=0
- 1类：未被访问，被修改 R=0,M=1
- 2类：被访问，未被修改 R=1,M=0
- 3类：被访问，被修改 R=1，M=1
系统从类类编号最小的非空类随机挑选一个置换。
3.7 第二次机会页面置换算法
改进版FIFO。
淘汰旧页面时先从检查头部页面的R位，
- 若为1，则说明此页面最近被使用过，置R=0，把它加到尾部去，重新设置其装入时间为当前时刻，继续搜寻
- 若M为0，如果此页面被写过，把它写回磁盘再淘汰，若未被写，直接淘汰
3.8 时钟页面置换算法
维持一个保存所有页面的环形链表，一个指针指向最老页面。
发生缺页中断时，检查指针指向页面，若R=0，则更新它，若R=1，清除R位，指针前移，继续搜索。
3.9 最不常用算法NFU
为每个页面维持一个初值0的计数器，每次时钟中断，由操作系统扫描所有页面，把计数器加上当前的R位更新，这样每个计数器的值大概反映了被访问的频繁程度。缺页中断时，置换计数器数值最小的页面。
3.10 老化算法-改进的LRU
在R位加进之前，先把计数器值右移一位，把R位加到计数器最左边， 特点：每次时钟滴答只能记下一位，因此如果两个页面在同一个时钟滴答期间被访问是不能分出的，而且由于计数器是有限位数，假设是8位，如果很多页面在8个时钟滴答都未被访问的话，就都是全零位无法区分，但实际情况是，若已经这么久没有被访问了，该页面一般也不是很重要了 。
3.11 工作集页面置换算法
定义一个工作集：在过去t秒内被访问的页面的集合。
扫描所有页面，若R=1，说明在这个时钟滴答被访问了，它应该是工作集的一部分，把当前时间写入页表项的“上次使用时间“ 。
若R=0，且生存时间（当前时间-上次使用时间）>t，置换它，如果<t，记住最小时间。
3.12 工作集时钟页面置换算法
维持一个以页框为元素的循环表，形成一个环。
每个表项包括上次使用时间，R位、M位。
缺页中断时，首先检查指针指向的页面，
- 若R=1，则说明它最近被访问了，把R位置为0，指针指向下一个位置；
- 若R=0，若它的生存时间>t且此页面干净，置换之。
- 如果不干净，继续往前走。（因为可能前方存在旧的又干净的页面)
参考：
https://blog.****.net/EveryFriDay_ShuJk/article/details/79817235
https://www.cnblogs.com/wujing-hubei/p/5967826.html
https://blog.****.net/qq_34777600/article/details/79508613