在地址映射过程中,若在页面中发现所要访问的页面不再内存中,则产生缺页中断。当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
页面置换算法有很多种,比如Optimal(最佳置换)算法,FIFO(先进先出)算法,LRU(最近最久未使用)算法等等,最佳置换算法是不实际的,它只是一种构想,因为我们并不能预测哪个页面在将来再也不会被使用。那么对于FIFO算法和LRU算法那个更好呢?这就涉及到一个概念---“缺页率”。在进程的运行过程中,若其所要访问的页面不在内存中则缺页。我们不能让缺页率太高,所以必须选择一种使得缺页率较小的置换算法。
FIFO算法实现简单,但是性能较差,因为它依据的条件是各个页面调入内存的时间,而页面调入的先后并不能反映页面的使用情况,LRU算法,是根据页面调入内存后的使用情况进行决策的,由于我们是无法预知页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似,所以LRU算法选择了内存中最久没有被使用到的页面进行淘汰。
该算法赋予每一个页面一个访问字段,用来记录一个页面自上次被访问所经历的时间t。当产生缺页的时候,选择现有页面中t值最大的,即最近最久未使用的页面进行淘汰。
有如下例子
为了实现此算法,我们用java里面的ArrayList来模拟操作系统中的页面缓冲区,将页面放在里面,输入一个页面访问序列,在缓冲区中进行页面的置换。
1、首先我们定义页面属性,有页面编号和页面的时间t
package LRU;
public class Page {
char num;//页面编号
int time;//页面没有被访问到的时长
}
2、然后进行页面置换算法:
package LRU;
import java.util.ArrayList;
import java.util.Scanner;
public class LRU {
static ArrayList<Page> pages = new ArrayList<Page>();//模拟缓冲区的队列
int size = 4;//设置缓冲区大小为4个页面
public static void main(String[] args) {
LRU lru = new LRU();
lru.initList();
System.out.println("当前缓冲区大小"+lru.size+"\n缓冲区状态为:");
lru.printList();
lru.getPages();
}
/**
* 得到要置换的所有页面序列
*/
private void getPages() {
String str = null;
System.out.println("请输入页面序列");
Scanner sca = new Scanner(System.in);
str = sca.next();
toChars(str);
}
/**
* 将序列序号存入char型数组
*
* @param str
*/
private void toChars(String str) {
char[] ch = new char[str.length() + 1];
for (int i = 0; i < str.length(); i++) {
ch[i] = str.charAt(i);
}
ch[str.length()] = '#';
exchange(ch);
}
/**
* 初始化缓冲区(cache)
*/
private void initList() {
for (int i = 0; i < size; i++) {
Page page = new Page();
page.num = '#';
page.time = 0;
pages.add(page);
}
}
private void exchange(char[] ch) {
char temp;
int time = 0;
int i = 0;
printList();
while (ch[i] != '#') {
if(i<9){
System.out.print("\n"+"第"+0+(i+1)+"次置换----");
}
else{System.out.print("\n"+"第"+(i+1)+"次置换----");}
if (isIn(ch[i]) != -1) {
System.out.print("当前页面存在缓冲区:");
int position = isIn(ch[i]);
pages.get(position).time = 0;
timeAdd(position);
printList();
i++;
continue;
}
if (space(ch[i]) != -1) {
System.out.print("缓冲区内有空余页面:");
int position = space(ch[i]);
pages.get(position).num = ch[i];
pages.get(position).time = 0;
timeAdd(position);
printList();
i++;
continue;
}
if (isIn(ch[i]) == -1) {
System.out.print("当前页面不在缓冲区:");
int max = 0;
int position = 0;
for (int j = 0; j < size; j++) {
if (pages.get(j).time > max) {
max = pages.get(j).time;
position = j;
}
}
pages.get(position).num = ch[i];
pages.get(position).time = 0;
timeAdd(position);
printList();
i++;
continue;
}
}
}
/**
* 判断缓冲区是否有空位
* @param ch
* @return
*/
private int space(char ch) {
int flag = -1;
for (int i = 0; i < size; i++) {
if (pages.get(i).num != '#') {
continue;
}
flag = i;
break;
}
return flag;
}
/**
* 判断当前页面有没有在缓冲区内,返回位置
* @param ch
* @return
*/
private int isIn(char ch) {
int flag = -1;
for (int i = 0; i < size; i++) {
if (ch != pages.get(i).num) {
continue;
}
flag = i;
break;
}
return flag;
}
/**
* 打印缓冲区页面
*/
private void printList() {
for (int i = 0; i < size; i++) {
System.out.print(pages.get(i).num + "\t");
}
}
/**
* 增加页面时间属性
* @param position
*/
private void timeAdd(int position) {
for (int i = 0; i < size; i++) {
if (i == position || pages.get(i).num == '#') {
continue;
}
pages.get(i).time += 1;
}
}
}
运行结果如下:
相关推荐
使用LRU算法实现页面置换算法。LRU算法基于一种假设,长期不使用的数据,在未来的使用性也不大。因此,当数据占用内存达到一定的阙值时,我们要移除最近最少使用的数据。LRU算法中,使用了一种有趣的数据结构,叫做...
C语言实现的对操作系统中LRU页面置换算法的模拟,有dos输出界面,简单明了
操作系统LRU页面置换算法
3、利用OPT,FIFO,LRU页面置换算法模拟页面置换过程并计算其缺页率。 4、每访问一个页面均需给出内存中的内容(内存中的页面号),若有淘汰还需给出淘汰的页面号。 5、通过给出特殊的页面访问顺序,分配不同的物理块...
这是一个自己完成软件工程的操作系统课程课程设计题目:此程序用于模拟虚拟磁盘页面置换算法,实现了FIFO页面置换算法和LRU页面置换算法,获得课程设计优秀的好成绩
FIFO、OPT、LRU页面置换算法实验代码和截图
lru页面置换算法模拟最近最久未使用置换算法课程设计 (2).pdflru页面置换算法模拟最近最久未使用置换算法课程设计 (2).pdflru页面置换算法模拟最近最久未使用置换算法课程设计 (2).pdflru页面置换算法模拟最近最久未...
LRU页面置换算法,使用Java语言编写,使用策略模式,可以方便的换成其他页面置换算法!相当好!
基于linux C模拟FIFI和LRU页面置换算法
主要实现主存空间的分配和回收、存储保护。主要是对用户区的管理。存储管理采用请求分页式存储管理方式。该系统的页面置换算法必须包括先进先出页面置换算法、最近最少使用LRU页面置换算法、最佳置换算法。
LRU页面置换算法模拟(最近最久未使用置换算法).doc
模拟先进先出FIFO,最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程 报告册和源程序
操作系统LRU页面置换算法 C语言程序 数组实现 简单,清晰且实用,
LRU页面置换算法的源代码,以及可执行程序
lru置换算法是操作系统很经典的页面置换算法,此算法必能掉是通过。
按照程序提示输入任意长度的页面访问序列,页面号之间用回车键区分,最终输出四个物理块中装入的页面情况,缺页数目和缺页率
该工程具体是在codeblock上面实现了操作系统课程上讲解的页面置换算法,包括先进先出(FIFO)、最佳置换算法(OPT)、最久最近未使用算法(LRU)。 具体实现功能有: 1、建立相应的数据结构 2、在屏幕上显示页面...
根据设计要求实现对页面置换算法的模拟以及 进程状态转换的模拟。 1.根据自己输入 物理块数量,访问页面总数,要访问的页面号, 2.然后选择所需的置换算法 OPT,LRU 二选一. 计算过程,并得出 缺页次数,缺页率,...