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.     

Deadline-based scheduling of periodic task systems on multiprocessors

We consider the problem of scheduling periodic task systems on multiprocessors and present a deadline-based scheduling algorithm for solving this problem. We show that our algorithm successfully schedules on m processors any periodic task system with utilization at most m²/(2m−1).     

Global Control of Robotic Highway Safety Markers: A Real-time Solution

This paper presents the design and implementation of a real-time solution for the global control of robotic highway safety markers. Problems addressed in the system are: (1) poor scalability and predictability as the number of markers increases, (2) jerky movement of markers, and (3) misidentification of safety markers caused by objects in the environment.An extensive analysis of the system and two solutions are offered: a basic solution and an enhanced solution. They are built respectively upon two task models: the periodic task model and the variable rate execution (VRE) task model. The former is characterized by four static parameters: phase, period, worst case execution time and relative deadline. The latter has similar parameters, but the parameter values are allowed to change at arbitrary times.The use of real-time tasks and scheduling techniques solve the first two problems. The third problem is solved using a refined Hough transform algorithm and a horizon scanning window. The approach decreases the time complexity of traditional implementations of the Hough transform with only slightly increased storage requirements.Supported, in part, by grants from the National Science Foundation (CCR-0208619 and CNS-0409382) and the National Academy of Sciences Transportation Research Board-NCHRP IDEA Program (Project #90).Jiazheng Shi received the B.E. and M.E. degrees in electrical engineering from Beijing University of Posts and Telecommunications in 1997 and 2000, respectively. In 2000, he worked with the Global Software Group, Motorola Inc. Currently, he is a Ph.D. candidate in the Computer Science and Engineering Department at the University of Nebraska–Lincoln. His research interests are automated human face recognition, image processing, computer vision, approximate theory, and linear system optimization.Steve Goddard is a J.D. Edwards Associate Professor in the Department of Computer Science & Engineering at the University of Nebraska–Lincoln. He received the B.A. degree in computer science and mathematics from the University of Minnesota (1985). He received the M.S. and Ph.D. degrees in computer science from the University of North Carolina at Chapel Hill (1995, 1998).His research interests are embedded, real-time and distributed systems with emphases in high assurance systems engineering and real-time, rate-based scheduling theory.Anagh Lal received a B.S. degree in Computer Science from the University of Mumbai (Bombay), Mumbai, in 2001. He is currently a graduate research assistant at the University of Nebraska–Lincoln working on a M.S. in Computer Science, and a member of the ConSystLab. His research interests lie in Databases, Constraint Processing and Real Time Systems. Anagh will be graduating soon and is looking for positions at research institutions.Jason Dumpert received a B.S. degree in electrical engineering from the University of Nebraska–Lincoln in 2001. He received a M.S. degree in electrical engineering from the University of Nebraska-Lincoln in 2004. He is currently a graduate research assistant at the University of Nebraska-Lincoln working on a Ph.D. in biomedical engineering. His research interests include mobile robotics and surgical robotics.Shane M. Farritor is an Associate Professor in the University of Nebraska–Lincolns Department of Mechanical Engineering. His research interests include space robotics, surgical robotics, biomedical sensors, and robotics for highway safety. He holds courtesy appointments in both the Department of Surgery and the Department of Orthopaedic Surgery at the University of Nebraska Medical Center, Omaha. He serves of both the AIAA Space Robotics and Automation technical committee and ASME Dynamic Systems and Control Robotics Panel. He received M.S. and Ph.D. degrees from M.I.T.     

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

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

基于时间帧的处理器PFair调度改进算法

为了解决PFair算法进行交互任务调度时,由于忽略了不同阶段的周期性任务而导致多个线程之间任务的迁移问题以及空间和时间的浪费问题,提出了基于时间帧的处理器PFair调度改进算法。该算法基于周期性任务系统的特点,引入时间帧控制和改变本地周期性任务调度来限制任务迁移,从而实现对PFair算法的改进。为了评估算法的迁移开销和公平性,通过实验对普通PFair算法及本文所提出的改进算法ERfair进行对比实验,结果表明,改进算法ERfair能够通过时间帧内调度和分区控制大大降低任务在不同处理器间的迁移次数。基于时间帧的处理器PFair调度改进算法在保证公平性的同时,提高了系统的效率,应用于多核处理器上的任务调度是可行的、有效的。     

Analysis of window-constrained execution time systems

Feasibility tests for hard real-time systems provide information about the schedulability of the task set. However, this information is a yes or a no answer, that is, whether the task set achieves the test or not. From the real-time system design point of view, having more information available would be useful. For example, how much the computation time can vary without jeopardising the system feasibility. This work specifically provides methods to determine off-line how much a task can increase its computation time, by maintaining the system feasibility under a dynamic priority scheduling. The extra time can be determined not only in all the task activations, but in n of a window of m invocations. This is what we call a window-constrained execution time system. The results presented in this work can be used in all kinds of real-time systems: fault tolerance management, imprecise computation, overrun handling, control applications, etc. Patricia Balbastre is an assistant professor of Computer Engineering. She graduated in Electronic Engineering at the Technical University of Valencia, Spain, in 1998. And the Ph.D. degree in Computer Science at the same university in 2002. Her main research interests include real-time operating systems, dynamic scheduling algorithms and real-time control. Ismael Ripoll received the B.S. degree from the Polytechnic University of Valencia, Spain, in 1992; the Ph.D. degree in Computer Science at the Polytechnic University of Valencia, Spain, in 1996. Currently he is Professor in the DISCA Department of the same University. His research interests include embedded and real-time operating systems. Alfons Crespo is Professor of the Department of Computer Engineering of the Technical University of Valencia. He received the PhD in Computer Science from the Technical University of Valencia, Spain, in 1984. He held the position of Associate professor in 1986 and full Professor in 1991. He leads the group of Industrial Informatics and has been the responsible of several European and Spanish research projects. His main research interest include different aspects of the real-time systems (scheduling, hardware support, scheduling and control integration, …). He has published more than 60 papers in specialised journals and conferences in the area of real-time systems.     

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.     

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.     

基于多处理机的混合实时任务容错调度

提出了一种混合实时任务容错调度算法．该算法采用Rate Monotonic(RM)算法完成周期任务的静态调度；采用预订处理机时间方法和Earlier Deadline First(EDF)算法动态调度非周期任务；采用主／副版本备份技术确保系统的容错能力．通过充分利用周期任务的剩余处理机时间调度非周期任务和主动备份与被动备份相结合的方法有效地减少了处理机数．仿真结果证明了算法的有效性．     

A compact task graph representation for real-time scheduling

A new task graph representation, namely the compact task graph (CTG), is developed to aid in the scheduling of a set of communicating periodic real-time tasks. This representation explicitly expresses the potential for parallelism across tasks as well as the idle times that may be encountered within application tasks. A CTG based scheduler can generate schedules that are able to meet deadlines by interleaving the execution of tasks on a single processor and/or overlapping the execution of tasks on multiple processors. The construction of a CTG is based upon the busy-idle execution profiles for the tasks generated by the compiler. The profiles are computed assuming that sufficient resources are available for parallel execution of all tasks. Thus, they expose all opportunities for overlapped and interleaved execution. The compiler analyzes the profiles to identify useful opportunities for interleaving and expresses them in the CTG without unnecessary partitioning of the tasks. The CTG is powerful because it expresses schedules that are not expressed by existing approaches for constructing task graphs. Schedules can be generated efficiently since a CTG's construction minimizes the splitting of tasks. We briefly demonstrate the usefulness of CTGs in scheduling real-time tasks and scheduling monitoring tasks without affecting the timing of application tasks.Supported in part by the National Science Foundation through a Presidential Young Investigator Award CCR-9157371 and Grant CCR-9212020.