Supervisory control for real-time scheduling of periodic and sporadic tasks with resource constraints

In the framework of supervisory control of timed discrete event systems, this paper addresses the design problem of a real-time scheduler that meets stringent time constraints of periodic tasks and sporadic tasks which exclusively access shared resources. For this purpose, we present the timed discrete event models of execution of periodic tasks and sporadic tasks and resource access for shared resources. Based on these models, we present the notion of deadlock-free and schedulable languages that contain only deadline-meeting sequences which do not reach deadlock states. In addition, we present the method of systematically computing the largest deadlock-free and schedulable language, and it is also shown that schedulability analysis can be done using this language. We further show that the real-time scheduler achieving the largest deadlock-free and schedulable language is optimal in the sense that there are no other schedulers to achieve schedulable cases more than those achieved by the optimal scheduler.     

Energy-efficient scheduling of real-time tasks with shared resources

This paper explores the energy-efficient scheduling of real-time tasks on a non-ideal DVS processor in the presence of resource sharing. We assume that tasks are periodic, preemptive and may access to shared resources. When dynamic-priority and fixed-priority scheduling are considered, we use the earliest deadline first (EDF) algorithm and the rate monotonic (RM) algorithm to schedule the given set of tasks. Based on the stack resource policy (SRP), we propose an approach, called blocking-aware two-speed (BATS) algorithm, to synchronize the tasks with shared resources and to calculate appropriate execution speeds so that the shared resources can be accessed in a mutual exclusive manner and the energy consumption can be reduced. Particularly, BATS uses a static low speed to execute tasks initially, and then it switches to a high speed dynamically whenever a task blocks a higher priority task. More specifically, the processor runs at the high speed from the beginning of the blocking until the deadline of the blocked task or the processor becomes idle. In order to guarantee that the deadlines of tasks are met, the static low speed and the dynamic high speeds are derived based on the theoretical analysis of the schedulability of tasks. Compared with existing work, BATS achieves more energy saving because its dynamic high speeds are lower than that of existing work and the processor has less chance to execute tasks at the high speeds. The schedulability analysis and the properties of our proposed BATS are provided in this paper. We also evaluated the capabilities of BATS by a series of experiments, for which we have some encouraging results.     

A new algorithm for scheduling periodic, real-time tasks

We consider the problem of preemptively scheduling a set of periodic, real-time tasks on a multiprocessor computer system. We give a new scheduling algorithm, the so-called Slack-Time Algorithm, and show that it is more effective than the known Deadline Algorithm. We also give an (exponential-time) algorithm to decide if a task system is schedulable by the Slack-Time or the Deadline Algorithm. The same algorithm can also be used to decide if a task system is schedulable by any given fixed-priority scheduling algorithm. This resolves an open question posed by Leung and Whitehead. Finally, it is shown that the problem of deciding if a task system is schedulable by the Slack-Time, the Deadline, or any given fixed-priority scheduling algorithm is co-NP-hard for each fixedm.     

Minimal schedulability interval for real-time systems of periodic tasks with offsets

We consider real-time systems in highly safety context where tasks have to meet strict deadlines. Tasks are periodic, may have offsets, share critical resources and be precedence constrained. Off-line scheduling should be of great help for such systems, but methods proposed in the literature cannot deal with them. Our aim is to extend and improve the well-known cyclicity result of Leung and Merill to every scheduling algorithm and to systems of interacting tasks with offsets. One of the main benefit of our result is to enable the use of off-line scheduling methods for those real-time critical systems.     

DFTS: A dynamic fault-tolerant scheduling for real-time tasks in multicore processors

This paper presents a dynamic scheduling for real-time tasks in multicore processors to tolerate single and multiple transient faults. The scheduling is performed based on three important issues: (1) current released tasks, (2) current available processor cores, and (3) consideration of the number of faults and their occurrences. Using tasks utilization along with a defined criticality threshold in the proposed scheduling method, current ready tasks are divided into critical- and noncritical ones. Based on whether a task is critical or noncritical, an appropriate fault-tolerance policy is exploited. Moreover, scheduling decisions are made to fulfill two key goals: (1) increasing scheduling feasibility and (2) decreasing the total tasks execution time. Several simulation experiments are carried out to compare the proposed method with two well-known methods, called checkpointing with rollback recovery and hardware replication. Experimental results reveal that in the presence of multiple transient faults, the feasibility rate of the proposed method is considerably higher than the other well-known fault-tolerance methods. Moreover, the average timing overhead of this method is lower than the traditional methods.     

End-to-end deadline control for aperiodic tasks in distributed real-time systems

A category of Distributed Real-Time Systems (DRTS) that has multiprocessor pipeline architecture is increasingly used. The key challenge of such systems is to guarantee the end-to-end deadlines of aperiodic tasks. This paper proposes an end-to-end deadline control model, called Linear Quadratic Stochastic Optimal Control Model (LQ-SOCM), which features a distributed feedback control that dynamically enforces the desired performance. The control system considers the aperiodic task arrivals and execution times’ variation as the two external factors of the system unpredictability. LQ-SOCM uses discrete time state space equation to describe the real-time computing system. Then, in the actuator design, a continuous manner is adopted to deal with discrete QoS (Quality of Service) adaptation. Finally, experiments demonstrate that the system is globally stable and can statistically provide the end-to-end deadline guarantee for aperiodic tasks. At the same time, LQ-SOCM is capable of effectively improving the system throughput.

A new fair scheduling algorithm for periodic tasks on multiprocessors

We present a new scheduling algorithm, called PL that is work-conserving and in terms of schedulability, optimal on multiprocessors for a synchronous periodic task set. The PL algorithm is a laxity based algorithm and ensures execution of a task with approximate proportional fairness at each task's period. Existing optimal algorithms on multiprocessors may cause excessive scheduling decisions and preemptions or may not be applied in a discrete environment. The proposed algorithm can be applied in a discrete environment and reduce the number of scheduling decisions and preemptions compared with a Pfair algorithm.     

A DVS-assisted hard real-time I/O device scheduling algorithm

The I/O subsystem has become a major source of energy consumption in a hard real-time monitoring and control system. To reduce its energy consumption without missing deadlines, a dynamic power management (DPM) policy must carefully consider the power parameters of a device, such as its break-even time and wake-up latency, when switching off idle devices. This problem becomes extremely complicated when dynamic voltage scaling (DVS) is applied to change the execution time of a task. In this paper, we present COLORS, a composite low-power scheduling framework that includes DVS in a DPM policy to maximize the energy reduction on the I/O subsystem. COLORS dynamically predicts the earliest-access time of a device and switches off idle devices. It makes use of both static and dynamic slack time to extend the execution time of a task by DVS, in order to create additional switch-off opportunities. Task workloads, processor profiles, and device characteristics all impact the performance of a low-power real-time algorithm. We also identify a key metric that primarily determines its performance. The experimental results show that, compared with previous work, COLORS achieves additional energy reduction up to 20%, due to the efficient utilization of slack time.

Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment

In a distributed heterogeneous computing system, the resources have different capabilities and tasks have different requirements. To maximize the performance of the system, it is essential to assign the resources to tasks (match) and order the execution of tasks on each resource (schedule) to exploit the heterogeneity of the resources and tasks. Dynamic mapping (defined as matching and scheduling) is performed when the arrival of tasks is not known a priori. In the heterogeneous environment considered in this study, tasks arrive randomly, tasks are independent (i.e., no inter-task communication), and tasks have priorities and multiple soft deadlines. The value of a task is calculated based on the priority of the task and the completion time of the task with respect to its deadlines. The goal of a dynamic mapping heuristic in this research is to maximize the value accrued of completed tasks in a given interval of time. This research proposes, evaluates, and compares eight dynamic mapping heuristics. Two static mapping schemes (all arrival information of tasks are known) are designed also for comparison. The performance of the best heuristics is 84% of a calculated upper bound for the scenarios considered.     

Power-aware scheduling algorithms for sporadic tasks in real-time systems

In this paper, we consider the canonical sporadic task model with the system-wide energy management problem. Our solution uses a generalized power model, in which the static power and the dynamic power are considered. We present a static solution to schedule the sporadic task set, assuming worst-case execution time for each sporadic tasks release, and propose a dynamic solution to reclaim the slacks left by the earlier completion of tasks than their worst-case estimations. The experimental results show that the proposed static algorithm can reduce the energy consumption by 20.63%–89.70% over the EDF* algorithm and the dynamic algorithm consumes 2.06%–24.89% less energy than that of the existing DVS algorithm.     

A new algorithm for scheduling periodic,real-time tasks

Algorithmica - We consider the problem of preemptively scheduling a set of periodic, real-time tasks on a multiprocessor computer system. We give a new scheduling algorithm, the so-called...     

异构分布系统的实时任务轮转式容错调度算法

建立了一个异构分布式系统实时调度模型,对异构分布式系统中的任务及不同处理机资源进行了形式化描述.结合基版本/副版本技术,给出了用于异构分布式系统的实时任务轮转式容错调度算法.实例分析表明,该算法有效提高了异构处理机环境下的资源利用率以及整体计算性能.     

Integrating job parallelism in real-time scheduling theory

We investigate the global scheduling of sporadic, implicit deadline, real-time task systems on multiprocessor platforms. We provide a task model which integrates job parallelism. We prove that the time-complexity of the feasibility problem of these systems is linear relatively to the number of (sporadic) tasks for a fixed number of processors. We propose a scheduling algorithm theoretically optimal (i.e., preemptions and migrations neglected). Moreover, we provide an exact feasibility utilization bound. Lastly, we propose a technique to limit the number of migrations and preemptions.     

Supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks

Supervisory control theory is a well-established theoretical framework for feedback control of discrete event systems whose behaviours are described by automata and formal languages. In this article, we propose a formal constructive method for optimal fault-tolerant scheduling of real-time multiprocessor systems based on supervisory control theory. In particular, we consider a fault-tolerant and schedulable language which is an achievable set of event sequences meeting given deadlines of accepted aperiodic tasks in the presence of processor faults. Such a language eventually provides information on whether a scheduler (i.e., supervisor) should accept or reject a newly arrived aperiodic task. Moreover, we present a systematic way of computing a largest fault-tolerant and schedulable language which is optimal in that it contains all achievable deadline-meeting sequences.     

Slack allocation algorithm for parallel machines

Energy consumption is a critical issue in parallel and distributed embedded systems. We present a novel algorithm for energy efficient scheduling of Directed Acyclic Graph (DAG) based applications on Dynamic Voltage Scaling (DVS) enabled systems. Experimental results show that our algorithm provides near optimal solutions for energy minimization with considerably smaller computational time and memory requirements compared to an existing algorithm that provides near optimal solutions.     

A constant-time dynamic storage allocator for real-time systems

Dynamic memory allocation has been used for decades. However, it has seldom been used in real-time systems since the worst case of spatial and temporal requirements for allocation and deallocation operations is either unbounded or bounded but with a very large bound. In this paper, a new allocator called TLSF (Two Level Segregated Fit) is presented. TLSF is designed and implemented to accommodate real-time constraints. The proposed allocator exhibits time-bounded behaviour, O(1), and maintains a very good execution time. This paper describes in detail the data structures and functions provided by TLSF. We also compare TLSF with a representative set of allocators regarding their temporal cost and fragmentation. Although the paper is mainly focused on timing analysis, a brief study and comparative analysis of fragmentation incurred by the allocators has been also included in order to provide a global view of the behaviour of the allocators. The temporal and spatial results showed that TLSF is also a fast allocator and produces a fragmentation close to that caused by the best existing allocators.

Adaptive energy-efficient scheduling for real-time tasks on DVS-enabled heterogeneous clusters

Developing energy-efficient clusters not only can reduce power electricity cost but also can improve system reliability. Existing scheduling strategies developed for energy-efficient clusters conserve energy at the cost of performance. The performance problem becomes especially apparent when cluster computing systems are heavily loaded. To address this issue, we propose in this paper a novel scheduling strategy–adaptive energy-efficient scheduling or AEES–for aperiodic and independent real-time tasks on heterogeneous clusters with dynamic voltage scaling. The AEES scheme aims to adaptively adjust voltages according to the workload conditions of a cluster, thereby making the best trade-offs between energy conservation and schedulability. When the cluster is heavily loaded, AEES considers voltage levels of both new tasks and running tasks to meet tasks’ deadlines. Under light load, AEES aggressively reduces the voltage levels to conserve energy while maintaining higher guarantee ratios. We conducted extensive experiments to compare AEES with an existing algorithm–MEG, as well as two baseline algorithms–MELV, MEHV. Experimental results show that AEES significantly improves the scheduling quality of MELV, MEHV and MEG.     

Adaptive resource management for dynamic distributed real-time applications

The dynamic distributed real-time applications run on clusters with varying execution time, so re-allocation of resources is critical to meet the applications’s deadline. In this paper we present two adaptive recourse management techniques for dynamic real-time applications by employing the prediction of responses of real-time tasks that operate in time sharing environment and run-time analysis of scheduling policies. Prediction of response time for resource reallocation is accomplished by historical profiling of applications’ resource usage to estimate resource requirements on the target machine and a probabilistic approach is applied for calculating the queuing delay that a process will experience on distributed hosts. Results show that as compared to statistical and worst-case approaches, our technique uses system resource more efficiently.