实现请求分页系统中页面置换算法（FIFO和LRU置换算法）——操作系统实验
由于本人java学艺不精，这两种算法均采用最基础的for循环来实现。等本小媛再修炼修炼，会对此代码进行优化，大家敬请期待。FIFO先进先出算法算法原理：要淘汰内存某页时,选择 最先进入内存的页 淘汰。例:已知 进程页面走向如下:7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1供该进程使用的内存块数为3, 采用 请求 调页策略。(1
·
由于本人java学艺不精，这两种算法均采用最基础的for循环来实现。等本小媛再修炼修炼，会对此代码进行优化，大家敬请期待。
FIFO先进先出算法
算法原理：
- 要淘汰内存某页时,选择 最先进入内存的页 淘汰。
- 例:已知 进程页面走向如下: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 供该进程使用的内存块数为3, 采用 请求 调页 策略。
- (1) 画出访问各页时内存块中页号情况 (2) 求缺页率
- 缺页率的计算：当CPU进入内存找某页时发现没有，需要重新调入，属于一次缺页。
代码实现：
代码实现分为两部分：part1：先从外部调入进程页直到内存块满;part2:当内存块满了之后，若要调入新的进程页号，则需根据先进先出原则淘汰内存块中的页号。
part1:当第一个页号调入内存时，由于内存块内为空，可直接调入。从第二个页号调入时，就要与之前已经调入内存块的页号进行对比。如果某页之前已被调入进内存块，则不需要再调入。非缺页记录变量加一；如果某页之前未被调用过，则此时被调入进内存块。
part2：当内存块被填满之后，在调用下一个进程页时，与内存块中已有的页号进行对比，如果之前已被调入，则不需要被再次调入。非缺页变量加一；如果之前未被调用，则需淘汰内存块中现有的页号，根据先进先出原则，在数组中i值最小的，是最早进入内存块的，i值大的是最晚进入内存块的。所以在淘汰进程页时，可以从i=0；开始淘汰，直到淘汰到i=number；
int yes=0;
int [] block=new int [number];//blcok数组是用来存放内存块内数据的，在这里先往内存块内存放数据，将内存块填满
block[0]=page[0];//最开始的时候，block里面是空的，所以可以直接进程页号可直接调入内存块中
for(int i=1;i<number;i++){//for循环将进程页号调入数组
boolean o=false;
for(int m=0;m<i;m++){//本层循环来判断内存中是否已经存在要使用的进程的页号
if (block[m]==page[i]){
yes++;//如果内存块中存在要调用的页号，则非缺页次数加一
o=true;}
}
while(o){
for(int j=0;j<i-1;j++){//输出此时内存块中的页号情况，由于此时内存块中并未赋新值，所以内存块中的情况依旧是上一轮循环后的结果。
System.out.print(block[j]+" ");
}
break;
}
while(!o){
block[i]=page[i];//如果内存中不存在要调用的页号，则将新页号调入内存块
for(int j=0;j<i;j++){
System.out.print(block[j]+" ");
}
break;
}
System.out.println();
}
int s=0;
int n=0;
for(int i=number;i<p;i++){//内存块被装满后
boolean e=false;
for(int j=0;j<number;j++){
if (page[i]==block[j]){
e=true;
n++;}//非缺页变量
}
if(e){
for(int m=0;m<number;m++){//输出此时内存块中的已有页号
System.out.print(block[m]+" ");
}
}
else{
block[s]=page[i];//数组中的页号从block[0]到block[number]
s++;
if(s==number){
s=0;//当到达数组最大值后，s再变为0，新的一轮淘汰开始
}
for(int m=0;m<number;m++){
System.out.print(block[m]+" ");
}
}
System.out.println();
}
System.out.println("缺页次数："+(p-n-yes)+"次");//非缺页次数由n和yes两部分组成
double g=(p-n-yes)/(double)p;
System.out.print("缺页率：");
System.out.println(String.format("%.2f",g));LRU算法 最近最久未使用置换法 ( LRU= Least Recently Used )
算法思想：
需要淘汰页面时,选择内存中最近一段时间里最久没有使用过 页面淘汰。
通常会使用一个 栈 来保存在内存中的页面的页号。当一个页面被访问时,其对应的页号要放在栈顶，当要淘汰页面时,栈底页号对应的页面即为要淘汰的页面(即最近最久未被访问的页面)。
由于我不会用代码表示栈，所以我还是用了数组。用i=0；表示栈底。i=number；表示栈顶。嘻嘻嘻
代码实现：依旧是分成两个部分；part1：先填满内存块；part2：对内存块内的页号进行淘汰。
此算法难点是，当要调入的页号已经在内存块内时，需要将此页号的位置放到栈顶，也就是数组=number的位置，并将数组内的其他页号向栈底推，也就是向i=0；的方向推。
int yes2=0;
int y=0;
int [] block2=new int [number];//block2数组来存放内存块内的页号。方法与FIFO相同
block2[0]=page[0];
for(int i=1;i<number;i++){
boolean o=false;
for(int m=0;m<i;m++){
if (block2[m]==page[i]){//如果页号已经在内存块内
yes2++;//非缺页变量加一
o=true;
y=m;
int z=block2[y];//当页号已在内存块中时，将此页号提到栈顶，其余页号往栈底推
for(int f=y+1;f<i;f++){
block2[f-1]=block2[f];
}
block2[i-1]=z;
break;
}
}
while(o){
for(int j=0;j<i-1;j++){
System.out.print(block2[j]+" ");
}
break;
}
while(!o){
block2[i]=page[i];
for(int j=0;j<i;j++){
System.out.print(block2[j]+" ");
}
break;
}
System.out.println();
}
int n2=0;
int b;
for(int i=number;i<p;i++){//内存块已满，淘汰页号算法
boolean e2=false;
for(int j=0;j<number;j++){
if (page[i]==block2[j]){
e2=true;
n2++;
b=j;
int z=block2[b];
for(int f=b+1;f<number;f++){
block2[f-1]=block2[f];
}
block2[number-1]=z;
break;
}
}
if(e2){
for(int m=0;m<number;m++){
System.out.print(block2[m]+" ");
}
}
else{
for(int h=1;h<number;h++){
block2[h-1]=block2[h];
}
block2[number-1]=page[i];
for(int m=0;m<number;m++){
System.out.print(block2[m]+" ");
}
}
System.out.println();
}
System.out.println("缺页次数："+(p-n2-yes2)+"次");
double g2=(p-n2-yes2)/(double)p;
System.out.print("缺页率：");
System.out.println(String.format("%.2f",g2));最后整体代码我也放到这里啦 （此代码只适合进程页号不小于内存块的情况，本人觉得如果进程页号小于内存块也就没有太大的必要性去研究了）
import java.util.Scanner;
public class Fal {
public static void main(String[] args) {
Scanner in=new Scanner (System.in);
System.out.print("请输入内存块数：");
int number=in.nextInt();
System.out.print("请输入进程页数：");
int p=in.nextInt();
System.out.print("请输入页面走向：");
int [] page=new int [p];//用page数组存储页面走向
for(int i=0;i<p;i++){
page[i]=in.nextInt();
}
System.out.print("页面走向为：");
for(int i=0;i<p;i++){
System.out.print(page[i]+" ");
}
System.out.println();
System.out.println(" FIFO页面置换算法"); //从这儿开始是FIFO算法
System.out.println("各物理块中的页号情况");
int yes=0;
int [] block=new int [number];//blcok数组是用来存放内存块内数据的，在这里先往内存块内存放数据，将内存块填满
block[0]=page[0];//最开始的时候，block里面是空的，所以可以直接进程页号可直接调入内存块中
System.out.println(block[0]);
int x=1;
for(int i=1;i<number;i++){//for循环将进程页号调入数组
boolean o=false;
for(int m=0;m<i;m++){//本层循环来判断内存中是否已经存在要使用的进程的页号
if (block[m]==page[i]){
yes++;//如果内存块中存在要调用的页号，则非缺页次数加一
o=true;}
}
while(o){
for(int j=0;j<x;j++){//输出此时内存块中的页号情况，由于此时内存块中并未赋新值，所以内存块中的情况依旧是上一轮循环后的结果。
System.out.print(block[j]+" ");
}
break;
}
while(!o){
block[i]=page[i];//如果内存中不存在要调用的页号，则将新页号调入内存块
x++;//x用来统计已调入的页号个数，如果调入了新的页号，则x++；方便输出。
for(int j=0;j<x;j++){
System.out.print(block[j]+" ");
}
break;
}
System.out.println();
}
int s=0;
int n=0;
for(int i=number;i<p;i++){//内存块被装满后
boolean e=false;
for(int j=0;j<number;j++){
if (page[i]==block[j]){
e=true;
n++;}//非缺页变量
}
if(e){
for(int m=0;m<number;m++){//输出此时内存块中的已有页号
System.out.print(block[m]+" ");
}
}
else{
block[s]=page[i];//数组中的页号从block[0]到block[number]
s++;
if(s==number){
s=0;//当到达数组最大值后，s再变为0，新的一轮淘汰开始
}
for(int m=0;m<number;m++){
System.out.print(block[m]+" ");
}
}
System.out.println();
}
System.out.println("缺页次数："+(p-n-yes)+"次");//非缺页次数由n和yes两部分组成
double g=(p-n-yes)/(double)p;
System.out.print("缺页率：");
System.out.println(String.format("%.2f",g));
System.out.println("_________________________________");
System.out.println(" LRU 页面置换算法");
System.out.println("采用栈保存的方法");
int yes2=0;
int y=0;
int [] block2=new int [number];//block2数组来存放内存块内的页号。方法与FIFO相同
block2[0]=page[0];
System.out.println(block[0]);
x=1;
for(int i=1;i<number;i++){
boolean o=false;
for(int m=0;m<i;m++){
if (block2[m]==page[i]){//如果页号已经在内存块内
yes2++;//非缺页变量加一
o=true;
y=m;
int z=block2[y];//当页号已在内存块中时，将此页号提到栈顶，其余页号往栈底推
for(int f=y+1;f<x;f++){
block2[f-1]=block2[f];
}
block2[x-1]=z;
break;
}
}
while(o){
for(int j=0;j<x;j++){
System.out.print(block2[j]+" ");
}
break;
}
while(!o){
block2[i]=page[i];
x++;
for(int j=0;j<x;j++){
System.out.print(block2[j]+" ");
}
break;
}
System.out.println();
}
int n2=0;
int b;
for(int i=number;i<p;i++){//内存块已满，淘汰页号算法
boolean e2=false;
for(int j=0;j<number;j++){
if (page[i]==block2[j]){
e2=true;
n2++;
b=j;
int z=block2[b];
for(int f=b+1;f<number;f++){
block2[f-1]=block2[f];
}
block2[number-1]=z;
break;
}
}
if(e2){
for(int m=0;m<number;m++){
System.out.print(block2[m]+" ");
}
}
else{
for(int h=1;h<number;h++){
block2[h-1]=block2[h];
}
block2[number-1]=page[i];
for(int m=0;m<number;m++){
System.out.print(block2[m]+" ");
}
}
System.out.println();
}
System.out.println("缺页次数："+(p-n2-yes2)+"次");
double g2=(p-n2-yes2)/(double)p;
System.out.print("缺页率：");
System.out.println(String.format("%.2f",g2));
}
}
本代码重复性高，且十分繁琐。但是由于本小媛技术不精，现在的能力也只能写成这样了，此后，等本小媛修炼一番，会对次代码进行优化。欢迎路过的各位大佬们，批评指点。
鸿蒙生态一站式服务平台。
更多推荐
20
0- 0
已为社区贡献1条内容
所有评论(0)