- 1 #include<iostream>
- 2 #include<process.h>
- 3 #include<stdlib.h>
- 4 #include<ctime>
- 5 #include<conio.h>
- 6 #include<stdio.h>
- 7 #include<string.h>
- 8 using namespace std;
- 9
- 10 #define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")/*表格控制*/
- 11 #define bsize 4 //物理块大小
- 12 #define psize 16 //进程大小
- 13 void chushihua();//初始化函数
- 14 void ymzh();
- 15 void yemianzhihuan ();
- 16 void changeaddr(struct Page p[], int logaddr);
- 17 void dizhizhuanhuan();
- 18 void menu();
- 19 int wang();
- 20
- 21 int yemianliu[32]={0};//全局变量数组,地址流
- 22 int p;
- 23 struct Page {
- 24 int pno;//页号
- 25 int flag;//标志位
- 26 int cno;//主存号
- 27 int modf;//修改位
- 28 int addr;//外存地址
- 29 }Page; //全局变量p是一共有多少地址流
- 30
- 31 typedef struct pagel
- 32 {
- 33 int num; /*记录页面号*/
- 34 int time; /*记录调入内存时间*/
- 35 }Pagel; /*页面逻辑结构,方便算法实现*/
- 36
- 37 Pagel b[bsize]; /*内存单元数*/
- 38 int c[bsize][psize];/*保存内存当前的状态:缓冲区*/
- 39 int queue[100];/*记录调入队列*/
- 40 int k;/*调入队列计数变量*/
- 41 int phb[bsize]={0};//物理块标号
- 42 int pro[psize]={0};//进程序列号
- 43 int flag[bsize]={0};//进程等待次数(存放最久未被使用的进程标志)*/
- 44 int i=0,j=0;//i表示进程序列号,j表示物理块号*/
- 45 int m =-1,n =-1;//物理块空闲和进程是否相同判断标志*/
- 46 int mmax=-1, maxflag=0;//标记替换物理块进程下标*/
- 47 int count =0; //统计页面缺页次数
- 48
- 49 void chushihua() //初始化函数
- 50 {
- 51 int t;
- 52 srand(time(0));//随机产生指令序列
- 53 p=12+rand()%32;
- 54 cout<<"地址流序列:";
- 55 cout<<endl;
- 56 for(i=0; i<p; i++)
- 57 {
- 58 t=1+rand()%9;
- 59 yemianliu[i]=t;//将随机产生的指令数存入页面流
- 60 }
- 61 for (i=p-1;i>=0;i--)
- 62 {
- 63 cout<<yemianliu[i]<<" ";
- 64 }
- 65 cout<<endl;
- 66 }
- 67 void ymzh()
- 68 {
- 69 chushihua();
- 70 yemianzhihuan();
- 71 }
- 72
- 73 void yemianzhihuan()
- 74 {
- 75 int a;
- 76 printf("----------------------------------\n");
- 77 printf("☆☆欢迎使用分页模拟实验系统☆☆\n");
- 78 printf("----------------------------------");
- 79 printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
- 80 printf("☆☆1.进入硬件地址变换算法 ☆☆\n");
- 81 printf("☆☆------------------------☆☆\n");
- 82 printf("☆☆2.进入页面置换算法 ☆☆\n");
- 83 printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
- 84 printf("请输入您的选择:");
- 85 switch(a)
- 86 {
- 87 case 1:
- 88 ymzh();
- 89 break;
- 90 case 2:
- 91 wang();
- 92 break;
- 93 default:
- 94 cout<<"输入有误,请重新输入!"<<endl;
- 95 break;
- 96 }
- 97 }
- 98
- 99 void changeaddr(struct Page p[], int logaddr){//地址变换
- 100 int j=logaddr/64;//对应的块号
- 101 int k=logaddr%64; //对应的偏移量
- 102 int flag=0;
- 103 int addr;
- 104 for(int i=0;i<8;i++)
- 105 {
- 106 if(p[i].pno==j)//找到对应的页号
- 107 {
- 108 if(p[i].flag==1)//页面标志为1
- 109 {
- 110 addr=p[i].cno*64+k;
- 111 cout<<"物理地址为:"<<addr<<endl;
- 112 cout<<"详细信息:"<<"\t页面号:"<<p[i].pno<<"\t 主存号:"<<p[i].cno<<"\t偏移量:"<<k<<endl;
- 113 flag=1;
- 114 break;
- 115 }
- 116 }
- 117 }
- 118
- 119 if(flag==0)
- 120 cout<<"该页不在主存,产生缺页中断"<<endl;
- 121 }
- 122
- 123 void dizhizhuanhuan()
- 124 {
- 125 int a;
- 126 int ins;//指令逻辑地址
- 127 struct Page p[8];
- 128 p[0].pno=0;p[0].flag=1;p[0].cno=5;p[0].modf=1;p[0].addr=011;
- 129 p[1].pno=1;p[1].flag=1;p[1].cno=8;p[1].modf=1;p[1].addr=012;
- 130 p[2].pno=2;p[2].flag=1;p[2].cno=9;p[2].modf=0;p[2].addr=013;
- 131 p[3].pno=3;p[3].flag=1;p[3].cno=10;p[3].modf=0;p[3].addr=015;
- 132 p[4].pno=4;p[4].flag=0;p[4].addr=017;
- 133 p[5].pno=5;p[5].flag=0;p[5].addr=025;
- 134 p[6].pno=6;p[6].flag=0;p[6].addr=212;
- 135 p[7].pno=7;p[7].flag=0;p[7].addr=213;
- 136 printf("\t\t\t--------------------------------\n");
- 137 printf("\t\t\t☆☆欢迎使用分页模拟实验系统☆☆\n");
- 138 printf("\t\t\t---------------------------------\n");
- 139 printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
- 140 printf("\t\t\t☆☆1.输入指令 ☆☆\n");
- 141 printf("\t\t\t☆☆------------------------☆☆\n");
- 142 printf("\t\t\t☆☆2.进入页面置换算法 ☆☆\n");
- 143 printf("\t\t\t☆☆------------------------☆☆\n");
- 144 printf("\t\t\t☆☆0.EXIT ☆☆\n");
- 145 printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
- 146 while(a!=0)
- 147 {
- 148 cout<<endl<<"请输入您的选择:";
- 149 cin>>a;
- 150
- 151 cout<<"页号"<<"标记位"<<"外存地址"<<"主存号"<<endl;
- 152 for(int i=0;i<8;i++)
- 153 {
- 154 cout<<p[i].pno<<"\t"<<p[i].flag<<"\t"<<p[i].addr<<"\t";
- 155 if(p[i].flag)
- 156 cout<<p[i].cno;
- 157 cout<<endl;
- 158 }
- 159
- 160 switch(a)
- 161 {
- 162 case 0:printf("\t\t\t再见!\t\t\t\n"); break;
- 163 case 1:
- 164 cout<<"请输入指令的逻辑地址:";
- 165 cin>>ins;
- 166 changeaddr(p, ins);break;
- 167 case 2: system("CLS"); a=wang();break;
- 168 default:cout<<"输入有误,请重新输入!"<<endl;break;
- 169 }
- 170 }
- 171 }
- 172
- 173 void menu()
- 174 {
- 175 int a;
- 176 printf("\t\t\t--------------------------------\n");
- 177 printf("\t\t\t☆☆欢迎使用分页模拟实验系统☆☆\n");
- 178 printf("\t\t\t---------------------------------\n");
- 179 printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
- 180 printf("\t\t\t☆☆1.输入指令 ☆☆\n");
- 181 printf("\t\t\t☆☆------------------------☆☆\n");
- 182 printf("\t\t\t☆☆2.进入页面置换算法 ☆☆\n");
- 183 printf("\t\t\t☆☆------------------------☆☆\n");
- 184 printf("\t\t\t☆☆0.EXIT ☆☆\n");
- 185 printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
- 186 printf("请选择所要执行的操作:");
- 187 scanf("%d",&a);
- 188 switch(a)
- 189 {
- 190 case 0: printf("\t\t\t-再见!-\t\t\t\n");break;
- 191 case 1: dizhizhuanhuan (); break;
- 192 case 2: wang (); break;
- 193 default:cout<<"输入有误,请重新输入!"<<endl;break;
- 194 }
- 195 }
- 196 int main()
- 197 {
- 198 menu();
- 199 }
- 200
- 201 //****************随机产生序列号函数
- 202 int* build()
- 203 {
- 204 printf("随机产生一个进程序列号为:\n");
- 205 int i=0;
- 206 for(i=0; i<psize; i++)
- 207 {
- 208 pro[i]=10*rand()/(RAND_MAX+1)+1;
- 209 printf("%d ", pro[i]);
- 210 }
- 211 printf("\n");
- 212 return(pro);
- 213 }
- 214
- 215 //***************************************查找空闲物理块
- 216 int searchpb()
- 217 {
- 218 for (j=0;j<bsize; j++)
- 219 {
- 220 if(phb[j] == 0)
- 221 {
- 222 m=j;
- 223 return m;
- 224 break;
- 225 }
- 226 }
- 227 return -1;
- 228 }
- 229 //************************************查找相同进程
- 230 int searchpro()
- 231 {
- 232 for(j=0;j< bsize;j++)
- 233 {
- 234 if(phb[j] =pro[i])
- 235 {
- 236 n=j;
- 237 return j;
- 238 }
- 239 }
- 240 return -1;
- 241 }
- 242
- 243 //*************************初始化内存
- 244 void empty()
- 245 {
- 246 for(i=0;i<bsize;i++)
- 247 phb[i]=0;
- 248 count=0; //计数器置零
- 249 } //******先进先出页面置换算法
- 250 void FIFO()
- 251 {
- 252 for( i=0; i<psize; i++)
- 253 {
- 254 // m=searchpb();
- 255 // n=searchpro();
- 256 //找到第一个空闲的物理快
- 257 for(j=0;j<bsize;j++) {
- 258 if(phb[j] == 0){
- 259 m=j;
- 260 break;
- 261 }
- 262 }
- 263 //找与进程相同的标号
- 264 for(j=0;j<bsize;j++) {
- 265 if(phb[j] == pro[i]){
- 266 n=j;
- 267 }
- 268 }
- 269
- 270 //找flag值最大的
- 271 for(j=0;j<bsize;j++)
- 272 {
- 273 if(flag[j]>maxflag)
- 274 {
- 275 maxflag = flag[j];
- 276 mmax = j;
- 277 }
- 278 }
- 279
- 280 if(n == -1)//不存在相同进程
- 281 {
- 282 if(m != -1)//存在空闲物理块
- 283 {
- 284 phb[m]=pro[i];//进程号填入该空闲物理块
- 285 // count++;
- 286 flag[m]=0;
- 287 for (j=0;j<=m; j++)
- 288 {
- 289 flag[j]++;
- 290 }
- 291 m=-1;
- 292 }
- 293 else//不存在空闲物理块
- 294 {
- 295 phb[mmax] =pro[i];
- 296 flag[mmax] =0;
- 297 for (j=0;j<bsize;j++)
- 298 {
- 299 flag[j]++;
- 300 }
- 301 mmax = -1;
- 302 maxflag = 0;
- 303 count++;
- 304 }
- 305 }
- 306 else//存在相同的进程
- 307 {
- 308 phb[n] = pro[i];
- 309 for(j=0;j<bsize;j++)
- 310 {
- 311 flag[j]++;
- 312 }
- 313 n=-1;
- 314 }
- 315 for(j=0;j < bsize;j++)
- 316 {
- 317 printf("%d ", phb[j]);
- 318 }
- 319 printf("\n");
- 320 }
- 321 printf("缺页次数为:%d\n",count);
- 322 printf("缺页率 :%16. 6f",(float)count/psize);
- 323 printf("\n");
- 324 }
- 325 /*初始化内存单元、缓冲区*/
- 326 void Init(Pagel *b,int c[bsize][psize])
- 327 {
- 328 int i,j;
- 329 for (i=0;i<psize;i++)
- 330 {
- 331 b[i].num=-1;
- 332 b[i].time=psize-i-1;
- 333 }
- 334 for(i=0;i<bsize;i++)
- 335 for(j=0;j<psize;j++)
- 336 c[i][j]=-1;
- 337 }
- 338 /*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/
- 339 int GetMax(Pagel *b)
- 340 {
- 341 int i;
- 342 int max=-1;
- 343 int tag=0;
- 344 for(i=0;i<bsize;i++)
- 345 {
- 346 if(b[i].time>max)
- 347 {
- 348 max=b[i].time;
- 349 tag= i;
- 350 }
- 351 }
- 352 return tag;
- 353 }
- 354
- 355 /*判断页面是否已在内存中*/
- 356 int Equation(int fold, Pagel *b)
- 357 {
- 358 int i;
- 359 for(i=0;i<bsize;i++)
- 360 {
- 361 if(fold==b[i]. num)
- 362 return i;
- 363 }
- 364 return -1;
- 365 }
- 366 /*LRU核心部分*/
- 367 void Lruu(int fold, Pagel *b)
- 368 {
- 369 int i;
- 370 int val;
- 371 val=Equation(fold, b);
- 372 if (val>=0)
- 373 {
- 374 b[val].time=0;
- 375 for(i=0;i<bsize;i++)
- 376 if (i!=val)
- 377 b[i].time++;
- 378 }
- 379 else
- 380 {
- 381 queue[++k]=fold;/*记录调入页面*/
- 382 val=GetMax(b);
- 383 b[val].num=fold;
- 384 b[val].time=0;
- 385 for (i=0;i<bsize;i++){
- 386
- 387 // URLcount++;
- 388 if (i!=val)
- 389 b[i].time++;
- 390 }
- 391 }
- 392 }
- 393
- 394 void LRU()
- 395 {
- 396 int i,j;
- 397 k=0;
- 398 Init(b, c);
- 399 for(i=0; i<psize; i++)
- 400 {
- 401 Lruu(pro[i],b);
- 402 c[0][i]=pro[i];
- 403 /*记录当前的内存单元中的页面*/
- 404 for(j=0;j<bsize;j++)
- 405 c[j][i]=b[j].num;
- 406 }
- 407
- 408 /*结果输出*/
- 409 printf("内存状态为:\n");
- 410 Myprintf;
- 411 for(j=0;j<psize;j++)
- 412 printf("|%2d", pro[j]);
- 413 printf("|\n");
- 414 Myprintf;
- 415
- 416 for(i=0;i<bsize;i++)
- 417 {
- 418 for(j=0; j<psize; j++)
- 419 {
- 420 if(c[i][j]==-1)
- 421 printf("|%2c",32);
- 422 else
- 423 printf("|%2d",c[i][j]);
- 424 }
- 425 printf("|\n");
- 426 }
- 427
- 428 Myprintf;
- 429 // printf("\n调入队列为:");
- 430 // for(i=0;i<k;i++)
- 431 // printf("%3d", queue[i]);
- 432
- 433 printf("\n缺页次数为:%6d\n 缺页率 :%16. 6f", k+1,(float)(k+1)/psize);
- 434 }
- 435
- 436 //********主函数
- 437 int wang()
- 438 {
- 439 int sel;
- 440 do{
- 441 printf("\t\t\t--------------------------------\n");
- 442 printf("\t\t\t☆☆欢迎使用分页模拟实验系统☆☆\n");
- 443 printf("\t\t\t---------------------------------\n");
- 444 printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
- 445 printf("\t\t\t☆☆ 虚拟内存 ☆☆\n");
- 446 printf("\t\t\t☆☆------------------------☆☆\n");
- 447 printf("\t\t\t☆☆1.产生随机序列 ☆☆\n");
- 448 printf("\t\t\t☆☆------------------------☆☆\n");
- 449 printf("\t\t\t☆☆2.最近最久未使用 ☆☆\n");
- 450 printf("\t\t\t☆☆------------------------☆☆\n");
- 451 printf("\t\t\t☆☆3.先进先出 ☆☆\n");
- 452 printf("\t\t\t☆☆------------------------☆☆\n");
- 453 printf("\t\t\t☆☆0.退出 ☆☆\n");
- 454 printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
- 455 printf("请选择所要执行的操作:");
- 456 scanf("%d",&sel);
- 457 switch(sel)
- 458 {
- 459 case 0: printf("\t\t\t再见!t\t\t\n"); break;
- 460 case 1: build(); break;
- 461 case 2: printf("最近最久未使用\n"); LRU();empty(); printf("\n");break;
- 462 case 3: printf("先进先出算法\n"); FIFO();empty();printf("\n");break;
- 463 default:printf("请输入正确的选项号!");printf("\n\n");break;
- 464 }
- 465 }while(sel !=0 );
- 466 return sel;
- 467 }