转载请注明： TheViper http://www.cnblogs.com/TheViper

加快分页过程

在任何分页式系统中，都需要考虑两个问题：

1.虚拟地址到物理地址的映射必须非常快

2.如果虚拟地址空间很大，页表也会很大

 对大而快速的页映射的需求成为了构建计算机的重要约束，最简单的设计是使用由一组“快速硬件寄存器”组成的单一页表，每个页表项对应一个虚页，虚页号作为索引。这个方法的优势是简单并且在映射过程中不需要访问内存。缺点是在页表很大时，代价高，每一次上下文切换都必须装载整个页表。

转换检查缓冲区

现象：大多数程序总是对少量的页面进行多次访问。

解决方案：为计算机设置一个小型的硬件设备，将虚拟地址直接映射到物理地址，而不必再访问页表，称为快表。

针对大内存的页表

1.多级页表

例如，考虑32位虚拟地址0x00403004(十进制4206596)位于数据部分12292字节处。它的虚拟地址对应PT1=1,PT2=2,OFFSET=4.

首先用PT1作为索引访问顶级页表得到表项1，它对应的地址范围是4M-8M,然后，它用PT2作为索引访问刚刚找到的二级页表并得到表项3，它对应的虚拟地址范围是在它的4M块内的12288-16383（即绝对地址4206592-4210687）.这个表项含有虚拟地址0x00403004所在页面的页框号。

如果该页面不在内存中，页表项中的“在\不在”位将是0，引发一次缺页中断。如果该页面在内存中，从二级页表中得到的页框号将与偏移量（4）结合形成物理地址。该地址被放到总线上并送到内存中。

倒排页表

对32位虚拟地址空间，多级页表可以很好的发挥作用，但是，随着64位计算机变得更加普遍，情况发生了彻底的变化。如果现在的地址空间是2的64次方字节，页面大小为4kb，就需要一个有2的52次方个表项的页表。如果每个表项8个字节，那么整个页表会超过3000万gb(30pb).

解决方案之一就是使用倒排页表。在这种设计中，在实际内存中每一个页框有一个表项，而不是每一个虚拟页面有一个表项。表项记录哪一个（进程，虚拟页面）定位于该页框。

虽然倒排页表节省了大量空间，但它也有严重的不足：从虚拟地址到物理地址的转换变得很困难。当进程n访问虚拟页面p,硬件不再能通过把p当做指向页表的一个索引来查找物理页框，而是必须搜索整个倒排页表来查找某一个表项（n,p）.此外，该搜索必须对每一个内存访问操作都要执行一次，而不仅仅是在缺页中断时执行。

可以使用快表，如果快表能够记录所有频繁使用的页面，地址转换就可能变得像通常的快表一样快。但是，当快表失效时，需要搜索整个倒排页表，一个可行的实现该搜索的方法是建立一张散列表，用虚拟地址来散列。即当前所有在内存中具有相同散列值的虚拟页面被链接在一起。

页面置换算法

当发生缺页中断时，操作系统必须在内存中选择一个页面将其换出内存，以便为即将调入的页面腾出空间。如果要换出的页面在内存驻留期间已经被修改过，就必须把它写回磁盘以更新该页面在磁盘上的副本。如果没被修改过，直接用调入的页面覆盖被淘汰的页面就可以了。

1.最优页面置换

如果一个页面在800万条指令内不会被使用，另一个页面在600万条指令内不会被使用，则置换前一页面，从而把因需要调入这个页面而发生的缺页中断推迟到将来。

但是它无法实现，因为当缺页中断发生时，操作系统无法知道各个页面下一次将在什么时候被访问。

2.最近未使用页面置换

系统会为每个页面设置两个状态位。当页面被访问（读或写）时设置为R位，当页面被写入时设置M位。这些位包含在页表项中，每次访问内存时都会更新这些位。

可以用M位和R位构造算法：当启动一个进程时，它的所有页面的两个位都由操作系统设置为0.R位被定期（比如在每次时钟中断时）的清零，以区别最近没有被访问的页面和被访问的页面。

当发生缺页中断时，操作系统会检查所有的页面，结果分为4类：

　　第一类：没有被访问，也没有被修改

　　第二类：没有被访问，已被修改

　　第三类：已被访问，没有被修改

　　第四类：已被访问，已被修改

一个第三类页面在它的R位被时钟中断清零后就变成了第一类。时钟中断不清除M位是因为在决定一个页面是否需要写回磁盘时要用到这个信息。

这个算法隐含的意思是，在最近一个时钟滴答中（典型时间是大约20ms）,淘汰一个没有被访问的已修改页面要比淘汰一个被频繁使用的干净页面好。

3.先进先出页面置换(FIFO)

由操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最久进入的页面放在表头。当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾。

4.第二次机会页面置换

FIFO可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单修改：检查最老页面的R位，如果R位为0，说明这个页面既老又没有被使用，可以立刻置换掉，如果是1，就将R位清零，并把该页面放到链表的尾端，修改它的装入时间使它就像刚转入的一样，然后继续搜索。

该算法实质就是寻找一个最近的时钟间隔以来没有被访问过的页面。如果所有的页面都被访问过了，该算法就成了FIFO。

5.时钟页面置换

尽管第二次机会页面置换是一个比较合理的算法，但它经常要在链表中移动页面。一个更好的办法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。

6.最近最少使用页面置换（LRU）

在缺页中断发生时，置换未使用时间最长的页面。虽然LRU理论上可行，但代价很高。为了完全实现LRU，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最远最少使用的页面在表尾。困难的地方在于每次访问内存时，都必须要更新整个链表。在链表中找到一个页面删除它，然后把它移到表头是一件非常费时的操作。

 7.用软件模拟LRU

前面两种LRU算法虽然在理论上可以实现，但只有非常少的计算机拥有这种硬件。

一种可能的方案是NFU(最不常用算法)，该算法将每个页面与一个软件计数器相关联。计数器初始值为0.每次时钟中断时，由操作系统扫描内存中的所有页面，将每个页面的R位加到它的计数器上。这个计数器大体上跟踪了各个页面被访问的频繁程度。发生缺页中断时，置换计数器值最小的页面。

NFC的主要问题是它从来不忘记任何事。比如，多次扫描，第一次扫描中被频繁使用的页面在第二次扫描时，其计数器值仍然可能很高。

幸运的是只需对NFC做一个小小的修改就能使它很好的模拟LRU.其修改分为两部分：首先，在R位被加之前先将计数器右移一位，然后，将R位加到计数器最左端的位。修改后的算法称为老化算法。

发生缺页中断时，将置换计数器值最小的页面，如果一个页面在前面4个时钟滴答中都没有被访问过，那么它的计数器最前面应该有4个连续的0。如果前面4个时钟滴答中哪怕有一次页面被访问，它的计数器值都会比前面4个时钟滴答中都没被访问的页面的计数器值大，且离当前时间越远，最左位的值对计数器值的影响越大，因为最后是比较值大小。

8.工作集页面置换

一个进程当前正在使用的所有页面集合称作工作集，如果整个工作集都被装入到内存中，那么进程在运行到下一运行阶段之前，不会产生很多次缺页中断。若内存太小而无法容纳整个工作集，则会产生大量缺页中断，因为通常只需几个纳秒就能完成的指令，现在需要10毫秒才能从磁盘读取一个页面。这种每执行几条指令程序就发生一次缺页中断的现象称为颠簸。

为解决这个问题，不少分页系统都设法跟踪进程的工作集，以确保在让程序运行之前，它的工作集已经在内存中了。

算法：发生缺页中断时，淘汰一个不在工作集中的页面。

具体的，选定k值，则每次内存访问后，最近k次内存访问所使用过的页面的集合就是唯一确定的了。设想有一个k位的移位寄存器，每进行一次内存访问就把寄存器左移一位，然后在最右端插入刚才所访问过的页面号。移位寄存器的k个页面后的集合就是工作集。

理论上，当发生缺页中断时，只要读出移位寄存器的内容并排序，然后删除重复的页面，结果就是工作集。然而，维护移位寄存器并在缺页中断时，处理它所需的开销太大，因此该技术从来没有被使用过。

作为替代，有几种近似的方法.一种方法是，不是向后找最近k次的内存访问，而是考虑其执行时间。进程的工作集可以看作在过去t秒实际运行时间中它所访问过的页面的集合。

因为只有那些在内存中的页面才可以作为候选者被淘汰，所以该算法忽略了那些不在内存中的页面。

具体的，假定使用硬件设置R位和M位，在每一个时钟滴答中，有一个定期的时钟中断会用软件方式清除R位。时间周期t包含多个时钟滴答。

在处理每个表项时，检查R位，如果是1，就设置上次使用时间为当前实际时间，表示缺页中断发生时，该页面正在被使用。如果是0，需要计算它的生存时间（即当前实际时间减去上次使用时间），然后和T比较。如果大于t,那么这个页面就不在工作集中，用新的页面替换。如果<=t,就把该页面临时保留下来，但是要记录生存时间最长（“上次使用时间”的最小值）的页面。

如果扫描完整个页表都没有适合被淘汰的，说明所有页面都在工作集中。在这种情况下，如果找到一个或多个R=0的页面，就淘汰生存时间最长的页面。

最坏的情况下，在当前时间滴答中，所有页面都被访问过（R=1），就随机选一个淘汰，当然最好选一个干净页面淘汰。

9.工作集时钟页面置换

发生缺页中断时，需要扫描整个页表才能确定被淘汰的页面，因此比较费时。

一种改进算法，它基于时钟算法，并且使用了工作集信息，称为工作集时钟算法。

每个表项包含来自工作集算法的上次使用时间，以及R位，M位。

总结

《现代操作系统》笔记——存储管理2