首页 >  硕士论文 > 软件工程硕士论文 >   正文

异构系统中实时任务的软件工程容错调度算法

添加时间:2018-10-15 20:23:27   浏览:次   作者: www.dxlwwang.com
专业论文资料, 搜索论文发表论文代写论文网为你解忧愁!详情请咨询我们客服。
获取免费的论文资料? 欢迎您,提交你的论文要求,获取免费的帮助

本文是一篇软件工程硕士论文,软件是由计算机程序和程序设计的概念发展演化而来的,是在程序和程序设计发展到一定规模并且逐步商品化的过程中形成的。软件开发经历了程序设计阶段、软件设计阶段和软件工程阶段的演变过程。(以上内容来自百度百科)今天为大家推荐一篇软件工程硕士论文,供大家参考。

 
第 1 章 绪论
 
1.1 研究背景和意义
随着计算机技术的飞跃进步,用户对计算机性能要求不断提高,使计算机系统日益趋向异构化。异构系统中,处理器的执行能力各不相同。将不同类型的任务分配给适合处理此类型的处理器执行,比把所有任务分配在同构处理器上执行效率更高。近年来,处理器制作工艺的进步让集成在芯片上的晶体管尺寸不断缩小且晶体管的数量急速增长,使得异构系统的规模和复杂度日益增长。计算机性能虽然很大程度地提高了,另一方面系统的故障率也增大了。异构系统已经广泛应用于各类安全相关的实时系统中,这类系统要求发生故障时,实时任务也必须在时间截止期内完成,否则将产生严重后果。根据实时系统对时间要求程度的不同,可以将其分为“硬实时系统”和“软实时系统”[1]。硬实时系统要求在限定的时间内必须得到响应。例如飞行控制系统、追踪导弹的雷达系统、以及监控危重病人的系统。如果时间需求未得到满足,可能会造成飞机失事、人员伤亡这样灾难性的后果。软实时系统的时间需求虽然重要,但是错过截止期系统功能仍然可以正常运行。例如数据采集系统[2],即使没有及时得到采集数据,也不会发生像飞机失事那样严重的后果。由于硬件缺陷、电磁干扰和宇宙射线辐射的影响,系统在运行时可能发生故障[3]。故障可分为两种类型,瞬时性故障和永久性故障[4]。当发生瞬时性故障时,系统可以立刻恢复正常[5]。当发生永久性故障时,发生故障的处理器不能再执行任何任务,此处理器上未完成的任务必须迁移到其他未发生故障的处理器上执行[6]。当系统的复杂性达到一定程度时,设计出完全无故障的系统是不可能的。因此,需要采取一些措施提高系统的可靠性。系统可靠性可以由四种方式得到保障:避错、消除错误、容错和错误预测[7]。避错主要作用在系统的设计和维护阶段,在系统设计阶段、需求分析以及代码编写,每个过程都必须最大程度地保证其正确性,但是在设计阶段完全避免错误是不太可能的。消除错误主要作用于系统测试和维护阶段,模拟真实环境进行测试,对错误检测分析,再改进以消除错误,测试阶段也不一定能发现所有的错误。容错主要作用于系统运行阶段,当系统发生错误时,采取措施来应对,避免系统因故障而崩溃。错误预测也作用于系统运行阶段,系统对当前运行环境进行分析,并对错误进行预测,采取措施避免错误发生。
.........
 
1.2 国内外研究现状
异构实时系统要求系统故障时也要保证任务正确执行。因此,需要对系统进行容错处理。容错调度是实现系统容错的重要方法,容错调度算法已经成为实时系统容错调度研究的热点。过去几十年间,大量研究人员投身于容错算法的研究中[15-21]。根据研究的故障类型,可以将文献分为两类:瞬时性容错调度算法和永久性容错调度算法。
 
1.2.1 瞬时性容错调度算法
系统的瞬时性故障可能导致故障任务本身不能按时完成,也可能导致其他任务不能按时完成。因此,为系统提供一定的容错能力十分必要。容错调度是实现系统容错的有效方式,下面对瞬时性故障相关的容错算法进行描述。根据任务的周期属性可以将容错算法分为周期任务调度算法和非周期任务调度算法。文献[3]针对周期性任务进行了研究。Zhu 和 Aydin 等人在[3]中提出了静态和动态可靠性感知的能源管理方案,在减少能源消耗的同时保证系统的可靠性。Haque等人在文献[4]中研究了在多核系统上以最低能耗实现可靠性目标的问题,该文献提出的算法中,采用主动性复制方式容错,但是基于同构系统平台。非周期性任务又可分为零星独立任务和依赖性任务。文献[19]研究了零星独立任务,文献[22]针对依赖性任务进行了研究。Han 等人在文献[19]提出了一种有效的调度方法,该方法能最大限度地减少能量消耗,基于 EDF 策略来容忍 k 个瞬时故障。此研究中提出了三种调度算法实现容错的同时减少能耗。Kumar 等人在文献[23]中提出了一个能量最小化容错调度算法。通过检查点策略使任务可以在故障情况下重新执行。设置最佳的检查点数量使系统避免完全重新执行。彭浩等人在文献[24]针对采用主/副版本技术的容错调度算法中,执行主版本时系统故障导致副版本运行时间变小,以至于可能错失截止期的问题提出了一种副版本不可抢占的全局容错调度算法FTGS-NPB,在主版本执行失败后给副版本分配最高优先级立刻得到资源开始执行,同时保证在其执行过程中不被其他任务抢占。这个算法基于同构系统。唐利红等人在文献[22]根据任务间依赖关系,建立了有向无环图(Directed Acyclic Graph)模型,提出一种容错调度算法 FT-DAG。在同步节点处添加时间冗余保障故障出现后系统在符合截止期的情况下,有足够的时间重新执行容错,还可以保障同步节点前继任务在出现瞬时性故障的情况下,不对其后继节点的执行产生影响。
............
 
第 2 章 相关研究
 
异构系统的结构日趋复杂,系统在执行实时任务期间不可避免地会发生一些故障。用户希望系统发生故障时仍然能得出正确的结果,所以对系统进行容错至关重要。实时调度是实现系统容错的有效方式。本章首先对容错的相关知识进行了介绍,然后详细地描述了实时调度相关技术。
 
2.1 容错研究
 
2.1.1 容错系统
容错可以保障系统的可靠性,在 2001 年,国际标准组织(IFIP)的 10.4 工作组对容错的概念进行了定义:当系统内部出现硬件或软件故障的情况下仍然能正确运行所有任务,并向外界提供无差错服务。A.Avizienis 教授 1967 年在[37]中提到:如果一个系统中的程序在发生故障的时候仍然能够正常执行,那么认为这个系统能够容错。图 2.1 给出了一个通用容错系统模型。在对一个系统进行容错研究时,要清楚处理的是什么类型的故障,根据故障持续时间对故障进行分类,可以将故障分为永久性故障和瞬时性故障。永久性故障由硬件缺陷造成,如果不采取修补措施,故障无法消除。瞬时性故障是由于周围环境变换的影响而产生。它发生后不久后会消失,并且为非重复性的。根据故障导致错误以及失效的不同,硬件故障的故障模型主要分为两类:Fail-stop 模型和 Byzantine 模型。Fail-stop 模型是比较理想的类型,即故障产生后,只有发生故障的部分会受到影响,系统中其他部件都运行正常[40]。Byzantine 模型是一种普遍的故障类型。即发生故障的部件会波及到其他部件[41]。常用的容错技术大多是遵循 Fail-stop 模型。随着硬件技术越来越发达,硬件缺陷引发的永久性故障占比逐步降低。统计数据显示,瞬时性故障为最主要的故障类型。系统中发生的故障 98%都是瞬时性故障[42]。但是,如果安全相关的系统发生了永久性故障,并且系统没有对故障进行处理的话,会发生无法预料的灾难性后果。因此在进行容错技术研究和容错计算机系统的设计时,不仅要处理瞬时性故障同样也要处理永久性故障。本文针对两种不同类型的故障分别进行容错,两类故障都遵循 Fail-stop 模型。
........
 
2.2 实时调度
随着高速网络和高性能 PC/工作站的发展,异构系统已经广泛应用于各类安全关键系统,如飞行控制系统、核电站控制系统等。这些系统中的任务如果未能在给定的时间约束前执行成功,往往会产生严重后果。实时系统在各个方面发挥着重要作用,如国防、航天航空、自动控制处理方面[46-48]。与通用计算机不同,实时系统的正确性不仅取决于产生结果值的正确性还取决于产生结果的时间[49]。根据系统对响应时间的需求,实时系统可以分为硬实时系统和软实时系统。硬实时系统:在安全相关的领域,如航空航天、军事、核工业等领域中,系统的时间约束必须得到满足,如果超过时间截止期,可能会发生飞机失事这样重大的安全事故,造成严重的生命和财产损失。因此在设计这一类系统时,一定要保证其时间约束和功能需求都得到满足。软实时系统:对响应时间的要求不高,只有当响应时间超出某一域值时,才会影响系统的正确性。如典型的软实时系统“VOD 系统”,即使出现数据延迟导致画面失真,对用户不会有很大的影响,更不会出现性命攸关的重大事故。本文针对硬实时系统进行研究,和通用计算机相比,实时系统有几个重要的特点:时间约束:实时系统中的任务都具有时间约束。时间是实时系统需要控制和管理的一个重要因素。所有任务必须在给定的时间范围内完成,否则其计算结果将会失去意义,甚至引发严重后果。可靠性:可靠性是衡量实时系统的一个非常重要指标,在实时应用中,运行过程中的微小故障也可能会造成料想不到的后果。因此,需要采取一些措施让应用在发生故障的时候仍然能正常运行,例如采用冗余配置对应用进行容错。可预测性:可预测性能预测实时任务的执行完成时间。由于实时系统对时间要求很高,所以可预测性也是实时系统中的一个重要性能要求。
........
 
第 3 章 瞬时性容错调度算法......14
3.1 引言 ..... 14
3.2 模型及问题定义 ............. 14
3.3 动机例子 ........... 17
3.4 DB-FTSA 算法 ................ 18
3.5 实验与分析 ....... 22
3.6 本章小结 ........... 28
第 4 章 永久性容错调度算法......29
4.1 引言 ..... 29
4.2 模型及问题定义 ............. 29
4.3 DBSA 算法 ........ 30
4.4 实验与分析 ....... 33
4.5 本章小结 ........... 38
第 5 章 总结与展望........39
5.1 总结 ..... 39
5.2 展望 ..... 39
 
第 4 章 永久性容错调度算法
 
4.1 引言
异构系统广泛应用于安全关键系统,使得系统对可靠性的要求很高。系统要求应用中的实时任务故障的情况下依然能正确执行。系统中的故障分为瞬时性故障和永久性故障。永久性故障如果得不到处理,会影响实时任务无法在时间截止期之内完成引发灾难性后果。由此,对系统进行容错以及保证任务的实时性显得十分重要。现有的永久性容错算法盲目地对任务进行备份,忽略了任务的实时性。在严格的时间约束下,盲目的备份容易超过时间截止期。本章针对这些问题,提出了一种基于时间截止期的永久性容错调度算法(Deadline-Based Scheduling Algorithm,简称为“DBSA”)。该算法在保证给定时间约束的条件下,定量地计算出时间截止期内能容错的次数。本章进行了一系列实验评估 DBSA 的有效性,实验结果表明 DBSA 在满足任务实时性的基础上提高了系统可靠性。
\
............
 
总结
 
在异构系统上进行调度很有挑战性,也是当前研究的一个热点。异构系统已经广泛应用于许多安全关键领域中,这类系统对可靠性的要求很高。系统中的实时任务要求系统发生故障的情况下仍然能提供正确的服务。因此,满足系统中任务的实时性和容错需求十分必要。容错调度算法是实现系统容错的一个重要方式。本文在原有容错算法的基础上进行改进,研究了在满足时间约束的条件下对任务进行容错的调度算法。本文主要工作和创新点包括:
(1) 提出了一种基于时间截止期的瞬时性容错调度算法。现有的瞬时性容错算法只对任务进行容错而忽视了任务的实时性。本文针对系统中的瞬时性故障,以时间截止期为主要约束条件,计算得出系统可提供容错的任务,然后给出了包含备份副本的任务分配方案。实验数据也证实了算法的有效性。
(2) 提出了一种基于时间截止期的永久性容错调度算法。现存的永久性容错算法盲目地备份任务致使调度长度超过时间截止期。本文针对系统中的永久性故障,根据时间约束量化出系统能容忍的永久性故障次数,并对所有任务及其副本进行分配。实验结果表明本算法在满足时间截止期的基础上有效地提高了系统可靠性。
..........
参考文献(略)

提供海量毕业论文,论文格式,论文格式范文,留学生论文,商务报告相关资料检索服务。
本论文由代写论文网整理提供 http://www.dxlwwang.com/
需要专业的学术论文资料,请联系我们客服
本文地址:
论文关键字:异构系统 实时任务 容错调度