中科大软院金老师的数据库实验2

《中科大软院金老师的数据库实验2》由会员分享，可在线阅读，更多相关《中科大软院金老师的数据库实验2（20页珍藏版）》请在装配图网上搜索。

1、数据库第二次实验实验名称：Buffer的存储及管理姓名：卷悅学号：SA12226141实验时间：2012.11.16实验地点：明德楼308丿USTCSchoolofSoftwaieEngmeenngZhangYiie目录1实验背景32实验平台33设计思路34概要设计55实验结果及分析76总结及致谢87附录：9丿USTCSchoolofSoftwaieEngmeenngZhangYiie1实验背景Inthisproject,wewillimplementasmiplestorageandbuffermanager.Thedocumentaddressesthestorageandbufferma

2、nager.Bufferandflamesizes,bufferandflamestoragestructures，pagefbnnats,pagestoragestnictures,fileformats,buffermgtechniques,hasliuigtechniques,filestoragestructures、andinterfacefxinctionsforthediskspaceandbuffermoduleswillbediscussedTheparticulartecluuqueischosenfiomthemateiialcoveredinclassthatarefe

3、levanttobufferandstoragemanager2实验平台本实验采用Wmdows7Home+VisualStudio20123设计思路采用4096大小的页面，即FiameSize=4096,buffer中一共有1024个页面，即DefBuffeiSize=1024o开始在硬盘上存储50000个页，按目录形式存储，即第一页包含目录大小，第一页的起始位置，每一页的逻辑偏移量。其中buffer和disk的映射关系如图2.1所示：图2.1buffei和disk映射关系示意图我们用两个哈希表來映射页框号到页号，页号到页框号。方便系统的查找，其概要设计图2.2所示：IntftopDEFBUF

4、SIZE图2.2HashTable设计图其中Ftop是一个一维数组，完成页框到页号的映射。Ptof是一个哈希链表，用來完成页号到页框的映射，上面的BCB是用來保存页框的信息的。置换的策略采用LRU：用recentused这个数据项记录最近使用的时间，遍历哈希表，找到最久没有使用的页框，把他的内容换成新的页面，挂到相应的链表上去。最后我们读入所指定操作，然后将所需要的数据打印到屏幕上。操作分两种，读和写，分别用0和1表示，指定了页号。通过遍历哈希表找到相应页号对应的页框，直接从内存中读取数据，并且修改使用时间和是否为脏。如果指定页号没有相应的页框，证明数据并不在内存中，我们需要从硬盘上读取数据，

5、如果buffei没有满，直接计算槽号,挂到相应的队列中。如果页框己用完，通过ecentused数据，置换最近最久没有使用的页面，把新页面挂到相应的哈希链表上去，用BCB记录该页框的信息。操作完成后我们需要计算从磁盘上读取的次数和从buffer中读取的次数，依此来计算buffer命中率。丿USTCSchoolofSofhvaieEngmeenngZhangYiie4概要设计根据设计思路，我们设计了如下的数据结构：bFrame：就是一个1024大小的页面structbFramecharfieldFrameSize;BCB：用來记录页框信息的结构体structBCBintpage_id;/页面号in

6、tframe_id;/页框号intcount;intlatch;unsigned_int64usedtime;/该页最近的使用时间intdirty/是否为脏，脏就要写回BCB*next;/;链向下一个BCB；classFilepublic:FILE*file;intdirsize;/文件目录大小intpagesize;/页面大小intposDataStart;/数据起始位置intpage_count;/页面数File()File(constchar*filename,int*dir);voidcreate();/用來初始化创建一个50000页面的文件voidclose(int*dir);/关闭

7、时保存文件信息；DSMgr:classDSMgrprivate:File*currFile;丿USTCSchoolofSofhvaieEngmeenngZhangYiieintnumPages;/所含页面数intpagesMAXPAGES;intDisklOCount;/记录磁盘10数public:DSMgr();intOpenFile(char*filename=data.dbf);/打开文件，默认为data.dbfvoidCloseFile();/关闭文件并保存信息voidReadPage(bFrame*frame,intpage_id);/从磁盘读取页面写到页框中一voidWritePa

8、ge(intpage_idjbFrame*frm);/将页框中的内容写到磁盘中intget_DiskIOCount();/返回命中次数；classBMgrprivate:DSMgrdsmgr;intnum_free_frames;/记录空闲页框数intftopBufferSize;/页框到页号的哈希表BCB*ptofBufferSize;/页号到页框号的哈希表bFramebufBufferSize;/buffer缓存装1024个页面inthitCount;/命中次城public:BMgr();intget_hitCount();/返回命中次数intget_diskIoCount();/返回磁盘

9、10次数bFrame&Read(intpage_id);/返回页号对应的页框voidRemoveBCB(BCB*ptr);/移除BCB块voidWrite(intpage_id?bFrame&input);BCB*SelectVictim();/选择要被置换出的页面BCB*Hash(intpage_id);/做页号到页框号的映射intFixPage(intpage_id,intRorW);/根据页号找到对应页框号，在内存中读取文件voidWriteDirtys();/将脏位为1的页框内容写回对应页；详细函数实现代码见附录丿USTCSchoolofSofhvaieEngmeenngZhangYi

10、ieiliiiiiuPressCDI回5实验结果及分析我们先调用File类的create方法,使其生成一个50000页的文件，在文件的第一页写入了目录。之后我们注释掉czte语句，直接读取文件内容进行实验，执行结果如图4.1所示：E:ustcstudydatabasesystemlab2str_buf_mgrDebugstr_buf_mgrxetotalI/Os:341570overallhitnumberInthebuffer：169565overallhitratiointhebuffer：33.913000overallruntimeforthetrace-driuenexperimen

11、t：4sanykeytocontinue.图4.1实验结果根据上图我们可知LRU算法，对文件进行给定操作，命中率大概在33.9%,其中10次数341570,Buffer命中次数169565。总共执行实验时间4s（在CPU为17-3520条件下）扩展性测试,如果把buffer大小改大一倍,即buffersize=2048,此时LRU算法的命中率应该明显上升，如图42所示:E:ustcstudydatabasesystemlab2str_buf_mgrDebugstr_buf_mgr.exeitotalI/Os：302977iioverallhitnumberinthebuffer：209569i

12、iioverallhitratiointhebuffer：41.913800iuouerallruntineforthetrace-driuenexperiment：8sPressanykeytocontinue.图42buffersize=2048时x-xUSTCSchoolofSofhvaieEngmeenngZhangYiie结果分析：我们不难发现，当buffersize设置为2048时，LRU的命中率达到了4：L9：L%,不难知道，LRU在buffer变大时，页面的置换没有那么频繁，不容易产生缺页，所以命中率明显提高。另外我们可以看到在图4.1中，命中buffer的次数是169565次

13、，10次数是341570,两者加起來大于500000次操作，原因很简单。我们把操作分为下面四种情况：先读再读：这样第二次读写时页面在buffer中节省io先写再写：这时两次写操作合并为对磁盘的一次写节省io先写再读：第二次读操作在buffer中节省io先读再写：这种情况下还是2次io操作没有节省io故所有的操作结果要大于500000次6总结及致谢本次实验让我们从底层了解了一个DBMS的管理策略，包括目录式的存储数据，读出写入数据，用LRU算法查找页面，以及算法的性能分析等等。感谢助教老师和金老师提供的指导和帮助。（代码部分见附录）丿USTCSchoolofSofhvaieEngmeenngZh

14、angYiie7附录:代码部分：#include#include#include#defineFrameSize4096#defineBufferSize1024#defineMAXPAGES50000usingnamespacestd;inlineunsigned_int64GetCycleCount()_asm_emit0x0F_asm_emit0x31struetbFramecharfieldFrameSize;；structBCBintpage_id;intframe_id;intcount;intlatch;unsigned_int64usedtime;intdirty;BCB*ne

15、xt;；classFilepublic:FILE*file;intdirsize;intpagesize;intposDataSta厂t;丿USTCSchoolofSofhvaieEngmeenngZhangYiieintpage_count;File()File(constchar*filename,int*dir);voidcreate();voidclose(int*dir);；classDSMgrprivate:File*currFile;intnumPages;intpagesMAXPAGES;intDisklOCount;public:DSMgr();intOpenFile(cha

16、r*filenamedata.dbF);voidCloseFile();voidReadPage(bFrame*frame，intpage_id);voidWritePage(intpage_id,bFrame*frm);intget_DiskIOCount();；-classBMgrprivate:DSMgrdsmgr;intnumfTeef厂ames;intftopBufferSize;BCB*ptofBufferSize;/BufferbFramebufBufferSize;inthitCount;public:BMgr();intget_hitCount();intget_diskIo

17、Count();bFrame&Read(intpage_id);voidRemoveBCB(BCB*ptr);voidWrite(intpage_id，bFrame&input);BCB*SelectVictim();丿USTCSchoolofSofhvaieEngmeenngZhangYiieBCB*Hash(intpage_id);intFixPage(intpage_idintRorW);voidWriteDirtys();File:File(constchar*filename,int*dir)file=fopen(filename，rb+);fread(&dirsize,sizeof

18、(int),l/ile);fread(&pagesize，sizeof(int)，lfile);fread(&posDataStart,sizeof(int)，;fread(dir,sizeof(int),dirsize/sizeof(int),file);page_count=dirsize/sizeof(int);-voidFile:create()inttemp;FILE*file_t=fopen(data.dbfH,”wb+”);temp=4*50000;fwrite(&temp,sizeof(int)ljfile_t);temp=4096;fwrite(&temp,sizeof(in

19、t)ljfile_t);if(4*3+4*50000)%40960)temp=(4*3+4*50000)/4096+l;elsetemp=(4*3+4*50000)/4096;fwrite(&temp,sizeof(int)ljfile_t);intdir_t50000;for(inti=0;i50000;i+)dir_ti=i;-fwrite(ditsizeof(int)?50000，file_t);fseek(file_tJtemp*4096J0);charc_temp4096;for(inti=0;isizeof(int),dirsize/sizeof(int力file);fclose(

20、file);DSMgr:DSMgr()OpenFile();DiskIOCount=0;intDSMgr:OpenF订e(cha*filename)currFile=newFile(filename，pages);numPages=currFile-page_count;if(currFileI=NULL)return1;else厂eturn0;voidDSMgr:CloseFile()currFile-page_counumPages;currFile-dirsize=numPages*sizeof(int);if(sizeof(int)*3+sizeof(int)*numPages)%cu

21、rFile-pagesize0)currFile-posDataSta厂t=(sizeof(int)*3+sizeof(int)*cuFFile-pagesize)/FrameSize+l;elsecurrFile-posDataSta厂t=(sizeof(int)*3+sizeof(int)*cuFFile-pagesize)/FrameSize;currFile-close(pages);voidDSMgr:ReadPage(bFrame*frame，intpage_id)intoffset;厂eturnbufFixPage(page_idJ0);offset=pagespage_id;f

22、seek(currFile-fileJcurrFile-posDataStaFt+offset，0)；fread(framesizeof(bFrame)1currFile-file);voidDSMgr:WritePage(intpage_id,bFrame*frm)intoffset;DiskIOCount+;offset=pagespage_id-1;fseek(currFile-fileJcurrFile-posDataStaFt+offset，0)；fwrite(frmsizeof(bFrame)?1?currFi;intDSMgr:get_DiskIOCount()_厂eturnDi

23、sklOCount;BMgr:BMgr()num_free_fFameshBuffe厂Size;hitCount=0;for(inti=0;ibFrame&input)strcpy(bufFixPage(page_idJ1).fieldsinput.field);voidBMgr:RemoveBCB(BCB*ptr)BCB*p_temp=NULL;p_temp=ptofptrpage_id%Buffe厂Size;if(ptr=p_temp)-ptofptr-page_id%BufferSize=ptr-next;-elsewhile(p_temp-next!=pt)p_temp=p_temp-

24、next;p_temp-nexr-next;-BCB*BMgr:SelectVictim()BCB*p_temp=NULL?*min_p_temp=NULL;unsigned_int64min;min=GetCycleCount();min_p_temp二ptof0;for(inti=0;iusedtimeusedtime;-p_temp=p_temp-next;一一if(min_p_temp-diTty)-厂eturnbufFixPage(page_idJ0);USTCSchoolofSofhvaieEngmeenngZhangYiiedsmgr.WritePage(min_p_temp-p

25、age_id&bufmin_p_temp-fid)；一一一一-RemoveBCB(min_p_temp);ftopmin_p_temp-frame_id=-l;厂eturnmin_p_temp;一一BCB*BMgr:Hash(intpage_id)BCB*p_temp=NULL;p_temp=ptofpage_id%BufferSize;while(p_temp!=NULL)-if(p_temp-page_id=page_id)厂eturnp_temp;p_temp=p_temp-next;-returnNULL;intBMgr:FixPage(intpage_idintRorW)BCB*p_

26、temp=NULL;p_temp=Hash(page_id);if(p_temp!=NULL)fhitCount+;if(RorW)p_temp-dirtynRoFW;p_temp-usedtime=GetCycleCount();厂eturnp_temp-frame_id;一-elseif(num_free_frames0)一一num_free_frames-;for(inti=0;icounp_temp-dirty=RorW;p_temp-frame_id=i;p_temp-latch=0;p_temp-next=NULL;p_temp-page_id=page_id;p_temp-use

27、dtime=GetCycleCount();ftopi=page_id;p_temp-next=ptofpage_id%BufferSize;ptofpage_id%BufferSize=p_temp;if(RorW=0)dsmgrReadPage(&bufi，page_id);urni;elsep_temp=SelectVictim();ftopp_temp-仆ame_id=page_id;p_temp-count=1;p_temp-dirty=RoFW;p_temp-latch=0;p_temp-next=NULL;p_temp-page_id=page_id;p_temp-usedtit

28、CycleCount();p_temp-next=ptofpage_id%BufferSize;ptofpage_id%BufferSize=p_temp;if(RorW=0)dsmgr.ReadPage(&bufp_temp-fame_id，page_id);厂eturnp_temp-frame_id;一-voidBMgr:WriteDirtys()BCB*p_temp=NULL;USTCSchoolofSofhvaieEngmeenngZhangYiiefor(inti=0;idirty)-dsmgrWritePage(p_temp-page_idj&bufp_temp-frame_id)

29、;调用dsmgr的帧写回函竅p_temp=p_temp-next;一一dsmgr.CloseFile();intmain()Filefile;file.create();intpageid，io;BMgra;FILE*fp=fopen(data-5w-50w-zipf.txtrt);int*temp=NULL;bFrameinput;strcpy(input.fieldsIamanewpage);temp=(int*)(input.field+16);_int64freq=2.9E9cycle;cycle=GetCycleCount();inti;for(i=0;i500000&fp!=NUL

30、L;i+)fscarrf(fpd，cr，&io，&pageid);if(io=0)a.Read(pageid);else*temp=pageid;a.Write(pageid,input);a.WriteDi厂tys();cycle=(GetCycleCount()-cycle)/freq;printf(i)totalI/Os：%dn?a.get_diskIoCount();printf(”ii)overallhitnumberinthebuffer：%dn”，aget_hitCount();printf(iii)overailhitratiointhebuffer：%lf%n?(double)(a.get_hitCount()/i*100);printf(”iv)overall厂untimeforthetrace-drivenexperiment:%lldsncycle);system(”pause);厂eturn0;