关于LRU页面置换算法

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

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

运行结果如下：