lru.java

页面置换算法 包括fifo 先进现出

package 操作系统.各个置换算法;

import javax.swing.JOptionPane;

public class Lru {// 最近最少使用置换算法（LRU）
	public static final int PROGRAMLEN = 12;
	public static final int PROGRAMNUM = 5;
	public static final int PAGELEN = 3;

	public static void main(String[] args) {

//		int[] program = new int[PROGRAMLEN];
//		for (int i = 0; i < PROGRAMLEN; i++)
//			program[i] = (int) (Math.random() * PROGRAMNUM + 1);
		int[] program = { 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 };// ------7 Lru
		for (int aProgram : program)
			System.out.print(" " + aProgram);

		int[] page = new int[PAGELEN];
		for (int i = 0; i < PAGELEN; i++)
			page[i] = 0;

		int[] index = new int[PAGELEN];// index的下标的page的下标对应，内容是对应最近访问时间
		for (int i = 0; i < PAGELEN; i++)
			index[i] = 0;

		int lostPage = 0;
		for (int i = 0; i < PROGRAMLEN; i++) {
			int j = 0;
			// 在page中已经存在要运行的页
			for (j = 0; j < PAGELEN; j++)
				if (program[i] == page[j]) {
					for (int k = 0; k < PAGELEN; k++)
						if (index[k] != 0)
							index[k]++;
					index[j] = 1;
					break;
				}
			if (j < PAGELEN)
				continue;

			lostPage++;
			// 在page中存在空白页
			for (j = 0; j < PAGELEN; j++)
				if (page[j] == 0) {
					page[j] = program[i];
					while (j >= 0)
						index[j--]++;
					j = -1;// j仅作为标志位，j==-1表明又空白位
					break;
				}
			if (j == -1)
				continue;

			// page没有匹配项和空白项，需要找出最近最长没有使用的页
			int longest = 0;
			for (j = 1; j < PAGELEN; j++)
				if (index[j] > index[longest])
					longest = j;
			page[longest] = program[i];
			index[longest] = 0;
			for (j = 0; j < PAGELEN; j++)
				index[j]++;
		}

		JOptionPane.showMessageDialog(null, "最近最少使用置换算法（LRU）缺页 " + lostPage
				+ " 次");
	}
}