Archive for January, 2012

2012/01/18

要求:模拟一个缓存管理器。给出的测试文件中包含50万个页面请求,每一行用(X,Y)表示,其中X=1表示对页面号为Y的页面写操作,X=0表示对页面号为Y的页面读操作。例如  0,6558     1,3024  等。 规定:磁盘上的页面大小等于Buffer的一个块大小,为4KB;磁盘上的数据库文件data.dbf包含5000个页面,缓冲区有1024个Buffer。设计一个缓存管理器,并统计页面请求的命中和不命中次数。 先说下我的思路,如图,问题牵涉到下面三个部分的协同工作,其中省略了磁盘的读写部分。 解释一下图中的各个部分: 1、Buffer的每一个块4KB,等于磁盘中的数据文件一页的大小,不同的是文件data.dbf有5000页,约193MB,Buffer只有1024块,因此不可能把文件全部加载到缓存中,所以需要有一种合适置换策略,尽量让访问最多的页面驻留在Buffer中,这样可以减少去磁盘读取的次数。 2、Buffer中的每一块都有一个相应的控制结构BCB,BCB详细的记录Buffer中块号(Frame ID)和这一块在文件中所对应的页面号(Page ID)。 3、先说Hash Table,然后再说Table。所有的BCB都散列在Hash Table中,对于每一个页面请求,先使用hash函数将请求的页面号(Page ID)定位到对应的bucket内,在bucket内是一串BCB组成的链表,逐个比较BCB结构内的页面号,如果有与所请求的页面相等的,则说明该页面在Buffer中,直接返回;如果没有搜索到,则说明该页面不再Buffer内,需要去data.dbf文件中将该页面读入,并且在Buffer中选择一个最久没有使用的块,将它的位置让给新的页面。 4、Table就是保存Buffer中每个块所对应的Page ID以及最近一次访问的时间,根据Table的内容,我们可以找出一个最久没有使用的块。 很显然的,如何有效的管理Table,使得我们可以高效的找出一个被替换出Buffer的牺牲页,是至关重要的。 如何来找呢? 老师给的实验参考上说要用LRU算法,因此我最先想到的是以引用时间为关键字,建立一个小根堆,一旦某一个页面被访问,立即更新它的引用时间,这样堆顶元素就是最久没有使用的块了。于是我写好了堆的算法,但是发现了一个致命的弱点:由于页面请求是随机的,因此无法根据请求的页面ID在堆中快速的找到相应的Page ID是在第几个位置(因为堆中元素是在不断调整的),除非逐个搜索,但是这样就变成线性查找了,失去了本来用堆的目的,因此放弃。用链表法?显然查找最小的时间的复杂度也是O(n)。 然后尝试使用FIFO,但是牵涉到是队列的调整(因为某个页面已经在队列中,这时它又被访问了,它的位置并不一定在队头,那么需要将它从队列中取出放到队尾,取出后其他元素也要前移,所以它的复杂度并不比线性查找要好。 之后,想到的是将Table与Buffer一一对应,即Table[1]记录Buffer[1]储存的是哪一个Page,已经访问的时间,但要寻找最小的时间时,遍历整个Table找到最小,时间复杂度是O(n),这个看似比较费时的操作在现在一般配置的机器上似乎并不慢,于是选择的是这种方法。 当我写好了以后,在CFAN的群里面和几位大牛讨论的时候还提到了一种NRU法,即最近未使用法,不过牵涉到对整个Table周期性的更新引用时间,我目前还没想好具体的做法,也许等写完这篇Blog后可以仔细的思考。 同样,程序的代码放在我的GitHub上,这里是运行结果: Dave GG说,可以不使用引用时间。 的确,因为现在的计算机执行指令的速度超乎想象,在2次更新引用时间之间,即使是gettimeofday()函数取得微秒级的时间,也有可能是一样的,但是有没有什么更好的方法呢?用计数器似乎还有一个溢出的问题。 纸上得来终觉浅,绝知此事要躬行。确实是这样的,每一次写这样的程序都会有很多收获,也有更多疑惑,会发现很多跟书上讲的不一致的东西。不知道真正的数据库里是用的什么替换算法?是怎么实现的?操作系统里真正又是用的什么置换算法?又是怎么实现的?

9,332 views