操作系统课程设计页面置换算法(LRU算法)

1、实 验 报 告题 目名 称页面置换算法(LRU算法)院 系信 息 学 院班 级1106402完成时间2013-05-17指导老师肖赛男本次实验成绩组长联系电话李国件地址394600097组员（姓名，学号）吕赟1106402-38主要任务算法的组织，综合调度，程序运行界面的实现组员（姓名，学号）蔡祥1106402-09主要任务算法的实现，测试，实验报告的完成主要原理及所参考的资料（包括实验内容及条件）实验原理：页面置换算法(LRU算法) 假定一个能够存放M个页面的内存，当发生缺页时，调入一个页面，通过LRU算法求出应该置换出的页面号。输入一连串的页面号，程序

2、自动选择调出的页面并计算缺页率。设计页面置换算法，这里采用最近最久未使用置换算法LRU。LRU算法的实现要归功于一个8位的寄存器的实现。主要参考书计算机操作系统原理 西安大学出版社 汤子瀛主编操作系统 电子工业出版社 William Stallings著主要算法流程图（包括实验步骤）算法流程图：输入页面访问序号取访问页的页号查夜表是否缺页否置换出寄存器数组页面标号最小的页面是按算法不同淘汰一页面调入所访问的页面实验说明：执行程序时，当主存没有可用页面时，为了选择淘汰主存中的哪一页面，腾出1个空闲块以便存放新调入的页面。淘汰哪个页面的首要问题是选择何种置换算法。该程序采用LRU方法选择，依置换策

3、略选择一个可置换的页面并计算它们的缺页率以便比较。本实验涉及的主要算法细节说明（包括数据结构）#include#include#define M 3#includeint reg2M;int count;int num;int N;/*初始化函数，数组reg0i存放页面号，初始化为-1，reg1i当作寄存器，初始化为0*/void init()int i;count=0;num=0; N=pow(2,7); /*二进制数10000000*/for(i=0;iM;i+)reg0i=-1;reg1i=0;/*寻找数组a中的最小值，返回最小值对应的下标*/int min(int a)int i,in

4、dex=0;int min=a0;for(i=1;iai)min=ai;index=i;return index;/*判断页面号x是否在数组中，如果在，返回对应的下标；否则返回-1*/int isIn(int x,int a)int i;int index=-1;for(i=0;iM;i+)if(ai=x)index=i;break;return index;/*判断虚拟的内存中是否已经存满了页面，如果满了，则返回-1，没有满则返回找到空的对应的第一个下标*/int isFull(int a)int i,index=-1;for(i=0;iM;i+)if(ai=-1)index=i;break

5、;return index;/*页面置换方法*/void swap(int x)int i,k,temp,temp0;int index=isIn(x,reg0); /*判断x是否在reg0数组中*/if(index!=-1)reg1index=reg1indexN; /*reg1index异或二进制数10000000*/elsetemp=isFull(reg0);if(temp!=-1) /*内存没有满，直接调入页面*/reg0temp=x;reg1temp=reg1tempN;else if(temp=-1)k=min(reg1); /*置换出寄存器中数值最小的对应的下标的页面*/temp

6、0=reg0k; /*临时保留要换出的页面号*/reg0k=x;reg1k=reg1kN;printf(the page %d is exchanged out!n,temp0);/*打印要置换出的页号*/count+; /*置换次数加1*/for(i=0;i1; /*寄存器中的所有数右移一位*/main()int x;system(cls);init();printf(Input a sort of pagesn);printf(while you input -1 ,it will stop!n);scanf(%d,&x);/*输入页面号，直到页面号为-1*/while(x!=-1)num

7、+; /*输入的页面次数加1*/swap(x);scanf(%d,&x);/*打印缺页数和缺页率*/printf(the count of Exchanged is: %d n,count);printf(the rate of exchanged is: %fn,count*1.0/num);getch();本次实践计划、进度安排及完成情况05月09号商讨如何实现本次实验以及同学之间的分工.05月10号查阅相关资料.05月16号05月17号基本完成程序修改完善程序.代码测试.完成实验报告.主要测试方法及测试数据，包括测试结果及测试人实验结果：Input a sort of pageswhil

8、e you input -1 ,it will stop!7012the page 7 is exchanged out!03the page 1 is exchanged out!04the page 2 is exchanged out!2the page 3 is exchanged out!43the page 0 is exchanged out!0the page 2 is exchanged out!-1The count of exchange is: 6The rate of exchange is: 0.500000本次实验的心得体会（每位同学一段）李国红通过这次实验，让我了解了页式存储管理的过程。在这次实验中，我首次用了C中重要的但我们又不常用的按位异或操作和移位操作来实现寄存器的功能，使我对C有更深的认识。本次实验也让我学到了LRU算法。吕赟通过本次课程设计，对LRU页面调度算法有了更深入的理解和掌握，进一步的巩固和复习了操作系统中关于LRU页面调度算法的知识，进一步的了解结构化、模块化程序设计的方法蔡祥通过这次实验，让我了解了页面储存管理的过程。这次实验中，我