《【优秀硕士论文参考】一种嵌入式移动实时数据库管理系统缓冲区管理机制研究.docx》由会员分享，可在线阅读，更多相关《【优秀硕士论文参考】一种嵌入式移动实时数据库管理系统缓冲区管理机制研究.docx（65页珍藏版）》请在课桌文档上搜索。
1、分类号学号学校代码密级公开律中科技火掌硕士学位论文一种嵌入式移动实时数据库管理系统缓冲区管理机制研究姓名：专业:计算机软件与理论指导教师：辩论时间：2008年5月28日摘要随着移动通信技术的快速开展和移动计算机的大量普及，由移动计算、实时应用结合传统数据库技术而形成的嵌入式移动实时数据库系统已成为数据库领域的新兴热点课题。其缓冲区管理在数据库管理系统中有着特殊的根底性地位，它也要同事务调度，并发控制策略一样充分考虑资源、时效、应用环境的限制，才能设计有力支持事务的实时性和移动性的高效的缓冲区管理算法。传统的缓冲区管理算法主要借鉴操作系统的页面管理算法如LRU,FIFO,CLOCK等,实现虽然简
2、单但是不适合移动实时环境；另外一个研究方向就是多缓冲池的配置，实现比较困难。同时对移动数据库的研究很多都是以内存数据库为前提，也很少考虑缓冲区管理，实际上嵌入式移动数据库不一定都是内存数据库.随着半导体技术的开展，很多嵌入式移动设备都配有一定容量的外存来满足数据持久化需求。所以研究新的Emrtdbms缓冲区管理策略非常必要。结合嵌入式、移动、实时环境的特点，充分考虑播送策略，实时数据库系统事务的特征、数据特点，一套新的以提高缓冲页命中率和提高实时事务按时完成比率为目标的客户端和效劳端缓冲区管理算法：识别事务截止期的混合优先级缓冲区管理算法和识别数据特征和事务截止期的综合优先级缓冲区管理算法充分
3、考虑了以上新特点；通过在IinUX平台下利用多进程程序设计技术设计的客、服端缓冲区管理原型系统，从缓冲区缺页率、实时事务错失率等方面进行性能评测实验，实验结果显示它与其它几种算法相比具有相对较好的综合性能。关键词：缓冲区管理，替换策略，缓存，截止期AbstractWiththefastdevelopmentofmobilecommunicationtechnologyandthelargenumberofpopularmobilecomputation,EmbeddedMobileReal-timeDatabaseSystemwhichintegratethemobilecomputation
4、,real-timeapplicationandtraditionaldatabasetechnologybecomeafocusintheresearchofdatabase.Thebuffermanagementinthissystemisinaspecialbasicposition,whichshouldconsideraboutthelimitationofresource,timeandapplicationofenvironmentaljustlikedispatchandcontrolstrategy,thendesignaefficientbuffermanagemental
5、gorithmwhichsupportthereal-timeandmovementofthetransaction.TraditionalbuffermanagementalgorithmsarefromtheoperatingsystemmanagementpagesalgorithmssuchasLRU,FIFO,CLOCKetc,althoughtherealizationofthesealgorithmsaresimplebuttheyarenotsuitableforreal-timemobileenvironment;anotherresearchdirectionismoreb
6、ufferpoolsconfigurationandtherealizationofthealgorithmisdifficult.Atthesametimetheresearchesofmobiledatabasearealotofmemorydatabaseastheprerequisite,andrarelyconsiderthebuffermanagement;embeddedmobiledatabaseisnotnecessarilymemorydatabase.Withthedevelopmentofsemiconductortechnology,alotofembeddedmob
7、iledevicesareequippedwithoutermemorytomeetthedemandfordatapersistence.Therefore,anewstudyEMRTDBMSbuffermanagementstrategyisnecessary.basedonembedded,mobile,real-timecharacteristicsoftheenvironmentandthinkcarefullyaboutthebroadcastingstrategy,real-timedatabasesystemtransaction,characteristicsofthedat
8、a,thenproposethatbothclientandserverbuffermanagementalgorithmswhichregardincreasingthebufferpagehitrateandimprovingreal-ti-metransactioncompletedratioontimeastheobjectiveofalgorithmsefficiency,theyarerespectivelytheintegrativeprioritywithdeadlinebuffermanagementalgorithm(IntePrio-dl)andthecompositiv
9、eprioritywithdatacharacteranddeadlinebuffermanagementalgorithm(ComPrio-dc&dl),moreoverdesignedthebuffermanagementprototypesystemofclientdbmsandserverdbmsbasedonlinux.SimulatedexperimentshowsthattheIntePrio-dandComPrio-dc&dlarebetterthansomeotherstrategiesonbufferpagesmissingandtransactionmissingrate
10、.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一种嵌入式移动实时数据库管理系统缓冲区管理机
11、制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 课题背景数据库系统作为一种重要的计算机科学开展至今已有几十年历史，随着嵌入式系统的广泛应用及嵌入式实时操作系统的不断普及和移动通信技术的快速开展
12、，嵌入式移动实时环境下的数据管理问题成为系统中的重要环节，由移动计算、实时应用以及嵌入式环境结合传统数据库技术而形成的嵌入式移动实时数据库，现己成为数据库系统领域的新兴热点课题。由于嵌入式移动实时环境的特性，与传统数据库管理系统相比，它可以支持更多新的应用：数字化信息效劳，公共信息发布，用户通过无线便携设备了解新闻、股票、天气等资讯信息，并及时做出决策；军事作战，每个士兵或作战设备都作为独立的系统单元，实时处理战场信息并与效劳器进行交互，效劳器综合各单元的移动信息指挥整个战场行动；移动电子商务，随着用户所处地点的改变，数据库查询将总是显示最新有效的适宜商务信息，满足商务用户对位置相关和异地操作
13、的特殊要求。本课题组的目标便是开发出一个嵌入式移动实时环境下的数据库管理系统，能够高效的管理移动端数据库和效劳器端的数据库。1.2 嵌入式移动实时数据库概况嵌入式系统嵌入式系统是指以应用为中心，以计算机技术为根底，软硬件可裁剪，对功能、可靠性、本钱、体积、能耗等有严格要求的专用计算机系统，它一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统及用户应用软件等几个局部组成。随着集成电路技术、计算技术、软件工程技术等的日趋成熟和完善，嵌入式系统正深入社会生活各个领域。嵌入式硬件受本钱和体系功耗限制，微处理器一般只有存储器、I/O控制和少量逻辑电路，在嵌入式操作系统上运行的软件要充分考虑这些硬件的性能
14、问题，做相应的特殊优化和设计，以充分利用嵌入式系统资源，提高嵌入式设备的应用效率。移动计算环境计算环境先后经历了集中式计算、分布式计算、网络计算以及移动计算等多种模式，目前受到广泛关注的移动计算技术的迅猛开展，使得各类无线计算设备在没有固定物理连接的情况下也能准确及时地把数据传输到中央信息系统并与之交互，分担全系统的计算压力，使信息能够被位于任何地点的计算设备共享。由于移动计算环境的复杂性，其系统通常采用移动结点和固定结点混合分布的结构。移动设备经无线通道通过移动效劳基站和固定网络相连，可在基站覆盖的一定区域内自由正常使用，整个区域被划分成许多小的单元，各个单元由特定的移动效劳基站管理，基站作
15、为固定结点以高速有线网络互联。与传统分布式系统不同，移动计算环境作为一个动态的分布式系统具有如下新的特点：(1)移动性；(2)频繁断接性；(3)网络条件多样性；(4)网络通信非对称性；(5)移动设备电源支持时间有限；(6)移动网络可靠性低；(7)系统规模可伸缩。实时数据库实时数据库系统(Real-TimeDataBaseSystemzRTDBS)是事务可以具有定时特性或显式定时限制的数据库系统。系统的正确性不仅依赖于逻辑结果，而且依赖于该逻辑结果产生的时间。RTDB并非是数据库和实时系统两者的简单结合，它需要对一系列的概念、理论、技术、方法和机制进行研究开发，如数据模型极其语言，数据库的结构与
16、组织;事务的模型与特性，尤其是截止时间及其类型;事务的优先级分派、调度和并发控制协议与算法;数据和事务特性的语义及其与一致性、正确性的关系，查询/事务处理算法与优化；I/O调度、恢复、通信的协议，缓冲区调度算法等等，这些问题之间彼此高度相关且与应用的类型紧密相联。实时数据库的主要特性主要表现在数据特征和事务特征上。1 RTDB的数据特征在RTDB中，数据随外部环境状态的变化而快速变化，其值只在一定的时间内是“流行的，过时那么无效了，故系统除了维护数据库内部状态（数据值）的正确性、相容性外，还必须同时维护内部状态与外部环境实际状态的一致性，以及数据用来决策或推导新数据时在时间上的相互一致性。定义
17、1.1RTDB中的一个数据对象D可定义为一个三元组,它们分别为D的当前值、采样时间、外部有效期（外部现实对象状态变化的时间间隔），有效期即自DTP算起DV有效的时间长度。对于每一D有内部一致性、外部一致性和相互一致性特征。1）内部一致性dv满足预先定义的数据库内部状态的完整性和一致性限制。这就是传统意义下的数据正确性；2）外部一致性设TC为当前或检测时间，当且仅当（TC-DTP）=DEV”那么称D是外部一致的，即DV和对应的外部现实对象的状态是一致的；3）相互一致性用来决策或导出新数据的一组相关数据称为一个相互一致集，记为R,其中的数据必须尽可能地在一个允许的公共时间期内被采样（或导出），这个
18、公共时间期就称为R的相互有效期，记为RMVI,对于R中的任两个数据D和D,有IDTP-DTP=RMVI,那么说R中的数据是相互一致的。外部一致性和相互一致性都是关于时间的，故统称时间一致性。既是内部一致又是时间一致的数据才是正确的。2 RTDB的事务特征由于实时任务往往有内部结构和相互之间的联系，传统的“原子的、平坦的数据库操作序列的事务概念及模型对实时事务不适合。RTDB事务表现出了许多不同的特征，这里只给出其标识性特征。定时可以是绝对、相对或周期时间。RTDB的定时性一方面由数据的时间一致性引起，此时它往往取周期或定期性限制的形式，如“每5秒取样一次、7:OO启开工控设备等;定时性的另一根
19、源是对现实世界施加于系统的反响时间的要求，这时它典型地取施加于非周期事务的截止时间限制的形式，如“假设温度到达2000度，那么在3秒内加冷却剂到反响堆。实时事务的新特性主要表现为：正确性，事务执行不仅要求逻辑结果上的正确，还要求时间正确性，事务价值与是否在给定截止期内提交有关；可预测性，某些系统中实时事务错失截止期将导致灾难性后果，因此要求能够预测这些事务的执行时间，以确保事务能够满足截止期，从而保证系统的正常运行；优先性，不同事务的提交对系统带来不同的价值，依照任务的紧迫度和价值大小划分事务的优先级，先保证高优先级事务在截止期内完成提交。为满足上述数据一致性和实时特征，实时事务通常需要维护的
20、一些属性有：绝对截止期、到达时间、相对截止期、估计执行时间、剩余执行时间、松弛时间、价值函数等。依照实时事务的特征，按价值函数可分为以下几种类型：实时事务的价值与其是否在截止期内完成提交有很大关系，不同的系统中事务超截止期带来的影响不同，由此可以利用事务的价值函数建模。硬截止期实时事务，又称硬实时事务，超过截止期会给系统带来严重后果，价值函数为负值，对应于一些危急性紧迫任务。软截止期实时事务，又称软实时事务，超过截止期后仍存在一定价值，但会不断下降，直至到某一时刻（称为最终有效时间）降为零，之后保持为零而不会变负。固截止期实时事务，又称固实时事务，一旦到达截止期，其价值立刻降为零，此后保持不变
21、，不会为负，它是软实时事务的最终有效时间和截止期重合的特例。图Ll反映了这几种不同类实时事务的价值函数，其中两坐标轴V和t分别表示价值和时间，S是事务的启动时间，d是截止期，e那么表示最终有效时间，在t0)页，与分别调入m+1页相比大大节约了时间。当引用序列是顺序的时候，采用这种策略会减少整体的I/O代价。然而预取将来不使用的页，就会增加I/O负担，更糟糕的事情是预取进来的页把将来可能访问的页替换出缓冲区。这是因为物理上连续的页不一定在逻辑引用序列上连续。关于预取算法的研究请参考文献请求调页算法在出现缺页时，它只调入请求的页面。由于很难预测事务将来的引用行为，预取策略在实际应用中不是很多。请调
22、策略在实际的缓冲区管理中比较广泛。为了区别在DBMS的在虚拟地址空间的内存缺页与在缓冲区中的页，本文称后者为缓冲区缺页。一般缓冲区替换算法在给定缓冲区大小和分配策略前提下的目的都是最小化缓冲区缺页率。最理想的情况是最久的将来被再次引用到的页面被选为被替换的页面,这基于能获知事务的将来引用行为，最有名的是OPT算法【划【划，它是一个理想的状态是上界，最坏的情况是最近的将来被用到的页面被淘汰掉，设计一个合理的算法的下界以随机算法的缺页率为参照更合理，因为它不使用任何和未知引用信息。下面我们以此为参照讨论基于请调的页面级替换算法，基于页面的算法主要分为工作负荷己知的缓冲区管理和基于统计的缓冲区管理两
23、类。基于访问模式的页面级缓冲区管理数据库管理系统对缓冲区的管理与操作系统对缓冲区管理有一个显著不同就是对数据库管理系统而言，其数据访问序列附经过查询优化阶段后就已知，但是对于操作系统而言，诸如此类的信息却很难获得。下面是几个工作负荷己知情况下的缓冲区页面管理算法。1 .基于工作集的缓冲区管理算法文献15口6中通过理论分析以及模拟试验观察到如果分配给DBMS的缓冲区小于工作负荷的活动数据集的大小时，数据在缓冲区中缺失的情况就会频繁发生。鉴于此，提出了一个DBMS冲区管理的算法，该算法给每个事务分配一个大小等于它的活动数据集大小的缓冲链。当某个事务需要访问一个页面，首先在整个缓冲区空间里面查找该页
24、面是否已经被缓存在缓冲区中，如果没有找到，就置换出一个最近最少访问的页面或从公共空闲页面缓冲池获得一个空闲的页面来作为新的缓冲页面的缓存空间。取得了较好的效果，但是此算法的缺点是事务运行时就需要准确地计算工作集大小，且得不到工作集大小的缓冲页数目时就不能投入运行，而必须等待。2 .基于数据库表的缓冲区管理算法文献口刀广泛研究了一般的数据库操作和页面访问的模式。在此根底上，他们提出了一种被称为DBMIN的DBMS缓冲区管理算法，该算法基于数据表对数据库缓冲区进行管理。在他们的研究中，数据库的操作被分为如下几类：1)顺序访问在顺序访问模式中，所有页面被一个接一个顺序访问。在一个无序表上的选择操作中，该表的每个页面仅仅被访问一次，被称为StraightSeqUential(SS);归并连接操作屡次扫描一簇元组记录，这种访问模式被称为CIUSteredSeqUentiaI(CS);如果整个表被屡次访问，例如嵌套循环连接操作，称之为LOoPingSeqUential(LP)。2)随机访问
