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

USTC——SchoolofSoftwareEngineeringZhangYue数据库第二次实验实验名称：Buffer的存储及管理姓名：张悦学号：SA12226141实验时间：2012.11.16实验地点：明德楼308USTC——SchoolofSoftwareEngineeringZhangYue目录1实验背景..............................................32实验平台..............................................33设计思路..............................................34概要设计..............................................55实验结果及分析........................................76总结及致谢............................................87附录：................................................9USTC——SchoolofSoftwareEngineeringZhangYue1实验背景Inthisproject,wewillimplementasimplestorageandbuffermanager.Thedocumentaddressesthestorageandbuffermanager.Bufferandframesizes,bufferandframestoragestructures,pageformats,pagestoragestructures,fileformats,bufferingtechniques,hashingtechniques,filestoragestructures,andinterfacefunctionsforthediskspaceandbuffermoduleswillbediscussed.Theparticulartechniqueischosenfromthematerialcoveredinclassthatarerelevanttobufferandstoragemanager.2实验平台本实验采用Windows7Home+VisualStudio20123设计思路采用4096大小的页面，即FrameSize=4096，buffer中一共有1024个页面，即DefBufferSize=1024。开始在硬盘上存储50000个页，按目录形式存储，即第一页包含目录大小，第一页的起始位置，每一页的逻辑偏移量。其中buffer和disk的映射关系如图2.1所示：图2.1buffer和disk映射关系示意图USTC——SchoolofSoftwareEngineeringZhangYue我们用两个哈希表来映射页框号到页号，页号到页框号。方便系统的查找，其概要设计图2.2所示：图2.2HashTable设计图其中Ftop是一个一维数组，完成页框到页号的映射。Ptof是一个哈希链表，用来完成页号到页框的映射，上面的BCB是用来保存页框的信息的。置换的策略采用LRU：用recentused这个数据项记录最近使用的时间，遍历哈希表，找到最久没有使用的页框，把他的内容换成新的页面，挂到相应的链表上去。最后我们读入所指定操作，然后将所需要的数据打印到屏幕上。操作分两种，读和写，分别用0和1表示，指定了页号。通过遍历哈希表找到相应页号对应的页框，直接从内存中读取数据,并且修改使用时间和是否为脏。如果指定页号没有相应的页框，证明数据并不在内存中，我们需要从硬盘上读取数据，如果buffer没有满,直接计算槽号,挂到相应的队列中。如果页框已用完，通过recentused数据，置换最近最久没有使用的页面，把新页面挂到相应的哈希链表上去，用BCB记录该页框的信息。操作完成后我们需要计算从磁盘上读取的次数和从buffer中读取的次数，依此来计算buffer命中率。USTC——SchoolofSoftwareEngineeringZhangYue4概要设计根据设计思路，我们设计了如下的数据结构：bFrame：就是一个1024大小的页面structbFrame{charfield[FrameSize];};BCB：用来记录页框信息的结构体structBCB{intpage_id;//页面号intframe_id;//页框号intcount;intlatch;unsigned__int64usedtime;//该页最近的使用时间intdirty;//是否为脏,脏就要写回BCB*next;//;链向下一个BCB};classFile{public:FILE*file;intdirsize;//文件目录大小intpagesize;//页面大小intposDataStart;//数据起始位置intpage_count;//页面数File(){}File(constchar*filename,int*dir);voidcreate();//用来初始化创建一个50000页面的文件voidclose(int*dir);//关闭时保存文件信息};DSMgr:classDSMgr{private:File*currFile;USTC——SchoolofSoftwareEngineeringZhangYueintnumPages;//所含页面数intpages[MAXPAGES];intDiskIOCount;//记录磁盘IO数public:DSMgr();intOpenFile(char*filename=data.dbf);//打开文件，默认为data.dbfvoidCloseFile();//关闭文件并保存信息voidReadPage(bFrame*frame,intpage_id);//从磁盘读取页面写到页框中voidWritePage(intpage_id,bFrame*frm);//将页框中的内容写到磁盘中intget_DiskIOCount();//返回命中次数};classBMgr{private:DSMgrdsmgr;intnum_free_frames;//记录空闲页框数intftop[BufferSize];//页框到页号的哈希表BCB*ptof[BufferSize];//页号到页框号的哈希表bFramebuf[BufferSize];//buffer缓存,装1024个页面inthitCount;//命中次数public:BMgr();intget_hitCount();//返回命中次数intget_diskIoCount();//返回磁盘IO次数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的页框内容写回对应页};详细函数实现代码见附录USTC——SchoolofSoftwareEngineeringZhangYue5实验结果及分析我们先调用File类的create方法,使其生成一个50000页的文件,在文件的第一页写入了目录。之后我们注释掉create语句，直接读取文件内容进行实验，执行结果如图4.1所示：图4.1实验结果根据上图我们可知LRU算法，对文件进行给定操作，命中率大概在33.9%，其中IO次数341570，Buffer命中次数169565。总共执行实验时间4s（在CPU为I7-3520条件下）扩展性测试，如果把buffer大小改大一倍，即buffersize=2048，此时LRU算法的命中率应该明显上升，如图4.2所示：图4.2buffersize=2048时USTC——SchoolofSoftwareEngineeringZhangYue结果分析：我们不难发现，当buffersize设置为2048时，LRU的命中率达到了41.91%,不难知道，LRU在buffer变大时，页面的置换没有那么频繁，不容易产生缺页，所以命中率明显提高。另外我们可以看到在图4.1中，命中buffer的次数是169565次，IO次数是341570，两者加起来大于500000次操作，原因很简单。我们把操作分为下面四种情况：先读再读：这样第二次读写时页面在buffer中节省io先写再写：这时两次写操作合并为对磁盘的一次写节省io先写再读：第二次读操作在buffer中节省io先读再写：这种情况下还是2次io操作没有节省io故所有的操作结果要大于500000次6总结及致谢本次实验让我们从底层了解了一个DBMS的管理策略，包括目录式的存储数据，读出写入数据，用LRU算法查找页面，以及算法的性能分析等等。感谢助教老师和金老师提供的指导和帮助。（代码部分见附录）USTC——SchoolofSoftwareEngineeringZhangYue7附录：代码部分：#includecstdio#includecstring#includecstdlib#defineFrameSize4096#defineBufferSize1024#defineMAXPAGES50000usingnamespacestd;inlineunsigned__int64GetCycleCount(){__asm_emit0x0F__asm_emit0x31}structbFrame{charfield[FrameSize];};structBCB{intpage_id;intframe_id;intcount;intlatch;unsigned__int64usedtime;intdirty;BCB*next;};classFile{public:FILE*file;intdirsize;intpagesize;intposDataStart;USTC——SchoolofSoftwareEngineeringZhangYueintpage_count;File(){}File(constchar*filename,int*dir);voidcreate();voidclose(int*dir);};classDSMgr{private:File*currFile;intnumPages;intpages[MAXPAGES];intDiskIOCount;public:DSMgr();intOpenFile(char*filename=data.dbf);voidCloseFile();voidReadPage(bFrame*frame,intpage_id);voidWritePage(intpage_id,bFrame*frm);intget_DiskIOCount();};classBMgr{private:DSMgrdsmgr;intnum_free_frames;intftop[BufferSize];BCB*ptof[BufferSize];//BufferbFramebuf[BufferSize];inthitCount;public:BMgr();intget_hitCount();intget_diskIoCount();bFrame&Read(intpage_id);voidRemoveBCB(BCB*ptr);voidWrite(intpage_id,bFrame&input);BCB*SelectVictim();USTC——SchoolofSoftware