基于多处理器嵌入式系统调度算法的研究

本文浅析了在多处理器体系结构上的调度实时任务的各种不同方法。我们首先比较了这些不同的解决方案，然后描述了一种调度任务集的方法。该方法基于端对端的任务调度，考虑任务间的线性优先约束以及任务对资源的需求。同时．这种调度方法的另外一个目的是尽量减少处理器间的通信代价。这个模型也考虑了不同处理器之间的不同通信带宽以及各种处理器拥有不同的处理性能。     

基于多处理器嵌入式系统调度算法的研究

本文浅析了在多处理器体系结构上的调度实时任务的各种不同方法.我们首先比较了这些不同的解决方案,然后描述了一种调度任务集的方法.该方法基于端对端的任务调度,考虑任务间的线性优先约束以及任务对资源的需求.同时-这种调度方法的另外一个目的是尽量减少处理器间的通信代价.这个模型也考虑了不同处理器之间的不同通信带宽以及各种处理器拥有不同的处理性能.     

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

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

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

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

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

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

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

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

一个多处理器实时线程调度算法的计算机模拟及分析

本文介绍了对作者提出的一种基于线程的、动态的、非抢占的多处理器实时任务调度算法的计算机模拟和结果分析，表明该算法在单处理器情况下比许多单处理器实时任务调度算法的调度频率高，在多处理器情况下的调度效率也较高。     

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

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

多处理器系统实时调度的可预测性

在多处理器实时系统中,由于调度的不规则性,系统的可预测性判定问题尤为重要。针对多处理器系统中实时任务调度的可预测性问题,给出了不可预测的实时任务集反例,证明了一种可预测的实时任务集合。对于多处理器实时系统中常用的最早截止期零松弛调度算法(earliest deadline zero laxity,EDZL)的可预测性,利用EDZL算法的基本性质,用一种简捷的方法证明了EDZL算法是可预测的。通过仿真系统验证了证明的正确性,该方法可用于多处理器及分布式实时系统的设计和验证。     

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

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

改进的异构多处理器的实时任务调度算法研究*

现有的很多调度算法存在时间复杂度过高或调度成功率低的问题。提出一种新的调度算法(HRTSA),提高实时任务的调度成功率。HRTSA首先通过METC策略初始化分簇,降低算法的时间复杂度;再在放置任务时根据处理器的负载均衡进行处理器负载的有效控制;最后通过任务复制调度以提高任务调度成功率。对比实验分析表明提出的HRTSA算法时间复杂度与RTSDA相比较低,调度成功率较高。     

改进型蚁群算法的多处理机任务调度研究

蚁群算法是一种新型的模拟进化算法,具有正反馈、分布式计算等特点,是一种解决组合优化问题的有效算法。在介绍蚁群算法基本原理以及探讨该算法的缺陷基础上,针对多处理器任务调度问题,提出了一种基于改进型蚁群算法的调度策略。仿真研究表明,该算法具有优良的全局优化性能,效果令人满意。     

A new fair scheduling algorithm for periodic tasks on multiprocessors

We present a new scheduling algorithm, called PL that is work-conserving and in terms of schedulability, optimal on multiprocessors for a synchronous periodic task set. The PL algorithm is a laxity based algorithm and ensures execution of a task with approximate proportional fairness at each task's period. Existing optimal algorithms on multiprocessors may cause excessive scheduling decisions and preemptions or may not be applied in a discrete environment. The proposed algorithm can be applied in a discrete environment and reduce the number of scheduling decisions and preemptions compared with a Pfair algorithm.     

多处理器并行EDPF优化实时调度算法

实时多处理器系统的任务调度问题始终都是一个重要课题。针对该系统须保证任务截止期和有效性的特点,提出了一种并行EDPF（Earliest Deadline and Processing Time First）优化调度算法。该算法适用于可并行任务,并在考虑到了任务集的截止期和资源因素基础上,加入了运行时间因素,达到了减少调度返回次数以及提高有效性的目的。最后通过大量的仿真,分析了一些必要参数对调度成功率的影响,并通过比较证明了该算法明显优于Myopic算法。     

Supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks

Supervisory control theory is a well-established theoretical framework for feedback control of discrete event systems whose behaviours are described by automata and formal languages. In this article, we propose a formal constructive method for optimal fault-tolerant scheduling of real-time multiprocessor systems based on supervisory control theory. In particular, we consider a fault-tolerant and schedulable language which is an achievable set of event sequences meeting given deadlines of accepted aperiodic tasks in the presence of processor faults. Such a language eventually provides information on whether a scheduler (i.e., supervisor) should accept or reject a newly arrived aperiodic task. Moreover, we present a systematic way of computing a largest fault-tolerant and schedulable language which is optimal in that it contains all achievable deadline-meeting sequences.     

Safe self-scheduling: A parallel loop scheduling scheme for shared-memory multiprocessors

In this papaer was present Safe Self-Scheduling (SSS), a new scheduling scheme that schedules parallel loops with variable length iteration execution times not known at compile time. The scheme assumes a shared memory space. SSS combines static scheduling with dynamic scheduling and draws favorable advantages from each. First, it reduces the dynamic scheduling overhead by statically scheduling a major portion of loop iterations. Second, the workload is balanced with a simple and efficient self-scheduling scheme by applying a new measure, thesmallest critical chore size. Experimental results comparing SSS with other scheduling schemes indicate that SSS surpasses other scheduling schemes. In the experiment on Gauss-Jordan, an application that is suitable for static scheduling schemes, SSS is the only self-scheduling scheme that outperforms the static scheduling scheme. This indicates that SSS achieves a balanced workload with a very small amount of overhead. This research has been supported in part by the National Science Foundation under Contract No. CCR-9210568.     

Improving energy efficiency of asymmetric chip multithreaded multiprocessors through reduced OS noise scheduling

The performance of the emerging chip multithreaded symmetric multiprocessors (SMPs) is of great importance to the high performance computing community. However, the growing power consumption of such systems is of increasing concern, and techniques that can be used to increase the overall system power efficiency while sustaining the performance are very desirable. Operating system (OS) noise can have a dramatic effect on the system performance. Effectively handling the smaller OS tasks while simultaneously preserving application thread synchronicity leads to gains in the overall system efficiency. Recently, under a fixed power budget, asymmetric multiprocessors (AMP) have been proposed to improve the performance of multithreaded applications. An AMP in this context is a multiprocessor system in which its processors are not operating at the same frequency. This paper proposes two simple scheduling methods that reduce the impact of OS noise, while simultaneously taking advantage of an opportunity to increase the overall machine energy efficiency on AMP servers. Prototyping AMPs on a commercial 2‐way dual‐core Hyper‐Threaded (HT) Intel Xeon SMP server, using real power measurements across six SPEC OpenMP applications, indicates that the first proposed scheduler performs better on average for HT‐enabled systems, whereas the second scheduler is superior on average for HT‐disabled systems. Copyright © 2009 John Wiley & Sons, Ltd.