剑灵网站模板,湖南做网站磐石网络案例,创胜网络科技有限公司,社群推广平台目录 1、介绍
2、缓冲池
3、处理页面请求
4、LRU替换和时钟策略
1#xff09;顺序扫描性能 - LRU
5、最近最常使用替换策略#xff08;MRU Replacement#xff09;
1#xff09;Sequential Scanning Performance - MRU
6、练习题
1#xff09;判断真假
2#xf…目录 1、介绍
2、缓冲池
3、处理页面请求
4、LRU替换和时钟策略
1顺序扫描性能 - LRU
5、最近最常使用替换策略MRU Replacement
1Sequential Scanning Performance - MRU
6、练习题
1判断真假
2LRU、MRU、Clock相关问题 1、介绍
我们前面简略讨论了 DBMS 的最低级别如何管理磁盘空间以及基于页面的数据库系统中如何管理文件和索引。现在我们将探讨 DBMS 中这两个级别之间的接口 - 缓冲区管理器the buffer manager。 缓冲区管理器负责管理内存中的页面并处理文件和索引管理器的页面请求。请记住内存空间是有限的因此我们无法负担得起将所有页面存储在缓冲池中。缓冲区管理器负责淘汰策略即在空间填满时选择淘汰哪些页面。当页面从内存中淘汰或新页面读入内存时缓冲区管理器会与磁盘空间管理器通信执行所需的磁盘操作。 2、缓冲池
内存通过将空间划分为页面可以放置的帧而转化为缓冲池。一个缓冲帧可以容纳与一个页面相同量的数据因此一个页面完美地适应一个帧。为了有效跟踪帧缓冲区管理器在内存中为元数据表分配了额外的空间。 该表追踪了4个信息
1. 与内存地址唯一关联的 “框架ID” 2. 用于确定框架当前包含哪个页面的 “页面ID” 3. 用于验证页面是否已被修改的 “脏位” 4. 用于跟踪当前使用页面的请求者数量的“Pin计数”
3、处理页面请求
当从缓冲管理器请求页面并且页面已经存在于内存中时页面的引用计数会递增并返回页面的内存地址。
如果页面不在缓冲池中且仍有空间将找到下一个空框架并将页面读入该框架。页面的引用计数设置为1并返回页面的内存地址。在页面不存在且没有空框架的情况下必须使用替换策略确定要驱逐的页面。
替换策略的选择在很大程度上取决于页面访问模式并通过计算页面命中次数选择最优策略。页面命中是指可以在内存中找到请求的页面而无需访问磁盘。每个页面未命中会产生额外的IO成本因此良好的淘汰策略对性能至关重要。访问模式的命中率定义为#页面命中次数 / (#页面命中次数 #页面未命中次数)或更简单地说#页面命中次数 / #页面访问次数。
此外如果被驱逐的页面的脏位被设置则将页面写入磁盘以确保更新被持久化。如果在内存中对页面进行更新则将脏位设置为1。一旦页面被写回磁盘脏位就被设置为0。
一旦请求者完成其工作负载它负责通知缓冲管理器减少其先前使用的页面的引用计数。
4、LRU替换和时钟策略
一个常用的替换策略是 LRU最近最少使用。当需要将新页面读入已满的缓冲池时将淘汰最近最少使用、引用计数为 0 且 Last Used 列具有最低值的未固定页面。为了追踪页面的使用情况在元数据表中添加了一个 Last Used 列用于记录页面引用计数减少的最新时间。LRU 是一个有效的策略选择因为它会保留常被访问的页面在内存中由于它们经常被访问因此很可能是最近使用的。 实现 LRU 通常可能成本较高。时钟策略提供了一种替代实现它使用元数据表中的一个 ref bit最近被引用列和一个时钟手变量来高效地近似 LRU。使用 ref bit 可以降低空间和时间成本。只需每个框架一个比特而不是多个比特来存储 Last Used 值。在时间方面缓冲管理器只需跟随clock hand。在 LRU 中缓冲管理器必须花费时间搜索 Last Used 列中的最小值。 时钟策略算法将元数据表视为帧的循环列表。它在开始时将时钟手设置为第一个未固定的帧并在将每个页面最初读入帧时将其相应行的ref bit设置为1。该策略在尝试淘汰时的工作方式如下 1. 遍历表中的帧跳过固定的页面并在到达末尾时绕回到帧0直到找到第一个未固定且ref bit 0的帧。 2. 在每次迭代期间如果当前帧的ref bit 1则将ref bit设置为0并将时钟手移动到下一个帧。 3. 在到达ref bit 0的帧时淘汰现有页面如果dirty bit被设置则将其写入磁盘然后将dirty bit设置为0读取新页面将帧的ref bit设置为1并将时钟手移动到下一个帧。 如果访问当前在缓冲池中的页面则时钟策略将页面的ref bit设置为1而不移动时钟手。
1顺序扫描性能 - LRU
LRU 总体上表现良好但在一组页面 S其中 $|S| $ 缓冲池大小被多次重复访问时性能会受到影响。这种访问模式称为顺序淹没经常在数据库工作负载中出现比如在表中扫描每个记录。
为了突显这一点请考虑一个使用 LRU 的 3 帧缓冲池具有以下访问模式
A B C D A B C D A B C D A B C D 5、最近最常使用替换策略MRU Replacement
另一个常用的替换策略是 MRU最近最常使用。与淘汰最近最少使用的未固定页不同MRU 策略淘汰最近最常使用的未固定页根据页面的固定计数最后一次减少的时间来衡量。
1Sequential Scanning Performance - MRU
起初使用这种策略可能会显得违反直觉但考虑一个使用 MRU 的 3 帧缓冲池的访问模式
A B C D A B C D A B C D A B C D 显然在发生顺序淹没访问模式时MRU 在页面命中率方面远远优于 LRU。
6、练习题
1判断真假
a. 缓冲池中的每个帧都是一个磁盘页面的大小。 真。帧的大小被定义为磁盘页面的大小。 b. 缓冲管理器代码而不是文件/索引管理代码负责设置页面的脏位。 假。页面的请求者文件/索引管理代码设置脏页。 c. 脏位用于跟踪页面的受欢迎程度。 假。脏位用于跟踪页面在写回磁盘之前是否已被修改。引用计数用于跟踪受欢迎程度。 d. 使用LRU策略时引用位用于在替换页面之前为页面提供“第二次机会”留在内存中。 假。引用位不用于LRU策略。它们用于时钟策略。 e. 对文件进行顺序扫描时当文件小于缓冲池时使用MRU或LRU将具有相同的命中率从空缓冲池开始。 真。由于我们可以将所有页面放入内存因此在顺序扫描期间我们不需要驱逐页面。 f. 页面的引用计数只能由缓冲管理器递减。 假。引用计数由请求页面的人递减表示他们已经使用完毕。 2LRU、MRU、Clock相关问题
对于以下问题我们有一个初始为空的缓冲池其中有4个缓冲帧。对于访问模式
A B D D E A E C A B C A E
a. LRU的命中率是多少
b. 当LRU完成时缓冲池中有哪些页面
c. MRU的命中率是多少
d. 当MRU完成时缓冲池中有哪些页面
e. Clock的命中率是多少
f. 当Clock完成时缓冲池中有哪些页面 详细的访问模式如下图所示。在 LRU 和 MRU 中行数对应于缓冲帧的数量每列对应于一个单独的访问其中字符表示缺失星号表示命中。 a. 7/13 b. A, C, B, E c. 7/13 d. E, B, D, C e. 6/13 f. C, A, B, E 以上DBS note4Buffer Management
祝好。
