【USTCStudy】高级数据库系统课程实验Storage and Buffer Manager

开头先吐槽一下：

然后考试就考到了！！！（悲

题目说明

Lab 1：根据下面的设计要求，实现一个Storage and Buffer Manager。

设计具体要求：adbs-lab.pdf（课程网站下载）

按文档要求实现一个Storage and Buffer Manager，要求至少实现LRU算法。
底层文件默认采用目录式堆文件。
建议先构建一个5万个page（页号从0到49999）的堆文件（使用自己实现的FixNewPage()接口），然后再运行trace文件：data-5w-50w-zipf.txt（包含了50万次满足Zipfan分布-0.8的页面请求，即80%的请求集中在前20%的页号上），根据设计文档要求统计磁盘IO、Buffer命中率、运行时间等数据。
*下面的实验为选做内容，不做强制要求。如果完成了选做实验（一个或者多个），最后实验成绩会根据完成的情况适当加分：（1）实现CLOCK、LRU-2、LIRS等其它缓存置换算法（至少一种），并与LRU算法的性能进行对比；（2）加入缓存请求时的并发控制，通过内存锁(latch)解决缓存访问时的冲突；要求通过多线程方式执行trace并给出测试结果。

以下为实验报告内容。

实验背景

在这个项目中，我们将实现一个简单的存储和缓冲区管理器。该文档涉及存储和缓冲区管理器。将讨论缓冲区和帧大小、缓冲区和帧存储结构、页面格式、页面存储结构、文件格式、缓冲技术、散列技术、文件存储结构以及磁盘空间和缓冲模块的接口函数。特定技术选自课程中与缓冲区和存储管理器相关的材料。

实验环境

开发环境：

操作系统：Windows 11 专业教育版
开发语言：C++
开发环境：VS2022

运行环境：

硬盘为机械硬盘

实验设计

本项目需要实现一个简单的Storage and Buffer Manager(存储和缓冲区管理器)。

根据文档要求和课程知识，本管理器将分为缓冲区管理和存储管理两部分程序，其中，缓冲区管理程序向更上一层提供接口，并负责调用存储管理器以及对缓冲区进行操作；存储管理程序则向缓冲区管理程序提供接口，并负责对文件存储进行操作。

由文档要求和DBMS架构可知，存储管理器类DSMgr需要实现以下接口函数，从而对数据库文件进行操作：

class DSMgr
{
public:
    DSMgr();//当前数据文件将保存在 DSManager 类中。该文件将被命名为 data.dbf
    int OpenFile(string filename);//打开由文件名指定的文件
    int CloseFile();//关闭当前正在使用的文件。只应在数据库更改或程序关闭时调用。
    bFrame ReadPage(int page_id);//由缓冲区管理器中的 FixPage 函数调用，原型是 ReadPage(page_id, bytes) 并返回它读入的内容，调用 fseek() 和 fread() 从文件中获取数据
    int WritePage(int frame_id, bFrame frm);//每当从缓冲区中取出一页时，都会调用 WritePage 函数。原型是 WritePage(frame_id, frm) 并返回写入了多少字节。此函数调用 fseek() 和 fwrite() 将数据保存到文件中
    int Seek(int offset, int pos);//移动文件指针
    FILE * GetFile();//返回当前文件
    void IncNumPages();//递增页面计数器
    int GetNumPages();//返回页面计数器
    void SetUse(int index, int use_bit);//用于设置页面数组中的位。该数组跟踪正在使用的页面。如果页面中的所有记录都被删除，那么该页面就不再真正使用，可以在数据库中再次使用。为了知道页面是否可重用，检查数组中是否有任何设置为零的use_bit。fixNewPage函数首先检查此数组的use_bit是否为零。如果找到，则重新使用该页面。如果不是，则分配一个新页面。
    int GetUse(int index);//返回相应 page_id 的当前 use_bit
private:
    FILE *currFile;//当前文件
    int numPages;//页面计数器
    int pages[MAXPAGES];//根据文档说明，MAXPAGES设为50000
}

而缓冲区管理器类需要实现以下接口函数：

class BMgr
{
public:
    BMgr(std::string filename, int choice, int input_frame_num = FRAME_NUM);//传入数据库文件名用于传递给存储管理器，传入choice用于选择管理算法，传入帧数量用于确定缓冲区大小。
    ~BMgr();
    // Interface functions
    int FixPage(int page_id, int prot);//这个函数的原型是FixPage(Page_id, protection)，它返回一个 frame_id。文件和访问管理器将使用记录的 record_id 中的 page_id 调用此页面。该函数查看页面是否已经在缓冲区中，如果是，则返回相应的 frame_id。如果该页面尚未驻留在缓冲区中，它会选择一个受害页面（如果需要）并加载到请求的页面中。
    int UnfixPage(int page_id);//这个函数的原型是 UnfixPage(page_id)，它返回一个 frame_id。此函数是对 FixPage 或 FixNewPage 调用的补充。此函数减少帧上的fix(固定)计数。如果计数减少到零，则页面上的锁被移除，并且如果选中，则帧可以被移除。page_id 被转换为 frame_id 并且它可能被解锁，以便在页面上的计数减少到零时，可以将它选为受害者页面。
    int NumFreeFrames();//NumFreeFrames 函数查看缓冲区并返回空闲且可以使用的缓冲区页数。这对于查询处理器的N路排序特别有用。该函数的原型类似于 NumFreeFrames() 并返回一个从 0 到 BUFFERSIZE-1(1023) 的整数。
    // Internal Functions
    int SelectVictim();//SelectVictim 函数选择要替换的帧。如果设置了所选帧的脏位，则需要将页面写入磁盘。
    int Hash(int page_id);//哈希函数以page_id为参数，返回frame id。
    void RemoveBCB(BCB * ptr, int page_id);//RemoveBCB函数从数组中删除 page_id 的缓冲区控制块。只有在 SelectVictim() 函数需要替换帧时才会调用此方法。
    void RemoveLRUEle(int frid);//RemoveLRUEle函数从列表中删除 LRU 元素。
    void SetDirty(int frame_id);//SetDirty函数设置frame_id的脏位。此脏位用于确定是否要写入帧。如果内容以任何方式修改，则必须写入帧。这包括任何目录页和数据页。如果位为1，则将写入。如果此位为零，则不会写入。
    void UnsetDirty(int frame_id);//UnsetDirty 函数将相应 frame_id 的 dirty_bit 分配为零。调用此函数的主要原因是调用了 setDirty() 函数但页面实际上是临时关系的一部分。在这种情况下，页面实际上不需要写入，因为它不想保存。
    void WriteDirtys();//WriteDirtys 函数必须在系统关闭时调用。该函数的目的是写出仍在缓冲区中可能需要写入的任何页面。如果 dirty_bit 为 1，它只会将页面写出到文件中。
    PrintFrame(int frame_id);//PrintFrame 函数打印出由 frame_id 描述的帧的内容。
private:
    DSMgr dsmgr;//存储管理器实例
    int frame_num;
    // Hash Table

    int* ftop;//frame_id 到 page_id 的表：int hTable[BufferSize]
    BCB** ptof;//page_id 到 BCB 的哈希表：BCB hTable[BufferSize]
    Replacer *lru;//LRU算法实例
}

缓冲区和帧存储结构

缓冲区是指主存中的空间，CPU 只能访问主存中的内容。缓冲区由一组帧组成。当一个页面被请求时，它被加载到缓冲区的内存中。大多数商业数据库管理系统使帧的大小与页面大小相同，以防止外部碎片。该项目采用了相同的策略。默认情况下，项目的缓冲区大小将设置为1024。

缓冲区由称为帧的逻辑分区组成。帧将存储在全局定义的结构中，描述帧的外观。该结构将定义为：

#define FRAMESIZE 4096//定义帧大小=页面大小=4096
struct bFrame
{
    char field[FRAMESIZE];
};

缓冲区数组将存储一系列帧，这些帧将存储加载到其中的页面。该数组将如下所示：

#define DEFBUFSIZE 1024
bFrame buf[DEFBUFSIZE]; //缓冲区，用户也可通过输入相关参数定义尺寸

这将是为缓冲区分配的空间，缓冲区管理器将访问该空间，文件和访问方法将引用所需的页面。

页面格式

这个项目中不需要参考页面的详细结构，唯一重要的信息是page_id和page_size(根据文档中代码的定义，页面大小为4096)，所以不需要设计页面格式，读取与写入操作是对整个页进行的。由于只有一个文件所以不需要考虑文件ID。

文件格式

使用基于目录的结构来组织数据库文件，如课程中所介绍的那样。每个文件都有一个基页，其中包含指向文件中每个页面的指针。基页中的每个指针都按页面的顺序排列。这类文件中的数据页没有指针，只有记录。必须查阅基页或目录才能获得文件中的下一页。

选择基于目录的文件格式是因为它适合为所请求的记录查找特定页面。该文件的目录将允许快速访问正确的页面，而无需搜索一长串页面以找到正确的页面。

缓冲技术

在大多数场景下，page数远大于BUFFSIZE，所以缓存器必须有一个调度机制，用以实现内存中缓存页frame的置换、淘汰，根据文档要求，这里使用了LRU（Least Recent Used）算法作为替换策略。LRU总是从LRU队列中逐出最近最少使用的页面，该队列用于组织按上次引用时间排序的缓冲区页面。它总是选择在LRU位置找到的页面作为受害者。LRU最重要的优势是其恒定的运行时复杂性。此外，LRU以其在具有高时间局部性的引用模式的情况下的良好性能而闻名，即当前引用的页面在不久的将来具有很高的重新引用概率。

关于LRU的实现主要有3种方式：

用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。这种实现思路比较简单，但缺点也很明显：需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。

利用一个链表来实现，每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。这种方法效率相对第一种稍高，但链表在定位数据的时候时间复杂度为O(n)。

基于双向链表。当需要插入新的数据项的时候，如果新数据项在链表中存在（命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。这样一来在链表尾部的节点就是最近最久未访问的数据项。基本所有操作可以实现时间复杂度O(1)。

根据文档要求，采用第三种方式，用双向链表实现。

哈希技术

对于缓冲区中的每个帧，必须保留一个缓冲区控制块。每个缓冲区控制块(BCB)都包含一个page_id、一个frame_id、page_latch、fix_count和dirty_bit。page_ids用作将page_id映射到BCB的散列函数的键。必须保留两个哈希表：一个将page_ids映射到frame_ids和BCB，另一个将frame_ids映射到page_ids。

文档建议使用简单的静态哈希技术。在静态哈希中，桶的数量是固定的。如果桶已满，则为额外的数据条目连接溢出链。使用键值，哈希函数将其映射到一个桶。并使用顺序搜索在单个桶内进行搜索。桶的数量不会随着时间的推移而改变。

哈希函数如下所示：

H(k) = (page_id)%buffer_size，式中buffer_size为默认的1024或其他自定义的缓冲区大小。

缓冲区控制块将包含 page_id、frame_id、latch、count、dirty_bit。

page_id 到 BCB 的哈希表：BCB hTable[BufferSize]

frame_id 到 page_id 的表：int hTable[BufferSize]

//缓冲区控制块(BCB)
//page_ids 用作将 page_id 映射到 BCB 的散列函数的键
//必须保留两个哈希表：一个将 page_ids 映射到 frame_ids 和 BCB，另一个将 frame_ids 映射到 page_ids
struct BCB
{
    BCB() {};
    int page_id;//页id
    int frame_id;//帧id
    int latch;//内存锁
    int count;//用户占用计数
    int dirty;//脏位
    BCB* next;//指向同hash值的下一项
    BCB(int page_id, int frame_id) : page_id(page_id), frame_id(frame_id), count(0), latch(0), dirty(0),next(NULL) {}
};

项目实现

在头文件DataStorageManager.h中定义类DSMgr，在C程序文件DataStorageManager.cpp中实现该类的相关方法，一些数据结构如bFrame、BCB在common.h中完成定义，以便引用。

在头文件BufferManager.h中定义类BMgr，在C程序文件BufferManager.cpp中实现该类的相关方法，同时引用头文件DataStorageManager.h以便调用对存储进行操作的各种接口。

通过文件Replacer.h(共用接口类)、LRUReplacer.h、LRU2Replacer.h分别定义LRU和LRU-2缓存算法类，对应cpp文件中实现其算法与接口，以供缓冲区管理器调用。

在文件ADBS.cpp中创建BMgr实例，读取文件data-5w-50w-zipf.txt中的记录，从而完成实验。

运行说明与实验结果

在项目中，需要执行 trace 驱动的实验来展示实施结果。trace 是根据 Zipf 分布生成的。跟踪中总共有 500000 个页面引用，这些页面被限制为一组编号范围为 1 到 50000 的页面。每个跟踪记录的格式为“x，###”，其中 x 是 0（读取）或 1（写入），### 是引用的页码。实验需要扫描 trace 文件并打印出内存和磁盘之间的总 I/O 次数。在实验开始时缓冲区应该是空的。trace 中涉及的50000页全部需要先物化到磁盘中，对应目录下的文件data.dbf。

生成数据库文件

作为准备工作，首先将50000页*4096字节的虚拟页文件物化到磁盘中，生成文件data.dbf，共200MB。

执行程序

直接运行程序ADBS.exe（LRU2缓存链表长800），程序会弹出命令行窗口，并物化数据库文件。输入1或2选择所用算法，开始计时，程序会打开文件data.dbf，然后逐行读取文件data-5w-50w-zipf.txt中的记录，根据其中的指令调用函数FixPages()，模拟读写页的操作。

运行结果

选做内容

实现LRU-2

LRU-2是通过维护一个访问次数2次以上的额外链表实现的算法，当第二次访问缓冲区某帧时，将其从历史访问链表移动到缓存链表中。算法实现于文件LRU2Replacer.cpp。

可以看出，LRU-2算法的命中率比LRU算法有显著的提升，在设定缓存链表长度为512的情况下，其命中率可以达到40.33%，而如果设定缓存链表长度为800，命中率可达43.72%。同时，随着命中率的提高，IO次数明显减少，运行时间也更快。

具体代码

可以访问Github或Github1s(在线VScode)查看

以下为代码结构

ADBS
├── DataStorageManager.cpp
├── BufferManager.cpp
├── LRUReplacer.cpp
├── LRU2Replacer.cpp
├── ADBS.h
├── ADBS.cpp
└── include
    ├── Common.h
    ├── DataStorageManager.h
    ├── BufferManager.h
    ├── Replacer.h
    ├── LRUReplacer.h
    └── LRU2Replacer.h

以下为具体代码：

`Common.h`

#pragma once

#include <iostream>
//定义帧存储结构
#define FRAMESIZE 4096//定义帧大小=页面大小=4096
struct bFrame
{
    char field[FRAMESIZE];
};

//定义缓冲区数组，数组将存储一系列帧
#define DEFBUFSIZE 1024
//bFrame buf[DEFBUFSIZE]; // or the size that the user defined by the input parameter 或用户通过输入参数定义的尺寸

#define MAXPAGES 50000

//缓冲区控制块(BCB)
//page_ids 用作将 page_id 映射到 BCB 的散列函数的键
//必须保留两个哈希表：一个将 page_ids 映射到 frame_ids 和 BCB，另一个将 frame_ids 映射到 page_ids
struct BCB
{
    BCB() {};
    int page_id;//页id
    int frame_id;//帧id
    int latch;//内存锁
    int count;//用户占用计数
    int dirty;//脏位
    BCB* next;//指向同hash值的下一项
    BCB(int page_id, int frame_id) : page_id(page_id), frame_id(frame_id), count(0), latch(0), dirty(0),next(NULL) {}   
};

struct LRUNode//LRU节点
{
    int frame_id;
    int pincount;
    LRUNode* prev;//指向链表前一项
    LRUNode* next;//指向链表下一项
    LRUNode(int frame_id) :frame_id(frame_id),pincount(1) {};
};

//哈希表的静态哈希技术。哈希函数将如下所示：

//H(k) = (page_id) % buffer_size

//缓冲区控制块将包含 page_id、frame_id、latch、count、dirty_bit
//page_id 到 BCB 的哈希表：BCB hTable[BufferSize]
//frame_id 到 page_id 的表：int hTable[BufferSize]

`DataStorageManager.h`

#pragma once

#include <iostream>
#include "Common.h"

class DSMgr
{
public:
    DSMgr();
    ~DSMgr();
    DSMgr(std::string filename);
    int OpenFile(std::string filename);
    int CloseFile();
    bFrame ReadPage(int page_id);
    int WritePage(int page_id, bFrame frm);
    int Seek(int offset, int pos);
    FILE* GetFile();
    void IncNumPages();
    int GetNumPages();
    void SetUse(int index, int use_bit);
    int GetUse(int index);
    int ReadCount;
    int WriteCount;
private:
    FILE* currFile;
    int numPages;
    int pages[MAXPAGES];
};

`BufferManager.h`

#pragma once

#include <list>
#include <unordered_map>
#include <mutex>

#include "DataStorageManager.h"
#include "LRUReplacer.h"
#include "LRU2Replacer.h"

#define FRAME_NUM 1024

//enum ReplacePolicy { Invalid = 0, Lru, Clock };

class BMgr
{
public:
    BMgr(std::string filename, int choice, int input_frame_num = FRAME_NUM);
    ~BMgr();
    // Interface functions接口功能
    //int FixPage(int page_id);
    int FixPage(int page_id, int prot);//函数原型是FixPage(Page_id, protection)，返回一个 frame_id。文件和访问管理器将使用记录的record_id中的page_id调用此页面。
    //该函数查看页面是否已经在缓冲区中，如果是，则返回相应的frame_id。如果该页面尚未驻留在缓冲区中，它会选择一个受害页面（如果需要）并加载请求的页面。
    void FixNewPage();
    int UnfixPage(int page_id);
    int NumFreeFrames();//查看缓冲区并返回空闲且可以使用的缓冲区页数。这对于查询处理器的N路排序特别有用。返回一个从 0 到 BUFFERSIZE-1(1023) 的整数。
    // Internal Functions内部功能
    int SelectVictim();
    BCB* Hash(int page_id);
    void RemoveBCB(BCB* ptr, int page_id);
    void RemoveLRUEle(int frid);
    void SetDirty(int frame_id);
    void UnsetDirty(int frame_id);
    void WriteDirtys();
    void PrintFrame(int frame_id);
    bFrame* buf;//缓冲区
    int InBufferCount;
    int OutBufferCount;
    int GetIONum(int choice);
private:
    DSMgr dsmgr;//存储管理器实例
    int frame_num;
    // Hash Table

    int* ftop;//frame_id 到 page_id 的表：int hTable[BufferSize]
    BCB** ptof;//page_id 到 BCB 的哈希表：BCB hTable[BufferSize]
    Replacer *lru;
};

`Replacer.h`

#pragma once

#include "Common.h"

class Replacer {
public:
    Replacer() = default;
    virtual ~Replacer() = default;
    virtual int Victim() = 0;
    virtual void Insert(int frame_id) = 0;
    virtual void Remove() = 0;
    virtual void Fix(int frame_id)=0;
    virtual void Print() = 0;
    virtual int Size() = 0;
};

`LRUReplacer.h`

#pragma once

#include "Replacer.h"

class LRUReplacer : public Replacer {

public:
    //LRUReplacer();
    LRUReplacer(int max_size = DEFBUFSIZE);
    ~LRUReplacer();
    int Victim();
    void Insert(int frame_id);
    void Remove();
    void Fix(int frame_id);
    int Size();
    void Print();

private:
    LRUNode* Lhead, * Ltail;
    int Lsize;
    int Lmax{ DEFBUFSIZE };

    inline void set_pointer(LRUNode* p, LRUNode* q) {
        p->next = q;
        q->prev = p;
    }
};

`LRU2Replacer.h`

#pragma once

#include <unordered_map>
#include "Replacer.h"

class LRU2Replacer : public Replacer {

public:
    //LRU2Replacer();
    LRU2Replacer(int max_size = DEFBUFSIZE);
    ~LRU2Replacer();
    int Victim();
    void Insert(int frame_id);
    void Remove();
    void Fix(int frame_id);
    int Size();
    void Print();

private:
    void Remove2();
    void Fix2(int frame_id);
    LRUNode* Lhead, * Ltail;
    LRUNode* L2head, * L2tail;
    int Lsize, L2size;
    int Lmax{ DEFBUFSIZE };
    int L2max;

    inline void set_pointer(LRUNode* p, LRUNode* q) {
        p->next = q;
        q->prev = p;
    }
};

`DataStorageManager.cpp`

#include "include/DataStorageManager.h"

DSMgr::DSMgr() {
    numPages = 0;
    ReadCount = 0;
    WriteCount = 0;
    for (int i = 0; i < MAXPAGES; i++) {
        pages[i] = 0;
    }
}

DSMgr::DSMgr(std::string filename) {
    OpenFile(filename);
}

DSMgr::~DSMgr() {
    CloseFile();
}

int DSMgr::OpenFile(std::string filename){
    currFile = fopen(filename.c_str(), "r+");
    if (currFile == nullptr) {
        currFile = fopen(filename.c_str(), "w");
        currFile = freopen(filename.c_str(), "r+", currFile);
    }
    else {
        fseek(currFile, 0L, SEEK_END);
        long sz = ftell(currFile);//函数 ftell 用于得到文件位置指针当前位置相对于文件首的偏移字节数。
        numPages = sz / FRAMESIZE;
    }
    return currFile != nullptr;
}

int DSMgr::CloseFile() {
    return fclose(currFile);
}

bFrame DSMgr::ReadPage(int page_id) {
    bFrame data;
    if (Seek(page_id * FRAMESIZE,0)) {
        fprintf(stderr, "Error: cannot find page: %d\n", page_id);
        exit(1);
    }
    fread(data.field, FRAMESIZE, 1, currFile);
    SetUse(page_id,1);
    ReadCount++;
    return data;
}

int DSMgr::WritePage(int page_id, bFrame frm) {//对帧id到page_id的转换应在BMgr中进行。
    if (Seek(page_id * FRAMESIZE, SEEK_SET) != 0) {
        fprintf(stderr, "Error: cannot find page: %d\n", page_id);
        exit(1);
    }
    SetUse(page_id, 0);
    WriteCount++;
    return (int)fwrite(frm.field, FRAMESIZE, 1, currFile);
}

int DSMgr::Seek(int offset, int pos) {
    return fseek(currFile, (long)offset, pos);
}

FILE* DSMgr::GetFile() {
    return currFile;
}

void DSMgr::IncNumPages() {
    numPages++;
}

int DSMgr::GetNumPages() {
    return numPages;
}

void DSMgr::SetUse(int index, int use_bit) {
    //SetUse 函数用于设置页面数组中的位。该数组跟踪正在使用的页面。如果页面中的所有记录都被删除，那么该页面就不再真正使用，可以在数据库中再次使用。
    //为了知道页面是否可重用，检查数组中是否有任何设置为零的 use_bits。
    //fixNewPage 函数首先检查此数组的 use_bit 是否为零。如果找到，则重新使用该页面。如果不是，则分配一个新页面。
    pages[index] = use_bit;
}

int DSMgr::GetUse(int index) {
    return pages[index];
}

`BufferManager.cpp`

#include "include/BufferManager.h"

#include <cassert>
#include <cstdio>

BMgr::BMgr(std::string filename, int choice, int input_frame_num) {
    printf("缓冲区容量%d\n", input_frame_num);
    frame_num = input_frame_num;
    ftop = new int[frame_num];//frame_id 到 page_id 的表：int hTable[BufferSize]
    ptof = new BCB*[frame_num];//page_id 到 BCB 的哈希表：BCB hTable[BufferSize]
    for (int i = 0; i < frame_num; i++) {
        ftop[i] = -1;//初始化frame到page映射的哈希表，全部置为-1，表示为空
        ptof[i] = NULL;//初始化page到frame映射的哈希表，全部置为NULL，表示为空指针
    }
    dsmgr.OpenFile(filename);
    buf = (bFrame*)malloc(frame_num * sizeof(bFrame));
    switch (choice)
    {
    case(1):
        lru = new LRUReplacer(frame_num);
        break;
    case(2):
        lru = new LRU2Replacer(frame_num);
        break;
    default:
        lru = new LRUReplacer(frame_num);
        break;
    }
    InBufferCount = 0;
    OutBufferCount = 0;
}

BMgr::~BMgr() {
    WriteDirtys();
}

int BMgr::FixPage(int page_id, int prot) {
    //这个函数的原型是FixPage(Page_id, protection)，它返回一个 frame_id。文件和访问管理器将使用记录的 record_id 中的 page_id 调用此页面。该函数查看页面是否已经在缓冲区中，如果是，则返回相应的 frame_id。如果该页面尚未驻留在缓冲区中，它会选择一个受害页面（如果需要）并加载到请求的页面中。
    BCB* bcb = Hash(page_id);
    //printf("FixPage id: %d, dirty: %d.\n", page_id, prot);
    if (bcb != NULL) {//在缓冲区
        InBufferCount++;
        lru->Fix(bcb->frame_id);//LRU中将对应节点提到最前
        if (prot) {
            SetDirty(bcb->frame_id);
        }
        return bcb->frame_id;
    } else {//不在缓冲区
        OutBufferCount++;
        int frame_id;
        if (NumFreeFrames()) {//1-1024
            frame_id = frame_num - NumFreeFrames();//0-1023
        }
        else//0
        {
            frame_id = SelectVictim();
        }
        //一系列加载动作
        buf[frame_id] = dsmgr.ReadPage(page_id);
        lru->Insert(frame_id);
        bcb = new BCB(page_id,frame_id);
        BCB* prebcb = ptof[page_id % frame_num];
        if (prebcb != NULL) {
            while (prebcb->next!=NULL) {
                prebcb=prebcb->next;
            }
            prebcb->next = bcb;
        }
        else
        {
            ptof[page_id % frame_num] = bcb;
        }
        ftop[frame_id] = page_id;
        if (prot) {
            SetDirty(bcb->frame_id);
        }
        return frame_id;
    }
}
void BMgr::FixNewPage() {
    //此函数的原型是 FixNewPage()，它返回一个 page_id 和一个 frame_id。当插入、索引拆分或对象创建时需要新页面时使用此函数。返回 page_id 以便分配给 record_id 和元数据。此函数将找到一个空页面，文件和访问管理器可以使用该页面来存储一些数据。

}
int BMgr::UnfixPage(int page_id) {
    return 0;
    //这个函数的原型是 UnfixPage(page_id)，它返回一个 frame_id。此函数是对 FixPage 或 FixNewPage 调用的补充。此函数减少帧上的fix(固定)计数。如果计数减少到零，则页面上的锁被移除，并且如果选中，则帧可以被移除。page_id 被转换为 frame_id 并且它可能被解锁，以便在页面上的计数减少到零时，可以将它选为受害者页面。
}
int BMgr::NumFreeFrames() {
    return frame_num - lru->Size();
    //NumFreeFrames 函数查看缓冲区并返回空闲且可以使用的缓冲区页数。这对于查询处理器的N路排序特别有用。该函数的原型类似于 NumFreeFrames() 并返回一个从 0 到 BUFFERSIZE-1(1023) 的整数。
}
// Internal Functions
int BMgr::SelectVictim() {//使用LRU算法选取最旧的帧
    int frame_id = lru->Victim();
    int victim_page_id = ftop[frame_id];
    BCB* bcb = Hash(victim_page_id);
    RemoveBCB(bcb, victim_page_id);
    //printf("SelectVictim frameid: %d", frame_id);
    return frame_id;
}
BCB* BMgr::Hash(int page_id) {
    int bid = page_id % frame_num;
    BCB* bcb = ptof[bid];
    while (bcb != NULL) {
        if (bcb->page_id == page_id) {
            return bcb;
        }
        bcb = bcb->next;
    }
    return NULL;
}

void BMgr::RemoveBCB(BCB* ptr, int page_id) {
    int bid = page_id % frame_num;
    //printf("RemoveBCB: %d\n",page_id);
    BCB* bcb = ptof[bid];
    if (bcb == ptr) {
        ptof[bid] = ptr->next;
    }
    else
    {
        while (bcb->next != ptr)
        {
            bcb = bcb->next;
        }
        bcb->next = ptr->next;
    }
    if (ptr->dirty) {
        dsmgr.WritePage(ptr->page_id, buf[ptr->frame_id]);
    }
    free(ptr);
}
void BMgr::RemoveLRUEle(int frid) {

}
void BMgr::SetDirty(int frame_id) {
    int page_id = ftop[frame_id];
    BCB* bcb = Hash(page_id);
    if (bcb) {
        bcb->dirty = 1;
    }
}
void BMgr::UnsetDirty(int frame_id) {
    int page_id = ftop[frame_id];
    BCB* bcb = Hash(page_id);
    if (bcb) {
        bcb->dirty = 0;
    }
}
void BMgr::WriteDirtys() {
    BCB* bcb;
    for (int i = 0; i < frame_num; i++) {
        bcb = Hash(ftop[i]);
        if (bcb->dirty) {
            dsmgr.WritePage(bcb->page_id, buf[bcb->frame_id]);
        }
    }
}
int BMgr::GetIONum(int choice) {
    switch (choice)
    {
    case 0:
        return dsmgr.ReadCount;
        break;
    case 1:
        return dsmgr.WriteCount;
        break;
    default:
        return dsmgr.ReadCount;
        break;
    }

}
void BMgr::PrintFrame(int frame_id) {

}

`LRUReplacer.cpp`

#include <cstdio>

#include "include/LRUReplacer.h"

LRUReplacer::LRUReplacer(int max_size) {
    Lsize = 0;
    Lmax = max_size;
    Lhead = new LRUNode(-1);
    Ltail = new LRUNode(-1);
    set_pointer(Lhead, Ltail);
}

LRUReplacer::~LRUReplacer() {
    /*LRUNode* p = head_, * tmp;
    for (; p != nullptr; p = tmp) {
        tmp = p->next;
        delete p;
    }*/
}

int LRUReplacer::Victim() {//选取链表尾部的节点，返回frame_id
    if (Lsize == 0)
        return -1;
    return Ltail->prev->frame_id;
}

void LRUReplacer::Insert(int frame_id) {
    LRUNode* node = new LRUNode(frame_id);
    node->next = Lhead->next;
    node->next->prev = node;
    set_pointer(Lhead, node);
    Lsize++;
    if (Lsize > Lmax) {
        Remove();
    }
}

void LRUReplacer::Remove() {//移除尾部节点
    LRUNode* node = Ltail->prev;
    set_pointer(node->prev, Ltail);
    free(node);
    Lsize--;
}

void LRUReplacer::Fix(int frame_id) {
    LRUNode* node = Lhead->next;
    if (node->frame_id == frame_id) {
        return;
    }
    while (node->frame_id != frame_id)
    {
        node = node->next;
        /*if (node->frame_id == -1) {
            printf("can`t find %d", frame_id);
            return;
        }*/
    }
    LRUNode* nextnode = node->next;
    LRUNode* prevnode = node->prev;
    set_pointer(prevnode, nextnode);

    node->next = Lhead->next;
    node->next->prev = node;
    node->prev = Lhead;
    Lhead->next = node;
}

int LRUReplacer::Size() {
    return Lsize;
}

void LRUReplacer::Print() {
    printf("lru replacer:\n");
    for (LRUNode* node = Lhead->next; node != Ltail; node = node->next) {
        printf("%d ", node->frame_id);
    }
    printf("\n");
}

`LRU2Replacer.cpp`

#include <cstdio>

#include "include/LRU2Replacer.h"

LRU2Replacer::LRU2Replacer(int max_size) {
    Lsize = 0;
    L2size = 0;
    Lmax = max_size;
    L2max = 800;
    Lhead = new LRUNode(-1);
    Ltail = new LRUNode(-1);
    L2head = new LRUNode(-1);
    L2tail = new LRUNode(-1);
    set_pointer(Lhead, Ltail);
    set_pointer(L2head, L2tail);
}

LRU2Replacer::~LRU2Replacer() {
    /*LRUNode* p = head_, * tmp;
    for (; p != nullptr; p = tmp) {
        tmp = p->next;
        delete p;
    }*/
}

int LRU2Replacer::Victim() {//选取链表尾部的节点，返回frame_id
    if (Lsize == 0)
        return -1;
    if (L2size >= L2max || Ltail->prev->frame_id == -1) {
        return L2tail->prev->frame_id;
    }
    else
    {
        return Ltail->prev->frame_id;
    }
}

void LRU2Replacer::Insert(int frame_id) {
    if (Lsize == Lmax) {
        Remove();
    }
    LRUNode* node = new LRUNode(frame_id);
    node->next = Lhead->next;
    node->next->prev = node;
    set_pointer(Lhead, node);
    Lsize++;
}

void LRU2Replacer::Remove() {//移除历史表尾部节点
    LRUNode* node = Ltail->prev;
    if (L2size >= L2max || node->frame_id == -1) {
        return Remove2();
    }
    set_pointer(node->prev, Ltail);
    /*node->prev->next = Ltail;
    Ltail->prev = node->prev;*/
    free(node);
    Lsize--;
}
void LRU2Replacer::Remove2() {//移除缓存表尾部节点
    LRUNode* node = L2tail->prev;
    set_pointer(node->prev, L2tail);
    /*node->prev->next = L2tail;
    L2tail->prev = node->prev;*/
    free(node);
    Lsize--;
    L2size--;
}

void LRU2Replacer::Fix(int frame_id) {
    //LRU2的第一个链纯顺序即可。
    //LRU2的第二个链才需要LRU操作。
    //目测是先找缓存链，然后再找历史记录链。
    LRUNode* node = L2head->next;
    if (node->frame_id == frame_id) {
        return;
    }
    while (node->frame_id != frame_id)
    {
        if (node->frame_id == -1) {
            return Fix2(frame_id);
        }
        node = node->next;
    }
    LRUNode* nextnode = node->next;
    LRUNode* prevnode = node->prev;
    set_pointer(prevnode, nextnode);
    node->next = L2head->next;
    node->next->prev = node;
    L2head->next = node;
    node->pincount++;
}

void LRU2Replacer::Fix2(int frame_id) {
    LRUNode* node = Lhead->next;
    if (node->frame_id == frame_id) {
        set_pointer(Lhead, node->next);
    }
    else {
        while (node->frame_id != frame_id)
        {
            node = node->next;
            /*if (node->frame_id == -1) {
                printf("can`t find %d", frame_id);
                return;
            }*/
        }
        LRUNode* nextnode = node->next;
        LRUNode* prevnode = node->prev;
        set_pointer(prevnode, nextnode);
    }
    node->next = L2head->next;
    node->next->prev = node;
    set_pointer(L2head, node);
    node->pincount++;
    L2size++;
}

int LRU2Replacer::Size() {
    return Lsize;
}

void LRU2Replacer::Print() {
    printf("lru replacer:\n");
    for (LRUNode* node = Lhead->next; node != Ltail; node = node->next) {
        printf("%d ", node->frame_id);
    }
    printf("\n");
}

`ADBS.h`

// ADBS.h: 标准系统包含文件的包含文件
// 或项目特定的包含文件。

#pragma once

#include <iostream>

// TODO: 在此处引用程序需要的其他标头。
#include "include/Common.h"

`ADBS.cpp`

// ADBS.cpp: 定义应用程序的入口点。
//

#include "ADBS.h"
#include "include/BufferManager.h"
using namespace std;

int main()
{
    //char* filename = const_cast<char*>(cmd.rest()[0].c_str());
    string filename = "data-5w-50w-zipf.txt";
    FILE* db_file = fopen("data.dbf", "r");
    /* create db with certain size */
    if (db_file == NULL) {
        db_file = fopen("data.dbf", "w");
        void* buffer = malloc(50000 * FRAMESIZE);
        fwrite(buffer, FRAMESIZE, 50000, db_file);
        free(buffer);
    }
    fclose(db_file);
    //printf("dbfile exist.");
    int choice;
    printf("输入1选择LRU算法，输入2选择LRU-2算法：");
    scanf("%d", &choice);
    if (choice == 2) {
        printf("LRU-2算法设定缓存链表长度为800\n");
    }
    clock_t start_time = clock();
    /* create buffer pool manager */
    BMgr* bmgr = new BMgr("data.dbf",choice);
    /* read data file */
    FILE* data_file = fopen(filename.c_str(), "r");
    if (data_file == NULL) {
        fprintf(stderr, "Error: file %s doesn't exist\n", filename);
        exit(1);
    }
    printf("成功打开文件...\n");
    int is_dirty, page_id;
    while (fscanf(data_file, "%d,%d", &is_dirty, &page_id) != EOF) {
        bmgr->FixPage(page_id, is_dirty);
        //printf("\r执行行数%d", line++);
        //bmgr->UnfixPage(page_id);
    }
    printf("执行完毕！\n命中计数: %d, 未命中计数: %d, 命中率%.2f%%\n", bmgr->InBufferCount, bmgr->OutBufferCount, (float)bmgr->InBufferCount*100.0/(bmgr->InBufferCount + bmgr->OutBufferCount));
    printf("读页次数: %d, 写页次数: %d, IO总次数: %d\n", bmgr->GetIONum(0), bmgr->GetIONum(1), bmgr->GetIONum(0) + bmgr->GetIONum(1));
    printf("运行时间: %.2fs\n", (double)(clock() - start_time) / CLOCKS_PER_SEC);
    fclose(data_file);
    system("pause");
    return 0;
}

【USTCStudy】高级数据库系统课程实验Storage and Buffer Manager

题目说明

实验背景

实验环境

实验设计

缓冲区和帧存储结构

页面格式

文件格式

缓冲技术

哈希技术

项目实现

运行说明与实验结果

生成数据库文件

执行程序

运行结果

选做内容

实现LRU-2

具体代码

以下为代码结构

以下为具体代码：

`Common.h`

`DataStorageManager.h`

`BufferManager.h`

`Replacer.h`

`LRUReplacer.h`

`LRU2Replacer.h`

`DataStorageManager.cpp`

`BufferManager.cpp`

`LRUReplacer.cpp`

`LRU2Replacer.cpp`

`ADBS.h`

`ADBS.cpp`

霍格沃茨之遗女皇版未加密资源整理与分享

typecho Database Query Error(转载备查，主要是记一下命令)

SakurakoujiLuna

Comments | NOTHING

题目说明

实验背景

实验环境

实验设计

缓冲区和帧存储结构

页面格式

文件格式

缓冲技术

哈希技术

项目实现

运行说明与实验结果

生成数据库文件

执行程序

运行结果

选做内容

实现LRU-2

具体代码

以下为代码结构

以下为具体代码：

Common.h

DataStorageManager.h

BufferManager.h

Replacer.h

LRUReplacer.h

LRU2Replacer.h

DataStorageManager.cpp

BufferManager.cpp

LRUReplacer.cpp

LRU2Replacer.cpp

ADBS.h

ADBS.cpp

霍格沃茨之遗女皇版未加密资源整理与分享

typecho Database Query Error(转载备查，主要是记一下命令)

SakurakoujiLuna

Comments | NOTHING

你想搜索什么...

`Common.h`

`DataStorageManager.h`

`BufferManager.h`

`Replacer.h`

`LRUReplacer.h`

`LRU2Replacer.h`

`DataStorageManager.cpp`

`BufferManager.cpp`

`LRUReplacer.cpp`

`LRU2Replacer.cpp`

`ADBS.h`

`ADBS.cpp`