操作系统大作业(含课程设计)

“计算机操作系统”课程设计大作业一、题目:页面置换算法模拟实验二、目的分别采用最佳(Optimal)置换算法、先进先出(FIFO)页面置换算法和最近最少使用(LRU)置换算法对用户输入的页面号请求序列进行淘汰和置换，从而加深对页面置换算法的理解。三、内容和要求请用C/C++语言编一个页面置换算法模拟程序。用户通过键盘输入分配的物理内存总块数，再输入用户逻辑页面号请求序列，然后分别采用最佳(Optimal)置换算法、先进先出(FIFO)页面置换算法和最近最少使用(LRU)置换算法三种算法对页面请求序列进行转换，最后按照课本P150页图4-26的置换图格式输出每次页面请求后各物理块内存放的虚页号，并算出每种算法的缺页次数。最后评价三种页面置换算法的优缺点。三种页面置换算法的思想可参考教材P149-P152页。假设页面号请求序列为4、3、2、1、4、3、5、4、3、2、1、5，当分配给某进程的物理块数分别为3块和4块时，试用自己编写的模拟程序进行页面转换并输出置换图和缺页次数。四、提交内容本大作业每个人必须单独完成，大作业以WORD附件形式提交。最后需提交的内容包括：算法算法思路及流程图、数据结构说明、源程序（关键代码需要注释说明）、运行结果截图、心得体会及总结。大作业严禁抄袭。发现抄袭一律以不及格论。请大家严格按照大作业题目来编写程序，不要上交以前布置的大作业。如果提交的大作业题目与本文档要求不符，成绩一律为不及格。请大家按时在网院网上系统里提交大作业，过了规定时间将无法再补交大作业。答：一、思路页面置换算法：当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。熟悉UNIX/LINUX的常用基本命令，练习并掌握UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序，学会如何把学到的知识用于解决实际问题，培养学生！二、各模块的伪码算法（1）先进先出算法伪码算法voidfifo()//先进先出算法{ inti=2,m,j; queye=1; a[1][0]=a[0][0]; for(j=1;j<20;j++) { if(i>3)i=1; if(find(j)=='F')//调用查找函数 { a[i][j]=a[0][j]; for(m=1;m<4;m++) { if(m!=i)a[m][j]=a[m][j-1];} queye=queye+1; i=i+1; } else { a[1][j]=a[1][j-1]; a[2][j]=a[2][j-1]; a[3][j]=a[3][j-1]; return('F');}（2）OPT置换算法伪码算法voidopt()//OPT置换算法{ inti,j,m,t; a[1][0]=a[0][0]; for(j=1;j<3;j++) { for(i=1;i<j+2;i++) { if((i-j)==1) a[i][j]=a[0][j]; else a[i][j]=a[i][j-1]; } }intfindo(intj)//查找OPT的函数{ if(a[1][j-1]==a[0][m])x=m; if(a[2][j-1]==a[0][m])y=m; if(a[3][j-1]==a[0][m])z=m; } //max=x; t=1; if(y>x&&y>z)t=2; if(z>x&&z>y)t=3; return(t);}（3）LRu置换算法伪码算法voidlru()//LRu置换算法{ intu,j,i;intk;a[1][0]=a[0][0]; //a[1][1]=a[0][0]; for(j=1;j<3;j++) { for(i=1;i<j+2;i++) { if((i-j)==1) a[i][j]=a[0][j]; else a[i][j]=a[i][j-1]; } } queye=3; for(j=3;j<20;j++) { if(find(j)=='T')//调用查找函数 { } a[3][j]=a[0][j]; intl(intj)//查找要替换的位置{ if(a[0][j]==a[1][j-1])return(1); if(a[0][j]==a[2][j-1])return(2); if(a[0][j]==a[3][j-1])return(3);}3、函数的调用关系图Voidfifo()函数流程图：

Char

find()函数流程图：

Void

opt()流程图：

int

findo()流程图：

Void

lru()流程图：

Int

l()流程图：

4、测试请求页式存储管理中常用页面置换算法运行结果部分源程序代码：#include"stdio.h"charfind(intj);intfindo(intj);intl(intj);intqueye;doublequeyelu;charz='%';chara[4][20]={'7','0','1','2','0','3','0','4','2','3','0','3','2','1','2','0','1','7','0','1'};//chara[][];voidfifo()//先进先出算法{inti=2,m,j; queye=1; a[1][0]=a[0][0]; for(j=1;j<20;j++) { if(i>3)i=1; if(find(j)=='F')//调用查找函数 { a[i][j]=a[0][j]; for(m=1;m<4;m++) { if(m!=i)a[m][j]=a[m][j-1];} queye=queye+1; i=i+1; } else { a[1][j]=a[1][j-1]; a[2][j]=a[2][j-1]; a[3][j]=a[3][j-1]; } } for(i=0;i<4;i++)//输出序列 { for(j=0;j<20;j++)体会与自我评价

这次操作系统课程设计，让我们对操作系统有了更深的认识，首先操作系统是一管理电脑硬件与软件资源的程序，同时也是计算机系统内核与基石。在进程运行过程中，若其访问的页面不在内存而需把它们调入内存，但内存以无空闲空间时，为了保证该进程能正常的运行，系统必须从内存中调出一