（计算机软件与理论专业论文）移动实时数据库事务的优先级分派与调度策略.pdf

i 华 中 科 技 大 学 硕 士 学 位 论 文 摘 要 随着移动计算技术的发展，移动计算系统开始逐渐走进人们的生活。在很多移 动计算系统中，事务具有实时性要求，如移动股票交易系统、导航/定位系统等。但 是由于移动通信网络具有不可靠性、带宽不对称性、频繁断接性等特点，使得移动 环境下的实时事务的实时性难以得到满足，因此有必要对移动实时事务处理进行研 究。 事务调度是实时事务处理的一个关键技术。相对于实时事务而言，移动实时事 务调度不仅要考虑传统实时事务调度所要考虑的问题，还要考虑移动环境的特点。 现有的移动实时事务调度策略大多数都集中于对无线网络的频繁断接的处理上，调 度的目标是最小化错失截止期的事务的数目。在一些移动实时应用中，系统可能给 事务赋予一定的价值以反映如果事务在截止期之前完成系统期望得到的收益，当事 务被赋予不同的价值时，系统的目标就变为最大化系统的实现价值。针对这种应用 有必要研究一种综合考虑事务的价值和无线网络频繁断接的移动实时事务优先级分 派与调度策略。该策略适用于移动环境下的软实时和固实时事务，按照期望价值/空 余时间来给事务分派优先级并在空余时间的计算式中加入了与断接有关的参数，同 时还把发送结果这一步骤加入到事务调度的过程中并增加了准入控制机制来防止系 统过载而导致大量事务夭折。 基于该策略设计了模拟实验并验证了该策略的性能。 关键词：移动实时，事务调度，价值，断接 ii 华 中 科 技 大 学 硕 士 学 位 论 文 abstract with the development of mobile computing technology, mobile computing systems have become more and more popular. in many mobile computing systems, such as mobile stock trading system, navigation/position system, transactions have temporal constraints. but owing to the limitations of the mobile communication network, such as unreliable network, unsymmetrical width and frequent disconnection, the temporal constraints of mobile real- time transactions are difficult to reach. therefore, it s necessary to explore mechanism on mobile real- time transaction processing. transaction scheduling is one of the main issues of real- time transaction processing. relative to real- time transaction, scheduling mobile real- time transactions needs to take into account the characteristics of mobile computing environment. most prior research on mobile real- time transaction scheduling has focused on the frequent disconnections in wireless network and the performance goal is to minimize the number of transactions that missed deadlines. in some mobile real- time applications, the system may assign a value to a transaction to reflect the profit that the system expects to receive if the transaction completed before its deadline. when transactions are assigned different values, the goal of the system shifts to maximizing the realized value of the system. in order to deal with such applications, we proposed a mobile real- time transaction scheduling strategy which considers both the transaction value and the frequent network disconnections. we focus particularly on soft real- time transactions and firm real- time transactions in mobile computing systems. our strategy adds disconnection factor to the slack time computing formula and assigns the value to a transaction by the expected value/slack time. we consider sending result as one step of scheduling transactions. also, an admission control mechanism is employed to prevent the system from overloading. a simulation experiment was conducted to evaluate the performance of the proposed strategy. key words: mobile real- time, transaction scheduling, value, disconnection 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密 ，在_年解密后适用本授权书。 不保密v。 （请在以上方框内打“” ） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 本论文属于 1 华 中 科 技 大 学 硕 士 学 位 论 文 1 引言 1 . 1 研究背景与意义 随着移动计算技术的迅速发展，移动计算系统和移动设备（如 pda、手提电脑、 移动电话等）开始走进人们的日常生活，使人们的通信方式、获取信息的方式发生 了前所未有的变革。在很多移动计算系统（如移动股票交易系统、车载导航/定位系 统、移动电子拍卖系统等）中，用户不仅关心系统的准确性，而且对系统的实时性 也有很高的要求，例如在移动股票交易系统中，如果用户的股票交易事务不能在截 止期内完成，就有可能给用户造成不可挽回的经济损失；在车载导航/ 定位系统中， 如果用户不能及时地收到所请求的导航/ 定位信息，便有可能驶入错误的道路甚至发 生危险；在移动电子拍卖系统中，如果用户的报价请求不能及时的发送出去，就有 可能使用户错失良机。2009 年，3g 牌照在中国正式发放，中国迎来了 3g 时代。3g 是将无线通信与国际互联网等多媒体通信相结合的第三代移动通信技术，它的到来 必将掀起无线通信的新浪潮，将进一步改变人们的学习、工作和生活的方式，同时 也将给人们的生活带来极大的便利。对于 3g 的核心应用，如手机宽带上网、视频通 话、手机电视、手机网游等来说，实时性是至关重要的，它关乎用户的切身利益， 直接影响到用户体验。由此看来，在不久的将来，人们随时随地地访问所需数据的 愿望就会成为现实，同时移动实时数据库技术的重要性也更加显得突出。 移动实时数据库对数据进行有效地存储和管理，对用户发出的移动实时事务进 行处理，将用户请求的数据按照一定的格式组织起来并返回给用户，它是移动计算 系统实现实时应用的关键技术。移动实时数据库技术综合了分布式数据库、实时数 据库、移动数据库等多种技术，但又不仅仅是这几种技术的简单叠加，而是需要进 行理论和实现上技术上的全面研究。事务处理是数据库管理系统的基本功能，主要 用于维护数据的一致性，支持多用户并发访问等，移动实时事务处理包括移动实时 事务模型、移动实时事务并发控制、移动实时事务原子提交、移动实时事务调度等 方面。目前，国内外对移动实时数据库的研究还不够成熟，特别是在移动实时事务 2 华 中 科 技 大 学 硕 士 学 位 论 文 处理技术上尚有许多亟待解决的问题。移动实时事务调度是决定移动实时数据库性 能的关键因素，然而在移动环境下，无线网络的不可靠性、带宽不对称性、频繁断 接性等特点对移动实时事务的实时性构成了巨大的挑战，使得移动实时事务调度相 对于传统实时事务以及移动事务而言变得更加困难，因此，有必要综合运用已有的 实时事务和移动事务调度理论对移动实时事务调度策略进行深入的研究。 1 . 2 移动计算环境的体系结构和特点 常见的移动计算系统由移动主机 （mobile host， mh） 、 移动服务支持站点 （mobile support station ，mss） 、固定节点 （fixed host，fh）以及固定网络（fixed network） 等组成1，其体系结构如图 1.1 所示。 fixed network mss mh mh mss mh mhmh mss mh mss mh mh fhfh wireless cellwireless cell wireless cellwireless cell 图 1.1 常见的移动计算系统的体系结构 fh 与 mss 通过固定网络建立连接，mss 具有无线通信接口，每个 mss 建立一 个无线通信单元 （wireless cell） ， 无线通信单元内的 mh 通过无线网络与其对应 mss 建立连接，进而与 fh 建立连接。通常 fh 包含有完整的数据和功能，mh 只包含有 部分的数据和一些功能模块，mh 上的大部分操作都需要提交到 fh 上去执行，然后 fh 将执行结果发送给对应的 mh。当一个 mh 的移动范围超出了某一个 mss 的无 3 华 中 科 技 大 学 硕 士 学 位 论 文 线通信单元并进入另一个 mss 的无线通信单元时，该 mh 就不能再同之前的 mss 进行通信而只能同现在的 mss 进行通信，这种现象称之为跨区切换。与基于固定网 络连接的分布式计算环境相比，移动计算环境主要有以下特点2： 1.移动性： 移动主机可以在某一个无线通信单元内以及在多个无线通信单元之间 的自由移动并在移动的过程中保持网络连接。 2.频繁断接性：在移动环境下，由于电源、网络条件等因素的限制，移动主机一 般不采取持续连接的工作方式，而是频繁的断接、再连接。 3.网络条件多样性：由于移动主机是可自由移动的，因而移动主机可能会处于固 定网络、无线网络、甚至是无网可用的环境下。 4.无线网络通信的不对称性： 无线网络通信的不对称性表现固定节点的发送能力 大大强于移动主机的发送能力，下行链路（固定节点到移动主机）的通信带宽和代 价与上行链路（移动主机到固定节点）的相差很大。 5.不可靠性：无线网络与固定网络相比，可靠性较低，更容易受到干扰而出现网 络故障。 6.移动主机的电源能力有限：移动主机主要依靠电池供电，而电池的容量相当有 限。 7.规模：在移动技术环境下，许多移动计算系统，如移动通信运营商所用的信息 系统，需要能够支持大量的移动用户并发访问，从而使移动计算系统的规模比传统 分布式系统的要大得多。 1 . 3 国内外研究现状 1 . 3 . 1 实时数据库研究 在数据库理论中，实时数据库系统（rtdbms）是指其事务具有显示时间限制 的数据库系统， 系统的正确性不仅依赖于逻辑结果， 还依赖于逻辑结果产生的时间3。 实时数据库技术是实时系统和数据库技术相结合的产物，在工业控制、航空航天以 及武器制导等领域有着广泛的应用。从 20 世纪 70 年代开始，有关实时数据处理的 4 华 中 科 技 大 学 硕 士 学 位 论 文 论文和专著就陆续出现在人们的视野中，到了 20 世纪 80 年代后期，实时数据库得 到了实时系统和数据库系统两个领域的研究者的普遍关注，1988 年发表的 acm sigmod record实时数据库系统专刊揭示了实时数据库研究领域的诞生4。实时数 据库系统的主要研究内容包括实时并发控制、分布式实时数据库、实时事务调度等 方面。 1.实时并发控制 传统的并发控制协议的研究主要集中于冲突检测、冲突解决等方面。冲突检测有 悲观和乐观两种方法，相应的并发控制协议被称为悲观并发控制协议（pessimistic concurrency control，pcc）和乐观并发控制协议（optimistic concurrency control， pcc） 。pcc 协议在存取数据之前检测冲突，occ 协议允许事务访问所需的数据，只 是在事务提交时检测冲突。检测到冲突时，常用的冲突解决办法有阻塞请求、夭折 或重启一个或多个冲突事务。实时并发控制协议一般基于传统的并发控制协议并针 对实时性所带来的问题作了相应的改进。 优先级反转（priority inversion）是实时并发控制面临一个的主要问题，即高优先 级的事务被迫等待低优先级的事务，常用的解决方法有高优先级夭折、优先级继承 （priority inheritance） 、优先级顶（priority ceiling）等。文献5中的并发控制协议采 用了高优先级夭折的方法，如果一个高优先级的事务请求对某个数据项加锁，而这 个数据项的锁已经被一个或者多个低优先级的事务持有，则持有锁的低优先级事务 被夭折；如果一个低优先级的事务请求某个被高优先级的事务持有的锁，则低优先 级事务等待。该协议可以避免优先级反转，但是其缺点是可能导致不必要的事务重 启。文献6采用了优先级继承的方法，当一个高优先级的事务被一个低优先级的事 务阻塞时，系统提升低优先级事务的优先级使之与高优先级的事务相等，从而加速 低优先级的事务的执行，防止其被中等优先级的事务抢占造成高优先级的事务继续 等待。文献7使用了优先级顶的方法，优先级顶协议为每个数据项设一个“优先级 顶” ，即所有可能使用它的事务中的优先级最高的那个事务的优先级，当一个事务对 该数据项加锁时，系统便把这个“优先级顶”赋予这个事务，使这个事务的优先级 最高。当这个事务完成对该数据项的操作后立即把它的优先级恢复正常，从而保证 5 华 中 科 技 大 学 硕 士 学 位 论 文 系统不会出现优先级反转的现象。 可串行化是传统数据库的一条重要的正确性准则， 在一些实时应用中为了实时性 可能会放松对精确性的要求。文献8的提出了 epsilon- data（- data） 和 delta- deadline （- deadline）的概念，放松了事务的 acid 特性，并由此提出了相应的并发控制策 略，但只适用于那些可以忍受一定程度的不精确数据和一定程度的时间延迟的应用， 如网络视频等。文献9提出了基于放松可串行化的并发控制技术- 可串行化 （epsilon- serializability） ，- 可串行化允许一个事务未提交的结果被另一事务读取 10。 2分布式实时数据库 分布式实时数据库是在集中式实时数据的基础上发展而来的。 一个分布式实时事 务通常被分解为若干个子事务并分发到多个节点上去执行，子事务执行完毕后分别 提交，为了保证事务的原子性，各子事务要么全部提交要么全部不提交，因此需要 原子提交协议的支持。传统的分布式提交协议，如两阶段提交协议 2pc（two- phase commit）11以及由 2pc 扩展而来的 pc（presumed commit） ，pa（presumed abort） 12等都没有考虑事务的实时性限制。文献13提出了一种针对分布式实时数据库的 实时提交协议 rcp（real- time commit protocol） ，rcp 的基本思想是协调者的提交 处理依赖于参与者及时完成的结果，在 rcp 中，参与者可以在本地单方面做出提交 /夭折的决定，并释放相应资源，此后若发现本地数据与全局数据不一致，则执行相 应的补偿事务，以消除本地子事务带来的影响10。 3实时事务调度 实时事务的一个基本特征是具有显示的时间限制，一般表现为截止期。 按照事 务错失截止期对系统带来的影响，实时事务可分为三类：硬实时事务、固实时事务、 软实时事务。 （1）硬实时事务：事务错失截止期可能对系统造成灾难性的后果。硬实时事务 i t 的价值函数( ) i v t 如图 1.2 所示。 其中 t 为时间， i a 是事务的到达时间， i d 是事务的截止期。 i t 的价值在截止期 i d 之前是一个常数值 i v ，在截止期 i d 之后立即变为一个负值 j v。 6 华 中 科 技 大 学 硕 士 学 位 论 文 t0 i d ( ) i v t i v j v i a 图 1.2 硬实时事务的价值函数 （2）固实时事务：一旦到达截止期，事务的价值会立即降为零，此后也固定为 零。固实时事务 i t 的价值函数( ) i v t 如图 1.3 所示。 t0 i d ( ) i v t i a i v 图 1.3 固实时事务的价值函数 i t 的价值在截止期 i d 之前是一个常数值 i v ，在截止期 i d 时变为零，此后也一直 为零。固实时事务与硬实时事务的区别在于固实时事务错失截止期不会对系统造成 灾难性的后果。 （3）软实时事务：超截止期后，事务仍有一定的价值，但随着时间的推移，其 价值不断下降，直到某一时刻降为零，此后一直保持为零。软实时事务 i t 的价值函 数( ) i v t 如图 1.4 所示。 其中 i d 是 i t 的截止期（也称为第一截止期） ， i d 是 i t 的扩展截止期。 i t 的价值 在截止期 i d 之前是一个常数值 i v ，在截止期 i d 之后并不立即降为零而是不断下降直 到时刻 i d 时才变为零，此后也一直为零。 7 华 中 科 技 大 学 硕 士 学 位 论 文 0t i d ( ) i v t i a i d i v 图 1.4 软实时事务的价值函数 1973 年，c.l.liu 和 j.w.layland 提出了一种适用于周期性硬实时事务的静态优 先级调度算法单调速率（rate monotonic, rm）算法14，rm 算法自从提出以来 得到了广泛的研究和应用，目前已经有大量基于 rm 算法的扩展改进算法被提出， 包括 edf（earliest deadline first） 、edf- cr（edf with conditional restart） 、efdf （earliest feasible deadline first） 、lsf（least slack first）等6。事务还可能被赋予 一定的价值，haritsa 等15提出了一系列基于价值的调度算法：hvf（highest value first） ，vd（value- inflated deadline） ，vrd（value- inflated relative deadline）以及 ba（bucket algorithm）等。其中的一些算法将在第二章对进行详细介绍。 随着实时数据库理论的日益成熟和完善，各种商业实时数据库产品层出不穷， 其中国际上比较知名的产品包括美国 aspentech 公司的 aspen infoplus，美国 wonderware 公司的 industrial sql server，美国 osisoft 公司的 pi（plant information system ）以及美国 honeywell 公司的 phd 等。相比而言，国内的实时数据库产品在 技术性能、用户功能扩展等方面还和国外的产品有一定的差距，目前国内比较有代 表性的有紫金桥软件公司的紫金桥实时数据库系统，中科院软件所的 agilor 实时数 据系统以及北京和利时系统工程有限公司的 realmis 系统等16。 1 . 3 . 2 移动数据库研究 从 20 世纪 90 年代初期开始，移动数据库开始成为一个新的研究方向。随着移动 通信技术的进步和移动产品商业价值的显现，移动数据库技术越来越受到重视，在 移动数据库领域，国外的一些著名研究机构如美国的 rutgers 大学、卡内基- 梅隆大 8 华 中 科 技 大 学 硕 士 学 位 论 文 学（cmu） 、佐治亚理工学院等已经在许多方面取得了丰硕的成果 17。有关移动数 据库的研究主要有以下几个方面： 1.移动事务模型 kt（kangaroo transaction）模型18是一种基于集中式移动环境（有固定节点、 基站和移动主机）的事务模型，该模型基于全局事务（也称 kangaroo 事务）和幼事 务（joey transaction）模型，一个全局事务由一个或多个幼事务组成，一个幼事务由 可以在某一个基站的无线通信单元内执行的所有操作组成，一个幼事务又包含一个 或多个子事务，幼事务可以独立提交。kangaroo 事务有两种不同的执行方式：一种 是补偿模式，在这种模式下任何一个幼事务的失败将引发所有已提交的幼事务被补 偿，其他处于活动状态的幼事务被夭折；另一种是分裂模式，与补偿模式不同的是， 在该模式下如果一个幼事务失败，已提交的事务不会被补偿，而其他处于活动状态 的事务是被提交还是夭折将由数据库管理系统来决定。cluster 模型17 19基于完全分 散式移动环境（各个节点的配置和处理能力是相同的） ，在 cluster 模型中数据库被 分为多个“cluster，各个节点均可以发起并执行全局事务，如果事务在本地更新数 据，则该数据的版本称为弱版本（weak version） ，弱版本数据只能由该弱事务访问， 一旦全局提交，弱版本就变为强版本（strict version） ，此时所有事务都可以访问该 数据。此外还有 pro- motion20模型，prewrite 模型等。 2.复制与缓存技术 复制主要是为了提高移动数据库的可用性和可靠性。由于移动网络的不可靠性， 移动主机上通常缓存有部分常用的数据，以减少移动主机访问服务器的频率，同时 保证用户在移动主机断接情况下可以继续执行一定的操作。 文献21给出了一种两级 复制（two- tier replication）技术。在断接的情况下，移动主机可以执行暂态更新事 务，生成数据的暂态版本，当重新连接时，移动主机丢弃暂态版本并将数据同步到 主节点上的最新版本。对于缓存较小的移动主机，缓存替换策略就显得非常重要， 文献22对不同的替换算法进行了分类讨论并通过实验进行了比较。 移动环境下的移 动主机的频繁断接性和移动性可能会使移动主机缓存的数据失效， 为此文献23提出 了三种缓存失效策略，它们都是通过服务器周期性地广播失效报告来使移动主机的 9 华 中 科 技 大 学 硕 士 学 位 论 文 缓存与服务器保持同步。 3.位置管理与位置相关查询 在移动数据库中，由于移动主机可自由移动，因而移动主机的位置可能是不断变 化的。位置更新是移动主机的位置管理的一个重要研究内容。基于时间的位置更新 策略是一种最简单的更新策略，移动主机根据预定的时间周期性的向服务器更新自 己的位置信息，这种策略会产生很多不必要的位置更新信息。文献24提出了基于运 动的位置更新策略，该策略根据移动主机穿越无线通信单元（wireless cell）的次数 来确定移动主机更新位置的时机，该策略在一般情况下可以减少发送位置更新信息 的次数。文献25提出了基于距离的位置更新策略，这种策略设定了一个距离限制， 如果移动主机的当前位置与服务器上记录的它的位置之间的差值超过了该距离限 制，移动主机就向服务器发出位置更新信息，该策略与前两种策略相比性能更优， 许多其他的位置更新策略都是由基于距离的位置更新策略改进而来的43。 在移动数据库中，由于移动主机的移动性，查询结果不仅与数据库的内容有关而 且与移动主机的位置有关，同一个查询请求在不同的位置提交可能得到不同的查询 结果，如用户在查询离自己所在地最近的银行。在不同的地点得到的查询结果可能 是不一样的，这种查询被称为位置相关查询。位置相关查询的一个研究方向是如何 从位置服务器中查找移动主机的位置，另一个重要的研究方向是查询与移动主机有 关的位置关系，如范围和邻近查询26等。 4.数据广播 数据广播是移动环境下实现可伸缩性访问的一个有效的方法， 移动主机即使处于 断接状态也可以选择接收从服务器发送过来的广播数据，可以以较小的代价解决大 规模用户访问的问题。广播调度算法是数据广播的一个重要的研究方面，主要分为 静态广播调度和自适应广播调度等27。 随着移动数据库在理论和实现技术上的不断完善以及移动设备的市场需求日益 增大，各大数据库公司纷纷推出了自己的移动数据库产品，如 oracle 的 oracle lite，sybase 的 adaptive server anywhere，ibm 的 db2 everyplace 以及 microsoft 的 sql server 移动版等。 在国内则有东软的 open base 和北京人大金仓信息技术股份有 10 华 中 科 技 大 学 硕 士 学 位 论 文 限公司的小金灵等。 1 . 3 . 3 移动实时数据库研究 实时数据库和移动数据库的研究为移动实时数据库技术打下了坚实的理论基础， 从 20 世纪 90 年代后期开始，研究者逐渐开始关注移动实时数据库，并取得了一定 的研究成果。 在事务模型方面， 文献28提出了两种移动实时事务模型 esfh （execution site is a fixed host）和 esmh（execution site is a mobile host） ，在 esfh模型中，移动主 机将整个事务发送到固定节点上执行，然后固定节点将执行结果返回给移动主机； 在 esmh 模型中，事务在移动主机上执行，在执行的过程中，移动主机向固定节点 请求所需的数据。文献2提出了一个分片段的移动实时事务模型，一个移动实时事 务包含一组片段，从理论上来讲该模型可有效的支持事务执行的移动性、分布性。 在移动实时数据库中， 并发控制的目标不仅包括传统实时并发控制策略中所提到 的节省系统资源、保持数据库的一致性、尽量避免优先级反转等，而且包括对移动 环境下断接的考虑以及减少错失截止期的事务的数目。文献29基于 hp- 2pl（high priority two- phase locking）协议提出了移动分布式实时数据库下的并发控制协议 dhp- 2pl（distributed high priority two- phase locking） ，文章提出了事务传送 （transaction shipping）的概念来减轻并发控制策略对网络性能的依赖，并采用了相 似性的概念来解决那些在移动网络环境下代价过高的数据访问冲突。 文献30首先给 出了一个能够减少并发控制中的阻塞的分歧控制锁模型以及一个支持断接的签出/签 入（check- out/check- in）协议，然后在其基础上提出了一个基于两阶段封锁机制的 并发控制协议 dc/pos- pai- 2pl。在移动广播环境下，传统数据库的严格的可串行化 标准对于移动实时事务来说显得过于苛刻，而某些放松可串行化的策略如 epsilon- 可 串行化、similarity- 可串行化又有可能在一定程度上影响数据库的一致性，文献31 提出了一种新的正确性标准弱可串行化（weak serializability） ，并提出了相应的 并发控制协议。 文献32介绍了分布式移动实时事务的原子提交的定义并在此定义的 基础上提出了一种针对分布式移动实时事务的一阶段提交协议 1pracp。 11 华 中 科 技 大 学 硕 士 学 位 论 文 在广播环境下， 当数据广播被用于将频繁更新的数据发送至移动主机上用于执行 只读事务时，就被称之为更新分发（updates dissemination） 。移动环境下已有的更新 分发协议由于没有考虑事务和数据的时间限制而不适用于移动实时只读事务，为此， 文献33提出了一种更新分发协议 hfmvb（hybrid forward multi- version data broadcast） ，通过缩短一致性间隔、立即广播更新、按需广播等方法，可以提高数据 的流通量，减少错失截止期的事务的数目。 在事务调度方面，文献1针对无线网络频繁断接的问题提出了一种调度策略 dt- protocol（disconnection tolerance protocol） ，其基本思想是为了保证移动主机及 时地收到可用的数据，服务器必须决定何时向移动主机发送执行结果。例如，如果 服务器预测在发送整个结果之前可能会发生断接，那么服务器可以在断接之前发送 部分或不精确的结果，但是如果服务器估计移动主机将会马上重连且事务在断接的 时间内不会超期，那么服务器可能会选择等待一段时间以发送更精确、完整的结果， 但是只适用于移动只读软实时事务。移动自组网（mobile ad- hoc network，manet） 是一种特殊的移动网络，文献3435针对 manet 的实时事务提出了相应的调度策 略，重点考虑的断接的因素。这两种移动实时调度策略将在第二章详细介绍。 1 . 4 论文的主要研究内容及组织结构 本文首先对现有的实时事务和移动实时事务调度策略进行分析， 然后对移动实时 事务的优先级分派与调度策略进行研究，研究的重点在于找到一种好的实时调度算 法同时要考虑移动环境对事务实时性的影响。本文共分为六章，文章的组织结构以 及各章的主要内容如下： 第 1 章对移动计算环境、课题的研究背景以及国内外研究现状进行了简要介绍。 第 2 章从基于最小化事务错失率以及基于最小化系统实现价值两个角度对常见 的实时事务优先级分派与调度策略进行了分类介绍并详细介绍了两种支持断接的移 动实时事务调度策略。 第 3 章对现有的实时事务及移动实时事务优先级分派及调度策略进行分析， 找出 了其缺点与可取之处，设计了一种综合考虑无线网络频繁断接以及事务价值的移动 12 华 中 科 技 大 学 硕 士 学 位 论 文 实时事务优先级分派与调度策略。 第 4 章给出了测试文本所提出的调度策略的原型系统，对系统模型、系统的主要 数据结构以及所涉及的关键技术进行了介绍。 第 5 章给出了实验数据并对实验结果进行了分析。 第 6 章总结了全文的工作，指出了进一步研究的方向。 13 华 中 科 技 大 学 硕 士 学 位 论 文 2 实时事务调度 2 . 1 实时事务调度 实时事务的调度是基于优先级的，优先级越高的事务越先执行，是一种抢占式调 度。现有的实时事务调度策略按照调度目标的不同可以分为两类：基于最小化事务 错失率（minimizing miss ratio）的调度6 14 37 38和基于最大化系统实现价值 （maximizing realized value）15 39 40 41的调度。 2 . 1 . 1 基于最小化事务错失率的调度 基于最小化事务错失率的调度的目标在于最小化错失截止期的事务的数目。 下面 对几种常见的基于最小化错失率的调度算法进行简要介绍（以t表示当前时间，e表 示事务的执行时间估算，p表示已执行时间，d 表示事务的截止期） 。 1.fcfs（first come first serve） ：具有最早放行时间（release time）的事务的优 先级最高6。如果事务的放行时间等于其到达时间（arrive time） ，则 fcfs 算法等同 于传统的先来先服务方法。 2.rm（rate monotonic） ：周期越短的事务的优先级越高14。rm 算法用来调度 周期性的硬实时事务，所谓周期性的事务是指周期性到达的事务。 3.edf（earliest deadline first） ：具有最早截止期的事务的优先级最高6。 4.lsf（least slack first） ：空余时间最短的事务优先级最高6 42。对于一个事务 t，其空余时间s定义为()sdtep=+。 2 . 1 . 2 基于最大化系统实现价值的调度 在一些实时数据库中， 系统可能给事务赋予一定的价值以反映如果事务在截止期 之前完成系统期望得到的收益15。在很多实际应用中，不同的实时事务具有不同的 价值，调度的目标就变为最大化系统的实现价值。 14 华 中 科 技 大 学 硕 士 学 位 论 文 文章39通过实验表明事务的价值和截止期都对系统的性能有重要影响。 以下是几 种基于价值的优先级分派算法（以 t a 表示事务的到达时间， t v 表示事务的价值， t d 表示事务的截止期， t p 表示事务的优先级， t p 的值越小表示优先级越高） ： 1. hvf（highest value first） ：优先级分派函数为：1 tt pv= 15。价值越大，事 务的优先级越高。 2. vd（value- inflated deadline） ：优先级分派函数为 ttt pdv= 15。vd 算法综 合考虑了截止期和价值这两个因素。 3. vrd（value- inflated relative deadline） ：优先级分配函数为() tttt pdav=， 其中 tt da表示事务的相对截止期15。 4. hrf（highest reward first） ：优先级分派函数为：( ) / t pev tr=，其中( )ev t 表示事务在时刻 t 的期望价值，即从时刻 t 来看，事务在预期的时刻执行完毕时的价 值，r为事务的剩余执行时间40。给定一个事务 i t ，其到达时间为 i a ，截止期为 i d ， 价值函数为( ) i v t ， i t 在 1 t 时刻的期望价值为 1 ( ) i ev t，则 11 ( )() iii ev tv tr=+。剩余执行 时间r可以用ep来表示，其中e为事务的执行时间估算，p为已执行时间。 2 . 2 移动实时事务调度 目前已有的对移动实时事务调度策略大多侧重于解决移动环境下的频繁断接给 事务实时性带来的影响。文献1提出了 dt- protocol （disconnection tolerance protocol）调度策略，该策略针对带有扩展截止期的移动软实时事务，且只支持查询 操作。dt- protocol 采用了- data 和- deadline 概念8。- data 指一定程度上的不精 确数据，- deadline 指一定程度上延长了的截止期（对于软实时事务也可称为扩展 截止期） ，这两个概念适用于那些可忍受一定程度的时间延迟及不精确结果的领域， 如无线网络视频。 dt- protocol 策略的主要思想体现在对无线网络频繁断接的处理上，其关键就在 于确定发送结果的最晚时间（发送之前需检查结果是否满足- data 的要求） ，这个时 15 华 中 科 技 大 学 硕 士 学 位 论 文 间称之为最迟响应时间( )l t。在进行事务调度时，事务的优先级分派基于最迟响应 时间( )l t，具有最早( )l t的事务的优先级最高。令 i t 为移动主机 mh_i发出的事务， ( ) i d t 为事务的截止期，( ) i d t 为事务的扩展截止期，t 为当前时间， ci t 为移动主机 和服务器之间建立连接的时间， i minc 为服务器与 mh_i之间连接保持的最短时间， i maxd 为服务器与 mh_i之间断接持续的最长时间。在 i t 执行的过程中，当一个新的 连接在时刻 ci t 建立起来后， 服务器将会估计该连接是否会在 i t 的扩展截止期( ) i d t 之 前断掉，有以下三种可能的情况： 1. ( ) iiciii mincdttmincmaxd +：如果在事务到达其扩展截止期之前发生 断接，则就有可能错失其扩展截止期。在这种情况下，须令 ( ) icii l ttminc=+，即 在 ( ) i l t 时刻之前，如果结果数据满足- data 的要求，服务器必须发送一个不精确的 结果。 2. 0( ) icii dttminc ：在事务的扩展截止期之前不会发生断接，在这种情况 下，服务器将会成功地发送一个精确的结果， ( )( ) ii l td t =。 3. ( )( ) iciiiici dtttmincmaxddtt + +：在这种情况下可以认为在连接至 少会保持到时刻( ) ii dtmaxd 。如果服务器认为 mh_i断接后不再重新建立连接， 那么 ( )( ) iii l tdtmaxd =，在 ( ) i l t 时刻之前，如果结果数据满足- data 的要求，服 务器必须发送一个不精确的结果。如果服务器认为 mh_i 断接后会重新建立连接， 服务器就会选择等待一段时间以发送更精确、完整的结果。当连接重新建立起来后 就又回到了前两种情况。 文献35针对移动自组网（mobile ad- hoc network，manet）中的实时事务提出 了相应的调度策略。manet 是一种特殊的移动网络,在 manet 中，没有固定的网 络基础设施（如 fh、固定网络等）和 mss 节点，移动主机可以自由移动并通过无 线网络互相连接。一种典型的 manet 的体系结构如图 2.1 所示。 在文献35中 mh 被分为两类：一类称之为 smhs（small mobile hosts） ，这类 mh 的主存、 磁盘、 电源以及计算能力都经过了缩减； 一类称之为 lmhs （large mobile hosts） ，此类移动主机的各种配置都比 smhs 的要强。每个 mh 都有一定的影响范 16 华 中 科 技 大 学 硕 士 学 位 论 文 围， 类似于图 1.1 中的 mss 的无线通信单元， mh 可以与那些在其影响范围内的 mh 直接通信。在图 2.1 中，带虚线的椭圆表示某个 mh 的影响范围，mh 之间的无线连 接用虚线段表示。 如果两个 mh 不在对方的影响范围内， 二者将通过它们之间的 mh 间接通信。由于电源和存储能力的限制，lmhs 存储有完整的数据库，而 smhs 上 只有部分功能模块。在 manet 中，mh 完全依靠电池供电，因而其电源能力非常 有限，为了节省电源，mh 可能处于以下三种状态之一：活动状态、待机状态和睡眠 状态。mh 最初都处于活动状态，当 mh 没有生成事务或者执行事务时，就转入待 机状态，当 mh 的电源消耗完毕时，就进入睡眠状态。 lmh_1smh_1smh_2 smh_3smh_4 lmh_2smh_5 图 2.1 manet 体系结构 当 lmh将执行结果发送至对应的 smh 时，如果对应的 smh 处于活动状态，该 smh 将会接收执行结果；如果对应的 smh 处于待机状态，该 smh 将会根据自身的 电源状况和事务类型来决定是否接收执行结果；如果对应的 smh 处于睡眠状态，那 么该 smh 将无法收到执行结果。断接主要产生于后两种情况，为了减轻断接对实时 事务的影响，文章对传统的 lsf 算法6作了修改，增加了对断接因素的考虑，其空 余时间 s 的计算公式为() dd sdtcpt=+， 其中 d 为事务的截止期， t 为当前时间， c 为事务的运行时间估计， d p 为运行期间的断接率， d t 为每次断接的平均持续时间。 d p 和 d t 的值可以通过事务执行历史统计得到。令 ij t为 smh_i发送给 lmh_j 的实时 事务，在 ij t执行的过程中（从开始执行到发送执行结果之前） ，lmh_j 统计 smh_i 发生断接的次数并记录每次断接持续的时间， 通过这些值， lmh_j就可以确定smh_i 的断接率以及每次断接的平均持续时间。 17 华 中 科 技 大 学 硕 士 学 位 论 文 2 . 3 小结 本章首先从基于最小化事务错失率和基于最大化系统实现价值两方面对实时事 务调度算法进行了介绍，然后对两种移动实时事务调度策略进行了分析，为第三章 做好了理论准备。 18 华 中 科 技 大 学 硕 士 学 位 论 文 3 一种移动实时事务的优先级分配与调度策略 3 . 1 移动实时事务模型和基本假设 为了简化并不失一般性，本文使用一个固定节点 fh，下文称之为 server，n 个 移动主机 mh，mh 通过无线网络