（计算机科学与技术专业论文）面向应用的缓冲区管理机制的研究与实现.pdf

国防科学技术大学研究生院学位论文 摘要 为了弥补处理器与磁盘之间的速度差距，许多的计算机系统都使用缓冲区来 缓存访问过的磁盘数据。目前主流的缓冲区管理机制主要采用单一固定的缓冲区 替换策略，比如l r u 策略，m r u 策略等。然而，越来越多的应用所表现出数据 访问特点的多样性，单一的替换策略显然已经不再适合多样的应用。 为此，本文结合两种集成多种替换策略、面向应用的缓冲管理机制，提出了 一种新的面向应用的缓冲管理机制，它不仅能够支持应用指定自己的数据访问顺 序模式，根据模式动态选择需要的替换策略。而且可以动态的检测访问顺序模式 的正确性，为应用调整自身的访问顺序模式提供参考。 本文通过分析部分应用的数据访问特点，提出了顺序、循环、概率和时间局 部四种访问顺序模式，新机制根据这些模式集成了l r u 、m r u 和l f u 三种替换 策略，并且指定了访问顺序模式与替换策略的对应关系；为了给应用提供反馈信 息，设置了检测功能，检测应用的实际模式是否与应用指定的模式匹配；在深入 研究了l i n u x 缓冲管理机制之后，在其基础上实现了我们的新机制。 最后，文章通过路径驱动的模拟方法，在d i s k s i m 模拟器上模拟了新机制，测 试结果表明，采用新机制的磁盘f o 系统在磁盘i o 次数和响应时问上都有一定程 度的减少和缩短，性能确实优于传统的采用单一替换策略的系统，而且较之采用 其他的两种面向应用的缓冲管理机制的系统也表现了一定的优越性。 主题词：缓冲区替换策略，访问顺序模式，路径驱动模拟 第i 页 国防科学技术大学研究生院学位论文 a b s t r a c t i no r d e rt of i l lt h es p e e dg a pb e t w e e np r o c e s s o ra n dd i s k , m a n yc o m p u t e rs y s t e m s u s eb u f f e rc a c h et ob u f f e rt h ed i s kd a t at h a th a sb e e na c c e s s e d a tp r e s e n t m o s to ft h e b u f f e rm a n a g e m e n tm e c h a n i s mo n l yu s co n ek i n db u f f e rr e p l a c e m e n tp o l i c y , l i k el r u m r ua n ds oo n b u ts e e nf r o mm o r ea n dm o r ea p p l i c a t i o n s ，t h ec h a r a c t e r so fd a t a a c o 船sa r ed i v e r s i f o r m o b v i o u s l yo n ep o l i c yc a nn o ts u i tm u l t i p l ea p p l i c a t i o n s t h e r e f o r e , u n i f y i n gt w op o l i c y - r e p l a c e m e n t - i n t e g r a t e d a n d a p p l i c a t i o n - s p e c i f i c b u f f e rm a n a g e m e n tm e c h a n i s m ，t h i st h e s i sp r o p o s ean e wa p p l i c a t i o n s p e c i f i cb u f f e r m a n a g e m e n tm e c h a n i s m w h i c hn o to n l yc a ns u p p o r ta p p l i c a t i o n sd e s i g n a t e 出由o w n d a t ar e f e r e n c ep a t t e r n sa n dc h o o s er e p l a c e m e n tp o l i c ya c c o r d i n gt or e f e r e n c ep a t t e r n d y n a m i c a l l y , b u ta l s o c a nd e t e c tc o r r e c t n e s so fr e f e r e n c ep a t t e r n , w h i c hc o u l db e c o n s i d e r e da sar e f e rf o ra p p l i c a t i o nt oa d a p ti t sa c t u a lr e f e r e n c ep a t t e r n t h r o u g ht h ea n a l y s i so f t h e d a t aa c c e s sc h a r a c t e rf r o ms o m ea p p l i c a t i o n s ，t h i st h e s i s p u tf o r w a r df o u rr e f e r e n c ep a t t e r n s ：s e q u e n t i a lr e f e r e n c ep a t t e r n ，l o o p i n gr e f e r e n c e p a t t e r n , p r o b a b i l i s t i cr e f e r e n c ep a t t e r n a n dt e m p o r a l l y - c l u s t e r e dr e f e r e n c ep a t t e r n a c c o r d i n gt ot h e s ep a t t e r n s ，t h es y s t e mi n t e g r a t e st h r e ep o l i c i e sl r u ，m r ua n dl f u ， a n dd e s i g n a t e st h ec o r r e l a t i o nb e t w e e nr e f e r e n c ep a t t e r na n dp o l i c y ；t os u p p l yt h e a p p l i c a t i o nw i t hf e e d b a c ki n f o r m a t i o n t h es y s t e mp r o v i d e sc h e c k - u pf u n c t i o n , t oe h e c k w h e t h e rt h ea p p l i c a t i o n sr e a lr e f e r e n c ep a t t e r nm a t c ht h ed e s i g n a t e dp a t t e m ；a f l e r u n d e r s t a n d i n gb u f f e rm a n a g e m e n tm e c h a n i s mo fl i n u x ，w eb u i l d0 1 1 1 n e wm e c h a n i s m b a s e d0 1 1i t f i n a l l y , t h i st h e s i sr i s et r a c e - d r i v e nm e t h o dt os i m u l a t et h en 蹦m e c h a n i s m0 1 1 d i s k s i ms i m u l a t o r 1 ks i m u l a t i o nr e s u l t ss h o wt h a t t h ed i s ki os y s t e mw i l l ln e w m e c h a n i s mc a nr e d u c et h er e s p o n s el a t e n c ya n dt h ed i s ki 0t i m e ，a n dh a sab e t t e r p e r f o r m a n c et h a nt h et r a d i t i o n a ls y s t e mt h a tr i s eu n i q u er e p l a c e m e n tp o l i c y ，a n di ts h o w s i t sa d v a n t a g eac e r t a i ne x t e n tc o m p a r i n gw i t ho n e su s i n go t h e ra p p l i c a t i o n - s p e c i f i c m e c h a n i s m s k e yw o m s ：b u f f e rc a c h er e p l a c e m e n tp o l i c y ，r e f e r e n c ep a t t e r n ，t r a c e - d r i v e n s i m u l a t i o n 第i i 页 国防科学技术人学研究生院学位论文 表目录 表2 1 模式判断方法1 0 表3 1 缓冲首部字段1 7 表3 2a d d r e s s 字段24space 表3 3a d d r e s s 对象的方法。25space 表4 1if l a g 置位表3 3 表4 2if l a g 新增的表示访问顺序模式的四位3 3 表4 3 页缓冲状态表。3 6 表4 4o p e n 系统调用的标志4 3 表4 5 新增的访问顺序模式的标志4 3 表4 6f e n t le m d 设置表。4 4 表4 。7f e n t l 新增e m d 。4 4 表5 1t r a c e 实例4 8 第1 页 国防科学技术大学研究生院学位论文 图目录 图1 1d e a r 缓冲管理器结构3 图1 2a p p l i c a t i o n - c o n t r o l l e df i l ec a c h i n g 原理图4 图2 1b a c k w a r dd i s t a n c e 示意图8 图2 2f o r w a r dd i s t a l l c e 示意图8 图2 3 定期检测技术示意图9 图2 4 定期检测技术算法实例1 0 图3 2 包含缓冲区和相应缓冲首部的缓冲区页2 6 图4 1 新机制工作原理图3 2 图4 2 活跃链表非活跃链表模式不一致带来的冲突3 5 图4 3 循环访问顺序模式页缓冲的状态转换图。3 6 图4 4 不同模式页缓冲的状态转换图3 7 图4 5 非活动链表轮循扫描方法3 9 图4 6 非活动链表顺序扫描方法。3 9 图4 7 平均分配释放法示例3 9 图5 1 访问顺序模式的检测结果4 9 图5 2 单应用的性能测试结果5 0 图5 3 多应用的性能测试结果5 l 第页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：画塑垂喝鱼篷遮鏖壅i 量地盘坠鸳鱼丝到 学位论文作者签名： 靠淦丝 j 期：。饵i1 月习扣 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留使川彳位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或胡，杓送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全都或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：力辽选因殓篷丑垂鱼星趟螂鱼鱼塞地 学位论文作者签名 作者指导教师签名 立i 能堕 耋l 燃、 j 翻：铆6 年f 硼母日 】j l l | ：妇，年胗肋狎 国防科学技术大学研究生院学位论文 第一章绪论 i i 课题研究背景和意义 随着v l s i 技术的迅猛发展，处理器和磁盘之问的速度差距越拉越大。这种差 距导致磁盘i o 一直是许多系统的性能瓶颈【h2 】。所以位于主存与磁盘之间的缓冲 c a c h e 变得越来越重要。合理的使用缓冲c a c h e 可以减少单独应用的响应时间，同 时通过减少磁盘i o 次数来提高系统的吞吐量。最终，高效的缓冲管理成为操作系 统和数据库管理系统的核心工作之一。 ， 缓冲管理的核心部分是缓冲替换这一块，因为在缓冲区大小固定的情况下， 替换策略的好坏决定了缓冲区命中率的高低。传统的缓冲管理采取固定的替换策 略一i ，r u ( 最近最少使用) 策略。研究表明越来越多的应用表现出不同的数据 访问特点，传统单一的缓冲替换在这些应用面前显得力不从心，具体表现在： - 科学计算 科学计算的数据通常都是从开头到结尾循环几次，刚刚被访闯过的数据缓冲 在一个循环周期内不会被再次访问，然而l r u 抛弃最近最少使用的缓冲块，很有 可能抛弃的是即将被访问的数据，很显然l r u 策略并不适合科学计算类的应用。 f 3 】 一数据库管理 数据库管理同样也是要处理大量的数据，数据库管理系统通常都足以顺序的 或者是奇特的方式扫描大量的数据；理想的内存管理策略每个操作都可能不同。 而且同样存在很严重的内存管理问题【4 】。通常使用标准的l r u 策略管理数据库代 码是可以接受的，但是管理数据就是很困难的。 现代的d b m s 经常通过网络来使用分布式内存和磁盘。组成这些系统的 d b m s 除非是能够基于这些不同种类( d r a m ，f l a s hr a m ，b a t t e r y b a c k e dr a m ) 的内存作决定，否则系统就不是高效的。所以必须由一个面向应用的内存策略来 建立一个精确的模型。 d b m s 通常能够知道如何按照需要管理内存，但是o s 却没有提供一个友好的 可编程的服务允许d b m s 向o s 告知对内存的需要，也不能获得内存当前的使用 状况。在自己的工作区中，d b m s 分配和控制私有的缓冲空间，避免与操作系统 内存管理策略产生冲突。 通常，关系数据库有几种通用的模式，但是他们都不能很好的吻合l r u 策略 的一般假设。f s 】建议o s 应该对d b m s 提供更好的支持，d b m s 应该简单地向操 作系统的虚存管理提出一些“建议”，以便使其能够高效支持d b m s 中大多数的 第1 页 国防科学技术大学研究生院学位论文 缓冲管理职责，避免o s 和d b m s 之间的缓冲管理冲突。 一图形应用 交互式的图形程序普遍都需要成熟的内存管理技术 6 1 。他们通常预先计算大量 的信息来完成实时的交互作用。访问这些信息通常是顺序的，信息所需的物理空 间通常大于可用的物理内存；这可能导致在l r u 替换策略作用下，引起了系统失 效。如果操作系统的替换策略可以适应这些应用的访问顺序模式，那么这类应用 就能够产生更多的图形细节，具有更高的吞吐量( 通过预取或者是面向应用的替 换策略) 。 多媒体应用 包括h d t v ( h i g h d e f i n i t i o n t e l e v i s i o n ) 应用，也需要特殊的内存管理。这些 应用必须有效的管理许多兆字节的实时信息。但是l r u 策略并不符合实时应用的 内存管理要求。虚拟内存管理系统应当是可扩展的、可以适应这些应用的特殊替 换策略要求。d 2 因此，不同类型的应用具有不同的数据访问特性，必须为每种应用选择最优 的策略，目前确实有很多研究针对特定的应用提出了最优或者次优的替换策略， 但是这些策略对于其他类型的应用来说不是最优的甚至是很差的。这种情况下， 如果一个系统中只有一种替换策略，系统的整体性能仍旧没有改观，与原本使用 l r u 策略的系统没有什么差异，所以要想真正提高系统性能，必须将多种替换策 略集成入一个系统，并且能够为不同的应用提供不同的管理策略，这样系统整体 性能才有望提高。本课题就提出了这样的一种面向应用的缓冲管理机制，可以减 少磁盘i o 的次数，增加系统的吞吐量，提高系统整体性能，这对于多类型应用的 系统来说意义重大。 1 2 课题研究的现状及本课题的工作 对于集成实现替换策略的、面向应用的缓冲管理机制，最关键的问题是如何 动态的为应用选择恰当的替换策略。目前这方面的研究主要有两个方向：一个是 由系统动态检测应用的访闯顺序模式，然后根据访问顺序模式与替换策略的对应 关系，选择相应的替换策略；另一种是，由应用自己给系统提供“暗示( h i n t ) ”， 指定其需要的替换策略。 系统动态检测应用访问顺序模式的研究中最有代表性的是j o n g m o oc h o i 等人 提出的d e a r ( d e t e c t i o n b a s e d a d a p t i v e r e p l a c e m e n t ) 机制叽如图1 1 为d e a r 策略的缓冲管理器的结构，其基本原理是将缓冲区的管理分为两个部分：一部分 管理磁盘缓冲的分配，另一部分负责缓冲的替换。前者被称做系统缓冲管理器 ( s y s t e mc a c h em a n a g e r 简称s c m ) ，系统只存在一个s c m ；后者被称为应用缓 第2 页 国防科学技术人学研究生院学位论文 冲管理器( a p p l i c a t i o nc a c h em a n a g e r 简称a c m ) ，每一个应用都分派一个a c m 。 当应用需要缓冲区的时候首先向s c m 提出申请，当s c m 没有足够的缓冲区时， 就向每个应用的a c m 都发一个请求，每个a c m 检测应用的访问顺序模式并选择 对应的替换策略替换一个缓冲区，然后按照优先级从这些缓冲区中选择低优先级 的进程，将它替换出的缓冲区释放给s c m ，s c m 再将这个缓冲区分配给提出申请 的应用。 圆圆圆 图1 1d e a r 缓冲管理器结构 这种机制的主要优点是：能够动态的检测应用的访问顺序模式，并且能够自 适应的调整应用的访问顺序模式，然后选定不同的缓冲替换策略，节省了应用很 多的工作；由于能够比较精确的检测出应用的访问顺序模式，替换策略的选择比 较准确。缺点是自适应产生的策略只是对应用历史状况的总结，因为不能很好预 测应用的未来，因此可能产生策略选择的乒乓效应( 在不同的策略之间来回切换) 。 由应用指定替换策略的研究中，最有代表性的是p c ic a o 等人的面向应用的文 件缓冲机制( a p p l i c a t i o n c o n t r o l l e df i l ec a c h i n g ) 【l i 】。如图1 2 其主要工作原理是： 使用了两层结构的替换策略，首先在应用层中，进程指定自己的替换策略；在内 核层，内核控制缓冲在各进程之间的分配。也就是说当系统中缓冲不足时，内核 向某进程发送替换请求，该进程按照自己指定的替换策略替换出一个缓冲，交给 系统，系统再将空闲缓冲交给需要缓冲的进程。主要的优点是没有访问顺序模式 的检测，直接由应用指定其替换策略，开销很小。主要的缺点是应用需要精确的 了解底层的替换策略，这给应用带来了很多负担，而且当应用错误的指定了替换 策略，系统不能校正，使得系统性能降低。 第3 页 国防科学技术_ 人学研究生院学位论文 u s e r l e v e l k e m e 里q 粤墅q ， 、 i i l i p r o c e s sp ， 、 l i l f 丫：r：f ： l l ， 豳磷啜豳 蔓二二鹾二 l i i f 图1 2a p p l i c a t i o n - c o n t r o l l e df i l ec a c h i n g 原理图 ( 内核和用户进程的碍层替换：( 1 ) 进程p 访问缓冲缺失( 2 ) 内核向进程q 申请缓 冲( 3 ) o 按照自己的替换策略释放一个缓冲b ( 4 ) 内核将b 分配给进程p ) 综合考虑这两种机制，我们决定结合两者的特性，设计一种既能由应用指定 访问顺序模式又能对访问顺序模式进行动态检测的策略：首先由应用在创建文件 时指定文件的访问顺序模式，应用在后续的文件访问中可以再次确定访问顺序模 式，内核在响应应用请求时根据不同的访问顺序模式确定相应的替换策略；内核 提供相应的系统调用接口供应用查询当前的访问顺序模式，应用可以根据查询的 结果知道当前的实际访矧哽序模式是否与原来指定的访问顺序模式一致，在下次 访问的时候就可以考虑更改自己的访问顺序模式。 这样做的目的是：首先应用直接对文件的使用方法负责，因为只有应用才最 清楚自己的需求；其次，文件自身可能的最优访问顺序模式与应用可能需要的文 件访问顺序模式清晰的分离，既可以降低应用开发的难度( 应用可能不需要了解 文件的最佳访问顺序) ，同时恰当支持应用的灵活性；第三，系统不再自适应选 择文件访问的替换策略，可以避免策略选择的乒乓效应 本课题的工作如下： 首先，研究应用的访问顺序模式，为应用指定访问顺序模式提供参考，同时 指定应用访问顺序模式与替换策略的对应关系。 第二，为了实现我们的机制，研究目前主流开源操作系统l i n u x 的缓冲管理机 制。 第三，结合l i n u x 缓冲管理机制的特点，在其上实现新的缓冲管理机制。 最后，通过实验，检验新机制对系统性能的影响。 第4 页 国防科学技术大学研究生院学位论文 1 3 论文结构 论文共分为六章。 第一章是绪论。主要介绍了课题的研究背景、研究意义、研究现状和具体的 工作。 第二章分析了部分应用访问的特点，并对其进行了抽象和分类，提出了四种 不同的访问顺序模式和相关的判断方法，并为每种模式选择最优的替换策略。 第三章分析了l i n u x 缓冲管理机制。对l i n u x 两种缓冲区的数据结构和操作进 行了详细的分析，明确了替换发生的时机与使用的两层缓冲结构的原因。 第四章是本课题的核心部分系统实现，首先展示了系统结构，然后介绍 了实现细节包括数据结构和核心算法的情况，最后介绍了面向应用的接口实现。 第五章对这个系统进行了模拟测试，并分析了测试结果。 第六章对本论文的主要工作进行了总结，明晰各部分的主要工作内容，并明 确了在今后的研究中需要迸一步加强的工作。 第5 页 国防科学技术大学研究生院学位论文 第二章应用的块访问顺序模式 我们知道应用的数据都是以文件块( 磁盘块) 的形式存储在磁盘中，每次访问 需要的磁盘块并进行相应的处理，对于这些块的访问存在一个访问次序，这个次 序可以是乱序的，也可以是有规律的，那么我们所说的块访问顺序模式( b l o c k r e f e r e n c e p a t t e r n ) 就是用来描述块访问次序的规律的。文件块包括控制数据块( 比 如包含磁盘索引节点信息的块) 和数据块，我们主要研究的是数据块所体现的访 问次序规律。 目前的一些研究表明很多的应用都表现出了特定的数据块访问顺序模式，也就 是本文第一章提到的数据访问特性：比如说大部分的科学计算应用都表现出了一 种循环的访问顺序模式，每个数据块都以一个特定的时间间隔被重复访问【。又 比如，许多的数据库应用表现了一种随机( p r o b a b i l i s t i c ) 的访问，以不同的概率 访问不同的索引块和数据块【1 4 】；很多u n i x 的应用表现出了顺序或者时间局部访问 ( t e m p o r a l l y - c l u s t e r e d ) 的访问顺序模式【1 1 “1 ；还有网络客户端和代理表现出了一 种非一致的( n o n - u n i f o r m ) 访问顺序模式【j q ；最后，多媒体应用处理连续媒体， 表现了顺序或者循环的访问顺序模式【1 2 1 。 这一章通过分析这些应用的访问顺序模式，从中提取出了四种特点鲜明的访问 顺序模式，并进行了形式化的描述，之后提出检测访问顺序模式的方法，最后分 析了不同访问顺序模式与不同的替换策略的对应关系。 2 1 用户块访问顺序模式的形式化描述 为了描述和分类的方便，我们对用户访问顺序模式进行抽象，我们对访问顺 序模式进行了如下的定义： 给定一个数据块的集合n = b 。，b 2 ，一，b 。 和一个访问序列是 ，其中w 表示访问的总时问间隔，= b i ( 1 f 肛) 表示在访问 序列中，距离开始t 问隔时应用对块6 ，进行了访闯。那么我们可以将访问顺序模式 定义为在w 时刻内，访问序列 所体现出的对集合n 中数据 块访问的顺序特征。 通过对各种应用的观察，根据访问顺序模式的定义，我们将访问顺序模式分 为四种：顺序，循环，时间局部和概率访问顺序模式。 顺序访问顺序模式( s e q u e n t i a lr c f e r e n c ep a t t e r n ) 特征：对于每个块的访问都是都是相邻的，而且每个块都不会被再次访问。 形式化描述：如果访问序列中任意的元素r i ，i j 满足1 s i s w , 1 j sw ，巧r j ， 第6 页 国防科学技术大学研究生院学位论文 那么访问序列 为顺序访问顺序模式。 循环访问顺序模式( 1 0 0 p i n gr e f e r e n c ep a t t e r n ) ： 特征：对于每个块都是以一个特定的时间间隔进行访问。 形式化描述：如果一个访问序列满足( 1 ) 对于所有的1 f ，l , r t ，并且( 2 ) 对于所有的f i w 一，r l + j = ，那么这个访问为个循环访问。我们称序列 的子序列 为一个循环，为循环的长度。 时间局部访问顺序模式( t e m p o r a l l y - c l u s t e r e dr e f e r e n c ep a t t e r n ) 特征：最近被访问酌块很可能再次被访问。 形式化描述：一个访问序列 如果满足对于t w , 1 i s j s t ， p r o b a b i l i t y ( r t + i = ) p r o b a b i l i t y ( r t + l = r j ) ，那个这个访问就是一个时间局部访问 概率访问顺序模式( p r o b a b i l i s t i er e f e r e n c ep a t t e r n ) 特征：每个块都有固定访问概率，而且每个块都是按照联合概率独立的被访 问。 形式化描述：如果一个访问序列 满足对于所有的 1 s f ，j s 嵋在所有的块中满足不均匀分布，而且当i j 时与是独立的，那么 这个访问为一个概率访问。 2 2 访问顺序模式的检测 2 2 1 块访问属性的定义 为了识别上一节定义的四种访问顺序模式，我们从过去访问的行为提取出几 个块属性，并进行形式化的描述。这几种属性包括：后向距离( b a c k w a r dd i s t a n c e ) 【1 7 】，频率( f r e q u e n c y ) ，前向距离( f o r w a r dd i s t a n c e ) 【1 8 。在本节中我们将对 这些属性进行形式化的描述。 b a c k w a r dd i s t a n c eb d t ( 6 f ) 定义：对于一个访问序列 ，在t 时刻块后l 的b a c k w a r d d i s t a n c e b d t ( 岛) 表示t 时刻之前，最近一次访问岛块的时刻与t 时刻的时间间隔。 形式化描述：如果对于t - x ，s f ，= 岛且- 6 f 则厶t ) - - x 如果b i 没有在r l ，r 2 ，, r t 中出现，则6 吐 ) ；o o f r e q u e n c y 启 ) 定义：给定一个访问序列 ，在t 时刻块6 l 的f r e q u e n c y 启( 6 ) 表示到t 时刻为止，应用对块抚的访问次数。 第7 页 国防科学技术大学研究生院学位论文 形式化描述：办( 包) = 岛在，吒，；，中出现的总次数。 6 f 心。“”。”4 ”“。 图2 1b a c k w a r d d i s t a n c e 示意图 f o r w a r dd i s t a n c e 属 ) 定义：给定一个访问序列 ，在t 时刻块岛的f o r w a r d d i s t a n c e 崩( 6 j ) 表示t 时刻之后第一次访问块岛的时刻与t 时刻的时间间隔。 形式化描述：如果对于，茎， a v g f d ( s u t , t i s t 笋) ，i f i j 时间局部后向距离 a v g 一，d s t l b i i s f ? ) i n o d e ) 就找到了页缓 冲队列，从队列中找到相应的页面就可以读出了。页缓冲的p a g e 结构除了连入附 属的i n o d e 结构的缓冲队列之外，同时也链入到一个散列表p a g eh a s ht a b l e 中的散 列队列中( 图中并没有给出) ，所以寻找目标页面的操作效率很高，并不需要在 整个页缓冲队列中线性搜索。 在写操作的时候，如前所述，一旦目标记录页已经存储在页缓冲中，写操作 只需要把内容写到页缓冲中即可，所以从发动写操作的进程的角度看速度也是很 快的。至于改变了内容的页缓冲，则由系统负责在c p u 较为空闲的时候写入设备。 为了这个目的，内核中设置了一个内核线程k f l u s h d 。平时这个线程总是在睡眠， 有需要( 例如写操作之后) 时就将其唤醒，然后当c p u 较为空闲的时候就会调度 其运行，将已经改变了内容的页缓冲写回到设备上。此外，页缓冲的p a g e 结构还 第1 4 页 国防科学技术大学研究生院学位论文 要链入一个l r u 队列中，要是一个页面很久没有受到访问，内存空间又比较短缺， 就可以把它释放。 d l f y 4 记康块门贞确 m t 删 图3 1l i n u x 缓冲结构框架图 3 2 基本数据结构 冲 纠 在内核中，页高速缓存( p a g ec a c h e ) 来存放页缓冲，缓冲区高速缓存( b u f f e r c a c h e ) 用来存放块缓冲。在下面的章节中页高速缓存和页缓冲表达一样的意思， 缓冲区高速缓存和块缓冲表达一样的意思。 3 2 1 缓冲区高速缓存 每个缓冲区高速缓存都存放一个单独的磁盘块，内核为每个缓冲区高速缓存 维护了很多信息，这些信息包括一个“脏( d i r t y ) 位”，表示内存中的缓冲区已经 被修改，必须写回到磁盘；还包括一个时间标志，表示缓冲区被刷新到磁盘之前 第1 5 页 国防科学技术大学研究生院学位论文 已经在内存中停留了多长时间。 另外，缓冲区的大小可以变化。当需要新缓冲区而现在有没有可用的缓冲区 时，页帧要按需被分配( 3 3 节) 。当空闲内存变得不足时，就释放缓冲区并反复使 用相应的页帧。 为了维护上述信息，缓冲区包括两种数据结构： 描述高速缓存中缓冲区的一组缓冲区首部。 有助于内核快速找到缓冲区首部的散列表，而缓冲区首部描述了与一对给 定的设备号和块号相关的缓冲区。 缓冲区首部( b u f f e rh e a d ) 是一个与每个缓冲区相关的b u f f e r _ h e a d 类型的数据 结构。它包含内核处理缓冲区所需要了解的所有信息。因此，在对每个缓冲区进 行操作之前，内核都要首先检查其缓冲区首部。 缓冲区首部的各字段如表3 1 所示( 只列出了我们比较关心的字段) 。每个缓 冲区首部的bd a t a 域存放对应缓冲区的开始地址。由于一个页帧可以存放多个缓 冲区，因此bt h i sp a g e 域就指向该页中的下一个缓冲区的首部。这个域简化了这 些页帧的存储和检索。bb l o c k n r 域中存放逻辑块号，即在磁盘分区内的索引号。 b _ s t a t e 域中存放以下标志： b h _ u p t o d a t e 如果缓冲区中包含了有效数据就置位。b u f f e r _ u p t o d a t e ( ) 函数会返回这个 标志的值。 b h _ d i r t y 如果缓冲区中的数据是脏数据就置位，也就是说，如果缓冲区中包含有必 须写入块设备的数据就置位。b u f f e r _ d i r t y ( ) 函数会返回这个标志的值。 b h _ l o c k 如果缓冲区加锁就置位，这发生在磁盘移动时所涉及的缓冲区。 b u f f e rl o c k e d ( 1 函数会返回这个标志的值。 b h _ r e q 如果相应的块已经被请求，就置位。b u f f e r _ r e q ( ) 函数会返回这个标志的值。 b h p r o t e c t e d 如果缓冲区是受保护的( 受保护的缓冲区永远不会被释放) 就置位。 b u f f e r 脚o t e c t e d ( 1 函数会返回这个标志的值。这个标志只用来实现缓冲区 高速缓存之上的r a m 盘。 第1 6 页 国防科学技术大学研究生院学位论文 表3 1 缓冲首部字段 s t r u c tb u f f e r _ _ h e a d u n s i g n e dl o n g u n s i g n e dl o n g u n s i g n e di n t k d e v t k d e v t u n s i g n e dl o n g s t r u c tb u f f e rh e a d s t r u e tb u f f e rh e a d s t r u c tb u f f e r h e a d c h a r + s t r u c tp a g e s t r u c ti n o d e bn e x t bb l o c k n r bs i z e bl i s t bd e v br d e v bs t a t e bn e x tf r e e b _ t h i s _ p a g e bd a t a b j m g e 冲突散列表中的f 一项 逻辑块号 块大小 包含缓冲区的l r u 链表 虚拟设备标志符 实际设备标志符 缓冲区状态标志 缓冲区首部链表中的下 一个元素 缓冲区首部链表中的上 一个元素 每页缓冲区链袭 指向缓冲区的指针 指向缓冲区所在的页描 述符 指向缓冲区属于的索引 节点对象 通常，缓冲区首部可能是以下的状态之一： 未用的缓冲区首部 该对象