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]

Modern cyber-physical embedded systems are characterized by a range of intricate functionalities that are subject to tight timing constraints. Unfortunately, traditional sequential task models and uniprocessors solutions are not suitable for this context: a more expressive model becomes necessary. In such cases, the Directed Acyclic Graph (DAG) is a proper model to express the complexity and the parallelism of the tasks of these kinds of systems. In recent years, several methods with different settings have been proposed to solve the schedulability problem for applications featuring DAG tasks. This paper presents a survey of the state-of-the-art of the DAG task model, focusing on scheduling tests that are more effective, easy to implement, and adopt, while providing a detailed comparison of global and partitioned scheduling solutions. Besides discussing the approaches and presenting them under a common convention, this work is the first to present a comprehensive experimental analysis of several state-of-the-art tests, thanks to the development of a C++ library that implements all the methods, which is made available at url will be inserted for camera-ready. [ABSTRACT FROM AUTHOR]

Timing verification of multi-core systems is complicated by contention for shared hardware resources between co-running tasks on different cores. This paper introduces the Multi-core Resource Stress and Sensitivity (MRSS) task model that characterizes how much stress each task places on resources and how much it is sensitive to such resource stress. This model facilitates a separation of concerns, thus retaining the advantages of the traditional two-step approach to timing verification (i.e. timing analysis followed by schedulability analysis). Response time analysis is derived for the MRSS task model, providing efficient context-dependent and context independent schedulability tests for both fixed priority preemptive and fixed priority non-preemptive scheduling. Dominance relations are derived between the tests, along with complexity results, and proofs of optimal priority assignment policies. The MRSS task model is underpinned by a proof-of-concept industrial case study. The problem of task allocation is considered in the context of the MRSS task model, with Simulated Annealing shown to provide an effective solution. [ABSTRACT FROM AUTHOR]

Recent real-time systems have been gradually connected externally through the Internet. As each subsystem constituting a system has been developed from different vendors, the number of cases of security vulnerabilities in communication between subsystems has increased. In particular, real-time systems are vulnerable to timing inference attacks, such as cache-based side-channel attacks. Among the various methods for handling security problems of these systems, the flush task (FT) method is a simple and effective method to reduce the probability of information leakage by conditionally initializing the state of resources shared by tasks before a given scheduling. However, existing FT methods are for global scheduling only, and techniques for partitioned scheduling have not yet been studied. In this paper, we propose an FT-aware bin-packing (FT-bin-packing) algorithm that effectively allocates real-time tasks to identical multiprocessors to reduce the number of FTs invoked during the schedule of tasks in each processor. Based on the experimental results, we analyze the properties and performance of the FT-bin-packing algorithm. These results indicate that it can improve the performance of existing heuristic algorithms by up to 96.8% depending on the experimental setting.

How to schedule the sensor transactions to maintain the temporal validity of real-time data is an important research issue for cyber-physical systems. Current studies on sensor transaction scheduling assume that the sensor transactions are executed on a platform with continuous resource supply. This assumption does not hold for component-based systems where each component's transactions obtain a fraction of the resources that are usually supplied by the underlying platform in a non-continuous manner. In this paper, we study the problem of scheduling sensor transactions in component-based systems. The sensor transactions are assumed to be executed in one component of the system that is deployed on a multiprocessor platform. The resource supply of each processor follows the explicit-deadline periodic (EDP) resource model. A partitioned scheduling method named PS-FC is proposed at first. It uses a sufficient and necessary condition of EDF scheduling upon an EDP resource to check the feasibility of each transaction on a processor. Then two faster partitioned scheduling methods, named PS-CI and PS-Hybrid, are proposed. PS-CI does the feasibility checks for transactions based on the candidate intervals of transaction deadlines. PS-Hybrid is a combination of PS-FC and PS-CI. The effectiveness and efficiency of the methods are evaluated through extensive experiments. [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]

Shared caches in multi-core processors introduce serious difficulties in providing guarantees on the real-time properties of embedded software due to the interaction and the resulting contention in the shared caches. Prior work has studied the schedulability analysis of global scheduling for real-time multi-core systems with shared caches. This article considers another common scheduling paradigm: partitioned scheduling in the presence of shared cache interference. To achieve this, we propose CITTA, a cache interference-aware task partitioning algorithm. We first analyze the shared cache interference between two programs for set-associative instruction and data caches. Then, an integer programming formulation is constructed to calculate the upper bound on cache interference exhibited by a task, which is required by CITTA. We conduct schedulability analysis of CITTA and formally prove its correctness. A set of experiments is performed to evaluate the schedulability performance of CITTA against global EDF scheduling and other greedy partition approaches such as First-fit and Worst-fit over randomly generated task sets and realistic workloads in embedded systems. Our empirical evaluations show that CITTA outperforms global EDF scheduling and greedy partition approaches in terms of task sets deemed schedulable. [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]

Summary: Real‐time systems are nowadays extensively used in most time‐critical embedded applications. The existing multiprocessor real‐time scheduling algorithms are based on partitioned and global scheduling approaches. The partitioned‐based algorithms suffer poor utilization bound, load balancing, not compatible for an open system environment, and the global scheduling approach faces problems like high scheduling, migration overhead. Cluster scheduling represents a hybrid scheduling approach which consists of a set of processors as clusters and tasks scheduled to each processor of clusters using a global scheduling approach. The different cluster formation heuristics are investigated for homogenous clusters. The main objective of this article is to propose task utilization‐based cluster formation and harmonic period aware task allocation for a hierarchical real‐time system on a multiprocessor platform. Tasks with high utilization, cluster size tune to a smaller value to achieve high utilization. Tasks with low utilization, the size of cluster tune to larger to reduce migration and scheduling overheads. Experimentation performed on multiprocessor real‐time simulator with a different set of tasks, multiprocessor system, different tasks utilization, and cluster size. Simulation results show that cluster base approach increases the number of tasks scheduled on a multiprocessor system, system utilization, and reduces response time, migration, and preemption overheads. [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]

As the computing devices and software executions are susceptible to manifold faults, fault tolerance has been an important research topic in safety-critical real-time systems. Moreover, multicore processors have recently emerged as prevailing computing engines for modern embedded systems. However, there exists rather rare work on the fault-tolerant scheduling of real-time tasks executing on multicores with shared resources, where the task synchronization originated from resource access contention may significantly degrade the schedulability of task system. With the focus on the partitioned-EDF scheduler with the MSRP (Multiprocessor Stack Resource Policy) protocol and primary/backup recovery mechanism, we first investigate a utilization bound and then identify its anomaly where the bound may decrease when more cores are deployed. Next, following the insights gained by the analysis of the bound, we propose a reliability and synchronization aware task partitioning algorithm (RSA-TPA) together with an efficient version to implement the joint management of task synchronization and system reliability, where several resource-oriented heuristics are developed to improve both the schedulability performance and workload balancing. The extensive simulation results show that the RSA-TPA schemes can obtain higher acceptance ratio (e.g., 60 percent more) and generate more balanced partitions, when compared to the existing schemes that consider either reliability management or task synchronization. Finally, with the different fault arrival rates being considered, the actual implementation in Linux kernel further demonstrates the applicability of RSA-TPA that has lower run-time overhead (e.g., 20 percent less) in comparison with other mapping algorithms. [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]

We study the worst case response time (WCRT) analysis and evaluation for sporadic message-processing tasks in a multicore automotive gateway of a controller area network (CAN) cluster. We first build a multicore automotive gateway on CAN clusters. Two WCRT analysis methods for message-processing tasks in the multicore gateway are subsequently presented based on global and partitioned scheduling paradigms. We evaluate the WCRT results of two analysis methods with real message sets provided by the automaker, and present the design optimization guide. [ABSTRACT FROM AUTHOR]

The increasing industrial demand for handling complex functionalities has influenced the design of hardware architectures for time critical embedded systems, during the past decade. Multicore systems facilitate the inclusion of many complex functionalities, while, at the same time, inducing cache related overheads, as well as adding partitioning complexity to the overall system schedulability. One of the efficient paradigms for controlling and reducing the cache related costs in real-time systems is limited preemptive scheduling (LPS), with its particular instance fixed preemption points scheduling (LP-FPPS), which has been shown to outperform other alternatives as well as has been supported by and investigated in the automotive domain. With respect to the partitioning constraints, partitioned scheduling has been widely used to preruntime allocate tasks to specific cores, resulting in predictable cache-related preemption delays estimations. In this paper, we propose to integrate the LP-FPPS and partitioned scheduling on fixed-priority multicore real-time systems in order to increase the overall system schedulability. We define a new joint approach for task partitioning and preemption point selection, which is based on the computation of the maximum blocking tolerance upon each allocation, thus being able to quantify the schedulability of the taskset on each processor. Furthermore, we investigate the partitioning strategies based on different heuristics, i.e., first fit decreasing and worst fit decreasing, and priority and density taskset orderings. The evaluation performed on randomly generated tasksets shows that in the general case, no single partitioning strategy fully dominates the others. However, the evaluation results reveal that the certain partitioning strategies perform significantly better with respect to the overall schedulability for specific taskset characteristics. The results also reveal that the proposed partitioning strategies outperform fully preemptive and nonpreemptive partitioned scheduling in terms of successful partitioning. [ABSTRACT FROM AUTHOR]

It remains a challenging problem to tightly estimate the worst-case response time of an application in a distributed embedded system, especially when there are dependencies between tasks. Recently, a holistic worst-case response time analysis approach called scheduling time bound analysis has been proposed to find a tight upper bound of the worst-case response times of applications specified by a set of task graphs. Since it assumes that the starting offsets of applications are known and fixed, it fails to make a tight estimation despite increased computation time when the starting offsets are dynamic. To overcome this problem, we propose a novel conservative performance analysis, called hybrid performance analysis, combining the response time analysis technique and the scheduling time bound analysis technique to compute a tighter bound faster. The proposed scheme is proven to be conservative formally. Through extensive experiments with real-life benchmarks and synthetic examples, the superior performance of our proposed approach compared with previous methods is confirmed. [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]

In mixed-criticality (MC) systems, multiple activities with various certification requirements (thus with different criticality levels) can co-exist on shared hardware platforms, where multicore processors have emerged as the de facto computing engines. In this paper, by using the partitioned earliest-deadline-first with virtual deadlines (EDF-VDs) scheduler for a set of periodic MC tasks running on multicore systems, we derive a criticality-aware utilization bound for efficient feasibility tests and then identify its characteristics. Our analysis shows that the bound increases with increasing number of cores and decreasing system criticality level. We show that, since the utilizations of MC tasks at different criticality levels can vary considerably, the utilization contribution of a task on different cores may have large variations and thus can significantly affect the system schedulability under the EDF-VD scheduler. Based on these observations, we propose a novel and efficient criticality-aware task partitioning algorithm (CA-TPA) to compensate for the inherent pessimism of the utilization bound. In order to improve the system schedulability, the task priorities are determined according to their utilization contributions to the system in CA-TPA. Moreover, by analyzing the utilization variations of tasks at different levels, we develop several heuristics to minimize the utilization increment and balance the workload on cores. The simulation results show that the CA-TPA scheme is very effective in achieving higher schedulability ratio and yielding balanced workloads. The actual implementation in Linux operating system further demonstrates the applicability of CA-TPA with lower run-time overhead, compared to the existing partitioning schemes. [ABSTRACT FROM PUBLISHER]

In this paper, we address the problem of executing (soft) real-time data processing applications on heterogeneous computing platforms with the goal of reducing the energy consumption. The typical application domain is edge computing (or fog computing ), where a certain amount of data, collected from the environment, needs to be pre-processed in real-time before being sent to the central server for storage and final processing. The kind of applications we address here can be easily parallelized, and we also need to reduce as much as possible the necessary energy to perform such tasks. Heterogeneous Multi-core Processors (HMP) such as ARM big.LITTLE are designed to combine both performances and energy efficiency, so they are one of the preferred choices for this kind of applications. Here we focus on Dynamic Voltage and Frequency Scaling (DVFS), parallelization, real-time scheduling and resource allocation techniques. In the first part of the paper, we present a model of the performance and energy consumption of a parallel real-time task executed on an ARM bigLITTLE architecture. We use this model in the second part of the paper where we first define the optimization problem as an Integer Non-linear Programming (INLP) problem, and then propose heuristics for efficiently solving it. Finally, we present a wide range of synthetic experiments that demonstrate the performance of our approach. [ABSTRACT FROM AUTHOR]

This article introduces schedulability analysis for Global Fixed Priority Scheduling with Deferred Preemption (gFPDS) for homogeneous multiprocessor systems. gFPDS is a superset of Global Fixed Priority Preemptive Scheduling (gFPPS) and Global Fixed Priority Nonpreemptive Scheduling (gFPNS). We show how schedulability can be improved using gFPDS via appropriate choice of priority assignment and final nonpreemptive region lengths, and provide algorithms that optimize schedulability in this way. Via an experimental evaluation we compare the performance of multiprocessor scheduling using global approaches: gFPDS, gFPPS, and gFPNS, and also partitioned approaches employing FPDS, FPPS, and FPNS on each processor. [ABSTRACT FROM AUTHOR]

In real-time systems, both scheduling theory and resource access protocols have been studied extensively. However, there is very limited research on scheduling algorithms for real-time systems with shared resources, where the problem becomes more prominent with the emergence of multicore processors. In this paper, focusing on partitioned-EDF scheduling and MSRP resource access protocol, we study the utilization bound and efficient task mapping schemes for a set of periodic real-time tasks that access shared resources in multiprocessor/multicore systems. Specifically, with synchronization overhead being considered, we illustrate the schedulability anomaly for such systems. We develop the first synchronization-cognizant utilization bound and further analyze its non-monotonicity where the bound can decrease when more processors are deployed. Then, we show that finding the optimal mapping for tasks with shared resources is NP-hard. Based on a novel approach that iteratively tightens the synchronization overhead, we propose two efficient synchronization-cognizant task mapping algorithms (SC-TMA) with the goal of achieving better schedulability and balanced workload on deployed processors. Finally, the proposed SC-TMA schemes are evaluated through extensive simulations with synthetic tasks. The results show that, the schedulability ratio and (average) system load under SC-TMA are close to that of an INLP (Integer Non-Linear Programming) based solution for small task systems. When compared to the existing task mapping algorithms, SC-TMA obtain much better schedulability ratio and lower/balanced workload on all processors. [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]

Most prior theoretical research on real-time partitioning algorithms for multiprocessor platforms has focused on ensuring that the cumulative computing requirements of the tasks assigned to each processor does not exceed the processor's processing power. However, computing capacity is often not the only limiting resource: on many multiprocessor platforms each individual computing unit may have limited amounts of multiple additional types of resources (such as local memory) in addition to having limited processing power. We present algorithms for partitioning a collection of sporadic tasks, each characterized by a WCET, a relative deadline, and a period, upon a multiprocessor platform in a manner that is cognizant of such additional constraints as well as the processing capacity constraints. [ABSTRACT FROM AUTHOR]

Abstract The DBF algorithm of sporadic task systems on multiprocessors uses the approximation of the exact demand bound function on uniprocessor as a criterion. The systems which are feasible under the partitioned paradigm are flagged as 'infeasible' sometimes. In this paper, we present a novel efficient DBF( eDBF) partitioned scheduling algorithm. A criterion which tracks the demand bound function exactly as needed is used to avoid the incorrect judgment in determining whether a processor can accommodate an additional task in the new algorithm. We give the pseudo code of the new algorithm on least-number processors and fixed-number processors respectively. Then, we prove the correctness of, and evaluated the effectiveness of this new algorithm. The experimental results demonstrate that eDBF has better performance than DBF and Density algorithms. [ABSTRACT FROM AUTHOR]

This survey covers hard real-time scheduling algorithms and schedulability analysis techniques for homogeneous multiprocessor systems. It reviews the key results in this field from its origins in the late 1960s to the latest research published in late 2009. The survey outlines fundamental results about multiprocessor real-time scheduling that hold independent of the scheduling algorithms employed. It provides a taxonomy of the different scheduling methods, and considers the various performance metrics that can be used for comparison purposes. A detailed review is provided covering partitioned, global, and hybrid scheduling algorithms, approaches to resource sharing, and the latest results from empirical investigations. The survey identifies open issues, key research challenges, and likely productive research directions. [ABSTRACT FROM AUTHOR]

This letter presents partition-oriented ERfair scheduler (POES), a low-overhead proportional fair scheduler for hard real-time multiprocessor embedded systems. POES achieves lower overheads using an online partitioning/merging mechanism that retains the optimal schedulability of a fully global scheduler by merging processor groups as resources become critical while using partitioning for fast scheduling at other times. The principal objective is to remain only just as global at any given instant of time as is necessary to maintain ERfair schedulability of the system throughout the schedule length. Experimental results reveal that POES incurs almost no migrations at low workloads and achieves up to 32 times reduction in the number of migrations suffered with respect to the global ERfair scheduler on a set of two to 16 processors even when the average system load is as high as 85%. Theoretical analysis proves that POES typically has the same amortized complexity as that of the global ERfair algorithm. [ABSTRACT FROM PUBLISHER]

Abstract: Proportionate fair schedulers provide an effective methodology for scheduling recurrent real-time tasks on multiprocessors. However, a drawback in these schedulers is that they ignore a task’s affinity towards the processor where it was executed last, causing frequent inter-processor task migrations which ultimately results in increased execution times. This paper presents Partition Oriented Frame Based Fair Scheduler (POFBFS), an efficient proportional fair scheduler for periodic firm and soft real-time tasks that ensures a bounded number of task migrations. Experimental results reveal that POFBFS can achieve 3 to 100 times reduction in the number of migrations suffered with respect to the General-ERfair algorithm (for a set of 25 to 100 tasks running on 2 to 8 processors) while simultaneously maintaining high fairness accuracy. [Copyright &y& Elsevier]

Recently, real-time application models where tasks may have as early as possible (ASAP) or as late as possible (ALAP) execution preferences, while meeting their deadlines, have been proposed and studied. In this work we consider the preference-oriented (PO) real-time scheduling problem for multiprocessor systems. Specifically, we focus on partitioned scheduling of fixed-priority preference-oriented real-time tasks on multiprocessor platforms. Firstly, we explore the use of the Reverse-Preference Priority Assignment (RPPA) scheme, where ALAP tasks are assigned higher priority compared to ASAP tasks on a given processor. Counter-intuitively, this helps the tasks to better fulfill their execution preferences when deployed in the context of the Preference-Oriented Fixed-Priority (POFP) scheduler. Then, considering the complementary execution preferences of the ASAP and ALAP tasks, we propose a preference-oriented partitioning algorithm to allocate tasks to processors. Finally, we extend the algorithm to exploit the period information about the ALAP and ASAP tasks when making the task allocation decisions. The proposed RPPA and preference-oriented partitioning algorithms are evaluated through extensive simulations. The results show that, when the POFP scheduler is adopted, RPPA can significantly improve the execution preferences of ALAP tasks with only marginal impact on ASAP tasks compared to the state-of-the-art priority assignment schemes. Furthermore, compared to the classical utilization based worst-fit-decreasing (WFD) partitioning scheme, the proposed PO partitioning schemes provide more opportunities for both ASAP and ALAP tasks to better fulfill their execution preferences, especially when combined with RPPA and POFP scheduling on each processor. • A novel Reverse-Preference Priority Assignment scheme for POFP scheduler is proposed • New Preference-Oriented partitioning algorithms are devised and analyzed • The schemes are evaluated via simulations and the results show their effectiveness [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]

A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks, each constrained to have its relative-deadline parameter be no larger than its period parameter, among the processors of an identical multiprocessor platform. Since the partitioning problem is easily seen to be NP-hard in the strong sense, this algorithm is unlikely to be optimal. A quantitative characterization of its worst-case performance is provided in terms of resource augmentation: It is shown that any set of sporadic tasks that can be partitioned among the processors of an m-processor identical multiprocessor platform will be partitioned by this algorithm on an m-processor platform in which each processor is (3 - 1/m) times as fast. [ABSTRACT FROM AUTHOR]

Schedulability is a fundamental problem in analyzing real-time systems, but it often has to be approximated because of the intrinsic computational hardness. Partitioned earliest deadline first (EDF) is one of the most popular polynomial-time and practical scheduler on multiprocessor platforms, and it was shown to have a speedup factor of at most 2.6322 − 1 / m. This paper further improves the factor to 2.5556 − 1 / m for both the constrained-deadline case and the arbitrary-deadline case, and it is very close to the known (non-tight) lower bound of 2.5 − 1 / m. The key ideas are that we develop a novel method to discretize and regularize sporadic task sets that are schedulable on uniprocessors, and we find that the ratio (ρ) of the approximate demand bound value to the machine capacity is upper-bounded by 1.5556 for the arbitrary-deadline case, which plays an important role in estimating the speed factor of partitioned EDF. [ABSTRACT FROM AUTHOR]