基于C++的请求分页虚拟页面替换算法

Galaxy

发布日期: 2018-11-03 00:07:19 浏览量: 463
评分:
star star star star star star star star star_border star_border
*转载请注明来自write-bug.com

一、需求分析

实现OPT、FIFO、LRU、Clock等页面替换算法。接收用户输入参数,包括程序长度(页面数)、页框个数及页面大小,输出结果采用不同颜色区分命中、替换及直接加入空闲块。

  • OPT(最佳置换算法):其所选择的被淘汰页面将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面,但是由于无法预知一个进程在内存中的若干个页面中,哪一个页面是未来最长时间内不被访问的,因而该算法无法实现

  • FIFO(先进先出页面是换算法):该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰

  • LRU(最近最久未使用置换算法):只能利用“最近的过去”作为“最近的将来”的近似,因此,LRU置换算法是选择最近最久未使用的页面予以淘汰

  • Clock:使用的较多的一种LRU近似算法

二、概要设计

  • FIFO算法:在该模拟系统中,使用队列来存储页面并且按照其到达队列的先后顺序进行排序,因此,每次需要进行页面替换时,便选择队首或者标识符指示其驻留时间最长的页面进行替换

  • LRU算法:同样使用数组队列来模拟,数组下标指示位置,而数组值则作为标识符来计算该页面自最后一次被访问到现在为止经历了多长时间,当选择被置换的页面时,则扫描该数组队列,找到标识符最大的页面进行替换

  • Clock算法:同样使用数组队列来模拟,数组下标指示内存位置,而数组值则作为标识符在替换过程中发挥作用。当选择被替换的页面时,则扫描该数组队列,检查数组值,若值为0,则进行替换;若数组值为1,则将数组值置为1,继续扫描下一个数组值。若扫描完毕没有合适的页面进行替换时,则对数组进行第二次扫描

三、详细设计

3.1 设计思想

  • FIFO算法:先进先出思想,即选择在内存中驻留时间最久的页面给予淘汰

  • LRU算法:根据页面调入内存后的使用情况作出决策,选择最近最久未使用耳朵页面予以淘汰

  • Clock算法:设置访问位,循环检查各页面使用情况,是一种LRU近似算法

3.2 模块设计

  • 输入子模块:接收用户的输入,用户的输入共有程序长度(页面数)、页框个数及页面大小三种

  • 模拟页面置换子模块:该模块共有三种函数,分别模拟FIFO算法,LRU算法,Clock算法

FIFO算法描述

  1. void fifo(int pageNum,int pageFrameNum,int size)
  2. {
  3. int m[pageFrameNum];
  4. for(int i = 0 ; i < pageFrameNum ; i++)
  5. m[i] = 0;
  6. //模拟页面访问
  7. for(int i = 0 ; i < pageNum; i++)
  8. {
  9. for(int k = 0; ; k++)
  10. {
  11. for(int j = 0 ; j < pageFrameNum ; j++)
  12. {
  13. if(m[j] == k)
  14. {
  15. m[j] = k+1;
  16. for(int h = 0 ; h < pageFrameNum ; h++)
  17. {
  18. if(m[h] == 0)
  19. cout << "# ";
  20. else
  21. {
  22. if(k == 0)
  23. {
  24. if(h!=j)
  25. cout << "% ";
  26. else
  27. cout << "+ ";
  28. }
  29. else
  30. {
  31. if(h!=j)
  32. cout << "% ";
  33. else
  34. cout << "t ";
  35. }
  36. }
  37. }
  38. cout << endl;
  39. k = -1;
  40. break;
  41. }
  42. }
  43. if(k < 0 )
  44. break;
  45. }
  46. }
  47. }

LRU算法描述

  1. void lru(int pageNum,int pageFrameNum,int size)
  2. {
  3. int m[pageFrameNum];
  4. for(int i = 0 ; i < pageFrameNum ; i++)
  5. {
  6. m[i] = 0;
  7. }
  8. for(int i = 0 ; i < pageNum; i++)
  9. {
  10. int j;
  11. for(j = 0; j < pageFrameNum; j++)
  12. {
  13. if(m[j] == 0)
  14. {
  15. m[j] = 1;
  16. for(int k = 0 ; k < pageFrameNum; k++)
  17. {
  18. if(m[k] == 0)
  19. cout << "# ";
  20. else
  21. {
  22. if(k != j)
  23. cout << "% ";
  24. else
  25. cout << "+ ";
  26. }
  27. }
  28. cout << endl;
  29. break;
  30. }
  31. }
  32. if(j > pageFrameNum-1)
  33. {
  34. int max = 0,tmp;
  35. for(int d = 0; d < pageFrameNum; d++)
  36. {
  37. if(m[d] > max)
  38. {
  39. max = m[d];
  40. tmp = d; //该位置页面被替换
  41. }
  42. }
  43. m[tmp] = 1;
  44. for(int f = 0; f < pageFrameNum; f++)
  45. {
  46. if(f != tmp)
  47. cout << "% ";
  48. else
  49. cout << "t ";
  50. }
  51. cout << endl;
  52. }
  53. //模拟页面访问过程
  54. while(true)
  55. {
  56. int tmp = rand()%(pageFrameNum+1);
  57. if(m[tmp] > 0)
  58. {
  59. for(int t = 0; t < pageFrameNum; t++)
  60. {
  61. if(m[t] > 0)
  62. m[t]++;
  63. }
  64. m[tmp] = 1;
  65. }
  66. break;
  67. }
  68. }
  69. }

Clock算法描述

  1. void clock(int pageNum,int pageFrameNum,int size)
  2. {
  3. int m[pageFrameNum];
  4. for(int i = 0 ; i < pageFrameNum ; i++)
  5. {
  6. m[i] = -1;
  7. }
  8. for(int i = 0 ; i < pageNum; i++)
  9. {
  10. int j;
  11. for(j = 0; j < pageFrameNum; j++)
  12. {
  13. if(m[j] == -1)
  14. {
  15. m[j] = 1;
  16. for(int k = 0 ; k < pageFrameNum; k++)
  17. {
  18. if(m[k] == -1)
  19. cout << "# ";
  20. else
  21. {
  22. if(k != j)
  23. cout << "% ";
  24. else
  25. cout << "+ ";
  26. }
  27. }
  28. cout << endl;
  29. break;
  30. }
  31. }
  32. if(j > pageFrameNum-1)
  33. {
  34. int flag = 0,tmp;
  35. for(int d = 0; d < pageFrameNum; d++)
  36. {
  37. if(m[d] == 0)
  38. {
  39. m[d] = 1;
  40. tmp = d;
  41. flag = 1;
  42. break;
  43. }
  44. else
  45. {
  46. m[d] = 0;
  47. }
  48. }
  49. if(flag == 0)
  50. {
  51. for(int d = 0; d < pageFrameNum; d++)
  52. {
  53. if(m[d] == 0)
  54. {
  55. m[d] = 1;
  56. break;
  57. }
  58. }
  59. }
  60. for(int f = 0; f < pageFrameNum; f++)
  61. {
  62. if(f != tmp)
  63. cout << "% ";
  64. else
  65. cout << "t ";
  66. }
  67. cout << endl;
  68. }
  69. //模拟页面访问过程
  70. while(true)
  71. {
  72. int tmp = rand()%(pageFrameNum+1);
  73. if(m[tmp] == 0)
  74. {
  75. m[tmp] = 1;
  76. }
  77. break;
  78. }
  79. }
  80. }

输出子模块:输出页面置换后的内存调用结果,其中输出符号表示:

  • t:替换

  • +:直接加入空闲区

  • #:页框空闲

  • %:页框不空闲

四、调试分析

输入程序长度(页面数)、页框个数、页面大小分别为20,10,2,三种算法输出结果如下(其中t表示替换,+表示直接加入空闲区,#表示页框空闲,%表示页框不空闲)。

FIFO算法

LRU算法

Clock算法

五、用户使用说明

该模拟系统为 C++ 语言模拟系统,请在 Codeblocks 等 C++ 编辑程序中打开编译运行,并根据提示进行输入。

上传的附件 cloud_download 基于C++的请求分页虚拟页面替换算法.zip ( 58.01kb, 6次下载 )
error_outline 下载需要6点积分

keyboard_arrow_left上一篇 : 基于JAVA的进程调度算法 基于C++的类UNIX文件系统 : 下一篇keyboard_arrow_right



Galaxy
2018-11-03 00:08:09
基于C++的请求分页虚拟页面替换算法,三种算法,操作系统课设必备

发送私信

人生如下棋,必有远见方能获胜

6
文章数
9
评论数
最近文章
eject