1、院 系：计 算 机 学 院实验课程： 操作系统实验项目：模拟操作系统的页面置换指导老师： 陈红英老师开课时间：2011 2012 年度第 2 学期专 业：网络工程班 级：10 级学 生：yuth学 号：*华南师范大学教务处一、综合设计实验题目 模拟操作系统的页面置换1、 采用一种熟悉的语言，如 C、PASCAL 或 C+ 等，编制程序，最好关键代码采用 C/C+ ，界面设计可采用其它自己喜欢的语言。 2、 模拟操作系统采用 OPT、FIFO 和 LRU 算法进行页面置换的过程。 3、 设程序中地址范围为 0 到 32767 ，采用随机数生成 256 个指令地址，满足 50%的地址是顺序执行，2
2、5%向前跳，25% 向后跳。为满足上述条件，可采取下列方法：设 d0=10000，第 n 个指令地址为 dn，第 n+1 个指令地址为 dn+1 ，n 的取值范围为 0 到 255。每次生成一个 1 到 1024 范围内的随机数 a，如果 a 落在 1 到512 范围内，则 dn+1 =dn+1。如果 a 落在 513 到 768 范围内，则设置 dn+1 为 1 到 dn 范围内一个随机数。如果 a 落在 769 到 1024 范围内，则设置 dn+1 为 dn2到 32767 范围内一个随机数。 例如：srand(); 初始化一个随机函数。 a0 10*rand()/32767*255+1
3、;a1=10*rand()/32767*a0语句可用来产生 a0与 a1中的随机数。或采用以下方式：（1）通过随机数产生一个指令序列，共 320 条指令。指令的地址按下述原则生成： A：50% 的指令是顺序执行的 B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是： A：在0 ，319的指令地址之间随机选取一起点 m B：顺序执行一条指令，即执行地址为 m+1 的指令 C：在前地址0,m+1中随机选取一条指令并执行，该指令的地址为 m D：顺序执行一条指令，其地址为 m+1 E：在后地址m+2 ，3 19中随机选取一条指令并执行 F：重复步骤 A-
4、E，直到 320 次指令 （2）将指令序列变换为页地址流 设：页面大小为 1K； 用户内存容量 4 页到 32 页； 用户虚存容量为 32K。 在用户虚存中，按每 K 存放 10 条指令排列虚存地址，即 320 条指令在虚存中的存放方式为： 第 0 条-第 9 条指令为第 0 页（对应虚存地址为0，9） 第 10 条-第 19 条指令为第 1 页（对应虚存地址为10，19） 第 310 条-第 319 条指令为第 31 页（对应虚存地址为310，319） 按以上方式，用户指令可组成 32 页。 4、 页面大小的取值范围为 1K，2K，4K，8K，16K 。按照页面大小将指令地址转化为页号。对于
5、相邻相同的页号，合并为一个。 5、 分配给程序的内存块数取值范围为 1 块，2 块，直到程序的页面数。 6、 分别采用 OPT、FIFO 和 LRU 算法对页号序列进行调度，计算出对应的缺页中断率。 7、 打印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。 8、 分析页面大小和分配给程序的内存块数对缺页中断率的影响。分析不同的页面置换算法的调度性能。 二、中文摘要 这次实验是模拟操作系统的页面置换，分别用先进先出算 FIFO、最近最久未使用算法 LRU 和最佳淘汰算法 OPT 等三种置换算法来管理管理内存块，并打印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。最后3
6、对不同算法的调度性能。三、关键词 页面置换 FIFO LRU OPT四、前言本实验的目的及要求1、掌握操作系统的页面置换过程，加深理解页式虚拟存储器的实现原理。 2、掌握用随机数生成满足一定条件的指令地址流的方法。 3、掌握页面置换的模拟方法。 五、实验设计 （一） 、需求分析1、用一种熟悉的语言，如 C、PASCAL 或 C+等，编制程序。2、分别采用 OPT、FIFO 和 LRU 算法对页号序列进行调度。（二） 、设计流程1、根据实验目标，明确实验的具体任务；2、编写程序实现页面置换；3、运行程序，调试；4、记录并分析实验结果。（二） 、关键技术根据实验要求，使得 50%的指令地址是顺序执
7、行，25%向前跳，25% 向后跳。可采取下列方法：设 d0=10000，第 n 个指令地址为 dn，第 n+1 个指令地址为 dn+1 ，n 的取值范围为 0 到 255。每次生成一个 1 到 1024 范围内的随机数 a，如果 a 落在 1 到 512 范围内，则 dn+1 =dn+1。如果 a 落在 513 到 768 范围内，则设置 dn+1 为 1 到 dn 范围内一个随机数。如果 a 落在 769 到 1024 范围内，则设置 dn+1 为 dn 到 32767 范围内一个随机数。开一个数组 address来记录指令地址，另一个数组 pagenum记录指令地址转换后所在的页，这样就得
8、到原始程序的页面访问序列。然后将相邻相同的页号合并。（三）详细设计 1、设计算法流程图4程 序 ， 提 供 程 序 的地 址 范 围 和 指 令 数获 取 页 面 大 小将 程 序 分 页获 取 程 序 可 用 内 存 块 数选 择 算 法 进 行页 面 调 度Programpagesizevoid transform(Programp); mem_sumFIFO()LRU()OPT()开 始结 束 endstart2、数据结构/程序类，指明程序地址范围和指令数class Programpublic:int AddressSize; /（0AddressSize）int StructureNu
9、m; /指令数public:Program(int m,int i)AddressSize=m;StructureNum=i; ;/内存块节点类class PhysicsPageNode 5public:int have; /是否有页面占领该内存块， -1 代表没有，1 代表有int Page_Num; /第几页占领该内存块int Elapsed_Time; /内存块的存在时间PhysicsPageNode *next; public:PhysicsPageNode()have=-1;Elapsed_Time=0; /刚生成时内存块的存在时间为 0next = NULL;/模拟操作系统的页面置
10、换类class PageReplacement private:int *address; /存储所有指令的地址int *pagenum; /存储所有指令地址所在的页float instr_sum; /指令数public:int pagesize; /页面大小(字节)int mem_sum; /程序获得的内存块数public:void transform(Program p); /分析程序 p，得到指令页面序列 ,初始化有关成员PhysicsPageNode* getphysage(PhysicsPageNode* pp,int pn); /检查指定页是否已在内存块中PhysicsPageNo
11、de* getfreepage(PhysicsPageNode* pp); /检查是否有空的内存块PhysicsPageNode* getlongelapsed(PhysicsPageNode* pp); /获得最长时间没访问的内存块void FIFO(); /先进先出算法void LRU(); /最近最久未使用算法void OPT(); /最佳淘汰算法;六、实验实现（一） 、实验主要硬件软件环境32 位 PC 机，VC+6.0（二） 、主要功能模块分析61、获得页号序列模块分析程序指令，获得页面序列。Dn 为地址，D0=10000；Dn 的地址获取方法：循环随机一个数 a1,1024;落在
12、1-512，Dn=D （n-1）+1，513-768，Dn 为1D（n-1 ）的随机数。如果 a 落在 769-1024，Dn 为 D（n-1 ）到所分析程序地址大小（32767） 。然后根据页面大小，将各指令地址化为页面号。最后将相邻相同的页号合并。/*分析程序，功能：得到指令页面序列。入口参数：一个程序类，指明程序地址范围和指令数。*/void PageReplacement:transform(Program p)Sleep(10);srand(time(0);int a,q,r;/初始化instr_sum=p.StructureNum;address = new int instr_s
13、um; /存储所有指令的地址pagenum = new int instr_sum;coutnext=np;p=np; for(i=0;iPage_Num=pn;ppn-Elapsed_Time=1; else /获取空闲页失败.置换存在时间最大的页面ppn=getlongelapsed(head);ppn-Page_Num=pn;ppn-Elapsed_Time=1;else /载入的页在内存页中。 /什么也不发生/将在内存中的页存在时间+1PhysicsPageNode *copp=head; while(copp!=NULL)9copp-Elapsed_Time+;copp=copp-n
14、ext;/输出算法，页面大小，缺页中断率等。coutnext=np;p=np;int counter=0; /计数器for(i=0;i30)counter=0; /计数器归零PhysicsPageNode *q=head;/内存页存在时间复位while(q!=NULL)10q-Elapsed_Time=1;q=q-next;pn=pagenumi; /需要载入的页号ppn=getphysage(head,pn); / 是否存在内存页if(ppn=NULL)/ 载入的页不在内存页中/缺页中断次数+1breaktimes+;/获取空闲页面ppn=getfreepage(head);if(ppn!=
15、NULL) /获取成功ppn-Page_Num=pn;ppn-Elapsed_Time=1; else /获取空闲页失败/存在时间最大的为最久未使用。因为每使用一次是减 3 个单位的存在时间。 ppn=getlongelapsed(head); ppn-Page_Num=pn;ppn-Elapsed_Time=1;else /载入的页在内存页中。 ppn-Elapsed_Time=ppn-Elapsed_Time-3;/输出算法，页面大小，缺页中断率等。cout“页面大小=“pagesize“ 内存块数=“mem_sum“ LRU 缺页中断率=“;cout.precision(2); /输出小数点后两位coutbreaktimes/instr_sumendl;4、OPT 模块最优淘汰算法 OPT当页面存在时，存在时间参数不变化。当要淘汰一个页时，预读未来 50 页，并用内存页的存在时间计数。
