经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C 语言 » 查看文章
先进先出(FIFO)页面置换算法C语言实现、最近最久未使用(LRU)页面置换算法C语言实现
来源:cnblogs  作者:S_MIL  时间:2021/12/15 9:05:44  对本文有异议

1.实现效果

 

 2.实现源代码

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

 

 

原文链接:http://www.cnblogs.com/SMIL/p/15675161.html

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号