2022年实时数据库系统之实时事务调度算法宣贯 .pdf
《2022年实时数据库系统之实时事务调度算法宣贯 .pdf》由会员分享,可在线阅读,更多相关《2022年实时数据库系统之实时事务调度算法宣贯 .pdf(6页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、实时数据库系统之实时事务调度算法实时数据库技术是实时系统和数据库技术相结合的产物,研究人员希望利用数据库技术来解决实时系统中的数据管理问题,同时利用实时技术为实时数据库提供时间驱动调度和资源分配算法。然而,实时数据库并非是两者在概念、结构和方法上的简单集成。需要针对不同的应用需求和应用特点,对实时数据模型、实时事务调度与资源分配策略、实时数据查询语言、实时数据通信等大量问题作深入的理论研究。实时事务调度策略定义如何为事务分配优先级,而调度的最重要目标是保证尽可能多的事务能够满足截止期。大部分实时任务调度算法并不能直接用于调度实时事务,原因在于:这些算法通常要求任务到达时间、截止期与最坏情况执行
2、时间与关键性等参数是已知的。而实时事务调度中广泛存在的不可预测因素,主要包括数据存取的动态性、磁盘I/O、事务夭折与回滚等, 导致事务的最坏情况执行时间很难估计。因此, 很多实时数据库采用主内存数据库模型,以消除I/O 操作所带来的影响。另一方面,实时数据库通常应用于开放环境,系统的负载变化是不可预知的且可能在较大范围内变化,给实时事务调度带来更多的困难。Abbott 等ABB88最先基于一个内存驻留的实时数据库模型,综合研究了FCFS ( First Come First Serve)、EDF(Earliest Deadline First )与 LSF( Least Slack First
3、)三种优先级分配方法以及串行执行 (Serial Execution )、2PL-HP(2PL-High Priority )与 2PL-CR(2PL-Conditional Restart)三种并发控制协议,仿真实验结果表明:就调度算法而言,EDF 算法表现出最好的性能; 并发控制中2PL-CR 表现出最好的性能,但是其性能很大程度地受到事务估计执行时间精度的影响。进一步地,Abbott 等ABB92也在磁盘驻留的实时数据库模型之上对上面的算法与协议进行了测试,结果表明LSF 优先级分配算法表现出最好的性能,而2PL-WP 协议与 LSF 或者 EDF 配合使用都优于2PL-HP 协议,并且
4、采用优先级驱动的I/O 调度相对于FIFO方式具有很大的性能改进。无论如何,当系统负载采用步进方式递增时,EDF 算法是性能最好的调度算法,而2PL-HP 协议表现最佳。最后,Abbott 等指出 CPU 调度算法是实时事务调度处理中最重要的策略,而在并发控制中使用优先级信息解决数据冲突有利于改进系统的性能。Huang 等HUA89基于一个实时数据库测试床RT-CARAT ,针对实时事务调度算法与冲突解决策略进行了实验研究,结果表明: 实时事务调度算法必须综合考虑事务的截止期与关键性(或者价值) ,并且在冲突解决策略中考虑这些信息能够改进系统性能;事务截止期与关键性的分布情况也在很大程度上影响
5、系统的性能。因此, 在随后的研究中,许多算法都把事务的关键性或者重要性看作调度算法中必须考虑的重要因素。上个世纪九十年代,实时事务调度的研究基本上是从基于价值的事务调度、基于准入控制的事务调度、 满足时态一致性的事务调度等几个方面发展,并且进一步地在调度中考虑不同的事务模型以及过载消解方法。最近几年,反馈控制方法也被应用到实时事务的调度中,名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 6 页 - - - - - - - - - 并取得了相当多的研究成果。另一方面,混合事
6、务的也得到了越来越多的研究。1 基于价值的事务调度在许多现实的应用中,不同的事务具有不同的价值或者不同的关键程度。在实时数据库领域,先前的一些研究也已经考虑调度具有不同价值的事务,而系统的主要性能指标通常也转换为最大化系统的实现价值。最初,Huang 等HUA89使用一个实时数据库测试床RT-CARAT评估了 MCF( Most Critical First ) 、EDF 与 CDF(Criticalness-Deadline First )三种调度算法的性能,其中CDF 算法中事务的优先级按照(相对截止期关键性)进行分配,结果表明综合考虑事务的截止期与关键性在很大上改进了系统的综合性能。Ha
7、ritsa等HAR91,HAR93给出了不同的基于价值的优先级分配算法:Highest Value First(HVF ) 、Value-Inflated Deadline ( VD ) 、Value-Inflated Relative Deadline (VRD )以及桶算法( BA:Bucket Algorithm ) ,其中 VD 算法中事务的优先级按照(截止期关键性)进行分配, VRD 算法等同于 CDF算法。实验结果表明,EDF算法在负载较轻时表现最佳,HVF 与VD 算法在较高负载下性能较好,而VRD 算法表现出最好的综合性能。不过, 通过对 BA算法的性能测试表明,没有一个固定的
8、截止期-价值的折衷能够适用于所有负载情况,根据负载情况合理选择参数能够产生最好的性能。此外,研究也表明了在采用综合截止期与价值的调度算法进行固定截止期事务调度时OCC-Wait协议的性能也优于2PL-HP协议。Tseng等TSE95提出了另一种基于价值的调度算法HRF(Highest Reward First) ,其中事务的优先级按照(价值剩余执行时间)进行分配,因此这种优先级是时变的。Haritsa 与Tseng 等HAR93,TSE95对于基于价值的调度算法进行了广泛研究,认为:如果事务的价值是偏斜 分 布 , 其 中10 的 事 务 提 供90 的 价 值 , 则 在 正 常 负 载 下
9、 算 法 性 能 排 序 为EDFHRF HVFVRD ,在系统过载时性能排序为HRFHVFVRDEDF。进一步, Tseng等TSE96研究了不同基于价值的实时事务调度算法在实时主内存数据库(RTMMDB )与部分驻留内存的实时数据库中的性能,目标在于评估并比较这些算法在主内存数据库环境中的性能,以及研究只存储部分数据在主内存中的效果。Tseng 等的实验结果表明:当只有部分数据驻留内存时,增加内存的大小能够产生改进系统的性能,从而实现更高的价值。任务的价值也被用于准入控制中,决定任务的接纳或者移除先前接纳的任务,这将在下一小节讨论。此外,Bestavros 等BES95研究了在软实时数据库
10、中如何利用价值函数确定提交事务或者延迟提交事务,这种在并发控制中综合考虑事务的截止期与价值的问题能够归结为名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 6 页 - - - - - - - - - 如何为竞争的事务定量配给冗余的资源,以便实现更大的系统价值。Hong 与 Chakravarthy等HON92,CHJ94在他们的研究工作中引入代价意识(Cost Consciousness)的概念,提出并评估了一个 CCA-ALF (Cost Conscious Approa
11、ch with Average Load Factor )调度策略,这是一个最大努力的方法,调度决策中既考虑了事务的静态方面(软/固截止期),也考虑了事务执行的动态方面(系统负载)。在 Braoudakis 的研究中BRA94,假设每个事务关联一个价值函数,标识了这个事务的时间需求与重要性。在这个框架下, 事务的不同特征能够被描述,包括硬、固定、软或者无截止期事务, 从而允许单个的事务处理协议在所有类型的事务上一致地执行。2 基于准入的事务调度实时事务调度面临的一个主要挑战是事务执行所需要的资源是事先未知的。例如,事务读/写的数据对象可能依赖于用户的输入或者传感器输入,因此为事务预留资源以保证
12、事务的最坏情况执行时间WCET (Worst Case Execution Time )是非常困难的。考虑当前在实时事务调度与实时并发控制方面众多的研究成果,其中包括许多时间认知的并发控制协议被提出,目的在于最大化满足截止期的事务数量。这些算法或者协议的优势只有当系统出现过载时才被具体地体现,它们的性能在系统欠载的情况下通常与非常简单的算法(如EDF 与2PL-HP)相当。既然当一个实时数据库系统过载时,大量的事务错失了截止期,如果通过准入控制与过载管理策略拒绝一些事务进入系统,就能够避免有限的资源浪费在执行不可能及时完成的事务上。正是基于这种思想,一些研究针对准入控制技术进行了较深入的研究。
13、Bestavros 等BES96给出一个实时数据库模型,并在此基础上研究了硬截止期事务的准入控制与过载管理问题。由于硬实时事务错失截止期可能产生严重的后果,因此硬实时事务的执行需求必须预先知道,或者定义一些补救活动,以保证系统不会出现灾难性的后果。Bestavros 等定义的事务模型中,每个事务由两个部分组成:基本子事务与补偿子事务。准入控制器用于决定是否接纳新到达的事务。这里,准入控制器由两个部分组成:并发准入控制器( CACM :Concurrency ACM )与负载准入控制器(WACM :Workload ACM ) 。为了保证补偿事务的完成,系统采用两层优先级模式进行调度。系统总是为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年实时数据库系统之实时事务调度算法宣贯 2022 实时 数据库 系统 事务 调度 算法
限制150内