实验描述见
main.cpp后几行的注释
几个注意事项：
-
实验与网上的不同
-
程序执行顺序的生成
- 顺序执行有规律，都是连续的2个，可以把2个连续的顺序执行的模块看做一个bundle
- 用
up和down记录当前向前跳河向后跳的次数，若向前跳的次数多则之后先考虑向后跳
-
OPT和FIFO和LRU区别
-
OPT(参照FIFO) FIFO LRU 在缺页置换时，考虑最长不用的内存页，替换掉 (参照体) 在成功命中内存页时，将命中内存页在栈中往栈顶提
main.cpp 主函数
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
/*
* @Author: MetaNetworks
* @Date: 2019-11-22 22:07:11
* @LastEditors: MetaNetworks
* @LastEditTime: 2019-11-23 17:04:44
* @Description: MetaNetworks' Code
*/
#include <iostream>
#include "cdef.h"
#define JOB_INS_NUM 320
int main(int argc, char const *argv[])
{
// 随机化种子
srand((long)time(0));
MemoryManager mManager(JOB_INS_NUM);
int *serial = mManager.simulate();
SwapAnalyzer analyzer(serial,JOB_INS_NUM);
analyzer.opt();
analyzer.fifo();
analyzer.lru();
return 0;
}
// 2、实验内容
// （1）假设每个页面中可存放10条指令，分配给一作业的内存块数为4。
// （2）用C语言模拟一作业的执行过程。该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已经在内存中，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块中均已装入该作业，则需进行页面置换。最后显示其物理地址，并转下一条指令。在所有320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。
// （3）置换算法：请分别考虑OPT、FIFO和LRU算法。
// （4）作业中指令的访问次序按下述原则生成：
// •50%的指令是顺序执行的。
// •25%的指令是均匀分布在前地址部分。
// •25%的指令时均匀分布在后地址部分。
// 具体的实施办法是：
// ① 在[0，319]之间随机选取一条起始执行指令，其序号为m；
// ② 顺序执行下一条指令，即序号为m+1的指令；
// ③ 通过随机数，跳转到前地址部分[0，m-1]中的某条指令处，其序号为m1；
// ④ 顺序执行下一条指令，即序号为m1+1的指令；
// ⑤ 通过随机数，跳转到后地址部分[m1+2，319]中的某条指令处，其序号为m2；
// ⑥ 顺序执行下一条指令，即序号为m2+1的指令；
// ⑦ 重复跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行的过程，直至执行320条指令。
cdef.h 数据结构定义
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
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
#define INS_PER_PAGE 10
#define MEM_BLOCK_PER_JOB 3
#define STATUS_ERROR -1
#define MAXINT 2147483647
set<int> exp3_s;
int getRandom(int minLap,int maxLap){
int n = rand()%(maxLap-minLap+1)+minLap;
// 记录不能走的
set<int> tmp;
tmp.clear();
while (exp3_s.find(n) != exp3_s.end())
{
// 找到了,证明这个数不可取
tmp.insert(n);
if(tmp.size() == maxLap - minLap + 1){
// 找完了
break;
}
n = rand()%(maxLap-minLap+1)+minLap;
}
if(tmp.size() == maxLap - minLap + 1){
//cout<<"警告：无符合的block块"<<endl;
return -1;
}
else{
exp3_s.insert(n);
//cout<<n<<endl;
return n;
}
}
class MemoryManager{
public:
int block_num;
int * ins = nullptr;
int block_index = 0;
int up=0,down = 0,force=0; // 向前跳和向后跳的次数
MemoryManager(int ins){
this->block_num = ins/2;
this->ins = (int *)malloc(sizeof(int)*this->block_num);
}
~MemoryManager(){
if(ins != nullptr)
free(ins);
}
void add(int num){
ins[block_index] = num;
block_index++;
}
int chooseBlock(int blockNum){
// 找一个相对较好的Block
if (up>down){
// 优先向下走
if(blockNum+2<=block_num){
//没有越界，可用向下走
int t = getRandom(blockNum+2,block_num);
if(t != STATUS_ERROR){
down ++;
return t;
}
}
// 不能向下走，只能向上走
if (blockNum != 1){
// 能向上走
int t = getRandom(1,blockNum-1);
if(t != STATUS_ERROR){
up ++;
return t;
}
}
}
// 优先向上走
else{
if (blockNum != 1){
// 向上走
int t = getRandom(1,blockNum-1);
if(t != STATUS_ERROR){
up ++;
return t;
}
}
else{
// 只能向下走
if(blockNum+2<=block_num) {
//没有越界，可用向下走
int t = getRandom(blockNum + 2, block_num);
if (t != STATUS_ERROR) {
down++;
return t;
}
}
}
}
// 不能向上走，也不能向下+1走，说明只剩下跳转到下一个block了
if (blockNum+1 <= block_num){
// 没到底
int t = getRandom(blockNum+1,blockNum+1);
if(t != STATUS_ERROR){
force ++;
return t;
}
}
return STATUS_ERROR;
}
//动作
int * simulate(){
int times = 0;
cout<<"开始生成随机指令序列..."<<endl;
while (true)
{
// 初始化一些记录变量,尽量保证向前跳和向后跳次数相等
block_index = 0;up = 0;down = 0;force = 0;exp3_s.clear();
// 自动随机
int current_b = getRandom(1,block_num);
add(current_b);
//cout<<current_b;
// step.1 生成起始block块,从1开始计数
while ((current_b = chooseBlock(current_b)) != STATUS_ERROR){
add(current_b);
//cout<<"->"<<current_b;
}
if (block_index == block_num){
// 一个序列完成
cout<<"生成完成：顺序执行"<<block_num<<"次，向前"<<up<<"次，向后"<<down<<"次，最后强制顺序执行："<<force<<"次"<<endl;
for (int i = 0; i < block_index; ++i) {
cout<<2*ins[i]-1<<"->"<<2*ins[i]<<"->";
}
cout<<endl;
cout<<"是否接受？接受请输入y并回车，其他任意键继续生成"<<endl;
int c = getchar();
if (c == 'y'){
break;
}
else{
cout<<"继续随机生成"<<endl;
}
} else{
//cout<<"警告："<<endl;
}
++times;
}
// 返回一个可用的序列，转换为页面而不是指令
int* ss=(int*)malloc(sizeof(int)*block_num*2);
int index =0;
for (int j = 0; j < block_num; ++j) {
ss[index] = (ins[j]*2-1-(ins[j]*2-1)%INS_PER_PAGE)/INS_PER_PAGE;
ss[index+1] = (ins[j]*2-(ins[j]*2)%INS_PER_PAGE)/INS_PER_PAGE;
index+=2;
}
return ss;
}
};
// 注意：页数是从0-9才是10
#include <queue>
class SwapAnalyzer{
public:
int *serial;
int length;
int mem[MEM_BLOCK_PER_JOB];
int total_size,lack_size;
SwapAnalyzer(int *serial, int length) : serial(serial), length(length) {reset();}
void mem_pop(){
for (int i = 0; i < MEM_BLOCK_PER_JOB-1; ++i){
int page = mem[i];
mem[i]=mem[i+1];
}
}
void mem_exchange(int old_page_id,int new_page_id){
int page = mem[old_page_id];
mem[old_page_id] = mem[new_page_id];
mem[new_page_id] = page;
}
void mem_in(int index,int page){
mem[index] = page;
}
void mem_insert_tail(int new_page){
mem[MEM_BLOCK_PER_JOB-1]=new_page;
}
int mem_find(int page){
int index = STATUS_ERROR;
for (int i = 0; i < MEM_BLOCK_PER_JOB ; ++i) {
if (mem[i] == STATUS_ERROR){
continue;
}
if(mem[i]==page){
index = i;
break;
}
}
return index;
}
int isFull(){
for (int i = 0; i < MEM_BLOCK_PER_JOB; ++i) {
if (mem[i]==STATUS_ERROR){
return i;
}
}
return STATUS_ERROR;
}
int getNextDistance(int beginIndex,int value){
int dis = 1;
for (int i = beginIndex; i < length; ++i) {
if (serial[i]==value){
return dis;
}
else{
dis++;
}
}
return STATUS_ERROR;
}
void opt(){
reset();
cout<<">>> OPT算法"<<endl;
for (int i = 0; i < length; ++i) {
//对应每一条访存页
int page = serial[i];
int point = isFull();
int result = mem_find(page);
if(result == STATUS_ERROR){
if (point != STATUS_ERROR){
// point空着
mem_in(point,page);
}
else{
// 没空
// 需要置换
// 选择一个最久未使用的
int maxIndex=STATUS_ERROR;
int maxDis= -1;
for (int j = 0; j < MEM_BLOCK_PER_JOB; ++j) {
int dis = getNextDistance(i+1,mem[j]);
if (dis>maxDis || dis == STATUS_ERROR){
maxIndex = j;
maxDis = dis;
}
if(dis == STATUS_ERROR){
break;
}
}
// 置换maxIndex
mem_in(maxIndex,page);
}
lack_size++;
}
total_size++;
}
cout<<"总指令数："<<total_size<<"，缺页次数："<<lack_size<<"，缺页率："<<(float)lack_size/total_size*100.0<<"%"<<endl;
}
void fifo(){
reset();
cout<<">>> FIFO算法"<<endl;
for (int i = 0; i < length; ++i) {
//对应每一条访存页
int page = serial[i];
int point = isFull();
int result = mem_find(page);
if(result == STATUS_ERROR){
if (point != STATUS_ERROR){
// point空着
mem_in(point,page);
lack_size++;
}
else{
// 没空
// 需要置换
mem_pop();
mem_insert_tail(page);
lack_size++;
}
}
total_size++;
}
cout<<"总指令数："<<total_size<<"，缺页次数："<<lack_size<<"，缺页率："<<(float)lack_size/total_size*100.0<<"%"<<endl;
}
void lru(){
reset();
cout<<">>> LRU算法"<<endl;
for (int i = 0; i < length; ++i) {
//对应每一条访存页
int page = serial[i];
int point = isFull();
int result = mem_find(page);
if(result == STATUS_ERROR){
if (point != STATUS_ERROR){
// point空着
mem_in(point,page);
lack_size++;
}
else{
// 没空
// 需要置换
mem_pop();
mem_insert_tail(page);
lack_size++;
}
}
else{
// LRU置换新 result号放至最后
int endi = (point == STATUS_ERROR)?MEM_BLOCK_PER_JOB-1:point-1;
for (int j = result; j < endi; ++j) {
mem_exchange(j,j+1);
}
}
total_size++;
}
cout<<"总指令数："<<total_size<<"，缺页次数："<<lack_size<<"，缺页率："<<(float)lack_size/total_size*100.0<<"%"<<endl;
}
private:
void reset(){
for (int &i : mem) {
i = STATUS_ERROR;
}
lack_size = 0;
total_size = 0;
}
};
结果
1
2
3
4
5
6
7
8
9
10
11
开始生成随机指令序列...
生成完成：顺序执行160次，向前81次，向后78次，最后强制顺序执行：0次
317->318->35->36->147->148->105->106->185->186->129->130->279->280->109->110->127->128->97->98->167->168->7->8->87->88->9->10->27->28->5->6->153->154->55->56->71->72->43->44->207->208->169->170->273->274->31->32->187->188->57->58->65->66->11->12->211->212->135->136->221->222->77->78->161->162->115->116->195->196->107->108->287->288->163->164->277->278->225->226->309->310->39->40->149->150->29->30->73->74->61->62->281->282->19->20->91->92->53->54->173->174->155->156->261->262->23->24->157->158->37->38->151->152->145->146->253->254->69->70->301->302->289->290->307->308->291->292->297->298->191->192->299->300->181->182->247->248->233->234->265->266->227->228->305->306->125->126->259->260->229->230->243->244->89->90->283->284->141->142->213->214->21->22->121->122->119->120->293->294->177->178->303->304->263->264->311->312->15->16->79->80->25->26->219->220->165->166->239->240->13->14->201->202->101->102->223->224->113->114->203->204->51->52->199->200->41->42->235->236->171->172->175->176->85->86->267->268->251->252->257->258->1->2->271->272->3->4->47->48->17->18->313->314->133->134->237->238->81->82->93->94->75->76->83->84->63->64->249->250->159->160->255->256->67->68->103->104->49->50->245->246->33->34->319->320->197->198->217->218->189->190->209->210->111->112->193->194->45->46->205->206->179->180->295->296->215->216->315->316->231->232->285->286->241->242->269->270->137->138->183->184->95->96->143->144->99->100->275->276->139->140->131->132->123->124->59->60->117->118->
是否接受？接受请输入y并回车，其他任意键继续生成
y
>>> OPT算法
总指令数：320，缺页次数：147，缺页率：45.9375%
>>> FIFO算法
总指令数：320，缺页次数：175，缺页率：54.6875%
>>> LRU算法
总指令数：320，缺页次数：173，缺页率：54.0625%
