devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

操作系统之存储管理——FIFO算法和LRU算法_银行家算法 页面地址重构 fifo算法

作者：你好赵伟 | 2024-06-07 23:50:57

赞

踩

银行家算法 页面地址重构 fifo算法

操作系统之进程调度——优先权法和轮转法（附上样例讲解）
操作系统之银行家算法—详解流程及案例数据
操作系统之多线程编程—读者优先/写者优先详解
操作系统之存储管理——FIFO算法和LRU算法
操作系统之磁盘调度——SCAN实例讲解

要求

一、实验目的
存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。
二、实验内容
（1）通过计算不同算法的命中率比较算法的优劣。同时也考虑了用户内存容量对命中率的影响。
页面失效次数为每次访问相应指令时，该指令所对应的页不在内存中的次数。
在本实验中，假定页面大小为1k，用户虚存容量为32k，用户内存容量为4页到32页。
（2）produce_addstream通过随机数产生一个指令序列，共320条指令。
A、指令的地址按下述原则生成：
1）50%的指令是顺序执行的
2）25%的指令是均匀分布在前地址部分
3）25%的指令是均匀分布在后地址部分
B、具体的实施方法是：
1）在[0，319]的指令地址之间随机选取一起点m；
2）顺序执行一条指令，即执行地址为m 1的指令；
3）在前地址[0，m 1]中随机选取一条指令并执行，该指令的地址为m’；
4）顺序执行一条指令，地址为m’ 1的指令
5）在后地址[m’ 2，319]中随机选取一条指令并执行；
6）重复上述步骤1）~5），直到执行320次指令
C、将指令序列变换称为页地址流
在用户虚存中，按每k存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条~第9条指令为第0页（对应虚存地址为[0，9]）；
第10条~第19条指令为第1页（对应虚存地址为[10，19]）；
。。。。。。
第310条~第319条指令为第31页（对应虚存地址为[310，319]）；
按以上方式，用户指令可组成32页。
（3）计算并输出下属算法在不同内存容量下的命中率。
1）先进先出的算法（FIFO）；
2）最近最少使用算法（LRU）；
3）最佳淘汰算法（OPT）；
4）最少访问页面算法（LFR）；
其中3）和4）为选择内容
三、系统框图
在这里插入图片描述
一、运行结果
a、运行程序：终端先显示：
Start memory management.
Producing address flow, wait for while, please.
b、地址流、地址页号流生成后，终端显示：
There are algorithms in the program
1、Optimization algorithm
2、Least recently used algorithm
3、First in first out algorithm
4、Least frequently used algorithm
Select an algorithm number, please.
用户输入适当淘汰算法的号码，并按回车，若是第一次选择，输出相应的地址页号流。然后输出该算法分别计算的用户内存从2k ~ 32k时的命中率，若输入的号码不再1~4中，则显示：
there is not the algorithm in the program,并重复b。
c、输出结果后，终端显示 “do you try again with anther algorithm(y/n)”。若键入y则重复b,否则结束。（一般讲四种算法都用过后结束，以便比较）。
二、运行结果讨论
1、比较各种算法的命中率
2、分析当用户内存容量增加是对命中率的影响

分析

上面就是实验要求，因为时间关系，只写了fifo和lru两种，但是这两个会了，剩下的了解算法原理就很容易实现。
对于两种算法的理解和实现为：

先进先出算法算法（Fifo）：

这个算法原理没有算法，就是先进先出。对于这个结构最好采用的就算队列了，对于java而言，我用的是list集合，每次添加数据的时候添加到第0位置，而如果移除的时候移除末尾的页数。在这个过程中，每执行一条指令的时候，如果这个指令对应的地址（指令/10）在list中，那么就命中，否则就是缺页，需要移除尾，在0位置添加元素。

举个例子，页面内存为3，（只能存三页），要执行指令地址页面对应为：4 2 3 4 1 2 1 5 6 3
那么流程顺序为：（4）缺页—>(2,4)缺页—>(3,2,4)缺页—>4命中—>（1,3,2）缺页4被置换—>2命中—>1命中—>（5,1,3）缺页2被替换—>(6,5,1)缺页2被替换—>（3,6,5）缺页1被替换。

最近最少使用算法（LRU）：

这个算法跟fifo其实还是挺像的，但是有一点区别，最近最少使用。也就是说在一个正常序列的时候如果命中的化，就会把这个地址的页号移动到首位（或者链表首位）。而如果缺页的时候，要把这个链表的末尾位置移除，因为末尾的元素是最近用的最少的（很久前才有的）。对于数据结构，我依然选择Arraylist。每次遇到指令地址的时候我只需要特殊判断下就可以了。我只为了实验的目的，没有考虑性能，因为检查是否存在地址的时候我用了list.contains（）方法，这是线性查询复杂度O（n）,如果数据量大可以list map组合使用，将查询降低到O(logn).还可以开一个boolean数组标记让查询复杂度降低到O（1），（但是这样的化增大空间），还好数据量不大，影响不大。

如果页面内存为3，（只能存三页），要执行指令地址页面对应为：4 2 3 4 1 2 1 5 6 3
那么流程顺序为（4)—>(2,4)—>(3,2,4)—>(4,3,2)命中—>(1,4,3)缺页2被替换—>(2,1,4)缺页—>(1,2,4)命中—>(5,1,2)缺页—>(6,5,1)缺页—>(3,6,5)缺页

代码

大致流程就是这样，有一点区别。
下面附上我的ac代码。有的解释会在注释中：

package 实验;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class storemanage {

	static int mingzhong;
	static int lenyeliu=320;
	static int errortime;//失效次数
	static int random[]=new int[330];//随机指令
	static Scanner sc=new  Scanner(System.in);
	static void init()//初始随机数
	{
		int index=0;
		while(index<320)
		{
			int m=(int) (Math.random()*320);
			random[index++]=m;//顺序指令
			int m1=(int) (Math.random()*(m+1));
			if(m1==320) {continue;}//跳出问本次
			random[index++]=m1;//前地址部分 最大317
			if(m1+1==320) {continue;}//跳出问本次
			random[index++]=m1+1;//顺序指令
			int m2=(int) (Math.random()*(319-(m1+2))+m1+2);
			if(m2==320) {continue;}//跳出问本次
			random[index++]=m2;//后地址
			if(index>320)
			{
				break;
			}			
		}
	}
	private static void  lur()
	{
		for(int memory=2;memory<=32;memory++)
		{
			mingzhong=0;errortime=0;
		    Queue<Integer>q1=new ArrayDeque<>();
		    int index=0;
		    while(index<320)
		    {
		    	if(q1.size()<memory)
		    	{
		    	  if(q1.contains(random[index]/10))
		    	  {
		    		 q1.remove(random[index]/10);
		    		 mingzhong++;
		    		 q1.add(random[index]/10);
		    	  }
		    	  else
		    	  {
		    		  q1.add(random[index]/10);
		    		  errortime++;
		    	  }
		    	}
		    	else
		    	{
		    		if(q1.contains(random[index]/10))
			    	  {
			    		 q1.remove(index);
			    		 mingzhong++;
			    	  }
			    	  else
			    	  {
			    		  q1.poll();//抛出
			    		  q1.add(random[index]/10);
			    		  errortime++;
			    	  }
		    	}
		    	index++;
		    }
		    double minz=1-(double)(errortime/(double)(320));//mingzhong/320一样
		    String minzhon=String.format("%.4f", minz);
		    System.out.println("lur :memory:"+memory+" 缺失个数："+errortime+" 命中个数"+mingzhong+"  命中率："+minzhon);
		
		}
		System.out.println("书否继续Y/N");
		String team=sc.next();
		if(team.equals("Y"))
		{
			System.out.println("请输入编号");
			int index=sc.nextInt();
			if(index==1) {fifo();}
			else
			{
				lur();
			}
		}
	}
	private static void fifo() {
		// TODO 自动生成的方法存根
		for(int memory=2;memory<=32;memory++)
		{
			mingzhong=0;errortime=0;
		    List<Integer>list=new ArrayList<>();
		    int index=0;
		    while(index<320)
	 	    {
			    if(list.size()<memory)//小于内存
			    {
				   if(list.contains(random[index]/10)) {mingzhong++;}
				   else
				   {
					   list.add(random[index]/10);
					   errortime++;
				   }				   
			    }
			    else//内存慢了
			    {
			    	   if(list.contains(random[index]/10)) {mingzhong++;}
					   else
					   {
						   list.remove(0);//移除第一个
						   list.add(random[index]/10);
						   errortime++;
					   }
			    }
			    index++;
			   // System.out.println(index);
		     }
		    double minz=1-(double)(errortime/(double)(320));//mingzhong/320一样
		    String minzhon=String.format("%.4f", minz);
		    System.out.println("fifo :memory:"+memory+" 缺失个数："+errortime+" 命中个数"+mingzhong+"  命中率："+minzhon);
		}
		System.out.println("书否继续Y/N");
		String team=sc.next();
		if(team.equals("Y"))
		{
			System.out.println("请输入编号");
			int index=sc.nextInt();
			if(index==1) {fifo();}
			else
			{
				lur();
			}
		}
	}
	public static void main(String[] args) {
	 
	  init();
	  System.out.println("随机数为");
	  for(int i=0;i<320;i++)
	  {
		  System.out.print(String.format("%5d", random[i]));
		  if((i+1)%20==0)System.out.println();
	  }
	  System.out.println("输入选择算法的计算方式序号\n1:先进先出的算法（FIFO）；\n" + 
	  		"2:最近最少使用算法（LRU）；\n" + 
	  		"3:最佳淘汰算法（OPT）；\n" + 
	  		"4:最少访问页面算法（LFR）；");
	  int index=sc.nextInt();
	  if(index==1) {
		  fifo();
	  }
	  else if(index==2)
	  {
		  lur();
	  }		
	}
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165

执行结果

在这里插入图片描述

fifo

在这里插入图片描述

lur

在这里插入图片描述
可以看得出成功了。并且最后都是0.9因为固定缺页数(首次命中)达到0.1.
如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/687546
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号