一种嵌入式移动实时数据库管理系统缓冲区管理机制研究

华中科技大学硕士学位论文一种嵌入式移动实时数据库管理系统缓冲区管理机制研究姓名：祝晖申请学位级别：硕士专业：计算机软件与理论指导教师：徐丽萍20080528华中科技大学硕士学位论文I摘要随着移动通信技术的快速发展和移动计算机的大量普及，由移动计算、实时应用结合传统数据库技术而形成的嵌入式移动实时数据库系统已成为数据库领域的新兴热点课题。其缓冲区管理在数据库管理系统中有着特殊的基础性地位，它也要同事务调度，并发控制策略一样充分考虑资源、时效、应用环境的限制，才能设计有力支持事务的实时性和移动性的高效的缓冲区管理算法。传统的缓冲区管理算法主要借鉴操作系统的页面管理算法如LRU,FIFO,CLOCK等，实现虽然简单但是不适合移动实时环境；另外一个研究方向就是多缓冲池的配置，实现比较困难。同时对移动数据库的研究很多都是以内存数据库为前提，也很少考虑缓冲区管理，实际上嵌入式移动数据库不一定都是内存数据库.随着半导体技术的发展，很多嵌入式移动设备都配有一定容量的外存来满足数据持久化需求。所以研究新的EMRTDBMS缓冲区管理策略非常必要。结合嵌入式、移动、实时环境的特点，充分考虑广播策略，实时数据库系统事务的特征、数据特点，一套新的以提高缓冲页命中率和提高实时事务按时完成比率为目标的客户端和服务端缓冲区管理算法：识别事务截止期的混合优先级缓冲区管理算法和识别数据特征和事务截止期的综合优先级缓冲区管理算法充分考虑了以上新特点；通过在linux平台下利用多进程程序设计技术设计的客、服端缓冲区管理原型系统，从缓冲区缺页率、实时事务错失率等方面进行性能评测实验，实验结果显示它与其它几种算法相比具有相对较好的综合性能。关键词：缓冲区管理，替换策略，缓存，截止期华中科技大学硕士学位论文IIAbstractWiththefastdevelopmentofmobilecommunicationtechnologyandthelargenumberofpopularmobilecomputation,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-dlandComPrio-dc&dlarebetterthansomeotherstrategiesonbufferpagesmissingandtransactionmissingrate.Keywords:buffermanagement,replacementstrategy,cache,deadline独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在________年解密后适用本授权书。本论文属于不保密□。（请在以上方框内打“√”）学位论文作者签名：指导教师签名：日期：年月日日期：年月日华中科技大学硕士学位论文11绪论1.1课题背景数据库系统作为一种重要的计算机科学发展至今已有几十年历史，随着嵌入式系统的广泛应用及嵌入式实时操作系统的不断普及和移动通信技术的快速发展，嵌入式移动实时环境下的数据管理问题成为系统中的重要环节，由移动计算、实时应用以及嵌入式环境结合传统数据库技术而形成的嵌入式移动实时数据库，现已成为数据库系统领域的新兴热点课题。由于嵌入式移动实时环境的特性，与传统数据库管理系统相比，它可以支持更多新的应用：数字化信息服务，公共信息发布，用户通过无线便携设备了解新闻、股票、天气等资讯信息，并及时做出决策；军事作战，每个士兵或作战设备都作为独立的系统单元，实时处理战场信息并与服务器进行交互，服务器综合各单元的移动信息指挥整个战场行动；移动电子商务，随着用户所处地点的改变，数据库查询将总是显示最新有效的合适商务信息，满足商务用户对位置相关和异地操作的特殊要求。本课题组的目标便是开发出一个嵌入式移动实时环境下的数据库管理系统，能够高效的管理移动端数据库和服务器端的数据库。1.2嵌入式移动实时数据库概况1.2.1嵌入式系统嵌入式系统是指以应用为中心，以计算机技术为基础，软硬件可裁剪，对功能、可靠性、成本、体积、能耗等有严格要求的专用计算机系统，它一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统及用户应用软件等几个部分组成。随着集成电路技术、计算技术、软件工程技术等的日趋成熟和完善，嵌入式系统正深入社会生活各个领域。嵌入式硬件受成本和体系功耗限制，微处理器一般只有存储器、I/O控制和少量逻辑电路，在嵌入式操作系统上运行的软件要充分考虑这些硬件的性能问题，做相华中科技大学硕士学位论文2应的特殊优化和设计，以充分利用嵌入式系统资源，提高嵌入式设备的应用效率。1.2.2移动计算环境计算环境先后经历了集中式计算、分布式计算、网络计算以及移动计算等多种模式，目前受到广泛关注的移动计算技术的迅猛发展，使得各类无线计算设备在没有固定物理连接的情况下也能准确及时地把数据传输到中央信息系统并与之交互，分担全系统的计算压力，使信息能够被位于任何地点的计算设备共享。由于移动计算环境的复杂性，其系统通常采用移动结点和固定结点混合分布的结构。移动设备经无线通道通过移动服务基站和固定网络相连，可在基站覆盖的一定区域内自由正常使用，整个区域被划分成许多小的单元，各个单元由特定的移动服务基站管理，基站作为固定结点以高速有线网络互联。与传统分布式系统不同，移动计算环境作为一个动态的分布式系统具有如下新的特点：（1）移动性；（2）频繁断接性；（3）网络条件多样性；（4）网络通信非对称性；（5）移动设备电源支持时间有限；（6）移动网络可靠性低；（7）系统规模可伸缩。1.2.3实时数据库实时数据库系统（Real-TimeDataBaseSystem,RTDBS）是事务可以具有定时特性或显式定时限制的数据库系统。系统的正确性不仅依赖于逻辑结果，而且依赖于该逻辑结果产生的时间。RTDB并非是数据库和实时系统两者的简单结合，它需要对一系列的概念、理论、技术、方法和机制进行研究开发，如数据模型极其语言，数据库的结构与组织;事务的模型与特性，尤其是截止时间及其类型;事务的优先级分派、华中科技大学硕士学位论文3调度和并发控制协议与算法;数据和事务特性的语义及其与一致性、正确性的关系，查询/事务处理算法与优化；I/O调度、恢复、通信的协议，缓冲区调度算法等等，这些问题之间彼此高度相关且与应用的类型紧密相联。实时数据库的主要特性主要表现在数据特征和事务特征上。1RTDB的数据特征在RTDB中，数据随外部环境状态的变化而快速变化，其值只在一定的时间内是“流行”的，过时则无效了，故系统除了维护数据库内部状态(数据值)的正确性、相容性外，还必须同时维护内部状态与外部环境实际状态的一致性，以及数据用来决策或推导新数据时在时间上的相互一致性。定义1.1RTDB中的一个数据对象D可定义为一个三元组[1]DV,DTP,DEVI，它们分别为D的当前值、采样时间、外部有效期(外部现实对象状态变化的时间间隔)，有效期即自DTP算起DV有效的时间长度。对于每一D有内部一致性、外部一致性和相互一致性特征。1)内部一致性dv满足预先定义的数据库内部状态的完整性和一致性限制。这就是传统意义下的数据正确性；2)外部一致性设TC为当前或检测时间，当且仅当(TC-DTP)