（计算机应用技术专业论文）嵌入式实时数据库中关键技术的研究与实现.pdf

东北大学硕士学位论文摘要 嵌入式实时数据库中关键技术的研究与实现 摘要 随着讨算机技术的发展，嵌入式系统在生产和生活中扮演着越来越重要的角 色，我们在家用电器、医疗卫生、生产生活等各个方面都能看到嵌入式系统的影子， 它们正推动着社会的进步。作为嵌入式系统的核心部分之一，嵌入式实时数据库目 前成为越来越热门的研究对象，国内外很多的研究人员都致力于这一技术的研究， 商业企业也不失时机地相继推出其具有定嵌入式实吲性能的数据库产品。 在这样的背景之f ，我们结合生产部门的需求和国家8 6 3 计划资助项目、省自 然科学基金资助项目的任务目标，开发和研制了应用于机械智能设备的嵌入式实时 数据库i e e b a s e 系统。 本文首先介绍了嵌入式实时数据库的相关概念及任务要求；然后讲述了几个f 在丌发的知名原型系统采用的关键技术；接着介绍了l e e b a s e 系统的结构及各部分 功能；之后着重讲述了系统的没计与实现，主要包括：数据库基本功能，数据库的 主动性，实时事务调度三方面内容，根据应用的需求，提出并采用了适合本系统应 用的改进的策略，并且在l i n u x 操作系统之上实现了整个系统的功能。 【关键字】：嵌入式系统，实时数据库，主动数据库，事务预分析，基于最? - n 先的可抢占优先级策略，实时事务凋度。 i i 东北大学硕士学位论文 a b s t r a c t r e s e a r c ha n d i m p l e m e n t a t i o n o nt h e k e yt e c h n i q u e s o f e m b e d d e dr e a l 。t i m ed a t a b a s e s a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , t h ee m b e d d e ds y s t e m sa r ep l a y i n g m o r ea n dm o r ei m p o r t a n tr o l e si nm o d e m l i f e ，s u c ha sf a m i l ye l e c t r i cp r o d u c t s ，m e d i c a l t r e a t m e n t ，m a n u f a c t u r e ，l i v e sa n ds oo n w ec a nm e e tt h e me v e r y w h e r ea n dt h e ya r e p r o m o t i n gt h es o c i e t yt ob eb e t t e r a so n eo ft h ek e r n e l si nt h ee m b e d d e ds y s t e m st h e e m b e d d e dr e a l - t i m ed a t a b a s ea l s ob e c o m e sam u c hh o t t e rs u b j e c tf o rr e s e a r c hm o r ea n d m o r e p e o p l e d e v o t et h e m s e l v e si n t o r e s e a r c h i n g o nt h e t e c h n o l o g y o fe m b e d d e d r e a l - t i m ed a t a b a s ei nh o m ea n da b r o a d c o m m e r c ea n d e n t e r p r i s e sa l s od e v e l o pa n dv e n d t h e i re m b e d d e dd a t a b a s e sw i t hs o m er e a l - t i m ec h a r a c t e r s u n d e rt h i sb a c k g r o u n d ，w ec o m b i n et h er e q u i r e m e n to f t h e p r o d u c t i o nd e p a r t m e n t m a dt h et a s kt a r g e to f t h ep r o j e c ts u p p o r t e db yt h en a t i o n a l8 6 3p r o g r a ma n dt h e l i a o n i n g p r o v i n c en a t u r es c i e n c ef o u n d a t i o nt or e s e a r c ha n d d e v e l o p a ne m b e d d e dr e a l - t i m e d a t a b a s en a m e dl e e b a s ef o r i n t e l l i g e n tm e c h a n i c a le q u i p m e n t t h i st h e s i sb e g i n sw i t ht h eb r i e f i n t r o d u c t i o no f t h ed e f i n i t i o n sr e l a t i n gt oe m b e d d e d r e a l - t i m ed a t a b a s ea n dt h ea i mo ft h ep r o j e c t t h e ni td e s c r i b e st h ek e yt e c h n i q u e s ， s e v e r a lw e l lk n o wp r o t ot y p ee m b e d d e dr e a l - t i m ed a t a b a s es y s t e m s ，w h i c ha r eu n d e r d e v e l o p m e n t a n df o l l o w i n gt h a tt h et h e s i si l l u s t r a t e st h es t r u c t u r eo f t h ew h o l ep 喇e c t a n dt h ef u n c t i o no fe a c hp a r ti nt h ee m b e d d e dr e a l t i m ed a t a b a s e a f t e rt h a t a st h em o s t i m p o r t a n tp a r t ，t h et h e s i sf o c u s o i lt h ed e s i g na n d i m p l e m e n t a t i o n o ft h ed a t a b a s es y s t e m ， w h i c hi n c l u d e st h eb a s i cf u n c t i o n so ft h ed a t a b a s e ，t h ea c t i v et r a n s a c t i o no ft h ed a t a b a s e a n dt h er e a l t i m et r a n s a c t i o n ss c h e d u l i n g a c c o r d i n gt ot h er e q u i r e m e n to f a p p l i c a t i o n s ，i t p u t sf o r w a r ds o m ei m p r o v e dp o l i c i e s a n di m p l e m e n t st h e mo nt h el i n u xo p e r a t i n g s y s t e m k e yw o r d s ： e m b e d d e d s y s t e m ，r e a l t i m ed a t a b a s e ，a c t i v ed a t a b a s e ，t r a n s a c t i o n p r e - a n a l y s i s ，p r i o r i t yw i t hp r e e m p t i o nt h r e s h o l db a s e do ne d ( e a r l i e s t d e a d l i n e ) ，r e a l t i m et r a n s a c t i o ns c h e d u l i n g i i i 声明 本文声明：所提交的学位论文是在导师的指导下完成的。论文中取 得的研究成果，除已经注明的引用的内容和致谢的地方外，本论文不包 含其他个人或集体己经发表或撰写过的作品成果。对本文的研究做出重 要贡献的个人和集体，均在沦文中作了明确的说明并表匀；谢意。 本人签名： 日期： 毒蔫芎 - 训弘p 东北大学硕士学位论文第一章嵌八式实时数据库概述 1 1 引言 第一章嵌入式实时数据库概述 1 1 1 嵌入式系统简介 随着后p ch , j 4 弋的到来，我们的生活当中正越来越多的遍布着嵌入式系统的产 品，例如制造及过程控制：人机操作面板、控制机床、电机驱动、测试设备、环 境监测、输配电设备、炼油厂设各、远程无人采集监控站；医疗卫生设备：x 光机、 c t 、医护管理系统、病房监测系统；楼宇自控及商业零售嘲点、商业p o s 、保安 监控设备；办公设备及信息家电、手机嵌入系统、程控电话等等，而且它还会进一 步地影响我们的生活。现代社会中嵌入式系统及产品最终会无所不在。 嵌入式系统是指用于执行独立功能的专用计算机系统。它由微电子芯片( 包括 微处理器、定时器、序列发生器、控制器、存储器、传感器等一一系列微电子芯片与 器件) 和嵌入在r o m 、r a m 和f l a s h 存储器中的微型操作系统、控制与应用软 件开发来实现各种自动化处理任务的电子设备或装置，即以应用为中心，软硬件可 裁减的适应应用系统，对功能、可靠性、成本、体积、功耗等综合性严格要求的专 用计算机系统。嵌入式系统主要由嵌入式处理器、相关支撑硬件、嵌入式操作系统 及应用软件系统等组成，它是集软硬件于一体的可独立工作的“器件”。 1 1 2 数据库发展简介 数据库是计算机领域发展最快的学科之一，因为它既是一门非常实用的技术， 也是一门涉及面广，研究范围宽的学科。因此，它吸引了理论研究、系统研制和应 用开发等不同方面众多学者、专家和技术人才致力于其研究与实践。数据库系统所 管理、存储的数据是各个部门宝贵的信息资源。在信息化来临，全球互联网 ( i n t e r n e t ) 高速发展的今天，信息资源的经济价值和社会价值越来越明显。建设 以数据库为中心的信息系统和应用系统，对于提高企业的效益、改进部门的管理、 改善人们的生活均具有实实在在的意义。 数据库系统已经从第一代网状、层次数据库系统发展到第二代关系数据库系统 和第一代以面向对象为主要特征的数据库系统。数据库技术与网络通信技术、面向 对象技术、并行计算技术、多媒体技术、人工智能技术等互相渗透，互相结合，成 为当前数据库技术发展的主要特征。它使数据库领域中新的技术内容层出不穷，新 的学科分支0 i 断涌现，形成了新一代数据库系统的大家族。与传统的数据库相比， 东北大学硕士学位论文第一章嵌入式实时数据库概述 当今数据库的整体概念、技术内容、应用领域，甚至某些原理都有了重大的发展和 变化。同时也更沣重数据库的实用性和精确性，于是出现了满足嵌入式产品需要的 嵌入式实时数据库。 1 2 嵌入式数据库 1 2 1 嵌入式数据库应用需求 嵌入式数据库的应用币在以高速牢增加。尤其是互联网应用，汽车引擎控制系 统，智能卡，移动p c ，处理控制等系统的应用和更新更使得嵌入式系统如鱼得水， 大行其道。数据是一个系统中的最重要的元素和处理对象，在其他独立的嵌入式应 用当中，由外设采集的数据和系统内部产生的数据，必须经过处理，整理，存储， 4 能形成有价值的信息。鉴于互联网的数据结构，我们通常就要在应用中使用特殊 的技术来存储和操作数据对象。对系统进行设计上的优化是很有价值的工作，也就 是既要开发和完善嵌入式数据库功能来提供支持数据的存储和操作，于是与之相适 应的数据库系统应运而生。 数据库理论的发展使得嵌入式数据库的研究= = _ i i 断深入，并且使其产品化以及不 断的改进和智能化成为可能。比如我们生活当中经常使用的洗衣机等家电产品，当 我们在控制面板上选择水量，力度，时间等选项后，只需等待它工作，对数掘进行 处理由嵌入式数据库管理系统来完成，冰箱，微波炉等电器也如此。包括移动通信 的实现也需要嵌入式移动数据库管理系统；医用c t 的数据库管理系统还需要包含 对数据进行分析的功能。 正如前面提到的，对于嵌入式系统已经有很多研究人员在丌发和使用，嵌入式 产品正存扮演着重要的角色。作为嵌入式系统的必要的一部分，嵌入式数据库就会 成为这种牛活中的必需。实际上，尽管嵌入式数据库发展很快，但是这个领域也仅 足近年来才得到广泛的关注，从数据库技术到嵌入式系统的整合尚未实现从手工到 _ j ：业化的转变，仍需要进行大量的工作。 1 2 2 嵌入式数据库特性 嵌入式数据库系统和传统的数据库在一些方面存在差异，原因在于他们的设计 目标和标准不同。 传统数据库系统的主要目标是数据的吞吐量，灵活性，可扩展性，功能性等， 然而尺寸，资源的使用和处理器的使用并不是考虑的重点，因为硬件相列从前已经 变得相对便。南：得多了。在嵌入式系统中这些原本显得不熏要的闯题变得重要起束， 东北大学硕士学位论文第一章嵌八式实时数据库概述 对于嵌入式数据库系统的主要问题可以归为以下几点： 存储器的最小化：对于嵌入式系统来讲，存储器的要求主要是从经济角度和应 用角度来考虑的，尽可能保持最小。典型的嵌入式数据库的存储器的大小在1 k 到2 m 。 资源分配的减少：在嵌入式系统中，数据库管理系统和应用通常是运行在同一 处理器上，将对数据库处理的大部分请求分配存最小的c p u 带宽上，尽可能的给 应用留有余地。 支持多操作系统：在企业的数据库系统中，d b m s 典型的是使用常规的操作系统， 运行在专门的服务器上。客户端( 可以是台式机) ，其他服务器，甚至是嵌入 式系统，通过网络互连和服务器相连接。因为数据库大多运行：在同样的硬件单 元上，如同嵌入式系统中的应用一样，嵌入式系统通常使用特别的操作系统， 数据库系统必须支持这些操作系统。 高效可用性：与传统的数据库系统相反，大多数嵌入式数据库系统在运行期问 不具有系统管理员。因此，嵌入式数据库必须能够自主运行。 1 3 实时数据库 绝大部分嵌入式数据库系统都要求是实时数据库系统，这是因为嵌入式系统的 主要作用是实时控制、监视、管理移动计算机、数据处理等，或者辅助其它设备运 转，完成各种自动化处理的任务。 1 3 1 实时数据库需求 当前，数据库的应用正在从传统领域向新的领域扩展，如c a d c a m 、c i m s ；数 据通信、电话交换、电力调度等网络管理；电子银行事务、电子数据交换与电子商 务、证券与股票交易；交通控制、雷达跟踪、空中交通管制；武器制导、实时仿真、 作战指挥自动化和c 3 i 系统，等等。这些应用有着与传统应用不同的特征，一方面， 需要维护大量共享数据和控制数据；另一方面，其应用活动( 任务或事务) 具有很 强的时m 胜限制，要求在规定的时刻和( 或) 定的时间段内完成其处理；同时， 所处理的数据也往往是“短暂”( t e m p o r a l ) 的，即具有一定的有效时问，过时之后 就会有新的数据产生，而当前的决策或推导则变得无效。所以，这种应用对数据库 和实时处理两者的功能及特性均有需求，既需要数据库来支持大量数据的共享，维 护其数据的一致性，又需要实时处理来支持其任务( 事务) 与数掘的定时性限制。 但是，传统的数据库系统旨在处理永久、稳定的数据，强调维护数据的完整性、 致性，其性能月标是高的系统吞吐量和低的代价，而根本：不考虑有关数据及其处 东北大学硕士学位论文第一章嵌八式实时数据库概迷 理的定州性限制，所以，传统的数据库管理系统( d b m s ) 不能满足这种实时应用的 需要。而传统的实时系统( r 1 、s ) 虽然支持任务的定叫限制，但它针对的是结构与 关系很简单、稳定不变和可预报的数据，不涉及维护大量共享数据及它们的完整性 和一致性，尤其是时间一致性。因此，只有将两者的概念、技术、方法与机制“无 缝集成”( s e a m l e s si n t e g r a t i o n ) 的实时数据库( r t d b ) 才能同时支持定时性和一致 性。 近年来，实刚数掘库已发展成为现代数据库研究的主要方向之一，受到了数据 库界和实时系统界的极大关注。数据库研究工作者的动机在于利用数据库技术的特 点和优点来解决实时系统中的数据管理问题：实时系统研究工作者则为给实时数据 库系统提供时间驱动调度和资源分配算法所吸引。然而，实时数据库系统并非是数 据库系统和实时系统两者的简单结合，而是需要对一系列的概念、理论、技术、方 法和机制进行研究丌发，如数据模型及其语言，数据库的结构与组织；事务的模型 与特性，尤其是截止时间及其软硬性；事务的优先级分派、凋度和并发控制协议与 算法；数据和事务特性的语义及其与一致性、正确性的关系，查询事务处理算法 与优化；i 0 调度、恢复、通信的协议与算法等等。这些问题之间彼此高度相关且 与应用的性质紧密联系。 1 3 2 实时数据库概念 所谓实时数据库系统( r t d b s ，r e a l t i m ed a t a b a s es y s t e m ) 就是其数据和事 务都具有定时特性或显式定时限制( e x p li c i t l yt i m i n gc o n s t r a i n t s ) 的数据库 系统。系统的正确性不仅依赖于事务的逻辑结果，而且依赖于该逻辑结果所产生的 时间。 1 3 3 实时数据库特性【3 l 从数据库的角度看，一个r t s 媳型的有三个紧密结合的子系统组成：被控系统、 执行控制系统、数据系统。被控系统就是所考虑的应用过程，称为外部环境或物理 世界；执行控制系统监视被控系统的状态，协调和控制它的活动，称为逻辑世界： 数据系统有效地存储、操纵与管理实时( 准确和及时) 信息，称为内部世界。执行 控制系统和数据系统通称控制系统。内部世界的状态是物理世界状态在控制系统中 的映像，执行控制系统通过内部世界状态而感知物理世界状态，并且基丁：此而与被 控系统交h 作用，所有这些都与时间紧密相联。因而实时数据库系统的特征_ j = 要表 现在数据和事务的时间相关上。 东北大学硕士学位论文第一章嵌入式实时数据库概述 1 、r t d b 的数据特征： 在r t d b 系统中，数据只在一定时间内是有意义的，其值随着外部环境状态不 i j 而频繁的改变，所以人们不能只考虑数据库内部状态的致性，还必须考虑外部 状态与内部状态之间的一致性；也不能认为使用数据时，简单的提供其最新值就是 最合适的，还必须考虑它与其他被使用数据之间的“时问一致性”。 实时数据库内部一致性就是传统意义下的数据库内部的一致性，也就是指数据 的当前状态( 或当前值) 满足所有对其预先定义的数据库内部的完整性限制和一致 性要求。由于数据库状态的变更都是以事务的形式进行的，因而事务操作的完整性 检验和可串行化能提供内部一致性保证。 在r t d b 系统中，数据库依靠逻辑世界与物理世界的频繁交互作用来获取准确、 及时的数据，所以一个正确的数据库状态必须与物理世界当时的状态一致。即事务 所使用的数据库中的当前值在其有效时间范围内。这就是实时数据库外部一致性的 含义。 现有的传统可串行化并发控制协议都是基于封锁或回滚鼋启动( r o l l b a c k r e s t a r t ) 的。封锁会导致优先级颠倒而导致优先级低的事务阻塞高优先级事务， 而回滚重启动除了浪费大量系统资源从而引起事务超时外，实时系统中有的事务 根本不可能回滚重启动，如记录飞行目标位置和速度等状态的事务、执行火箭“点 火”操作的事务等。对于这种反映物理世界不可逆事件的事务，不可能采用封锁或 者回滚技术，必要时只有先牺牲内部一致性来确保外部一致性，然后再恢复内部一 致性。 2 、r t d b 的事务特征： 定时性是r t d b 事务的根本特点。定时可以按绝对时间、相对时间或周期时间。 它一方面是由数据的时问一致性所引起的，这种定时性往往采取定期或周期性限制 的形式，如“每五秒取样一次”、“每天七点启动机器人”等。引起事务定日寸性的另 一根源是物理世界施加于控制系统的反应时削要求，它典型地采取施加于非定期事 务的截七时间限制形式，如“若温度达到1 0 0 0 摄氏度，则在五秒内加冷却剂到反 应堆”。 定时性包括了两方面的含义： a 定时限制 事务的执行具有显式的时间限制，如期限、截止时间( d e a d l i n e ) 等。这是 由于控制系统要随时紧密地跟踪被控系统而引起的。它要求r t d b 系统必须要有时 东北大学硕士学位论文 第一章嵌八式实时数据库概述 l 刚处理机构。 根据错过截止时间而引起的后果，实时事务还有软实时和硬实时之分： 硬实时事务是指如果事务的完成时间超过截止时间，则会导致恶果，它对 应于安仝危害性活动，比如航空控制。 软实u , i 事务是指如果事务的完成时问超过截l 旧j 问，事务仍然具有一定的 价值，但其价值量不断降低，直到下降为零，此后一直保持为零。 b 定时萨确性 事务能按合适的时间要求正确执行。这是由于要求数据对于控制系统的各种决 策活动随时有效而引起的。它要求权衡定时限制与数据一致性等多方面因素，提供 合适的调度算法。完全实现事务的定时性和一致性是一个复杂而困难的任务，它还 依赖于事务的模型与处理。 1 4 嵌入式实时数据库 1 4 1 嵌入式数据库和实时数据库的兼容 嵌入式数据库中大部分是实时数据库，但是并非所有的实时数据库都一日以不加 改造的应用到一个嵌入式系统当中，实际上应由两者的特点结合而产生的数据库系 统才是满足要求的嵌入式实时数据库系统。 比如大多数的嵌入式系统要运行在无人工出现的环境中，同时资源的装载又迫 使嵌入式系统不得不仔细平衡，尤其是存储器。这样通常就意昧着存储器的能力必 须确保尽u j 能的低，也就是说，在这样系统中的数据库必须用小的存储器，并定时 向主数据库上传输数据。大部分实时数据库在设计时既考虑到即时数据的处理，也 考虑到海量数据的存储及查询，往往使用较大磁盘空间。 嵌入式系统能够被实施在不同的硬件环境下来支持不同的操作系统平台，这就 要求嵌入式数据库适应不同的操作系统。另一方面，实时数据库系统却要在数据库 系统卜设置卅i 同要求的平台。在实时数据库中使用的数据必须是逻辑致的，也是 时间一致的。为了维护由实时系统控制的环境状态和由数据库内部数据反映的状态 致性，数掘的时削一致是必须的。 由此，嵌入式实时数据库并非嵌入式数据库和实时数据库的简单叠加，而要有 其自身的特征。 东北大学硕士学位论文第一章嵌八式实时数据库概述 1 4 2 嵌入式实时数据库的特性 随着且联网、高速无线互连、廉价内存及高速处埋器的出现，胀入式系统现在 也需要管理更多、更复杂的数据。换句话说，数据库系统不能由于所管理数据量的 激增而牺牲性能。更加复杂的数据需要数据库管理系统必须能够管理复杂的体系结 构和数据间的相互关系。 目前，对于隈入式实时数据库系统主要有以下几点特征1 4 j ： 1 人量更短、更快的处理过程 那些挑战数据管理性能的嵌入式实时系统应该具备非常高的数据处理速率，而 单一处理过程的持续时间应该十分短暂( 单一处理过程指的是对数据进行的一次基 本操作，包括只读、写入或读写) 。例如，机项盒以1 0 m b s 的速率从卫星上接收电 子信息；i p 路由器每秒可进行l o 万次路由处理；在传感器网络的帮助下，工业控 制系统每秒可进行数万次信号传输。 此外，由于嵌入式实时系统的彳i 同任务有着不同的优先权，而且它们可以动态 改变。因此嵌入式数据库可以根据操作环境的变化，对数据管理过程的优先权进行 排列。例如，为了适应输入速率的提高，数据输入系统必须对它的数据处理进程进 行调节，以便释放输入缓存，避免数据丢失。在理想情况下，应用软件可以提高与 写入数据相关处理过程的优先权，从而迅速清空输入缓存，但同时要牺牲其它处理 过程的优先权，例如数据查询、数据读取等。当高峰过后，所有的优先权排列情况 便又恢复到正常的状态。 2 可分享数据和事件处理 嵌入式实时运算是一种典型的由事件推动的操作过程，它会对外界资源的中断 做出相应的反应。新数据或发生变化的数据都会引发系统对它进行处理，例如。一 个i p 路由器向其它路出器发送一个路径选择表或工业控制器导致屏幕上出现一个 警示信号等。为了避免在定期对数据库数据查询过程中出现不必要的处理过程，嵌 入式系统数据库管理系统必须通过将事件传播到其它关联软件模块的方法共享事 件处理。例如，一个由传感器产生的中断会导致数据库中的某个数值发生变化。这 一变化最终将导致一个数据库事件，而这。一事件将通知其它的相关软件模块所发生 的变化。 3 对复杂数据的管理及设计灵活性 嵌入式实时系统经常需要对高度复杂的数据进行管理。一个理想的嵌入式应用 软件应能够在一特殊的结构中对数据库中的数据进行读写。对于c 语言程序员来 说，这意味着嵌入式结构、嵌套结构、原子类型中固定或不固定长度的各类阵列、 东北大学硕士学位论文第一章嵌八式实时数据库概述 隐式数据，以及可选择数据单元。数据库的真正价值在于可以根据不同的标准进行 检索。嵌入式系统数据库则需要支持单一或复合索引。理想情况下，数据库呵以提 供可由程序激活或关| = d j 的索引。 4 数据定义与源代码分离 嵌入式数据库管理还应具备将数据定义从应用软件源代码中分离出米的能力， 从而可以使用户更灵活、更简单地对数据结构进行修改。这。点需要通过数据库管 理系统的数据库主义浯- 言( d d l ) 来实现。d d l 丰要用来表达数据组、数据属性( 火 小和类型) 、获耿方法及数据的其它特征。编译程序可以对d d l 进行编泽，验证其 正确性，以供数据库管理系统软件使用。 5 高有效性 诸如通信和网络基础架构之类的嵌入式实时系统必须十分健壮，即使在硬件或 软件发生故障时也必须能正常工作。对于嵌入式实时数据库来说，这就意味着即使 在所依附的硬件发生故障的条件f ，仍然确保数据安全。当然，数据库必须备份到 其它的硬盘上，简单地映射或复制是不够的。嵌入式实时数据库必须保证主数据库 的所有备份数据库无论何时都是同步的。 6 与其它系统共享数据 判断一个企业运营隋况，往往要对企业的数据进行收集、整理和分析。事实上， 企业或组织的所有嵌入式实时数据系统和设备都要随着用户数据收集能力、传输和 获取需求的增加而不断升级。因此，嵌入式实时数据管理系统必须要能与企业中的 其它系统进行数据共享。 1 5 实现的任务及文章的组织 1 5 1 任务描述 我们所开发的项目是要应用于企业生产中的，为电机开发一个嵌入式的智能前 端设备如图11 ，通过传感器实时地采集电机运行时产生的数据，并且通过嵌入式 实刚数据库系统的处理，例如存储、监测数据值等，如果某些指标超过或者低于规 定的范围，就会通过应用程序来产生报警，通知传感器，进而控制电机。另外，嵌 入式数据库还要定期的将数据导入到主数据库中，以便于在必要时进行综合分析等 i 一作，这个主数据库可以采用s q l s e v e r ，s y b a s e 等大型的数据库。 这个项同是东北大学信息学院软件实验室和浙江大学信息学院、机械学院共同 申请的8 6 3 项目，我们主要负责软件部分嵌入式实时数据库系统称之为l e e b a s e ， 操作系统和硬件部分由浙江大学负责。截至本文完成，该项目正在进行系统集成和 东北大学硕士学位论文第一章嵌入式实时数据库概述 联调，其中还会遇到一定的问题，我们正在逐步解决，并争取通过多种测试手段对 系统进行全面的检验，以期使系统更加强壮和完善，通过鉴定并能很好的在实际生 广中运行。 怙 羚l 嵌入巡k 小 感 器 ，斗卜数喜氍甚翻螽li 主数据库 i i e e b a s e 8 一 ， 图1 1嵌入式实时数据库i e e b a s e 和嵌入式系统的关系 f ig1 it h er e l a t i o no ft h ee m b e d d e dr t d bi e e b a s ea n dt h ee m b e d d e d s y s t e m 1 , 5 2 文章的组织结构 本文主要论述了我们所完成的得到匡i 家8 6 3 资助和辽宁省自然科学基金资助的 课题嵌入式实时系统中一个重要部分：嵌入式实时数据库的设计与实现。 本文的组织结构如下：首先对嵌入式实时数据库中的一些相关概念作了简要概 述；第二章主要简述了目前在嵌入式实时数据库的商用和研究情况，并且讨论了几 个著名的f 在开发中的系统原型所采用的技术及算法；第三章介绍了我们这个数据 库的体系结构，嵌入式实时数据库在整个系统中的位置以及各部分功能；第四章主 要讲述了在嵌入式实时数据库的基本功能的设计与实现，主要包括数据管理的查 询、存储、更新、索引，事务管理的并发控制、恢复等。第五章主要讲述了数据库 的主动性的设计与实现，研究了传统策略并提出了适应于i e e b a s e 数据库的改进策 略。第六章讨论了实时事务调度策略，在传统实时事务调度的基础之上加入了满足 i e e b a s e 系统要求的改进算法。最后总结全文，提出该系统值得完善的部分。力争 在本文中能够将该嵌入式实时数据库中所涉及到的部分问题阐述清楚。 东北大学硕士学位论文第二章嵌入式实时数据库技术基础 第二章嵌入式实时数据库技术基础 嵌入式实时数据库技术的发展使各大公司相继开发出相应的产品，各火高校也 存进行进一步的研究和完善，这使得嵌入式实时数据库的产品竟相出炉。目前主要 有以卜- 产品分别在商业上和研究领域占有一席之地，它们在各个属性上具有不同的 特点 】。我们就通过刑这些产品进行比较分析来掌握有关嵌入式实时数据库的一些 技术攀础。 2 1嵌入式实时数据库商业产品 尽管目前没有真正的嵌入式实时数据库应用于商业市场，但是开发商还是绞尽 脑汁拿出部分满足嵌入式实时数据库特性的产品来，原因在于既能满足一部分市场 需求又能占有市场份额回笼资金，以便于进步开发。 2 1 1 产品简介 p e r v a s i v e s q l ：p e r v a s i v e s q l 是由p e r v a s i v e 软件公司开发的1 6 】。这个数据库 有三种不同的嵌入式数据库版本，分别用于智能卡( s m a r t - c a r d ) 、移动系统、陂入 式系统。这三种版本相互结合，同时也与该公司的其他非嵌入式数据库相结合。该 公司的系统较为接近嵌入式数据库的要求，很小的存储器要求是其重要标志。 p o i y h e d r a ：p o l y h e d r a 公司生产的数据库具有以下三点特征：第，满足部分 实时性的数据库系统；第二，主存数据库；第三，支持主动行为。 v e l o c i s ：v e l o c i s 是由m b r a n e 有限公司开发的。这个系统主要目的是用于网络商 业和w e b 应用，同时也有一部分支持嵌入式操作系统。 r d m ：r d m 同样由m b r a n e 有限公司开发，r d m 也号称为实时数据库，然而 它的实现的基本原理与p o l y h e d r a 不同，比如作为个嵌入式库并没有采用 c l i e n t s e r v e r 模式。 b e r k e l e yd b ：b e r k e l e yd b 是由s l e e p y c a t 软件公司开发的。 e t h a nl i b r a r y 模式 实现的，最重要的特点是分布式的，并且原码开放。 t i m e s t e n ：t i m e s t e n 是由t i m e s t e n 软件公司开发的。它是一个关系数据库， 和p o l y h e d r a 系统一样，它也是主存实时数据库。 东北犬学硕士学位论丈第二章嵌入式实时数据库技术基础 2 1 2 典型产品比较 数据库管理系统模式 从数据库管理系统模式来讲( 数据库管理系统模式是指数据库系统的结构) ， 以上产品中r d m 和b e r k e l e yd b 产品是l i b r a r y 模式的，其它的均为c l i e n t s e r v e r 模式的。c l i e n t s e r v e r 模式是指数据库服务器是一个和实时应用相分离而运行的应 用，即便是它们运行在同一个处理器上也是如此。这种d b m s 被称为使用请求向 应模式，服务器或者是通过进程之间的通信或者是通过网络被访问。l i b r a r y 模式将 d b m s 和系统应用结合在一起成为一个可执行系统，当一个任务想要访问数据库它 只要执行功能调用请求。事务的执行是代表任务的线程，即d b m s 内部的线程可 能被使用。 表2 1 嵌入式嵌入式数据库系统支持的数据库管理模式 t a b l e1 2d b m sm o d e l s s u p p o r t e db yd i f f e r e n te m b e d d e d d a t a b a s e s y s t e m s d b m ss y s t e mc i i e n t ，s e n r e r l i b r a r y p e r v a s i v e s q l x p o l y h e d m x v e l o e i s ， x r d mx b e r k e l e yd bx t i m e s t e nx 数据模型 从数据模型角度来看( 数据模型描述数据库中的数据的组织形式) ，除了 b e r k e l e yd b 使用了其他形式的数据模型以及p o l y h e d r a 同时使用了关系和对象关系 数据模型之外，其它的数据库均使用了关系数据模型。关系模型的好处就是一个表 的列可以和其它表有关系，以便于创建较为复杂的逻辑关系。而它的缺点就是关系 模型增加数据查找的负载。这是因为数据元素使用带有指针的索引来组织，而执行 索引的查找要花费一定的时间，尤其是当数据是存储在硬盘上的时候。面向对象的 数据库( o d m b s ) 使用的是不同的数掘模型，它是面向对象模型和程序高度结合 的产物，o d m b s 是对面向对象语意的扩展。一个面向对象数据库存储的对象可以 被不同的应用共享。第三种数据模型由关系模型和面向对象模型发展而来，称之为 对象关系模型。p o l y h e d r a 虽号称使用了对象荚系模型，实际上，并非真正的则象 关系模型，因为对象本身不能被存储在数据库中。实际上嵌入式数据库都要找到访 东北大学硕士学位论文第二章嵌入式实时数据库技术基础 问数据的捷径，绕过常规的索引查询。 表2 2 嵌入式数据库系统数据支持的数据模硝 t a b l e 。2 2d a t am o d e l ss u p p o r t e db yd i f f e r e n te m b e d d e dd a t a b a s e s y s t e m s d b m sr e l a t i o n a l o b i e c t o r i e n t e d o b i e c t - r e l a t i o n a l o t h e r p e r v a s i v e s q l x p o l y h e d r a x ( x ) v e l o c i sx i r d mx tb e r k e l e yd bx t i m e s q e nx 索引结构 为了有效的查询数据，数据库必须具有有效的索引机制。p e r v a s i v es q l 和r d m 使用了b 1 - t r e e ，p o l y h e a d r a 使用了h a s h i n g ，b e r k e l e yd b 使用了多种索引方法， 包括b + - t r e e ，h a s h i n g 以及队列方法，t i m e s t e n 也使用了多种索引方法，包括b + 一t r e e ，h a s h i n g ，t - t r e e ，v e l o c i s 使用了多种索引结构类型。 表2 3 嵌入式数据库系统支持的索引结构 t a b l e2 3d a t a i n d e x i n gs t r a t e g i e su s e db y d i f f e r e n te m b e d d e dd a t a b a s es y s t e m s d b m s s y s t e m b + t r e et t t e e h a s h i n g c t h e r p e r v a s i v es q lx p o l y h e d r a x v e l o c i sn an an an a r d m x b w e k e l e yd b xxx t i m e s t e n xxx b r t r e e 索引的主要目的是使硬盘的访问最小化，而在主存数据库中使用t - t r e e 也是目前值得关注的索引方法，它是比b + - t r e e 更深的树结构，因为它是平衡- 叉 ；l | ，每个节点都有两个孩子( 最值) 。对于本地数据，它与b + t r e e 相比，在找到 正确的数据之前就会访问更多的节点。而对于主存数据库这并不足什么问题，因为 主存内查找数据比之在磁盘上查找快得多。t - t r e e 索引的丰要热点就是比相应的b 。t r e e 算法更低的复杂度和更快的执行时间。但是t - t r e e 在遍历利并发控制相结合 时可能会出现问题，原因在于它要确保遍历期间树的完整性。另外提出一种称为 7 l - t a i l 的改进的索引策略，它减少了重新平衡所需的代价。另外，有两种针对t - t a i l 和t - t r e e 结构的算法，一种为积极的，另一种为消极的。h a s h i n g 使用了h a s h 列表， 东北大学硕士学位论文第二章嵌八式实时数据库技术基础 该列表包含的关键字是根据来自关键字本身的值，不同的关键字可以被赋予为同样 的值。使用h a s h i n g 的好处就是在数据库中查找确定值的时间相对于数据总数是独 立的。然而h a s h i n g 会比b t r e e 引起更多的磁盘i o ，这是因为数据会更多的要参 照定位，比如数据元素d l 被使用，那么d 2 就可能很快被用到，在使用b t r e e 索引 的情况1 i 两个元素会排列很近，当一个被从磁盘中检索到那么另一个也会被容易的 检索，而h a s h 列表中这两个元素会在不同的块中，从而在两个数据都被用到的时 候引起磁盘的i o 。h a s h 的另一个缺点就是执行非确定性查询时会花费很多时间。 比如考虑对所有大于x 的值的查询，对于b t r e e 只要找到x 的右子树的元素就可 以了，而h a s h 却必须要查遍所有的块爿能找到所有满足条件的数据。值得注意的 是b e r k e l e yd b 同时使用了b + - t r e e 和h a s h i n g 两种索引，他们认为h a s h i n g 适合于 数据库方案特别小的比如主存数据库，或者是当数据库太大以至引起由于c a c h e 仅 能适用于结点的- - 4 , 部分，而导致要获取大多数节点时使用b - t r e e 索引会引起磁 盘i o 。b t r e e 索引适用于介于这两种极端情况之间的数据库方案。此外，他们还 使用了队列这种方法主要用于查询队列的首尾数据，这种方法适用于耗费较大数据 容量的系统类型，比如静态机器。 存储器 数据库的存储器的要求对于嵌入式数据库是一个重要的问题。它包括两部分： 是数据库本身的大小，另一个是因存储数据而必须在其上负担( o v e r l o a d ) 数据 量的大小。带指针的索引列表中指针所需的存储空间就是典型的数据负担。典型的 c l i e n t s e r v e r 要求比嵌入式数据库大的多的存储器，p e r v a s i v e s q l 却是一个例外， 这是由于p e r v a s i v e 本身的接口是底层的。b e r k e l e yd b 使用了较小的存储器是因为 额外的功能可以在数据库的上端实现。对于数据负担，p o l y h e d r a 对每一个记录有 表2 4 嵌入式数据库系统存储器尺寸比较 t a b l e2 4d i f f e r e n tm e m o r yn e e d so f i n v e s t i g a t e de m b e d d e dd a t a b a s es y s t e m s d b m s s y s t e mm e m o r yr e q u i r e m e n t s p e r v a s i v e s q lf o rs m a r tc a r d s 8 k b p e r v a s i v e s q lf o re m b e d d e ds y s t e m s 5 0 k b p e r v a s i v es q lf o rm o b i l es y s t e m s5 0 4 0 0 k b p o l y h e d r