中科大高级数据库实验二—buffer的存储与管理.docx
《中科大高级数据库实验二—buffer的存储与管理.docx》由会员分享，可在线阅读，更多相关《中科大高级数据库实验二—buffer的存储与管理.docx（26页珍藏版）》请在冰点文库上搜索。
高级数据库第二次试验
姓名：
张先荣 学号：
SA16225439 班级：
软件系统设计6班
一．实验目的
为了了解数据库Buffer的工作原理，对数据库底层有个更加深入的了解，实现一个简单的模拟的缓冲管理器，本次试验涉及到缓冲管理器，缓冲技术，散列技术，文件存储结构，磁盘空间等。
详细步骤如下：
（1）模拟实现一个块在磁盘和缓冲区之间的交互。
（2）要求创建一个data.dbf,然后创建存储管理器对文件的读写进行操作。
（3）建立一个缓冲区管理器与存储管理器交互、
（4）测试500000条数据库请求的txt文件，读取指定的页号到页面缓冲区，计算磁盘IO次数与命中率。
二．实验环境
硬件环境：
联想G470笔记本
内存：
8G
软件环境：
开发系统:
Windows7
开发工具：
VisualStudio2013
开发语言：
C++版本：
.NET4.5
三．实验思路
由题目描述我们可以设计出以下几个主要类：
1.File_Create类：
用来创建指定的data.dbf文件；
2.DSMgr类：
用来读写data.dbf文件，实现指定page_id的page
的读写；
3.BMgr类：
用来管理Buffer中bframe，维护数组ptof[]、ftop[]，还有对buffer空间不够用时挑选置换bframe的LRU算法；
4.BCB类：
用来维护与缓冲区Buffer关联的page信息
5.bFrame类：
定义Buffer中的bFrame，即page在缓冲区中的存在形式；
6.LRU类：
最近最少使用算法，当Buffer空间已满时用来挑选置换的bFrame，里面维护一个frameid；
这里我们先假设页面的大小为4096，缓冲区一共有1024个页面，开始在磁盘上存储了50000个页，按照目录进行存储。
然后用哈希表映射页框号到页号，页号到页框号。
如图表1所示：
图表1磁盘与内存
其中，BCB类和bFrame类按照buffer2.txt文件定义，LRU类是包含了一个LRUNode类，定义了LRU节点信息，用于维护被关联的frameID。
我们在
LRU定义双向链表，因此，在置换的时候直接从尾节点找到并删除即可。
因为我们page一共定义了50000个（pageid范围0-49999），而缓冲区大小只有1024个（frameid范围0-1023），所以pageid不能和frameid等值对应，因此需要一个哈希函数将pageid映射到一个对应的frameid，这里采取最简单的做法frameid=pageid%1024，那么在查找的时候，ptof[pageid%1024]表示已经存在的page应该存放的位置，直接去里面找；如果是新读进来的块，则更新BCB块信息，再将BCB块挂到这个位置的链表上去。
这个数组主要还是用于查找已存在的page所属的BCB块。
为实际Buffer中维护的只有1024个page，每次需要将空闲的一个
bFrame找一个出来并且读page到这个frameid的bFrame中，令ftop[frameid]
=pageid，表示当前页框号为frameid的bFrame中关联着页号为pageid的
page。
同时创建一个BCB块包含pageid和这个找到的空闲的frameid等信息，并挂到ptof[pageid%1024]的位置上去。
这种情况只适用于Buffer中的1024个bFrame还有空闲的情况。
四．实验流程
流程图如图2所示。
图表2流程图
五.实验类图
实验类如图3所示：
图表3类图
六.概要设计。
1.BufferManager,用来管理Buffer中bframe，维护数组ptof[]、ftop[]，还有对buffer空间不够用时挑选置换bframe的LRU算法.
2.DSManager,用来读写data.dbf文件，实现指定page_id的page的读写；
3.其他一些类：
4.将对应page_id的page读入到buffer中。
如果buffer已满，则需要选择换出的frame
5.设置特定bcb中的dirty值为1
七.实验结果
1.如图所示，当buffersize=1024，操作总页数是500000，此时的IO总次数是362321，命中率是27.5%，程序运行总时间是29.3s
图表4buffersize=1024
2.如图所示，当buffersize=2048，操作总页数是500000，此时的IO总次数是325001，命中率是34.9%，程序运行总时间是29.8s
图表5buffersize=2048
3.如图所示，当buffersize=5049，操作总页数是500000，此时的IO总次数是271259，命中率是45.7%，程序运行总时间是42.79s
图表6buffersize=5049
4.如图所示，当buffersize=10000，操作总页数是500000，此时的IO总次数是225925，命中率是54.8%，程序运行总时间是49.8s
图表6buffersize=10000
统计的I/O次数、命中buffer次数和命中率。
可以发现随着BufferSize
的增加，磁盘I/O数越小，命中次数越多，命中率越高。
八.详细代码
#include"BufferManager.h"#include"DSManager.h"#include"Operate.h"
#include#include#include#include
classBufferManager
{
public:
BufferManager（）;
intFixPage（intpage_id）;
NewPageFixNewPage（bFramebuf[]）;//NewPageintUnfixPage（intpage_id）;
intNumFreeFrames（）;intSelectVictim（）;intHash（intpage_id）;
voidRemoveBCB（BCB*ptr,intpage_id）;voidRemoveLRUEle（intfrid）;
voidSetDirty（intframe_id）;voidUnsetDirty（intframe_id）;voidWriteDirtys（）;
boolFindFrame（intpage_id）;voidPrintFrame（intframe_id）;
voidcalcLRUList（BCB*ptr,intfrid）;intftop[DEFBUFSIZE];
BCB*ptof[DEFBUFSIZE];
bFramebuf[DEFBUFSIZE];
};
classDSManager
{
public:
DSManager（）;
intOpenFile（stringfilename）;intCloseFile（）;
bFrameReadPage（intpage_id）;
intWritePage（intpage_id,bFramefrm）;intSeek（intoffset,intpos）;
FILE*GetFile（）;voidIncNumPages（）;intGetNumPages（）;
voidSetUse（intindex,intuse_bit）;intGetUse（intindex）;
private:
FILE*file;intnumPages;
intpages[MAXPAGES];
};
#pragmaonce
#defineDEFBUFSIZE2048
#defineFRAMESIZE4096
#defineMAXPAGES 100000
#defineCOUNT500000structbFrame{
charfield[FRAMESIZE];
};
structNewPage{
intpage_id;intframe_id;
};
structBCB{
BCB（）;
intpage_id;intframe_id;intlatch;intcount;intftime;intstime;intdirty;BCB*next;
};
structLRUEle{
LRUEle（）;
intfid;
doubleb2dtime;LRUEle*less_recent;LRUEle*more_recent;
};
classOperate
{
public:
Operate（void）;
~Operate（void）;
};
#pragmaonce
#include"BufferManager.h"#include"DSManager.h"#include#include
#include#includeusingnamespacestd;
DSManagerds;
BufferManagerbm;
LRUEle*lru;
LRUEle*mru;
BufferManager:
:
BufferManager（）
{
inti=0;
for（i=0;i{
ptof[i]=NULL;//初始化BCB数组
ftop[i]=-1;
}
ds.OpenFile（"data.dbf"）;
}
intBufferManager:
:
FixPage（intpage_id）
{
intfid=-1;
intframe_id=Hash（page_id）;BCB*bcb=ptof[frame_id];while（bcb!
=NULL）
{
if（bcb->page_id==page_id）
{
break;
}
bcb=bcb->next;
}
if（bcb!
=NULL）
{
if（bcb->stime!
=-1）
{
bcb->ftime=bcb->stime;
}
}
else
{
calcLRUList（bcb,bcb->frame_id）;returnbcb->frame_id;
bcb=ptof[frame_id];fid=SelectVictim（）;
buf[fid]=ds.ReadPage（page_id）;ftop[fid]=page_id;
if（bcb!
=NULL）
{
while（bcb->next!
=NULL）
{
bcb=bcb->next;
}
bcb->next=newBCB（）;bcb=bcb->next;
}
else
{
}
bcb=newBCB（）;ptof[frame_id]=bcb;
bcb->next=NULL;
bcb->page_id=page_id;bcb->frame_id=fid;bcb->latch=0;
bcb->count=0;
bcb->ftime=static_cast（time（0））;bcb->stime=-1;
calcLRUList（bcb,fid）;
}
returnfid;
}
intBufferManager:
:
UnfixPage（intpage_id）
{
return0;
}
intBufferManager:
:
SelectVictim（）
{
intvFrame=0,pid=0,fid=0;BCB*bcb=NULL;
boolfound=false;LRUEle*temp=lru;if（temp==NULL）
{
return0;
}
for（inti=0;i{
if（ftop[i]==-1）
{
returni;
}
}
vFrame=temp->fid;pid=ftop[vFrame];fid=Hash（pid）;bcb=ptof[fid];
while（found!
=true）
{
if（bcb==NULL）
{
break;
}
while（bcb->frame_id!
=vFrame）
{
bcb=bcb->next;
}
if（bcb->count==0&&bcb->latch==0）
{
}
else
{
found=true;
temp=temp->more_recent;if（temp==NULL）
{
break;
}
vFrame=temp->fid;pid=ftop[vFrame];fid=Hash（pid）;bcb=ptof[fid];
}
}
pid=ftop[vFrame];fid=Hash（pid）;bcb=ptof[fid];if（bcb!
=NULL）
{
if（bcb->next!
=NULL）
{
while（bcb!
=NULL&&bcb->page_id!
=pid）
{
bcb=bcb->next;
}
if（bcb!
=NULL&&bcb->dirty==1）
{
ds.WritePage（pid,buf[vFrame]）;
}
if（bcb!
=NULL）
{
RemoveLRUEle（vFrame）;RemoveBCB（bcb,pid）;
}
}
}
returnvFrame;
}
boolBufferManager:
:
FindFrame（intpage_id）
{
intf_id=NULL;
//cout<for（inti=0;i{
if（ptof[i]->page_id==page_id）
{
f_id=ptof[i]->frame_id;
}
}
//cout<=NULL）
returntrue;
else
returnfalse;
}
intBufferManager:
:
Hash（intpage_id）
{
//H（k）=（page_id）%buffer_size,hash转换函数//
intfid;
intbufsize=DEFBUFSIZE;
fid=page_id%bufsize;//不处理偏移问题//
returnfid;
}
voidBufferManager:
:
RemoveBCB（BCB*ptr,intpage_id）
{
BCB*bcb=ptof[Hash（page_id）];BCB*tmp=NULL;
if（bcb==ptr）
{
if（bcb->next!
=NULL）
{
}
else
{
}
else
{
}
bcb=bcb->next;deleteptr;
ptof[Hash（page_id）]=bcb;ptr=bcb=NULL;
deleteptr;ptof[Hash（page_id）]=NULL;ptr=bcb=NULL;
while（bcb->next!
=ptr）
{
bcb=bcb->next;
}
bcb->next=ptr->next;deleteptr;
ptr=NULL;
}
}
//删除LRU元素//
voidBufferManager:
:
RemoveLRUEle（intfrid）
{
LRUEle*ptr=mru;LRUEle*temp=NULL;if（ptr==NULL）
{
return;
}
while（ptr!
=NULL&&ptr->fid!
=frid）
{
ptr=ptr->less_recent;
}
if（ptr==NULL）
{
return;
}
ptr->less_recent->less_recent->more_recent=ptr;temp=ptr->less_recent->less_recent;
deleteptr->less_recent;
ptr->less_recent=temp;
}
//LRUList维护//
voidBufferManager:
:
calcLRUList（BCB*ptr,intfrid）
{
if（mru==NULL）//为空是创建一个新的//
{
mru=newLRUEle（）;mru->fid=frid;
mru->less_recent=NULL;mru->more_recent=NULL;if（ptr->stime!
=-1）
{
}
else
{
}
mru->b2dtime=（ptr->stime-ptr->ftime）;
mru->b2dtime=-1;
}
else
{
lru=mru;
doublet=0.0;if（ptr->stime!
=-1）
{
}
else
{
}
t=ptr->stime-ptr->ftime;
t=-1;
LRUEle*pt=mru;if（t==-1）
{
while（pt->less_recent!
=NULL&&pt->less_recent->b2dtime!
=-1）
{
pt=pt->less_recent;
}
if（pt->less_recent==NULL）
{
pt->less_recent=newLRUEle（）;
pt->less_recent->more_recent=pt;pt=pt->less_recent;
pt->fid=frid;
pt->less_recent=NULL;pt->b2dtime=t;
}
else
{
}
else
{
}
lru=pt;
LRUEle*temp=newLRUEle（）;temp->fid=frid;
temp->b2dtime=t;
temp->less_recent=pt->less_recent;temp->more_recent=pt;
pt->less_recent->more_recent=temp;pt->less_recent=temp;
while（pt->less_recent!
=NULL&&t>pt->less_recent->b2dtime）
{
pt=pt->less_recent;
}
if（pt->less_recent==NULL）
{
pt->less_recent=newLRUEle（）;
pt->less_recent->more_recent=pt;pt=pt->less_recent;
pt->b2dtime=t;pt->fid=frid;
pt->less_recent=NULL;lru=pt;
}
else//需要在中间插入新的元素//
{
LRUEle*temp=newLRUEle（）;temp->b2dtime=t;
temp->fid=frid;
temp->less_recent=pt->less_recent;temp->more_recent=pt;
pt->less_recent->more_recent=temp;pt->less_recent=temp;
}
}
}
}
//找出空闲的frame//
intBufferManager:
:
NumFreeFrames（）
{
inti=0,j=0,num=0,Free=0;BCB*bcb=NULL;
for（i=0;i{
j=ftop[i];if（j==-1）
{
Free++;
}
else
{
num=Hash（j）;
intframe_id=num;bcb=ptof[num];
while（bcb!
=NULL&&bcb->frame_id!
=j）
{
bcb=bcb->next;
}
if（bcb!
=NULL&&bcb->frame_id==j）
{
if（bcb->count==0&&bcb->latch==0）
{
Free++;
}
}
}
}
returnFree;
}
//设置特定bcb中的dirty值为1//
voidBufferManager:
:
SetDirty（intframe_id）
{
intpid=ftop[frame_id];intfid=Hash（pid）;
BCB*bcb=ptof[fid];
while（bcb!
=NULL&&bcb->page_id!
=pid）
升级会员 