分布式在线状态下任务时间参数预测技术的研究

广东工业大学硕士学位论文分布式在线状态下任务时间参数预测技术的研究姓名：黄常青申请学位级别：硕士专业：计算机应用技术指导教师：徐海水20070501分布式在线状态下任务时间参数预测技术的研究作者：黄常青学位授予单位：广东工业大学相似文献(10条)1.期刊论文高军礼.李迪.郑时雄.GAOJun-li.LIDi.ZHENGShi-xiong基于RT-UML模型的实时系统可调度性分析-信阳师范学院学报（自然科学版）2006,19(3)简要回顾实时系统的开发现状,对实时系统可调度性相关理论进行探讨.提出一种基于实时统一建模语言对实时系统可调度性进行分析的方法.通过将系统RT-UML模型中实时任务的相关数量信息提取出来,在相应分析工具中进行可调度性分析,分析结果自动反馈到模型中去,实现了对实时系统可调度性进行系统实现前的离线分析.2.学位论文王磊容错实时系统可调度性分析研究2005实时系统在工业、商业和军事领域中得到了广泛应用，这类系统对响应时间具有严格的要求，尤其是强实时系统，如果不能满足响应时限，将可能导致灾难性的后果。因此在实时系统设计过程中必须提供相应的手段来保证整个系统运行的实时性。可调度性分析是一种验证计算机系统是否满足实时性要求的方法，广泛应用于实时系统的开发过程。但是随着应用需求的不断提高，实时系统的设计也变得越来越复杂，尤其是实时操作系统、容错技术以及分布式计算技术在实时系统中的大量应用，现有的分析方法已无法满足复杂的应用需求。本文以实时控制系统的开发为背景，研究了在采用符合OSEK/VDX标准的实时操作系统，主/副版本任务错误机制，以及在分布式系统环境下，进行系统可调度性分析的方法。本文的工作主要集中在以下四个方面：1.混合抢占和分组抢占调度下的系统可调度性分析研究。混合抢占和分组抢占调度是OSEK/VDX操作系统规范推荐的两种实时调度策略，目前并未见到针对这两种调度策略的可调度性分析研究。本文分别针对这两种调度策略提出了计算任务最大响应时间的方法，通过对任务最大响应时间和截止时间的比较判定系统的可调度性。为了分析容错机制对系统可调度性的影响，将主/副版本容错机制分别与混合抢占调度和分组抢占调度相结合，提出了容错机制下任务最大响应时间的计算方法，并在此算法基础上给出了系统可承受最小错误间隔的算法。2.抢占门限调度下的系统可调度性分析研究。抢占门限调度比混合抢占和分组抢占具有更强的灵活性和通用型。但是目前针对这种调度策略的可调度性分析只考虑了系统正常运行的情况，并未考虑容错机制的影响。为此本文对这种调度策略进行了可调度性分析的容错扩展研究，提出了主/副版本容错机制下的任务最大响应时间计算方法。为了获得最优的系统容错性能，还提出了优化遍历算法和启发式算法来计算系统抢占门限优先级分配的最优策略。3.分布式实时系统的可调度性分析研究。现有的针对分布式实时系统的可调度性分析方法无法在满足分析精确性的同时保证较高的计算性能，在实际应用中无法满足复杂实时系统设计对可调度性分析的性能要求。为解决这一问题，本文针对事务周期不大于其截止时间的情况，提出了线性分布式系统事务端到端最大响应时间和最小响应时间的计算方法。该方法充分考虑了任务和消息的本地、全局依赖关系以及释放抖动的影响，可以获得精确的分析结果。通过关键时刻分析和规范形式转换，降低了算法的计算复杂度。实验表明，本文提出的分布式系统可调度性分析算法在保证分析精确性的同时，对于高CPU利用率和大任务量的情况都具有优越的计算性能，可满足复杂分布式系统的可调度性分析要求。另外，通过对事务运行最坏和最优两种边界情况的分析可以精确地预测事务的最大响应抖动。4.可调度性分析在实际产品开发中的工程应用方法研究。基于抽象理论模型的研究与工程实践之间往往存在着较大差别，尤其是实际采用的操作系统本身的运行开销会影响分析结果的准确性。本文以SmartOSEK操作系统为例，研究了OSEK操作系统运行开销对任务响应时间的影响，提出了在实际运行环境中根据操作系统的运行开销提高任务最大响应时间计算精度的方法。为了在实时系统工程开发中有效地使用可调度性分析技术来验证系统的时间性能，本文还提出了支持OSEK/VDX标准的实时系统开发和时间性能验证流程，并介绍了一套用于支持该流程自主研发的嵌入式软件开发平台——SmartIDE。3.期刊论文沈卓炜.汪芸.ShenZhuowei.WangYun基于EDF调度策略的端到端实时系统可调度性分析算法-计算机研究与发展2006,43(5)端到端实时任务调度模型可用于描述许多分布式实时系统.提出一种基于EDF调度策略的端到端实时任务调度模型,给出了端到端实时系统的可调度性判定条件,并提出其可调度性分析算法,该可调度性判定条件及可调度性分析算法适用于采用非连续工作型同步协议和连续工作型同步协议控制下的端到端实时系统.与固定优先级的端到端实时任务调度模型及其算法相比,基于EDF调度策略的端到端实时任务调度模型和算法更加简单和易于实现,仿真结果也表明具有较高的性能.4.学位论文陈艾面向能耗优化的分布式实时系统调度算法研究2007实时系统，特别是运行在安全关键应用领域的分布式实时系统，具有十分严格的及时性和可靠性要求。随着当前系统能耗已经成为计算系统的重要设计约束，如何在实时系统设计中进行能耗优化，已经成为实时系统研究中亟待解决的问题。实时调度是保障实时系统及时性和可靠性的重要方法。实时系统能耗优化调度将能耗优化机制与既有的实时调度策略相结合，从系统整体行为中挖掘其潜在的节能能力，已成为实时系统能耗优化设计最有效的策略。本论文'1以分布式实时系统的能耗优化调度算法设计为方向，分别对分布式强实时系统的可调度性验证的形式化方法、实时任务调度、容错实时调度等关键问题进行了深入的研究，提出一系列相关方法和策略，以期进一步完善实时系统能耗优化调度方法。实时系统的可调度性验证是确保实时系统满足及时性的重要手段，是实时系统设计中的关键技术。分布式实时系统大量复杂特征的引入，需要采用更严谨的形式化验证方法来判断实时系统是否满足定时约束。针对这一现状，本论文在对当前已有实时系统的形式化描述模型的表达能力和建模难度进行分析比较的基础上，提出了一种与频率相关的时间Petri网——FRTPN模型，以及基于该模型的可调度性验证方法。FRTPN引入变迁频率设置空间以及频率相关的静态引发时域，支持面向频率调节的能耗优化调度研究；同时它增加一类抑制弧支持容错机制的建模：另外，本论文在借鉴现有时间Petri网相关验证技术的基础上，给出了FRTPN模型的基于状态类的可调度性验证方法，并通过对检查点容错策略进行建模验证了FRTPN模型的有效性。基于动态电压调整(DVS)技术的实时能耗优化调度方法已经成为实时系统能耗优化设计的最有效策略。针对现有分布式实时系统离线DVS调度算法采用的系统描述模型普遍缺乏全面准确刻画任务特征的能力，难以支持复杂分布式实时系统的可调度性验证的问题。本论文以FRTPN模型上的实时系统可调度验证为基础，提出了一种基于能耗/时间渐变率的启发式离线DVS调度算法，综合考虑了频率调整对系统能耗与松弛时间造成的影响，并以此为指导对待调频任务进行选择。另外，本论文还对任务分配进行了深入研究，提出了一种以任务利用率均匀化为目标的任务分配方法，以减少频率切换过程导致的能耗开销。在上述算法实现过程中，本论文根据FRTPN模型状态空间的变化规律，优化系统状态空间的生成过程，提高了算法的实现效率。容错技术是保障实时安全关键系统可靠性的重要手段，而基/副版本容错调度是目前解决分布式实时系统容错问题的有效方法。针对当前基/副版本容错实时调度中缺乏对能耗优化机制考虑的问题，本论文对基/副版本容错系统的DVS能耗优化调度展开研究。首先提出一种离线设置处理器执行频率的静态容错DVS调度算法，在此基础上提出能够在线收集动态松弛时间并进行再分配的动态容错DVS调度算法，最后提出一种以尽量推迟副版本释放时间为目标的基/副版本时限优化分配算法。模拟试验表明，上述算法能够有效地改善容错实时系统的能耗开销。综上所述，本论文所做工作的主要贡献与创新特色体现在以下三个方面：(1)提出了一种能够有效对系统的能耗特征和容错机制建模的频率相关时间Petri网模型——FRTPN及其相关可调度性验证方法，能够满足复杂的分布实时系统的建模及面向能耗优化的实时系统可调度性验证需求。(2)提出了一种以系统能耗/时间渐变率为指导的离线DVS调度算法(ETGBS)以及一种以任务利用率均匀化为目标的任务分配算法(UBTA)，有效降低系统的能耗开销。(3)首次开展了基/副版本容错系统的能耗优化调度研究，提出了相应的静态DVS调度算法(PBSS)、动态DVS调度算法(PBDS)以及基/副版本的时限优化分配算法(PBDA)，在满足分布式容错实时系统的及时性、可靠性的前提下，降低系统能耗。5.期刊论文牛云.戴冠中.梁亚琳.NIUYun.DAIGuan-zhong.LIANGYa-lin基于时间需求迭代和排队模型的开放式实时系统可调度性分析算法研究-计算机科学2009,36(1)基于RM调度策略和可延期服务器调度的开放式实时系统,以往的可调度性分析算法造成较低资源利用率.结合时间需求分析和服务台休假M/M/1/K排队模型,考虑带宽保留服务器,提出一种高资源利用率的可调度性分析算法,对系统中所有周期任务进行可调度性分析测试.给出其在临界点的响应时间;根据非周期事件到来率和接收缓冲定量分析非周期事件的平均响应时间和事件丢失率.实验表明,提出的可调度性分析方法通过估计任务的响应时间范围,能够在较高资源利用率下,验证多任务系统的可调度性.6.学位论文舒国强面向对象的实时系统可调度性验证和代码生成技术研究2003该文研究了一种以保证时间约束为最终目标的实时系统面向对象开发方法,该方法应用了可调度性验证和自动代码生成两项核心技术,解决了一类时间约束的验证和保障问题.该文的研究内容分为三个部分:系统建模、模型的可调度性验证、模型的自动代码生成.这三部分分别对应该文研究的实时系统开发方法应用的三个步骤.该文首先基于UML语言建立了一个实时系统对象模型的四部分核心元素集合,给出了系统行为特别是时间约束有关的建模元素的形式化定义,它们是对实时系统进行分析和实现的依据.该文研究了从对象模型中提取出和时间约束有关的任务集合,并应用传统的实时调度理论验证端到端时间约束的方法.该文讨论几种典型任务集合的实现,并分别分析了它们的调度性验证算法和结论.为了保障系统实现能够和设计模型一致地满足时间约束,该文给出了从对象模型自动生成目标平台上源代码的方法,并基于一个简单的目标平台接口规范设计了运行时支持库.该文的研究工作是对使用面向对象方法开发实时系统的探索,该文的研究成果可以为实时系统开发的工程实践提供的理论指导.最后作者通过一个完整的实例研究说明了该文构造的方法在工程实践中的应用.7.期刊论文李俊.阳富民.卢炎生.LIJun.YANGFu-min.LUYan-Sheng一种可行的容错实时系统可调度性分析-软件学报2005,16(8)针对容错实时系统中容错优先级两种分配策略存在的不足,通过对容错实时任务进行基于最坏响应时间的可调度性分析,提出了允许容错优先级降低的分配策略以提高系统的容错能力.经过深入的分析和实验证明,这种容错优先级的分配策略能够在以前两种分配策略无法提高系统容错能力的情况下,有效地提高系统的容错能力,设计并实现了改进的最佳容错优先级分配因子的搜索算法,并通过模拟实验进行了验证.8.学位论文窦强分布式强实时系统中可调度性分析算法的研究2001与单处理器实时系统相比,分布式实时系统中的可调度性分析算法比较复杂并具有自身的特点.该文的研究主要分两个部分,第一部分是对分布式系统中消息的通讯开销进行分析研究.第二部分是在综合考虑各任务和消息的响应时间以及不同的任务同步控制方式的基础上对任务序列的最大响应时间进行分析研究,并提出相应的分析算法.9.期刊论文刘军祥.王永吉.Matthe