09年9月28日,参加东软高端就业笔试,专业笔试关于缓存调度算法,由于事先没有准备,仓惶作答,漏洞百出,今作以总结,以备后用。
FIFO
package Fifo;
//FIFO(Firt in First out)算法
class Page {
private int num;
public Page(int num) {
this.num = num;
}
public int getNum() {
return num;
}
}
class LinkNode {
Page page;
LinkNode next;
}
public class MyFiFo {
LinkNode first;
LinkNode last;
int maxSize = 10; // 缓存的尺寸
int currentSize = 0;
public MyFiFo(int maxSize) {
this.maxSize = maxSize;
}
public void changePage(Page p) {// FIFO 算法,每次读取新页都重新调整缓存结构
LinkNode newItem = new LinkNode();
newItem.page = p;
newItem.next = null;
if (first == null) {
first = newItem;
last = first;
currentSize++;
} else {
LinkNode current = first;
boolean isIn = false;
for (int i = 0; i < currentSize; i++) {// 查看所请求的页面是否在缓存中
if (current.page.getNum() == p.getNum()) {
isIn = true;
break;
}
current = current.next;
}
if (!isIn) { // 如果所请求页面不在缓存中,向缓存中添加数据
// 从数据库里读出数据放到newItem上
if (currentSize < maxSize) { // 缓存未满时,添加页面
last.next = newItem;
last = newItem;
currentSize++;
}else { // 缓存已满,先删除头部,再向尾部添加
first = first.next;
last.next = newItem;
last = newItem;
}
}
}
print();
}
public void print() {
LinkNode current = first;
System.out.println();
while (current != null) {
System.out.print(current.page.getNum() + ",");
current = current.next;
}
}
public static void main(String[] args) {
MyFiFo fifo = new MyFiFo(10);
int arr[] = { 2,2, 5,5, 3, 7, 2, 5, 4, 7, 4, 6, 9, 10, 3, 53, 45, 56,56, 5,67,
89, 23 };
for (int i = 0; i < arr.length; i++) {
fifo.changePage(new Page(arr[i]));
}
}
}
图解:
图片来源:
LRU
package Fifo;
//LRU最久未使用淘汰算法
public class MyLRU {
LinkNode first;
LinkNode last;
int maxSize = 10; // 缓存的尺寸
int currentSize = 0;
public MyLRU(int maxSize) {
this.maxSize = maxSize;
}
public void changePage(Page p) {// LRU 算法,每次读取新页都重新调整缓存结构
LinkNode newItem = new LinkNode();
newItem.page = p;
newItem.next = null;
if (first == null) {
first = newItem;
last = first;
currentSize++;
} else {
LinkNode current = first;
LinkNode trailCurrent = first;
for (int i = 0; i < currentSize; i++) {// 先判断缓存中有没有该页,有则删除
if (current.page.getNum() == p.getNum()) {
if (current == first) { //有该页且在队头
first = first.next;
if (first == null) //删除后,如果缓存为空,重设last
last = first;
} else {
trailCurrent.next = current.next;
if (current == last) { //如果删除的是最后一个,重设last指针
last = trailCurrent;
}
}
currentSize--;
break;
}
trailCurrent = current;
current = current.next;
}
//删除完后,在队尾添加
if (currentSize < maxSize) {//缓存未满时的插入
if (first == null) { //如果缓存为空,添加并重设first、last指针
first = newItem;
last = first;
} else { //如果缓存不为空添加到尾部
last.next = newItem;
last = newItem;
}
currentSize++;
} else { //缓存已满时,先删除队头,再向队尾插入
first = first.next;
currentSize--;
last.next = newItem;
last = newItem;
currentSize++;
}
}
print();
}
public void print() {
LinkNode current = first;
System.out.println();
while (current != null) {
System.out.print(current.page.getNum() + ",");
current = current.next;
}
}
public static void main(String[] args) {
MyLRU fifo = new MyLRU(10);
int arr[] = { 2, 2, 5, 3, 3, 7, 2, 5, 4, 7, 7, 4, 6, 9, 10, 3, 53, 45,
56, 67, 89, 23, 53 };
for (int i = 0; i < arr.length; i++) {
fifo.changePage(new Page(arr[i]));
}
}
}
图解:
图片来源:
- 大小: 13.1 KB
- 大小: 14.7 KB
分享到:
相关推荐
实验6虚拟内存置换算法——最佳置换算法(OPI)、先进先出(FIFO)、最近最久未使用算法(LRU), 调试可运行,,含实验报告,含具体流程图 ,有注释和变量解释 含本人实验报告,有具体流程图,实验课上写的,有更好的想法...
通过利用VC++建立MFC中控件形式模拟建立页面淘汰算法演示,中间环节除了要写出三种重要算法的具体代码之外,还要继续利用之前学过的C++控件知识,很多控件的使用需要借助于网上的实例代码,然后自己慢慢摸索,并结合...
基于C语言的FIFO和LRU算法的实现。
本代码通过了老师的检查,测试平台是:vc++6.0,并提交了实验报告,如果您有什么建议,请告诉我,一起进步。
对比FIFO/LRU两种算法的命中率。有源程序,有结果,有对比说明,有测试用例。
该工程具体是在codeblock上面实现了操作系统课程上讲解的页面置换算法,包括先进先出(FIFO)、最佳置换算法(OPT)、最久最近未使用算法(LRU)。 具体实现功能有: 1、建立相应的数据结构 2、在屏幕上显示页面...
LRU算法和FIFO算法合体
操作系统课程设计用Java的可视化功能把操作系统基本算法可视化,在Windows窗体可视化界面里面,使用基本图形要素模拟算法基本要素,把算法运行过程通过要素变化过程可视化。本软件可自行输入物理块数、页面长度和...
模拟先进先出FIFO,最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程 报告册和源程序
使用MFC制作的有界面的算法模拟,较为简洁
1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6 当内存块数量为3时,试问LRU,FIFO,OPT三种置换算法的缺页次数各是多少? (注意:所有内存块最初都是空的,凡第1次用到的页面都产生一次缺页)
2 最近最久未使用算法(LRU算法)基本思想 2 二 程序设计 2 1 数据结构设计 2 2 函数设计 3 3 流程图 5 1 FIFO算法设计流程图 5 2 LRU 算法设计流程图: 6 三 代码 8 四 结果分析 12 五 实验总结及心得体会 13">...
这是一个自己完成软件工程的操作系统课程课程设计题目:此程序用于模拟虚拟磁盘页面置换算法,实现了FIFO页面置换算法和LRU页面置换算法,获得课程设计优秀的好成绩
随机给出一个页面执行序列,如:1,5,3,4,2,1,3,4,5,7,9,……。要求计算以下几种置换算法的缺页数、缺页率和命中率。 最佳置换算法OPT(Optimal) ...最近最少使用算法LRU(Least Recently Used)
目的:(1)通过编写程序实现请求分页存储管理页面Optimal、FIFO、LRU调度算法,使学生掌握虚拟存储管理中有关缺页处理方法等内容,巩固有关虚拟存储管理的教学内容。 (2)了解Windows2000/XP中内存管理机制,掌握...
自己写的 希望有错提出来 期中那个OPT写的不是很好,希望可以多多指教
该工程具体是在codeblock上面实现了操作系统课程上讲解的页面置换算法,包括先进先出(FIFO)、最佳置换算法(OPT)、最久最近未使用算法(LRU)。 具体实现功能有: 1、建立相应的数据结构 2、在屏幕上显示页面的...
页面置换算法(FIFO算法,LRU算法)
FIFO、OPT、LRU页面置换算法实验代码和截图
3、利用OPT,FIFO,LRU页面置换算法模拟页面置换过程并计算其缺页率。 4、每访问一个页面均需给出内存中的内容(内存中的页面号),若有淘汰还需给出淘汰的页面号。 5、通过给出特殊的页面访问顺序,分配不同的物理块...