提高软非周期任务响应性能的调度算法

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

两种经典实时调度算法的研究与实现

速率单调（RM）调度和最早截止期限优先（EDF）调度在实时调度领域占有重要低位。基于一个x86体系结构的小系统上设计实现RM和EDF调度算法,并在不同的工作负载下,以任务截止期错失率作为衡量不同任务调度算法性能优劣的指标,对两种算法进行了性能分析和比较。在通常情况下,RM和EDF都可以保证任务成功调度,EDF算法可承受较多的工作负载。但是随着负载的增加,EDF算法性能急剧下降,到一定过载程度,EDF算法性能低于RM算法。     

一种多QoS目标约束的云计算任务调度策略

针对云计算环境下大量用户任务请求各异的服务质量（Quality of Service, QoS）调度目标要求,通过综合考虑云用户任务的截止时间底线、调度预算等QoS目标约束条件以及各类可用资源的性能参数,对任务调度的多QoS目标约束条件进行形式化建模,基于构造的隶属度函数将多QoS目标约束的优化求解问题转化成一个单目标约束的优化问题,对转化后的单目标约束优化问题进行近似求解,最终提出一种多QoS目标约束的云计算任务调度策略。在CloudSim模拟器上的仿真结果表明,提出的多QoS目标约束的云计算任务调度策略总体上优于传统的Min-min算法以及改进的以QoS为导向的Min-min算法。     

基于RM与EDF的实时混合调度算法研究

通过对实时系统中静态调度算法RM和动态调度算法EDF的研究与分析,针对两种调度算法在实际应用中的问题,提出了一种基于阈值δ的混合调度算法,将RM与EDF调度算法相结合,并从数学角度描述了混合调度算法的可调度性与实时任务的周期、执行时间等属性之间的关系,给出了混合调度算法可调度性的充分必要条件。最后用实验验证了混合调度算法的有效性。     

基于网络带宽约束的网格任务调度算法研究

在对网格计算任务调度算法的研究中,分析一般适应性调度启发算法即最小一最小(Min-min)算法的不足,在最小一最小(Min-min)算法的基础上,加入考虑QoS方面主要是网络带宽因素的任务调度算法.对以上算法做了实验并指出下一步的研究方向.     

嵌入式实时操作系统任务调度算法的改进与应用

在嵌入式系统中,任务调度器的好坏很大程度上决定了系统的性能.针对经典的速率单调(RM)调度算法以任务的周期作为优先级的评测标准,容易导致某些周期长且重要的任务错过截止期限,而当任务数量趋于无穷时,CPU的利用率仅为69%的特点,提出一种新的静态调度算法-NSRL.该算法在任务控制块(TCB)中增加两个域,分别为任务的重要度和裕度为零的时刻.在高优先级任务优先执行的前提下,重要度较高且未执行的任务当且仅当裕度为零时,具有较高的优先权可以抢占当前任务运行.通过理论分析和具体实验,该方法降低了任务截止期错失率,提高了CPU利用率,可以更有效地调度实时任务,在无线宽带移动计算中得到了较好应用.     

混合云中基于数据保护的耦合任务调度策略

经济因素是驱动混合云负载调度和资源管理的关键因素,同时数据机密和安全性、任务依赖性等问题也对调度策略提出更高的要求。针对以上问题提出综合优化成本开销的调度策略,不仅考虑数据安全迁移和外包运行的总成本,也深入分析应用程序模型中任务依赖性调度。最后通过云仿真平台的实验仿真,并与现有的资源调度算法进行对比,实验结果表明该混合云调度策略在提高吞吐能力和降低总体成本开销方面的综合改善。     

一种基于代价抢占的混合可重构任务调度算法*

针对同时存在独立任务和相依性任务的混合可重构任务调度,提出了基于代价抢占的混合可重构任务实时调度算法。提出了相依性任务等价运行截止时刻的计算方法,使混合可重构任务按照配置截止时刻排队配置。针对相依性任务调度特点,分析得到了相依性任务集合调度失败的充分条件,提前判定和丢弃无法调度成功的相依性任务集合;通过有限预配置防止相依性任务无效占用可重构资源;通过基于代价抢占减少调度失败任务个数。仿真结果表明,该调度算法提高了任务调度成功率。     

截止时限为关键参数的混合关键级实时任务调度研究

混合关键级系统 (mixed criticality system)的研究源于在单一平台上执行多个重要级不同的功能,当前混合关键级调度研究,一般考虑高关键级任务在不同关键级运行模式表现为或周期或计算时间不同,即以任务释放时间间隔和最差情况执行时间为关键参数.但截至时限(dendline)也是实时任务的重要时间参数,尤其是对硬实时任务,以截止时限作为关键参数进行相应混合关键级调度的研究尚是空白.针对此问题,以截止时限作为关键参数,以响应时间分析为基础,对单处理器平台中的混和关键级任务的可调度性进行分析,并提出了一种预提升关键级的调度算法RCLA(raising critical-level in advance),在低关键级运行模式下,高关键级低优先级任务有限度地提前抢占低关键级高优先级任务的执行,既确保了满足高关键级任务在不同关键级运行模式下的截止时限,也让尽可能多的任务可以被调度执行,使得计算资源得以充分利用.仿真结果验证了RCLA算法的有效性.     

基于多维QoS约束的网格任务调度算法

针对现有网格任务调度算法存在的问题,提出一种基于多维服务质量(QoS)约束的算法,综合考虑2种造成任务停滞的原因,从多维QoS参数匹配最优出发,利用过滤值进一步提高网格系统的利用率,减少任务的完成时间,降低任务的失效率,从而更好地满足用户的QoS需求。仿真实验结果表明,该算法符合网格的复杂环境,且是有效的。     

Dynamic Real-time Scheduling of Firm Periodic Tasks with Hard and Soft Aperiodic Tasks

In this paper, we address the problem of the dynamic scheduling of skippable periodic task sets (i.e., period tasks allowing occasional skips of instances), together with aperiodic tasks. Scheduling of tasks is handled thanks to the merging of two existing approaches: the Skip-Over task model and the EDL (Earliest Deadline as Late as possible) aperiodic task server. The objective is to provide two on-line scheduling algorithms, namely EDL-RTO and EDL-BWP, in order to minimize the average response time of soft aperiodic requests, while ensuring that the QoS (Quality of Service) of periodic tasks will never be less than a specified bound. We also extend our results to the acceptance of sporadic tasks (i.e., aperiodic tasks with deadlines). We show that these novel scheduling algorithms have better performance compared to related algorithms regarding aperiodic response time and acceptance ratio. Audrey Marchand guaduated in Computer Engineering at the Ecole polytechnique of the University of Nantes (France), in 2002. She is currently a PhD student at the University of Nantes. Her research interests include real-time scheduling theory, aperiodic service mechanisms, quality of service guarantees in soft real-time systems, and Linux-based real-time operating systems and applications. Maryline Chetto received the degree of Docteur de 3ème cycle in control engineering and the degree of Habilitée à Diriger des Recherches in Computer Science from the University of Nantes, France, in 1984 and 1993, respectively. From 1984 to 1985, she held the position of Assistant professor of Computer Science at the University of Rennes, while her research was with the Institut de Recherche en Informatique et Systèmes Aléatoires, Rennes. In 1986, she returned to Nantes and is currently a professor with the Institute of Technology of the University of Nantes. She is conducting her research at IRCCyN. Her main research interests include scheduling and fault-tolerance technologies for real-time applications. She has published more than 60 journal articles and conference papers in the area of real-time operating systems. She is the leader of a French national R&D project, namely Cleopatre, supported by the French government, which aims to provide free open source real-time solutions.     

Scheduling algorithm for real-time tasks using multiobjective hybrid genetic algorithm in heterogeneous multiprocessors system

The scheduling problem for real-time tasks on multiprocessor is one of the NP-hard problems. This paper proposes a new scheduling algorithm for real-time tasks using multiobjective hybrid genetic algorithm (mohGA) on heterogeneous multiprocessor environment. In solution algorithms, the genetic algorithm (GA) and the simulated annealing (SA) are cooperatively used. In this method, the convergence of GA is improved by introducing the probability of SA as the criterion for acceptance of new trial solution.     

云环境下周期和非周期混合实时任务双容错调度算法

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

A Feasibility Decision Algorithm for Rate Monotonic and Deadline Monotonic Scheduling

Rate monotonic and deadline monotonic scheduling are commonly used for periodic real-time task systems. This paper discusses a feasibility decision for a given real-time task system when the system is scheduled by rate monotonic and deadline monotonic scheduling. The time complexity of existing feasibility decision algorithms depends on both the number of tasks and maximum periods or deadlines when the periods and deadlines are integers. This paper presents a new necessary and sufficient condition for a given task system to be feasible and proposes a new feasibility decision algorithm based on that condition. The time complexity of this algorithm depends solely on the number of tasks. This condition can also be applied as a sufficient condition for a task system using priority inheritance protocols to be feasible with rate monotonic and deadline monotonic scheduling.     

Scheduling of Offset Free Systems

In this paper, we study the problem of scheduling hard real-time periodic tasks. We consider independent tasks which are characterized by a period, a hard deadline and a computation time, but where the offsets may be chosen by the scheduling algorithm. We first show that we can restrict the problem by considering non-equivalent offset assignments. More precisely, we show that there are finitely many non-equivalent offset assignments and we propose a method to reduce significantly this number and consider only the minimal number of non-equivalent offset assignments. We then propose an optimal offset assignment rule which considers only the non-equivalent offset assignments. However the number of combinations remains exponential; for this reason, we also propose a nearly optimal algorithm with a more reasonable time complexity.     

Multicycle Polling Scheduling Algorithms for FieldBus Networks

The paper deals with the scheduling of periodic information flow in a FieldBus environment. The scheduling problem is defined from an analytical point of view, giving a brief survey of the most well-known solutions. One of these is called multicycle polling scheduling, which is based on the hypothesis that all the production periods of the periodic processes to be scheduled are harmonic. Although in some process control or manufacturing scenarios, this hypothesis may be acceptable, there are many real industrial processes to which it cannot be applied. The aim of the paper is to make a contribution towards solving the scheduling problem. It essentially concerns extension of the theory on which multicycle polling scheduling is based to a much more realistic and general scenario, where the periods of all the processes to be scheduled have arbitrary values. The authors present a new formulation of multicycle polling scheduling, called extended multicycle polling scheduling, and demonstrate that it comprises the scenario currently considered in the literature. Two algorithmic solutions for extended multicycle polling scheduling are then proposed, giving a computational complexity analysis which will highlight the capability of the algorithmic scheduling solutions to be performed on-line. The paper concludes by comparing the multicycle polling scheduling approach known in literature and the one presented in the paper. Comparison is performed by evaluating the use of available bandwidth to serve both periodic and asynchronous traffic in the two approaches.     

具有依赖关系的周期任务实时调度方法

随着多核技术在嵌入式领域的快速发展,越来越多的功能被集成在同一个平台上,任务之间的关系越来越复杂.而当前大多数的实时周期任务的调度模型都是不考虑任务之间关系的相互独立的任务模型.文中则针对具有依赖关系的周期任务,提出了一种基于ST(Simple-Tree)的实时周期任务调度模型,通过该模型来维护任务之间的依赖关系.此外,为了有效地提高系统利用率以及降低死限丢失率,文中还提出了可延迟时间越短越优先的调度方法并和RM算法、EDF算法进行仿真实验比较,结果表明该方法具有较高的核利用率和较低的死限丢失率.     

具有模糊多目标的网格任务调度算法

在异构的网格计算平台上,网格中有用户、资源管理员、组织管理者等实体,这些实体对网格的管理、使用、维护、安全性、可靠性等目标都提出了要求,并且这些目标有时是不可量化的。针对具有模糊多目标网格计算的任务调度问题,提出模糊多目标网格任务调度模型,使用模糊化等式对多目标进行模糊处理,给出求解该模型的模糊化定理,并对该定理进行证明。利用差分优化算法无需目标函数连续可微的特点,提出使用模糊差分优化算法完成模糊多目标的网格任务调度。实验结果表明,模糊差分优化算法较现有算法在执行时间上处于劣势,但在可靠性、安全性和丢失任务数三个指标上要优于现有算法。