实验五 存储分配.doc

实验五 存储分配实验目的通过对页面、页表、地址转换和页面转换过程的模拟，加深对请求调页系统的原理和实现过程的理解。实验内容和步骤1 假设每个页面中可存放10条指令，分配给一个作业的内存块数为42 用C语言模拟一作业的执行过程。该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块中均已装入该作业，则需进行页面转换。最后显示其物理地址，并转下一条指令。在所有320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3 置换算法：请分别考虑OPT、FIFO和LRU算法。4 作业中指令的访问次序按下述原则生成：50%的指令是顺序执行的25%的指令是均匀分布在前地址部分25%的指令是均匀分布在后地址部分具体的实施办法：在0,319之间随机选取一条起始指令，其序号为m顺序执行下一条指令，即序号为m+1的指令通过随机数，跳转到前地址部分0,m-1中的某条指令处，其序号为m1；顺序执行下一条指令，即序号为m1+1的指令通过随机数，跳转到后地址部分m1+2,319中的某条指令处，其序号为m2;顺序执行下一条指令，即序号为m2+1的指令重复跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行的过程，直至执行320条指令。问题讨论1如果增加分配给作业的内存块数，将会对作业运行过程中的缺页率产生什么影响？2为什么一般情况下，LRU具有比FIFO更好的性能？关键知识 在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已 无空闲 空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。在这一过程中，选择换出页面的算法称为页面置换算法。一个好的页面置换算法，应具有较低的页面更换频率。页面置换算法的好坏，将直接影响到系统的性能。以下分别是实验要求的三个页面置换算法的介绍及设计思想。最佳置换算法（Optimal）：最佳置换算法是Blady在理论上提出的一种算法。其所选择的被淘汰页是将来不再被使用，或者是在最远的将来才被访问的页面。 采用这种页面置换算法， 保证有最少的缺页率。但由于目前还无法预知一个进程在内存的若干个页面中，哪个在最长的时间内不会被访问，因而，现实中该算法是无法实现的。因此在该算法的模拟过程中，页面访问次序必须是给定的，具体实现为：对每一个物理块设置一个整数型的访问标志位，当需要置换物理块中的某一页时，将每一个物理块中的页面号与当前需调入页以后的每一页面号进行比较，若物理块中的页面号与所有的页面号都不同，则该页即为将来不再使用的页，将访问标记设置为1000，表示将来不会用，设置为一个很大数；若找到页号相同的则将其访问次序记入访问标记，比较访问标记，最大的即为最久不会被访问的，将其换出。先进先出法（First In First Out）：该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。在该算法的模拟过程中，每当某一页面进入内存时（包括页面置换时页面的置入），物理块中各页面访问标记自动加一，置换后，将置换页面所在的物理块中访问标记减一；这样能防止当物理块访问标记出现两个以上相同的值的错误执行，更好地模拟了先进先出法； 最近最久未使用（Least Recently Used）： 该算法以最近的过去作为不久将来的近似， 将过去最长一段时间里不曾被使用的页面置换掉。在该算法的模拟过程中，每当物理块中的页面被访问时，便将其访问标记置为1以后每执行一条指令，便将物理块中各页面的访问标记加一，需置换时访问标记最大的便是将要被置换的。#include #include#include#include#define Bsize 4 typedef struct BLOCK/声明一种新类型物理块类型 int pagenum;/页号 int accessed;/访问字段，其值表示多久未被访问 BLOCK; int pc;/程序计数器，用来记录指令的序号int n;/缺页计数器，用来记录缺页的次数 static int temp320;/用来存储320条随机数BLOCK blockBsize; /定义一大小为4的物理块数组void init( ); /程序初始化函数int findExist(int curpage);/查找物理块中是否有该页面int findSpace( );/查找是否有空闲物理块int findReplace( );/查找应予置换的页面void display ( );/显示void suijishu( );/产生320条随机数,显示并存储到temp320void pagestring( );/显示调用的页面队列void OPT( );/OPT算法void LRU( );/ LRU算法void FIFO( );/FIFO算法void init( ) for(int i=0;iBsize;i+) blocki.pagenum=-1; blocki.accessed=0; pc=n=0; int findExist(int curpage) for(int i=0; iBsize; i+) if(blocki.pagenum = curpage ) return i;/检测到内存中有该页面，返回block中的位置 return -1;int findSpace( ) for(int i=0; iBsize; i+) if(blocki.pagenum = -1) return i;/找到空闲的block，返回block中的位置 return -1;int findReplace( ) int pos = 0; for(int i=0; iblockpos.accessed) pos = i;/找到应予置换页面，返回BLOCK中位置 return pos;void display( ) for(int i=0; iBsize; i+) if(blocki.pagenum != -1) printf( %02d,blocki.pagenum); coutpc; cout*按照要求产生的320个随机数：*endl; for(int i=0;i320;i+) tempi=pc; if(flag%2=0) pc=+pc%320; if(flag=1) pc=rand( )% (pc-1); if(flag=3) pc=pc+1+(rand( )%(320-(pc+1); flag=+flag%4; printf( %03d,tempi); if(i+1)%10=0) coutendl; void pagestring( ) for(int i=0;i320;i+) printf( %02d,tempi/10); if(i+1)%10=0) coutendl; void OPT( ) int exist,space,position ; int curpage; for(int i=0;i320;i+) if(i%100=0) getch( ); pc=tempi; curpage=pc/10; exist = findExist(curpage); if(exist=-1) space = findSpace ( ); if(space != -1) blockspace.pagenum = curpage; display( ); n=n+1; else for(int k=0;kBsize;k+) for(int j=i;j320;j+) if(blockk.pagenum!= tempj/10) blockk.accessed = 1000; /将来不会用，设置为一个很大数 else blockk.accessed = j; break; position = findReplace( ); blockposition.pagenum = curpage; display( ); n+; cout缺页次数:nendl; cout缺页率:(n/320.0)*100%endl;/- void LRU( ) int exist,space,position ; int curpage; for(int i=0;i320;i+) if(i%100=0) getch( ); pc=tempi; curpage=pc/10; exist = findExist(curpage); if(exist=-1) space = findSpace( ); if(space != -1) blockspace.pagenum = curpage; display( ); n=n+1; else position = findReplace( ); blockposition.pagenum = curpage; display( ); n+; else blockexist.accessed = -1;/恢复存在的并刚访问过的BLOCK中页面accessed为-1 for(int j=0; j4; j+) blockj.accessed+; cout缺页次数:nendl; cout缺页率:(n/320.0)*100%endl;/-void FIFO( ) int exist,space,position ; int curpage; for(int i=0;i320;i+) if(i%100=0) getch( ); pc=tempi; curpage=pc/10; exist = findExist(curpage); if(exist=-1) space = findSpace( ); if(space != -1) blockspace.pagenum = curpage; display( ); n=n+1; else position = findReplace( ); blockposition.pagenum = curpage; display( ); n+; blockposition.accessed-; for(int j=0; jBsize; j+) blockj.accessed+; cout缺页次数:nendl; cout缺页率:(n/320.0)*100%endl;void main( ) int select; cout请输入第一条指令号(0320)：; suijishu( ); cout*对应的调用页面队列*endl; pagestring( ); do cout*endl; cout-1:OPT 2:LRU 3:FIFO 4:退出-endl; cout*endl; coutse