操作系统课程设计实验报告.doc

西 安 工 业 大 学

信息与计算科学

10级《操作系统实验》课程设计报告

题 目: 页面置换算法
班 级： 101001
学 号： 101001113
姓 名： 龙 云 祥
时 间： 2013-01-10

一．题目：页面置换算法
二．主要任务：
设计一个虚拟存储区和内存工作区,编程序演示下述算法的具体实现过程,并计算访问命中率。主界面以灵活选择某算法，且以下算法都要实现:
1、先进先出算法（FIFO）
2、最近最久未使用算法（LRU）
3、最佳置换算法（OPT）
三．主要思想：
(1)先进先出算法（FIFO）：最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换予以淘汰，即只需把一个进程已调入内存的页面，按先后顺序连接成一个队列，并设置指针，使它总是指向最老的页面。这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。
（2） 最近最久未使用算法（LRU）：FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：
（1）寄存器。为了记录进程在内存中各项使用情况，在每个内存中的页面配置一个移位寄存器。当进程访问物理块，要将相应的寄存器的位置改成1，此时信号每隔一段时间将寄存器右移一位，那么具有最小数值的寄存器所对应页面，就是最近最久未使用的页面。（2）栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。
因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。
(3) 最优置换算法（OPT）:最优置换是在理论上提出的一种算法。其实质是：当调入新的一页而必须预先置换某个老页时，所选择的老页应是将来不再被使用，或者是在最远的将来才被访问。采用这种页面置换算法，保证有最少的缺页率。但是最优页面置换算法的实现是困难的，因为它需要人们预先就知道一个进程整个运行过程中页面走向的全部情况。不过，这个算法可用来衡量其他算法的优劣。
四. 目的：
通过模拟实现请求页式存储管理的几种基本页面置换法，了解虚拟存储技术。并掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。
五．方案：
按FIFO、LRU、OPT的策略进行页面置换，输出页面置换情况和缺页次数以及缺页率。先进先出算法，每次换出的页面时在页框中停留时间最长的，故缺页次数对页框长度取余的余数便可体现置换页面的页号。最近最久未使用算法，每次置换的都是最近最久没有使用的，故将每次使用的页号的下表记录在数组中，置换数组中最大的页号。最佳置换算法，每次置换的都是即将不会被用到的，如果页框中有多个页号将不会被用到，则根据先进先出置换算法进行换页。
六．框图：
（1）主界面流程图：
开始

输入数字：

Switch：

2：LRU

1：FIFO

3：OPT

退出

（2） FIFO流程图：

开始

For循环

Y

页号是否在页框

N

Count%3

Switch：

1：s[0]
2：s[1]
0：s[2]
退出

(3) LRU流程图:开始

For循环

Y

页号是否在页框

N

退出
置换页面
寻找最近最久未使用的页号

（4） OPT流程图：
开始

For循环

Y

页号是否在页框

N

退出
置换页面
寻找即将不使用的页号

数组找那个最大的页号

七．详细程序：
package com.lyx;
import java.util.Scanner;
public class Test {
void FIFO(int[] p,int[] s,int n){/*先进先出算法*/
int a;
int count=1;
s[0]=p[0];
System.out.println(p[0]);
for(int i=1;i<n;i++){
for(;;){
if(s[0]!=p[i]&&s[1]!=p[i]&&s[2]!=p[i]){
a=++count%3;
switch(a)
{
case 0: s[2]=p[i]; continue;
case 1: s[0]=p[i]; continue;
case 2: s[1]=p[i]; continue;
}
}
else break;
}
for(int j=0;j<3;j++){
if(s[j]==-1){
System.out.print(" ");
}else{
System.out.print(s[j]+" ");
}
}
System.out.println();
}
System.out.println("缺页次数："+count);
System.out.println("缺页率："+count+"/"+n);
}
void LRU(int[] p,int[] s,int n){/*最近最久未使用算法（LRU）*/
int count=1;
s[0]=p[0];
System.out.println(p[0]);
for(int i=1;i<n;i++){
for(int j=0;j<3;j++){
if(s[0]==p[i]){
}
if(s[1]==p[i]){
s[1]=s[0];
s[0]=p[i];
}
if(s[2]==p[i]){
s[2]=s[1];
s[1]=s[0];
s[0]=p[i];
}
if(s[0]!=p[i]&&s[1]!=p[i]&&s[2]!=p[i]){
count++;
s[2]=s[1];
s[1]=s[0];
s[0]=p[i];
}
}
for(int j=0;j<3;j++){
if(s[j]==-1){
System.out.print(" ");
}else{
System.out.print(s[j]+" ");
}
}
System.out.println();
}
System.out.println("缺页次数："+count);
System.out.println("缺页率："+count+"/"+n);
}
void OPT(int[] p,int[] s,int n){/*OPT算法*/
int opt[]=new int[3];
int count= 0;
int k=0;
int i=0;
int j=0;
for (j = 0; j < n; j++){
if(k>=3){
break;
}
boolean flag = false;
for (i = 0; i < 3 ;i++){
if (p[j]==s[i]){
flag = true;
break;
}
}
if (flag==false){
s[k] = p[j];
k++;
count++;
}
for(int r=0;r<3;r++){
if(s[r]==-1){
System.out.print(" ");
}else{
System.out.print(s[r]+" ");
}
}
System.out.println();
} /*前3个数放入*/
for (i=j;i<n;i++){
k=0;
for (j = 0; j < 3 ;j++){
opt[j] = 100;
}
for(j=0;j<3;j++){
if(s[j]!=p[i]){
k++;
}
}/*判断新页面号是否在物理块中*/
if(k==3){ //如果都不在物理块中
boolean flag = false;
for (int t = 0; t < 3; t++){
for (j = i+1; j <n; j++){
if (s[t] == p[j]){
opt[t] = j;
flag=false;
break;
}else{
flag = true;
}
}
if(flag==true){
s[t]=p[i];
count++;
break;
}
}
if(flag==false){
int leap = 0;
for (int t = 0; t < 3; t++){
if (opt[t] > opt[leap]){
leap = t;
}
}
s[leap] = p[i];
count++;
}
}
for(j=0;j<3;j++){
System.out.print(s[j]+" ");
}
System.out.println();
}
System.out.println("缺页次数："+count);
System.out.println("缺页率："+count+"/"+n);

}
public static void main(String[] args) {
Test t=new Test();
int n=0;
Scanner input=new Scanner(System.in);
int M;
System.out.println("输入页面总数:");
int m=input.nextInt();
M=m;
int p[]=new int[M];
System.out.println("输入页面号(非负整数):");
for(int i=0;i<p.length;i++){
p[i]=input.nextInt();
}
do{
int s[]={-1,-1,-1};
System.out.println("-------页面置换算法--------");
System.out.println("1.先进先出算法（FIFO)");
System.out.println("2.最近最久未使用算法（LRU）");
System.out.println("3.最佳置换算法（OPT）");
System.out.println("4.退出");
System.out.println("请选择：");
int a=input.nextInt();
switch(a){
case 1: t.FIFO(p,s,m); break;
case 2: t.LRU(p,s,m); break;
case 3: t.OPT(p,s,m);break;
case 4: break;
}
if(a==4)break;
}while(n!=4);
}
}

八. 程序测试:
测试数据：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
FIFO算法：
7
7
7
2
2
2
4
4
4
0
0
0
7
7
7

0
0
0
3
3
3
2
2
2
1
1
1
0
0

1
1
1
0
0
0
3
3
3
2
2
2
1
测试结果：

LRU算法：
7
7
7
2
2
4
4
4
0
1
1
1

0
0
0
0
0
0
3
3
3
0
0

1
1
3
3
2
2
2
2
2
7
测试结果：

OPT算法：
7
7
7
2
2
2
2
2
7

0
0
0
0
4
0
0
0

1
1
3
3
3
1
1
测试结果：

九．实验总结：
通过本次实验，增强了自己的动手能力和思维能力，在编程序前，首先要掌握算法，通过仔细分析算法的规律，以利于程序的编写，更有利于程序效率的提高，在本次编程时，主要体会如下：
首先应该熟悉算法，有利于编程。在本实验算法中如何有效快速的将页框填满，不同的算法使用不同的方法；引用数组时，指针更加方便准确，但是指针的赋值应注意；运行程序后，测试数据，不能只限与某一组数据，而应多考虑几组特殊的数据，使得程序更具有普遍性，丰富程序的可读性。当然更重要的是遇到问题该如何解决，对以后编程有更大的帮助。