内存 FRU 算法
对于虚拟页式存储,内外存信息的替换是以页面为单位进行,当内存中没
有进程所需访问的页面时,内存会产生缺页中断,CPU 要通过内存访问算法去
从外存(硬盘,光盘等)调取页面继续进程的执行,但是把哪个页面调出才会
使程序运行的更快而且不会产生抖动,是值得思考的,现在的内存调度算法有
先进先出 FIFO 算法,最近最少使用 LRU 算法,最近最不常用 LFU 算法,其优
劣高下众说纷纭。
通过大量实验,我发现了内存 FRU 算法,先看内存中有没有需要的页面,
再按先进先出算法进行置换,如果有就不置换,如果没有就置换。
举一个例子,内存中有 3 个活动页面,其余在硬盘的虚拟内存上,如果进
程按 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3 的顺序请求页面,那么
内存的调入情况如下表:
进程页面
内存页面
1
1
2
2
1
2
3
3
2
1
3
4
4
3
2
4
2
4
3
2
4
1
1
4
3
5
5
5
1
4
6
6
6
5
1
7
2
2
6
5
8
1
1
2
6
9
2
1
2
6
9
3
3
1
2
7
7
3
1
6
6
7
3
3
6
7
3
1#页面
2#页面
3#页面
缺页中断 1 10 11 12 13
由上表可知,采用 FRU 算法对于 15 个请求页面会产生 13 次缺页中断,此处 C
语言代码不再赘述。