for(inti=temp[0];i<=temp[0]+temp[1]-1;i++)
mem[i]=true;
vector:
:
iteratorfirst=occupied.begin();
occupied.erase(first+page-1);
}
//_sleep(2000);
//getchar();
}
}
运行情况:
1.一次最多申请20块的请求情况
2.一次最多申请20块的请求失败时内存的使用情况
4.一次最多申请5块的请求情况
2.一次最多申请5块的请求失败时内存的使用情况
总结:
相对来说一次最多申请20块时比一次最多请求5块时,碎片情况要比较严重。
最多申请20块因为没有足够的连续区域而停止的概率要比最多申请5块时因为没有足够的连续区域而停止的概率大。
虽然有大块的区域没有分配,但是连续块的数量还是无法满足最多申请20块时的请求。
(二)
实验内容:
设计一个虚拟存储区和内存工作区,并使用下述算法计算访问命中率。
1)最佳置换算法(Optimal)
2)先进先出法(FisrtInFirstOut)
3)最近最久未使用(LeastRecentlyUsed)
4)最不经常使用法(LeastFrequentlyUsed)
其中,命中率=1-页面失效次数/页地址流长度。
试对上述算法的性能加以较各:
页面个数和命中率间的关系;同样情况下的命中率比较。
实验准备:
本实验中主要的流程:
首先用srand()和rand()函数定义和产生指令序列,然后将指令序列变换成相应的页地址流,并针对不同的算法计算出相应的命中率。
实现:
页面请求序列的产生:
采用指导书上产生指令的方法,先产生一个[0,1023]之间的随机数m,然后将m加1作为第一个请求,然后产生一个0到m+2之间的随机数m1,作为第二条指令,接着将m1+1作为第三条指令。
最后产生一个[m1+2,2047]之间的随机数作为第四条指令。
这样重复进行512次,一共产生了2048条指令。
接着按照指令整除64的计算方法可以获得这条指令所在的页面号。
这样便产生了2048个页面请求。
最优置换:
所有置换算法其他部分都基本相同,不同的是选择置换页面的部分。
对于最优置换,发生页错误时,使用selectBest函数选择页面。
传入start作为计算得而起始点。
设置一个time数组用来记录内存中的每一个页,在start之后第一次出现时在页面请求数组里的下标。
当然需要先将time数组初始化为INI(10000)作为初始值,这样就能代表内存中还没有页,能保证这个位置能被优先替换。
在计算完time数组后,只要在time数组中找出最大值,返回下标,这个下标就代表需要置换的内存中的页。
先进先出置换:
设置一个age数组用来记录内存中对应页的年龄,age数组初始化为INI,这样就能保证这些位置能够首先填充上页。
每次置换只要在age数组里找出最大的值(即代表这个页来得最早),返回其下标,并把这个位置置成0即可。
与最优置换不同的时,如果没有发生页错误,需要遍历age数组,把每一位都加1。
最近最久未使用:
需要设置一个useTime数组来记录上一次使用到现在的时间。
初始化为INI,这样能保证初始的值是最大的,即会被优先换出去。
每次置换时,只需要在useTime数组中找出最大的值(即上次使用时间距今最久),返回下标,并把这个位置成0。
每次发生命中时需要把除了命中页之外的所有页的useTime加1,命中页清零。
每次页错误时,需要把除了被替换页之外的所有页的useTime加1。
最不经常使用法:
需要设置一个fru数组来记录内存中页被访问的次数。
初始化为-1,保证这些位置能够马上被填充上。
发生页错误时,只需要在fru数组中找出最小的值,然后返回其下标,并把对应位置成1。
每次发生命中时,需要把命中页对应的fru加1。
即提高其使用频率。
数据结构及核心函数:
#defineINI10000
#definePAGENUM20//内存页数
intcomm[2048];
classCreateReq
{
public:
CreateReq();
intproduceNum(intnum);
};
intCreateReq:
:
produceNum(intnum)
{
returnrand()%num;
}
CreateReq:
:
CreateReq()
{
srand(unsigned(time(0)));
for(inti=0;i<=511;i++){
intm=produceNum(1024);
comm[i*4]=m+1;
intm1=produceNum(m+2);
comm[i*4+1]=m1;
comm[i*4+2]=m1+1;
comm[i*4+3]=produceNum(2047-m1-2+1)+m1+2;
}
for(inti=0;i<=2047;i++)
comm[i]=comm[i]/64;
}
classcontrol
{
private:
intfru[PAGENUM];
intuseTime[PAGENUM];
intage[PAGENUM];
intmemBest[PAGENUM];
intmemFifo[PAGENUM];
intmemLru[PAGENUM];
intmemLfu[PAGENUM];
floatpfBest;
floatpfFifo;
floatpfLru;
floatpfLfu;
floatrateBest;
floatrateFifo;
floatrateLru;
floatrateLfu;
public:
control(void)
{
pfBest=0;
pfFifo=0;
pfLru=0;
pfLfu=0;
for(inti=0;i<=PAGENUM-1;i++){
memBest[i]=INI;
memFifo[i]=INI;
memLru[i]=INI;
memLfu[i]=INI;
age[i]=INI;
useTime[i]=INI;
fru[i]=0;
}
}
intselectBest(intpage,intstart);
intselectFifo();
intselectLru();
intselectLfu();
voidrun(void);
boolexist(intpage,intmem[]);
voidinc(intage[]);
};
voidcontrol:
:
inc(intage[])
{
for(inti=0;i age[i]++;
}
boolcontrol:
:
exist(intpage,intmem[])
{
for(inti=0;i if(page==mem[i])
returntrue;
returnfalse;
}
intcontrol:
:
selectBest(intpage,intstart)
{
intbig=0;
inttemp;
inttime[PAGENUM];
for(inti=0;i<=PAGENUM-1;i++){//构建time数组,记录这个页在后面的出现时间
time[i]=INI;
if(memBest[i]==INI)
returni;
for(intj=start+1;j<=2047;j++)
if(comm[j]==memBest[i]){
time[i]=j;
break;
}
}
for(inti=0;i<=PAGENUM-1;i++){
if(time[i]>=big){
big=time[i];
temp=i;
}
}
returntemp;
}
intcontrol:
:
selectFifo()
{
inttemp;
intold=0;
for(inti=0;i<=PAGENUM-1;i++){
if(age[i]>=old)
{
old=age[i];
temp=i;
}
}
age[temp]=0;
returntemp;
}
intcontrol:
:
selectLru()
{
inttemp;
intbig=0;
for(inti=0;i<=PAGENUM-1;i++){
if(big<=useTime[i]){
big=useTime[i];
temp=i;
}
}
useTime[temp]=0;
returntemp;
}
intcontrol:
:
selectLfu()
{
inttemp;
intsmall=0;
for(inti=0;i<=PAGENUM-1;i++){
if(small>=fru[i]){
small=fru[i];
temp=i;
}
}
fru[temp]=1;
returntemp;
}
voidcontrol:
:
run(void)
{
for(inti=0;i<=2047;i++){
//getchar();
if(!
exist(comm[i],memBest)){//最优页置换
pfBest++;
memBest[selectBest(comm[i],i)]=comm[i];
}
if(!
exist(comm[i],memFifo)){//Fifo页置换
pfFifo++;
memFifo[selectFifo()]=comm[i];
}
if(!
exist(comm[i],memLru)){//lru页置换
pfLru++;
memLru[selectLru()]=comm[i];
}
else{
for(intj=0;j<=PAGENUM-1;j++){
if(memLru[j]!
=comm[i])
useTime[j]++;
}
}
if(!
exist(comm[i],memLfu)){//lfu页置换
pfLfu++;
memLfu[selectLru()]=comm[i];
}
else{
for(intj=0;j<=PAGENUM-1;j++){
if(memLfu[j]!
=comm[i])
fru[j]++;
}
}
inc(age);
}
rateBest=1-pfBest/2047;
rateFifo=1-pfFifo/2047;
rateLru=1-pfLru/2047;
rateLfu=1-pfLfu/2047;
cout<<"在内存能容纳"< cout<<"在内存能容纳"< cout<<"在内存能容纳"< cout<<"在内存能容纳"< getchar();
}
voidmain(void)
{
CreateReqa;
controlb;
b.run();
}
运行情况:
1.内存能容纳10页
2.内存能容纳20页
3.内存能容纳30页