页面置换算法（FIFO,LRU,OPT）_最佳置换算法opt、先进先出算法fifo和最近最久未使用算法lru。

1.先进先出置换算法（FIFO）：是最简单的页面置换算法。这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。
2．最佳置换算法（OPT）（理想置换算法）：从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。
3．最近最久未使用（LRU）算法：这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。

具体代码实现：

/**

• 先进先出页面置换算法FIFO
• 借助JDK内置数据结构队列
  */

package com.page_replacementAlgorithm;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;
public class FIFO {

	private final int capacity = 3;
	private int index = 0;
	// 构造一个初始容量为3的空列表
	private Queue<Integer> queue = new ArrayBlockingQueue<Integer>(capacity);

	public FIFO(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			if (queue.size() < capacity) { // 小于queue初始容量
				if (!queue.contains(arr[i])) { // queue没有该页面，将其添加进queue尾部
					queue.add(arr[i]);
				} else {
					continue;
				}
			} else {// 超出queue容量，置换掉最先调入内存的页面
				if (!queue.contains(arr[i])) {
					queue.poll();//获取并移除此队列的头，如果此队列为空，则返回 null。
					queue.add(arr[i]);
				} else {
					continue;
				}
			}
			traverse();
		}
		System.out.println("访问页面需从外存调入的次数为："+(num-1));
		System.out.println("缺页率为："+(float)(num-1)/arr.length);
	}

	/**
	 * 遍历queue容器
	 */
	int num = 1;
	public void traverse() {
		System.out.print("第" + (num++) + "次" + "页面置换：\t");
		for (int i : queue) {
			System.out.print(i + " ");
		}
		System.out.println();
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

-***************
/**

• 最佳置换算法OPT
• 借助ArrayList数据结构
  */

package com.page_replacementAlgorithm;

import java.util.ArrayList;
import java.util.List;


public class OPT {

	private final int capacity = 3;
	private int[] index = new int[2];
	private List<Integer> list = new ArrayList<Integer>(capacity);
	public OPT(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			if (list.size() < capacity) { // 小于list初始容量
				if (!list.contains(arr[i])) { // list没有该页面，将其添加进list尾部
					list.add(arr[i]);
				} else {
					continue;
				}
			} else {// 超出list容量
				index[0] = 100;
				index[1] = 101;
				if (!list.contains(arr[i])) { // 下一个页面如果不在list中
					int a = 0;
					for (int j = i; j < arr.length; j++) {
						if (list.contains(arr[j])) { // arr[j]这个页面会在测试数据中会出现较早
							if (index[0] != list.indexOf(arr[j])) {

								index[a++] = list.indexOf(arr[j]);// 返回此列表中首次出现的指定元素的索引
								if (a == 2) {
									break;
								}
							}
						}
					}
					list.set(noExist(), arr[i]);// 置换掉永不使用的,或许在最长时间内不再访问的页面
				} else { // 下一个页面在list中
					continue;
				}
			}
			traverse();
		}
		System.out.println("访问页面需从外存调入的次数为："+(num-1));
		System.out.println("缺页率为："+(float)(num-1)/arr.length);
	}

	/**
	 * 遍历list容器
	 */
	int num = 1;

	public void traverse() {
		System.out.print("第" + (num++) + "次" + "页面置换：\t");
		for (int i : list) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	/**
	 * 返回要替换的下标
	 */
	private int noExist() {
		int[] brr = { 0, 1, 2 };
		if (brr[0] != index[0] && brr[0] != index[1])
			return brr[0];
		if (brr[1] != index[0] && brr[1] != index[1])
			return brr[1];
		if (brr[2] != index[0] && brr[2] != index[1])
			return brr[2];
		return 2;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

********************************************** -**********************

/**

• 最近最久未使用和最少使用置换算法 LRU
• 自己写的一个栈MyStack数据结构
  */

package com.page_replacementAlgorithm;

public class LRU {

	// 初始化一个容量为 5 的栈
	private MyStack<Integer> stack = new MyStack<Integer>(5);
	private int index = 0;// 一个数组下标的标识，用来除去栈底元素

	public LRU(int[] arr) {
		for (int i = 0; i < arr.length; i++) {// 将数组里 数据存入栈中
			if (stack.getLength() < stack.size()) { // 判断栈不满
				if (!stack.exist(arr[i])) { // 判断栈中有没有该元素，有的话返回true
					stack.push(arr[i]);
					 stack.traverse();
				} else { // 如果有该元素，删除掉栈中该元素，并将该元素置于栈顶
					stack.removeSameElement(arr[i]);
					stack.push(arr[i]);
					stack.traverse2();
				}
			} else { // 栈已满，删除到栈底元素
				if (stack.exist(arr[i])) { // 继续判断如果栈中存在相同元素，将该元素从栈中取出放到栈顶
					stack.removeSameElement(arr[i]);
					stack.push(arr[i]);
					stack.traverse2();
				} else { // 栈中没相同元素，删除栈底元素，在栈顶加新元素
					stack.remove(arr[index++]);
					stack.push(arr[i]);
					stack.traverse(); // 遍历栈中元素
				}
			}
		}
		System.out.println("访问页面需从外存调入的次数为："+(stack.getNum()-1));
		System.out.println("缺页率为："+(float)(stack.getNum()-1)/arr.length);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

-******************************
以下是栈
*****-

package com.page_replacementAlgorithm;

import java.util.EmptyStackException;

/**
 * @ClassName: MyStack
 */
public class MyStack<E> {

	private Object[] Capacity;
	private int size = 0;
	private int length = 0;
	private int index = 0;
	/**
	 * 初始化一个空栈
	 */
	public MyStack() {
	}
	
	/**
	 * 初始化一个大小为 Capacity 的栈
	 */
	public MyStack(int initialCapacity) {
		if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        Capacity = new Object[initialCapacity];
        size = initialCapacity;
	}
	
	/**
	 *  栈的大小
	 */
	public int size() {
		return  size;
	}
	/**
	 * 把项压入堆栈顶部
	 */
	public E push(E item) {
		if(length < size()) {
			Capacity[index++] = item;
			length++;
		}else {
			try {
				throw new Exception("栈满");
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		return item;
	}
	
	/**
	 * 移除堆栈顶部的对象，并作为此函数的值返回该对象。
	 */
	public synchronized E pop() {
		int len = getLength();
		if (len == 0)
			throw new EmptyStackException();
		Capacity[--index] = null;
		length--;
		index--;
		return (E) Capacity[index];
	}
	
	/**
	 * 移除堆栈中的对象，并作为此函数的值返回该对象。
	 */
	public synchronized boolean removeSameElement(E element) {
		int len = getLength();
		if (len == 0)
			throw new EmptyStackException();
		
		int in = searchIndex(element);
		if(in!=-1) {
			int i=in;
			for(; i<size()-1;i++) {
				if(Capacity[i+1]!=null) {
					Capacity[i] = Capacity[i+1];
				}
			}
			Capacity[i] = null;
			length--;
			index--;
			return true;
		}
		return false;
	}
	
	/**
	 * 栈满的话，移除栈底元素
	 */
	public synchronized boolean remove(E element) {
		int len = getLength();
		if (len == 0)
			throw new EmptyStackException();
		int i;
		for (i = 0; i < size() - 1; i++) {
			Capacity[i] = Capacity[i + 1];
		}
		Capacity[i] = null;
		length--;
		index--;
		return true;
	}
	
	/**
	 * 查看堆栈顶部的对象，但不从堆栈中移除它。
	 */
	public synchronized E peek() {
		int len = size();
		if (len == 0)
			throw new EmptyStackException();
		return (E) Capacity[index-1];
	}

	/**
	 * 测试堆栈是否为空。
	 */
	public boolean empty() {
		return getLength() == 0;
	}
	
	/**
	 * 返回堆栈对象的个数
	 */
	public int getLength() {
		return length;
	}
	
	/**
	 * 根据下标查找堆栈中的对象
	 */
	public E search(int i) {
		if(i<size() || i>=0)
			return (E) Capacity[i];
		throw new ArrayIndexOutOfBoundsException();
	}
	
	/**
	 * 根据元素查找此在堆栈中的下标
	 * 返回-1 表示查找失败
	 */
	public int searchIndex(E element) {
		for(int i=0; i<getLength(); i++) {
			if(Capacity[i].equals(element)) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 查看堆栈中是否存在 该对象
	 */
	public boolean exist(E element) {
		for (Object object : Capacity) {
			if(object != null) {
				if(object.equals(element) || object==element)
					return true;
			}
		}		
		return false;
	}
	
	/**
	 * 从栈底到栈顶遍历堆栈中的对象
	 */
	int num = 1;
	public void traverse() {
		System.out.print("第"+(num++)+"次"+"页面置换：\t\t");
		for (Object object : Capacity) {
			System.out.print(object+"\t");
		}
		System.out.println(); 
	}
	public void traverse2() {
		System.out.print("容器内未置换页面：\t");
		for (Object i : Capacity) {
			System.out.print(i + "\t");
		}
		System.out.println();
	}
	public int getNum() {
		return num;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

*********************************-

/**
 * 测试页面置换算法
 */
package com.page_replacementAlgorithm;

import java.util.Scanner;


public class Test {
	
	/**
	 * OPT课本数据 20个页面
	 * 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
	 */
	/**
	 * FIFO课本数据    20个页面 
	 * 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
	 */

	/**
	 * LRU课本上的数据   11个数据 
	 * 4 7 0 7 1 0 1 2 1 2 6
	 */
	private static boolean flag = true;
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		while (flag) {
			System.out.println("*************************");
			System.out.println("   请输入  1或2或3 进行选择        ");
			System.out.println("          1.OPT          ");
			System.out.println("          2.FIFO         ");
			System.out.println("          3.LRU          ");
			System.out.println("*************************");

			int result = s.nextInt();
			// int[] arr = input();
			if(result == 1) {
				new OPT(input());
				isContinue();
			} else if (result == 2) {
				new FIFO(input());
				isContinue();
			} else if (result == 3) {
				new LRU(input());
				isContinue();
			} else {
				System.out.println("您输入的信息有误，请重新输入！");
				isContinue();
			}
		}
	}

	private static int[] input() {
		System.out.println("请输入有多少个页面：");
		Scanner s = new Scanner(System.in);
		int num = s.nextInt();
		System.out.println("在输入页面号，以空格隔开");
		int[] arr = new int[num]; // 用来保存输入的页面数据
		for (int i = 0; i < num; i++) {
			arr[i] = s.nextInt();
		}
		return arr;
	}
	
	private static void isContinue() {
		Scanner s = new Scanner(System.in);
		while(true) {
			System.out.println("是否继续： y/n");
			String result = s.nextLine();
			if(result.equalsIgnoreCase("n")) {
				flag = false;
				System.out.println("***********************");
				System.out.println("*        谢谢观赏            *");
				System.out.println("***********************");
				break;
			} else if(result.equalsIgnoreCase("y")) {
				break;
			}else {
				System.out.println("输入有误");
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84