Search

Real-time constrained multiprocessor systems have been widely applied across various domains. In this paper, we focus on the scheduling algorithm for directed acyclic graph (DAG) tasks under partitioned scheduling on multiprocessor systems. Effective real-time task scheduling algorithms significantly enhance the performance and stability of multiprocessor systems. Traditional real-time task scheduling algorithms commonly rely on a single-heuristic parameter as the reference for task allocation, which typically results in suboptimal performance. Inspired by the Tetris algorithm, we propose a novel heuristic scheduling algorithm, named Tetris game scoring scheduling algorithm (TGSSA), that integrates multiple-heuristic parameters. The process of real-time DAG task scheduling on a multiprocessor system is modeled as a Tetris game. Through simulations of the worst-case response time (WCRT) analysis and observed average response times in RT-Linux, which is a frequently-used real-time operating system, our algorithm demonstrates superior performance, effectively improving the efficiency and stability of real-time operating systems. [ABSTRACT FROM AUTHOR]

The adoption of multiprocessor platforms is growing commonplace in Internet of Things (IoT) applications to handle large volumes of sensor data while maintaining real-time performance at a reasonable cost and with low power consumption. Partitioned scheduling is a competitive approach to ensure the temporal constraints of real-time sensor data processing tasks on multiprocessor platforms. However, the problem of partitioning real-time sensor data processing tasks to individual processors is strongly NP -hard, making it crucial to develop efficient partitioning heuristics to achieve high real-time performance. This paper presents an enhanced harmonic partitioned multiprocessor scheduling method for periodic real-time sensor data processing tasks to improve system utilization over the state of the art. Specifically, we introduce a general harmonic index to effectively quantify the harmonicity of a periodic real-time task set. This index is derived by analyzing the variance between the worst-case slack time and the best-case slack time for the lowest-priority task in the task set. Leveraging this harmonic index, we propose two efficient partitioned scheduling methods to optimize the system utilization via strategically allocating the workload among processors by leveraging the task harmonic relationship. Experiments with randomly synthesized task sets demonstrate that our methods significantly surpass existing approaches in terms of schedulability. [ABSTRACT FROM AUTHOR]

Current real-time systems applications are mostly large-scale, where tasks are intrinsically time-constrained and meaningfully dependent. Nevertheless, while the initial partitioning solution has a huge impact on scheduling results, most tasks-allocation problems are NP-complete and lack binding semantics. The scheduling analysis strategies are inevitably required to validate the system scheduling before its actual deployment. However, once the proposed scheduling is invalid, no possible corrections are provided, and a costing NP-complete partitioning regeneration is provoked as the only possible correction action. Whereas, sometimes nearby task re-allocations guarantee the scheduling correction. This paper proposes an approach to efficiently correct initial dependent task partitioning solutions while considering their allocation semantics. The ultimate objective is to conduct a correct schedule for multiprocessor real-time systems by means of a driven task re clustering and/or re-allocation without the need for extra complex partitioning regeneration. Simulation results show that our proposed approach is faster than classic partitioning regeneration, ameliorates the partitioning semantic results, and gives efficient scheduling results. [ABSTRACT FROM AUTHOR]

Real-time systems with strict timing constraints have been widely applied in many fields. The Directed acyclic graph (DAG) task model has been widely studied and applied to model real-time systems with partial parallelism and precedence constraints in each task. Our paper focuses on the worst-case response time (WCRT) analysis of DAG tasks under partitioned scheduling on multiprocessors. We investigate a parallel structure named $Str$ S t r , which helps obtain more accurate analysis results, and propose a new offline scheduling analysis algorithm named reducing repetitive calculation (RRC). Experiments with synthetic workload are conducted to compare the results calculated by RRC and the state-of-the-art, as well as the observed average response time on a real embedded system. Results show that RRC has better performance in terms of analysis accuracy. [ABSTRACT FROM AUTHOR]

A Mixed-Criticality System (MCS) features the integration of multiple subsystems that are subject to different levels of safety certification on a shared hardware platform. In cost-sensitive application domains such as automotive E/E systems, it is important to reduce application memory footprint, since such a reduction may enable the adoption of a cheaper microprocessor in the family. Preemption Threshold Scheduling (PTS) is a well-known technique for reducing system stack usage. We consider partitioned multiprocessor scheduling, with Preemption Threshold Adaptive Mixed-Criticality (PT-AMC) as the task scheduling algorithm on each processor and address the optimization problem of finding a feasible task-to-processor mapping with minimum total system stack usage on a resource-constrained multi-processor. We present the Extended Maximal Preemption Threshold Assignment Algorithm (EMPTAA), with dual purposes of improving the taskset’s schedulability if it is not already schedulable, and minimizing system stack usage of the schedulable taskset. We present efficient heuristic algorithms for finding sub-optimal yet high-quality solutions, including Maximum Utilization Difference based Partitioning (MUDP) and MUDP with Backtrack Mapping (MUDP-BM), as well as a Branch-and-Bound (BnB) algorithm for finding the optimal solution. Performance evaluation with synthetic task sets demonstrates the effectiveness and efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

The architecture of ARINC-653 partitioned scheduling has been widely applied to avionics systems owing to its robust temporal isolation among applications. However, this partitioning mechanism causes the problem of how to optimize the partition scheduling of a complex system while guaranteeing its schedulability. In this paper, a model-based optimization approach is proposed. We formulate the problem as a parameter sweep application, which searches for the optimal partition scheduling parameters with respect to minimum processor occupancy via an evolutionary algorithm. An ARINC-653 partitioned scheduling system is modeled as a set of timed automata in the model checker UPPAAL. The optimizer tentatively assigns parameter settings to the models and subsequently invokes UPPAAL to verify schedulability as well as evaluate promising solutions. The parameter space is explored with an evolutionary algorithm that combines refined genetic operators and the self-adaptation of evolution strategies. The experimental results show the applicability of our optimization method. [ABSTRACT FROM AUTHOR]

Heterogeneous multicore processors have recently become de facto computing engines for state-of-the-art embedded applications. Nonetheless, very little research focuses on the scheduling of periodic (implicitdeadline) real-time tasks upon heterogeneous multicores under the requirements of task synchronization, which is stemmed from resource access conflicts and can greatly affect the schedulability of tasks. In view of partitioned Earliest Deadline First and Multiprocessor Stack Resource Policy, we first discuss the blocking-aware utilization bound for uniform heterogeneous multicores and then illustrate its nonmonotonicity, where the bound may decrease with more deployed cores. Following the insights obtained from the bound analysis, taking the system heterogeneity into consideration, we propose a Synchronization-Aware Task Partitioning Algorithm for Heterogeneous Multicores (SA-TPA-HM)). Several resource-guided and heterogeneity-oriented mapping heuristics are incorporated to reduce the negative impacts of blocking interferences for better schedulability performance of tasks and balanced workload distribution across cores. The extensive simulation results show that SA-TPA-HM can obtain the schedulability ratios approximate to an Integer Non-Linear Programming-based solution, and much higher (e.g., 60% more) in contrast to the existing partitioning algorithms targeted at homogeneous multicores. The measurement results in Linux kernel further reveal the practical viability of SA-TPA-HM that can experience lower runtime overhead (e.g., 15% less) when compared to other mapping schemes. [ABSTRACT FROM AUTHOR]

Predictable scheduling and resource sharing primitives are fundamental aspects of real-time systems. To prevent race conditions, access to shared resources must ensure mutual exclusion, e.g., using semaphores. Further, real-time locking protocols are required to avoid un-controlled priority inversions. For uniprocessor systems, the Priority Ceiling Protocol (PCP) has been widely accepted and supported in real-time operating systems. However, it remains arguable as to whether there exists a preferable approach for resource sharing in multiprocessor systems. In this paper, we show that the proposed Resource-Oriented Partitioned (ROP) scheduling with a distributed resource sharing policy, originating from the concept of the Distributed Priority Ceiling Protocol (DPCP), can achieve a non-trivial speedup factor guarantee. Specifically, we prove that the proposed R-PCP-rm-rm algorithm achieves a speedup factor of $11-6/(m+1)$11-6/(m+1) on a platform consisting of $m$m processors, where each job of a task may request at most one shared resource at most one time. Our empirical evaluations show that the proposed algorithm is highly effective in terms of task sets deemed schedulable. [ABSTRACT FROM AUTHOR]

Previous work focuses on the problem of energy for Imprecise Mixed-Criticality Systems on multiprocessor platforms, which provides degraded services for low criticality tasks in the high criticality mode. However, the proposed solution based on the partitioning heuristic Criticality-Unaware Worst Fit Decreasing method (CU-WFD) may consume more energy. In this paper, we propose a novel partitioning algorithm named EEAA based on the genetic algorithm and explore various parameter combinations, aiming to find a task-to-processor assignment method that can further reduce energy consumption with the best parameter combinations. In addition, we conduct experiments to evaluate EEAA and the experimental result shows that EEAA achieves energy savings of 12.56% compared to CU-WFD. [ABSTRACT FROM AUTHOR]

Multicore platforms are being increasingly adopted in Cyber-Physical Systems (CPS) due to their advantages over single-core processors, such as raw computing power and energy efficiency. Typically, multicore platforms use a shared memory bus that connects the cores to the off-chip main memory. This sharing of memory bus may cause tasks running on different cores to compete for access to the main memory whenever data/instructions are need to be read/written from/to the main memory. Such competition is problematic, as it may cause variations in the execution time of tasks in a non-deterministic way. To reduce the complexity of analyzing this problem, the 3-phase task model was proposed that divides tasks' executions into distinct memory and execution phases. The distinctive memory phases are then scheduled to eliminate/minimize main memory contention between concurrently executing tasks. However, 3-phase tasks running on different cores may still compete to access the shared memory bus/main memory in order to execute memory phases. This paper presents a partitioned scheduling-based approach that allows one to derive memory bus contention-aware worst-case response time of tasks that follow the 3-phase task model. In particular, the bus-contention analysis is derived by considering two memory access models, i.e., (i) dedicated memory access model, where a core having allowed to access the main memory via memory bus is permitted to execute more than one memory phase, and (ii) fair memory access model, that restrict each core to execute only one memory phase in its allocated bus access. Both these models represent different system and application requirements, and the resulting bus contention of tasks may vary depending on the considered model. To evaluate the effectiveness of the proposed bus contention analysis, we compare its performance against an existing analysis in the state-of-the-art by performing (i) case-study experiments, using benchmarks from the Mälardalen Benchmark suite, and (ii) empirical evaluation using synthetic task sets. Results show that our proposed analysis can improve task set schedulability of 3-phase tasks by up to 88 percentage points. [ABSTRACT FROM AUTHOR]

The scheduling of mixed-criticality implicit-deadline sporadic task systems on identical multiprocessor platforms is considered. Two approaches, one for global and another for partitioned scheduling, are described. Theoretical analyses and simulation experiments are used to compare the global and partitioned scheduling approaches. [ABSTRACT FROM AUTHOR]

The partitioned EDF scheduling of implicit-deadline sporadic task systems upon identical multiprocessor platforms is considered. The problem is known to be intractable, but many different polynomial-time algorithms have been proposed for solving it approximately. These different approximation algorithms have previously been compared using utilization bounds; they are compared here using a different metric—the speedup factor. It is shown that from the perspective of their speedup factors, the best partitioning algorithms are those that (i) assign the tasks in decreasing order of utilization; and (ii) are “reasonable” in the sense that they will assign a task if there is capacity available on some processor—such algorithms include the widely-used First-Fit Decreasing, Best-Fit Decreasing, and Worst-Fit Decreasing partitioning heuristics. [ABSTRACT FROM AUTHOR]

The design of cyber–physical systems (CPSs) is facing the explosion of new functionalities requiring increased computation capacities and, thus, the introduction of multi-core processors. Moreover, some functionalities may impose precedence constraints between the programs implementing these new functionalities. While important effort has been dedicated to the scheduling of precedence constraints tasks on multi-core processors, existing work considers either partitioned scheduling for a single precedence graph defining precedence constraints between sub-tasks, or global scheduling policies. In this paper, we consider partitioned scheduling for multiple precedence graphs defining precedence constraints between tasks. We propose a partitioning heuristic that minimizes communication delays while maximizing sub-tasks parallelism. We also propose to decrease the complexity of existing schedulability analysis by providing appropriate graph reductions. [ABSTRACT FROM AUTHOR]