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.     

Partitioned EDF scheduling on a few types of unrelated multiprocessors

A polynomial-time approximation scheme (PTAS) is derived for the partitioned EDF scheduling of implicit-deadline sporadic task systems upon unrelated multiprocessor platforms that are comprised of a constant number of distinct types of processors. This generalizes earlier results showing the existence of polynomial-time approximation schemes for the partitioned EDF scheduling of implicit-deadline sporadic task systems on (1) identical multiprocessor platforms, and (2) unrelated multiprocessor platforms containing a constant number of processors.     

The Non-preemptive Scheduling of Periodic Tasks upon Multiprocessors

The non-preemptive scheduling of periodic task systems upon processing platforms comprised of several identical processors is considered. The exact problem has previously been proven intractable even upon single processors; sufficient conditions are presented here for determining whether a given periodic task system will meet all deadlines if scheduled non-preemptively upon a multiprocessor platform using the earliest-deadline first scheduling algorithm. Supported in part by the National Science Foundation (Grant Nos. CCR-9988327 and ITR-0082866). Sanjoy Baruah is a professor of Computer Science at the University of North Carolina at Chapel Hill. He received his Ph.D. from the University of Texas at Austin in 1993. His research and teaching interests are in scheduling theory, real-time and safety-critical system design, and resource-allocation and sharing in distributed computing environments.     

An Upper Bound of Task Loads in a Deadline-D All Busy Period for Multiprocessor Global EDF Real-Time Systems

This paper addresses a number of mathematical issues related to multiprocessor global EDF platforms. We present a deadline-d all busy period and backward interference which are important concepts for multiprocessor EDF systems, and some general schedulability conditions for any studied job are proposed. We formally prove that at most m-1 different tasks’ jobs could contribute their execution time to an interval starting with a P_busy−d, and we propose an approach for computing an exact upper bound of the total deadline-d task load in a given interval. Therefore, the proposed results are important foundations for constructing exact schedulability analyses of global EDF scheduling systems.     

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

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

EDZL scheduling analysis

A schedulability test is derived for the global Earliest Deadline Zero Laxity (EDZL) scheduling algorithm on a platform with multiple identical processors. The test is sufficient, but not necessary, to guarantee that a system of independent sporadic tasks with arbitrary deadlines will be successfully scheduled, with no missed deadlines, by the multiprocessor EDZL algorithm. Global EDZL is known to be at least as effective as global Earliest-Deadline-First (EDF) in scheduling task sets to meet deadlines. It is shown, by testing on large numbers of pseudo-randomly generated task sets, that the combination of EDZL and the new schedulability test is able to guarantee that far more task sets meet deadlines than the combination of EDF and known EDF schedulability tests. In the second part of the paper, an improved version of the EDZL-schedulability test is presented. This new algorithm is able to efficiently exploit information on the slack values of interfering tasks, to iteratively refine the estimation of the interference a task can be subjected to. This iterative algorithm is shown to have better performance than the initial test, in terms of schedulable task sets detected.

<Emphasis FontCategory="SansSerif">LRE</Emphasis>-<Emphasis FontCategory="SansSerif">TL</Emphasis>: an optimal multiprocessor algorithm for sporadic task sets with unconstrained deadlines

This article presents a detailed discussion of LRE-TL (Local Remaining Execution-TL-plane), an algorithm that schedules hard real-time periodic and sporadic task sets with unconstrained deadlines on identical multiprocessors. The algorithm builds upon important concepts such as the TL-plane construct used in the development of the LLREF algorithm (Largest Local Remaining Execution First). This article identifies the fundamental TL-plane scheduling principles used in the construction of LLREF . These simple principles are examined, identifying methods of simplifying the algorithm and allowing it to handle a more general task model. For example, we identify the principle that total local utilization can never increase within any TL-plane as long as a minimal number of tasks are executing. This observation leads to a straightforward approach for scheduling task arrivals within a TL-plane. In this manner LRE-TL can schedule sporadic tasks and tasks with unconstrained deadlines. Like LLREF, the LRE-TL scheduling algorithm is optimal for task sets with implicit deadlines. In addition, LRE-TL can schedule task sets with unconstrained deadlines provided they satisfy the density test for multiprocessor systems. While LLREF has a O(n ²) runtime per TL-plane, LRE-TL’s runtime is O(nlog n) per TL-plane.     

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

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

Schedulability Analysis of Global Scheduling Algorithms on Multiprocessor Platforms

This paper addresses the schedulability problem of periodic and sporadic real-time task sets with constrained deadlines preemptively scheduled on a multiprocessor platform composed by identical processors. We assume that a global work-conserving scheduler is used and migration from one processor to another is allowed during a task lifetime. First, a general method to derive schedulability conditions for multiprocessor real-time systems will be presented. The analysis will be applied to two typical scheduling algorithms: earliest deadline first (EDF) and fixed priority (FP). Then, the derived schedulability conditions will be tightened, refining the analysis with a simple and effective technique that significantly improves the percentage of accepted task sets. The effectiveness of the proposed test is shown through an extensive set of synthetic experiments.     

一种基于EDF算法的多处理器实时调度算法

多处理器系统实时调度理论是目前实时系统研究的热点问题。EDF调度算法是目前流行的实时调度算法,有很多优点,但在多处理器系统应用中存在问题。论文研究了EDF调度算法在多处理器系统中的调度理论,在此基础上,提出了一种基于EDF算法的优先级驱动实时调度算法,算法充分利用了EDF调度算法的优点,较大程度地克服了EDF算法在多处理器系统中的调度缺点,并提供了较好的实时调度性能。     

一种同构多处理机动态实时调度算法

本文提出一种新型线性复杂度多处理机实时任务启发式调度算法,利用并行技术为动态实时系统提供较优解．使用大量存在可行调度的任务集合测试多处理机实时任务调度算法的性能,分析了几种主要参数对调度成功率的影响．实验表明新调度算法调度成功率较高,适用于不完全知晓任务参数的动态多处理机实时系统．     

Improved multiprocessor global schedulability analysis

A new technique was recently introduced by Bonifaci et al. for the analysis of real-time systems scheduled on multiprocessor platforms by the global Earliest Deadline First (EDF) scheduling algorithm. In this paper, this technique is generalized so that it is applicable to the schedulability analysis of real-time systems scheduled on multiprocessor platforms by any work-conserving algorithm. The resulting analysis technique is applied to obtain a new sufficient global Deadline Monotonic (DM) schedulability test. It is shown that this new test is quantitatively superior to pre-existing DM schedulability analysis tests; in addition, the degree of its deviation from any hypothetical optimal scheduler (that may be clairvoyant) is quantitatively bounded. A new global EDF schedulability test is also proposed here that builds on the results of Bonifaci et al. This new test is shown to be less pessimistic and more widely applicable than the earlier result was, while retaining the strong theoretical properties of the earlier result.     

Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible

Optimal online scheduling algorithms are known for sporadic task systems scheduled upon a single processor. Additionally, optimal online scheduling algorithms are also known for restricted subclasses of sporadic task systems upon an identical multiprocessor platform. The research reported in this article addresses the question of existence of optimal online multiprocessor scheduling algorithms for general sporadic task systems. Our main result is a proof of the impossibility of optimal online scheduling for sporadic task systems upon a system comprised of two or more processors. The result is shown by finding a sporadic task system that is feasible on a multiprocessor platform that cannot be correctly scheduled by any possible online, deterministic scheduling algorithm. Since the sporadic task model is a subclass of many more general real-time task models, the nonexistence of optimal scheduling algorithms for the sporadic task systems implies nonexistence for any model which generalizes the sporadic task model.     

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.     

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.     

An efficient approach for the multiprocessor non-preemptive strictly periodic task scheduling problem

Strict periodicity constraint is of great importance since it concerns some hard real-time systems where missing deadlines leads to catastrophic situations. However, the problem of schedulability analysis for non-preemptive strictly periodic tasks on a multiprocessor platform is even more intractable than the one with the common periodicity. In order to implement such systems, designers need effective tools based on fast and near-optimal solutions.This paper presents a schedulability analysis which results mainly in a, two versions, task assignment and start-time calculation algorithm. The first one targets the harmonic task periods case while the second one targets the non-harmonic task periods case. Each version is based on a sufficient uniprocessor schedulability test. In addition, for the non-harmonic case which is the most intractable, the uniprocessor sufficient schedulability test uses the strictly periodic task utilization factor. This factor stands for the fraction of time spent to execute a task while its strict periodicity and the ones of the already scheduled tasks are met. As a result, an efficient and easily implementable scheduling algorithm is proposed which begins by assigning tasks to processors then attributes a start-time to every task in such a way that strict periodicity and deadline constraints are met. The effectiveness of the proposed scheduling algorithm, in both versions, has been shown by a performance evaluation and comparisons with an optimal and a similar suboptimal solution.     

面向抖动优化的任务静态优先级指派算法

对任务相对截止时限进行优化设置是一种减少输出抖动的有效方法,但现有方法均是针对最早时限优先调度算法,不能适用于任务集采用静态优先级调度算法的场合.为此,提出通过优化优先级指派实现任务集的整体抖动最小化,并给出一种启发式的优先级指派算法.根据单调速率调度算法确定任务的初始优先级,以最小化局部抖动方式依次对任务的优先级进行再调整,从而得到近似最优的优先级指派.仿真实验结果表明,该算法能有效减少任务集的整体输出抖动.     

An optimal algorithm for scheduling soft aperiodic tasks indynamic-priority preemptive systems

The paper addresses the problem of jointly scheduling tasks with both hard and soft real time constraints. We present a new analysis applicable to systems scheduled using a priority preemptive dispatcher, with priorities assigned dynamically according to the EDF policy. Further, we present a new efficient online algorithm (the acceptor algorithm) for servicing aperiodic work load. The acceptor transforms a soft aperiodic task into a hard one by assigning a deadline. Once transformed, aperiodic tasks are handled in exactly the same way as periodic tasks with hard deadlines. The proposed algorithm is shown to be optimal in terms of providing the shortest aperiodic response time among fixed and dynamic priority schedulers. It always guarantees the proper execution of periodic hard tasks. The approach is composed of two parts: an offline analysis and a run time scheduler. The offline algorithm runs in pseudopolynomial time O(mn), where n is the number of hard periodic tasks and m is the hyperperiod/min deadline     

Precedence-constrained task allocation onto point-to-point networksfor pipelined execution

The problem of scheduling directed acyclic task flow graphs to multiprocessor systems using point-to-point networks is examined. An environment where the application has a strict throughput requirement is assumed. Pipelined parallelism is used to meet the throughput requirement. Communication and computation are completely overlapped. Each task and message has a periodic rate and deadline equal to the throughput requirement. A heuristic procedure based on preclustering, recursive mincut bipartitioning, and iterative improvement is proposed to reduce the maximum contention due to communication in the network, increasing the likelihood that messages meet their deadlines. The task assignment procedure takes into account the topology of the multiprocessor system and the distance between communicating tasks     

Parameter adaptation for generalized multiframe tasks: schedulability analysis,case study,and applications to self-suspending tasks

The generalized multiframe task model (GMF) extends the sporadic task model and multiframe task model. Each frame in the GMF model contains an execution time, a relative deadline, and a minimum inter-arrival time. These parameters are fixed after task specification time in the GMF model. However, multimedia and adaptive control systems may be overloaded and no longer stabilized when the task parameters in such systems are not flexible. In order to address this problem, deadlines and periods of frames may change to alleviate temporal overload, e.g., in the parameter adaptation and elastic scheduling model. In this paper, we propose a new model GMF-PA (the GMF model with parameter adaptation). This model allows task parameters to be flexible in arbitrary-deadline systems. A necessary schedulability test based on mixed-integer linear programming is given to check the schedulability under EDF scheduling and optimally assign frame deadlines and periods at the same time. We also prove that the test is a sufficient and necessary schedulability test when frame deadlines and periods must be integers. An approximation algorithm is also deployed to reduce computational running time and indicates a sufficient schedulability test in general. The speed-up factor of our approximation algorithm is \(1+\epsilon \) where \(\epsilon \) can be arbitrarily small, with respect to the exact schedulability test of GMF-PA tasks under EDF. We also apply the GMF model to self-suspending tasks. By extending recent work on scheduling self-suspending tasks, we remove the assumption that frame deadlines are equally assigned in self-suspending tasks, and the system is extended from constrained-deadline systems to arbitrary-deadline systems. We have done extensive experiments to show that the schedulability ratio is improved using our techniques in our GMF-PA model.