分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，也同样为它们加以编号，如0#块、1#块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。虚拟内存的作用内存在计算机中的作用很大，电脑中所有运行的程序都需要经过内存来执行，如果执行的程序很大或很多，就会导致内存消耗殆尽。为了解决这个问题，Windows中运用了虚拟内存技术，即拿出一部分硬盘空间来充当内存使用，当内存占用完时，电脑就会自动调用硬盘来充当内存，以缓解内存的紧张。请求分页虚拟存储系统是将作业信息的副本存放在磁盘这一类辅助存储器中，当作业被调度投入运行时，并不把作业的程序和数据全部装入主存，而仅仅装入立即使用的那些页面，至少要将作业的第一页信息装入主存，在执行过程中访问到不在主存的页面时，再把它们动态地装入。而替换规则用来确定替换主存中哪一部分，以便腾空部分主存，存放来自辅存要调入的那部分内容。
本次课程设计采用一些常用的存储器分配算法，设计一个请求页式存储管理模拟系统并调试运行。通过随机数产生一个指令序列，将指令序列变成为页地址流，计算并输出下述各种算法在不同内存容量下的命中率。
(1) 硬件：PC机，要求能运行Windows XP、Windows7或Windows 10操作系统。
(2) 软件：
·操作系统：Windows系列。
·程序设计语言：C
首先我们需要通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成（可选，也可随机产生）：
①50%的指令是顺序执行的；
②25%的指令是均匀分布在前地址部分；
③25%的指令是均匀分布在后地址部分。
在生成指令序列之后我们需要将指令序列变成为页地址流，设：
①页面大小为1k；
②用户内存容量为4页到32页；
③用户虚量容量为32k。
在用户虚存中，按每k存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条~第9条指令为第0页（对应虚存地址为[0，9]）；
第10条~第19条指令为第1页（对应虚存地址为[10，19]）；
……
第310条~第319条指令为第31页（对应虚存地址为[310，319]）；
按以上方式，用户指令可组成32页。
根据访问的页数生成访问串，然后我们需要编写和执行不同的页替换策略算法（FIFO先进先出页面替换策略、OPT最佳页面替换策略、LRU最近最少用页面替换策略、CLOCK时钟页面替换策略），并计算并输出下述各种算法在不同内存容量下的命中率。
为了使用在需求分析中指定的原则，通过随机数产生一个指令序列，共320条指令。具体的实施方法是：
①在[0，319]的指令地址之间随机选取一起点m；
②顺序执行一条指令，即执行地址为m+1的指令；
③在前地址[0，m+1]中随机选取一条指令并执行，该指令地址为m’；
④顺序执行一条指令，其地址为m’+1;
⑤在后地址[m’+2，319]中随机选取一条指令并执行；
⑥重复上述步骤①~⑤，直到执行320次指令。
关于随机数产生法，系统提供函数srand()和rand()，分别进行初始化和产生随机数。
然后创建存储指令序列的结构体，存放生成的指令序列和指令所在页号，以便于之后通过页号的访问串来执行页替换策略算法。
接下来我们要创建结构体数组记录放在主存中的页的一些信息，即驻留集。为了实现LRU策略我们需要增加计数器，为了实现CLOCK策略我们需要增加访问位。因此内存块结构体成员包括页面号、计数器、访问位。
在用户通过随机数产生了指令序列之后，也相应生成了对应页面号的访问串，这时候用户可以选择测试不同页替换策略算法的缺页数和命中率。
FIFO先进先出页面替换策略替换最早进入的页；OPT最佳页面替换策略淘汰下次访问距当前最远的那些页中序号最小的页；LRU最近最少用页面替换策略通过计数器淘汰上次使用距当前最远的页；CLOCK时钟页面替换策略基于LRU的思想，硬件在页面被访问时设置页表项中的访问位，随着表针的移动，淘汰访问位是0的页面，或清除页面的访问位。
基于上述策略的特点设计好程序算法。
最后，计算并输出下述各种算法在不同内存容量下的命中率。在本次课程设计中，页地址长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不内存的次数。
首先通过srand()函数初始化种子，再依照之前需求分析和系统设计所要求的原则来生成随机数并且存入指令序列结构体数组中，在存入指令地址的同时计算并存入页面号和偏移。需要注意的是需要判断m和m’是否为319，如果为319则m+1或m’+1会引起指令越界。
关键代码：
1. void initcount(){
2. int flag=0;
3. srand((unsigned)time(NULL));//根据系统时间产生随机数
4. for(int i=0;i<ordernum;i+=4){
5. int rands=rand()%ordernum;//0-319中选一点
6. if(rands==ordernum-1){
7. printf("指令即将越界！\n");
8. flag=1;
9. }
10. o[i].order=rands+1;//执行m+1指令
11. o[i+1].order=rand()%(o[i].order+1);//在[0,m+1]选择执行m'
12. if(o[i+1].order==ordernum-1){
13. printf("指令即将越界！\n");
14. flag=1;
15. }
16. o[i+2].order=o[i+1].order+1; // 执行m'+1
17. o[i+3].order=rand()%(ordernum-o[i+2].order-1)+o[i+2].order+1;//在[m'+2,319]执行
18. }
19. for(int i=0;i<ordernum;i++){
20. o[i].page=o[i].order/pageordermax;
21. o[i].offset=o[i].order%pageordermax;
22. }
23. if(flag!=1)
24. printf("随机指令集生成成功！\n");
25. }
运行结果如图所示，指令列为随机生成的指令的指令地址，页面号为指令所在的页面号，偏移是指指令在页面的偏移量。这些信息都存储在指令序列的结构体数组之中，之后执行页替换策略算法时，即使用结构体数组之中的数据。
为了实现FIFO策略，即替换最早进入的页，我们可以通过设置一个变量now_page来记录相对于整个主存结构体目前最早进入页的下标来实现。now_page初始化为0，如果访问页在主存中则不作处理，如果不在主存且驻留集有空，则now_page加1，将页调入，如果不在主存且驻留集满，则替换掉下标为now_page的页，并且now_page加一指向相对更新的数组下标。
关键代码：
1. void fifo(){
2. initmemoryblock();
3. float lack_rate;
4. int lack_pagenum=0;
5. int now_page=0;//位于队列前的指令在驻留集的下标
6. printf("\t\t*********************************\n");
7. printf("\t\t* 访问串 * 驻留集 * 页故障 *\n");
8. for(int i=0;i<ordernum;i++){
9. bool is_flag=false;
10. for(int j=0;j<memorysize;j++){
11. if(m[j].pagenumber==o[i].page){//指令在驻留集中
12. showline(o[i].page,true);
13. is_flag=true;
14. break;
15. }
16. if(m[j].pagenumber==-1){//指令不在驻留集中，且有驻留集为空
17. m[now_page].pagenumber=o[i].page;
18. now_page=(now_page+1)%memorysize;
19. is_flag=true;
20. lack_pagenum++;
21. showline(o[i].page,false);
22. break;
23. }
24. }
25. if(!is_flag){//指令不在驻留集中，且无驻留集为空
26. m[now_page].pagenumber=o[i].page;//页面替换
27. showline(o[i].page,false);
28. now_page=(now_page+1)%memorysize;
29. lack_pagenum++;
30. }
31. }
32. printf("\t\t*********************************\n");
33. lack_rate=lack_pagenum/(1.0*ordernum);
34. printf("缺页%d，命中率为%f\n",lack_pagenum,1-lack_rate);
35. }
执行FIFO策略算法。我们根据之前生成的指令序列的页面号作为访问串，使用FIFO策略，页替换过程应为：1.驻留集有空，加入1；2.驻留集有空，加入8；3.驻留集有空，加入0；4.驻留集有空，加入3；5.页替换，1替换成4；6.页替换，8替换成7；7.页替换，0替换成5；8.页替换，3替换成2；9.页替换，4替换成3；10.页替换，7替换成9；11.页替换，5替换成8；12.页替换，2替换成6；13.页替换，3替换成5；14.页替换，9替换成3；15.页替换，8替换成2；16.页替换，6替换成0；17.页替换，5替换成9。发生了17次缺页。算法运算的结果如图所示。可知运行无误。
为了实现OPT策略算法，即淘汰下次访问距当前最远的那些页中序号最小的页，我们可以通过设置两个变量far_pagei和postion来实现。如果访问页在主存中则不作处理，如果不在主存且驻留集有空，则直接将页调入，如果不在主存且驻留集满，则替换掉距当前最远的那些页中序号最小的页。
计算掉距当前最远的那些页中序号最小的页的算法如下：将变量far_pagei和postion初始化为0。然后从驻留集中依次取页面的页面号，再依次从指令序列结构体数组当前访问指令地址之后取指令地址的页面号与之相比，若页面号相同则说明之后需要访问这个页面，将这个指令地址页面号的下标与当前postion相对比，如果大于postion，说明比当前记录的驻留集中的页面号更远访问内存，则将far_pagei替换为当前驻留集页面号的下标；如果页面号一直不相同，说明之后没有访问到这个页面，直接将其postion认为319（最大）。这样far_pagei所记录的便是驻留集中距当前最远的那些页中序号最小的页的下标。
关键代码：
1. void opt(){
2. initmemoryblock();
3. float lack_rate;
4. int lack_pagenum=0;
5. printf("\t\t*********************************\n");
6. printf("\t\t* 访问串 * 驻留集 * 页故障 *\n");
7. for(int i=0;i<ordernum;i++){
8. bool is_flag=false;
9. for(int j=0;j<memorysize;j++){
10. if(m[j].pagenumber==o[i].page){//指令在驻留集中
11. showline(o[i].page,true);
12. is_flag=true;
13. break;
14. }
15. if(m[j].pagenumber==-1){//指令不在驻留集中，且有驻留集为空
16. m[j].pagenumber=o[i].page;
17. showline(o[i].page,false);
18. is_flag=true;
19. lack_pagenum++;
20. break;
21. }
22. }
23. if(!is_flag){//指令不在驻留集中，且无驻留集为空
24. int far_pagei=0;
25. int postion=0;
26. for(int j=0;j<memorysize;j++){
27. int k;
28. for(k=i;k<ordernum;k++){
29. if(m[j].pagenumber==o[k].page)
30. break;
31. }
32. if(k>postion){
33. postion=k;
34. far_pagei=j;
35. }
36. }
37. m[far_pagei].pagenumber=o[i].page;
38. showline(o[i].page,false);
39. lack_pagenum++;
40. }
41. }
42. printf("\t\t*********************************\n");
43. lack_rate=lack_pagenum/(1.0*ordernum);
44. printf("缺页%d，命中率为%f\n",lack_pagenum,1-lack_rate);
45. }
执行OPT策略算法。我们根据之前生成的指令序列的页面号作为访问串，使用OPT策略，页替换过程应为：1.驻留集有空，加入1；2.驻留集有空，加入8；3.驻留集有空，加入0；4.驻留集有空，加入3；5.驻留集为1、8、0、3,1最远，1替换成4；6.驻留集为4、8、0、3,4最远，4替换成7；7.驻留集为7、8、0、3,7最远，7替换成5；8.驻留集为5、8、0、3,0最远，0替换成2；9.驻留集为5、8、2、3,2最远，2替换成9；10.驻留集为5、8、9、3,8最远，8替换成6；11.驻留集为5、6、9、3,5、6最远，5替换成2；12.驻留集为2、6、9、3,2、6最远，2替换成0。发生了12次缺页。算法运算的结果如图所示。可知运行无误。
为了实现LRU策略算法，即通过计数器淘汰上次使用距当前最远的页，我们可以通过在主存结构体数组设置计数器来实现。将主存结构体数组中的所有数组成员的计数器都初始化为0。如果访问页在主存中则将访问页计数器改为-1，并对所有驻留页计数器加1，如果不在主存且驻留集有空，则直接将页调入，将该页计数器设为-1，并对所有驻留页计数器加1，如果不在主存且驻留集满，则替换掉主存中计数器最大的页，将新替换的页计数器设为-1，并对所有驻留页计数器加1。
关键代码：
1. void lru(){
2. initmemoryblock();
3. float lack_rate;
4. int lack_pagenum=0;
5. printf("\t\t*********************************\n");
6. printf("\t\t* 访问串 * 驻留集 * 页故障 *\n");
7. for(int i=0;i<ordernum;i++){
8. bool is_flag=false;
9. for(int j=0;j<memorysize;j++){
10. if(m[j].pagenumber==o[i].page){//指令在驻留集中
11. m[j].counter=-1;
12. addcounter();
13. showline(o[i].page,true);
14. is_flag=true;
15. break;}
16. if(m[j].pagenumber==-1){//指令不在驻留集中，且有驻留集为空
17. m[j].pagenumber=o[i].page;
18. m[j].counter=-1;
19. addcounter();
20. showline(o[i].page,false);
21. is_flag=true;
22. lack_pagenum++;
23. break;}
24. }
25. if(!is_flag){//指令不在驻留集中，且无驻留集为空
26. int max_counter=0;
27. int counter=0;
28. for(int j=0;j<memorysize;j++){
29. if(m[j].counter>counter){
30. counter=m[j].counter;
31. max_counter=j;}
32. }
33. m[max_counter].pagenumber=o[i].page;
34. m[max_counter].counter=-1;
35. addcounter();
36. showline(o[i].page,false);
37. lack_pagenum++;}
38. }
39. lack_rate=lack_pagenum/(1.0*ordernum);
40. printf("缺页%d，命中率为%f\n",lack_pagenum,1-lack_rate);
41. }
执行LRU策略算法。我们根据之前生成的指令序列的页面号作为访问串，使用LRU策略，页替换过程应为：1.驻留集有空，加入1；2.驻留集有空，加入8；3.驻留集有空，加入0；4.驻留集有空，加入3；5.页替换，查看计数，1替换成4；6.页替换，查看计数，0替换成7；7.页替换，查看计数，8替换成0；8.页替换，查看计数，3替换成5；9.页替换，查看计数，4替换成2；10.页替换，查看计数，7替换成3；11.页替换，查看计数，0替换成9；12.页替换，查看计数，2替换成8；13.页替换，查看计数，9替换成6；14.页替换，查看计数，3替换成9；15.页替换，查看计数，8替换成3；16.页替换，查看计数，6替换成2；17.页替换，查看计数，5替换成0。发生了17次缺页。算法运算的结果如图所示。可知运行无误。
为了实现CLOCK策略算法，即基于LRU的思想，硬件在页面被访问时设置页表项中的访问位，随着表针的移动，淘汰访问位是0的页面，或清除页面的访问位，我们可以通过在主存结构体数组设置访问位和指针指向变量pointer来实现。将主存结构体数组中的所有数组成员的访问位和指针指向变量pointer都初始化为0。如果访问页在主存中则将访问页的访问位更新为1，如果不在主存且驻留集有空，则直接将页调入，将页访问位设为1，并且指针向后指一位，如果不在主存且驻留集满，则指针一直向后指（指到最后通过取模返回数组首），替换掉访问位为0的页，调入新页并设置访问位为1，指针向后移动一位。
关键代码：
1. void clockc(){
2. initmemoryblock();
3. float lack_rate;
4. int lack_pagenum=0;
5. int pointer=0;
6. printf("\t\t* 访问串 * 驻留集 * 页故障 *\n");
7. for(int i=0;i<ordernum;i++){
8. bool is_flag=false;
9. for(int j=0;j<memorysize;j++){
10. if(m[j].pagenumber==o[i].page){//指令在驻留集中
11. m[j].access=1;
12. showline(o[i].page,true);
13. is_flag=true;
14. break;}
15. if(m[j].pagenumber==-1){//指令不在驻留集中，且有驻留集为空
16. m[pointer].pagenumber=o[i].page;
17. m[pointer].access=1;
18. pointer=(pointer+1)%4;
19. showline(o[i].page,false);
20. is_flag=true;
21. lack_pagenum++;
22. break;}
23. }
24. if(!is_flag){//指令不在驻留集中，且无驻留集为空
25. for(int j=0;j<=memorysize;j++){
26. if(m[pointer].access==0){
27. m[pointer].pagenumber=o[i].page;
28. m[pointer].access=1;
29. break;}
30. if(m[pointer].access==1){
31. m[pointer].access=0;
32. pointer=(pointer+1)%4;}
33. }
34. pointer=(pointer+1)%4;
35. showline(o[i].page,false);
36. lack_pagenum++;
37. }
38. }
39. lack_rate=lack_pagenum/(1.0*ordernum);
40. printf("缺页%d，命中率为%f\n",lack_pagenum,1-lack_rate);
41. }
执行CLOCK策略算法。我们根据之前生成的指令序列的页面号作为访问串，使用CLOCK策略，页替换过程应如表所示。而算法运算的结果如图所示。可知运行无误。
表中红色表示访问位为1，星号表示替换指针的位置。
为了使各算法的性能比较更为明显，将课设中的指令序列长度设置为320，每页存放指令个数设置为10.我生成10次指令序列，并统计和比较各算法的命中率，以此实现性能比较，结果如表1所示。
表1 各算法指令序列长度为320和页指令个数为10的命中率
比较各算法在不同序列长度和页指令个数时的命中率，结果如表2所示。
表2 各算法在不同指令序列长度和页指令个数时的命中率
通过表1和表2，我们可以发现OPT策略相对于其他三种策略的命中率更高，其他三种策略的命中率相差不是很大。通过表2.4我们还可以发现，特别是指令序列长度和页指令个数增大时，OPT策略相对于其他策略命中率的差距显得更加大了。
通过本次课程设计，让我对分页存储管理有了更加清晰的认识。分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号。而替换规则用来确定替换主存中哪一部分，以便腾空部分主存，存放来自辅存要调入的那部分内容。虚拟内存的作用内存在计算机中的作用很大，电脑中所有运行的程序都需要经过内存来执行，如果执行的程序很大或很多，就会导致内存消耗殆尽。因此设计一个存储管理系统很有必要。
在我进行课程设计时，我也对我们所学的页替换策略进行了复习。FIFO先进先出页面替换策略替换最早进入的页；OPT最佳页面替换策略淘汰下次访问距当前最远的那些页中序号最小的页；LRU最近最少用页面替换策略通过计数器淘汰上次使用距当前最远的页；CLOCK时钟页面替换策略基于LRU的思想，硬件在页面被访问时设置页表项中的访问位，随着表针的移动，淘汰访问位是0的页面，或清除页面的访问位。
在清楚了页替换策略的原理之后我就构思如何编写算法程序来实现他们，FIFO策略和OPT策略实现主要是通过设计算法后存储需要替换页的下标来实现的，而LRU算法的实现是通过定义一个书上所说的计数器来实现，CLOCK算法是通过定义访问位来实现的。在了解清楚原理之后，设计算法就如鱼得水了。
同时，在进行本次课程设计的同时，我也发现了自己的可深入之处，那就是将驻留集长度设为可变的驻留集长度，为此我将驻留集长度设为了常量，可以随时调节，但是输出页面排版没有优化，且本次课程设计没做要求便没有展示。
在最后的统计分析时，OPT策略是理想中的最优策略，故其命中率始终是三个里面最高的。和之前所说的一样，统计这里也有可深入之处，我在课设报告的性能分析处只比较了不同指令序列长度和页指令个数下命中率的变化。同时我们也可以改变驻留集长度来验证不同策略是否有belady奇异现象。
完整代码下载：https://download.csdn.net/download/weixin_43977664/15242974