软 件 学 院
上 机 实 验 报 告
课程名称： 操作系统原理
实验项目： 虚拟内存页面置换算法
实 验 室： 地狱018
姓 名： 死神 学 号：
专业班级： 实验时间： 2015/12/13
第二篇：虚拟内存页面置换算法
《操作系统》实验四
【实验题目】：虚拟内存页面置换算法
【实验目的】
通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。
【实验内容】
问题描述：
设计程序模拟先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。
程序要求如下：
1）利用先进先出FIFO，最佳置换OPI和最近最久未使用LRU三种页面置换算法模拟页面访问过程。
2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。
3）输入：最小物理块数m，页面个数n，页面访问序列P1, … ,Pn，算法选择1-FIFO，2-OPI，3-LRU。
4）输出：每种算法的缺页次数和缺页率。
实验要求：
1) 上机前认真复习页面置换算法，熟悉FIFO，OPI，LRU三种页面分配和置换算法的过程；
2) 上机时独立编程、调试程序；
3) 根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源程序、实例运行结果截图）。
源程序如下：（不包含界面部分的代码）
package yemzh;
publicclass Opall {
/*
* apple theapplethetree 为前台传递的数据。也可以直传apple thetree,theapple=apple.length;
*/
privateint theapple;//苹果数---也就是页面个数
privateint thetree;//苹果树---物理块数。
privateint[] lemon;//放物理块的数组。
privateint[] apple;//放苹果的数组。
private String[][] grapes;//用于返回的结果数组。
privateint[] lemoncy;//放物理块的数组的拷贝。用于lru算法。
publicint theall;//为命中的页面数。返回到前台去。
public Opall(int thetreec,int[] applec){
thetree=thetreec;
theapple=applec.length;
apple=applec;
lemon=newint[thetreec];
}
public String[][] getFifo(){
grapes=new String[thetree][theapple];
initlemon(lemon);
fifo();
return grapes;
}
public String[][] getOptimal(){
grapes=new String[thetree][theapple];
initlemon(lemon);
optimal();
return grapes;
}
public String[][] getLru(){
grapes=new String[thetree][theapple];
initlemon(lemon);
lRu();
return grapes;
}
privatevoid initlemon(int[] len){
int thelength=len.length;
for(int i=0;i<thelength;i++){
len[i]=-1;
}
}
/*
* fifo
*/
privatevoid fifo(){
int fire=0;
theall=0;
for(int i=0;i<theapple;i++){
if(fire==thetree){
fire=0;
}
if(noFind(i)){
lemon[fire]=apple[i];
fire++;
theall++;
initGrapes(i,theall);
}
else{
blank(i);
}
}
}
/*
* optimal():
*/
privatevoid optimal(){
int fly;
theall=0;
for(int i=0;i<theapple;i++){
if(noFind(i)){
if(theall<thetree){
fly=theall;
}
else{
fly=findIndex(i);
}
lemon[fly]=apple[i];
theall++;
initGrapes(i,theall);
}
else{
blank(i);
}
}
}
privatevoid lRu(){
int butter;
int butterfly;
theall=0;
for(int i=0;i<theapple;i++){
if(noFind(i)){
theall++;
if(theall<=thetree){
butterfly=theall-1;
}
else{
butter=findnumb(i);
butterfly=findtheno(butter);
}
lemon[butterfly]=apple[i];
initGrapes(i,theall);
}
else{
blank(i);
}
}
}
/*
* findtheno(butter)功能是：根据lru算法，找到页面号butter所在的物理块下标。
*/
privateint findtheno(int butter) {
// TODO Auto-generated method stub
for(int i=0;i<thetree;i++){
if(butter==lemon[i]){
return i;
}
}
return -1;
}
/*
* findnumb(fb)的功能：根据lru算法，找到该被替换的页面号。
*/
privateint findnumb(int fb) {
// TODO Auto-generated method stub
lemoncy=newint[thetree];//lemoncy为lemon的copy。
initlemon(lemoncy);
int yy=0;
for(int i=fb-1;i>=0;i--){
if(noFindcy(i)){
lemoncy[yy]=apple[i];
yy++;
}
if(yy==thetree){
return apple[i];
}
}
return -1;
}
privateboolean noFindcy(int ncy) {
// TODO Auto-generated method stub
int oneapple=apple[ncy];
for(int j=0;j<thetree;j++){
if(lemoncy[j]==oneapple){
returnfalse;
}
}
returntrue;
}
/*
* findIndex(intfi)的功能:查找到该被替换的物理块的下标。
*/
privateint findIndex(int fi) {
// TODO Auto-generated method stub
int themax=-1;
int theindex=-1;
for(int i=0;i<thetree;i++){
int yy=findNo(i,fi+1);//当前这个页面肯定不在里面，所以从下一个页面开始找。
if(yy<0){
return i;
}
if(yy>themax){
themax=yy;
theindex=i;
}
}
return theindex;
}
/*
* findNo(fn,fi)的功能是： 为了找到从fi开始，最先出现lemno[fn]的下标。如果没找到则返回-1。
*/
privateint findNo(int fn, int fi) {
// TODO Auto-generated method stub
int onelemon=lemon[fn];
for(int i=fi;i<theapple;i++){
if(onelemon==apple[i]){
return i;
}
}
return -1;
}
/*
* initGrapes 初始化grapes数组，用于显示。
*/
privatevoid initGrapes(int ia, int thell) {
// TODO Auto-generated method stub
if(thell<thetree){
int i;
for(i=0;i<thell;i++){
grapes[i][ia]=Integer.toString(lemon[i]);
}
for(; i<thetree;i++){
grapes[i][ia]="";
}
}
else{
for(int j=0;j<thetree;j++){
grapes[j][ia]=Integer.toString(lemon[j]);
}
}
}
/*
* blank()方法的功能： 填充空白字符串“”。
*
*/
privatevoid blank(int bk) {
// TODO Auto-generated method stub
for(int j=0;j<thetree;j++){
grapes[j][bk]="";
}
}
/*
* noFind（int i）方法功能： 当前的页面号在物理块中是否找到，没找到返回true，反之返回false。
*/
privateboolean noFind(int nf) {
// TODO Auto-generated method stub
int oneapple=apple[nf];
for(int j=0;j<thetree;j++){
if(lemon[j]==oneapple){
returnfalse;
}
}
returntrue;
}
}
运行结果如下：
初始界面如下：
输入数据：
确定输入以后：
按照提示初始化页面系列号：
输入符合要求的数据后，点击计算，结果如下：
点击“关闭”按钮，结束程序；点击“重新”按钮，则重新开始，如下：
输入错误提示如下：
第一个：
物理块个数为0，或不是正整数就会得到以上的提示。页面个数也一样。
第二个：
输入的数不是自然数得到的提示。