已阅读5页,还剩61页未读, 继续免费阅读
(计算机软件与理论专业论文)实时数据库的安全性研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
摘要 摘要 实时数据库根本目标就是使满足截止时间的事物数量为最大,因而管理和 支持优先考虑时间的事务处理是非常重要的。然而,随着实时计算迅速发展 安全和时态一致性就成了许多实时应用另外必须考虑的问题。而那些实施强制 访问控制的传统多级安全数据库模式对以时间一优先的应用来说是不足够的,传 统实时数据库模式又不支持安全限制条件。使用侵入检测找出数据库中可疑行 为并辨别出异常事务是当前常用的方法。但是,当数据客体被攻击者篡改为正 好满足数据库限制条件而导致损害能够通过数据库中其他合法用户传播时,系 统不能识别出此恶意攻击而不能作出正确响应。因此,为了保证实时数据库系 统的实时性及安全性,需要提供一种新方法同时支持实时性和安全性,并且期 望使用时态一致性数据在其截止时间内事务被安全执行。 针对上述问题本文首先探讨了基于b e l l l a p a d u l a 访问限制模式的安全控 制因素,分析了安全并发控制算法,陈述了实时系统设计者应该考虑的实时性 和安全性,描述了一种规范语言允许设计者在适当的级别设定数据库的重要属 性以支持部分安全并探讨了一种自适应方法以达此目的。然后提出了“结合静态 语义分析和基于矩阵的异常事务识别方法”以识别受此异常事务影响的数据客 体和其他事务而找到隐藏在事务间的依赖关系以确保安全性,并结合实例给出 分析过程。接着利用非精确调度中任务的可选部分为强制部分的错误恢复提供 潜在的时间容余,提出了在多个错误发生时既能保证报酬最大化又能提供强制部 分恢复处理的k f t 容错优化调度形式算法”,以适当降低实时任务精确度以及 广东丁业大学工学硕士学位论文 在错误发生时提供最大利用率以保证系统的实时性与可靠性,并结合实例给出分 析过程。最后探讨了在无确定工作量和数据访问模式下为事务提供截止时间丢 失比例和时态一致性保障的q 抒方法,并通过动态调整基于反馈控制环中测量性 能差错上的系统行为,提出了实时性、安全性与时态一致性保障的实时反馈调度 体系结构,并采纳反馈控制器要求的自适应修改策略动态调整工作量以达到用 户期望的时态、安全保障的实时数据服务。 关键字:b e l l l a p a d u l a ;隐蔽通道;部分安全;非干预性原则;静态语义分析 k 错误模式的容错优化算法;反馈调度。 a b s t r a c t t h ed e c i s i v ep e r f o r m a n c eo fr e a 一t i m ed a t a b a s es y s t e m sism a x i m i z e d t h en u m b e ro ft h et r a n s a c t i o n st h a tc o m p l e t eb e f o r et h e i rd e a d l i i l e s ,t h e n m a n a g e m e n ta n dt r a n s a c t i o np r o c e s s i n gf o rr e a l t i m es y s t e m saree s s e n t i a l i ns u p p o r t i n gt i m e c r i t i c a la p p l i c a t i o n s h o w e v e r ,a sr e a l t i m es y s t e m s c o n t i n u et oe v o l v e ,s e c u r i t ya n dt e m p o r a lc o n s is t e n c yb e c o m ea n o t h e r p r o b l e mm u s tb ec o n s i d e r e di nm a n yr e a l t i m ea p p l ic a t i o n t r a d i t i o n a l m u l t i l e v e ls e c u r ed a t a b a s ei m p i e m e n t e dm a d a t o r ya c c e s sm e c h a n i s misn o t e n o u g hf o rp r i o r t i m ea p p l i c a t i o n s t r a d i t i o n a lr e a l t i m ed a t a b a s ed on o t p r o v i d es u p p o r tf o rs e c u r ec o m m i t m e n t u s i n gi n t r u s i o nd e t e c t i o nt of i n d a b n o r m a lt r a n s a c t i o ni sc o m m o nu s a g en o w a d a y s b u tt h er e s u l t i n gd a m a g e b yad a t ai t e mi sm o d i f i e db ya na t t a c k e rs u c ht h a tt h em o d i f i e dv a l l l e s a t i s f i e sd a t a b a s ec o n s t r a i n t scans p r e a dt oo t h e rp a r t so ft h ed a t a b a s e t h r o u g ho t h e rv a l i du s e r s ,u s e r si t s e l f c a n n o ti d e n t i f yt h em a l i c i o u s a c t i v i t i e sa n dr e s p o n da c c o r d i n g l y s o ,i si sn e c e s s a r yt op r e s e n tanew a p p r o a c h t o g u a r a n t e e t i m e l i n e s sa n d s e c u r i t y c o n s t r a i n t s i m u l t a n e o u s l y ,w h i l et r a n s a c t i o n scanb ep r o c e s si ni t st i m e c o n s t r a i n t u s i n gt e m p o r a lc o n s i s t e n c y d a t a t h ep a p e rf i r s td i s c u s ss e c u r ec o n t r o lf a c t o ro na c c e s sr e s t r i c t n e s s m o d e lb a s e db e l l l a p a d u l a ,a n y l a s i ss e c u r ec o n c u r r e n c ya l g o r i t h m ,a d d r e s s i s s u e st h a tr e a l t i m es y s t e m sd e s i g n e rs h o u l dc o n s i d e rf o rs u p p o r t i n g b o t h r e q u i r e m e n t s o f t i m e l i n e s sa n ds e c u r i t y ,a l s od e s c r i b ea s p e c i f i c a t i o nl a n g u a g et h a ta ll o wt h ed e s i g n e rt os p e c i f yi m p o r t a n t p r o p e r t yo ft h ed a t a b a s ea ta na p p r o p r i a t el e v e lt os u p p o r tp a r t i a l s e c u r i t ya n dd e m o n s t r a t ea n a d a p t i v ep a l i c y t oa c h i e v ei t i t m 童三些查兰三兰竺三:薹兰i :j : t h e n ,p r e s e n ta p p r o a c hw h i c hn c o r p o r a t es t a t i cs e m a n t i ca n dm a t r i xb a s e d t or e c o g n i z ea b n o r m a lt r a n s a c t i o nt of i n do u ta 1 1t r a n s a c t i o n sa n di t e m s a f f e c t e db yt h em a l i c i o u st r a n s a c t i o nb yi n e o r p o r a t i n gt h es t a r i c s e m a n t i ca n a l y s i sa n dm a t r i x b a s e dd a m a g ea s s e s s m e n t ,a n dg i v i n gc o n c r e t e a n a l y s i sp r o c e s st h r o u g hi n s t a n c e t h ep a p e ra l s op r o v i d ek - f to p t i r e a l s c h e d u li n ga l g o r i t h mw h i c huseo p t i o n a lp a r t so fi m p r e c i s et a s kt o p r o v j d ep o t e n t i a lr e d u n d a n c yt oa s s u r el i m e l i n e s sa n dr e l i a b i l i t yi nt h e p r e s e n c eo fm u l t i e r r o rt h ea p p r o a c hc a r ld e c r e a s ep r e c i s i o no fr e a l t i m e t a s ka n dp r o v i d eam a x i m i z e u t i l i t yf a u l t t o l e r a n to p t i m a ls c h e d u l i n gf o r e r r o r r e c o v e r yo fm a n d a t o r yp a r t s ,a n dp r o p o s eaf o r m a lk - f a u l tt o l e r a n t o p t i m a ls c h e d u l i n ga l g o r i t h mw h i c hcang u a r a n t e em a x i m i z e r e w a r da n d p r o v i d er e c o v e r yo p e r a t i o nf o rm a n d a t o r ys i m u l t a n e o u s ,a n dg i v ec o n c r e t e a n a l y s i sp r o c e s s t h r o u g hi n s t a n c e f i n a l l y ,t h ep a p e rp r e s e n ta nd a t a f r e s h n e s sa n ds e c u r i t yf e e d b a c kc o n t r o la r c h i t e c t u r ew h i c hu s e sq o s m a n a g e m e n tt og u a r a n t e e so nt e m p o r a la n ds e c u r e ,a n dd i s c u s so h 伊s c h e m e p r o v i d i n gg u a r a n t e e sf o rt r a n s a c t i o n so nd e a d li n em i s sr a t i oa n dt e m p o r a l c o n s i s t e n c ye v e ni nt h ep r e s e n c eo fu n p r e d i c t a b l ew o r k l o a d sa n du n k n o w n d a t aa c c e s sp a t t e r n s b ya d j u s t i n gs y s t e ma c t i o no nm e a s u r e dp e r f o r m a n c e e r r o r ,a d o p t i n ga d a p t e du p d a t ep o l i c yw h i c ha d j u s tw o r k l o a dt oa c h i e v e d e s i r a b l er e a l t i m ed a t as e r v i c eo nt e m p o r a la n ds e c u r eg u a r a n t e e s k e y w o r d s :b e l l _ l a p a d u l a ;c o n v e r tc h a n n e l ;p a r t i a ls e c u r e :n o n - i n t e r f e n c e s t a t i cs e m a t i ca n a l y s i s ;k - f to p t i m a ls c h e d u l i n ga l g o r i t h m :f e e d b a c k s c h d u li n g i v 第一章绪论 第一章绪论 1 1 实时数据库的发展与现状 实时数据库就是其数据和事务都有显式定时限制的数据库,系统的正确性f i 仅依赖于事务的逻辑结果,而且依赖于该逻辑结果所产生的时间。实时数据库足 数据库系统发展的一个分支,它适用于处理不断更新的快速变化的数据及具有时 间限制的事务处理。实时数据库技术是实时系统和数据库技术相结合的产物,研 究人员希望利用数据库技术来解决实时系统中的数据管理问题,同时利用实时技 术为实时数据库提供时间驱动调度和资源分配算法。然而,实时数据库并非是两 者在概念、结构和方法上的简单集成。需要针对不同的应用需求应用特点,对实 时数据模型、实时事务调度与资源分配策略、实时数据查询语言、实时数据通信 等大量问题作深入的理论研究m 。 实时数据库系统最早出现在1 9 8 8 年3 月的a c ms i g m o dr e c o r d 的一期专刊 中。这标志着实时领域与数据库领域的融合,标志着实时数据库这个新兴研究领 域的确立。随后,一个成熟的研究群体逐渐出现,尤其是美国、英国、德国、瑞 典等国对r t d b 的研究非常关注,此后,出现了大批有关实时数据库方面的论文 和原型系统。现已有许多成功的实验系统,有的甚至已商品化,典型的有h i p a c 、 z i pr t d b m s 等系统。而国内的研究起步稍晚,基本上是在8 0 年代末、9 0 年 代初才开始,但发展很快,目前已有成功的实验系统,但尚未形成正式产品。 近年来,r t d b 已发展为现代数据库研究的主要方向之一,受到了数据库界 和实时系统界的极大关注。然而,随着计算领域的迅速扩张,航空业、国防、工 业自动化、商业信息以及交通控制等系统所保存的大量信息需要被不同安全权限 的多个用户共享,以及制造业、w e b 服务、电子商务等对实时数据服务要求的增 加都需要实时数据库支持优先考虑安全的策略。在这些应用中,事务和数据客体 有不同的安全级别,对非法的直接1 4 接访问提供防卫措旌对实时数据库来说是 广东工业大学t 学硕+ 学位论文 非常关键的。并且,事务必须在其截止时间内完成提交。然而由于实时事务限制 性条件,在没有统一访问模式的w e b 一服务和传感器网络等系统中并不能准确预 测数据库工作量。因此,瞬间过载发生时就造成截止时间丢失和时态违背。对一 些应用来说,即使非预测工作量 h 现,人们仍期望从一个事务到另一事务的服务 质量无明显改变。同时这些应用系统所保存的大量信息需要被不同安全权限的多 个用户共享,安全就成了实时应用另一个必须考虑的问题。因此,实时数据库的 数据库安全模式必须满足时间和安全限制条件。 而那些实旌强制访问控制的传统多级安全数据库模式对以时间一优先的应用 来说是不足够的,而传统的实时数据库模式又不支持安全限制条件。因此,在实 时数据库中,既保证信息安全,在实时性能没有明显降低的情况下又满足其时间 限制条件在现在实时应用中是非常重要的。 使用侵入检测找出数据库中可疑行为并辨别出异常事务是当前常用的方法。 侵入检测是网络安全一个活跃而重要的研究领域,侵入检测系统作为防御组件能 够对侵入提供全面的防护措施。其目的就是找到提交给管理系统的恶意事务。但 是,现今许多基于误用的签字检测和基于反常的非签字检测都是针对操作系统 级,系统管理级的侵入检测是非常有限的,而且还不能保证对所有异常行为作出 正确响应。因此,当数据客体被攻击者篡改为正好满足数据库限制条件而导致损 害能够通过数据库中其他合法用户传播时,系统不能识别出此恶意攻击而不能作 出正确响应。因此,为了保证实时数据库系统的实时性及安全性,需要提供一种 新方法同时支持实时性和安全性,并且期望使用时态一致性数据在其截止时间内 事务被安全执行。 1 2 国内外研究动态 在2 0 0 2 年i n k a n g ,s h s o n 和j a s t a n k o v i c 出版的“s e c u r er e a l 一t i m e t r a n s a c t i o np r o c e s s i n gw i t ht i m e l i n e s sg u a r a n t e e s ”中陈述了固实时数据 库的安全性,安全作为一个正确性标准,并把截止时间丢失的事务数量作为性能 尺度来衡量。此文检查了两阶段锁定( 2 p l ) 优先级算法,乐观的并发控制算法 第一章绪论 j _ e e _ 目自e ! 口= = 目e ! = ! | | = 自口| j = = = j | ! ! e = j j ,| = _ = = | = = j _ t = j e 目= = = _ _ 目= ,! 日= 詈i i 以及依赖于相同或不同安全级别事务的并发控制方法d a ( d u a la p p r o a c h ) 。但 是,在确保没有降低安全性能的前提下使丢失的截止时间事务保持在最小的同 时,并没有对丢失的截止时间和安全进行平衡。d a 方法根据事务的安全级别采 用不同的并发控制算法,而本文的方法可以对相同或不同的安全级别事务进行处 理。在1 9 9 2 年j g o g u e n 和j m e s e g u e r 发表的“s e c u r i t y p o l i c y a n ds e c u r i t y m o d e ls ”以及1 9 9 2 年m 1 t s u 和b z h a n g 发表的“p e r f o r m a n c ee v a l u a t i o no f c a u t i o u sw a i t i n g ”针对没有给定期望的截止时间丢失百分比的情况下提出丫 平衡安全和实时方法,通过动态调整作者定义的安全比率来达到期望的截止时间 丢失比率。我们的方法也使用系统安全容忍级别,但是此系统安全容忍级别时预 先设定好的一个常量值。根据系统安全容忍级别来决定需要牺牲可以满足截止时 间的事务。2 0 0 0 年s h s o n ,r r m u k k a m a l a 和r d a v i d 发表的“i n t e g r a t i n g s e c u r i t ya n dr e a l t i m er e q u i r e m e n tu s i n g sc o v e r tc h a n n e lc a p a c it y ”使 用一个s 2 p l 方法在提高实时性的前提下允许安全的部分违背。为了不会因为拥 有锁的高级别事务阻塞低访问级别事务而采用“虚拟锁”。为了达到期望的实时 性及安全性,可以在需要的时候允许潜在的冲突违背而采用部分安全策略。并采 用b e l l l a p a d u l a 安全模式来定义在两个确定安全级别之间安全需求允许的部 分安全,以及为了允许部分安全而要模糊安全级别之间的界限。随着系统性能的 下降,需要模糊更多的界限而允许更多的安全违背以减少安全冲突的数量而使系 统性能得到提高。是否维持安全或优先级取决于系统。如果系统要求安全维持而 不管冲突事务的截止时间,那么就朝着有利于安全方面解决冲突。如果系统折衷 安全和优先级的性能,那么目标就是在截止时间丢失百分比没有明显增加的情况 下,尽可能的维持系统安全。q u a z in a h m e d 和s u s a nv v r b s k y 发表的 “m a i n t a i n i n gs e c u r i t ya n dt i m e l i n e s si nr e a l t i m ed a t a b a s es y s t e m s ” 提出了保证特殊系统的安全性与实时性的安全2 p l h p 算法以及安全性和优先级 融合的安全o p t 算法。国内从事实时数据库安全性研究的机构主要有:国防科技 大学计算杌系、中国科学院软件所,成都电子科技大学。 广东1 业大学工学硕士学位论文 1 3研究的目的及意义 随着制造业、w e b 服务、电子商务等对实时数据服务要求的增加以及军事组 织、政府部门对信息访问做了严格的限制。人们期望使用时态。致性数据在其截 止时间内事务被安全执行。然而由于高服务要求和实时事务紧迫的时间时态一 直性限制条件,在没有统一访问模式的w e b 服务和传感器网络等系统中并不能 准确预测数据库工作量。因此,实时数据库经常发生过载。结果,瞬间过载发生 时就造成截止时间丢失和时态违背,例如、在线股票交易和( a g i 】e ) 制造事务 应该在他们的截止时间内使用刷新数据在当前市场条件或处理状态改变之前被 处理。在这些应用中,截止时间的丢失或时态的非一直性会导致利润的损失或产 生质量的下降。对一些应用来说,即使非预测工作量出现,人们仍期望从“个事 务到另一事务的服务质量无明显改变。不幸的是,实时性和数据一直性需求是相 互冲突的。同时这些应用系统所保存的大量信息需要被不同安全权限的多个用户 共享,安全就成了实时应用另一个必须考虑的问题。因此,实时数据库的数据库 安全模式必须满足时间和安全限制条件。 因而在实时数据库中,除了确保事务截止时间丢失比例的最小化,满足安全 限制条件以及提供数据库数据和持续改变的外部环境间的时态一直性是非常必 要的。传统的多级安全数据库模式对于优先考虑时间的应用是不足够的,而传统 的实时数据库模式又不支持安全限制条件。基于这个目的,我们提出动态平衡方 案以平衡用户事务和灵活行动中的修改工作量,目标是把安全与实时系统结合起 来,这样不仅可以提供实时保障,同时在不降低实时性能的前提下又可以满足实 时数据库要求的安全限制条件。 1 4 本课题研究的思路和主要内容 本课题研究的思路是:首先介绍了数据库和实时事务的关系,实时事务的种 类,实时数据库的目标以及并发控制算法;然后针对实时数据库内的隐蔽通道问 题对多级安全实时数据库、安全控制因素、隐蔽通道属性、非干预性原则以及安 全并发控制算法进行了研究。并且提出了为保障安全的“结合静态语义和基于矩 4 第一章绪论 阵的异常事务识别方法”。然后研究了涉及实时性能的部分安全概念、实时性j 安全性保障规范语言、实时与安全需求以及实时数据库中实时需求和安全需求的 融合,提出了“基于非精确计算的多错误模式f 的容错优化调度算法”以保证 系统的实时性。最后探讨了在无确定工作量和数据访问模式下为事务提供截止时 问丢失比例和时态一致性保障的q m f 方法,提出了使用服务质量管理的确保时态 与安全的时态、安全实时反馈控制体系结构。 本课题研究的主要内容: ( 1 ) 实时数据库的并发控制算法; ( 2 ) 针对实时数据库隐蔽通道问题的安全性策略以及针对恶意事务的“结合静态 语义和基于矩阵的异常事务识别方法”; ( 3 ) 在保障安全的前提下提供实时保障的策略,并且提出了“基于非精确计算的 多错误模式下的容错优化调度算法”; ( 4 ) 时态性与安全性融合的实时数据库的服务质量管理方法; 1 5 论文的组织 本文的内容安排如下: 第一章本章作者查阅了大量最新的中外文献,介绍了实时数据库的发展和 现状,实时数据库的起源,分析了实时数据库与传统数据库的区别,以及现阶段 实时数据库的运用领域,存在的困难和问题,目前国内外的研究动态,接着介绍 了本课题研究目的和意义,最后介绍了本课题研究的思路和主要内容和本文的组 织。 第_ 二章本章主要介绍数据库和实时事务的关系,实时事务的种类,实时数 据库的概念,目标以及实时数据库的并发控制算法。 第三章本章重点研究了针对隐蔽通道问题而采取的安全性策略涉及的多级 安全实时数据库、安全控制因素、隐蔽通道属性、非干预性原则以及安全并发控 制算法进行了研究。 第四章本章主要研究了使用静态语义分析所产的读、写前及写后集合之前 5 广东工业大学工学硕士学位论文 的关系采确定异常事务,并使用基于矩阵的损失评估方法识别受此异常事务的数 据客体和其他事务而找到隐藏在事务间的依赖关系。并且提出了为保障安全的 “结合静态语义和基于矩阵的异常事务识别方法”。 第五章本章研究了涉及实时性能的部分安全概念、实时性与安全性保障规 范语言、实时与安全需求以及实时数据库中实时需求和安全需求的融合。 第六章本章阐述了i ,c t ( ) 和l c t ( ) 函数的计算方法,探讨了在k 错误模 式及时间限制条件下的k f t 优化调度的属性、产生规则、产生过程以及调度是 否为k i 叩优化的判定方法,分析了此模式下非精确任务的容错优化调度的产生 方法,在此基础上提出了“基于非精确计算的多错误模式下的容错优化调度算法” 以保证系统的实时性,并通过实例给出了具体分析过程。 第七章本章探讨了在无确定工作量和数据访问模式下为事务提供截止时间 丢失比例和时态一致性保障的q m f 方法,并通过动态调整基于反馈控制环中测量 性能差错上的系统行为,采纳反馈控制器要求的自适应修改策略动态调整工作量 以达到用户期望的时态、安全保障的实时数据服务。提出了使用服务质量管理的 确保时态与安全的时态、安全实时反馈控制体系结构。 最后是本文的结论。 第二章实时数据库的并发控制算法 第二章实时数据库的并发控制算法w m t s 实时数据库是提供时间约束的数据库操作的一种实时系统,它管理有时问约 束的数据和事务。它追求的是数据的时态一致性,时间约束条件以及时效性。它 们在生产,航空电子,控制与通信以及程控股票交易等系统中起着很重要的作用。 而传统数据库通过用对每个数据事务和操作的连续性来做到保持逻辑一致性它 强调的是数据一致性,吞吐量和响应时间以及正确性。而一个实时数据库系统还 需要实现时态致性的约束条件。它追求的是数据时态一致性,时间约束条件以 及时效性。因此,实时数据库系统是这样一个数据库系统:在满足传统数据库系 统的一致性需求外,系统中事务还必须有明确的时间限定条件。 2 1 数据库和实时系统n 优先考虑时间调度和并发控制作为实时数据库系统调度操作的两个组成部 分。在对优先考虑时间调度和并发控制得到很好的发展和理解时,对于他们的融 合却只有有限的认识。尽管最近这个问题得到积极的研究,但是这种被推荐的解 决方法仍然处于初级阶段。把数据库和实时系统融合为一个整体时主要的问题 是在开发过程中,对于来源于不同客观实体和不兼容的假定下缺乏协调性。 通常实时系统设计者和研究者更可能依据任务而不是事务考虑问题,然而, 任务和事务是不同的计算概念,他们的类似和区别影响他们怎样进行设计、实施 和控制。在许多任务被设计成非终止的同时所有的事务被设计成终止,另外事务 也是一个恢复的单元,而任务不是。任务的执行行为是可预报的,因而它的执行 时间可以算出,但是一个事务的执行行为是动态的,因为它的值是根据数据库中 的值得到的,因而精确的预测出它的执行时间是困难的。任务只等待另一个任务, 同时事务也等待i o 事件的完成。 另一个不兼容假定的例子是数据存取的时序安排。在实时计算机系统,传 统的调度资源是处理器,内存和磁盘;合作调度这些硬件资源去满足系统的实时 性能目标。在实时数据库系统,除了标准的物理资源,根据存储在数据库中的数 7 广东工业人学工学硕上学位论文 据目标而形成的一系列逻辑资源,也是根据实时性能目标对其进行调度的。然而, 数据是另类资源,考虑调度时要把它同硬件资源的调度区别对待。硬件资源的服 务次序一般不会影响到服务的正确性,与硬件资源不同的是,库中形成一组逻辑 资源的数据目标也进行调度。然而,数据是种独特的资源,需要把它的调度同 硬件资源的调度区分开来。与硬件资源的服务。般不会影响到服务的正确性,与 此不同的是,逻辑资源的正确性是和事务访问数据目标的顺序有关。 数据是逻辑资源,因此调度策略最为关心的问题是利用这样一个逻辑资源进 行并发调度的事务的数量而不是数据目标本身。然而,像c p u 和磁盘等硬件资 源,在一个时间点只对单一的请求服务。当重启造成它们已经获得的系统资源丢 失时,那么从存储数据目标来的事务是可以抢占的。相反,对使用硬件资源的事 务来说,对他们的抢占,只是造成了它的执行时间的一个延迟而已。最后,已经 确定的数据目标在某种意义上来讲不能被另一个数据目标代替。而硬件资源从类 似服务器得到的服务通常是具有相同意义的。基于上述的所以原因,硬件资源使 用的调度策略不会直接应用到数据存储调度。 2 2 实时事务m m , 事务是一组顺序读,写操作。许多原因都可以造成事务的终止,因而,事务 执行的所有初始修改都被认为是暂时性的,只有当此事务通过了它的提交时间我 们才认为此事务的修改是永久性的。事务是根据它的优先级访问处理器的。系统 性能尺度的优化也是根据优先级的设定来衡量的,最明显的性能尺度是事务的截 止时间。 2 2 1 事务的终止 事务有2 种类型的终止:期满终止和非期满终止 被期满终止的事务在终止后不被重启。例如,可能存在数学错误,或者事务被延 迟了很长一段时间使得它的值降为零,用户决定取消此事务。相反的,当一个事 务被非期满终止时,此事务被重启。由于此事务和其他高优先级事务存在数据冲 第一章实时数捌库的并发控制算法 突,此事务被终l 。然而,对于一个接受多次非期满终止的事务来说,它的值最 终有可能降为零时,那么此事务就变为期满终止的事务。 2 2 2 事务的类型 根据错过它的截止时间所造成的后果分为:硬截止时间事务;软截止时间事 务;固截止时间事务。 硬截止时间事务错过它的截止时间会造成灾难性的后果;软截止时间事务错 过截止时间会导致性能的下降但不会造成灾难性的后果。在错过截止时间后,事 务的值减小;固截止时间事务错过截止时间会导致性能的下降但不会造成灾难性 的后果。在错过截止时间后,事务的值马上变为零。 软和固截止时间事务的区别在于他们对待迟来任务的态度,软截止时间事务 在它的截止时间之后完成时,对系统来说只是它的值减小,而固截止时间事务在 它的截止时间之后完成时,对于系统来说,它的值降到0 ,有时甚至会产生危害 的后果。所以,迟缓的事务永远都是被中止或丢弃”。 2 3 实时数据库n 传统的数据库系统旨在处理永久、稳定的数据,强调维护数据的完整性、 一致性,其性能目标是高的系统吞吐景和低的代价,并不考虑有关数据及其处理 的定时限制,所以,传统的数据库管理系统( d b m s ) 不能满足这种实时应用的需要。 而传统的实时系统( r t s ) 虽然支持任务的定时限制,但它针对的是结构与关系很 简单、稳定不变和可预报的数据,不涉及维护大量共享数据及它们的完整性和一 致性,尤其是时间一致性。 实时数据库与基于传统数据库技术的数据库在原理、实现技术、功能和系 统性能方面有很大的不同。但实时数据库并不是数据库技术和实时系统两者的简 单结合,它在概念、理论、技术、方法和机制方面具备自身特点。实时数据库, 其数据和事务都有显式定时限制,系统的正确性不仅依赖于事务的逻辑结果,而 且依赖于该逻辑结果所产生的时间。实时处理过程非常复杂,因为除了满足传统 数据库系统的一致性需求外,实时数据库系统的时间限制是正确性标准的不可缺 广东工业大学t 学硕u 上学位论文 少的一个完整部分。 2 4 实时数据库的性能目标 实时数据库系统的性能目标就是使错过截止时间的事务数目减到最少9 。根 据各自的截止时间确定其优先级,因此,事务完成的早晚并不重要,而是否在它 的截止时间之前才是最重要的。由于目标的不同,传统数据库系统的性能指标并 不合适实时数据库系统。 2 5 实时数据库的并发控制算法m m 传统数据库的并发控制并不适合实时数据库。因为其除了要求数据一致性, 还必须满足时间限制条件。许多依赖于事务阻塞或重启的实时并发控制方法使用 优先考虑时间来迎合事务时间限制条件。但由于时间的不可预铡,阻塞或重启都 不是很恰当。此外实时数据库性能目标与传统性能目标有着根本的不同,它是使 截止时间内完成事务的数量为最大而不是要求并发执行的事务数量保持为最大。 虽然实时数据库的实时性能取决于好几个因素,但对于一个给定的系统配置,决 定实时性能的最基本因素是对数据存储进行调度的并发控制协议。此协议通过解 决非串行并发事务数据存储而使处于冲突中的事务达到串行性而保持数据库的 完整性。但是,并不是每个可串行化调度都可以接受,那些未满足事务时间需求 的调度就不被接受。因此,对于能否在它的截止时间之前完成此策略起了直接作 用。 如果把截止时间作为事务唯一参数,实时数据库系统的性能目标就是尽量把 错过截止时间的事务数量保持在最小。因此事务的完成时间相对于其截止时间的 早晚程度与其是否在其截止时间内完成对其本身并不重要。实时数据库事务优先 级的采用下面2 种方法:最早截止时间优先( e a r l i e s td e a d l i n ef i r s t ) ,最小 松弛时间优先( m i n i m u ms l a c kf i r s t ) 。 1 0 薹,二耋童壁鍪耋耋墼茎垒耋型茎鎏 2 5 1 并发控制方法【s 1 6 1 t ,m ” 25 1 1 悲观的并发控制算法p c c ( p e s s i m is t i cc o n c u rr e n c yc o n t r o i ) 2 阶段锁定是传统数据库中最大众化的悲观并发控制协议。使用此方法, 事务在获得锁之前禁止访问数据库目标。事务执行由目标事务获得锁并进行执 行和目标事务释放拥有的锁2 部分组成。当t r 请求锁时,而此锁i f 被处于冲突 的事务t 。占有,t l 被阻塞,等待t 。释放锁之后才能获得锁执行操作。实时数 据库系统提出的许多锁协议都来源于优先级中止和优先级继承。优先级中止是 当优先级发生倒置时,低优先级事务被中止。而优先级继承允许低优先级事务 继承阻塞事务队列中具有最高优先级事务的优先级而继续执行。 1 ) 优先级中止( p ri o ri t ya b o r t ) : 此算法通过结合确保高优先级事务不会被低优先级事务延迟的冲突解决 方案对基本两阶段锁定进行修改而形成。使用此方法,高优先级事务不会看到 低优先级事务,增加了紧急事务满足其截止时间的机会。但此方法的一个缺点 就是低优先级事务可以被后来丢弃的高优先级事务重启。这种浪费资源的重启 造成性能下降。 2 ) 优先级继承( p r i o r i t yi n h e r i t a n c e ) : 优先级继承考虑的是实际冲突因而灵活的解决了优先级倒置问题。在此协 议下,当请求事务被占有锁的低优先级事务阻塞时,占有锁的低优先级事务继 承被阻塞的高优先级事务的优先级继续执行直到它的终止并释放锁。由于增加 了优先级,占有锁的事务可以尽快完成,减少了被阻塞的高优先级事务等待时 间。 3 ) 有条件的优先级继承( c o n d i t i o n a lp r i o r i t yin h e r i t a h o e ) : 这种协议力图减少p i 的组塞时间和p a 的终止率。当事务t 被低优先级事 务t 组塞时,如果低优先级事务的执行接近结束,此低优先级事务就继承高 1 l 广东工业人学工学硕十学位论文 优先级事务的优先级而避免了中止和资源浪费。否则,低优先级事务被中止, 避免了高优先级事务长时间等待,此协议假设预先知道事务长度。 4 ) 优先级向上取整运算协议( p ri o rj t yc e ii n gp r o t o c o i ) : 优先级向上取整运算协议是另外一个基于锁的并发控制协议。它是从消除 了p i 中的死锁和限定高优先级事务的阻塞时问不超过一个事务的执行时间的 优先级继承掷议扩展来的。此协议定义为在一个客体上可能拥有锁的虽高优先 级事务的优先级,只处理已经存在的冲突。为了获得客体上的锁,其要求事务 t 的优先级必须大于在客体的向上取整优先级。否则,事务t 被在此客体上猢 有锁的最大向上取整的优先级事务组塞。 2 5 1 2 乐观的并发控制o c c ( o p t i m is t i cc o n c u rr e n c yc o n tr o i ) 乐观并发控制认为任何两个并发事务请求同一数据库i + 1 标的概率很低。事 务的所有操作在它请求时就可以执行。事务被允许提交前必须通过后向或前向 校验测试以检查那些正在测试的事务和已经开始执行提交的事务之间是否存 在冲突。在后向校验中,把校验事务t u 读集合和提交事务t r 写集合进行比较, 如非空重启t u 。在前向校验中,把校验事务t 。写集合与任何激活但未提交事 务的读集合进行比较。如存在非空交集则所有的提交事务可能会发生顺序错 误。此时可以选择中止提交事务t 。或者和t 。存在冲突的所有其他事务。 1 ) 基于广播提交的乐观共发控制o c c - b c ( o c cw i t hb r o a d c a s tc o m m i t ) : 这是一种使用了变种的前向校验即基于广播提交的乐观并发控制,此方法 利用优先级解决事务问冲突。当查出冲突时就对冲突事务的优先级进行检查。 如果提交事务优先级高过所有与它产生冲突的事务优先级,执行事务被中止。 如果正处于冲突的执行事务有更高优先级,提交事务等待直到执行事务提交。 2 ) w i t - 5 0 : 在此方法中,除了等待方案,还结合了优先级来提高解决冲突的决定方案。 如果和提交事务t 存在冲突的一半或以上的事务优先级高于此提交事务,提交 第二章实时数据库的并发控制算法 事务t 则必须等到高优先级事务的完成。否则t 被提交,同时冲突事务被终止。 当事务t 等待时,由于拥有高优先级的处于冲突的一个事务可能被提交,因而 t 可能被重启。 3 ) 时间戳t 0 ( t i m e s t a m po r d e r in g ) : 给每个事务在其启动时间分配+ 时间戳,事务按照时间戳次序顺序提交并 执行。不按此次序进行的任何读、写操作都会造成此请求事务的中止。 4 ) 多版本的并发控制m c c ( m u i t i v e r s i o nc o n c u rr e n c yc e n t r e l ) : 与给定写的通常语义的锁定修改和乐观的延迟修改相比较而言,多版本的并 发控制把写操作作为数据库客体的一个新的版本的产生。时间戳作为读请求的恰 当的返回版本。保持多版本数据客体的好处是不必增加并发控制的花费,因为此 版本在恢复算法中需要用到。 5 ) 混合算法( h y b r i da i g o r i t h m ) : 混合算法是结合了时间戳和乐观技术的算法。其充分利用了广播提交并发控 制的非串行化执行去检查和解决冲突。使用动态时间戳分配时间戳时间段。如果 在事务校验段时发现数据冲突,由事务的优先级决定哪个事务被终止。 25 1 3 可推测的并发控制s c c ( s p e c u ia t i v ec o n o u rr e n c yc e n t r e i ) 【3 】c b 】 s c c 是使用冗余以确保串行化执行以尽可能早的发现冲突而采取相应措施以 增加在严格时间限制条件下满足时间需求可能性的一种新的并发控制方法。s c c 采用和p c c 类似的方法即尽可能早的查出潜在的有害冲突,同时也采纳了o c c 的 方法一为了避免那些可能造成他们错过时间限定的不必要的延迟而使产生冲突 的事务并发执行。由于依靠冗余执行,设有足够的系统资源可供本文介绍的s c c 算法使用。 广东工业人学工学硕士学位论文 基于次序的s c c 算法( s c c o b ) : 各种并发控制算法在冲突被查出的时间上和他们选择解决冲突的方式上基 本上都是不同的。只要冲突发生,p c c 就使用锁协议来检奄冲突并使用阻塞解 决冲突。o c c 协议在事务提交时检查冲突并使用重启解决冲突。而s c c 协议事 务间的冲突“发生就查出并使用可推测的冗余计算解决冲突。 图2 1 基本o c
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年考官培训考核模拟试题及参考答案
- 2026年木地板制造行业市场调查研究报告及未来五至十年垂直整合与横向拓展
- 财务报表审计实务操作模拟试卷及答案
- 营养师食品营养标签解读与运用模拟试卷及答案
- 高处作业安全操作证基础知识模拟试题及答案
- 2026年河北中模拟试卷带答案
- 2026年驾照电脑试题模拟测试题(含答案)
- 2026年公务员考试行测冲刺卷(含答案)
- 价格师考试价格实务模拟试卷及答案
- 中医方剂学核心考点预测试卷及答案
- 2025成都农业科技职业学院教师招聘考试题目及答案
- 2026年中国出口信用保险公司招聘笔试大纲及备考指南
- 中小学以体育强化为核心落实“健康第一”教育理念实施方案
- 间羟胺药物课件
- 2026年深泽县辅警招聘考试备考题库必考题
- 江苏省南京市玄武区2025-2026学年九年级上学期期中历史试卷(含答案)
- 上海交易集团秋招面笔试题及答案
- 整县屋顶分布式光伏项目绿色施工方案
- 手术室精益管理汇报
- T/CAR 10-2022食品速冻装置隧道式速冻装置
- 景区团建合同协议书范本
评论
0/150
提交评论