文章目录碎片中断2.1优化替换(Optimal，OPT )2.1.1基本思想2.1.2算例2.2先进先出替换算法) First In First Out，FIFO )2.2.2. 1基本思想2.2.2算例2.2
原文： 3359 blog.csdn.net/u 011080472/article/details/51206332
缺页
在请求分页系统中，可以通过查询页表中的状态位来确定内存中是否存在要访问的页。 每次尝试访问的页面不在内存中时，都会发生页面错误，操作系统会根据页面表的外部地址从外部存储器中查找缺少的页面，然后将其装入内存。
缺页本身是一种中断，与常规中断一样，需要经过四个处理步骤。
1.CPU现场保护
2 .中断原因分析
3 .转移到缺页中断处理程序进行处理
4 .恢复CPU现场，继续执行
但是，对于页面错误，如果内存中不存在要访问的页面，则会有硬件引起的特殊中断，因此与普通中断不同。
5 .命令执行过程中产生缺页中断信号并进行处理
6 .在执行一个指令的过程中，可能会发生多次缺页
7 .缺页中断返回时，执行发生中断的命令，正常中断返回时，执行以下命令
8 .页面替换算法
如果在进程运行过程中出现页面不足，则内存中是否有可用的物理块是因为系统必须从内存中选择页面并将其调用到磁盘交换空间，以便可以将缺少的页面加载到内存中。 但是，此时应该置换该页面，需要基于一定的页面置换算法(Page Replacement Algorithm )进行决定。
2.1最佳替换(Optimal，OPT )2.1.1基本思想替换后不再访问，或者将来较晚返回访问的页面时，缺页中断率最低。 但是，该算法需要取决于今后各行业的使用情况，如果某个进程还没有运行，很难估计今后将不再使用哪些页面，或者最长时间后将使用哪些页面。 所以这个算法不能实现。 但该算法仍然很有意义，成为阐明其他算法优劣的一个标准。
2.1.2算例采用固定分配局部置换的策略，嘉定系统为某个进程向内存分配3个物理块，页面访问顺序为2、3、2、1、5、2、4、5、3、2、5、2。 假设系统没有采用预调节页面策略，也就是说，没有提前调入任何页面。 在进程运行过程中，将2、3、1三个页面一次调入内存，发生了三次缺页中断。 第一次访问页面5时，发生第四次缺页中断，根据OPT算法，页面1将被丢弃，因为以后不再使用； 第五次缺页被中断时，页面2被丢弃。 因为这是5、3、2这3个页面中，将来最晚访问页面的页面。 这样类推：
注：第四次中断会排除最后不访问的1，并将最后访问的3放在底部的内存块中。 在以后的安排中，最后不访问的页面或最后访问的页面总是放在底部的内存块中。 内存块按从上到下的顺序存储第一个访问的页面。
中断次数为6，缺页中断率为6/12*100%=50%。
2.2先进先出置换算法(First In First Out，FIFO )2.2.1基本思想置换替换最初存入内存的页面，即最长时间驻留在内存中的页面。 按进入内存的优先级排队，从队列末尾进入，从队列开头删除。 但该算法淘汰了频繁访问的页面，不适应流程实际执行的规律，目前已很少使用。
2.2.2算例仍以OPT算例为例。
中断次数为9，缺页中断率为9/12*100%=75%。
2.2.3 Belady异常一般来说，分配给进程的物理块越多，运行时分页错误次数应该越少。 使用FIFO时，可能会发生相反的情况。 分配给4个物理块的分页错误次数竟然比3个物理块的分页错误次数还多。
例如，进程访问顺序为0、2、1、3、0、2、4、0、2、1、3、4。
如果M=3，缺页将被中断9次。 缺页中断率9/12*100%=75%。
如果M=4，缺失页面将被中断10次。 缺页中断率10/12*100%=83.3%。
2.3最近最早使用的替换算法(Least Recently Used，LRU ) 2.3.1基本思想替换最近最久未访问的页面。 根据程序的局部性原理，刚访问的页面可能会很快被再次访问； 长期未被访问的页面最近可能不会被访问。
LRU算法一般适用于各种类型的程序，但由于系统必须经常记录和更新各个页面的访问历史，开销过大，LRU算法需要硬件支持。
2.3.2算例仍以OPT算例为例。
中断次数为6，缺页中断率为7/12*100%=58.3%。
堆栈LRU实现：
使用特殊堆栈存储内存中每页的页码。 每次访问一页时进行调整。 也就是说，从堆栈中删除被访问的页面的页码，并将其推入堆栈的顶部。 因此，堆栈的顶部始终是最新访问的页面的页码，而堆栈的底部始终是最近未访问的页码。 发生页面错误时，总是会丢弃与堆栈底部的页码相对应的页面。