一个现代的数据库构造十分复杂，包含了诸多个模块之间的精密配合。其中，缓冲区是一个十分重要的模块。
学习过CSAPP课程的人肯定记得存储器架构的一个原理：使用容量较小的高速存储器，作为容量较大的低速存储器的高速缓存，这样就能用较低的成本达到较高的性能。
数据库系统中，磁盘IO的龟速导致了极大的开销。因此，使用缓冲区能使得许多本来要IO的情况变成直接在内存中操作，极大提升性能。由于缓冲区不命中的惩罚太高（5ms左右），缓冲区的性能取决于命中率。
理解缓冲区的运作机制，对于进一步认识操作系统的存储器架构有着很大的帮助。在实现一个缓冲区的过程中，也会使用到这些技术。
一、 Buffer管理器原理
DBMS系统中，诸如查询等过程直接使用到的数据位于内存的缓冲区中，而不是直接进行磁盘IO。缓冲区管理器为数据库的上层查询等过程提供了可用的内存缓冲区，其实现依赖更底层的存储管理，在DBMS架构中间位置。
Paste_Image.png
如图，缓冲区是内存中的一片区域，用于程序和磁盘交换数据。缓冲区被划分成了许多大小相同的帧（frame），一般情况下每个帧的大小和一个磁盘块（页）相等。当磁盘的页被缓存到缓冲区，DBMS用到的数据可以直接从缓冲区进行获取。如果请求的数据未能在缓冲区中找到，那么缓冲区将调用存储管理从磁盘中缓存请求数据的页。对数据进行的修改也同样是在缓冲区里做修改，并标记该页为脏数据。脏数据在清空缓冲区以及页替换的时候必须被写回磁盘。由于缓冲区大小有限，磁盘文件的页可能远多于缓冲区的大小，因此缓冲区很可能会满，此时无法缓存从磁盘来的数据，必须选择一个已缓存的页进行替换。替换策略对于缓存的性能会有很大的影响，本实验使用LRU——最近最少使用算法，进行页的替换。
Paste_Image.png
实验中采取静态哈希，将磁盘中的页和缓冲区的帧关联起来。需要维护两个列表（可以理解为数组）：ptof（page到frame）和ftop（frame到page）。 ftop列表中下标为frame_id的元素ftop[frame_id] ，即为帧frame_id中所存储页的page_id。ptof列表中的项都为指向BCB的指针，由于page远比frame多，实际需要使用哈希函数H(k) = (page_id)%buffer_size。例如下标为h(k)的元素ptof [ h(k) ] ，是一个指针，指向一个描述frame的结构体，结构体对应的frame中缓存了page_id对应的页。由于可能有多个page的h(k)值相同，实际上ptof 中的项是一个指向链表的头部的指针，链表中的节点是映射到相同h(k)的page对应BCB的指针。Ftop和ptof两个列表都是构造函数中动态分配的，长度和缓冲区相同，可以在程序中可以自行设定。详细的实现参考代码。
在这个实验中，代码实现了简单的存储和缓冲区管理器，并根据一个测试用例文件来模拟随机读写的过程，统计该过程中缓冲区的命中次数以及磁盘IO次数、总计读写时间，并在此基础上计算出平均IO时间和命中率，用来评估缓冲区的性能。由于缓冲区大小可以自行设定，本实验还比较了不同缓冲区大小情况下的命中率等性能指标。
本实验中涉及到的主要知识包括：缓冲区和帧的大小、帧的存储结构、 页的大小和格式、 页的存储结构、 文件格式、 缓冲技术、 哈希技术、 文件存储结构、磁盘空间和缓冲区管理模块的接口函数。
此外，关于缓冲区有以下两个设定:
- Buffer的frame大小和文件的page大小是一致的，均为4096字节
- buffer的大小动态分配，可以在程序中修改参数设定，默认为1024个frame
二、 Buffer管理器实现
本部分是对代码的整体分析，包括类的设计和一些主要函数的实现。
2.1 BMgr类的实现
Bmgr类即为缓冲区管理类，提供了缓冲区读写以及缓存页面管理等功能，依赖存储管理类实现从磁盘缓存页的功能。类的原型如下：
class BMgr//此类提供缓冲区管理
{
public:
BMgr(int bufsize);//初始化哈希表，实例化一个LRU对象，分配缓冲区的frame空间
~BMgr();
//外部接口
int FixPage(int page_id, int prot);
int FixNewPage(int page_id);
int WritePageBuf(int page);
int UnfixPage(int page_id);
int NumFreeFrames();
//内部调用的函数
BCB * GetBCBByPage(int page_id);
int SelectVictim();
int Hash(int page_id);
void RemoveBCB(int page_id);
void RemoveLRUEle();
void SetDirty(int frame_id);
void UnsetDirty(int frame_id);
void WriteDirtys();
void PrintFrame(int frame_id);
DSMgr storage;
LRU *lru;//用于处理替换frame的LRU指针
bFrame *buf;//缓冲区的实例，数组成员是bFrame结构体
//哈希表，用于frame和page的双向映射
private:
int DEFBUFSIZE;
int * ftop;//frame到page的映射
BCB** ptof;//page到frame（对应BCB指针）的映射
};
类中的ptof和ftop是两个指针，和前面所述的列表有所区别。实际上，用该类创建对象的时候执行构造函数，自动为这两个指针动态分配初始值。随后，就可以搭配哈希函数，像使用列表一样使用这两个指针。实例化了一个DSMgr对象，用于底层的数据存取（磁盘IO）。Lru指向一个LRU对象，用于实现缓冲区中的页替换策略。buf是一个动态分配的数组，用于存储从磁盘缓存的页，即缓冲区。
BMgr类中定义的重要的函数意义如下：
- BMgr(int bufsize);
初始化BMgr类的对象，创建哈希表，实例化一个LRU对象，分配缓冲区的frame空间 - ~BMgr();
清空缓冲区前的操作，包括：回写所有脏数据，删除哈希表，删除buf，删除所有BCB结点，释放LRU对象（触发LRU的析构函数，清空LRU中的链表） - int FixPage(int page_id, int prot);
读取缓冲区中page_id指定的页，如果缓冲区中不存在，那么从磁盘缓存该页再读取。缓冲区如果满了，执行替换策略。 - int WritePageBuf(int page);
向缓冲区中的page指定的页写数据，如果该页不存在，那么就调用FixPage缓存该页，之后再写数据。 - int NumFreeFrames();
在缓存中找到一个可用的frame，并返回frame_id - BCB * GetBCBByPage(int page_id);
通过page_id找到对应的BCB结构体，返回其指针。 - int SelectVictim();
使用LRU算法在缓冲区中找一个页面，并替换掉。 - int Hash(int page_id);
p使用page_id找到在缓冲区中的frame_id - void RemoveBCB(int page_id);
从缓冲区中删除page_id指定的页，如果是脏数据那么就写回磁盘。 - void SetDirty(int frame_id);
将帧frame_id中的脏数据强行写回磁盘。 - void WriteDirtys();
将所有脏数据写回磁盘，用于清空缓冲区以及关闭系统时使用。
2.2 DSMgr类的实现
Bmgr类即为存储管理类，提供了磁盘块读写等功能，直接和底层的磁盘交互，并为上层的缓冲区管理类提供支持。实际上，此实验中并未执行真正的磁盘块读写，因此这个类只具有形式上的完备，供BMgr调用。类的原型如下：
class DSMgr//"DataStorage"类，提供数据存取的功能
{
public://外部接口
DSMgr();
int OpenFile(string filename);
int CloseFile();
void ReadPage(int page_id);
int WritePage(int frame_id);
int Seek(int offset, int pos);
void GetFile();
void IncNumPages();
int GetNumPages();
void SetUse(int index, int use_bit);
bool GetUse(int page_id);
private:
fstream file;
int numPages;
int pages[MAXPAGES];
};
这个模块中最重要的函数是以下几个：
- void ReadPage(int page_id);
缓冲区管理器调用该函数从磁盘中读取对应的页，每调用一次IO计数+1。 - int WritePage(int frame_id);
缓冲区管理器调用该函数将当前帧的内容写到对应的磁盘块中，每调用一次IO计数+1。 - bool GetUse(int page_id);
利用该函数查询磁盘文件中页号为page_id的磁盘块时候存在，这在修改页的时候需要使用到。
2.3 LRU类的实现
LRU类为缓冲区中基于LRU算法的页替换机制提供了支持。 提供了磁盘块读写等功能，直接和底层的磁盘交互，并为上层的缓冲区管理类提供支持。类的原型如下：
class LRU//LRU类提供缓冲区中frame的替换策略
{
private:
LRUNode * head;//头指针，在此处删除
LRUNode * rear;//尾指针，在此处插入
public:
LRU();
void MoveToRear(int page_id);
int DeleteHead();
void InsertRear(int page_id);
~LRU();
};
类中提供了一个头指针head和尾指针rear，分别指向链表的头部和尾部，初始化状态下两个指针都为NULL。链表结点如下：
struct LRUNode//LRU算法中队列中的节点
{
LRUNode *next;
int page_id;//此节点对应的page
LRUNode(LRUNode* ptr, int page) { next = ptr; page_id = page; }
};
链表中的数据域包含该节点对应页的page_id，指针域指向下一个结点。链表提供的构造函数必须包含两个参数，一个是该结点的next指针（新创建结点时一般为空），另一个是当前结点的page_id(不能缺)。
***LRU类实例化对象辅助BMgr类进行缓存页面替换，提供了3个接口：***
void MoveToRear(int page_id);
将page_id对应的结点移到链表的尾部（链表每次删除结点都是从首部开始）。缓存中page_id对应的页如果被读写，那么对应的结点移到尾部，表示该结点应该最后被删除。int DeleteHead();
从链表首部删除一个结点，并返回该结点对应的page_id。首部的结点肯定是最近最少使用的，需要置换页面时直接删除对应结点即可，同时返回page_id供其他函数完成删除页面的其他操作。void InsertRear(int page_id);
当新的页面被缓存到缓冲区的时候，需要在链表尾部插入一个新的结点，将该页面用LRU的方式管理起来。
特别注意的时，LRU类的对象生命周期结束时，需要清理掉链表中动态生成的结点，否则会造成内存泄漏。这一工作在的析构函数~LRU（）中反复调用DeleteHead()函数即可，直到所有结点完全释放。
2.4 BCB结构体
每一个BCB结构体为缓冲区中的一个帧（frame）提供了附加的状态信息，对缓冲区的管理正是基于BCB。由于多个page的哈希值可能相同，因此BCB组织成链表，哈希值相同的page的缓存帧对应的BCB在同一个链表中。结构体的定义如下：
struct BCB//哈希表的节点指向该类节点，记录了frame的状态信息
{
int page_id;//当前BCB对应帧的frame_id
int frame_id;//当前BCB对应帧中缓存页的页号
bool latch;//锁定状态，本实验改良了LRU没用到
int count;//引用计数，本实验改良了LRU没用到
bool dirty;// true表示当前缓存的页中的数据被修改，需要写回磁盘
BCB * next;//指向下一个相同哈希值的BCB结点
//BCB结构体只能以带参构造函数进行初始化
BCB(int a, int b, bool c, int d, bool e, BCB *f);
};
注：完整的代码以及注释参考打包的文件，此外，打包文件中还包含了一个可以直接运行的release版本的.exe程序（运行时测试文件data-5w-50w-zipf.txt必须和.exe位于同一路径，且测试文件不能为别的命名）。实验代码是在Visual Studio中编写并完成测试，重复验证请使用相同的环境。
2.5 其它函数
- io_count：全局变量结构体，用于记录程序运行时间，IO次数，命中次数等信息。
- test（int bufsize）函数：需要给定参数buf，用于在缓冲区大小为bufsize情况下运行测试缓冲区管理模块的性能。测试方法是逐行读取和解析给定的data-5w-50w-zipf.txt文件，模拟读写数据，并记录缓冲区的行为。具体代码见附件打包。
void test(int bufsize)
{
io_count.IO_init();//初始化统计信息的io_count结构体
io_count.start_time = clock();//开始计时
BMgr buffer(bufsize);
string trace_temp;
ifstream file("data-5w-50w-zipf.txt");
while (!file.eof())//逐行读取文件进行解析，根据解析的结果进行读写
{
//
}
file.close();
io_count.end_time = clock();//计时结束
IOCount(bufsize);//打印IO情况的统计
}
- Main()函数：主函数中分别在缓冲区大小为32，64，128，……，4096，8192的情况下测试了缓冲区管理模块的性能。
int main()
{
cout << "盛广智 软设3班 SA16225249 缓冲区管理器实验演示demo" << endl;
for(int i=5;i<14;++i)
{
test(pow(2, i));//依次测试缓冲区大小为32，64，……，8192时候的性能
}
cin.get();
return 0;
}
三、 测试运行结果
代码编写完成后，直接生成解决方案即可开始编译。编译完成后，直接Ctrl+F5即可开始运行，实际运行结果如下图所示：
Paste_Image.png
四．结果分析
实验结果的关键数据为平均读写时间和命中率，汇总如表格所示：
| 缓冲区大小（frame） | 平均读写时间（ms） | 命中率 |
|---|---|---|
| 32 | 9.48043 | 7.14% |
| 64 | 9.0925 | 11.13% |
| 128 | 8.6381 | 15.75% |
| 256 | 8.12124 | 20.94% |
| 512 | 7.51641 | 26.96% |
| 1024 | 6.81362 | 33.91% |
| 2048 | 6.00701 | 41.91% |
| 4096 | 5.07932 | 51.09% |
| 8192 | 4.00322 | 61.75% |
根据表格中的数据画出曲线图，结果如下所示：
Paste_Image.png
通过观察上图可知，随着缓冲区的增大，命中率会逐渐上升，平均读写时间逐渐下降。尤其是在缓冲区很小时，增加缓冲区可以显著提升命中率，极大的改善平均读写时间。当缓冲区较大时，继续增大缓冲区容量带来的收益逐渐减小。
出现以上现象的原因是：当读写一个页时，首先在缓冲区搜索，如果找不到则需要从磁盘缓存该页到缓冲区，之后再在缓冲区中读写。因此，增加缓冲区容量可以使得更多的磁盘块被保存在内存中，从而使得命中率上升。一般而言，磁盘IO的代价比起内存的读写高1000倍，提高命中率可以有效减少磁盘IO次数，从而使得平摊到每次读写的时间减少。
实际上，缓冲区增大使得维护的成本升高，主要是维护哈希表的代价和维护LRU链表的代价会随着缓冲区增加而线性增长。但是，相比磁盘IO的延迟时间，这些开销基本可以忽略不计。但是，一般数据库文件可能比内存大很多，缓存大小相比数据库而言很小，这时存储的空间局部性的好坏对于命中率影响很大。
一般意义上，类似操作系统这种对于缓存性能极度敏感的场合，需要通过预取等办法，将命中率提高到99%甚至更高（缓存不命中惩罚非常高，99%和98%命中的性能可能会差一倍）。
附件：完整版代码
#include <iostream>
#include <fstream>
#include <string>
#include <math.h>
#include <time.h>
using namespace std;
struct IO//用来记录在模拟buffer过程中文件IO（读/写）以及buffer命中的次数
{
int read_count;
int write_count;
int read_io;
int write_io;
int read_hit;
int write_hit;
clock_t start_time;
clock_t end_time;
float io_delay;//此变量计数磁盘IO的时间，单位ms（实验仅模拟了IO的效果，并没有真正的读写数据库的磁盘块）
void IO_init()
{
read_count = 0;
write_count = 0;
read_hit = 0;
write_hit = 0;
read_io=0;
write_io=0;
start_time = 0;
end_time = 0;
io_delay = 0;
}
};
IO io_count;//用于技术的全局对象（IO结构体的实例）
const int FRAMESIZE = 4096; //每个frame的字节大小
const int MAXPAGES = 50000; //每个文件包含最多的page数
struct BCB//哈希表的节点指向该类节点，记录了frame的状态信息
{
int page_id;
int frame_id;
bool latch;//锁定
int count;
bool dirty;
BCB * next;
//BCB结构体只能以带参构造函数进行初始化
BCB(int a, int b, bool c, int d, bool e, BCB *f)
{
page_id = a;
frame_id = b;
latch = c;
count = d;
dirty = e;
next = f;
}
};
struct page
{
int page_id;
int page_size;
};
struct bFrame//frame的具体结构定义
{
char field[FRAMESIZE];
};
struct LRUNode//LRU算法中队列中的节点
{
LRUNode *next;
int page_id;//此节点对应的page
LRUNode(LRUNode* ptr, int page) { next = ptr; page_id = page; }
};
class LRU//LRU类提供缓冲区中frame的替换策略
{
private:
LRUNode * head;//头指针，在此处删除
LRUNode * rear;//尾指针，在此处插入
public:
LRU();
void MoveToRear(int page_id);
int DeleteHead();
void InsertRear(int page_id);
~LRU();
};
class DSMgr//"DataStorage"类，提供数据存取的功能
{
public://外部接口
DSMgr();
int OpenFile(string filename);
int CloseFile();
void ReadPage(int page_id);
int WritePage(int frame_id);
int Seek(int offset, int pos);
void GetFile();
void IncNumPages();
int GetNumPages();
void SetUse(int index, int use_bit);
bool GetUse(int page_id);
private:
fstream file;
int numPages;
int pages[MAXPAGES];
};
class BMgr//"Buffer"类，提供缓冲区管理
{
public:
BMgr(int bufsize);
~BMgr();
//外部接口
int FixPage(int page_id, int prot);
int FixNewPage(int page_id);
int WritePageBuf(int page);
int UnfixPage(int page_id);
int NumFreeFrames();
//内部调用的函数
BCB * GetBCBByPage(int page_id);
int SelectVictim();
int Hash(int page_id);
void RemoveBCB(int page_id);
void RemoveLRUEle();
void SetDirty(int frame_id);
void UnsetDirty(int frame_id);
void WriteDirtys();
void PrintFrame(int frame_id);
DSMgr storage;
LRU *lru;//用于处理替换frame的LRU指针
bFrame *buf;//缓冲区的实例，数组成员是bFrame结构体
//哈希表，用于frame和page的双向映射
private:
int DEFBUFSIZE;
int * ftop;//frame到page的映射
BCB** ptof;//page到frame（对应BCB指针）的映射
};
void IOCount(int bufsize)
{
int total = io_count.read_count + io_count.write_count;
double average_time = (1000 * (double)(io_count.end_time - io_count.start_time) / (CLOCKS_PER_SEC * total)) + ( io_count.io_delay / total );
float hitrate = (io_count.read_hit +io_count.write_hit)/ total;
cout<<"*****************************************************************************************************"<<endl;
cout << "缓冲区大小： " << bufsize;
cout << "\t\t读IO： " << io_count.read_io;
cout << "\t写IO： " << io_count.write_io<< endl;
cout << "读page次数： " << io_count.read_count;
cout << "\t写page次数： " << io_count.write_count;
cout << "\t读page命中： " << io_count.read_hit;
cout << "\t\t写page命中： " << io_count.write_hit<<endl;
cout << "读写总数： " << total;
cout << "\t命中总数： " << io_count.read_hit+io_count.write_hit;
cout << "\t平均读写时间： " << average_time <<" ms";
cout << "\t命中率： " << 100*((float)(io_count.read_hit+io_count.write_hit)) / (io_count.read_count + io_count.write_count)<<" % "<< endl;
cout << "***************************************************************************************************" << endl;
}
void test(int bufsize)
{
io_count.IO_init();//初始化统计信息的io_count结构体
io_count.start_time = clock();//开始计时
BMgr buffer(bufsize);
string trace_temp;
ifstream file("data-5w-50w-zipf.txt");
while (!file.eof())//逐行读取文件进行解析，根据解析的结果进行读写
{
getline(file, trace_temp);
string method = trace_temp.substr(0, 1);//'0'读取page,1'写回page
int page = stoi(trace_temp.substr(2));
if (method == "0")
{
++io_count.read_count;
int frame = buffer.FixPage(page, 0);
}
else
{
++io_count.write_count;
int frame = buffer.WritePageBuf(page);
}
}
file.close();
io_count.end_time = clock();//计时结束
IOCount(bufsize);//打印IO情况的统计
}
int main()
{
cout << "XXX 软设3班 SA16225XXX 缓冲区管理器实验演示demo" << endl;
for(int i=5;i<14;++i)
{
test(pow(2, i));//依次测试缓冲区大小为32，64，……，8192的时候的命中率和平均时间
}
cin.get();
return 0;
}
//以下是BMgr类成员函数的实现
BMgr::BMgr(int bufsize)
{
DEFBUFSIZE = bufsize;
ftop=new int [DEFBUFSIZE];//frame到page的映射
ptof=new BCB* [DEFBUFSIZE];//page到frame（对应BCB指针）的映射
for (int i = 0; i<DEFBUFSIZE; ++i)
{
ftop[i] = -1;//初始化frame到page映射的哈希表，全部置为-1，表示为空
ptof[i] = NULL;//初始化page到frame映射的哈希表，全部置为NULL，表示为空指针
}
lru = new LRU();
buf = new bFrame[DEFBUFSIZE];
}
BMgr::~BMgr()
{
WriteDirtys();//关闭buffer之前必须写回所有的脏数据
for (int i = 0; i < DEFBUFSIZE; ++i)
{
if ((ftop[i]) != -1)
{
int page = ftop[i];
RemoveBCB(page);
}
}
delete ptof;
delete ftop;
delete lru;
delete buf;
}
BCB * BMgr::GetBCBByPage(int page_id)
{
BCB * ptr = ptof[page_id % DEFBUFSIZE];
while(ptr!=NULL)
{
if (ptr->page_id == page_id)
{
return ptr;
}
else
{
ptr = ptr->next;
}
}
return NULL;
}
int BMgr::FixPage(int page_id, int prot)
{
BCB *f_ptr = ptof[page_id % DEFBUFSIZE];
int frame_id = Hash(page_id);
if (frame_id == -1)
{
int freeframe = NumFreeFrames();
if (freeframe == -1)
{
SelectVictim();
freeframe = NumFreeFrames();
}
lru->InsertRear(page_id);
storage.ReadPage(page_id);
f_ptr = ptof[page_id % DEFBUFSIZE];
if (f_ptr == NULL)
{
ptof[page_id % DEFBUFSIZE] = new BCB(page_id, freeframe, true, 0, false, NULL);
}
else
{
while (f_ptr->next != NULL)
{
f_ptr = f_ptr->next;
}
f_ptr->next = new BCB(page_id, freeframe, true, 0, false, NULL);
}
ftop[freeframe] = page_id;
frame_id = freeframe;
}
else
{
io_count.read_hit++;
lru->MoveToRear(page_id);
while (f_ptr != NULL)
{
if (f_ptr->page_id == page_id)
{
f_ptr->count = 0;
if (f_ptr->count == 0)
{
f_ptr->latch = true;
}
return f_ptr->frame_id;
}
else
{
f_ptr = f_ptr->next;
}
}
}
return frame_id;
}
int BMgr::FixNewPage(int page_id)//如果要写的page在磁盘中是不存在的，那么生成新的page并放置缓冲区中，并设置该frame的dirty为true
{
BCB *f_ptr = ptof[page_id % DEFBUFSIZE];
int frame_id = NumFreeFrames();
if (frame_id == -1)
{
SelectVictim();
frame_id = NumFreeFrames();
}
lru->InsertRear(page_id);
f_ptr = ptof[page_id % DEFBUFSIZE];
if (f_ptr == NULL)
{
ptof[page_id % DEFBUFSIZE] = new BCB(page_id, frame_id, true, 0, false, NULL);
}
else
{
while (f_ptr->next != NULL)
{
f_ptr = f_ptr->next;
}
f_ptr->next = new BCB(page_id, frame_id, true, 0, false, NULL);
}
ftop[frame_id] = page_id;
SetDirty(frame_id);
return frame_id;
}
int BMgr::WritePageBuf(int page)
{
if (Hash(page) == -1)
{
if(storage.GetUse(page))
{
FixPage(page,0);
SetDirty(GetBCBByPage(page)->frame_id);
}
else
{
FixNewPage(page);
}
}
else
{
++io_count.write_hit;
lru->MoveToRear(page);
SetDirty(GetBCBByPage(page)->frame_id);
}
return GetBCBByPage(page)->frame_id;
}
int BMgr::UnfixPage(int page_id)//这个函数无用
{
BCB * f_ptr = ptof[page_id % DEFBUFSIZE];
while (f_ptr != NULL)
{
if (f_ptr->page_id == page_id)
{
if (f_ptr->latch)
{
(f_ptr->count)++;
if (f_ptr->count>0)
{
f_ptr->latch = false;
}
}
else
{
(f_ptr->count)++;
}
return f_ptr->frame_id;
}
else
{
f_ptr = f_ptr->next;
}
}
}
int BMgr::NumFreeFrames()
{
int i = 0;
while ((ftop[i] != -1) && (i<DEFBUFSIZE))
{
++i;
}
if (i == DEFBUFSIZE)
{
return -1;
}
else
{
return i;
}
}
int BMgr::SelectVictim()
{
int del_page = lru->DeleteHead();
if (GetBCBByPage(del_page)->dirty == true)
{
storage.WritePage(GetBCBByPage(del_page)->frame_id);
}
RemoveBCB(del_page);
//RemoveLRUEle();
return 0;
}
int BMgr::Hash(int page_id)//根据page_id找到frame_id
{
BCB* frame_ptr = ptof[page_id % DEFBUFSIZE];
while (frame_ptr != NULL)
{
if (frame_ptr->page_id == page_id)
{
return frame_ptr->frame_id;
}
else
{
frame_ptr = frame_ptr->next;
}
}
return -1;
}
void BMgr::RemoveBCB(int page_id)
{
BCB * ptr = ptof[page_id % DEFBUFSIZE];
if (ptr->page_id == page_id)
{
ptof[page_id % DEFBUFSIZE] = ptof[page_id % DEFBUFSIZE]->next;
ftop[ptr->frame_id] = -1;
delete ptr;
}
else
{
while (ptr->next != NULL)
{
if (ptr->next->page_id == page_id)
{
BCB *tmp = ptr->next;
ptr->next = ptr->next->next;
ftop[tmp->frame_id] = -1;
delete tmp;
}
else
{
ptr = ptr->next;
}
}
}
}
void BMgr::RemoveLRUEle()//使用LRU算法从buffer删除一个page
{
bool delete_tag = false;
int LRUpage = -1;//用来记录LRU算法删除的page号码
int LRUcount = 0;//用来记录LRU算法删除page的对应frame的count，始终记录最大值
for (int i = 0; i<DEFBUFSIZE; ++i)
{
BCB *ptr = ptof[i];
while (ptr != NULL)
{
if (ptr->latch == false)
{
if (ptr->count > LRUcount)
{
LRUpage = ptr->page_id;
LRUcount = ptr->count;
}
ptr = ptr->next;
}
else
{
ptr = ptr->next;
}
}
}
if(delete_tag!=true)
{
RemoveBCB(LRUpage);
}
}
void BMgr::SetDirty(int frame_id)////将frame对应的BCB结构体中的dirty置为true
{
GetBCBByPage(ftop[frame_id])->dirty = true;
}
void BMgr::UnsetDirty(int frame_id)//将frame对应的BCB结构体中的dirty置为false
{
//
}
void BMgr::WriteDirtys()//脏数据全部写回磁盘文件，清空缓冲区/关闭数据库要用到
{
for(int i=0;i<DEFBUFSIZE;++i)
{
int page = ftop[i];
if (page != -1)
{
if (GetBCBByPage(page)->dirty == true)
{
storage.WritePage(GetBCBByPage(page)->frame_id);
GetBCBByPage(page)->dirty = false;
}
}
}
}
void BMgr::PrintFrame(int frame_id) //打印当前frame的数据，这个实验模拟缓冲区的特性，不涉及具体数据
{
//
}
//以下是DSMgr类中成员函数的实现
DSMgr::DSMgr() {}
int DSMgr::OpenFile(string filename) { return 0; }
int DSMgr::CloseFile() { return 0; }
void DSMgr::ReadPage(int page_id)
{
io_count.read_io++;
io_count.io_delay += 8.16;
}
int DSMgr::WritePage(int frame_id)
{
io_count.write_io++;
io_count.io_delay += 4.08;
return 0;
}
int DSMgr::Seek(int offset, int pos) { return 0; }
void DSMgr::GetFile() {}
void DSMgr::IncNumPages() {}
int DSMgr::GetNumPages() { return 0; }
void DSMgr::SetUse(int index, int use_bit) {}
bool DSMgr::GetUse(int index)
{
return true;
}
//以下是LRU类的实现，一种用于置换page的策略
LRU::LRU()
{
head = NULL;
rear = NULL;
}
void LRU::MoveToRear(int page_id)
{
if (head != rear)
{
if (head->page_id == page_id)
{
InsertRear(DeleteHead());
}
else
{
LRUNode *ptr = head;
while ((ptr->next != NULL) && (ptr->next->page_id != page_id))
{
ptr = ptr->next;
}
if (ptr->next->page_id == page_id)
{
if (ptr->next->next != NULL)
{
LRUNode *tmp = ptr->next;
ptr->next = ptr->next->next;
InsertRear(page_id);
delete tmp;
}
}
}
}
}
int LRU::DeleteHead()
{
if ((head == NULL) && (rear == NULL))
{
return -1;
}
else if (rear == head)
{
LRUNode *tmp = head;
int page = tmp->page_id;
head = NULL;
rear = NULL;
delete tmp;
return page;
}
else
{
LRUNode *tmp = head;
head = head->next;
int page = tmp->page_id;
delete tmp;
return page;
}
}
void LRU::InsertRear(int page_id)
{
if ((head == NULL) && (rear == NULL))
{
rear = new LRUNode(NULL, page_id);
head = rear;
}
else
{
rear->next = new LRUNode(NULL, page_id);
rear = rear->next;
}
}
LRU::~LRU()
{
while (DeleteHead() != -1) {}
}
