页面置换算法的模拟实现 C
- 1 #include <stdio.h>
- 2 #include <stdlib.h>
- 3
- 4 /*全局变量*/
- 5 int mSIZE; /*物理块数*/
- 6 int pSIZE; /*页面号引用串个数*/
- 7 static int memery[10]={0}; /*物理块中的页号*/
- 8 static int page[100]={0}; /*页面号引用串*/
- 9 static int temp[100][10]={0}; /*辅助数组*/
- 10
- 11 /*置换算法函数*/
- 12 void FIFO();
- 13 void LRU();
- 14 void OPT();
- 15
- 16 /*辅助函数*/
- 17 void print(unsigned int t);
- 18 void designBy();
- 19 void download();
- 20 void mDelay(unsigned int Delay);
- 21
- 22 /*主函数*/
- 23 int main()
- 24 {
- 25 int i,k,code;
- 26 // system("color 0E");
- 27 designBy();
- 28 printf("按任意键开启功能");
- 29 // printf(" >>>");
- 30 getchar();
- 31 system("cls");
- 32 // system("color 0E");
- 33
- 34
- 35 printf("请输入引用串的个数(M<=10)：");
- 36 scanf("%d",&pSIZE);
- 37 printf("请输入物理块的个数(M<=10)：");
- 38 scanf("%d",&mSIZE);
- 39 puts("请依次输入页面号引用串(连续输入，无需隔开)：");
- 40 for(i=0;i<pSIZE;i++)
- 41 scanf("%1d",&page[i]);
- 42 download();
- 43 system("cls");
- 44 // system("color 0E");
- 45 do{
- 46 puts("输入的页面号引用串为：");
- 47 for(k=0;k<=(pSIZE-1)/20;k++)
- 48 {
- 49 for(i=20*k;(i<pSIZE)&&(i<20*(k+1));i++)
- 50 {
- 51 if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))
- 52 printf("%d\n",page[i]);
- 53 else
- 54 printf("%d ",page[i]);
- 55 }
- 56 }
- 57 printf("* * * * * * * * * * * * * * * * * * * * * * *\n");
- 58 printf("* 请选择页面置换算法：\t\t\t *\n");
- 59 printf("* ----------------------------------------- *\n");
- 60 printf("* 1.先进先出(FIFO) 2.最近最久未使用(LRU) *\n");
- 61 printf("* 3.最佳(OPT) 4.退出 *\n");
- 62 printf("* * * * * * * * * * * * * * * * * * * * * * *\n");
- 63 printf("请选择操作：[ ]\b\b");
- 64 scanf("%d",&code);
- 65 switch(code)
- 66 {
- 67 case 1:
- 68 FIFO();
- 69 break;
- 70 case 2:
- 71 LRU();
- 72 break;
- 73 case 3:
- 74 OPT();
- 75 break;
- 76 case 4:
- 77 system("cls");
- 78 // system("color 0C");
- 79 designBy(); /*显示设计者信息后退出*/
- 80 printf("谢谢使用页面置换算法演示器! \n");
- 81 exit(0);
- 82 default:
- 83 printf("输入错误，请重新输入：");
- 84 }
- 85 printf("按任意键重新选择置换算法：>>>");
- 86 getchar();
- 87 system("cls");
- 88 }while (code!=4);
- 89 getchar();
- 90 }
- 91
- 92 /*载入数据*/
- 93 void download()
- 94 {
- 95 int i;
- 96 system("color 0B");
- 97 printf("正在载入数据，请稍候 !!!\n");
- 98 printf("Loading...\n");
- 99 printf(" O");
- 100 for(i=0;i<51;i++)
- 101 printf("\b");
- 102 for(i=0;i<50;i++)
- 103 {
- 104 mDelay((pSIZE+mSIZE)/2);
- 105 printf(">");
- 106 }
- 107 printf("\nFinish.\n载入成功，按任意键进入置换算法选择界面：>>>");
- 108 getchar();
- 109 }
- 110
- 111 /*设置延迟*/
- 112 void mDelay(unsigned int Delay)
- 113 {
- 114 unsigned int i;
- 115 for(;Delay>0;Delay--)
- 116 {
- 117 for(i=0;i<124;i++)
- 118 {
- 119 printf(" \b");
- 120 }
- 121 }
- 122 }
- 123
- 124 /*显示设计者信息*/
- 125 void designBy()
- 126 {
- 127
- 128 printf(" 课题：页面置换算法的模拟实现 \n");
- 129 printf(" 学号：1610704202 \n");
- 130 printf(" 姓名：xxx \n");
- 131 }
- 132
- 133
- 134 void print(unsigned int t)
- 135 {
- 136 int i,j,k,l;
- 137 int flag;
- 138 for(k=0;k<=(pSIZE-1)/20;k++)
- 139 {
- 140 for(i=20*k;(i<pSIZE)&&(i<20*(k+1));i++)
- 141 {
- 142 if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))
- 143 printf("%d\n",page[i]);
- 144 else
- 145 printf("%d ",page[i]);
- 146 }
- 147 for(j=0;j<mSIZE;j++)
- 148 {
- 149 for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i++)
- 150 {
- 151 if(i>=j)
- 152 printf(" |%d|",temp[i][j]);
- 153 else
- 154 printf(" | |");
- 155 }
- 156 for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1));i++)
- 157 {
- 158 for(flag=0,l=0;l<mSIZE;l++)
- 159 if(temp[i][l]==temp[i-1][l])
- 160 flag++;
- 161 if(flag==mSIZE)/*页面在物理块中*/
- 162 printf(" ");
- 163 else
- 164 printf(" |%d|",temp[i][j]);
- 165 }/*每行显示20个*/
- 166 if(i%20==0)
- 167 continue;
- 168 printf("\n");
- 169 }
- 170 }
- 171
- 172 printf("----------------------------------------\n");
- 173 printf("缺页次数：%d\t\t",t+mSIZE);
- 174 printf("缺页率：%d/%d\n",t+mSIZE,pSIZE);
- 175 printf("置换次数：%d\t\t",t);
- 176 printf("访问命中率：%d%%\n",(pSIZE-(t+mSIZE))*100/pSIZE);
- 177 printf("----------------------------------------\n");
- 178 }
- 179
- 180 /*计算过程延迟*/
- 181 void compute()
- 182 {
- 183 int i;
- 184 printf("正在进行相关计算，请稍候");
- 185 for(i=1;i<20;i++)
- 186 {
- 187 mDelay(15);
- 188 if(i%4==0)
- 189 printf("\b\b\b\b\b\b \b\b\b\b\b\b");
- 190 else
- 191 printf("Θ");
- 192 }
- 193 for(i=0;i++<30;printf("\b"));
- 194 for(i=0;i++<30;printf(" "));
- 195 for(i=0;i++<30;printf("\b"));
- 196 }
- 197 /*先进先出页面置换算法*/
- 198 void FIFO()
- 199 {
- 200 int memery[10]={0};
- 201 int time[10]={0}; /*记录进入物理块的时间*/
- 202 int i,j,k,m;
- 203 int max=0; /*记录换出页*/
- 204 int count=0; /*记录置换次数*/
- 205 /*前mSIZE个数直接放入*/
- 206 for(i=0;i<mSIZE;i++)
- 207 {
- 208 memery[i]=page[i];
- 209 time[i]=i;
- 210 for(j=0;j<mSIZE;j++)
- 211 temp[i][j]=memery[j];
- 212 }
- 213 for(i=mSIZE;i<pSIZE;i++)
- 214 {
- 215 /*判断新页面号是否在物理块中*/
- 216 for(j=0,k=0;j<mSIZE;j++)
- 217 {
- 218 if(memery[j]!=page[i])
- 219 k++;
- 220 }
- 221 if(k==mSIZE) /*如果不在物理块中*/
- 222 {
- 223 count++;/*计算换出页*/
- 224 max=time[0]<time[1]?0:1;
- 225 for(m=2;m<mSIZE;m++)
- 226 if(time[m]<time[max])
- 227 max=m;
- 228 memery[max]=page[i];
- 229 time[max]=i; /*记录该页进入物理块的时间*/
- 230 for(j=0;j<mSIZE;j++)
- 231 temp[i][j]=memery[j];
- 232 }
- 233 else
- 234 {
- 235 for(j=0;j<mSIZE;j++)
- 236 temp[i][j]=memery[j];
- 237 }
- 238 }
- 239 compute();
- 240 print(count);
- 241 getchar();
- 242 }
- 243 /*最近最久未使用置换算法*/
- 244 void LRU()
- 245 {
- 246 int memery[10]={0};
- 247 int flag[10]={0}; /*记录页面的访问时间*/
- 248 int i,j,k,m;
- 249 int max=0; /*记录换出页*/
- 250 int count=0; /*记录置换次数*/
- 251 /*前mSIZE个数直接放入*/
- 252 for(i=0;i<mSIZE;i++)
- 253 {
- 254 memery[i]=page[i];
- 255 flag[i]=i;
- 256 for(j=0;j<mSIZE;j++)
- 257 temp[i][j]=memery[j];
- 258 }
- 259 for(i=mSIZE;i<pSIZE;i++)
- 260 {
- 261 /*判断新页面号是否在物理块中*/
- 262 for(j=0,k=0;j<mSIZE;j++)
- 263 {
- 264 if(memery[j]!=page[i])
- 265 k++;
- 266 else
- 267 flag[j]=i; /*刷新该页的访问时间*/
- 268 }
- 269 if(k==mSIZE) /*如果不在物理块中*/
- 270 {
- 271 count++;
- 272 /*计算换出页*/
- 273 max=flag[0]<flag[1]?0:1;
- 274 for(m=2;m<mSIZE;m++)
- 275 if(flag[m]<flag[max])
- 276 max=m;
- 277 memery[max]=page[i];
- 278 flag[max]=i; /*记录该页的访问时间*/
- 279 for(j=0;j<mSIZE;j++)
- 280 temp[i][j]=memery[j];
- 281 }
- 282 else
- 283 {
- 284 for(j=0;j<mSIZE;j++)
- 285 temp[i][j]=memery[j];
- 286 }
- 287 }
- 288 compute();
- 289 print(count);
- 290 getchar();
- 291 }
- 292 /*最佳置换算法*/
- 293 void OPT()
- 294 {
- 295 int memery[10]={0};
- 296 int next[10]={0}; /*记录下一次访问时间*/
- 297 int i,j,k,l,m;
- 298 int max; /*记录换出页*/
- 299 int count=0; /*记录置换次数*/
- 300 /*前mSIZE个数直接放入*/
- 301 for(i=0;i<mSIZE;i++)
- 302 {
- 303 memery[i]=page[i];
- 304 for(j=0;j<mSIZE;j++)
- 305 temp[i][j]=memery[j];
- 306 }
- 307 for(i=mSIZE;i<pSIZE;i++)
- 308 {
- 309 /*判断新页面号是否在物理块中*/
- 310 for(j=0,k=0;j<mSIZE;j++)
- 311 {
- 312 if(memery[j]!=page[i])
- 313 k++;
- 314 }
- 315 if(k==mSIZE) /*如果不在物理块中*/
- 316 {
- 317 count++;
- 318 /*得到物理快中各页下一次访问时间*/
- 319 for(m=0;m<mSIZE;m++)
- 320 {
- 321 for(l=i+1;l<pSIZE;l++)
- 322 if(memery[m]==page[l])
- 323 break;
- 324 next[m]=l;
- 325 }
- 326 /*计算换出页*/
- 327 max=next[0]>=next[1]?0:1;
- 328 for(m=2;m<mSIZE;m++)
- 329 if(next[m]>next[max])
- 330 max=m;
- 331 /*下一次访问时间都为pSIZE,则置换物理块中第一个*/
- 332 memery[max]=page[i];
- 333 for(j=0;j<mSIZE;j++)
- 334 temp[i][j]=memery[j];
- 335 }
- 336 else {
- 337 for(j=0;j<mSIZE;j++)
- 338 temp[i][j]=memery[j];
- 339 }
- 340 }
- 341 compute();
- 342 print(count);
- 343 getchar();
- 344 }
页面置换算法的模拟实现
版权声明：本文为Catherinezhilin原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。