数据库管理系统的实现——缓冲区管理器

2017-02-08 本文已影响0人夏木与晴空

一个现代的数据库构造十分复杂，包含了诸多个模块之间的精密配合。其中，缓冲区是一个十分重要的模块。
学习过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) {}
}

数据库管理系统的实现——缓冲区管理器

一、 Buffer管理器原理

二、 Buffer管理器实现

2.1 BMgr类的实现

2.2 DSMgr类的实现

2.3 LRU类的实现

2.4 BCB结构体

2.5 其它函数

三、测试运行结果

四．结果分析

附件：完整版代码

猜你喜欢

热点阅读

数据库管理系统的实现——缓冲区管理器

一、 Buffer管理器原理

二、 Buffer管理器实现

2.1 BMgr类的实现

2.2 DSMgr类的实现

2.3 LRU类的实现

2.4 BCB结构体

2.5 其它函数

三、 测试运行结果

四．结果分析

附件：完整版代码

猜你喜欢

热点阅读

三、测试运行结果