基于LRU的缓冲区简单模拟

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/%e5%9f%ba%e4%ba%8elru%e7%9a%84%e7%bc%93%e5%86%b2%e5%8c%ba%e7%ae%80%e5%8d%95%e6%a8%a1%e6%8b%9f/

实现一个Storage and Buffer Manager，功能的抽象视图如下所示，即高效率的实现上层App和下层Disk之间的Buffer：缓冲区的设计使用的数据结构： 1.使用了1024块包含4096个char字符的存储空间。

#define FRAMESIZE 4096 
struct bFrame 
{ 
    Char field [FRAMESIZE ]; 
}; 
#define DEFBUFSIZE 1024 
bFrame buf[DEFBUFSIZE];

2.缓存控制块BCB的设计采用了如下的数据结构：

struct BCB{ 
    BCB(); 
    int page_id; 
    int frame_id; 
    int latch; 
    int count;
    int dirty;
    BCB * next; 
};

BCB（缓冲区控制块）的组织如下图所示： 3.使用了两个hash table分别将page_id转为frame_id和把frame_id转为page_id。 –page_ids to frame_ids –H(k) = (page_id)%buffer_size –Frame_ids to page_ids 4.使用LRU算法进行缓冲区的调度，此处使用双向链表实现LRU算法，定义的数据结构如下：

struct LRUEle {
    LRUEle();
    int fid;
    LRUEle * less;
    LRUEle * more;
};

5.另外，分别实现了两个类DSMgr和BMgr,DSMgr用来实现对磁盘数据的读写控制，而BMgr是用来控制缓冲区的各种操作以及LRU算法中对缓冲区块的各种选取和修改。这两个类的框架如下：

class BMgr
{
public:
    BMgr();
    // Interface functions
    int FixPage(int page_id, int prot);   //将对应page_id的page读入到buffer中。如果buffer已满，则需要选择换出的frame
    int UnfixPage(int page_id);
    int NumFreeFrames();
    bool FindFrame(int page_id);
    // Internal Functions
    int SelectVictim();    //在需要置换的时候，选择换出的frame
    int Hash(int page_id);  //Page_id到frame_id 的HASH转换
    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);
    void calcLRUList(BCB * ptr, int frid , int flag);
    // Hash Table
    int ftop[DEFBUFSIZE];
    BCB* ptof[DEFBUFSIZE];
    bFrame buf[DEFBUFSIZE];
};

class DSMgr
{
public:
    DSMgr();
    int OpenFile(string filename);//按照文件名打开文件，本实验主要是用于打开data.dbf文件；关闭文件。
    int CloseFile();
    bFrame ReadPage(int page_id); //按page_id读取dbf文件中的一页，返回一个bFrame类型的对象。
    int WritePage(int frame_id, bFrame frm);//按page_id将frm内容写入dbf	文件。
    int Seek(int offset, int pos);  //在dbf文件中定位指针
    FILE * GetFile();
    void IncNumPages();
    int GetNumPages();
    void SetUse(int index, int use_bit);
    int GetUse(int index);
    FILE *currFile;
    int numPages;
	int pages[MAXPAGES];
};

LRU算法的设计与实现： LRU的算法实现使用双向链表，链表的前端表示最近最久未被使用的块，链表的越靠后的节点表示的是距现在最近被使用的块。所以，LRU算法的操作就被转化为对双向链表的插入和删除和查找的操作。算法维护一个双向链表，链表的头指针代表最近最久未被使用的缓冲区块号。链表的尾部指的是刚刚被使用过的缓冲区块号。具体的原理是：当一个块被访问时，首先查看缓冲区中是否有该块，如果此时能够在缓冲区中找到该块，则不需要进行读磁盘操作，但是由于该块现在被访问，所以需要调整他在LRU队列中的位置，遍历LRU链表，找到该块然后将该块移到链表的最后面；如果缓冲区中没有该块，则需要查看缓冲区中是否有空间存放该块，如果缓冲区中有空块，此时不需要使用LRU算法进行调度，但是需要将写入的块存入LRU链表的最后面，如果缓冲区中没有空块，则LRU算法就会选出一块符合要求的块，让需要写入的块写入被选取的块中，并且将刚刚被移入的块存入LRU链表的最后面。在运行过程中，程序通过int BMgr::FixPage(int page_id , int prot)来实现对所要读写的页号的检查，如果发现没有在缓冲区中并且此时缓冲区中没有空余的空间，此时使用int BMgr::SelectVictim()函数选出一个被替换的候选快，当一块需要被替换出缓冲区时，需要使用RemoveLRUEle(vFrame)和RemoveBCB(bcb,bcb->page_id)两个函数对LRU链表相应表项进行删除以及删除缓冲区控制块。另外void BMgr::calcLRUList(BCB * ptr, int frid , int flag)用来实现对LRU链表的调整，包括对新加入的块的添加和对已经存在的块的位置的调整。整个程序中最重要的函数是FixPage(int page_id , int prot)，下面附上该函数的具体实现：

int BMgr::FixPage(int page_id , int prot)
{
    int fid = -1;
    int frame_id=Hash(page_id);
	BCB * bcb =ptof[frame_id];
    while(bcb != NULL)
    {
	if (bcb->page_id == page_id)
		break;
         bcb = bcb->next;
    }
    if(bcb != NULL)
    {
	calcLRUList(bcb, bcb->frame_id , 2);
	    return bcb->frame_id;
    }
    else
    {
	BCB * bcb1 = ptof[frame_id];
	fid = SelectVictim(); 
	buf[fid] = d.ReadPage(page_id);
	ftop[fid] = page_id;
	if(bcb1 != NULL)
	{
		bcb = new BCB();
		bcb->next = NULL;
		bcb->page_id = page_id;
		bcb->frame_id = fid;
		bcb->latch = 0;
		bcb->count = 0;
		calcLRUList(bcb, fid , 1);
	}
	else
	{
		bcb1 = new BCB();
		ptof[frame_id] = bcb1;
		bcb1->next = NULL;
		bcb1->page_id = page_id;
		bcb1->frame_id = fid;
		bcb1->latch = 0;
		bcb1->count = 0;
		calcLRUList(bcb1, fid , 1);
	}
    }
    return fid;
}

程序在第一次运行时，需要人为的构造一个data.dbf文件，由于具体的数据内容不影响执行的结果，直接用文件流写入二进制数据即可。可按如下程序方式写入，然后就可以生成测试数据。

FILE *fp = fopen("data.dbf", "w+");
char str[100000];
memset(str, 0， sizeof(str));
for (int i = 0; i<4096; i++)
{
	fwrite(str, sizeof(char), sizeof(str), fp);
}
fclose(fp);

基于LRU的缓冲区简单模拟

CATALOG

FEATURED TAGS

FRIENDS