一分钟学会页面置换算法【OPT、FIFO、LRU、NUR】_opt算法

程序执行期间，若程序所要访问的页面未在内存时，便发出缺页中断，中断处理程序首先保留CPU环境，转入缺页中断处理程序。查找页表，得到该页在外存的物理块后，如果内存未满，则将缺页调入内存并修改页表。
如果内存已满，则按照某种置换算法从内存中选出一页换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。

最佳置换(OPT)算法选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面；采用最佳置换算法可保证获得最低的缺页率。但是由于无法预知哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的；

先进先出（FIFO）算法淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

最近最久未使用（LRU）算法根据页面调入内存后的使用情况进行决策，选择最近最久未使用的页面予以淘汰；该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问一来所经历的时间T，当需要淘汰一个页面时，选择现有页面中T值最大的，即最近最久未使用的页面予以淘汰。

CLCOK算法又称为最近未使用算法（NUR） 每页设置一个访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列；当某个页面被访问时，其访问位置1。淘汰时，检查其访问位，如果是0，就换出；若为1，则重新将它置0；再按FIFO算法检查下一个页面，到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首再去检查第一个页面。

1．假设系统为某进程分配了四个物理块，页面使用走向为：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，分别采用OPT算法，FIFO算法，LRU算法，给出页面的置换过程，以及各自发生了几次页面置换？
OPT:4次；FIFO:6次；LRU:4次

2．打开“Microsoft Visual C++ 6.0”，输入相关代码，根据代码注释把空缺的FIFO算法补充完毕，对程序行进编译运行。给出你所填写的FIFO算法代码：

bc[p%blockCount]=pc[i];
					p++;
1
2

3．根据提示输入上述相关数据，分别记录OPT算法、FIFO算法、LRU算法以及CLOCK算法运行结果：
（1）OPT算法：

（2）FIFO算法

（3）LRU算法

（4）CLOCK算法

——————————————————————————————————————————————————————————————————————————————————————
附上源代码：

#include<iostream>
using namespace std;
void Print(int bc[],int blockCount){
	for(int i=0; i<blockCount;i++){
		cout<<bc[i]<<" ";
	}
	cout<<endl;
}
int Travel(int bc[],int blockCount,int x){
	int index =-1;
	int i;
	for(i=0; i<blockCount; i++){
      if(bc[i]==x){
			index=i; 
			break;
	  }
	}
	return index;
}
void FIFO(int pc[], int bc[], int pageCount, int blockCount){
	cout<<"0:FIFO置换算法"<<endl;
	int i;
	if(pageCount<=blockCount){
		cout<<" 缺页次数为"<<0<<endl;
		cout<<"缺页率为  "<<0<<endl;
	}
	else{
		int noPage=0;
		int p=0;
		for(i=0; i<pageCount;i++){
			cout<<"引用页:"<<pc[i]<<endl;
			if(Travel(bc,blockCount,pc[i])==-1){
				if(i<blockCount){
					bc[i]=pc[i];
				}
				else{
					bc[p%blockCount]=pc[i];
					p++;//页面不在内存，淘汰最先进入的页面。
				}
				noPage++;
				cout<<"物理块情况: ";
				Print(bc, blockCount);
			}
			cout<<endl;
		}
		cout<<"缺页次数为："<<noPage<<endl;
		cout<<" 缺页率为："<<(float)noPage/pageCount<<endl;
	}
}   
int FoundMaxNum(int a[],int n){
	int k,j;
	k=a[0];
	j=0;
	for(int i=0; i<n;i++){
		if(a[i]>=k){
			k=a[i];
			j=i;
		}
	}
	return j;
}
 void LRU(int pc[],int bc[], int pageCount, int blockCount) {
	cout<<"1:LRU 置换算法"<<endl;   
	if(pageCount<=blockCount){
		cout<<"缺页次数为："<<0<<endl; 
		cout<<"缺页率为："<<0<<endl;
	}
	 else{
		int noPage=0;
		int i, j, m;
		int*bc1=new int[blockCount];   
		for(i=0;i<blockCount;i++){
			bc1[i]=0;
		}
		for(i=0; i<pageCount;i++){
			 cout<<"引用页:"<<pc[i]<<endl;
			if(Travel(bc,blockCount,pc[i])==-1){//页面不在内存
				if(i<blockCount) {//欲调页
					bc[i]=pc[i];
					for(int p=0; p<=i; p++){
							bc1[p]++;
					}
				}
				else{
					for(j=0;j<blockCount;j++){  
						bc1[j]++;
					}
					int k=FoundMaxNum(bc1,blockCount);		
					bc[k]=pc[i];
					bc1[k]=1;
				}
				noPage++;
				cout<<"物理块情况:"; 
				Print(bc,blockCount);
			}
			else {                                 //页面在内存
				if(i<blockCount){
					for(j=0; j<=i; j++){
					bc1[j]++;
				}
				for(m=0; m<i;m++){
					if(bc[m]==pc[i]){
						break;
					}
				}
				bc1[m]=1;
				bc[m]=pc[i];
			}
			else{
				for(j=0;j<blockCount;j++){
					bc1[j]++;
				}
				for(m=0;m<blockCount;m++){
					if(bc[m]==pc[i]){
						break;
					}
				}
				bc1[m]=1;
				bc[m]=pc[i];
				}
			}
			cout<<endl;
	 }
	cout<<"缺页次数为:"<<noPage<<endl;
	cout<<"缺页率为:"<<(float)noPage/pageCount<<endl; 
	delete bc1;
	}
 }
void Optiomal(int pc[],int bc[],int pageCount,int blockCount){	
	cout<<"2:最佳置换算法"<<endl;   
	if(pageCount<=blockCount){
		cout<<"缺页次数为："<<0<<endl;
		cout<<"缺页率为："<<0<<endl;
	}
	else{
		int noPage=0;
		int i,j, k;
		for(i=0; i<pageCount;i++){
			cout<<"引用页:"<<pc[i]<<endl;
			if(Travel(bc,blockCount,pc[i]) ==-1){
				if(i<blockCount){
					bc[i]=pc[i];
				}
				else{
					int max=0;
					int blockIndex;;
					for(j=0;j<blockCount; j++){
						for(k=i;k<pageCount; k++){
							if(bc[i]=pc[k]){	
							break;
							}
						}
						if(k>=max){ 
							max=k;
							blockIndex=j;
						}
					}
					bc[blockIndex]=pc[i];
				}
				 noPage++;
				cout<<"物理块情况:"; 
				Print(bc, blockCount);
			}
			cout<<endl;
		}
		cout<<"缺页次数为："<<noPage<<endl;
		cout<<"缺页率为："<<(float)noPage/pageCount<<endl;
	}
}
void NRU(int pc[], int bc[], int pageCount,int blockCount){
	cout<<"3: Clock置换算法"<<endl ;
	if(pageCount<=blockCount){
		cout<<"缺页次数为"<<0<<endl;
		cout<<"缺页率为"<<0<<endl;
	}
	else{
	int noPage=0;
	 int i,j;
	 int *bc1=new int[blockCount];   
	 for(i=0;i<blockCount;i++){
		 bc1[i]=0;
	 }
	 int replace=0;
	 for(i=0;i<pageCount;i++){
		cout<<"引用页:"<<pc[i]<<endl;
		int index=Travel(bc, blockCount, pc[i]);
		if(index ==-1) {
			for(j=0;j<blockCount;j++){
				if(bc1[replace]==1){
					bc1[replace]=0;
					replace =(replace+1)%blockCount;
				}
				else{
					break;
				}
			}
				bc[replace]=pc[i];
				bc1[replace]=1;
				replace=(replace+1)% blockCount; 
				noPage++;
				cout<<"物理块情况:"; 
				Print(bc,blockCount);  
				cout<<"标志位情况:";   
				Print(bc1,blockCount);
		}
		else{
			bc1[index]=1;
			replace=(index+1)% blockCount; 
			cout<<"物理块情况:";
			Print(bc,blockCount);
			cout<<"标志位情况:";
			Print(bc1,blockCount);
		}
		cout<<endl;
	 }
	cout<<"缺页次数为："<<noPage<<endl;
	cout<<"缺页率为："<<(float)noPage/pageCount<<endl;
	delete bc1;
	}
}
 int main(){
	int pageCount,blockCount,i;
	cout<<"输入页面数"<<endl;
	cin>>pageCount;
	int *pc=new int[pageCount];  
	cout<<"输入页面走向"<<endl;  
	for(i=0;i<pageCount;i++){
		cin>>pc[i];
	}
	cout<<"输入物理块数"<<endl;   
	cin>>blockCount;  
	cout<<"0:FIFO置换算法"<<endl;   
	cout<<"1:LRU置换算法"<<endl;   
	cout<<"2:最佳置换算法"<<endl;
	cout<<"3: Clock置换算法"<<endl;
	cout<<"按数字选择类别:"<<endl;
	int n;
	while(cin>>n){
		if(n==0){
			int *bc=new int[blockCount];
			FIFO(pc,bc,pageCount,blockCount);
			delete bc;
		}
		else if(n==1){
			int *bc=new int[blockCount];
			LRU(pc,bc,pageCount,blockCount);
			delete bc;
		}
		else if(n==2){
			 int *bc=new int[blockCount];
			 Optiomal(pc,bc,pageCount,blockCount);
			 delete bc;
		}
		else if(n==3){
			 int *bc=new int[blockCount];
			 for(i=0; i<blockCount;i++){
				bc[i]=-1;
			 }
			NRU(pc,bc,pageCount,blockCount); 
			delete bc;
		}
		else break;
	}
	delete pc; 
	return 0;
}
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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266

其实做人最重要的是自信，到哪儿都一样。————《叶问4》