页面置换算法的模拟实现 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 }