请求页式管理缺页中断模拟设计--+LRU随机淘汰算法

1、学 号： 0120610340231课 程 设 计题 目请求页式管理缺页中断模拟设计- LRU、随机淘汰算法学 院计算机学院专 业计算机科学与技术班 级计算机0602姓 名朱 林指导教师王 红 霞2009年01月08日课程设计任务书学生姓名： 朱 林 专业班级： 计算机0602 指导教师： 王红霞 工作单位： 计算机科学与技术学院 题 目:请求页式管理缺页中断模拟设计- LRU、随机淘汰算法初始条件：1预备内容：阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页式存储管理等概念，并体会和了解缺页和页面置换的具体实施方法。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括

2、课程设计工作量及其技术要求，以及说明书撰写等具体要求）1实现指定淘汰算法。能够处理以下的情形： 能够输入给作业分配的内存块数； 能够输入给定的页面，并计算发生缺页的次数以及缺页率； 缺页时，如果发生页面置换，输出淘汰的页号。2设计报告内容应说明： 需求分析； 功能设计（数据结构及模块说明）； 开发平台及源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；v）对实

3、验题的评价和改进意见，请你推荐设计题目。时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，一律按0分记）指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日请求页式管理缺页中段模拟设计 LRU、随机淘汰算法1需求分析 用一种计算机高级语言来实现请求页式管理缺页中段模拟设计的LRU和随机淘汰算法，设计要求如下： 能够输入给作业分配的内存块数； 能够输入给定的页面，并计算发生缺页的次数以及缺页率； 缺页时，如果发生页面置换，输出淘汰的页号。 请求分页流程图： 2功能设计 2.1数据

4、结构 （1）用结构体定义页表表项： struct page int page_num; /页面号 int memory_num; /页面对应的内存物理块号 int flag; /状态标志，判断页面是否在内存 ; (2)算法中涉及到的主要变量： int page_size; /给定的页面数 int memory_size; /给定的内存物理块数 int *page_array, /存放页面的输入序列 int *memory; /存放内存物理块的序列 int lacktime; /缺页次数 int page; /当前页面号 int *save； /保存被淘汰的页面号(随机算法中) int *cha

5、nge_page; /保存被淘汰的页面号(LRU算法中) int *weight; /记录内存中页面的存在次数(LRU算法中) bool in; /标志页面是否在内存中(LRU算法中) 2.2模块说明 (3)LRU淘汰算法 void LRU() 用一个整形指针change_page保存被淘汰的页面号； 用一个整形指针weight记录内存中各页面的存在次数； a.若当前页在内存中，置in的值为1； b.若当前页不在内存中且内存已满，lacktime加1，比较内存中的页面的weight值，weight值最大的那个页面即为将要被淘汰的页，然后将当前页装入内存，并修改当前页和被淘汰页的页表内容； c.

6、若当前页不在内存中且内存未满，lacktime加1，将此页装入内存，并修改页表表项的内容； 输出lacktime的值，缺页率和被淘汰的页面号； (4)随机淘汰算法 void random() 用一个整形指针save保存被淘汰的页面号； do a.若当前页面在内存中，输出相关信息； b.若当前页面不在内存中，lacktime加1，将此页面装入内存，并修 改页表表项的相应内容； while(内存未满) 当内存已满时： a.若当前页面在内存中，输出相关信息； b.若当前页面不在内存中，lacktime加1，随机淘汰内存中的一个页面，将被淘汰的页面号保存在save中，并修改被淘汰和当前页面 在页表中的

7、相应内容； 输出lacktime的值，缺页率和被淘汰的页面号； 3开发平台及源程序主要部分 3.1开发平台 （1）使用系统：Windows XP （2）使用语言：C+ （3）开发工具：Visual C+ 6.0 3.2源程序主要部分 随机淘汰算法： void random() cout<<"-随机-"<<endl;init();int *save=new intpage_size;int count=0;cout<<"随机替换算法:"<<endl;int lackTime=0;int replace=0;

8、int is_full=0;int page=0;do if(page_tablepage_arraypage.flag =1) cout<<page_arraypage<<" is in memory"<<endl;page+;if(page=page_size)break;else continue; elselackTime+; cout<<page_arraypage<<"is not in memory!"<<endl; memoryis_full=page_arraypa

9、ge; page_tablepage_arraypage.flag=1;page_tablepage_arraypage.memory_num=is_full; is_full+;page+;if(page=page_size)break;while(is_full!=memory_size); for( int i=page;i<page_size;i+) if(page_tablepage_arrayi.flag =1) cout<<page_arrayi<<" is in memory"<<endl;continue; els

10、e lackTime+; replace=rand()%memory_size; for(int j=0;j<10;j+) if( page_tablej.memory_num=replace) cout<<page_arrayi<<"is not in memory!take place of page "<<j<<endl; savecount+=j; page_tablej.memory_num=-1; page_tablej.flag=0; break; memoryreplace=page_arrayi; pa

11、ge_tablepage_arrayi.flag=1;page_tablepage_arrayi.memory_num=replace; cout<<"缺页次数："<<lackTime<<endl;cout<<"缺页率： "<<double(lackTime)/page_size*100<<"%"<<endl;cout<<"淘汰页号的序列为："for(int i=0;i<count;i+) cout<<

12、savei<<"->"cout<<"结束"<<endl;cout<<"-"<<endl;LRU淘汰算法：void LRU()cout<<"-LRU-"<<endl;init();int *change_page=new intpage_size;int *weight=new int memory_size;int i;for(i=0;i<memory_size;i+) memoryi=-1; for(i=0;i<

13、page_size;i+) change_pagei=0; int lackTime=0;int k=0,l=0; bool in=0; int max=0;int q; for(q=0;q<memory_size;q+)cout<<memoryq<<" "cout<<endl; for(i=0;i<page_size;i+) in=0;for(q=0;q<memory_size;q+) if (page_arrayi=memoryq)in=1;break; if(in=0 && memorymemory

14、_size-1!=-1)lackTime+;for(q=0;q<memory_size;q+)weightq=0;for(q=0;q<memory_size;q+)for(int p=i-1;p>=0;p-) weightq+;if(memoryq=page_arrayp)break; max=0; for(q=0;q<memory_size;q+) if(weightq>max) max=weightq;for(q=0;q<memory_size;q+)if (max=weightq) break; change_pagek+=memoryq; memor

15、yq=page_arrayi; if(in=0 && memorymemory_size-1=-1) lackTime+; memoryl+=page_arrayi; for(int q=0;q<memory_size;q+) cout<<memoryq<<" "cout<<endl; cout<<"缺页次数："<<lackTime<<endl; cout<<"缺页率："<<double(lackTime)/page_

16、size*100<<"%"<<endl; cout<<"淘汰页号：" for(int m=0;m<k;m+) cout<<change_pagem<<"->" cout<<"结束"<<endl; cout<<"-LRU-"<<endl;main()函数int main() int select1;int select2;char choice;cout<<"

17、;输入给定的页面数："<<endl;cin>>page_size;cout<<"输入给作业分配内存的物理块数"<<endl;cin>>memory_size;page_array=new intpage_size;memory=new intmemory_size; loop:cout<<"0.用户输入请求序列 1.随机生成请求序列"<<endl; cin>>select1;if(select1=1) cout<<"随机生成页面

18、请求序列（0-10）"<<endl;int temp1;for(int i=0;i<page_size;i+) temp1=rand()%10; cout<<temp1<<" "page_arrayi=temp1; cout<<endl;else if(select1=0) int temp2;cout<<"输入"<<page_size<<"个请求页面号（0-10）"<<endl;for(int i=0;i<page_

19、size;i+) cin>>temp2;page_arrayi=temp2;else exit(0); cout<<"请选择使用那种替换算法：0、退出 1、LRU 2、随机"<<endl;cin>>select2;if(select2=1) LRU();else if(select2=2) random();else exit(0); cout<<"是否继续？（Y/y or N/n）"cin>>choice;if(choice='Y' | choice='y&

20、#39;) goto loop;else exit(0);delete page_array;delete memory;return 0;4调试报告 4.1测试用例 随机淘汰算法： 输入的页面号序列为：1 3 2 4 2 1 2 1 3 4 ，给定内存物理块数为3。 LRU淘汰算法：输入的页面号序列为：4 2 1 2 3 5 4 3 1 2，给定内存物理块数为3。 4.2运行结果及分析 随机淘汰算法的运行结果如下： 结果分析，如下表： 1 3 2 4 2 1 2 1 3 4 1 1 1 1 1 1 1 1 1 1 3 3 4 4 4 4 4 3 3 2 2 2 2 2 2 2 4 LRU淘汰

21、算法的运行结果如下： 结果分析，如下表： 4 2 1 2 3 5 4 3 1 2 4 4 4 4 3 3 3 3 3 3 2 2 2 2 2 4 4 4 2 1 1 1 5 5 5 1 15总结在本次操作系统课程设计，我采用C+实现请求页式管理缺页中段模拟设计的随机和LRU淘汰算法。首先，应了解虚拟存储器和页式存储管理的有关内容，并掌握随机和LRU淘汰算法的核心思想及具体的流程。然后，在这个基础上，结合所掌握的C+编程方法和技巧，编写正确的算法。 随机淘汰算法比较容易实现，当需要调入一个新页面进入内存时，用rand()函数产生一个0memory_size-1的随机数，作为将要被淘汰的内存物理块

22、号，然后修改页表内容即可。LRU算法就显得复杂一些，其核心问题在于怎样找到内存中最近最少使用的那个页面。最初设计这个算法时，出现了一点问题，在某种情况下，会淘汰刚刚被访问过的页面。经过修改，弥补了这个不足之处，算法的运行结果正确。 从这次的课程设计中，我有很大收获。首先，巩固了所学的有关页式存储管理的相关知识，更深层次地理解并掌握了LRU和随机淘汰算法的精髓。通过使用C+语言模拟LRU和随机算法实现请求页式管理，进一步提高了我的编程能力，并且有助于将操作系统和C+有机地结合起来，使我更加明白了学科之间是紧密联系的。 此外，经过这次课程设计，我更加感悟到了，仅仅学习书本上的理论知识是不够的，要在

23、平时多进行实际操作，这样才能融会贯通，更加牢固地掌握所学知识。在以后的学习过程中，我应该更加深入学习有关C+的内容，提高自己的动手能力。 附录：F1参考文献1张尧学，史美林编著计算机操作系统教程（第三版）清华大学出版社2006 2闵联营，何克右C+程序设计教程武汉理工大学出版社2005F2源代码#include<iostream>using namespace std;struct page int page_num; int memory_num; int flag; ;page page_table10;int page_size,memory_size;int *page_a

24、rray,*memory;void init() for(int i=0;i<10;i+) page_tablei.page_num=i;page_tablei.memory_num=-1;page_tablei.flag=0;for(int i=0;i<memory_size;i+)memoryi=-1;void random()cout<<"-随机-"<<endl;init();int *save=new intpage_size;int count=0;cout<<"随机替换算法:"<<e

25、ndl;int lackTime=0;int replace=0; int is_full=0;int page=0;do if(page_tablepage_arraypage.flag =1) cout<<page_arraypage<<" is in memory"<<endl;page+;if(page=page_size)break;else continue; else lackTime+; cout<<page_arraypage<<"is not in memory!"<&

26、lt;endl; memoryis_full=page_arraypage; page_tablepage_arraypage.flag=1;page_tablepage_arraypage.memory_num=is_full； is_full+;page+;if(page=page_size)break;while(is_full!=memory_size); for( int i=page;i<page_size;i+)if(page_tablepage_arrayi.flag =1) cout<<page_arrayi<<" is in memo

27、ry"<<endl;continue;else lackTime+; replace=rand()%memory_size; for(int j=0;j<10;j+) if( page_tablej.memory_num=replace) cout<<page_arrayi<<"is not in memory!take place of page "<<j<<endl; savecount+=j; page_tablej.memory_num=-1; page_tablej.flag=0; bre

28、ak; memoryreplace=page_arrayi; page_tablepage_arrayi.flag=1;page_tablepage_arrayi.memory_num=replace; cout<<"缺页次数："<<lackTime<<endl;cout<<"缺页率： "<<double(lackTime)/page_size*100<<"%"<<endl;cout<<"淘汰页号的序列为："for(in

29、t i=0;i<count;i+) cout<<savei<<"->"cout<<"结束"<<endl;cout<<"-"<<endl;void LRU() cout<<"-LRU-"<<endl;init();int *change_page=new intpage_size;int *weight=new int memory_size;int i;for(i=0;i<memory_size;i+)

30、 memoryi=-1; for(i=0;i<page_size;i+) change_pagei=0; int lackTime=0; int k=0,l=0; bool in=0; int max=0;int q; for(q=0;q<memory_size;q+)cout<<memoryq<<" " cout<<endl; for(i=0;i<page_size;i+) in=0; for(q=0;q<memory_size;q+) if (page_arrayi=memoryq) in=1;break; i

31、f(in=0 && memorymemory_size-1!=-1) lackTime+; for(q=0;q<memory_size;q+)weightq=0; for(q=0;q<memory_size;q+) for(int p=i-1;p>=0;p-) weightq+; if(memoryq=page_arrayp)break; max=0; for(q=0;q<memory_size;q+) if(weightq>max) max=weightq; for(q=0;q<memory_size;q+) if (max=weightq

32、) break; change_pagek+=memoryq; memoryq=page_arrayi; if(in=0 && memorymemory_size-1=-1) lackTime+; memoryl+=page_arrayi; for(int q=0;q<memory_size;q+)cout<<memoryq<<" "<<endl;cout<<"缺页次数："<<lackTime<<endl;cout<<"缺页率："<<double(lackTime)/page_size*100<<"%"<<endl;cout<<"淘汰页号："for(int m=0;m<k;m+) cout<<change_pagem<<"->"cout<<&quo