《操作系统》课程实验指导书
《操作系统》课程实验
指导书
第 1 页 共 10 页
《操作系统》课程实验指导书
课程实验任务（一）：请求页式存储管理
一、目的与要求
1、目的
近年来，由于大规模集成电路（LSI）和超大规模集成电路（VLSI）技术的发展，使存储器的容量不断扩大，价格大幅度下降。但从使用角度看，存储器的容量和成本总受到一定的限制。所以，提高存储器的效率始终是操作系统研究的重要课题之一。虚拟存储技术是用来扩大内存容量的一种重要方法。学生应独立地用高级语言编写几个常用的存储分配算法，并设计一个存储管理的模拟程序，对各种算法进行分析比较，评测其性能优劣，从而加深对这些算法的了解。 2、 要求
为了比较真实地模拟存储管理，可预先生成一个大致符合实际情况的指令地址流。然后模拟这样一种指令序列的执行来计算和分析各种算法的访问命中率。 二、示例
1、题目 本示例是采用页式分配存储管理方案，并通过分析计算不同页面淘汰算法情况下的访问命中率来比较各种算法的优劣。另外也考虑到改变页面大小和实际存储器容量对计算结果的影响，从而可为算则好的算法、合适的页面尺寸和实存容量提供依据。
本程序是按下述原则生成指令序列的： （1） 50%的指令是顺序执行的。
（2） 25%的指令均匀散布在前地址部分。 （3） 25%的指令均匀散布在后地址部分。
示例中选用最佳淘汰算法（OPT）和最近最少使用页面淘汰算法（LRU）计算页面命中率。公式为
命中率?1?页面失效次数
页地址流长度假定虚存容量为32K，页面尺寸从1K至8K，实存容量从4页至32页。 2、 算法与框图
（1） 最佳淘汰算法(OPT)。 这是一种理想的算法，可用来作为衡量其他算法优劣的依据，在实际系统中是难以实现的，因为它必须先知道指令的全部地址流。由于本示例中已预先生成了全部的指令地址流，故可计算出最佳命中率。
该算法的准则是淘汰已满页表中不再访问或是最迟访问的的页。这就要求将页表中的页逐个与后继指令访问的所有页比较，如后继指令不在访问该页，则把此页淘汰，不然得找出后继指令中最迟访问的页面淘汰。可见最佳淘汰算法要花费较长的运算时间。 （2） 最近最少使用页淘汰算法(LRU)。 这是一种经常使用的方法，有各种不同的实施方案，这里采用的是不断调整页表链的方法，即总是淘汰页表链链首的页，而把新访问的页插入链尾。如果当前调用页已在页表内，则把它再次调整到链尾。这样就能保证最近使用的页，总是处于靠近链尾部分，而不常使用的页就移到链首，逐个被淘汰，在页表较大时，调整页表链的代价也是不小的。 （3） 程序框图如下图2所示。
第 2 页 共 10 页
《操作系统》课程实验指导书
产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产size=1assigned=4产产产产产产AlgAlg=OPT/LRU产OPTLRU产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产产 图2 计算页面命中率框图
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
第 3 页 共 10 页
《操作系统》课程实验指导书
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
*********************************************
(2)示例中使用的有关数据结构、常量和变量说明如下： length 被调试的指令地址流长度，可作为一个常量设定。 called当前请求的页面号。
pagefault页面失效标志，如当前请求页called已在页表内，则置pagefault=false，否则为true。
table 页表。table[i]=j,表示虚存的第j页在实存的第i页中。
used当前被占用的实存页面数，可用来判断当前实存中是否有空闲页。 （3）本程序启动后，屏幕上显示“the algorithm is：”，用户可选择最佳淘汰算法（打入“OPT”）或者最近最少使用淘汰算法(打入“LRU”) 计算页面命中率。当然还可以加入各种其他的算法。 4、小结
(1) 编制评测各种算法性能的模拟程序是研制系统程序，尤其是操作系统所必须的。模
拟的环境愈是真实，其结果愈是可靠，也就更有利于选择合适的方案。本实习虽属
第 4 页 共 10 页
《操作系统》课程实验指导书
简单，但可作为一个尝试。
(2) 注意正整数的范围只能从0??32767，限制程序中的虚存尺寸为32K，实际如采用
更大的虚存实存，更能说明问题。
三、实习题
（1） 编制和调试示例给出的请求页式存储管理程序，并使其投入运行。
（2） 增加1～2种已学过的淘汰算法，计算它们的页面访问命中率。试用各种算法的
命中率加以比较分析。
提示：可选用FIFO方法，即先访问的页先淘汰，也可选用LRU方法中的其他方案。如在页表中设置标志位，按标志位值得变化来淘汰。也可用LFU方法，为页表中各页面设置访问计数器，淘汰访问频率最低的页（注意：当前访问的页不能淘汰）等等。 四、思考题
（1）设计一个界地址存储管理的模拟系统，模拟界地址方式下存储区的分配和回收过程。
提示：必须设置一个内存分配表，按照分配表中有关信息实施存储区的分配，并不断根据存储区的分配和回收修改该表。算法有首次匹配法，循环首次匹配法和最佳匹配法等。可用各种方法的比较来充实实习内容。可使用碎片收集和复盖等技术。 （2）自行设计或选用一种较为完善的内存管理方法，并加以实现。 提示：设计一个段页式管理的模拟程序或通过一个实际系统的消化和分析，编制一个程序来模拟该系统。
第 5 页 共 10 页