操作系统报告3.docx
《操作系统报告3.docx》由会员分享，可在线阅读，更多相关《操作系统报告3.docx（20页珍藏版）》请在冰点文库上搜索。
操作系统报告3
软件学院
实验报告
课程名称：
操作系统原理
实验项目：
虚拟内存页面置换算法
实验室：
姓名：
学号：
专业班级：
实验时间：
2014.12.21
实验成绩
评阅教师
一、实验目的及要求
通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。
结合Linux的内层的分析方法查看内存的分配过程及linuxkernel的内存管理机制。
二、实验性质
设计性
三、实验学时
2学时
4、实验环境
1.实验环境：
C与C++程序设计学习与实验系统
2.知识准备：
（1）使用Linux的基本命令；
（2）了解Linuxvmstat、free、top等命令查看linux系统的内存分配情况；
（3）掌握虚拟内存页面置换算法FIFO等基本算法理论。
五、实验内容及步骤
假设有n个进程分别在T1,…,Tn时刻到达系统，它们需要的服务时间分别为S1,…,Sn。
分别采用先来先服务FCFS和短作业优先SJF进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。
通过已知最小物理块数、页面个数、页面访问序列、及采用置换方式可以得出页面置换的缺页次数和缺页率，及每次缺页时物理块中存储。
1．输入的形式
intPageOrder[MaxNumber];//页面序列
intPageNum,LackNum=0,BlockNum;//页面个数，缺页次数，最小物理块数
2.输出的形式
doubleLackPageRate//缺页率
缺页个数
每次缺页时物理块中存储
程序所能达到的功能
模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。
假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1,…,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。
测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。
程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。
intPageOrder[MaxNumber];//页面序列
intPageCount[MaxNumber]={0};//计算内存内数据离下一次出现的距离
intPageNum,LackNum=0,BlockNum;//页面个数，缺页次数，最小物理块数
doubleLackPageRate=0;
boolfound=false;
3.程序流程图
程序流程图如图5-3-1所示。
图5-3-1算法流程图
六、实验数据及结果分析
（一）调试过程中出现的问题及解决方法
1.遇到的问题
调试中，中文字符出现编码错误；
2.解决方法
更改终端的编码方式。
（2）实验执行的结果
1.FIFO算法执行结果如图6-2-1所示。
图6-2-1FIFO算法执行结果
2.OPT算法执行结果如图6-2-2所示。
图6-2-2OPT算法执行结果
3.LRU算法执行结果如图6-2-3所示。
图6-2-3LRU算法执行结果
七、实验总结
（一）实验过程的收获
通过这次实验，加深了对虚拟内存页面置换概念的理解，进一步掌握了先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。
（2）遇到的问题
（三）解决问题过程的思考
（4）程序调试能力的思考
（5）对本实验的认识及思考
附录源程序清单
1.页面类。
classPage{
privateintid=-1;
privateintcount;
publicintgetId（）{
returnid;
}
publicvoidsetId（intid）{
this.id=id;
}
publicintgetCount（）{
returncount;
}
publicvoidinc（）{
count++;
}
publicvoidsetCount（intcount）{
this.count=count;
}
}
2.FIFO
importjava.util.ArrayList;
importjava.util.Iterator;
importjava.util.List;
importjava.util.Scanner;
publicclassFIFO{
/**
*先进先出算法
*/
privatestaticfinalintPRO_MEMORY=5;//系统分配的内存块数
privatestaticPage[]pages=newPage[PRO_MEMORY];
privatestaticintcountOldPoint;//纪录最久的页面下标
privatestaticintcount;//纪录当前在使用的总页面数
privatestaticintlackTime;//缺页次数
privateListusePageNumList=newArrayList（）;//页面使用列表
publicstaticvoidmain（String[]args）{
System.out.println（"--------先进先出算法------------"）;
FIFOfifo=newFIFO（）;
fifo.init（）;
fifo.input（）;
fifo.running（）;
}
//初始化
publicvoidinit（）{
for（inti=0;ipages[i]=newPage（）;
}
}
//接收用户输入列表
publicvoidinput（）{
System.out.print（"请输入页面使用列表,以空格分开:
"）;
Scannersc=newScanner（System.in）;
Stringinput=sc.nextLine（）;
String[]inputList=input.split（"\\s"）;
try{
for（Stringin:
inputList）{
usePageNumList.add（Integer.valueOf（in））;
}
}
catch（Exceptione）{
System.out.println（"输入的必须是数字,请重新开始！
！
！
"）;
System.exit（0）;
}
}
//系统运行
publicvoidrunning（）{
Iteratorit=usePageNumList.iterator（）;
//列表置入替换
while（it.hasNext（））{
countOldPoint=countOldPoint%PRO_MEMORY;
intinPageId=it.next（）;
//查找内存中是否有该页面
if（search（inPageId））{
System.out.println（"内存中有ID为"+inPageId+"这个页面,不进行替换"）;
}
elseif（countpages[count].setId（（Integer）inPageId）;
System.out.println（"页号ID:
"+pages[count].getId（）+"正在放入内存"）;
count++;
}
else{//替换
replace（inPageId）;
lackTime++;
countOldPoint++;
}
display（）;
}
System.out.println（"缺页次数为:
"+lackTime+",缺页率是:
"+（float）lackTime/usePageNumList.size（））;
}
//查找内存中是否有该页面
publicbooleansearch（intpageId）{
for（inti=0;iif（pages[i].getId（）==pageId）{
returntrue;
}
}
returnfalse;
}
//替换算法
publicvoidreplace（intpageId）{
//置换最久的页面
intoutPageId=-1;
outPageId=pages[countOldPoint].getId（）;
pages[countOldPoint].setId（pageId）;
System.out.println（"页号ID:
"+pageId+"正在放入内存,页号ID:
"+outPageId+"被替换出去"）;
}
//显示当前内存页
publicvoiddisplay（）{
System.out.print（"当前内存保留的页数是:
"）;
for（Pagepage:
pages）{
System.out.print（page.getId（）+""）;
}
System.out.println（）;
}
}
3.OPT
importjava.util.ArrayList;
importjava.util.Iterator;
importjava.util.List;
importjava.util.Scanner;
publicclassOPT{
/**
*最佳置换算法
*/
privatestaticfinalintPRO_MEMORY=5;//系统分配的内存块数
privatestaticPage2[]pages=newPage2[PRO_MEMORY];
privatestaticintcount;//纪录当前在使用的总页面数
privatestaticintlackTime;//缺页次数
privateListusePageNumList=newArrayList（）;//页面使用列表
publicstaticvoidmain（String[]args）{
System.out.println（"--------最佳置换算法------------"）;
OPTopt=newOPT（）;
opt.init（）;
opt.input（）;
opt.running（）;
}
//初始化
publicvoidinit（）{
for（inti=0;ipages[i]=newPage2（）;
}
}
//接收用户输入列表
publicvoidinput（）{
System.out.print（"请输入页面使用列表,以空格分开:
"）;
Scannersc=newScanner（System.in）;
Stringinput=sc.nextLine（）;
String[]inputList=input.split（"\\s"）;
try{
for（Stringin:
inputList）{
usePageNumList.add（Integer.valueOf（in））;
}
}
catch（Exceptione）{
System.out.println（"输入的必须是数字,请重新开始！
！
！
"）;
System.exit（0）;
}
}
//系统运行
publicvoidrunning（）{
Iteratorit=usePageNumList.iterator（）;
intcurrentPoint=0;//当前读取输入列表的下标
//列表置入替换
while（it.hasNext（））{
intinPageId=it.next（）;
//查找内存中是否有该页面
if（search（inPageId））{
System.out.println（"内存中有ID为"+inPageId+"这个页面,不进行替换"）;
}
elseif（countpages[count].setId（（Integer）inPageId）;
System.out.println（"页号ID:
"+pages[count].getId（）+"正在放入内存"）;
count++;
timeRefresh（）;
}
else{//替换
replace（inPageId,currentPoint）;//传入当前下标确定需要遍历的未来输入列表
timeRefresh（）;
lackTime++;
}
currentPoint++;
display（）;
}
System.out.println（"缺页次数为:
"+lackTime+",缺页率是:
"+（float）lackTime/usePageNumList.size（））;
}
//查找内存中是否有该页面
publicbooleansearch（intpageId）{
for（inti=0;iif（pages[i].getId（）==pageId）{
timeRefresh（）;
returntrue;
}
}
returnfalse;
}
//时间更新
publicvoidtimeRefresh（）{
for（Page2page:
pages）{
page.inc（）;
}
}
//替换算法
publicvoidreplace（intpageId,intcurrentPoint）{
//寻找最长时间不使用的页面,count最大的内存块
intmax=0,perCount,outPageId=-1,cur=0,searchCounter=0;//cur为内存块下标,searchCounter纪录是否内存块搜索完毕
//循环爆出最长为使用的页面
for（inti=currentPoint+1;ifor（Page2page:
pages）{
if（page.getId（）==usePageNumList.get（i））{
searchCounter++;
}
else{
page.inc（）;//未找到则增长值
}
}
if（searchCounter==pages.length）{
break;
}
}
//进行搜索,查找替换目标
for（inti=0;iperCount=pages[i].getCount（）;
if（maxmax=perCount;
cur=i;
outPageId=pages[i].getId（）;
}
//System.out.println（"--------当前-页号count------->"+perCount）;
}
pages[cur].setId（pageId）;
System.out.println（"页号ID:
"+pageId+"正在放入内存,页号ID:
"+outPageId+"被替换出去"）;
reSet（）;
}
//搜索完毕进行重置
publicvoidreSet（）{
for（Page2page:
pages）{
page.setCount（0）;
}
}
//显示当前内存页
publicvoiddisplay（）{
System.out.print（"当前内存保留的页数是:
"）;
for（Page2page:
pages）{
System.out.print（page.getId（）+""）;
}
System.out.println（）;
}
}
/*
*未来最久未使用纪录
*/
classPage2{
privateintid=-1;
privateintcount;
publicintgetId（）{
returnid;
}
publicvoidsetId（intid）{
this.id=id;
}
publicintgetCount（）{
returncount;
}
publicvoidinc（）{
count++;
}
publicvoidsetCount（intcount）{
this.count=count;
}
}
4.importjava.util.ArrayList;
importjava.util.Iterator;
importjava.util.List;
importjava.util.Scanner;
publicclassLRU{
/**
*最近最久未使用算法
*/
privatestaticfinalintPRO_MEMORY=5;//系统分配的内存块数
privatestaticPage[]pages=newPage[PRO_MEMORY];
privatestaticintcount;//纪录当前在使用的总页面数
privatestaticintlackTime;//缺页次数
privateListusePageNumList=newArrayList（）;//页面使用列表
publicstaticvoidmain（String[]args）{
System.out.println（"--------最近最久未使用算法------------"）;
LRUlru=newLRU（）;
lru.init（）;
lru.input（）;
lru.running（）;
}
//初始化
publicvoidinit（）{
for（inti=0;ipages[i]=newPage（）;
}
}
//接收用户输入列表
publicvoidinput（）{
System.out.print（"请输入页面使用列表,以空格分开:
"）;
Scannersc=newScanner（System.in）;
Stringinput=sc.nextLine（）;
String[]inputList=input.split（"\\s"）;
try{
for（Stringin:
inputList）{
usePageNumList.add（Integer.valueOf（in））;
}
}
catch（Exceptione）{
System.out.println（"输入的必须是数字,请重新开始！
！
！
"）;
System.exit（0）;
}
}
//系统运行
publicvoidrunning（）{
Iteratorit=usePageNumList.iterator（）;
//列表置入替换
while（it.hasNext（））{
intinPageId=it.next（）;
//查找内存中是否有该页面
if（search（inPageId））{
System.out.println（"内存中有ID为"+inPageId+"这个页面,不进行替换"）;
}
elseif（countpages[count].setId（（Integer）inPageId）;
System.out.println（"页号ID:
"+pages[count].getId（）+"正在放入内存"）;
reSet（count）;
count++;
timeRefresh（）;
}
else{//替换
replace（inPageId）;
timeRefresh（）;
lackTime++;
}
display（）;
}
System.out.println（"缺页次数为:
"+lackTime+",缺页率是:
"+（float）lackTime/usePageNumList.size（））;
}
//查找内存中是否有该页面
publicbooleansearch（intpageId）{
for（inti=0;iif（pages[i].getId（）==pageId）{
timeRefresh（）;
reSet（i）;
returntrue;
}
}
returnfalse;
}
//访问后置0
publicvoidreSet（intcur）{
pages[cur].setCount（0）;
}
//时间更新
publicvoidtimeRefresh（）{
for（Pagepage:
pages）{
page.inc（）;
}
}
//替换算法
publicvoidreplace（intpageId）{
//寻找时间数最大的页面
intmax=0,perCount,outPageId=-1,cur=0;//cur为下标
for（inti=0;iperCount=pages[i].getCount（）;
if（maxmax=perCount;
outPageId=pages[i].getId（）;//换出去的页号
cur=i;
}
}
reSet（cur）;
升级会员 