页面替换FIFO、LRU----------Java实现

Java实现
1、实验要求

1、实验结果

地址流整理、FIFO替换结果

LRU页面替换（代码中不包含这部分）

堆栈实现LRU

不同页数命中情况

package project0202;

import java.util.*;

public class projectmain {

	public static void FIFO(ArrayList<Integer> l, int page) {
		ArrayList<String> L = new ArrayList<String>();
		ArrayList<String[]> L1 = new ArrayList<String[]>();
		ArrayList<Integer> LL = new ArrayList<Integer>();
		int i = 0;
		int j = 0;
		while (i < l.size()) {
			String s[] = new String[page];
			if (LL.size() < page && !LL.contains(l.get(i))) {
				LL.add(l.get(i));

				L.add("移进");
			} else if (LL.size() < page) {

				L.add("命中");
			} else {
				if (!LL.contains(l.get(i))) {
					LL.set(j % page, l.get(i));

					j++;
					L.add("替换");
				} else {

					L.add("命中");
				}

			}
			for (int t = 0; t < LL.size(); t++) {
				s[t] = LL.get(t).toString();
			}
			if (LL.size() == page) {
				s[j % page] += "*";
			}
			L1.add(s);
			i++;
		}
		for (int n = 0; n < page; n++) {
			for (int t = 0; t < l.size(); t++) {
				System.out.print(L1.get(t)[n] + "\t");
			}
			System.out.println();
		}
		for (int t = 0; t < l.size(); t++) {
			System.out.print(L.get(t) + "\t");
		}
		int count = Collections.frequency(L, "命中");
		double d = (double) count / l.size();
		System.out.println();
		System.out.println("命中次数：\t" + count + "\t地址流个数：\t" + l.size());
		System.out.println("命中率为：\t" + d);
		System.out.println();

	}

	public static void LRU(ArrayList<Integer> l, int page) {
		ArrayList<ArrayList<String>> L = new ArrayList<ArrayList<String>>();
		ArrayList<ArrayList<Integer>> L1 = new ArrayList<ArrayList<Integer>>();

		int i = 0;
		do {
			ArrayList<Integer> LL = new ArrayList<Integer>();
			if (i != 0)
				LL.addAll(L1.get(L1.size() - 1));
			if (LL.contains(l.get(i))) {

				LL.remove(l.get(i));
//				System.out.println(LL);
				LL.add(l.get(i));
//				System.out.println(LL);
			} else {

				LL.add(l.get(i));

			}
			i++;
			L1.add(LL);
		} while (i < l.size());
		HashSet<Integer> set = new HashSet<Integer>();
		set.addAll(l);
		int N = set.size();
//		System.out.println(N);
		int n = 1;
		while (n <= N) {
			ArrayList<String> L0 = new ArrayList<String>();
			ArrayList<Integer> LL = new ArrayList<Integer>();
			i = 0;
			while (i < l.size()) {
				if (i != 0)
					LL = (ArrayList<Integer>) L1.get(i - 1).clone();
//				LL.remove(LL.size()-1);
				if (LL.contains(l.get(i))) {
					if (LL.indexOf(l.get(i)) < LL.size() - n) {
						L0.add("替换");
					} else
						L0.add("命中");
				} else {
					if (LL.size() < n) {
						L0.add("移入");
					} else
						L0.add("替换");
				}
				i++;
			}
			L.add(L0);
			n++;
		}
		int j = 0;
		while (j < N) {
			for (i = 0; i < L1.size(); i++) {
				if (j < L1.get(i).size()) {
					System.out.print(L1.get(i).get(L1.get(i).size() - j - 1) + "\t");
				} else
					System.out.print(" " + "\t");
			}
			j++;
			System.out.println();
		}
		j = 0;
		while (j < N) {
			for (i = 0; i < L1.size(); i++) {
				System.out.print(L.get(j).get(i) + "\t");
			}
			int count = Collections.frequency(L.get(j), "命中");
			double d = (double) count / l.size();
			System.out.print("\t页数：" +( j+1));
			System.out.print("\t命中次数：" + count + "\t地址流个数：" + l.size());
			System.out.print("\t命中率为：" + d);
			j++;
			System.out.println();
		}

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入页面大小");
		int pagesize = sc.nextInt();
		System.out.println("请输入主存容量");
		int memorysize = sc.nextInt();
		int page = memorysize / pagesize;
		ArrayList<Integer> L = new ArrayList<Integer>();
		ArrayList<Integer> l = new ArrayList<Integer>();
		System.out.println("请输入地址流个数");
		int i = sc.nextInt();
		System.out.println("请输入" + i + "个地址");
		while (i > 0) {
			L.add(sc.nextInt());
			i--;
		}
		System.out.println(L);
		i = 0;
		while (i < L.size()) {
			l.add(L.get(i) / pagesize);
			i++;
		}
		System.out.println(l);
		FIFO(l, page);
		LRU(l, page);


	}

}