操作系统之页面置换模拟程序设计_NRU改进_最近未用nru示例

介绍

1. 假设分给一作业的内存块数为4，每个页面中可存放10条指令。

2. 用C语言设计一个程序，模拟一作业的执行过程。设该作业共有320条指令，即它的地址空间为32页，目前它的所有页面都还未调入内存。在模拟过程中，如果所访问的指令已经在内存，则显示其物理地址，并转下一条指令。如果所访问的指令尚未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块中均已装入该作业的虚页面，则需进行页面置换。最后显示其物理地址，并转下一条指令。在所有320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。

3. 置换算法：请考虑 NRU改进算法。

4. 作业中指令的访问次序要求按下述原则生成：

   • 50%的指令是顺序执行的。
   • 25%的指令是均匀分布在前地址（即低地址）部分。
   • 25%的指令是均匀分布在后地址（即高地址）部分。

   具体的实施办法是：
   ① 在[0，319]之间随机选取一条起始执行指令，其序号为m；
   ② 顺序执行下一条指令，即序号为m+1的指令；
   ③ 通过随机数，跳转到前地址部分[0，m-1]中的某条指令处，其序号为m1；
   ④ 顺序执行下一条指令，即序号为m1+1的指令；
   ⑤ 通过随机数，跳转到后地址部分[m1+2，319]中的某条指令处，其序号为m2；
   ⑥ 顺序执行下一条指令，即序号为m2+1的指令；
   ⑦ 重复“跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行”的过程，直至执行完全部320条指令。

5. 指令序列转换成页访问序列。
   第 0 条-第 9 条指令为第0页（对应虚存地址为[0，9]）
   第10条-第19条指令为第1页（对应虚存地址为[10，19]）
   ………………………………
   第310条-第319条指令为第31页（对应虚存地址为[310，319]）

最近未用(Not Recently Used, NRU)算法_改进

CLOCK算法是给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1;当该页随后再被访问到时，它的使用位也被置为1。对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU)算法.
而其改进算法不仅考虑使用情况A,还增加了置换代价(修改位M)。
则有四类页面 (根据A，M)：
第1类：无访问(A=0) ，无修改(M=0) ；
第2类：无访问(A=0) ，有修改(M=1) ；
第3类：有访问(A=1) ，无修改(M=0) ；
第4类：有访问(A=1) ，有修改(M=1) ；

算法描述

1. 从指针指向的当前位置开始扫描循环队列。寻找A=0,M=0页面（第一类页面）
2. 若第一步失败，则重新开始寻找A=0,M=1页面（第二类页面）。并将经过的页面访问位置0。
3. 若第二步失败，则返回开始位置，此时所有访问位均为0。重复第一步。（实际上是寻找第三类页面）
   若仍失败，重复第二步。（实际上是寻找第四类页面）

代码

//页面置换_NRU改进 
#include<bits/stdc++.h>
using namespace std; 
int s[320];
int cnt = 0;
int lost = 0;
typedef struct node {
	int order; //页面序号 
	int A;//访问位 
	int M;//修改位 
}cache_;//页面元素 
list<cache_> cache ;
list<cache_>::iterator it ;
list<cache_>::iterator endd;
list<cache_>::iterator l;
//初始化 
void init()
{ 
	cnt = 0;	//访问次数为 0 
	lost = 0;	//缺页次数为 0  
	it = cache.begin() ;
	endd = cache.end();
	endd --;
	for(int i=0;i<320;i++)
		s[i] = 220+i;  //设置指令的物理地址 
}
//寻找当前指令是否在内存块中
bool find (int x)
{
	bool judge = false;
	for(list<cache_>::iterator iter = cache.begin() ; iter != cache.end() ; iter++)
    {
        if((*iter).order == x ){
        	judge = true; 
			(*iter).A = 1;  
		} 
    } 
    return judge;
} 
//当内存空间已满的时候，进行页面置换 
void delete_cache(){ 
	bool judge = false;
	l = it --;
	//第一次访问，寻找A=0，M=0的第一类页面，所遇到的第一个页面即为所选的淘汰页，不改变访问位 
	for(list<cache_>::iterator iter = it ; iter != cache.end() ; iter++)
    {
        if((*iter).A  == 0 && (*iter).M  == 0){
        	it = iter; 
			judge = true;
			break; 
		}  
		if (iter == endd) iter = cache.begin() ;
		if (iter == l) break; 
    } 
	if ( judge == true ) {
		cache.erase( it); 
		int cc = 1;
		for(list<cache_>::iterator iter = cache.begin() ; iter != cache.end() ; iter++)
	    {
	        if( it == iter ) {
	        	if(cc < 3) it = iter++;
	        	else it = cache.begin();
	        	break;
			}
			cc ++;
	    } 
		return;
	}
	//若第一轮失败，寻找A=0，M=1的页面，将所遇到的第一个页面作为淘汰页面，
	//并将所有扫描过的页面访问位置0 
	for(list<cache_>::iterator iter = it ; iter != cache.end() ; iter++)
    {
        if((*iter).A  == 0 && (*iter).M  == 1){
        	it = iter; 
			judge = true;
			break; 
		}  
		(*iter).A  = 0;  
		
		if (iter == endd) iter = cache.begin() ;
		if (iter == l) break; 
    } 
    if ( judge == true ) {
		cache.erase( it); 
		int cc = 1;
		for(list<cache_>::iterator iter = cache.begin() ; iter != cache.end() ; iter++)
	    {
	        if( it == iter ) {
	        	if(cc < 3) it = iter++;
	        	else it = cache.begin();
	        	break;
			}
			cc ++;
	    } 
		return;
	}
	//若第二步也失败，则将指针返回到开始的位置，重复第一步，必要时重复第二步 
	
	//第一次访问，寻找A=0，M=0的第一类页面，所遇到的第一个页面即为所选的淘汰页，不改变访问位 
	for(list<cache_>::iterator iter = it ; iter != cache.end() ; iter++)
    {
        if((*iter).A  == 0 && (*iter).M  == 0){
        	it = iter; 
			judge = true;
			break; 
		}  
		
		if (iter == endd) iter = cache.begin() ;
		if (iter == l) break; 
    } 
	if ( judge == true ) {
		cache.erase( it); 
		int cc = 1;
		for(list<cache_>::iterator iter = cache.begin() ; iter != cache.end() ; iter++)
	    {
	        if( it == iter ) {
	        	if(cc < 3) it = iter++;
	        	else it = cache.begin();
	        	break;
			}
			cc ++;
	    } 
		return;
	}
	//若第一轮失败，寻找A=0，M=1的页面，将所遇到的第一个页面作为淘汰页面，
	//并将所有扫描过的页面访问位置0 
	for(list<cache_>::iterator iter = it ; iter != cache.end() ; iter++)
    {
        if((*iter).A  == 0 && (*iter).M  == 1){
        	it = iter; 
			judge = true;
			break; 
		}  
		(*iter).A  = 0;  
		
		if (iter == endd) iter = cache.begin() ;
		if (iter == l) break; 
    } 
    if ( judge == true ) {
		cache.erase( it); 
		int cc = 1;
		for(list<cache_>::iterator iter = cache.begin() ; iter != cache.end() ; iter++)
	    {
	        if( it == iter ) {
	        	if(cc < 3) it = iter++;
	        	else it = cache.begin();
	        	break;
			}
			cc ++;
	    } 
		return;
	}
}
//执行每一条指令 
int process(int x)
{
	cout<<"第"<< cnt<<" 条指令  " ;  
	cnt++; 
	cache_ y;
	y.order = x/10;
	y.A = 0;
	y.M = 0;
	//判断当前指令是否在内存块中 
	bool judge = find(x/10);
	//如果当前指令在内存块中，显示其物理地址 
	if(judge == true) {
		cout <<"  物理地址："<<s[x]<<endl;
	}
	//如果当前指令不在内存块中 
	else{ 
		lost ++;
		//如果内存块还有空余，直接将该指令所在页面调入内存块 
		if(cache.size() < 4 ){
			cache.push_back(y);
		}
		//如果内存块没有空余，进行页面置换 
		else {
			delete_cache();
			cache.push_back(y);
		} 
		cout <<"  物理地址："<<s[x]<<endl;
	}
	return 1;
}
int main()
{
	init();
	int m=rand()%320;//在[0，319]之间随机选取一条起始执行指令，其序号为m 
	process(m);//执行指令，即序号为 m的指令
	process(m+1);//顺序执行下一条指令，即序号为m+1的指令 
	//	重复"跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行"的过程，159次 
	for(int i=0;i<316;i+=4)
	{ 
		int m1=rand()%m;//通过随机数，跳转到前地址部分[0，m-1]中的某条指令处，其序号为m1
		process(m1);//执行指令，即序号为m1的指令
		process(m1+1);//顺序执行下一条指令，即序号为m1+1的指令
		int m2=rand()%(320-(m1+2)) + m1 + 2;//通过随机数，跳转到后地址部分[m1+2，319]中的某条指令处，其序号为m2
		process(m2);//执行指令，即序号为m1的指令
		process(m2+1);//顺序执行下一条指令，即序号为m2+1的指令
	}
	int m1=rand()%m;//通过随机数，跳转到前地址部分[0，m-1]中的某条指令处，其序号为m1
	process(m1);//执行指令，即序号为m1的指令
	process(m1+1);//顺序执行下一条指令，即序号为m1+1的指令
	cout<<endl<<"缺页率为"<<lost/320.0  <<endl; 
	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

测试结果