操作系统之存储管理——FIFO算法和LRU算法
操作系统之进程调度——优先权法和轮转法(附上样例讲解)
操作系统之银行家算法—详解流程及案例数据
操作系统之多线程编程—读者优先/写者优先详解
操作系统之存储管理——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
文章来源: bigsai.blog.csdn.net,作者:Big sai,版权归原作者所有,如需转载,请联系作者。
原文链接:bigsai.blog.csdn.net/article/details/84790849
- 点赞
- 收藏
- 关注作者
评论(0)