【优秀硕士论文参考】一种嵌入式移动实时数据库管理系统缓冲区管理机制研究.docx

分类号学号学校代码密级公开律中科技火掌硕士学位论文一种嵌入式移动实时数据库管理系统缓冲区管理机制研究姓名：专业:计算机软件与理论指导教师：辩论时间：2008年5月28日摘要随着移动通信技术的快速开展和移动计算机的大量普及，由移动计算、实时应用结合传统数据库技术而形成的嵌入式移动实时数据库系统已成为数据库领域的新兴热点课题。其缓冲区管理在数据库管理系统中有着特殊的根底性地位，它也要同事务调度，并发控制策略一样充分考虑资源、时效、应用环境的限制，才能设计有力支持事务的实时性和移动性的高效的缓冲区管理算法。传统的缓冲区管理算法主要借鉴操作系统的页面管理算法如LRU,FIFO,CLOCK等,实现虽然简单但是不适合移动实时环境；另外一个研究方向就是多缓冲池的配置，实现比较困难。同时对移动数据库的研究很多都是以内存数据库为前提，也很少考虑缓冲区管理，实际上嵌入式移动数据库不一定都是内存数据库.随着半导体技术的开展，很多嵌入式移动设备都配有一定容量的外存来满足数据持久化需求。所以研究新的Emrtdbms缓冲区管理策略非常必要。结合嵌入式、移动、实时环境的特点，充分考虑播送策略，实时数据库系统事务的特征、数据特点，一套新的以提高缓冲页命中率和提高实时事务按时完成比率为目标的客户端和效劳端缓冲区管理算法：识别事务截止期的混合优先级缓冲区管理算法和识别数据特征和事务截止期的综合优先级缓冲区管理算法充分考虑了以上新特点；通过在IinUX平台下利用多进程程序设计技术设计的客、服端缓冲区管理原型系统，从缓冲区缺页率、实时事务错失率等方面进行性能评测实验，实验结果显示它与其它几种算法相比具有相对较好的综合性能。关键词：缓冲区管理，替换策略，缓存，截止期AbstractWiththefastdevelopmentofmobilecommunicationtechnologyandthelargenumberofpopularmobilecomputation,EmbeddedMobileReal-timeDatabaseSystemwhichintegratethemobilecomputation,real-timeapplicationandtraditionaldatabasetechnologybecomeafocusintheresearchofdatabase.Thebuffermanagementinthissystemisinaspecialbasicposition,whichshouldconsideraboutthelimitationofresource,timeandapplicationofenvironmentaljustlikedispatchandcontrolstrategy,thendesignaefficientbuffermanagementalgorithmwhichsupportthereal-timeandmovementofthetransaction.TraditionalbuffermanagementalgorithmsarefromtheoperatingsystemmanagementpagesalgorithmssuchasLRU,FIFO,CLOCKetc,althoughtherealizationofthesealgorithmsaresimplebuttheyarenotsuitableforreal-timemobileenvironment;anotherresearchdirectionismorebufferpoolsconfigurationandtherealizationofthealgorithmisdifficult.Atthesametimetheresearchesofmobiledatabasearealotofmemorydatabaseastheprerequisite,andrarelyconsiderthebuffermanagement;embeddedmobiledatabaseisnotnecessarilymemorydatabase.Withthedevelopmentofsemiconductortechnology,alotofembeddedmobiledevicesareequippedwithoutermemorytomeetthedemandfordatapersistence.Therefore,anewstudyEMRTDBMSbuffermanagementstrategyisnecessary.basedonembedded,mobile,real-timecharacteristicsoftheenvironmentandthinkcarefullyaboutthebroadcastingstrategy,real-timedatabasesystemtransaction,characteristicsofthedata,thenproposethatbothclientandserverbuffermanagementalgorithmswhichregardincreasingthebufferpagehitrateandimprovingreal-ti-metransactioncompletedratioontimeastheobjectiveofalgorithmsefficiency,theyarerespectivelytheintegrativeprioritywithdeadlinebuffermanagementalgorithm(IntePrio-dl)andthecompositiveprioritywithdatacharacteranddeadlinebuffermanagementalgorithm(ComPrio-dc&dl),moreoverdesignedthebuffermanagementprototypesystemofclientdbmsandserverdbmsbasedonlinux.SimulatedexperimentshowsthattheIntePrio-dandComPrio-dc&dlarebetterthansomeotherstrategiesonbufferpagesmissingandtransactionmissingrate.Keywords:buffermanagement,replacementstrategy,cache,deadline摘要IAbstractII1绪论1.I课题背景(1)1.2 嵌入式移动实时数据库概况(1)1.3 嵌入式移动实时数据库管理系统(5)1.4 数据库管理系统缓冲区(8)1.5 本文组织(9)2数据库缓冲区管理的根本策略和方法2.1 数据库管理系统缓冲区管理器的工作原理及主要任务(11)2.2 数据库缓冲区分配方法(14)传统数据库管理系统缓冲区替换算法(16)2.4 实时数据库管理系统缓冲区替换算法(20)2.5 本章小结(22)3一种嵌入式移动实时数据库管理系统缓冲区管理机制3.1 引言与根本假设(24)播送模型(24)3.3 EMRTDBMS客户端(EMRTDBMSCIient)缓冲区管理(26)3.4 EMRTDBMS效劳器端(EMRTDBMSSerVer)缓冲区管理(41)预刷新策略的应用(46)算法性能理论分析(47)本章小结(48)4系统实现与性能评价4.1缓冲区管理原型系统(49)系统性能评价(52)4.3本章小结(55)5总结与展望工作总结(58)5.2展望(58)致谢(60)参考文献(61)1绪论1.1 课题背景数据库系统作为一种重要的计算机科学开展至今已有几十年历史，随着嵌入式系统的广泛应用及嵌入式实时操作系统的不断普及和移动通信技术的快速开展，嵌入式移动实时环境下的数据管理问题成为系统中的重要环节，由移动计算、实时应用以及嵌入式环境结合传统数据库技术而形成的嵌入式移动实时数据库，现己成为数据库系统领域的新兴热点课题。由于嵌入式移动实时环境的特性，与传统数据库管理系统相比，它可以支持更多新的应用：数字化信息效劳，公共信息发布，用户通过无线便携设备了解新闻、股票、天气等资讯信息，并及时做出决策；军事作战，每个士兵或作战设备都作为独立的系统单元，实时处理战场信息并与效劳器进行交互，效劳器综合各单元的移动信息指挥整个战场行动；移动电子商务，随着用户所处地点的改变，数据库查询将总是显示最新有效的适宜商务信息，满足商务用户对位置相关和异地操作的特殊要求。本课题组的目标便是开发出一个嵌入式移动实时环境下的数据库管理系统，能够高效的管理移动端数据库和效劳器端的数据库。1.2 嵌入式移动实时数据库概况嵌入式系统嵌入式系统是指以应用为中心，以计算机技术为根底，软硬件可裁剪，对功能、可靠性、本钱、体积、能耗等有严格要求的专用计算机系统，它一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统及用户应用软件等几个局部组成。随着集成电路技术、计算技术、软件工程技术等的日趋成熟和完善，嵌入式系统正深入社会生活各个领域。嵌入式硬件受本钱和体系功耗限制，微处理器一般只有存储器、I/O控制和少量逻辑电路，在嵌入式操作系统上运行的软件要充分考虑这些硬件的性能问题，做相应的特殊优化和设计，以充分利用嵌入式系统资源，提高嵌入式设备的应用效率。移动计算环境计算环境先后经历了集中式计算、分布式计算、网络计算以及移动计算等多种模式，目前受到广泛关注的移动计算技术的迅猛开展，使得各类无线计算设备在没有固定物理连接的情况下也能准确及时地把数据传输到中央信息系统并与之交互，分担全系统的计算压力，使信息能够被位于任何地点的计算设备共享。由于移动计算环境的复杂性，其系统通常采用移动结点和固定结点混合分布的结构。移动设备经无线通道通过移动效劳基站和固定网络相连，可在基站覆盖的一定区域内自由正常使用，整个区域被划分成许多小的单元，各个单元由特定的移动效劳基站管理，基站作为固定结点以高速有线网络互联。与传统分布式系统不同，移动计算环境作为一个动态的分布式系统具有如下新的特点：(1)移动性；(2)频繁断接性；(3)网络条件多样性；(4)网络通信非对称性；(5)移动设备电源支持时间有限；(6)移动网络可靠性低；(7)系统规模可伸缩。实时数据库实时数据库系统(Real-TimeDataBaseSystemzRTDBS)是事务可以具有定时特性或显式定时限制的数据库系统。系统的正确性不仅依赖于逻辑结果，而且依赖于该逻辑结果产生的时间。RTDB并非是数据库和实时系统两者的简单结合，它需要对一系列的概念、理论、技术、方法和机制进行研究开发，如数据模型极其语言，数据库的结构与组织;事务的模型与特性，尤其是截止时间及其类型;事务的优先级分派、调度和并发控制协议与算法;数据和事务特性的语义及其与一致性、正确性的关系，查询/事务处理算法与优化；I/O调度、恢复、通信的协议，缓冲区调度算法等等，这些问题之间彼此高度相关且与应用的类型紧密相联。实时数据库的主要特性主要表现在数据特征和事务特征上。1 RTDB的数据特征在RTDB中，数据随外部环境状态的变化而快速变化，其值只在一定的时间内是“流行的，过时那么无效了，故系统除了维护数据库内部状态（数据值）的正确性、相容性外，还必须同时维护内部状态与外部环境实际状态的一致性，以及数据用来决策或推导新数据时在时间上的相互一致性。定义1.1RTDB中的一个数据对象D可定义为一个三元组<DV,DTP,DEVI>,它们分别为D的当前值、采样时间、外部有效期（外部现实对象状态变化的时间间隔），有效期即自DTP算起DV有效的时间长度。对于每一D有内部一致性、外部一致性和相互一致性特征。1）内部一致性dv满足预先定义的数据库内部状态的完整性和一致性限制。这就是传统意义下的数据正确性；2）外部一致性设TC为当前或检测时间，当且仅当（TC-DTP）<=DEV”那么称D是外部一致的，即DV和对应的外部现实对象的状态是一致的；3）相互一致性用来决策或导出新数据的一组相关数据称为一个相互一致集，记为R,其中的数据必须尽可能地在一个允许的公共时间期内被采样（或导出），这个公共时间期就称为R的相互有效期，记为RMVI,对于R中的任两个数据D和D',有IDTP-D'TP<=RMVI,那么说R中的数据是相互一致的。外部一致性和相互一致性都是关于时间的，故统称时间一致性。既是内部一致又是时间一致的数据才是正确的。2 RTDB的事务特征由于实时任务往往有内部结构和相互之间的联系，传统的“原子的、平坦的数据库操作序列的事务概念及模型对实时事务不适合。RTDB事务表现出了许多不同的特征，这里只给出其标识性特征。定时可以是绝对、相对或周期时间。RTDB的定时性一方面由数据的时间一致性引起，此时它往往取周期或定期性限制的形式，如“每5秒取样一次、"7:OO启开工控设备等;定时性的另一根源是对现实世界施加于系统的反响时间的要求，这时它典型地取施加于非周期事务的截止时间限制的形式，如“假设温度到达2000度，那么在3秒内加冷却剂到反响堆。实时事务的新特性主要表现为：正确性，事务执行不仅要求逻辑结果上的正确，还要求时间正确性，事务价值与是否在给定截止期内提交有关；可预测性，某些系统中实时事务错失截止期将导致灾难性后果，因此要求能够预测这些事务的执行时间，以确保事务能够满足截止期，从而保证系统的正常运行；优先性，不同事务的提交对系统带来不同的价值，依照任务的紧迫度和价值大小划分事务的优先级，先保证高优先级事务在截止期内完成提交。为满足上述数据一致性和实时特征，实时事务通常需要维护的一些属性有：绝对截止期、到达时间、相对截止期、估计执行时间、剩余执行时间、松弛时间、价值函数等。依照实时事务的特征，按价值函数可分为以下几种类型：实时事务的价值与其是否在截止期内完成提交有很大关系，不同的系统中事务超截止期带来的影响不同，由此可以利用事务的价值函数建模。硬截止期实时事务，又称硬实时事务，超过截止期会给系统带来严重后果，价值函数为负值，对应于一些危急性紧迫任务。软截止期实时事务，又称软实时事务，超过截止期后仍存在一定价值，但会不断下降，直至到某一时刻（称为最终有效时间）降为零，之后保持为零而不会变负。固截止期实时事务，又称固实时事务，一旦到达截止期，其价值立刻降为零，此后保持不变，不会为负，它是软实时事务的最终有效时间和截止期重合的特例。图Ll反映了这几种不同类实时事务的价值函数，其中两坐标轴V和t分别表示价值和时间，S是事务的启动时间，d是截止期，e那么表示最终有效时间，在t<s时V=O表示事务启动前对系统是无价值的。（a）硬实时事务（b）软实时事务（C）固实时事务图Ll实时事务按价值函数分类图嵌入式移动实时数据库管理系统数据库技术总是与计算环境的一定开展阶段相适应，新的计算环境和需求促成数据库技术的形成和开展。与通用的桌面系统不同，由于嵌入式系统没有充足的内存和磁盘资源，微处理器的处理能力也有限，所以不管是嵌入式的操作系统还是数据库管理系统，都要尽量占用很少的系统资源。嵌入式移动数据库系统可以支持移动用户在多种网络条件下有效地访问所需数据，完成数据查询和事务处理；通过数据库的同步技术和数据播送技术，即使在断接的情况下用户也可以继续访问所需数据,这使得嵌入式数据库系统具有高度的可用性；它还可以充分利用无线网络固有的播送能力，以较低的代价同时支持多移动用户对后台主数据源的访问，从而实现高度的可伸缩性，这是传统的客户/效劳器或分布式数据库系统所难以比较的。同时;实时数据库系统是处理具有时间约束事务的数据库系统，一般实时事务的时间约束用截止期来表示，即实时事务必须在截止期内提交。在实时数据库系统中，衡量系统性能的标准不是平均响应时间和吞吐量，而是错失率，即错失截止期的实时事务所占的比率，特别是硬实时事务的错失率，严格意义上的实时数据库系统是不允许有失败的，因为可能产生灾难性的后果，实时事务一般按照由截止期和价值确定的优先级进行调度。因此，在嵌入式移动实时环境中，数据库系统需要不断跟踪环境变化而产生时间约束，以保证数据有效性，做出正确决策。综上所述，嵌入式移动实时数据库系统除了要满足传统数据库的要求外，更是在占用存储空间、可靠性、可管理性、移植性和平安性等方面有进一步要求，作为实时数据库技术在嵌入式系统中的一种应用，其软硬件结构有了很大的变化，需要对实时数据库的软件模块进行剪裁、配置。此外，实时数据库软件需要具有较高的可靠性和实时性，这对资源有限的嵌入式系统而言是一个很大的挑战，即如何在有限的系统资源的根底上保证数据有较高的时效性和一致性。由于嵌入式移动实时数据库应用市场需求的与日俱增，越来越多的商家都投入到这个大的开放性的市场中，也出现了一系列各具特色的商业产品。在国外，有SybaSe提供业界领先解决方案的SQLAnyWhere,Orade针对移动计算推出的OraCIeLite,IBM的DB2SateIlite及DB2Everyplace,以及历史悠久的BerkeleyDB和微软的MSDE引擎等等；在国内，理论研究取得很大进步的同时，实际产品开发也取得了一些成果，较有代表性的有东软的OPenBASEMini,人大金仓研发的“小金灵系统等。现在嵌入式移动实时数据库已经形成了较为成熟的产业链，成为嵌入式系统不可缺少的局部,但是相对国外数据库的开展模式而言，国内起步较晚、应用面较小、应用领域也不够广，同时存在着理论研究、原型设计与产品商业化别离的缺乏。不过随着计算终端的小型化，应用领域的不断扩展，可以预见，不久的将来其应用将进入到移动互联网、移动电子商务政务、移动物流、移动金融系统、移动新闻等多个商业与经济领域。典型的嵌入式移动实时数据库管理系统体系结构如图1.2所示，在这个移动计算环境中高速固定网络局部构成连接固定结点的骨干，固定网络由多个固定主机效劳器(FixedHost,简称FH)和移动效劳支持结点(MobileServerStation,简称MSS)组成，每个MSS负责建立一个无线网络单元，无线单元内的移动设备MObiIeUnit(简称MU)与MSS之间是通过无线网络连接，MU又称为移动计算(MobileCompute,简称Me)或者移动客户机。现在使用的无线通信方式有：卫星通信系统、蜂窝系统、红外线技术和无线局域网。固定主机中安装有嵌入式移动实时数据库管理系统的效劳器端，多个效劳器组成一个分布式系，称为中心效劳器，它们之间的同步对MC透明，客户端在逻辑上可把中心效劳器组当作一个中心效劳器（称为EMRTDBMS图移动实时数据库管理系统典型结构图移动客户端主机MC上有自己的嵌入式数据库，整个数据库管理系统的客户端局部功能可以局部地在MC上执行，在用户不需要获取当前全局数据的情况下，MC能独立完成用户任务。当用户执行移动事务时，MC先局部执行该事务，维持本地数据一致性，再提交给中心效劳器数据库以保证全局数据同步，中心效劳器上根据时间特性和网络状况合理地接收数据，Emrtdbmsserver执行移动事务并更新中心数据库，然后提供一定的播送机制将最新的数据库状态传送给所有有相关应用需求的移动客户主机，维持全局数据的一致性。1.4 数据库管理系统缓冲区1.4.1 数据库管理系统缓冲区的根本功能因为磁盘设备等外存的大容量和抗挥发性，以及相对较低的位本钱，一般数据库管理系统采用磁盘作为存储大量数据的存储介质，但是目前的操作系统访问的数据必须位于主存中，且主存访问时间远远低于磁盘访问时间，因此直接从内存获取所需要的数据将大大缩短事务的执行时间，但是数据库的数据量一般很大,无法把全部数据放在内存中,而只能将一局部数据放入内存,这就给事务的执行带来了不确定性。因此，缓冲区在数据库系统的数据安置环节中起着非常重要的作用，它是根本文件系统和面面向元组的文件系统之间的调解器，数据库的高性能要以高效的缓冲机制作为底层支持。1.4.2 嵌入式移动实时数据库管理系统缓冲区D缓冲区管理的主要任务数据库管理系统缓冲区管理器的主要任务就是使得页面可以在内存中寻址，并且同日志管理程序和恢复管理器协调一致地向磁盘写页面，同时它应把事务将要访问的数据尽量多地换入内存中,尽可能的减少实际的磁盘1/0次数，使执行速度得以提高。缓冲区管理主要包括三方面：查找缓冲区，分配缓冲区和缓冲页替换。缓冲替换算法是用来决定将哪些数据放在内存以及存放多长时间的一组策略。2)数据库管理系统缓冲区管理有效性评价标准传统的缓冲区管理的目标是提高缓冲区的吞吐量和整体利用率，主要是以缓冲页面的命中率的大小为好坏评价标准，但是嵌入式实时数据库应用于对数据刷新和处理要求时限性很强的系统,其事务与一般数据库的事务和数据相比,一个最大的不同是具有时态约束。由于新的特点,用于关系数据库的调度方法,例如事务调度、I/O调度以及缓冲区调度都不能直接用于实时数据库系统中,因为传统的调度方法很少考虑截止期和事务的类型，所以嵌入式实时数据库管理系统缓冲区的有效性标准不能单纯的以页面命中率为标准，而应该主要以事务的错失率的多少为评价的标准的同时,辅以页面命中率的标准，才能适应嵌入式移动实时应用的要求。1.5 本文主要研究内容及组织本课题组的目标是研究嵌入式移动实时数据库根本理论和实现技术最终开发出一个支持能够支持弹载、车载、舰载、综合航点系统、战术通信系统、武器自动导航等军事应用需求的数据库管理系统，称为EMRTDBMS(EmbeddedMobileReal-timeDatabaseManagementSystem),体系结构采用1.3节图1.2所示的典型移动计算环境的体系结构。客户端设备带有外存储器，客户端的数据库为非内存数据库。它是实时数据库的进一步开展，是它在嵌入式和移动计算环境的应用，有很多新特点，对于其缓冲区应充分考虑各方面的特点来设计缓冲区管理器，由于目前没有专门针对EMDBMS的缓冲区管理的研究，必须把传统DBMS的缓冲区管理、MDBMS的缓存管理和嵌入式移动环境充分结合来设计适宜的缓冲区管理器。本文结合课题组工程要求拟从EMDBMS的体系结构、事务、播送策略、数据特性以及系统的工作机制方面来考虑EMRTDBMS缓冲区管理器的设计。本文的组织结构安排如下：第一章介绍嵌入式移动实时数据库的理论和应用背景，简单概括该环境下缓冲区管理的新特点和新需求；第二章纵览国内外常用的缓冲区管理文献，分析它们各自的思想特点和适用环境，特别是如何适应嵌入式移动实时环境；第三章根据课题组的工程主题提出一种综合管理策略，针对此策略分析了已有的缓冲区管理策略的不适宜之处，提出改进思想，设计了一种基于嵌入式移动实时数据库数据特征和事务特征的综合缓冲区管理算法，同时进行理论分析；第四章应用上一章中的算法开发一个缓冲区管理原型系统，并选定模拟移动实时环境的参数，在该原型系统上对算法进行性能评价实验，并与传统算法进行性能比较;第五章对全文工作进行总结，并指出以后研究工作的方向。2数据库缓冲区管理的根本策略和方法2.1数据库管理系统缓冲区管理器的工作原理及主要任务工作原理缓冲区管理器是数据库管理系统（以下简称DBMS）的一个重要部件，处于DBMS的底层,缓冲区管理的是内存中的一个分段，这个分段被分成相等大小的局部称之为框架，每个框架可以容纳一个或多个页面，为了方便一般把框架大小设置成与磁盘块大小相等。缓冲区管理器为高层模块提供效劳，其相互作用的原理如下：首先缓冲区的模块向缓冲区管理器提出效劳请求，并给出需要访问页的页号。然后缓冲区管理器所做的工作如下：1）在缓冲区中搜索检查所请求的页是否在缓冲区中。如果找到了，就返回页所在内存框架的地址给调用者。2）寻找空闲框架如果需要的页面不在缓冲池中，那么检查是否有一个当前不包含有效页面的框架。3）确定被替换的页面如果没有空闲框架存在的情况下，就必须找到一个包含有效页面的框架替换,用以提供应新的调用者，如果找不到可以被移出的页面那么报警处理。4）回写己修改正的页面到磁盘如果被替换的页面在缓冲区中被修改了，那么应按照先写日志协议把它写回到它对应的磁盘块里。如果没有修改，那么可以简单地覆盖它。5）建立框架地址确定用哪个框架来容纳所请求的页面。6）确定块的地址利用文件目录和根本文件描述项，把页的标识符按照约定的规那么转换成对应的文件描述符和块号，把该块读入到所选定的内存框架中。最后缓冲区管理器返回框架的首地址给调用者。主要任务缓冲区管理主要任务包括：查找缓冲页，分配缓冲区和缓冲页替换三方面。1 .搜索缓冲页当数据库管理器收到一个页面访问请求时，它就首先在缓冲区中搜索，查找相应的页是否在缓冲区中。因为页面访问请求在数据库系统中是非常频繁的，所以搜索策略的有效性就非常重要。按照搜索策略的不同可以分成如图2.1所示的几类。搜索策略I排序表非排序表链表哈希表图2.1DBMS缓冲区搜索策略分类图直接搜索：直接搜索就是在缓冲区中顺序检查各缓冲页的头部的相关字段看是否是所要找的页面。由于没有考虑页面的排序，所以这种搜索方法查找成功的平均查找长度是N2（设缓冲区的总页数是N）,不成功时的长度是N.现在的DBMS一般都工作在虚存系统之上，缓冲区管理器管理的都是虚存，在其中搜索页将会出现在虚存空间的长距离寻址，很可能导致频繁的缺页请求，从而使增加了页面调度的负担而影响系统性能。因此应该采用基于表的搜索技术，才能提高寻址速度，同时减少内存缺页率。间接搜索：间接搜索一般要借助于额外的表，转换表用页号作为在表中的位移，缓冲区的入口有N个（N为缓冲区中虚存框架数。查找成功时的平均查找长度在经过排序和没有排序的表中均为N/2,但是有序表在查找不成功的时的平均长度减少到N/2,而且有序表可以使用二分查找等效率比较好的技术。然而当表条目需要插入和删除时就会涉及到比较复杂的操作。通过为有序表建立索引或用平衡二叉树来实现，可以把时间复杂度降到更低，到达对数级，不过相关的更新等维护操作的代价将会更大。一个带有链式入口的表与顺序表相比有下面两方面的优势：1）由于没有入口条目需要移动，所以更新代价比较小。2）链接顺序可以用于传递额外的管理信息例如，表项可能链在MRU链中，这时链表就包含了一定的替换信息，可供MRU算法使用。哈希搜索：由于在一个页表中大局部频繁的操作大都直接通过页号来访问，哈希技术在这种应用中可能是最高效的了。通过一个适宜的哈希算法可以将页号转换成页表中的一个位置，通过它找到相应的页表项，这个表项描叙了页信息和页在缓冲区中的当前位置。一般通过链地址法来解决同义词冲突的问题，选定一个适宜大小的哈希表，可以使每次逻辑应用的搜索长度控制在1至1.2之间。一个哈希表的例子如图2.2所示。图2.2哈希表搜索示意图2 .分配缓冲区数据库管理系统缓冲区管理器的缓冲区分配算法为数据库中的并发事务分配可用的缓冲框架。此算法与缓冲页面替换算法密切相关，有时缓冲页面的分配算法和替换算法是一个算法，同时用于向各事务分配缓冲页和替换页（如全局MRU,LRU算法）。但是缓冲页的分配与选择替换页的问题在逻辑上是两回事，在比较好的实现中缓冲分配算法应单独考虑。为了设计出较好的页面分配和和替换算法，数据库事务的访问行为特点应该被充分地考虑。在虚拟存储系统中，下面几个数据库引用序列的根本特征明显不同于一般程序的页面引用序列,主要不同点有：(1)由于数据库页是由多个事务共享的集中的资源，故在缓冲中由多个事务并发的使用一个页的情况非常频繁。(2)在某些时候，基于存在的访问路径结构，数据库事务的引用行为是可预测的，通常，包含系统表和较高层次的索引数据等特定数据的页面有比普通数据页高的引用概率。这些可以确定的有特定作用的页当它们被引用时应该以一种特别的方式处理。3 .缓冲页替换如果一个逻辑访问失败，即缓冲管理器接受某一事务的页面访问请求后在缓冲区中找不到请求页，此时缓冲区管理器查找空闲框架而失败时，就必须按照某种策略选择一个页替换为新页腾出框架，这称为缓冲页替换。决定替换哪一页是最关键的，假设刚被替换出去的页在稍后的请求中又被要求调入将会增加系统的开销，增加响应时间，所以寻找一种适宜的策略力争把最不可能用到的页替换掉是设计高效的缓冲替换算法的追求目标。2.2 数据库缓冲区分配方法缓冲区分配算法分类缓冲区分配算法可以分成局局部配算法和全局分配算法。局局部配算法不考虑事务的并发访问页的行为，而把缓冲框架只分配给某一特定的事务使用。由于并发访问同一个数据库页的情况经常发生，所以对于局部缓冲管理算法应设计一种补充的机制处理共享页的缓冲框架分配。局局部配算法可以进一步细分为静态分配和动态分配算法。静态分配算法就是在事务生命期内给某一事务分配的缓冲区框架数恒定。一个简单的局部静态算法就是分配一个固定大小的分区给每个并行的事务单独使用；一些改进的算法可能根据事务开始时的信息，针对不同的事务分配不同大小的分区。局部动态分配算法是分配可变长缓冲分区给各事务，各个分区可以根据引用事务的当前行为增加或减少。与局局部配算法相反，全局分配算法不仅考虑当前运行事务的引用模式，而且还考虑其他事务的引用行为。全局分配的依据是所有事务对数据的获取行为。全局和局部相结合的策略也曾被考虑过。比较清晰的一种。至冲区分配弊法等尺寸缓冲区分配法多尺寸缓冲区（段）分配法动态分配算法图2.3缓冲区分配算法分类图局部静态分配算法的主要缺点（不管是面向事务的和面向页面的）是不管DBMS的负载变化多么频繁它都保持不变性。由于分配给每个事务的缓冲框架数目的不变性，静态分配在一个交叉访问的环境中是非常低效的，故局部静态分配方法一般不予考虑。在局部动态分配算法中，一个事务所分配的缓冲区的大小的增加和减少的依据是该事务的变化的缓冲区空间需求。当一个缓冲缺页发生时，分配算法为事务计算一个最优的大小的分区，根据该事务的页面引用的历史信息，该事务的缓冲区大小可能保持恒定或增加，也可能减少几个框架。同理，基于页面的动态分配算法中缓冲区大小也会改变。例如，某一由数据库管理系统缓冲区由系统区和用户数据区组成，当新的系统页需要安置时就安置到系统区，新的用户数据页就安置到数据区，且各个区的大小可据需求的变化而改变。然而局部算法在计算事务的缓冲大小的最正确值时考虑的仅仅是单个事务的引用行为，全局算法会考虑所有并行运行事务的引用行为特征。所有的页都是用同一种方法来分析而不仅仅考虑请求缓冲页面分配事务的特点。当DBMS缓冲区大小恒定时，全局缓冲分配算法和页面替换算法要保持一致。当产生一个缓冲缺页时，一个专门的缓冲算法就决定哪个页将被替换。这个决策是全局的。由于局部静态的分配算法在数据库环境下比较低效，全局的分配算法与替换算法密切相关，在缓冲替换算法的相关章节介绍，下面较详细的讨论缓冲区的局部动态分配算法。局部动态缓冲区分配算法有名的动态存储分配算法有工作集算法叫工作集算法常用于描述程序和数据库事务的访问行为局部性。事务W(t,m)工作集是该事务在时刻t之前m次页面引用所引用的页面的一个集合，m被称为窗口尺寸.w(t,m)=W(t,m)定义为t时刻工作集的尺寸。一个事务的平均工作集长度常常用来衡量它的局部性，局部性越高，平均工作集长度越小。工作集模型常用于实现缓冲区分配算法。根本原理是在缓冲区中保持一定数量页面以构成事务的工作集，替换时寻找不属于任何事务工作集的页面作为替换页。所以窗口大小m应该谨慎地选定，力争其大小是事务有效执行所需最小页面数。在某一事务高局部性阶段，它的工作集减小，它的多余缓冲页可以重新分配给其他事务使用。一种更深入更精巧的工作集算法能根据事务类型的不同的工作集窗口，从而可以建立一个优先级系统。还有一些改进的动态存储分配算法如：WSCLOCK算法，它是CLoCK算法的一个改进。详细讨论见文献。2.3 传统数据库管理系统缓冲区替换算法数据库页置换发生在逻辑引用失败，且缓冲区没有空闲框架的时候，替换算法根据请求时间的不同可分为预取和请调算法两种。传统的预取算法不仅调入所请求的页面，同时还一起调入在物理上与请求的页相邻的m(m>0)页，与分别调入m+1页相比大大节约了时间。当引用序列是顺序的时候，采用这种策略会减少整体的I/O代价。然而预取将来不使用的页，就会增加I/O负担，更糟糕的事情是预取进来的页把将来可能访问的页替换出缓冲区。这是因为物理上连续的页不一定在逻辑引用序列上连续。关于预取算法的研究请参考文献请求调页算法在出现缺页时，它只调入请求的页面。由于很难预测事务将来的引用行为，预取策略在实际应用中不是很多。请调策略在实际的缓冲区管理中比较广泛。为了区别在DBMS的在虚拟地址空间的内存缺页与在缓冲区中的页，本文称后者为缓冲区缺页。一般缓冲区替换算法在给定缓冲区大小和分配策略前提下的目的都是最小化缓冲区缺页率。最理想的情况是最久的将来被再次引用到的页面被选为被替换的页面,这基于能获知事务的将来引用行为，最有名的是OPT算法【划【划，它是一个理想的状态是上界，最坏的情况是最近的将来被用到的页面被淘汰掉，设计一个合理的算法的下界以随机算法的缺页率为参照更合理，因为它不使用任何和未知引用信息。下面我们以此为参照讨论基于请调的页面级替换算法，基于页面的算法主要分为工作负荷己知的缓冲区管理和基于统计的缓冲区管理两类。基于访问模式的页面级缓冲区管理数据库管理系统对缓冲区的管理与操作系统对缓冲区管理有一个显著不同就是对数据库管理系统而言，其数据访问序列附经过查询优化阶段后就已知，但是对于操作系统而言，诸如此类的信息却很难获得。下面是几个工作负荷己知情况下的缓冲区页面管理算法。1 .基于工作集的缓冲区管理算法文献15口6中通过理论分析以及模拟试验观察到如果分配给DBMS的缓冲区小于工作负荷的活动数据集的大小时，数据在缓冲区中缺失的情况就会频繁发生。鉴于此，提出了一个DBMS冲区管理的算法，该算法给每个事务分配一个大小等于它的活动数据集大小的缓冲链。当某个事务需要访问一个页面，首先在整个缓冲区空间里面查找该页面是否已经被缓存在缓冲区中，如果没有找到，就置换出一个最近最少访问的页面或从公共空闲页面缓冲池获得一个空闲的页面来作为新的缓冲页面的缓存空间。取得了较好的效果，但是此算法的缺点是事务运行时就需要准确地计算工作集大小，且得不到工作集大小的缓冲页数目时就不能投入运行，而必须等待。2 .基于数据库表的缓冲区管理算法文献口刀广泛研究了一般的数据库操作和页面访问的模式。在此根底上，他们提出了一种被称为DBMIN的DBMS缓冲区管理算法，该算法基于数据表对数据库缓冲区进行管理。在他们的研究中，数据库的操作被分为如下几类：1)顺序访问在顺序访问模式中，所有页面被一个接一个顺序访问。在一个无序表上的选择操作中，该表的每个页面仅仅被访问一次，被称为StraightSeqUential(SS);归并连接操作屡次扫描一簇元组记录，这种访问模式被称为CIUSteredSeqUentiaI(CS);如果整个表被屡次访问，例如嵌套循环连接操作，称之为LOoPingSeqUential(LP)。2)随机访问