Search

Suspension-based locks are widely used in real-time systems to coordinate simultaneous accesses to exclusive shared resources. Although suspension-based locks have been well studied for sequential real-time tasks, little work has been done on this topic for parallel real-time tasks. This article for the first time studies the problem of how to extend existing sequential-task locking protocols and their analysis techniques to the parallel task model. More specifically, we extend two locking protocols OMLP and OMIP, which were designed for clustered scheduling of sequential real-time tasks, to federated scheduling of parallel real-time tasks. We present corresponding blocking analysis techniques, and develop path-oriented techniques to analyze and count blocking time. Schedulability tests with different efficiency and accuracy are further developed. Experiments are conducted to evaluate the performance of our proposed approaches against the state-of-the-art. [ABSTRACT FROM AUTHOR]

A number of scheduling algorithms have been proposed for real-time parallel tasks modeled as Directed Acyclic Graphs (DAGs). Many of them focus on scheduling DAG tasks with implicit deadlines. Fewer studies have considered DAG tasks with constrained deadlines or arbitrary deadlines. In this study, we propose a scheduling strategy based on fluid scheduling theory and we target DAG tasks with constrained or arbitrary deadlines. We prove that the proposed algorithm has a capacity augmentation bound of $\frac{1}{2}(1+\beta +\sqrt{(1+\beta)^2-\frac{4}{m}})$ 1 2 (1 + β + (1 + β) 2 - 4 m ) when scheduling multiple DAG tasks with constrained deadlines, in which $m$ m is the number of processors and $\beta$ β is the maximum ratio of task period to deadline. This value is lower than the current best result $\beta +2\sqrt{(\beta +1-\frac{1}{m})(1-\frac{1}{m})}$ β + 2 (β + 1 - 1 m) (1 - 1 m) . We also prove that a capacity augmentation bound of $\frac{1}{2}(1+\sqrt{2}+\sqrt{(1+\sqrt{2})^2-\frac{4\sqrt{2}}{m}})$ 1 2 (1 + 2 + (1 + 2) 2 - 4 2 m ) is guaranteed by our algorithm in the case of scheduling multiple DAG tasks with deadlines greater than periods. To the best of our knowledge, this is the first capacity augmentation bound that has been proven for scheduling multiple DAG tasks with deadlines greater than periods. Our experiments show that our algorithm outperforms the state of the art scheduling algorithms in the percentage of schedulable task sets. [ABSTRACT FROM AUTHOR]

Achieving high result-accuracy in approximate computing (AC) based real-time applications without violating power constraints of the underlying hardware is a challenging problem. Execution of such AC real-time tasks can be divided into the execution of the mandatory part to obtain a result of acceptable quality, followed by a partial/complete execution of the optional part to improve accuracy of the initially obtained result within the given time-limit. However, enhancing result-accuracy at the cost of increased execution length might lead to deadline violations with higher energy usage. We propose Prepare, a novel hybrid offline-online approximate real-time task-scheduling approach, that first schedules AC-based tasks and determines operational processing speeds for each individual task constrained by system-wide power limit, deadline, and task-dependency. At runtime, by employing fine-grained DVFS, the energy-adaptive processing speed governing mechanism of Prepare reduces processing speed during each last level cache miss induced stall and scales up the processing speed once the stall finishes to a higher value than the predetermined one. To ensure on-chip thermal safety, this higher processing speed is maintained only for a short time-span after each stall, however, this reduces execution times of the individual task and generates slacks. Prepare exploits the slacks either to enhance result-accuracy of the tasks, or to improve thermal and energy efficiency of the underlying hardware, or both. With a 70 - 80% workload, Prepare offers 75% result-accuracy with its constrained scheduling, which is enhanced by 5.3% for our benchmark based evaluation of the online energy-adaptive mechanism on a 4-core based homogeneous chip multi-processor, while meeting the deadline constraint. Overall, while maintaining runtime thermal safety, Prepare reduces peak temperature by up to 8.6 °C for our baseline system. Our empirical evaluation shows that constrained scheduling of Prepare outperforms a state-of-the-art scheduling policy, whereas our runtime energy-adaptive mechanism surpasses two current DVFS based thermal management techniques. [ABSTRACT FROM AUTHOR]

The mixed-criticality system provides multiple real-time applications with different criticalities in a single system. Poor energy-saving performance of the previous studies on mixed-criticality sporadic tasks are mainly due to the fact that the slack time generated from the random arrival of sporadic tasks is not taken into account. In this article, we focus on scheduling energy aware mixed-criticality sporadic tasks and take the random arrival of sporadic tasks into account. We proposed a dynamically frequency updating mixed-criticality algorithm (DFU). DFU based on the earliest deadline first scheme can exploit the slack time generated from high criticality tasks in a low criticality mode to reduce processor frequency. In addition, it also can dynamically update the utilization of sporadic tasks set to further reduce processor frequency. The simulation experiments are conducted to evaluate the performance of DFU and experimental results show that DFU consumes 34.29% less energy than that of the existing algorithms. [ABSTRACT FROM AUTHOR]

Multicore processors have become mainstream computation platforms not only for general and high-performance computers but also for real-time embedded systems. To fully utilize the computation power of multicores, software must be parallelized. Recently, there has been a rapidly increasing interest in real-time scheduling of parallel real-time tasks, but the field is still much less mature than traditional real-time scheduling of sequential tasks. In this article, we study the real-time scheduling and techniques for parallel real-time tasks based on decomposition, where a task graph is transferred to a set of independent sporadic tasks. In particular, we propose new decomposition strategies that better explore the structure feature of each task to improve schedulability. We develop schedulability tests for the global earliest deadline first (EDF) scheduling algorithm based on decomposition and three types of its variants, with their own pros and cons in different aspects. We conduct experiments to evaluate the real-time performance of our proposed scheduling algorithms against the state-of-the-art scheduling and analysis methods of different types. [ABSTRACT FROM AUTHOR]

Reconfigurable devices (RDs) are extremely advantageous when employed in real-time embedded systems. Nonetheless, they are susceptible to soft errors. In a broad sense, the present research addresses the challenge of improving the reliability of independent periodic real-time hardware tasks in RDs by utilizing hybrid fault-tolerant scheduling. The current paper combines static and dynamic real-time scheduling techniques to improve the reliability of the system. First, the proposed algorithm statically schedules primary tasks and preserves area and time for possible backup tasks on the RD. The overlapping of passive backup tasks is possible. Next, at the run time, event-triggered dispatcher dynamically determines which candidate backup copy should be selected for configuration on the overloaded preserved areas. Reliability, task deadline, and RD area limitations are the determining factors of backup overloading in the static phase. On the other hand, in the dynamic phase, the execution result of the primary tasks—in this case, success or failure—is the deciding factor based on which the dispatcher configures the true backup task on the preserved area. Experimental results show that the hybrid scheduling technique enhances the mean-time-to-failure of the system by an average factor of 1.22 in comparison with a similar state-of-the-art study. [ABSTRACT FROM AUTHOR]

Utilization bound is a well-known concept in real-time scheduling theory for sequential periodic tasks, which can be used both for quantifying the performance of scheduling algorithms and as efficient schedulability tests. However, the schedulability of parallel real time task graphs depends on not only utilization, but also another parameter tensity, the ratio between the longest path length and period. In this paper, we use utilization-tensity bounds to better characterize the schedulability of parallel real-time tasks. In particular, we derive utilization-tensity bounds for parallel DAG tasks under global EDF scheduling, which facilitate significantly more precise schedulability analysis than the state-of-the-art analysis techniques based on capacity augmentation bound and response time analysis. Moreover, we apply the above results to the federated scheduling paradigm to improve the system schedulability by choosing proper scheduling strategies for tasks with different workload and structure features. [ABSTRACT FROM AUTHOR]

Recently, several parallel frameworks have emerged to utilize the increasing computational capacity of multiprocessors. Parallel tasks are distinguished from traditional sequential tasks in that the subtasks contained in a single parallel task can simultaneously execute on multiple processors. In this study, we consider the scheduling problem of minimizing the number of processors on which the parallel real-time tasks feasibly run. In particular, we focus on scheduling sporadic parallel real-time tasks, in which precedence constraints between subtasks of each parallel task are expressed using a directed acyclic graph (DAG). To address the problem, we formulate an optimization problem that aims to minimize the maximum processing capacity for executing the given tasks. We then suggest a polynomial solution consisting of three steps: (1) transform each parallel real-time task into a series of multithreaded segments, while respecting the precedence constraints of the DAG; (2) selectively extend the segment lengths; and (3) interpret the problem as a flow network to balance the flows on the terminal edges. We also provide the schedulability bound of the proposed solution: it has a capacity augmentation bound of 2. Our experimental results show that the proposed approach yields higher performance than one developed in a recent study. [ABSTRACT FROM AUTHOR]

For the problem of lacking real-time scheduling mechanism in the embedded Forth operating system at present, this paper investigated the key technologies of multitask-scheduling of embedded operating system based on Forth virtual machine architecture. On the basis of Forth virtual machine technology, this paper defined a new interrupt task type to deal with real-time emergencies and proposed a new scheduling algorithm, which enabled the scheduling of terminal tasks, background tasks and interrupt tasks in Forth system to be successfully executed. The experimental results demonstrate that the improved Forth system can handle emergencies through real-time scheduling and has a high real-time response. It is especially suitable for the embedded environment which is required for real-time performance, so as to meet the increasingly complex application requirements of embedded system for efficient operating system and Forth technology. [ABSTRACT FROM AUTHOR]

Dynamic voltage and frequency scaling (DVFS) is a widely used solution to reduce power consumption. Modern multi-core architectures support core-level DVFS, where each core has its own power supply and can change its frequency independently from other cores. This paper aims at optimizing power consumption of multi-core processors while ensuring deadline constraints of real-time periodic tasks. From theoretical aspects, we prove a tight lower bound of power consumption for executing real-time tasks, which indicates to what extent scheduling algorithms can approach. From practical aspects, we propose a Power Scaling Algorithm (PSA) to assign real-time periodic tasks to a power efficient platform. PSA not only determines the optimal frequencies for each core, but also provides the appropriate number of active cores, which can skip the local optimum and achieve the global minimum. This lower power bound is validated by several extensive experiments. • The optimal frequency setting of a core-level DVFS system is proved. This frequency setting can minimize the total power consumption when core number is fixed. • The low bound of power consumption for scheduling real-time tasks is proved. • Power Scaling Algorithm (PSA) is proposed to configure power-efficient core-level DVFS systems, and is applied as a prerequisite for other power-aware real-time scheduling algorithms. • PSA automatically computes the number of cores needed to ensure schedulability, which can help scheduling heuristics skip the local optimum and achieve the global minimum power consumption. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of multiprocessor real-time scheduling for parallel tasks modeled as directed acyclic graph (DAG). We propose a new decomposition-based scheduling algorithm to schedule parallel DAG tasks with implicit-deadlines. We prove that our algorithm has a resource augmentation bound of 2.618 for DAG tasks with implicit-deadlines when the decomposed tasks are scheduled using Global EDF scheduling, i.e., if the input set of DAG tasks is schedulable on m unit-speed processors, the proposed scheduling algorithm will always succeed on m processors with speed 2.618. This result improves the resource augmentation bound of 2.618 for tasks with special DAGs provided by Qamhieh et al. in 2019. Moreover, when using Global DM (Partitioned-DM, respectively) scheduling for the decomposed tasks, we prove a resource augmentation bound of 3.42 for DAG tasks with implicit-deadlines, which improves the resource augmentation bound of 3.73 for tasks with special DAGs (3.42 for fork-join tasks, respectively). [Display omitted] • An improved decomposition-based scheduling algorithm is proposed for parallel tasks. • The density of the decomposed tasks in the proposed scheduling algorithm is reduced. • Improved resource augmentation bounds for the proposed algorithm are provided. [ABSTRACT FROM AUTHOR]

The priority-driven scheduling of periodic and sporadic task systems upon identical multiprocessor platforms is considered, under the restrictions that (i) each job may be assigned exactly one priority throughout its lifetime, and (ii) each job may execute upon only a single processor. It is shown that feasibility-analysis under these restrictions is intractable (NP-hard in the strong sense). A scheduling algorithm is presented that satisfies these restrictions, and that has a worst-case utilization bound comparable to the worst-case utilization bounds of partitioned scheduling algorithms, and of scheduling algorithms that retain the priority-assignment restriction but allow arbitrary interprocessor migration. [ABSTRACT FROM AUTHOR]