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.     

EDF调度算法可调度性分析方法的改进研究

任务集的可调度性分析是实时系统研究和应用的关键问题。针对抢占式与不可抢占式EDF(earliest deadline first)调度算法, 分别给出了实时任务集新的可调度性测试条件, 针对任务集为可调度时可以实现快速判定。通过与已有的EDF算法的可调度性判定充要条件相结合, 提出了改进的抢占式与不可抢占式EDF算法的可调度性分析方法。仿真实验表明, 相对现有EDF算法的可调度性分析方法, 所提出的方法能有效提高算法性能。     

A New Approach for Scheduling of Parallelizable Tasks in Real-Time Multiprocessor Systems

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.     

基于Linux的多核实时任务调度算法改进

嵌入式实时系统通常被实现为多任务系统,以满足多个外部输入的响应时间的最后期限约束。Linux内核中已经实现了基于EDF(Earliest Deadline First)调度算法的DL调度器,使得实时任务能在截止期限内运行完成。但对于多核处理器,由于实时任务在EDF算法下会出现Dhall效应,论文对 Linux内核中实时任务调度算法进行了改进。在EDF算法的基础上,实现LLF(Least Laxity First)调度算法并对其加以改进,通过降低任务上下文切换频率以及减少松弛度的计算来减小调度过程中的颠簸现象。实验证明该方法既避免了Dhall效应,又减少了任务上下文切换带来的系统开销,并使得任务能在截止期限内完成调度,取得了较好的调度性能。     

交换以太网中实时消息截止期划分算法研究

为解决交换式以太网中实时消息在发送及接收链路上的截止期划分问题,首先给出了非抢占式EDF调度算法的可调度性分析方法,并分析了消息的提前释放对非抢占式EDF调度算法可调度性的影响,在此基础上提出了新的截止期划分算法(MDPS)。算法通过计算可满足调度条件时消息在发送链路及接收链路截止期应该划分的下限,并结合截止期的松驰量实现实时消息在发送及接收链路上的截止期划分。算法实验比较和分析表明,该算法在提高网络聚合带宽、减小消息的错失率方面明显优于现有的ADPS算法。     

Dual-Priority versus Background Scheduling: A Path-Wise Comparison

In this paper, two well-known scheduling policies for real-time systems, namely background scheduling (BS) and dual-priority (DP) are compared in terms of response times for soft real-time traffic (SRT). It is proved in the preemptive as well as in the non-preemptive case that, when the SRT traffic is FIFO, the DP policy always outperforms BS for all instances of SRT tasks. When the SRT traffic is not FIFO but if all tasks are of equal size then, in the non-preemptive case, the average response times is shown to be always better under DP than under BS. As a complementary result, some non-FIFO examples where BS behaves better than DP for some SRT tasks but also on the average of the SRT response times, are given. The proofs are based on a trajectorial method that may be used for comparing other scheduling policies.     

软件容错模型中的容错实时调度算法

在软件容错模型的容错实时调度算法中,主部分可执行性的预测精度是影响调度算法性能的关键.针对此问题提出了DPA(deep-prediction based algorithm)和EDPA(EDF-based DPA)算法.算法考虑当前时间至替代部分通知时间之间的任务执行情况,通过构建预测表对待执行主部分的可执行性进行精确预测.当主部分不发生错误时算法根据预测表调度任务. DPA依照预测表中通知时间的先后顺序调度主部分,而EDPA则按照EDF算法调度预测表中的主部分.模拟结果表明,DPA和EDPA较目前同类算法可获得更多的主部分执行时间,降低CPU的消耗.当软件错误率较低、任务周期较短时,算法能够以较小的调度开销获得较高的调度性能.     

A Method for Performance Analysis of Earliest-Deadline-First Scheduling Policy

This paper introduces an analytical method to approximate the fraction of jobs missing their deadlines in a soft real-time system when the earliest-deadline-first (EDF) scheduling policy is used. In the system, jobs either all have deadlines until the beginning of service (DBS) and are non-preemptive, or have deadlines until the end of service (DES) and are preemptive. In the former case, the system is represented by an M/M/m/EDF+G model, i.e., a multi-sever queue with Poisson arrival, exponential service, and generally distributed relative deadlines. In the latter case, it is represented by an M/M/1/EDF+G model, i.e., a single-server queue with the same specifications as before. EDF is known to be optimal in both of the above cases. The optimality property of EDF scheduling policy is used for the estimation of a key parameter, namely the loss rate when there are n jobs in the system. The estimation is possible by assuming an upper bound and a lower bound for this parameter and then linearly combining these two bounds together. The resulting Markov chains can then be easily solved numerically. Comparing numerical and simulation results, we find that the existing errors are relatively small.     

Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors

The scheduling of systems of periodic tasks upon multiprocessor platforms is considered. Utilization-based conditions are derived for determining whether a periodic task system meets all deadlines when scheduled using the earliest deadline first scheduling algorithm (EDF) upon a given multiprocessor platform. A new priority-driven algorithm is proposed for scheduling periodic task systems upon multiprocessor platforms: this algorithm is shown to successfully schedule some task systems for which EDF may fail to meet all deadlines.     

基于软件容错的动态实时调度算法

在硬实时系统中，由于任务超时完成将会导致灾难性后果，因而硬实时系统具有严格的时间及可靠性限制条件．目前实时容错调度算法大多针对硬件的容错，很少考虑软件运行的故障．提出了一种类似EDF的软件容错的动态实时调度算法PKSA(Probng-step Algorithm)，本算法在任务执行过程中，通过若干试探性检测步骤，提高了任务可执行性的预测，尽可能地避免了任务早期的失败对后续任务的影响，因此提高了任务的完成率，并同时有效地减少了浪费的CPU时间片．通过实验测试．同目前所知的同类算法相比，具有更佳的调度性能-调度成本比.     

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

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

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

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

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

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

Tardiness bounds under global EDF scheduling on a multiprocessor

We consider the scheduling of a sporadic real-time task system on an identical multiprocessor. Though Pfair algorithms are theoretically optimal for such task systems, in practice, their runtime overheads can significantly reduce the amount of useful work that is accomplished. On the other hand, if all deadlines need to be met, then every known non-Pfair algorithm requires restrictions on total system utilization that can approach approximately 50% of the available processing capacity. This may be overkill for soft real-time systems, which can tolerate occasional or bounded deadline misses (i.e. bounded tardiness). In this paper we derive tardiness bounds under preemptive and non-preemptive global when the total system utilization is not restricted, except that it not exceed the available processing capacity. Hence, processor utilization can be improved for soft real-time systems on multiprocessors. Our tardiness bounds depend on the total system utilization and per-task utilizations and execution costs—the lower these values, the lower the tardiness bounds. As a final remark, we note that global may be superior to partitioned for multiprocessor-based soft real-time systems in that the latter does not offer any scope to improve system utilization even if bounded tardiness can be tolerated.

基于EDF算法的可行性判定及实现

实时调度算法是实时系统中的关键技术。验证实时调度算法的可行性是在实时系统中实施某种调度算法的必经环节。在介绍实时系统中常用的各种实时调度算法,包括固定优先级调度算法和动态优先级调度算法基础上,详细分析了动态优先级调度算法EDF算法的运算过程和使用条件。提出了该算法在实际应用中存在的问题。针对该硬实时调度算法,提出了分别在简单模型上和复杂模型上如何判定实时任务的可行性。为实际应用中实现该实时调度算法确定了依据。     

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

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

Static scheduling of multiple workflows with soft deadlines in non-dedicated heterogeneous environments

Typical patterns of using scientific workflows include their periodical executions using a fixed set of computational resources. Using the statistics from multiple runs, one can accurately estimate task execution and communication times to apply static scheduling algorithms. Several workflows with known estimates could be combined into a set to improve the resulting schedule. In this paper, we consider the mapping of multiple workflows to partially available heterogeneous resources. The problem is how to fill free time windows with tasks from different workflows, taking into account users’ requirements of the urgency of the results of calculations. To estimate quality of schedules for several workflows with various soft deadlines, we introduce the unified metric incorporating levels of meeting constraints and fairness of resource distribution.The main goal of the work was to develop a set of algorithms implementing different scheduling strategies for multiple workflows with soft deadlines in a non-dedicated environment, and to perform a comparative analysis of these strategies. We study how time restrictions (given by resource providers and users) influence the quality of schedules, and which scheme of grouping and ordering the tasks is the most effective for the batched scheduling of non-urgent workflows. Experiments with several types of synthetic and domain-specific sets of multiple workflows show that: (i) the use of information about time windows and deadlines leads to the significant increase of the quality of static schedules, (ii) the clustering-based scheduling scheme outperforms task-based and workflow-based schemes. This was confirmed by an evaluation of studied algorithms on a basis of the CLAVIRE workflow management platform.     

A new real time disk-scheduling method based on GSR algorithm

Disk scheduling has an important role in QOS guarantee of soft real-time environments such as video-on-demand and multimedia servers. Since now, some disk-scheduling algorithms have been proposed to schedule real-time disk requests. One of the most recent algorithms is global seek-optimizing real-time (GSR) that schedules the disk requests with different ready times by a global regrouping scheme. In the present paper, we propose a real-time disk-scheduling algorithm based on GSR that is called IGSR (improved GSR). IGSR creates the scan-groups of the requests and tries to find a good feasible schedule by optimized grouping with considering another chance for tasks that miss their deadlines at initial grouping. With regard to the admission policy of tasks, two different version of proposed method are presented: the first one has been designed for the case that all the disk requests available simultaneously and second one has been designed for the case that requests are admitted dynamically (GSR does not support the second one). It means that in the second case, the request queue may change when a task is running but in the first one it does not change. Simulation results showed IGSR outperformed GSR and some other related works in terms of maximum supportable streams, number of missed deadlines, and disk throughput.     

Real-time task scheduling by multiobjective genetic algorithm

Real-time tasks are characterized by computational activities with timing constraints and classified into two categories: a hard real-time task and a soft real-time task. In hard real-time tasks, tardiness can be catastrophic. The goal of hard real-time tasks scheduling algorithms is to meet all tasks’ deadlines, in other words, to keep the feasibility of scheduling through admission control. However, in the case of soft real-time tasks, slight violation of deadlines is not so critical.In this paper, we propose a new scheduling algorithm for soft real-time tasks using multiobjective genetic algorithm (moGA) on multiprocessors system. It is assumed that tasks have precedence relations among them and are executed on homogeneous multiprocessor environment.The objective of the proposed scheduling algorithm is to minimize the total tardiness and total number of processors used. For these objectives, this paper combines adaptive weight approach (AWA) that utilizes some useful information from the current population to readjust weights for obtaining a search pressure toward a positive ideal point. The effectiveness of the proposed algorithm is shown through simulation studies.     

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

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