实验3 页面置换算法.docVIP

实验3 页面置换算法 实验目的： 设计和实现最佳置换算法、随机置换算法、先进先出置换算法、最近最久未使用置换算法、简单Clock置换算法及改进型Clock置换算法；通过支持页面访问序列随机发生实现有关算法的测试及性能比较。 实验设计 课题假设前提说明 虚拟内存页面总数为N，页号从0到N-1 物理内存由M个物理块组成 页面访问序列串是一个整数序列，整数的取值范围为0到N-1。页面访问序列串中的每个元素p表示对页面p的一次访问 页表用整数数组或结构数组来表示 页面访问序列随机生成 确定虚拟内存的尺寸N，工作集的起始位置p，工作集中包含的页数e，工作集移动率m（每处理m个页面访问则将起始位置p +1），以及一个范围在0和1之间的值t； 生成m个取值范围在p和p + e间的随机数，并记录到页面访问序列串中； 生成一个随机数r，0 ≤ r ≤ 1； 如果r t，则为p生成一个新值，否则p = (p + 1) mod N； 如果想继续加大页面访问序列串的长度，请返回第2步，否则结束。 工作集与缺页率 工作集 多数程序都显示出高度的局部性，也就是说，在一个时间段内，一组页面被反复引用。这组被反复引用的页面随着时间的推移，其成员也会发生变化。有时这种变化是剧烈的，有时这种变化则是渐进的。我们把这组页面的集合称为工作集。 缺页率 缺页率 = 缺页中断次数/页面访问次数 性能测评 测试不同的页面访问序列及不同的虚拟内存尺寸 源程序清单和说明 #includeiostream #includestdlib.h using namespace std; int const InsideCount = 3;//内存中存放的页面数 int count = 0; int Inside[InsideCount]; int const PageCount =10;//总的页面数 int Page[PageCount]; int insert = 0;//先到先出置换算法fcfo中表示 当内存满的时候，新进入的页号放的位置 int suiji = 0; //随机置换算法randchange 当内存满的时候，新进入的页号放的位置 int state[InsideCount];//clock置换算法中，内存中的每个页面号对应的状态 int state2[InsideCount][2];// 二维数组，第一行第一列为访问位，第一行的第二列为修改位 double lost = 0.0; //检测页号是否在内存中 bool isInside(int num){ for(int i = 0; i InsideCount; i++){ if(Inside[i] == Page[num]){ state[i] = 1; return true; } } return false; } //判断页面是否已经被修改 bool change(){ if((rand()%2+1) == 1 ){ cout该页面被修改endl; return true; } else return false; } //用于改进型clock置换算法，检测页号是否在内存中并把访问位和修改位置1 bool isInside2(int num){ for(int i = 0; i InsideCount; i++){ if(Inside[i] == Page[num]){ if(change()){ state2[i][0] = 1; state2[i][1] = 1; } else{ state2[i][0] = 1; } return true; } } return false; } //用于改进型clock置换算法，判断内存中第几个需要被置换 int whichpage(){ int j; for(j=0; j InsideCount;j++){ if(state2[j][0] == 0state2[j][1] == 0){ return j; } } for(j=0; j InsideCount;j++ ){ if(state2[j][0] == 0state2[j][1] == 1){ return j; } state2[j][0] = 0 ; } for(j=0; j InsideCount;j++ ){ state2[j][0] = 0 ; } return whichpage(); } //最佳置换算法（OPT） void