关于LRU页面置换算法_JAVA_编程开发_程序员俱乐部

在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

页面置换算法有很多种，比如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;
??}
?}
}

运行结果如下：