page.java

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

package 操作系统;

import javax.swing.JOptionPane;

public class page {

	public static final int PROGRAMLEN = 10000;
	public static final int PROGRAMNUM = 10;
	public static final int PAGELEN = 6;
	public static final double MIU = 5;
	public static final double SIGMA = 10;
	public static final int NORMLEN = 25;

	public static void main(String[] args) {

		int lostPageOfOpt = 0;
		int lostPageOfClock = 0;
		int lostPageOfLru = 0;
		int lostPageOfFifo = 0;
		int[] program = new int[PROGRAMLEN]; // program为要装入的程序
		for (int i = 0; i < PROGRAMLEN; i++)
			if (i % 25 == 0)
				for (int j = 0; j < NORMLEN && i < PROGRAMLEN; i++, j++)
					program[j] = Norm_rand();
			else
				program[i] = (int) (Math.random() * PROGRAMNUM + 1);

		for (int pro : program)
			System.out.print(" " + pro);
		System.out.println();

		lostPageOfOpt += Opt(program);
		lostPageOfLru += Lru(program);
		lostPageOfClock += Clock(program);
		lostPageOfFifo += Fifo(program);

		JOptionPane.showMessageDialog(null, "执行各种頁面置換算法平均缺页次数："
				+ "\n最佳置换算法（OPT）                   " + lostPageOfOpt
				+ "\n最近最少使用置换算法（LRU）  " + lostPageOfLru
				+ "\n时钟页面置换算法（Clock）       " + lostPageOfClock
				+ "\n先进先出置换算法（FIFO）          " + lostPageOfFifo);

	}

	public static int Norm_rand() {
		double N = 12;
		double x = 0, temp = N;
		do {
			x = 0;
			for (int i = 0; i < N; i++)
				x = x + (Math.random());
			x = (x - temp / 2) / (Math.sqrt(temp / 12));
			x = MIU + x * Math.sqrt(SIGMA);
		} while (x <= 0); // 在此我把小于0的数排除掉了
		int m = (int) x;
		if (m <= 0)
			m = 1;
		else if (m > PROGRAMNUM)
			m = PROGRAMNUM;
		return m;

	}

	public static int Opt(int[] aProgram) {

		int[] program = aProgram;

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

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

		for (int i = 0; i < PROGRAMLEN; i++) {

			int j = 0;
			for (j = 0; j < PAGELEN; j++)
				if (program[i] == page[j])
					break;
			if (j < PAGELEN)
				continue;

			lostPage++;
			for (j = 0; j < PAGELEN; j++)
				if (page[j] == 0) {
					page[j] = program[i];
					break;
				}
			if (j < PAGELEN)
				continue;

			for (j = 0; j < PAGELEN; j++) {
				int k;
				for (k = i + 1; k < PROGRAMLEN; k++)
					if (page[j] == program[k]) {
						index[j] = k;// index存的是page中各数第一次出现的下标
						break;
					}
				if (k == PROGRAMLEN)
					index[j] = PROGRAMLEN;
			}

			int suffixOfMax = 0;
			for (j = 1; j < PAGELEN; j++) {
				if (index[j] > index[suffixOfMax])
					suffixOfMax = j;
			}
			page[suffixOfMax] = program[i];
		}
		return lostPage;

	}

	public static int Lru(int[] aProgram) {

		int[] program = aProgram;

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

		int[] index = new int[PAGELEN];
		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]++;
		}
		return lostPage;
	}

	public static int Clock(int[] aProgram) {

		int[] program = aProgram;

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

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

		int pointer = 0;

		for (int i = 0; i < PROGRAMLEN; i++) {
			int j = 0;
			for (j = 0; j < PAGELEN; j++)
				if (page[j] == program[i]) {
					index[j] = 1;
					break;
				}
			if (j < PAGELEN)
				continue;

			lostPage++;
			while (index[pointer] == 1) {
				index[pointer++] = 0;
				pointer %= PAGELEN;
			}
			page[pointer] = program[i];
			index[pointer++] = 1;
			pointer %= PAGELEN;
		}
		return lostPage;
	}

	public static int Fifo(int[] aProgram) {

		int[] program = aProgram;

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

		int lostPage = 0;
		for (int i = 0; i < PROGRAMLEN; i++) {
			int j = 0;
			for (j = 0; j < PAGELEN; j++) {
				if (program[i] == page[j])
					break;
			}
			if (j < PAGELEN)
				continue;

			lostPage++;
			for (j = 0; j < PAGELEN; j++)
				if (page[j] == 0) {
					page[j] = program[i];
					break;
				}
			if (j < PAGELEN)
				continue;

			for (j = 0; j < PAGELEN - 1; j++)
				page[j] = page[j + 1];
			page[PAGELEN - 1] = program[i];
		}
		return lostPage;
	}
}