首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 132 毫秒
1.
一种新的分布式控制系统容错调度算法   总被引:3,自引:3,他引:0       下载免费PDF全文
目前多数容错调度算法在调度非周期任务时采用预留时间的方法,非周期任务无法得到充分响应。针对该问题,提出一种新的分布式控制系统容错调度算法,采用任务集划分的方法在不同处理机上运行不同的周期任务子集,使每个处理机具有不同的非周期任务预留时间,当非周期任务发生时,即可得到有效响应。结果表明,该方法能提高容错调度的效率。  相似文献   

2.
一种基于多处理机的容错实时任务调度算法   总被引:27,自引:2,他引:25  
容错是实时系统的重要要求,在实时系统中,若一个实时任务没在规定的时间期限内完成,则认为系统出现错误,针对多处理机实时系统提出了一种容错调度算法.算法采用了任务的主从备份技术和First-fit启发式方法,通过为可能因处理机故障而执行失败的实时任务预留重新运行的时间来实现容错功能;并通过对预留时间段的重叠利用和无错时预留时间的回收分配,来提高处理机的利用率和系统对任务的接收率.模拟结果表明算法是有效  相似文献   

3.
混合型实时容错调度算法的设计和性能分析   总被引:17,自引:2,他引:15  
以往文献中研究的实时容错调度算法都只能调度单一的具有容错需求的任务.该文建立了一个混合型实时容错调度模型,提出一种静态实时容错调度算法.该算法能同时调度具有容错需求的实时任务和无容错需求的实时任务.该文还提出了一个求解最小处理机个数的算法,用于对静态实时容错调度算法的性能进行模拟分析.为了提高静态调度算法的调度性能,提出了一种动态调度算法.最后,通过模拟实验分析了静态和动态调度算法的性能.实验表明,调度算法的性能与实时任务的个数、任务的计算时间、周期和处理机个数等系统参数相关.  相似文献   

4.
基于异构分布式系统的实时容错调度算法   总被引:26,自引:1,他引:26  
目前文献中研究的实时容错调度算法都是基于同构分布式系统,系统中的所有处理机完全相同。该文首先建立了一个基于异构分布式系统实时容错调度模型,异构分布式系统中的各个处理机均不相同。基于该异构分布式系统模型,该文引入了可靠性代价(reliability cost)概念,并提出两种静态实时容错调度算法(RTFTNO和RTFTRC)用于调度周期性实时容错任务。算法RTFTRC在调度任务时,尽量使系统的可靠性代价最小;而算法RTFTNO在调度实时任务时,没有考虑系统的可靠性代价。该文详细讨论了两种调度算法的性能。性能模拟实验分别比较了两个算法的可靠性代价,超时比率和可调度性;并研究了任务的计算时间与可靠性代价的关系以及调度长度阈值与最小处理机个数的关系。实验结果表明,算法RTFTRC的性能优于算法RTFTNO。  相似文献   

5.
基于EDF的分布式系统实时容错调度算法   总被引:1,自引:0,他引:1  
将分布式系统的任务分配算法与处理器局部调度算法相结合,提出一种主动备份的、基于EDF的分布式系统实时容错调度算法,其特点是主/副版本执行时间可以重叠。给出了该调度算法的任务集可调度的充分条件、任务集可调度所需最小处理器个数的计算方法。模拟结果比较了主动备份容错调度算法与被动备份容错调度算法,结果表明卞动备份算法效率更优。  相似文献   

6.
目前研究单机实时系统的调度算法文章大多只能调度单一类型的任务。本文在PKSA算法的基础上,建立了一种混合型实时容错模型,提出一种调度算法不仅可以调度有容错需求的周期任务,同时也能够调度无容错需求的周期任务和非周期非实时任务,实现了调度混合型任务的目的。  相似文献   

7.
目前研究单机实时系统的调度算法文章大多只能调度单一类型的任务。本文在PKSA算法的基础上,建立了一种混合型实时容错模型,提出一种调度算法不仅可以调度有容错需求的周期任务,同时也能够调度无容错需求的周期任务和非周期非实时任务,实现了调度混合型任务的目的。  相似文献   

8.
基于延迟主动副版本的分布式实时容错调度算法   总被引:6,自引:0,他引:6  
主/副版本备份技术是分布式系统常用的实时容错调度方法,然而传统的主动方式副版本即使在无处理机故障时也需要在备份处理机上完全运行,增加了处理机消耗.提出一种基于固定优先级调度算法的延迟主动副版本(deferred active backup-copy)备份技术,该技术通过尽量向后调度主动方式的副版本,并在主版本成功执行时终止副版本的执行来减少备份的冗余度.在此基础上,提出一种基于该技术的以最小化处理机数目为优化目标的启发式任务分配算法--基于延迟主动副版本的最佳适应算法DABCBF(deferred active backup-copy based best-fit algorithm).DABCBF在保证系统的实时性和容错能力的前提条件下,通过尽量减少主版本的最坏响应时间来最大程度地减少冗余,以节省处理机.最后通过仿真实验,证明了算法的可行性和有效性.  相似文献   

9.
为解决云环境下安全调度和可靠性问题,综合考虑云计算共享性、动态性等特点,以具有依赖关系的并行任务为基础,提出一种两阶段安全驱动的容错调度算法(TSDFT).建立安全模型计算任务调度风险率,根据风险率选择处理机,使用自适应备份策略对任务进行备份预处理;在上一阶段基础上,通过被动副本方式实现任务容错调度,每个处理机维护主/副本2个局部队列,支持一个以上处理机同时失效.仿真结果表明,该算法能有效降低异构系统中任务调度风险率,提高调度的安全性和可靠性.  相似文献   

10.
容错多处理机中一种高效的实时调度算法   总被引:5,自引:0,他引:5  
针对基于主副版本容错的多处理机中独立的、抢占性的硬实时任务,提出了一种高效的调度算法——TPFTRM(task partition based fault tolerant rate-monotonic)算法.该算法将单机实时RM 算法扩展到容错多处理机上,并且调度过程中从不使用主动执行的任务副版本,而仅使用被动执行和主副重叠方式执行的任务副版本,从而最大限度地利用副版本重叠和分离技术提高了算法调度性能.此外,TPFTRM 根据任务负载不同将任务集合划分成两个不相交的子集进行分配;还根据处理机调度的任务版本不同,将处理机集合划分成3 个不相交的子集进行调度,从而使TPFTRM 调度算法便于理解、实现以及减少了调度所需要的运行时间.模拟实验对各种具有不同周期和任务负载的任务集合进行了调度测试.实验结果表明,TPFTRM与目前所知同类算法相比,在调度相同参数的任务集合时不仅明显减少了调度所需要的处理机数目,还减少了调度所需要的运行时间,从而证实了TPFTRM 算法的高效性.  相似文献   

11.
Hard-real-time systems require predictable performance despite the occurrence of failures. In this paper, fault tolerance is implemented by using a novel duplication technique where each task scheduled on a processor has either an active backup copy or a passive backup copy scheduled on a different processor. An active copy is always executed, while a passive copy is executed only in the case of a failure. First, the paper considers the ability of the widely-used rate-monotonic scheduling algorithm to meet the deadlines of periodic tasks in the presence of a processor failure. In particular, the completion time test is extended so as to check the schedulability on a single processor of a task set including backup copies. Then, the paper extends the well-known rate-monotonic first-fit assignment algorithm, where all the task copies, included the backup copies, are considered by rate-monotonic priority order and assigned to the first processor in which they fit. The proposed algorithm determines which tasks must use the active duplication and which can use the passive duplication. Passive duplication is preferred whenever possible, so as to overbook each processor with many passive copies whose primary copies are assigned to different processors. Moreover, the space allocated to active copies is reclaimed as soon as a failure is detected. Passive copy overbooking and active copy deallocation allow many passive copies to be scheduled sharing the same time intervals on the same processor, thus reducing the total number of processors needed. Simulation studies reveal a remarkable saving of processors with respect to those needed by the usual active duplication approach in which the schedule of the non-fault-tolerant case is duplicated on two sets of processors  相似文献   

12.
曹洁  曾国荪 《计算机应用》2015,35(3):648-653
云环境中的处理机故障已成为云计算不可忽视的问题,容错成为设计和发展云计算系统的关键需求。针对一些容错调度算法在任务调度过程中调度效率低下以及任务类型单一的问题,提出一种处理机和任务主副版本分组的容错调度方法;并给出了副版本可重叠执行的判定方法,以及任务最坏响应时间的计算公式。通过实验和分析表明,和以前算法相比,将处理机分成两组分别执行任务主版本和任务副版本,减少了任务调度所需进行可调度测试的时间,增加了副版本重叠执行的机会,减少了所需的处理机个数,对提高系统处理机的利用率和容错调度的效率具有重要的意义。  相似文献   

13.
Silly  Maryline 《Real-Time Systems》1999,17(1):87-111
In this paper, we are concerned with the problem of serving soft aperiodic tasks on a uniprocessor system where periodic tasks are scheduled on a dynamic-priority, preemptive basis and exclusively access to critical sections. Scheduling of tasks is handled by the Dynamic Priority Ceiling Protocol working with an Earliest Deadline scheduler. Our analysis determines the maximum processing time which may be stolen from periodic tasks without jeopardizing both their timing constraints and resource consistency. It provides the basis for an on-line scheduling algorithm, the EDL Server, to deal with the minimization of response times for soft aperiodic tasks.  相似文献   

14.
提高软非周期任务响应性能的调度算法   总被引:9,自引:0,他引:9  
何军  孙玉方 《软件学报》1998,9(10):721-727
实时环境中常常既包含硬周期任务,又包含软非周期任务,引入一种改进软非周期实时任务响应时间的算法.已有的解决混合任务调度问题的方法都是基于速率单调(Rate Monotonic)策略的,其中从周期任务“挪用时间”的算法被证明优于其他所有算法.但是,速率单调算法限制了处理器的使用率,从而使周期任务的可“挪用”时间受到限制.最后期限驱动(Deadline Driven)策略DD可使潜在的处理器利用率达到100%.新算法正是在周期任务的调度中适当加入了DD策略,从而使非周期任务的响应时间得以缩短.仿真实验的结果表明,这种算法的性能优于已有的所有算法,而由它所带来的额外开销却不算很高.  相似文献   

15.
The paper addresses the problem of jointly scheduling tasks with both hard and soft real time constraints. We present a new analysis applicable to systems scheduled using a priority preemptive dispatcher, with priorities assigned dynamically according to the EDF policy. Further, we present a new efficient online algorithm (the acceptor algorithm) for servicing aperiodic work load. The acceptor transforms a soft aperiodic task into a hard one by assigning a deadline. Once transformed, aperiodic tasks are handled in exactly the same way as periodic tasks with hard deadlines. The proposed algorithm is shown to be optimal in terms of providing the shortest aperiodic response time among fixed and dynamic priority schedulers. It always guarantees the proper execution of periodic hard tasks. The approach is composed of two parts: an offline analysis and a run time scheduler. The offline algorithm runs in pseudopolynomial time O(mn), where n is the number of hard periodic tasks and m is the hyperperiod/min deadline  相似文献   

16.
In a parallelizable task model, a task can be parallelized and the component tasks can be executed concurrently on multiple processors. We use this parallelism in tasks to meet their deadlines and also obtain better processor utilisation compared to non-parallelized tasks. Non-preemptive parallelizable task scheduling combines the advantages of higher schedulability and lower scheduling overhead offered by the preemptive and non-preemptive task scheduling models, respectively. We propose a new approach to maximize the benefits from task parallelization. It involves checking the schedulability of periodic tasks (if necessary, by parallelizing them) off-line and run-time scheduling of the schedulable periodic tasks together with dynamically arriving aperiodic tasks. To avoid the run-time anomaly that may occur when the actual computation time of a task is less than its worst case computation time, we propose efficient run-time mechanisms.We have carried out extensive simulation to study the effectiveness of the proposed approach by comparing the schedulability offered by it with that of dynamic scheduling using Earliest Deadline First (EDF), and by comparing its storage efficiency with that of the static table-driven approach. We found that the schedulability offered by parallelizable task scheduling is always higher than that of the EDF algorithm for a wide variety of task parameters and the storage overhead incurred by it is less than 3.6% of the static table-driven approach even under heavy task loads.  相似文献   

17.
强实时环境下调度非周期任务的时限寻优方法   总被引:1,自引:0,他引:1  
文章提出了强实时环境下调度弱时限非周期任务的时限寻优方法(DOA),该方法在保证周期任务和偶发性任务满足时限要求的前提下,使非周期任务的响应时间达到最优。它还可根据实时应用的需要对算法的执行性能和计算复杂度进行折衷调整。仿真实验表明,DOA与现有的动态调度算法相比,使非周期任务响应时间更短,同时它收敛快,额外开销小,计算复杂度低,实现方便,因此是强实时环境下对周期任务与非周期任务进行混合调度的一种较好的方法。  相似文献   

18.
实时多处理机系统BEST-FIT启发式容错调度   总被引:4,自引:0,他引:4  
本文从有效利用资源的角度出发,提出了一种以最小化处理机数目为优化目标的Best-Fit启发式容错调度算法。该算法采用主/副版本备份技术和副版本的主动运行方式与被运行方式相结合的方法,将实时任务的主版本和副版本调度到不同处理机上运行;并且按照Best-Fit启发式策略为实时任务主版本寻找“最佳满足”处理机,使尽可能多的实时任务副版本以被动方式运行。算法既保证了系统的实时性和容错性,也节约了处理机。分析和仿真结果均证明了算法的有效性。  相似文献   

19.
Dynamic scheduling of real-time tasks under precedence constraints   总被引:6,自引:0,他引:6  
While scheduling theory has been developed over a long period of time, it is important to note that most results concern problems with static characteristics. However, a real-time system is dynamic and requires on-line and adaptive scheduling strategies. So, an important aspect of real-time systems research is to devise methods flexible enough to react to a dynamic change of processor load and to attempt to schedule all the tasks judiciously.In this paper, we are particularly concerned with the problem of scheduling tasks which are of two kinds: periodic and sporadic, on a monoprocessor machine. Periodic tasks are independent, run cyclically and their characteristics are known in advance. In addition, we allow for the unpredictable occurrence of aperiodic task groups, with timing and precedence constraints. Clearly, the main problem is to devise a schedulability test that makes it possible to decide whether a new occurring group can be accepted, without upsetting the tight timing behavior requirements.We present an optimal acceptance test which returns a decision on the basis of the current state of processor load and by considering tasks to be scheduled according to the well known preemptive algorithm Earliest Deadline. The acceptance algorithm and a complexity analysis are presented.  相似文献   

20.
应用于实时系统的RMS算法的改进   总被引:2,自引:3,他引:2  
本文阐述了以PLC为核心的HGJD001实验台电气控制系统,并采用上位计算机实现对实验台运行状态的通讯监测。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号