分布式控制系统中多种混合任务的容错调度

分布式控制系统中存在有强实时、软实时和非实时等多种实时性的任务,其中强实时任务必须在其时限前完成,否则会出现灾难性后果,因此必须为分布式控制系统提供一定的容错能力。首先给出了用于调度多种实时性任务的单处理器调度算法——双优先级队列调度算法,并分析算法的可调度性条件。针对分布式控制系统,考虑基版本与副版本的执行时间不同时,结合版本复制技术和单处理器调度算法提出了一种新的容错调度算法。分析了算法的可调度行,给出了可任务集的可调度条件判断方法和基版本任务时限的设置方法。在此基础上,采用启发式静态任务分配算法,保证各处理器的负载均衡。本算法在保证任务容错可调度的条件下,可提高系统中各处理器的利用率,仿真结果表明该算法是有效的。     

基于GA的DCS中任务的容错优化调度

分布式控制系统(DCS)中的实时任务必须在其时限前完成,否则会出现灾难性后果,因此必须为DCS提供一定的容错能力。该文基于EDF算法和版本复制技术给出了DCS的容错调度算法。在此基础上采用启发式任务分配算法分配任务,通过遗传算法对基版本任务时限进行优化,以提高处理器的利用率。仿真结果表明该算法是有效的。     

一种新的异构实时分布式系统的容错调度算法

一般来说,异构分布式实时系统中任务的周期并不完全相同且任务的时限不等于它们的周期,同时系统中还有一些无容错需求的任务.因此现有的任务调度算法一般不能满足这些要求.针对这类系统,在结合基版本/副版本技术和EDF算法的基础上,给出了一种新的容错调度算法.该算法由两部分组成：任务分配调度算法和单处理器调度算法.对于单处理器调度算法,本文采用了EDF算法;在此基础上,给出一种启发式静态任务分配算法.分析了系统的可调度性,给出了任务可调度条件和基版本/副版本时限的设置方法.仿真结果表明,这种算法是有效的.     

基于EDF的分布式控制系统容错调度算法

现有的分布式实时系统的容错调度算法要求系统中所有任务的周期相同且等于其时限,而实际中任务的周期常常是互不相同的.根据控制系统中任务的特点,结合任务分配算法与处理器的调度算法,提出了基于基版本/副版本技术和EDF算法的容错调度算法.该算法不要求任务的周期都相同,并通过设置基版本/副版本任务时限控制它们的执行时间不重叠,给出了基版本/副版本任务时限的设置方法,并对任务集的可调度性进行了分析.当任务集可调度时,给出其最大利用率和最小处理器个数的约束条件.最后给出一个仿真实例,结果表明了算法的有效性.     

多处理器单调速率任务分配算法性能评价

多处理器任务分配调度算法是一类经典实时调度算法，然而目前研究在如何根据任务集特征选择任务分配算法方面少见指导性原则，不利于提高多处理器任务分配算法的可调度率及使用尽可能少的处理器达到最优调度结果。基于两种多处理器任务调度策略的比较，本文给出划分策略下的多处理器RM调度的可调度条件和任务分配算法夏分析。仿真结果表明，各任务分配算法所需处理器数与任务集总利用率成正比。同时，分析总结出各算法适用范围及如何根据任务集利用率选择合适算法的指导原则。最后结果还表明，实际算法性能与理论性能界存在差异。     

面向多处理器的实时周期任务容错调度算法研究

主副版本策略是多处理器系统实时任务调度中处理容错问题的一种重要方式.根据分布式控制系统的特点,本文提出一种改进的FTRMBF算法-PR-FTRMBF,以提高系统周期任务的可调度性.在FTRMBF等已有的调度算法中,当没有处理器分配给当前副版本时,将为副版本分配新的处理器;本文提出的改进算法则以回溯的方式重新分配主版本.在保证系统实时性能和容错能力的前提下,节省了处理器数目.仿真实验表明,与FTRMBF算法相比,改进算法显著提高了系统任务的可调度性.     

分布式实时系统中负载平衡任务分配算法

提出了一种以系统负载平衡为目标的分布式实时系统任务分配算法。该算法首先通过对任务分组，减小系统负载，再按照一种新的目标函数，启发搜索任务分配树，来获得系统负载平衡条件下系统负载最小的任务分配方案，有效地减小了启发式搜索算法的计算复杂度。     

基于延迟副版本的分布式控制系统容错调度算法

针对分布式控制系统中的周期性实时任务,基于版本复制技术设计一种新的容错调度算法.该算法将主动副版本技术、被动副版本技术和副版本重叠技术融合起来,充分利用它们的优点.算法通过延迟副版本的开始执行时间减少主/副版本执行时问的重叠,从而减少副版本的冗余度并提高处理器的利用率.给出了任务集容错可调度性的判别定理和副版本冗余时间的计算方法.在采用以最小化"最坏情况响应时间"的最佳适应方法和首次适应任务分配方法的基础上,给出启发式任务分配算法.最后对算法进行了仿真实验,实验结果表明了算法的有效性和可行性.     

异构实时多处理器系统的动态调度算法研究

实时多处理器系统的动态调度算法一直是实时系统中的重要研究课题.根据异构实时多处理器的特点,提出了一种新的异构实时动态调度算法P_IEFT.该算法采用了一个新的处理器分配策略——将任务分配到能最早完成任务的处理器上.该策略能够缩短调度长度,提高后继任务被接受的可能性,从而能够提高成功调度率.模拟结果表明,该调度算法的成功调度率高于近视算法和节约算法的成功调度率.     

深海集矿机多任务调度控制系统设计

设计并实现了一种基于多处理器的深海采矿实时调度控制系统,结合嵌入式ARM控制系统和实时操作系统μC/OS-II对深海集矿机的轨迹规划、实时避障、故障监测等基本实时控制任务进行划分,将划分好任务分配到固定各个多处理器系统中。采用MCDF调度算法实现全局动态调度,从理论上分析了所提出算法的可调度性,并在深海采矿多处理器集矿机控制系统中验证了算法设计有效性和可行性,为嵌入式用于深海采矿研究进行了探讨,表明了算法的有效性。     

一种严格按比例派发服务的混合实时调度算法

在混合实时系统中,调度器必须既保证所有硬实时任务严格按照其时间约束在截止期内完成,又要尽可能地提高软实时任务和非实时任务的服务质量.提出了一种严格按比例派发服务器算法(RPDS),并以此为基础构建了一种层次式调度框架.RPDS将处理器时间流分成连续的小段,并在每一小段中强制为非硬实时任务分配一个时间片.实验结果表明,RPDS可以合理地为各种类型应用分配处理器时间,并且降低了实时任务的截止期错失率.     

On-line scheduling of scalable real-time tasks on multiprocessor systems

The computation time of scalable tasks depends on the number of processors allocated to them in multiprocessor systems. As more processors are allocated to a scalable task, the overall computation time of the task decreases but the total amount of processors’ time devoted to the execution of the task, called workload, increases due to parallel execution overhead. In this paper, we propose a task scheduling algorithm that utilizes the property of scalable tasks for on-line and real-time scheduling. In the proposed algorithm, the total workload of all scheduled tasks is reduced by managing processors allocated to the tasks as few as possible without missing their deadlines. As a result, the processors in the system have less load to execute the scheduled tasks and can execute more newly arriving tasks before their deadlines. Simulation results show that the proposed algorithm performs significantly better than the conventional algorithm based on a fixed number of processors to execute each task.     

A non-preemptive scheduling algorithm for soft real-time systems

Real-time systems are often designed using preemptive scheduling and worst-case execution time estimates to guarantee the execution of high priority tasks. There is, however, an interest in exploring non-preemptive scheduling models for real-time systems, particularly for soft real-time multimedia applications. In this paper, we propose a new algorithm that uses multiple scheduling strategies for efficient non-preemptive scheduling of tasks. Our goal is to improve the success ratio of the well-known Earliest Deadline First (EDF) approach when the load on the system is very high and to improve the overall performance in both underloaded and overloaded conditions. Our approach, known as group-EDF (gEDF) is based on dynamic grouping of tasks with deadlines that are very close to each other, and using Shortest Job First (SJF) technique to schedule tasks within the group. We will present results comparing gEDF with other real-time algorithms including, EDF, Best-effort, and Guarantee, by using randomly generated tasks with varying execution times, release times, deadlines and tolerance to missing deadlines, under varying workloads. We believe that grouping tasks dynamically with similar deadlines and utilizing a secondary criteria, such as minimizing the total execution time (or other metrics such as power or resource availability) for scheduling tasks within a group, can lead to new and more efficient real-time scheduling algorithms.     

分时EDF算法及其在多媒体操作系统中的应用

提出了一种新的CPU调度算法－－分时EDF（Earliest Deadine First)算法,该算法能保证硬实时任务不丢失死线,并易于在分时系统中实现。以分时EDF算法为基础,提出一种新的CPU层次调度算法－－HRFSFQ,该算法用于多媒体操作系统时能保证各类任务的QoS。最后通过大量实验证明了上述算法的有效性和正确性。     

云计算环境下带安全约束的工作流调度问题的研究

资源调度问题一直是云计算环境下的热点研究问题,然而当前的大部分研究都集中在满足用户的时间或成本需求上,很少考虑用户在调度过程中对安全的需求。针对这一问题,在对常见的云环境下工作流任务的资源调度问题进行建模的基础上,提出了一个安全约束模型,并使用变近邻粒子群算法对该问题进行了求解。最后在CloudSim仿真平台上,用最大 最小蚁群算法和遗传算法与该算法进行了对比,实验结果表明,该算法具有很好的可用性和寻优能力。关键词：     

基于排队论和时间需求分析法的实时系统时间行为分析*

针对目前广泛使用的固态优先级RMS调度策略,利用时间需求分析算法对系统中所有周期任务进行可调度性分析测试,保证其在临界点仍可以满足时限。利用排队论中的M/M/1/K排队系统,根据非周期事件接收缓冲和可延期服务器定量分析非周期事件的平均响应时间和系统异步事件丢失率,使之符合系统要求。     

New Algorithms for Resource Reclaiming from Precedence Constrained Tasks in Multiprocessor Real-Time Systems

The scheduling of tasks in multiprocessor real-time systems has attracted many researchers in the recent past. Tasks in these systems have deadlines to be met, and most of the real-time scheduling algorithms use worst case computation times to schedule these tasks. Many resources will be left unused if the tasks are dispatched purely based on the schedule produced by these scheduling algorithms, since most of the tasks will take less time to execute than their respective worst case computation times. Resource reclaiming refers to the problem of reclaiming the resources left unused by a real-time task when it takes less time to execute than its worst case computation time. In this paper, we propose two algorithms to reclaim these resources from real-time tasks that are constrained by precedence relations and resource requirements, in shared memory multiprocessor systems. We introduce a notion called a restriction vector for each task which captures its resource and precedence constraints with other tasks. This will help not only in the efficient implementation of the algorithms, but also in obtaining an improvement in performance over the reclaiming algorithms proposed in earlier work [[2]]. We compare our resource reclaiming algorithms with the earlier algorithms and, by experimental studies, show that they reclaim more resources, thereby increasing the guarantee ratio (the ratio of the number of tasks guaranteed to meet their deadlines to the number of tasks that have arrived), which is the basic requirement of any resource reclaiming algorithm. From our simulation studies, we demonstrate that complex reclaiming algorithms with high reclaiming overheads do not lead to an improvement in the guarantee ratio.     

一种新颖的带模糊截止时限的磁盘调度算法

设计了一种新的基于截止时限的磁盘调度算法，该算法支持带多优先级的请求。对于某些实时要求，其截止时限是不确定的或者不精确的，该算法采用模糊集来描述这类不确定性，模糊截止时限的隶属度函数表示对请求完成时间的满意程度。调度的目的是最优的指定优先级，使得截止时限的满意程度最大化。根据请求截止时限的不同，把满意程度划分为若干连续的区间。在每个不同的区间内，每个请求都对应有修正的截止时限，把请求按照其修正的截止时限非减的顺序分配优先级，才能实现请求优先级的最优配置。仿真结果表明该算法能有效的分配请求的优先级，降低请求的丢失率，保证了更多的请求得到满足。