请求页式存储管理 Linux 课程设计

一、目的与要求
1、目的
近年来，由于大规模集成电路（LSI）和超大规模集成电路（VLSI）技术的发展，使存储器的容量不断扩大，价格大幅度下降。但从使用角度看，存储器的容量和成本总受到一定的限制。所以，提高存储器的效率始终是操作系统研究的重要课题之一。虚拟存储技术是用来扩大内存容量的一种重要方法。学生应独立地用高级语言编写几个常用的存储分配算法，并设计一个存储管理的模拟程序，对各种算法进行分析比较，评测其性能优劣，从而加深对这些算法的了解。
任务三采用最佳淘汰算法(OPT)实现，任务四采用最近最少使用页淘汰算法(LRU)实现。
2、 要求
为了比较真实地模拟存储管理，可预先生成一个大致符合实际情况的指令地址流。然后模拟这样一种指令序列的执行来计算和分析各种算法的访问命中率。
二、示例
1、题目 本示例是采用页式分配存储管理方案，并通过分析计算不同页面淘汰算法情况下的访问命中率来比较各种算法的优劣。另外也考虑到改变页面大小和实际存储器容量对计算结果的影响，从而可为算则好的算法、合适的页面尺寸和实存容量提供依据。
本程序是按下述原则生成指令序列的：
（1） 50%的指令是顺序执行的。
（2） 25%的指令均匀散布在前地址部分。
（3） 25%的指令均匀散布在后地址部分。
示例中选用最佳淘汰算法（OPT）和最近最少使用页面淘汰算法（LRU）计算页面命中率。公式为
命中率=1-页面失效次数/页地址流长度
 
假定虚存容量为32K，页面尺寸从1K至8K，实存容量从4页至32页。
2、 算法与框图
（1） 最佳淘汰算法(OPT)。
这是一种理想的算法，可用来作为衡量其他算法优劣的依据，在实际系统中是难以实现的，因为它必须先知道指令的全部地址流。由于本示例中已预先生成了全部的指令地址流，故可计算出最佳命中率。
该算法的准则是淘汰已满页表中不再访问或是最迟访问的的页。这就要求将页表中的页逐个与后继指令访问的所有页比较，如后继指令不在访问该页，则把此页淘汰，不然得找出后继指令中最迟访问的页面淘汰。可见最佳淘汰算法要花费较长的运算时间。
（2） 最近最少使用页淘汰算法(LRU)。
这是一种经常使用的方法，有各种不同的实施方案，这里采用的是不断调整页表链的方法，即总是淘汰页表链链首的页，而把新访问的页插入链尾。如果当前调用页已在页表内，则把它再次调整到链尾。这样就能保证最近使用的页，总是处于靠近链尾部分，而不常使用的页就移到链首，逐个被淘汰，在页表较大时，调整页表链的代价也是不小的。


3、程序运行结果格式
(1) 程序运行结果格式
THE VIRTUAL ADDRESS STREAM AS FOLLOWS:
a[0] =16895 a[1]=16896 a[2]=16897 a[3]=16302
a[4]=25403 a[5]=13941 a[6]=13942 a[7]=8767
……
……
……
A[252]=23583 a[253]=20265 a[254]=20266 a[255]=20267
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
The algorithm is:opt
PAGE NUMBER WITH SIZE 1k FOR EACH ADDRESS IS:
pageno[0]=17 pageno[1]=17 pageno[2]=17 pageno[3]=16
pageno[4]=25 pageno[5]=14 pageno[6]=14 pageno[7]=9
……
……
……
pageno[252]=24 pageno[253]=20 pageno[254]=20 pageno[255]=20

vmsize=32k pagesize=1k
------------- --------------
page assigned pages_in/total references
4 7.031250000000000E-1
6 7.578125000000000E-1
8 8.085937500000000E-1
10 8.554687500000000E-1
12 8.945312500000000E-1
14 9.140625000000000E-1
16 9.140625000000000E-1
18 9.140625000000000E-1
20 9.140625000000000E-1
22 9.140625000000000E-1
24 9.140625000000000E-1
26 9.140625000000000E-1
28 9.140625000000000E-1
30 9.140625000000000E-1
32 9.140625000000000E-1
PAGE NUMBER WITH SIZE 2k EACH ADDRESS IS:
……
……
……
PAGE NUMBER WITH SIZE 4k EACH ADDRESS IS:
……
……
……
PAGE NUMBER WITH SIZE 8k EACH ADDRESS IS:
……
……
……
End the result for opt
** **********************************************
the algorithm is lru
……
……
……同上
End the result for lru
*********************************************

任务量巨大，存储管理和任务调度是Linux中最复杂的两部分，关注~

而不常使用的页就移到链首，逐个被淘汰，在页表较大时，调整页表链的代价也是不小的。

---

你要是仔细设计的话，LRU的时间损耗是1，即“常数损耗”。

。。。求牛人