C语言实现页面置换算法(FIFO、LRU)

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
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
#include<iostream>
#include<process.h>
#include<stdlib.h>
#include<ctime>
#include<conio.h>
#include<stdio.h>
#include<string.h>
using namespace std;

#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|n")/*表格控制*/
#define bsize 4 //物理块大小
#define psize 16 //进程大小
 void chushihua();//初始化函数
 void ymzh();
 void yemianzhihuan ();
 void changeaddr(struct Page p[], int logaddr);
 void dizhizhuanhuan();
 void menu();
 int wang();

 int yemianliu[32]={0};//全局变量数组,地址流
 int p;
 struct Page  {
     int pno;//页号
     int flag;//标志位
     int cno;//主存号
     int modf;//修改位
     int addr;//外存地址
}Page;  //全局变量p是一共有多少地址流

 typedef struct pagel
 {
     int num; /*记录页面号*/
     int time;  /*记录调入内存时间*/
 }Pagel;  /*页面逻辑结构,方便算法实现*/

 Pagel b[bsize]; /*内存单元数*/
 int c[bsize][psize];/*保存内存当前的状态:缓冲区*/
 int queue[100];/*记录调入队列*/
 int k;/*调入队列计数变量*/
 int phb[bsize]={0};//物理块标号
 int pro[psize]={0};//进程序列号
 int flag[bsize]={0};//进程等待次数(存放最久未被使用的进程标志)*/
 int i=0,j=0;//i表示进程序列号,j表示物理块号*/
 int m =-1,n =-1;//物理块空闲和进程是否相同判断标志*/
 int mmax=-1, maxflag=0;//标记替换物理块进程下标*/
 int count =0; //统计页面缺页次数

 void chushihua() //初始化函数
{
     int t;
     srand(time(0));//随机产生指令序列
         p=12+rand()%32;
     cout<<"地址流序列:";
     cout<<endl;
     for(i=0; i<p; i++)
     {
         t=1+rand()%9;
         yemianliu[i]=t;//将随机产生的指令数存入页面流
    }
    for (i=p-1;i>=0;i--)
    {
        cout<<yemianliu[i]<<" ";
    }
    cout<<endl;
}
void ymzh()
{
    chushihua();
     yemianzhihuan();
}

 void yemianzhihuan()
 {
      int a;
     printf("----------------------------------n");
     printf("☆☆欢迎使用分页模拟实验系统☆☆n");
     printf("----------------------------------");
     printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆n");
     printf("☆☆1.进入硬件地址变换算法  ☆☆n");
     printf("☆☆------------------------☆☆n");
     printf("☆☆2.进入页面置换算法      ☆☆n");
     printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆n");
     printf("请输入您的选择:");
 switch(a)
 {
     case 1:
         ymzh();
         break;
     case 2:
         wang();
         break;
     default:
     cout<<"输入有误,请重新输入!"<<endl;
     break;
 }
}

 void changeaddr(struct Page p[], int logaddr){//地址变换
     int j=logaddr/64;//对应的块号
     int k=logaddr%64; //对应的偏移量
     int flag=0;
     int addr;
     for(int i=0;i<8;i++)
     {
        if(p[i].pno==j)//找到对应的页号
        {
            if(p[i].flag==1)//页面标志为1
            {
             addr=p[i].cno*64+k;
             cout<<"物理地址为:"<<addr<<endl;
             cout<<"详细信息:"<<"t页面号:"<<p[i].pno<<"t 主存号："<<p[i].cno<<"t偏移量:"<<k<<endl;
             flag=1;
             break;
            }
        }
    }

        if(flag==0)
            cout<<"该页不在主存,产生缺页中断"<<endl;
    }

 void dizhizhuanhuan()
 {
     int a;
     int ins;//指令逻辑地址
     struct Page p[8];
    p[0].pno=0;p[0].flag=1;p[0].cno=5;p[0].modf=1;p[0].addr=011;
    p[1].pno=1;p[1].flag=1;p[1].cno=8;p[1].modf=1;p[1].addr=012;
    p[2].pno=2;p[2].flag=1;p[2].cno=9;p[2].modf=0;p[2].addr=013;
    p[3].pno=3;p[3].flag=1;p[3].cno=10;p[3].modf=0;p[3].addr=015;
    p[4].pno=4;p[4].flag=0;p[4].addr=017;
    p[5].pno=5;p[5].flag=0;p[5].addr=025;
    p[6].pno=6;p[6].flag=0;p[6].addr=212;
    p[7].pno=7;p[7].flag=0;p[7].addr=213;
     printf("ttt--------------------------------n");
     printf("ttt☆☆欢迎使用分页模拟实验系统☆☆n");
     printf("ttt---------------------------------n");
     printf("ttt☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆n");
     printf("ttt☆☆1.输入指令              ☆☆n");
     printf("ttt☆☆------------------------☆☆n");
     printf("ttt☆☆2.进入页面置换算法      ☆☆n");
     printf("ttt☆☆------------------------☆☆n");
     printf("ttt☆☆0.EXIT                  ☆☆n");
     printf("ttt☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆n");
 while(a!=0)
 {
    cout<<endl<<"请输入您的选择:";
     cin>>a;

    cout<<"页号"<<"标记位"<<"外存地址"<<"主存号"<<endl;
     for(int i=0;i<8;i++)
     {
         cout<<p[i].pno<<"t"<<p[i].flag<<"t"<<p[i].addr<<"t";
         if(p[i].flag)
         cout<<p[i].cno;
         cout<<endl;
    }

 switch(a)
 {
     case 0:printf("ttt再见!tttn"); break;
     case 1:
         cout<<"请输入指令的逻辑地址:";
         cin>>ins;
         changeaddr(p, ins);break;
     case 2: system("CLS"); a=wang();break;
     default:cout<<"输入有误,请重新输入!"<<endl;break;
    }
}
}

 void menu()
 {
 int a;
     printf("ttt--------------------------------n");
     printf("ttt☆☆欢迎使用分页模拟实验系统☆☆n");
     printf("ttt---------------------------------n");
     printf("ttt☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆n");
     printf("ttt☆☆1.输入指令              ☆☆n");
     printf("ttt☆☆------------------------☆☆n");
     printf("ttt☆☆2.进入页面置换算法      ☆☆n");
     printf("ttt☆☆------------------------☆☆n");
     printf("ttt☆☆0.EXIT                  ☆☆n");
     printf("ttt☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆n");
     printf("请选择所要执行的操作:");
     scanf("%d",&a);
     switch(a)
     {
     case 0: printf("ttt-再见!-tttn");break;
     case 1: dizhizhuanhuan (); break;
     case 2: wang (); break;
     default:cout<<"输入有误,请重新输入!"<<endl;break;
    }
}
int main()
 {
     menu();
}

//****************随机产生序列号函数
 int* build()
 {
     printf("随机产生一个进程序列号为:n");
     int i=0;
     for(i=0; i<psize; i++)
     {
         pro[i]=10*rand()/(RAND_MAX+1)+1;
         printf("%d ", pro[i]);
}
     printf("n");
     return(pro);
}

//***************************************查找空闲物理块
 int searchpb()
 {
     for (j=0;j<bsize; j++)
     {
         if(phb[j] == 0)
         {
               m=j;
             return m;
             break;
        }
    }
     return -1;
}
//************************************查找相同进程
 int searchpro()
 {
     for(j=0;j< bsize;j++)
     {
         if(phb[j] =pro[i])
         {
             n=j;
             return j;
        }
    }
 return -1;
}

//*************************初始化内存
void empty()
 {
     for(i=0;i<bsize;i++)
         phb[i]=0;
     count=0;   //计数器置零
}   //******先进先出页面置换算法
 void FIFO()
{
     for( i=0; i<psize; i++)
     {
//     m=searchpb();
//     n=searchpro();
        //找到第一个空闲的物理快
        for(j=0;j<bsize;j++) {
            if(phb[j] == 0){
                m=j;
                break;
            }
        }
        //找与进程相同的标号
        for(j=0;j<bsize;j++) {
            if(phb[j] == pro[i]){
                n=j;
            }
        }

 //找flag值最大的
     for(j=0;j<bsize;j++)
    {
         if(flag[j]>maxflag)
         {
             maxflag = flag[j];
             mmax = j;
        }
    }

    if(n == -1)//不存在相同进程
    {
        if(m != -1)//存在空闲物理块
        {
            phb[m]=pro[i];//进程号填入该空闲物理块
//             count++;
             flag[m]=0;
             for (j=0;j<=m; j++)
             {
                 flag[j]++;
            }
            m=-1;
        }
         else//不存在空闲物理块
         {
             phb[mmax] =pro[i];
             flag[mmax] =0;
             for (j=0;j<bsize;j++)
            {
                 flag[j]++;
            }
             mmax = -1;
             maxflag = 0;
             count++;
        }
    }
    else//存在相同的进程
    {
         phb[n] = pro[i];
         for(j=0;j<bsize;j++)
        {
             flag[j]++;
        }
        n=-1;
    }
     for(j=0;j < bsize;j++)
     {
        printf("%d ", phb[j]);
    }
         printf("n");
    }
     printf("缺页次数为:%dn",count);
     printf("缺页率 :%16. 6f",(float)count/psize);
     printf("n");
}
/*初始化内存单元、缓冲区*/
 void Init(Pagel *b,int c[bsize][psize])
 {
     int i,j;
     for (i=0;i<psize;i++)
     {
         b[i].num=-1;
         b[i].time=psize-i-1;
}
 for(i=0;i<bsize;i++)
     for(j=0;j<psize;j++)
        c[i][j]=-1;
}
/*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/
 int GetMax(Pagel *b)
 {
     int i;
     int max=-1;
     int tag=0;
     for(i=0;i<bsize;i++)
     {
         if(b[i].time>max)
         {
             max=b[i].time;
             tag= i;
        }
    }
     return tag;
}

/*判断页面是否已在内存中*/
 int Equation(int fold, Pagel *b)
 {
     int i;
    for(i=0;i<bsize;i++)
    {
         if(fold==b[i]. num)
             return i;
    }
     return -1;
}
/*LRU核心部分*/
 void Lruu(int fold, Pagel *b)
 {
     int i;
     int val;
     val=Equation(fold, b);
     if (val>=0)
     {
         b[val].time=0;
         for(i=0;i<bsize;i++)
             if (i!=val)
                 b[i].time++;
    }
     else
     {
         queue[++k]=fold;/*记录调入页面*/
         val=GetMax(b);
         b[val].num=fold;
         b[val].time=0;
         for (i=0;i<bsize;i++){

//         URLcount++;
             if (i!=val)
                 b[i].time++;
        }
    }
}

 void LRU()
 {
     int i,j;
     k=0;
     Init(b, c);
     for(i=0; i<psize; i++)
     {
         Lruu(pro[i],b);
         c[0][i]=pro[i];
        /*记录当前的内存单元中的页面*/
         for(j=0;j<bsize;j++)
            c[j][i]=b[j].num;
    }

    /*结果输出*/
     printf("内存状态为:n");
     Myprintf;
    for(j=0;j<psize;j++)
         printf("|%2d", pro[j]);
     printf("|n");
     Myprintf;

     for(i=0;i<bsize;i++)
     {
         for(j=0; j<psize; j++)
         {
             if(c[i][j]==-1)
                 printf("|%2c",32);
              else
                 printf("|%2d",c[i][j]);
        }
         printf("|n");
    }

     Myprintf;
//     printf("n调入队列为:");
//    for(i=0;i<k;i++)
//        printf("%3d", queue[i]);

    printf("n缺页次数为:%6dn   缺页率 :%16. 6f", k+1,(float)(k+1)/psize);
}

//********主函数
 int wang()
 {
     int sel;
     do{
     printf("ttt--------------------------------n");
     printf("ttt☆☆欢迎使用分页模拟实验系统☆☆n");
     printf("ttt---------------------------------n");
     printf("ttt☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆n");
     printf("ttt☆☆       虚拟内存         ☆☆n");
     printf("ttt☆☆------------------------☆☆n");
     printf("ttt☆☆1.产生随机序列          ☆☆n");
     printf("ttt☆☆------------------------☆☆n");
     printf("ttt☆☆2.最近最久未使用        ☆☆n");
     printf("ttt☆☆------------------------☆☆n");
     printf("ttt☆☆3.先进先出              ☆☆n");
     printf("ttt☆☆------------------------☆☆n");
     printf("ttt☆☆0.退出                  ☆☆n");
     printf("ttt☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆n");
     printf("请选择所要执行的操作:");
     scanf("%d",&sel);
     switch(sel)
    {
         case 0: printf("ttt再见!tttn"); break;
         case 1: build(); break;
         case 2: printf("最近最久未使用n"); LRU();empty(); printf("n");break;
         case 3: printf("先进先出算法n"); FIFO();empty();printf("n");break;
         default:printf("请输入正确的选项号!");printf("nn");break;
    }
}while(sel !=0 );
     return sel;
}