容错多处理机中一种高效的实时调度算法

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

一种基于多处理机的容错实时任务调度算法

容错是实时系统的重要要求,在实时系统中,若一个实时任务没在规定的时间期限内完成,则认为系统出现错误,针对多处理机实时系统提出了一种容错调度算法．算法采用了任务的主从备份技术和Ｆｉｒｓｔ－ｆｉｔ启发式方法,通过为可能因处理机故障而执行失败的实时任务预留重新运行的时间来实现容错功能;并通过对预留时间段的重叠利用和无错时预留时间的回收分配,来提高处理机的利用率和系统对任务的接收率．模拟结果表明算法是有效     

一种实时异构系统的集成动态调度算法

提出了一种实时异构系统的集成动态调度算法.该算法通过一个新的任务分配策略以及软实时任务的服务质量QoS(quality of service)降级策略,不仅以统一方式完成了对实时异构系统中硬、软实时任务的集成动态调度,而且提高了算法的调度成功率.同时,还进行了大量的模拟研究.这些模拟以传统的近视算法为基准,将其应用在实时异构系统集成动态调度时的调度成功率与新算法进行比较,模拟结果表明,在多种任务参数取值下,新算法的调度成功率均高于传统的近视算法.     

一种求解多处理机调度问题的a-平坦化调度算法

在分析多处理机调度问题的基础上,提出了α-平坦的概念,并将其引入到多处理机调度问题中;基于此,提出了一种新的基于α-平坦的求解多处理机调度问题的算法。算法首先对作业集合做平坦化处理,然后再对处理后所得的新问题进行求解,最终获得原调度问题的一个近似解。实验结果表明,通过该算法可以求得较好的结果,相对于其它启发式算法,该算法具有较好的稳定性。     

多处理机调度问题的蚁群算法

建立了多处理机调度问题模型，分析了贪心法和模拟退火算法的优缺点。通过实例采用蚁群算法解决了此问题，结果表明该方法比较有效。     

基于图匹配的多处理机调度算法

本文对具有高通讯延迟的多处理机系统（机群系统）上的任务调度算法进行了研究，与以往算法主要考虑任务图的关键路径不同，本文给出了任务图的调度与其偶图匹配的对应关系，并由此提出了一种新的启发式算法，通过模拟试验显示本算法具有较好的调度效果。     

实时异构系统的动态调度算法研究

实时多处理器系统是解决复杂时应用的有效手段,目前对实时多处理器调度算法的研究却大多集中在同构系统上,对实时异构系统的调度则研究得比较少,提出了一种新的实时异构系统的动态调度算法,该算法采用了集中式的调度方案,同时,引入了一个新的任务分配策略,从而通过提高任务可行性而提高了算的调度成功率,此外,为了评估该算法的性能,还进行了大量的模拟研究,由于近视算法经简单修改便可以应用到实时异构系统的动态调度中,因此,在模拟研究中,以近视算法作为基准,将其应用于实时异构系统动态调度时的性能与新算法进行了比较,模拟结果显示,在多种任务参数的取值下,新算法的调度成功率均高于近视算法。     

一种混合粒子群与蚁群算法在多处理机调度中的应用研究

提出了一种基于蚁群优化和粒子群优化的混合算法以解决多处理机调度问题。这种混合算法利用蚁群算法和粒子群优化算法的特性,可以显著提高计算效率,具有较大的实用价值。     

一种新的组优先级动态实时调度算法

传统动态调度算法由于对优先级个数没有限制,在实际应用中往往受制约,达不到很好的调度性能.针对此问题,考虑硬实时抢占任务调度需要,提出一种新的组优先级动态实时调度算法.研究作业执行顺序改变对系统可调度性能的影响,给出作业分组可调度性能测试.新算法将满足分组可调度测试公式的作业作为一个任务组,各任务组之间按照最小截止期优先调度,任务组内按照最短作业优先的原则执行作业.仿真结果表明,与最小截止期优先等传统调度算法相比,新算法不仅能有效降低算法所需优先级个数,还能提高任务调度的成功率,缩短平均响应时间,减少任务切换次数.     

一种新的实时多处理器系统的动态调度算法

实时多处理器系统的动态调度算法一直是实时系统研究中的重要课题,而评价实时调度算法性能的一个最重要的指标是调度成功率.在近视算法的基础上提出了一种新的实时多处理器系统的动态调度算法--节约算法.在该算法中,提出了一个新的处理器选择策略,从而提高了算法的调度成功率.同时,为了研究节约算法的有效性,对其进行了大量的模拟,分析了一些任务参数的变化对算法调度成功率的影响,并与近视算法的调度成功率进行了比较.模拟结果显示,节约算法的调度成功率要优于近视算法.     

实时多处理器系统的动态分批优化调度算法

提出了一种实时多处理器系统的新的高效动态调度算法--动态分批优化调度算法,该算法突破了以往算法中一次只安排一项任务的做法,采用在每次扩充当前局部调度时,按一定规则在待调度的任务集中选取一批任务,对该批任务中的每项任务在每个处理器上运行构造目标函数,将问题转化为非平衡分配问题,一次性为这些任务都安排一个处理器或为每个处理器安排一项任务,使得这种安排具有最好的"合适性",以增大未安排任务的可行性.这种方法极大地提高了算法的调度成功率.同时,为了研究该算法的有效性,对其进行了大量的模拟,分析了一些任务参数的变化对算法调度成功率的影响,并与节约算法的调度成功率进行了比较.模拟结果显示,在节约算法的调度成功率小于10%的约束条件下,该算法的调度成功率大于90%,说明新算法的优势是非常明显的.     

基于分批优化的实时多处理器系统的集成动态调度算法

提出了一种基于分批优化的实时多处理器系统的集成动态调度算法，该算法采用在每次扩充当前局部调度时，通过对所选取的一批任务进行优化分配的策略以及软实时任务的服务质量QoS（quality of service）降级策略，以统一方式实现了对实时多处理器糸统中硬、软实时任务的集成动态调度．进行了大量的模拟研究，结果表明．在多种任务参数取值下，新算法的调度成功率均高于近视算法（Myopic Algorithm）．     

实时多处理器系统中基于能量节约的动态调度算法

当前处理器由于较高的能量消耗。导致处理器热量散发的提高及系统可靠性的降低，已经成为目前计算机领域较为关心的问题．然而目前一些有效降低能量消耗的技术大多针对单处理器系统，较少考虑多处理器系统．本文提出的调度算法针对多处理器系统，以最短任务优先调度为基础，结合其它有效技术，如共享空闲时间回收等，使得实时任务在其截止期内完成的同时能够有效地减低整个系统的能量消耗．针对独立任务集及具有依赖关系的任务集，本文提出两种算法：STFBA1及STFBA2（Shortest Task First—Based Algorithm）．与目前所知的有效算法相比，我们的算法具有更好的性能（调度长度及能量消耗）．     

实时多处理机系统BEST-FIT启发式容错调度

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

Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems

The utilization bound for earliest deadline first (EDF) scheduling is extended from uniprocessors to homogeneous multiprocessor systems with partitioning strategies. First results are provided for a basic task model, which includes periodic and independent tasks with deadlines equal to periods. Since the multiprocessor utilization bounds depend on the allocation algorithm, different allocation algorithms have been considered, ranging from simple heuristics to optimal allocation algorithms. As multiprocessor utilization bounds for EDF scheduling depend strongly on task sizes, all these bounds have been obtained as a function of a parameter which takes task sizes into account. Theoretically, the utilization bounds for multiprocessor EDF scheduling can be considered a partial solution to the bin-packing problem, which is known to be NP-complete. The basic task model is extended to include resource sharing, release jitter, deadlines less than periods, aperiodic tasks, non-preemptive sections, context switches, and mode changes.     

PLUFS: 一种开销敏感的周期任务在线多处理器节能实时调度算法

现有周期任务多处理器节能调度算法虽然在考虑处理器实际开销情况下可以实现较好的节能效果,但仍不能保证最优可调度性.针对嵌入式实时系统中不可忽视的状态切换开销,提出一种开销敏感的周期任务在线多处理器节能实时调度算法PLUFS.该算法通过TL面流调度模型与处理器实际切换开销模型相结合,在每个TL面的初始时刻、任务结束执行时刻实现节能调度,在不违反周期任务集最优可调度性的前提下,达到实时约束与能耗节余的合理折中.经过理论证明和模拟实验,结果表明：PLUFS算法不仅保证了周期任务集的最优可调度性,而且节能效果整体优于现有算法,能耗节余比现有算法提高约10%～20%.     

实时多处理器动态调度算法的研究与应用

实时多处理器系统的动态调度算法一直是实时系统研究中的重要课题。该文首先介绍了实时多处理器动态调度的几种方法,并对这些方法进行了分析、对比和研究。然后针对水下航行器制导系统多任务特点,讨论了水下航行器制导系统的动力学、运动学模型及控制、导引方程,并对其任务进行详细划分。最后结合任务的偏序关系、运行时间及截止期,对水下航行器多任务模型进行了实时多处理器动态调度,给出最佳调度方案。