（计算机应用技术专业论文）事务管理器软件构架及调度优化方法研究.pdf

、 j l ； p j ， i 一 i l li f r l ff l f f f l f f l f l l lirffu lr r i i i i l l 舢 y 18 1 | , 1 1 1 2 1 1 i i i i 5 i ir l l l 7 l a l l l l 5 1 1 1 11 4 i t t l | 。 n a n ji n gu n i v e r s i t yo f a e r o n a u t i c sa n da s t r o n a u t i c s t h eg r a d u a t es c h o o l c o l l e g eo fi n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y r e s e a r c ho nt r a n s a c t i o n m a n a g e r s o f t w a r ea r c h i t e c t u r ea n d s c h e d u l i n g o p t i m i z a t i o nm e t h o d a t h e s i si n c o m p u t e rs c i e n c ea n dt e c h n o l o g y b y ， l i a oz h e n g x i n a d v i s e db y p r o w a nl i n r u i s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o r t h ed e g r e eo f m a s t e ro fe n g i n e e r i n g j a n u a r y , 2 0 1 0 ， i f 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进 行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外， 本学位论文的研究成果不包含任何他人享有著作权的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标 明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许 论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：廛堡斑 作者签名：迓正霾 日 期：迦坦：墨：丝 j j 审 入 t 矿 ， ， 南京航空航天大学硕士学位论文 摘要 本文的研究背景是某飞机显控系统对嵌入式数据库的应用需求预研项目。为提高事务管理 器事务调度的成功率及软件的构架性能，对事务管理器的混合事务调度、并发控制及软件构架 模型进行研究。 首先通过引入工作流参考模型、元模型等工作流技术来分析调度流程，构建事务管理器的 功能模型，并采用b p e l 语言对事务调度过程进行形式化描述。进而针对事务调度，引入混合事 务调度的概念，给出混合事务调度模型，并对非周期性事务调度进行研究。通过t b 算法缩短非 周期性事务截止期，促进非周期事务的响应时间，从而减少事务的截止期错失率。 其次，在事务管理器领域设计阶段，以面向对象和面向构件方法论为指导，建立初始类模 型、细化类模型等来描述对象的结构关系，并使用交互模型和状态模型来描述对象行为。引入 算法模式和代理机制对软件构架模型进行优化，提高软件构架性能。在进一步细化的基础上， 针对存在的不必要的事务重启，引入时间戳矢量的概念，提出改进的基于时间戳矢量的乐观并 发控制算法，解决事务不必要重启的问题。 最后，给出事务管理器的软件构架及其a c m e 描述，并给出基于时间戳矢量的乐观并发控 制算法的程序实现。 文中提到的事务管理器功能模型、混合事务调度模型等方法论被用于事务管理器的研究和 实现中，规范了整个软件的研究开发过程，提高了模型分析与设计效率，所给出的改进的t b 算法和基于时间戳矢量的乐观并发控制算法，具有一定的理论意义和工程实用价值。 关键词：事务管理器；混合事务调度：t b 算法；乐观并发控制；时间戳矢量；b p e l 表示；a c m e 表示； 事务管理器软件构架及调度方法优化研究 a b s t r a c t t h eb a c k g r o u n do ft h i ss t u d yw a sb a s e do na l la i r c r a f td i s p l a yc o n t r o ls y s t e mf o re m b e d d e d d a t a b l ea p p l i c a t i o nr e q u i r e m e n t sp r e - r e s e a r c hp r o j e c t i no r d e rt oi m p r o v et h es u c c e s sr a t eo f t r a n s a c t i o ns c h e d u l i n ga n dt h ep e r f o r m a n c eo fs o f t w a r ef r a m e w o 出，t h em i x e dt r a n s a c t i o ns c h e d u l i n g , c o n c u r r e n c yc o n t r o la n ds o f t w a r ea r c h i t e c t u r em o d e la r er e s e a r c h e d f i r s to fa l l ，t h ea r t i c l ei n t r o d u c e dt h et e c h n o l o g yo fw o r k f l o ws u c ha st h ew o r k f l o wr e f e r e n c e m o d e la n dm e t a - m o d e lt oa n a l y z et h es c h e d u l i n gp r o c e s s t h ef u n c t i o n a lm o d e lo ft h et r a n s a c t i o n m a n a g e ri sp r o p o s e dw i t ht h ew o r k f l o wm o d e l a n dt h ef o r m a ld e s c r i p t i o no ft h es c h e d u l i n gp r o c e s s i sg i v e nb yu s i n gb p e l b yr e s e a r c h e do nt h es c h e d u l i n ga l g o r i t h m ，t h em i x e dt r a n s a c t i o ns c h e d u l i n g i sp r o p o s e d t h et b 。a l g o r i t h mi su s e dt os h o r t e nt h ed e a d l i n eo fn o n - c y c l i c a lt r a n s a c t i o n ，a n d p r o m o t e dt h er e s p o n s et i m eo fn o n - p e r i o d i ct r a n s a c t i o n ，t h e r e f o rr e d u c e dt h et r a n s a c t i o nd e a d l i n e m i s sr a t i o t h e n ，i nt h ea e f ao fs o r w a r ea r c h i t e c t u r em o d e l ，o b j c o t - o r i e n t e da n dc o m p o n e n t - o r i e n t e d m e t h o d o l o g yw a su s e dt oe s t a b l i s hs o f t w a r ea r c h i t e c t u r em o d e la n di n i t i a lc l a s sm o d e l ，w h i c h d e s c r i b e dt h es t r u c t u r eo ft h er e l a t i o n s h i pb e t w e e nt h eo b j e c t ，t h eo b j e c tb e h a v i o ra r cd e s c r i b eb yt h e i n t e r a c t i v em o d e la n dt h es t a t em o d e l t h ea l g o r i t h m sd e s i g np a t t e r na n da g e n c ym o d e la r ei m p o r t e d t oo p t i m i z et h es o f t w a r ea r c h i t e c t u r ep e r f o r m a n c e h lt h ea r e ao fc o n c u r r e n c yc o n t r o l ，w i t hr e g a r dt o t h ee x i s t e n c eo fu n n e c e s s a r yt r a n s a c t i o nr e s t a r t ，t h eb a s e dt i m e s t a m p - v e c t o ro p t i m i s t i cc o n c u r r e n c y c o n t r o la l g o r i t h m sw a sp r o p o s e db yi n t r o d u c t i o no ft h ec o n c e p to fv e c t o rt i m e s t a m p f i n a l l y , t h et e c h n i q u eo fs o f t w a r ei m p l e m e n t a t i o n i sp r e s e n t e d t h em a j o rc o m p o n e n t sa r c d e s c r i b e db ya c m e b a s e d0 nt h i s ，t h et y p i c a li m p l e m e n t a t i o no ft h ek e ya l g o r i t h mi sp r e s e n t e d t h ea r t i c l em e n t i o n st h et r a n s a c t i o nm a n a g e rf u n c t i o nm o d e l s ，m i x e dm o d e l sm e t h o d o l o g yf o r t r a n s a c t i o ns c h e d u l i n gt r a n s a c t i o nm a n a g e ra r eu s e di nr e s e a r c ha n di m p l e m e n t a t i o n ，s p e c i f i c a t i o no f t h ee n t i r es o f t w a r ed e v e l o p m e n tp r o c e s s ，i m p r o v et h ee f f i c i e n c yo ft h em o d e la n a l y s i sa n dd e s i g n ，t h e i m p r o v e m e n tg i v e no ft h et b a l g o r i t h ma n dt h eb a s e dt i m e s t a m p - v e c t o ro p t i m i s t i cc o n c u r r e n c y c o n t r o la l g o r i t h mh a sac e r t a i nt h e o r e t i c a ls i g n i f i c a n c ea n dp r a c t i c a le n g i n e e r i n gv a l u e k e yw o r d s ：t r a n s a c t i o nm a n a g e r , m i x e dt r a n s a c t i o ns c h e d u l i n g , t b a l g o r i t h m , o p t i m i s t i c c o n c u r r e n c yc o n t r o l ，t i m e s t a m pv o c t o r , b p e ld e s c r i p t i o n ，a c m er e p r e s e n t a t i o n , ， a l 南京航空航天大学硕士学位论文 目录 第一章绪论1 1 1 研究领域的应用与发展概况l 1 2 课题研究意义和研究内容3 1 3 课题研究的主要工作4 第二章实时事务调度方法与工作流建模方法5 2 1 传统实时事务调度方法5 2 1 1 优先级分派策略5 2 1 2 典型调度方法6 2 2 实时并发控制协议8 2 2 1 并发控制方法8 2 2 2 实时并发控制9 2 3 工作流建模方法1 3 2 3 1 工作流参考模型1 3 2 3 2 元过程模型1 6 2 3 3 工作流描述语言b p e l 1 7 2 4 本章小结2 0 第三章事务管理器的领域模型2 l 3 1 事务管理器的领域分析2 1 3 1 1 事务管理器的需求描述2 2 3 1 2 事务管理器的功能模型2 4 3 2 事务管理器b p e l 描述2 7 3 3 混合实时事务调度算法2 9 3 3 1 混合实时事务调度模型3 0 3 3 2 基于t b 非周期性事务调度3 1 3 4 事务管理器用例模型3 2 3 5 典型活动模型3 5 3 6 本章小结3 6 第四章事务管理器的对象体系结构3 7 4 1 初始类构架3 7 4 2 构架优化3 9 4 3 事务调度行为模型4 l 4 3 1 事务调度交互图4 1 事务管理器软件构架及调度方法优化研究 4 3 2 事务调度状态图4 3 4 4 基于时间戳矢量的乐观并发控制方法“ 4 4 1 不必要重启问题的提出4 5 4 4 2 算法描述4 6 4 5 本章小结5 1 第五章事务管理器的典型应用实现5 2 5 1 开发环境选择与配置5 2 5 1 1 基于t o r n a d o 的宿主机开发环境5 2 5 1 2t o r n a d o 开发环境配置5 3 5 2 事务管理器的a c 艇描述5 4 5 3 基于时间戳矢量的乐观并发控制算法实现5 8 5 4 本章小结6 2 第六章总结与展望6 3 参考文献6 5 致谢6 9 在学期间的研究成果及发表的学术论文7 0 i v 南京航空航天大学硕士学位论文 图表清单 图2 1 工作流参考模型o 1 4 图2 2 过程定义元模型1 6 图3 1 事务管理器领域模型2 4 图3 2 混合实时事务调度模型3 0 图3 3 事务管理器系统用例3 3 图3 4 事务调度器用例3 4 图3 5 事务指派活动模型3 6 图4 1 事务管理器初始类架构3 8 图4 2 事务调度精化类模型4 l 图4 3 事务调度顺序图4 2 图4 4 实时事务状态图。4 4 图4 5o c c t i 协议中事务的执行过程示例4 6 图4 6 算法错失率比较。5 0 图4 7 算法事务重启率比较。5 0 图5 1 事务管理器构件图5 6 表4 1 对象属性表4 0 表4 2 对象操作表4 0 表4 3 实验参数4 9 v 事务管理器软件构架及调度方法优化研究 注释表 w f m cw o r k f l o wm a n a g e m e n tc o a c l i t i o n b p e l b u s i n e s sp r o c e s se x e c u t i o nl a n g u a g ef o rw e bs e r v i c e s u m lu n i f o r mm o d e li n gl a n g u a g e p c cp e s s i m i s t i cc o n c u r r e n c yc o n t r o l o c c o p t i m i s t i cc o n c u r r e n c yc o n t r o l 2 p l - h p 2 p l h i g hp r i o r i t y 。 o c c - t i o c c 。t i m e s t a m pi n t e r v a l o c c d a t i d y n a m i ca d j u s t m e n to fs e r i a l i z a t i o no r d e ru s i n g t i m e s t a m pi n t e r v a ls t b st o t a lb a n d w i d t hs e r v e r a c m ea s s o ci a ti o no fc a p it a lm a r k e te lit e s 南京航空航天大学硕士学位论文 第一章绪论 1 1 研究领域的应用与发展概况 数据库技术作为计算机科学的一个分支，已经应用到科教、电力、通信、交通、金融、军 事等人类社会生活中的方方面面，数据库系统已经成为世界各国信息管理的重要基础。从数据 库系统诞生以来，数据库理论与技术发展极其迅速，其研究取得了丰硕成果，其应用日益广泛， 时至今日，它几乎无所不在。数据库技术从开始到现在一共经历了三个发展阶段：第一代是网 状、层次数据库系统，第二代是关系数据库系统，第三代是以面向对象数据模型为主要特征的 数据库系统。然而随着计算机系统硬件技术的飞跃、i n t e r n e t 和w e b 技术的发展，数据库系统 所管理的数据以及应用环境的不断变化，使得数据库技术向深度计算( d e e pc o m p u t i n g ) 和普 适计算( p e r v a s i v ec o m p u t i n g ) 两端发展。因而产生了许多研究方向和研究成果，比如：处理 多媒体数据的多媒体数据库、与w e b 技术结合的分布式数据库、支持高性能的并行数据库系统、 支持决策分析的数据仓库、嵌入式数据库系统幢。， 由于电子商务的发展和普及，使得人们日常处理的电子信息数量越来越庞大、处理的流程 越来越烦杂，大量的应用需要一种简便适当的管理数据的技术。在这些应用中，只需要存储、 读取和处理数据，应用程序自身可能并不复杂，并且应用行业背景可能多样，比如：飞机制造、 金融管理、工业流程管理等。这些应用程序开发人员也许是行业里的专家，但却不是数据库管 理方面的专家，他们不精通数据库管理系统方面的配置和管理等，而且这些应用程序也并不需 要类似予传统数据库中复杂的事务处理、系统配置和管理等功能b 儿引。这些应用程序只注重应 用本身，数据管理只是嵌入在应用程序中的一部分，嵌入式数据库技术使得这一问题的解决成 为可能。 综上所述，数据库系统在追求强人的处理能力的同时。也在向高效、移动和轻便的方向发 展，嵌入式数据库技术逐渐成为了数据库研究领域的一个重要热点。同传统数据库相比，嵌入 式数据库犹如拆卸减重后的改装车，而传统数据库则是v o l v o 旅行车 1 。传统数据库要求有足 够的i t 技术支持、专门的数据库管理人员和昂贵的系统资源，而嵌入式数据库却不需要这些额 外的东西。同传统的数据库函数库m 1 应用相比，嵌入式数据库应用能够扩展到多用户环境、能 够对繁重的事务处理进行操作、支持复杂的数据集成与恢复，而传统的数据库函数库的却不具 备类似的功能。 对于嵌入式数据库，目前国内外数据库方面的专家和学者都未曾给出一个准确的定义从 目前的研究和应用来看，嵌入式数据库是指支持移动计算或某种特定计算模式的数据管理系统、 它通常与操作系统和具体应用集成在一起运行在各种智能嵌入式设备或移动设备上l 。不难 l 事务管理器软件构架及调度方法优化研究 看出嵌入式数据库用以处理大量的、时效性强、且具有严格时序的数据、它以高可靠性、高实 时性为目标，其数据的正确性不仅依赖于逻辑结果，而且依赖于逻辑结果产生的时间。 嵌入式数据库的应用范围比较广泛，主要分为水平应用和垂直应用擒1 。水平应用即用于不 同的领域，应用核心不需要修改，只需对应用的前端或后端进行适当的定制。垂直应用与水平 应用相比，具有显著的行业特殊性，不同领域的应用差别比较大，结果表示和服务器数据库的 管理也有很大不同。另外还有其它一些专门的移动应用它们都要求提供方便、快捷的服务，如 3 g 通信中的移动嵌入式数据库应用。 由于嵌入式数据库的前景被普遍看好，各国的研究机构纷纷展开了对嵌入式数据库的研究， 各个数据库厂商也将开发嵌入式数据库作为一个重要的发展方向。目前国外方面的嵌入式数据 库产品主要有b e r k e l e yd b 、s q l i t e 、s y b a s e 公司的s q l a n y w h e r e 以及o r a c l e 公司的o r a c l e l i t e 、p i c o d b m s 、f i r e b i r d 、c l o u d s c a p e 等。b e r k e l e yd b 和s q l i t e 都是基于文件系统的数 据库，开发者需要将b e r k e l e yd b 嵌入到自己的应用程序中，两者运行在同一地址空间，避免 了与应用服务器之间的进程间通信开销，b e r k e l e yd b 不是关系数据库，因而不支持s q l 查询 语言，而是通过调用a p i 来进行操作，这些a p i 提供了查询、插入、删除等功能1 9 。s q l i t e 是 d r i c h a r d h i p p 用一个小型的c 库开发的一种强有力的嵌入式关系数据库，支持大多数的 s q l 一9 2 标准，支持事务的a c i d 性，但数据库依然是一个文件，零配置，可以和p h p 结合，包 含t c l 绑定0 。i b m 公司在d b 2 通用数据库中推出了i b md b 2s a t e l l i t e 和e v e r y p l a c e 版本， 它所提供的移动计算功能使移动办公用户获得了与企业数据保持同步的能力。o r a c l e 的o r a c l e l i t e 版本现在也可运行在低端w i n c e 、p a l m 等平台上，提供了一整套开发、提交和中央化管理 的工具，并可以和o r a c l e 的桌面数据库保持同步，可以满足移动和嵌入式应用的要求1 。s q l a n y w h e r es y b a s e 的产品，其功能全面，对数据库的访问都通过嵌入式s o l ( e m b e d d e ds o l ，e s q l ) 来编写，其生成的数据库占用内存较小，维护内存数据的持久化。它提供了数据库管理和企业 同步技术，可实现移动、工作组以及嵌入式数据库解决方案的快速开发与部署 引。 而国内的“小金灵”嵌入式数据库是人大金仓研制的面向掌上电脑、p d a 、手机等移动设备， 进行数据存储管理和移动计算的数据库产品。它在嵌入式操作系统形成了一个数据库环境，可 以进行数据增加、删除、修改和查询等功能引。o p e n b a s em i n i 是东软( n e u s o f t ) 公司开发的， 具有微小内核结构的产品。最小的应用系统可以达到5 0 k 左右。提供了对标准s q l 的支持；具 有事务处理功能：具有完善的数据同步机制，支持主动同步，支持与异构数据源的同步，实现 了冲突检测并提供了多种冲突解决方案；具有强大的系统管理：t ：具，方便实现系统的建立和管 理；提供了多种灵活的编程接口，方便嵌入式应用的开发，目前系统可以支持w i n d o w sc e 和 p a l mo s 两种主流的嵌入式操作系统。 嵌入式数据库系统同时具备实时性、主动性和嵌入式的特点，并采用了内存数据库的技术， 2 一 ! 南京航空航天大学硕士学位论文 它集成了实时数据库系统、内存数据库系统和主动数据库的处理技术。因而嵌入式数据库成为 目前研究的热点。其高可靠性、实时性、资源有限性、多样性的特点主要依赖于事务调度技术， 并发控制就是其中的一个重要方面，这也是本文研究的主要内容。 目前，对嵌入式数据库系统事务调度和并发控制的研究还比较少，但是在实时数据库的并 发控制方面，国内外已经取得了不少研究成果，主要是集中在对正确性标准的探讨和对传统的 并发控制协议进行实时性改造上。在正确性标准的研究方面，主要的理论成果有：e 一可串行化 并发控制、一可串行化并发控制、基于语义的并发控制。在对传统的并发控制机制进行改造方 面，主要的理论成果包括，基于2 p l 的实时并发控制协议，如：2 p l h p 、2 p l - p i 、2 p l - c p o i 、 2 p l - p c 等。以及基于o c c 的实时并发控制协议，如：o c c - b c 、o c c f v 、o c c - b v 、o c c s a c r i f i c e 、 o c c w a i t 、o c c w a i t x 、0 c c t i 、0 c c d a 、o c c d a t i 、o c c p d a t i 、o c c r p d a t i 等。还有基于 s c c 的并发控制协议，如：s c c 一2 8 、s c c - k s 、s c c - d c 、s c c - v w 、a v c c 、s c c - d p 等。另外还有基 于资源预报的并发控制协议、多版本并发控制协议、两级并发协议等。 以上的并发控制协议基本上是对非实时数据库系统中的并发控制协议的改进，并不能很好 的满足嵌入式数据库所要求的及时、高效。为此，还必须重新探讨嵌入式数据库的事务模型和 事务调度和并发控制。文献 1 5 提出了基于功能替代的事务模型，该模型改善了实时事务对动 态实时环境的应变能力。由于受到功能替代性的影响，事务调度分为内部调度和外部调度，提 高了系统的成功率，研究了实时事务的可调度分析，并给出了相应的内部调度策略。但是，也 给并发控制带来了新的问题。 具有功能替代性和补偿性的实时事务使得并发控制更加复杂，不仅有事务级的并发控制， 还有替代级的并发控制引 ，并且补偿也要参与并发控制，从而使得并发控制变得很复杂。所 以本文将从事务分类的角度，针对不同类型的事务采用不同的调度和并发策略，从而对嵌入式 数据库的事务调度和并发控制展开了研究。 1 2 课题研究意义和研究内容 本文的研究背景是某飞机显控系统对嵌入式数据库应用需求的预研项目。针对某飞机显控 系统对嵌入式数据库应用需求，本课题提出了一种嵌入式数据库功能划分的方案，嵌入式数据 库包括请求处理器、任务执行器、事务管理器、状态监控器、文件管理器、存储管理器等6 个 功能模块。本人主要负责嵌入式数据库事务管理器功能模块的设计与实现。本课题引入工作流 参考模型的思想来优化事务管理器模型，采用面向对象和面向构件的软件开发方法解决事务管 理器的设计与实现，重点解决混合事务调度和并发控制存在的问题。 当前嵌入式数据库研究内容新，且具有较大的技术难度，而事务管理器是嵌入式数据库的 核心功能部件。文章首先探讨了传统实时事务调度方法和并发控制协议的优缺点，并结合工作 3 事务管理器软件构架及调度方法优化研究 流参考模型的思想和面向对象的软件建模方法论，对事务管理器的领域模型进行分析。然后通 过各种优化方法对事物管理器的分析和实现进行多方面的优化，最后给出事务管理器的典型应 用实现。具体章节内容组织如下。 第一章：绪论。系统介绍嵌入式数据库领域中与本文相关的研究内容的发展概况，以及课 题的研究意义，阐述论文研究的主要内容和章节安排。 第二章：实时事务调度方法与工作流建模方法。探讨了课题研究中所用的工作流技术，以 及与本文研究工作相关的传统知识和技术，包括实时数据库技术、传统的嵌入式数据库采用的 调度方法和并发控制协议等，着重对一些主要的实时并发控制协议进行了分析和探讨。 第三章：事务管理器的领域模型。通过对事务管理器的需求描述，引入工作流参考模型的 思想给出事务管理器功能模型；并对事务管理器给出b p e l 描述。在事务管理器功能模型的基础 上，提出混合实时事务调度模型和改进的t b + 算法。最后给出事务管理器的用例模型和典型活动 模型。 第四章：事务管理器的对象体系结构。首先建立软件的类构件，并对模型进行多级优化， 提高软件构件性能，从而建立软件的行为模型。为软件建立动态行为模型，从结构特征、行为 特征、数据特征等多个方面进行设计。最后在类构件的基础上，提出改进的基于时间戳矢量的 乐观并发控制方法。 第五章：事务管理器的典型应用实现。展示了事务管理器子系统的实现过程，从开发环境 的建立，a c m e 的模板描述，并最终给出事务管理器的典型业务实现。 第六章：总结与展望。阐述了本研究工作的理论价值与实用价值，总结了文章中的收效及 创新点，并给出了下一步可能研究工作的主要方向。 1 3 课题研究的主要工作 本毕业论文从论文开题、资料的收集与学习、项目需求分析、模型研究与设计、代码编写 到论文的撰写，历时一年多。 在这一年多的时间里，本人阅读了大量的专业书籍和文章。首先从了解传统数据库事务管 理开始，从各种期刊文献中提炼出他人设计事务管理器的思想及实现的技术，逐步完善自己的 需求，对嵌入式实时数据库的事务调度和并发控制做了重点的研究。接着，从研究 ：作流技术 开始，阅读了国内外关于工作流建模的论文，理解工作流的运行过程。把：r ：作流技术运用到事 务管理器软件的研究中其后在研究和实现事务管理器软件的过程中。对面向对象方法、设计 模式和软件体系结构的深层次学习，使我加深了对软件设计的理解。 4 南京航空航天大学硕士学位论文 第二章实时事务调度方法与工作流建模方法 作为各种应用的底层系统软件，嵌入式数据库管理系统的研究与实现需要很多知识积累和 技术支持，研究工作也非常繁多，需要解决的问题复杂多样。数据库领域方面的学者和专家几 十年的杰出贡献给这个领域留下了丰富的经验和无数的成果。本章首先分析传统实时事务调度 方法和并发控制协议存在的优缺点，然后阐述了工作流建模方法，着重研究了工作流参考模型、 元过程模型和工作流描述语言b p e l 。为本文的研究内容奠定关键技术方法。 2 1 传统实时事务调度方法 简单地讲，事务调度就是如何为事务分派优先级，给出事务或任务的执行顺序，不同的系 统目标有不同的调度算法。传统的数据库追求的目标是系统吞吐量及平均响应时间，而实时数 据库系统追求的目标是单个事务时间限制的满足及全系统满足时间限制事务的比率最大。由于 实时事务调度中广泛存在不可预测因素，主要包括数据存取的动态性、磁盘i o 、事务夭折与 回滚等，导致事务的最坏情况执行时间很难估计。因此很多实时数据库采用内存数据库模型， 以消除i 0 操作所带来的影响。另一方面，实时数据库通常应用于开放环境，系统的负载变化 是不可预知的，且可能在较大范围内变化，给实时事务调度带来更多困难。 大多数实时调度策略都是基于优先级的，故首先讨论如何分派事务的优先级。 2 1 1 优先级分派策略 目前有许多给实时任务事务分派优先级的方法，下面只是分析了已经用于或被认为适用于 实时系统的几种方法的优缺点。 ( 1 ) 最早放行最优先( e r fe a r li e s tr e l e a s ef i r s t ) 。该策略将最高的优先级指派给具 有最早“放行”时间的事务。其优点就是简单，而主要缺点是它根本不考虑事务的截i = 期，只 是按“放行”时间来调度事务，显然不适用于实时数据库的事务调度。 ( 2 ) 截止期最早最优先( e d fe a r l l e s td e a d l i n ef i r s t ) 。具有最早截止期事务的优先级 最高，这是一种获得广泛应用的调度策略，其主要缺点是它让已过时或儿乎快要超过截止期的 事务获得最高优先级，而这种事务无论如何都不能满足其截j i 二期而重启，造成系统资源的浪费， 因而也不适用于实时数据库。 ( 3 ) 可达截止期最早最优先( e f d fe a r l l e s tf e a s i b l ed e a d l i n ef i r s t ) 具有最早的可 达截止期者优先级最高。如果所有的事务都具有不可达截止期，则按e d f 指派优先级。这样具 有不可达截止期的事务可不必立刻夭折。e f d f 策略克服了e d f 的缺点，是其改进版本。 5 事务管理器软件构架及调度方法优化研究 ( 4 ) 空余时间最短最优先( l s fl e a s ts l a c kf i r s t ) 。该策略将最高优先级分派给具有最 短空余时间的事务。l s f 与e d f 和e f d f 两者都不一样，它考虑了当前时间与剩余执行时间估算， 因此，随着事务的停止执行，其优先级动态上升，而若事务在执行，则因当前时间与事务已执 行的时间同步增加，故其空余时间不变，因而其优先级也不变。该策略也有类似于e d f 的缺点， 同样可限制空余时间大于或等于0 ，即只考虑可达截止期情形。 ( 5 ) 价值最高最优先( h v fh i g h e s tv a l u ef i r s t ) 。该策略让每一个事务都拥有一个价值 函数，其值最大的事务优先级最高。该策略的关键是如何合理地构造好价值函数。 ( 6 ) 价值密度最大最优先( g v d fg r e a t e s tv a l u ed e n s i t yf i r s t ) 。价值密度函数即事务 完成时的期望价值与实现该价值所需计算量的最大比者优先级最高。显然，对于期望价值一样 的事务该策略偏向较短者，因为它单位消耗时间所获得的价值更大，同h v f 策略一样，该策略 一 的问题也是如何设计价值函数的问题。 ( 7 ) 速率单调分析( r m ar a t em o n o t o n i ca n a l y s i s ) 。r m a 是一种统计性的对周期性硬实 时事务进行调度的算法，它要求预先知道数据对象和事务的执行时间，最高优先级赋予具有最 短生命周期的事务。 ( 8 ) 非精确调度( i m p r e c i s es c h e d u l i n g ) 。非精确调度放松了传统调度标准，有“滤网 法”( s i e v e ) 和“里程碑法”( m i l e s t o n e ) 两种非精确调度方法。滤网法要求系统提供多个算 法，并且提供的算法具有所需执行时间与结果的精确度呈正比的关系，即时间越长该算法结果 的精确度就越高。里程碑要求系统提供的算法是可以分割的，执行到每个分割点( 或里程碑) 都可以给出近似的结果，随着更多的分割点被执行，系统的结果也越来越精确。显然里程碑法 的算法必须是可重入的。 ( 9 ) 多标准调度( m u l t 卜c r i t e r i as c h d u l i n g ) 。多标准调度的目标可以基于多个标准， 如实时数据库中尽可能地满足时间约束和逻辑约束。 2 1 2 典型调度方法 ， 由于现实世界中实时系统的不同类型及施加于它们的要求的不同类型，使得调度算法的设 计或选择变得复杂和困难，因为这些决定了各种事务的特性，如计算时间、资源需求、重要程 - 度、先后次序关系，还有时间限制等，这些特性就是调度策略的依据。一个理想的调度策略就 是应该满足所有这些特性然而，这是很困难的。因此，在目前的研究中，许多调度算法都把 事务的关键性或者重要性当作调度算法中必须考虑的重要因素1 1 8 1 。下面从静态表驱动调度、优 先级驱动可抢占调度、动态计划式调度和动态尽力调度等几种典型的调度方法对实时事务调度 的研究现状进行简要回顾。 1 静态表驱动调度 6 南京航空航天大学硕士学位论文 这种调度方法执行静态可调度性分析，产生一种调度表，在运行时按调度表决定一个事务 何时执行。这种方法适用于周期性的事务。其主要优点是具有可预报性，即确定一个合适的调 度使所有任务都满足其定时要求、次序限制等。若只有周期性这单一的特征，则可用e d f 技术 构造一个调度表，问题是除了定期性限制外，还可以有执行次序、排他性、通信及循环等限制， 此时，解决调度是n p 完全的，大多数算法都是在寻求合适调度中采用了“分支界限”的一些 技术。 2 优先级驱动可抢占调度 该方法强调“最高优先者”。每一个事务都指派一个优先级，按优先级高低执行。在执行过 程中，若有更高优先级的事务到达，则让位给它执行。这有利于新到达的高优先级事务( 如时 间紧迫的硬实时事务) ，但一个重要问题是其他共享资源( 如数据) 也必须都是可抢占的( 这很 难) ，否则优先级高的事务仍然必须等待它所需要但被低优先级事务所占有的资源，形成所谓“优 先级颠倒”情形，甚至引起死锁。 3 动态计划式调度 它对当前事务进行动态可调度分析或可行性检验，仅当断定是可行的时候，才放行，并产 生一个事务执行计划或调度。它提供了事务可行性预报，凡放行的事务都保证会满足其时间限 制。但问题是，如何使事务的执行时间估算、资源需求、定时限制、截止期或周期、执行次序 约束等诸多因素的假定成立，从而使这“保证满足时间限制”的算法有效。可以用一种“探索 函数”来构造调度计划，然而探索的开销及动态分析的时机必须考虑，而且分析时机决定着分 析的量及其计算开销。 4 动态尽力式调度 动态尽力式调度是当前许多实时系统中使用的方法。该方法是基于事务的特征为每一种事 务计算出一个优先值。然后就按其优先级来调度多任务。其可靠性经由深入的模拟仿真并随同 记载这些事务和优先级调整来获得。该方法不进行可行性检验，系统尽最大努力去满足各事务 的截止期，但并不保证事务在执行期间不被夭折。所以，这种方法的主要缺点就是没有可预报 性。一个事务执行或者直到其截1 e 期到达或者直到完成，无论哪一种都事先不知道定时限制是 否能够满足。 经以上分析，不难看出，实时数据库中优先级分派策略一般均要考虑事务的截止期。然而 在许多实时数据库中，不仅事势具有截止期，而且数据具有时态一致性需求。而且实时数据库 越来越多的应用到开放与不可预测的环境中，特别是实时