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.

基于CAN总线实时应用的可靠调度性研究

CAN总线是一种高级的串行通信协议，适用于各种分布式控制系统。在实时应用中，标准的CAN协议使用静态优先级算法，对传输信道的利用率比较低。对基于CAN总线通信的动态优先级调度算法进行研究后，提出了一种基于指数分配方式的MTS算法，在保证强实时性消息的同时兼顾了低优先级消息的公平性。  

An analysis of global edf schedulability for arbitrary-deadline sporadic task systems

Recent results on the global multiprocessor edf scheduling of sporadic task systems are, for the most part, applicable only to task systems in which each task’s relative deadline parameter is constrained to be no larger than its minimum inter-arrival separation. This paper introduces new analysis techniques that allow for similar results to be derived for task systems in which individual tasks are not constrained in this manner. For tasks with deadlines greater than their minimum inter-arrival separation, two models are considered, with and without an implicit intra-task job precedence constraint. The new analyses yield schedulability conditions that strictly dominate some previously proposed tests that are generally accepted to represent the current state of the art in multiprocessor edf schedulability analysis, and permits the derivation of an improved speed-up bound.

Measuring the Performance of Schedulability Tests

The high computational complexity required for performing an exact schedulability analysis of fixed priority systems has led the research community to investigate new feasibility tests which are less complex than exact tests, but still provide a reasonable performance in terms of acceptance ratio. The performance of a test is typically evaluated by generating a huge number of synthetic task sets and then computing the fraction of those that pass the test with respect to the total number of feasible ones. The resulting ratio, however, depends on the metrics used for evaluating the performance and on the method for generating random task parameters. In particular, an important factor that affects the overall result of the simulation is the probability density function of the random variables used to generate the task set parameters. In this paper we discuss and compare three different metrics that can be used for evaluating the performance of schedulability tests. Then, we investigate how the random generation procedure can bias the simulation results of some specific scheduling algorithm. Finally, we present an efficient method for generating task sets with uniform distribution in a given space, and show how some intuitive solutions typically used for task set generation can bias the simulation results.This work has been partially supported by the European Union, under contract IST-004527, and by the Italian Ministry of University Research (MIUR), under contract 2003094275.Enrico Bini received the Ph.D. in Computer Engineering from Scuola Superiore SantAnna in Pisa, in October 2004. In 2000 he received the Laurea degree in Computer Engineering from Università di Pisa and, one year later, he obtained the Diploma di Licenza from the Scuola Superiore SantAnna. In 1999 he studied at Technische Universiteit Delft, in the Nederlands, by the Erasmus student exchange program. In 2001 he worked at Ericsson Lab Italy in Roma. In 2003 he was a visiting student at University of North Carolina at Chapel Hill, collaborating with prof. Sanjoy Baruah. His research interests cover scheduling algorithms, real-time operating systems, embedded systems design and linear programming.Giorgio Buttazzo is an Associate Professor of Computer Engineering at the University of Pavia, Italy. He graduated in Electronic Engineering at the University of Pisa in 1985, received a Master in Computer Science at the University of Pennsylvania in 1987, and a Ph.D. in Computer Engineering at the Scuola Superiore S. Anna of Pisa in 1991. During 1987, he worked on active perception and real-time control at the G.R.A.S.P.  

Real-Time Disk Scheduling for Multimedia Applications with Deadline-Modification-Scan Scheme

Real-timedisk scheduling (RTDS) is important for time-critical multimediaapplications. In conventional approaches of real-time disk scheduling,such as SCAN-EDF, the seek-optimizing SCAN scheme is appliedto reduce the disk service time of the real-time EDF schedule.Since only tasks with the same deadline are seek-optimized, theobtained improvement of SCAN-EDF is limited. In this paper, basedon the maximum-scannable-group (MSG) concept, a deadline-modification-scan (DMS or DM-SCAN) algorithm is proposed.Our algorithm uses MSG to automatically decide the suitable taskgroups for seek-optimizing. Based on the MSG concept, we repeatedlyapply DMS to further increase disk throughput to support moretasks. We have implemented the proposed algorithm on UnixWare2.01. The appropriate problem behaviors and parameter valuesto yield good solutions are investigated. Experiments show thatDMS is better than conventional approaches in both the obtaineddisk throughput and the supported tasks. Moreover, our proposedapproach can schedule task sets that are not schedulable by EDFand SCAN-EDF.  

Generalization of EDF and LLF: Identifying All Optimal Online Algorithms for Minimizing Maximum Lateness

It is well known that the Earliest-Deadline-First (EDF) and the Least-Laxity-First (LLF) algorithms are optimal algorithms for the problem of preemptively scheduling jobs that arrive over time on a single machine to minimize the maximum lateness (1|r _j ,pmtn|L _max). It was not previously known what other online algorithms are optimal for this problem. As this problem is fundamental in machine scheduling, it deserves a thorough investigation. In this paper, the concept of compound laxity is introduced, and a complete characterization of all optimal online algorithms for this problem is derived.  

多处理器混合关键性系统中的划分调度策略

多核处理器正越发广泛地应用到现代嵌入式系统的设计与实现当中，其强大的计算能力为将多个不同关键性级别的功能子系统集成到统一的共享资源平台提供了支持.混合关键性系统的调度问题即便在单处理器平台中都极具挑战性，在多处理器平台则更为困难.将目前资源利用率最高的单处理器混合关键性调度算法EY-VD扩展到多处理器平台中.首先，结合传统的划分调度策略提出了适用于多处理器混合关键性系统的MC-PEDF(mixedcriticality partitioned earliest deadline first)划分调度算法.尽管比之前的算法有更好的可调度性能，但传统的划分策略不能有效地平衡不同关键性级别下的负载，故其不完全适用于混合关键性系统.为了克服传统策略的不足，提出了划分调度策略OCOP(one criticality one partition).OCOP允许系统在关键性模式切换时对实时任务集进行重新划分，进而更好地平衡各个处理器在不同关键性模式中的资源利用率.基于OCOP，提出了第2种划分调度算法MC-MP-EDF(mixed-criticality multi-partitioned EDF).基于随机生成任务集的仿真实验结果表明，与MC-PEDF和已有的算法相比，MC-MP-EDF能够显著地提高系统的可调度性，尤其是在处理器数量较多的系统中.