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