操作系统课设页面置换算法

操作系统课设页面置换算法 沈阳理工大学课程设计专用纸 No1 目录 一、课程设计目的及要求 ................................ 1 二、相关知识 .......................................... 1 三、题目分析 .......................................... 2 四、概要设计 .......................................... 3 五、代码及流程 ........................................ 3 六、运行结果 .......................................... 7 七、设计心得 .......................................... 8 八、参考文献 .......................................... 9 1 沈阳理工大学课程设计专用纸 No1 一、课程设计目的及要求 页面置换算法 实验目的:深入掌握内存调度算法的概念原理和实现方法。 设计要求:编写程序实现:1)先进先出页面置换算法(FIFO) 2)最近最久未使用页面置换算法(LRU) 3)最佳置换页面置换算法(OPT) 演示页面置换的三种算法。 二、相关知识 2.1 先进先出(FIFO)算法 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。 2.2 最近最久未使用(LRU)算法 FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历 ，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面的时间t 予以淘汰。 2.3 最佳(Optimal)算法 1 沈阳理工大学课程设计专用纸 No1 最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰的页面，将是以后永不使用的，或是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是将来最长时间内不再访问的，因而该算法时无法实现的，但可以利用该算法评价其他算法。 三、题目分析 熟悉页面置换算法及其实现。页面置换算法是虚拟存储管理实现的关键，通过本次课程设计理解内存页面调度的机制，在模拟实现FIFO、LRU和OPT几种经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。 2 沈阳理工大学课程设计专用纸 No1 四、概要设计 4.1进入系统模块。进入登陆界面，输入内存页面数和实际页数。 4.2页面号打印模块。打印输入的页面号。 4.3菜单选择模块。选择相应的页面的置换方式，选择相应的字母，进入相应的 功能。 4.4算法模块。选择相应的页面置换算法。 4.5显示输出模块。显示页面被置换的情况。 4.6缺页次数和缺页率模块。计算页面号输入的结果。 4.7退出系统模块。退出置换页面。 五、代码及流程 #include #define M 40 int N; struct Pro//内存页的结构体 { int num,time; }; int Input(int m,Pro p[M]) //输入函数，输入实际页号和实际页数 { cout<<"请输入实际页数:"; do { cin>>m; if(m>M)cout<<"数目太多，请重试"<>p[i].num;//num页面号 p[i].time=0; } return m;//m代表实际页面走向数 } void print(Pro* page1) //打印当前内存中存放的页面 { Pro*page=new Pro[N];//定义一个指针 page=page1; for(int i=0;i>N; Pro p[M]; 4 沈阳理工大学课程设计专用纸 No1 Pro*page=new Pro[N]; char c; int m=0,t=0; float n=0; m=Input(m,p); do{ for(int j=0;j>c; if(c=='f') //FIFO页面置换 { n=0;//记录缺页数 cout<<"页面置换情况: "<=0) ++i;//找到相同的页面 else { n++; page[t].num=p[i].num;//如果没有找到相同的页，则进行页面替换，缺 页数加一 print(page); t=(++t)%N; } } cout<<"缺页次数: "<=0) 5 沈阳理工大学课程设计专用纸 No1 page[t].time=0; else { n++; t=Max(page); page[t].num=p[i].num; page[t].time=0; } if(t==0){page[t+1].time++;page[t+2].time++;} if(t==1){page[2].time++;page[0].time++;} if(t==2){page[1].time++;page[0].time++;} if(k==-1) print(page); i++; } cout<<"缺页次数:"<=0)i++; else { int temp=0,cn; for(t=0;t