We address the problem of scheduling periodic implicit-deadline real-time tasks on m uniform processors. We introduce PCG^*, an optimal TL-plane algorithm based on PCG [Chen and Hsueh, 2008], which guarantees at most 2(m - 1) preemptions per TL-plane, matching the best-known theoretical bound for uniform platforms. The proposed algorithm advances the state of the art by offering an optimal real-time scheduling solution with a tight preemption bound within TL-planes. The numerical experiments presented in this work provide strong evidence that PCG^* yields a substantial reduction in the number of preemptions relative to PCG. When applied to identical processor platforms, PCG^* is also a best-possible polynomial time algorithm in terms of preemptions in a TL-plane, matching the (m-1) preemption bound achieved by LRE-TL [Funk, 2010].

This paper introduces unfair-PCG, the first unfair optimal scheduling algorithm for periodic implicit-deadline tasks on uniform multiprocessor platforms. The approach leverages the TL-plane scheduling method, allowing tasks to execute beyond their local execution time if processing resources are available. The algorithm ensures optimal resource utilisation while meeting task deadlines, thereby enhancing response times and enabling power-saving mechanisms.

The seminal work on the global real-time scheduling of periodic tasks on unrelated multiprocessor platforms is based on a two-step method. First, the workload of each task is distributed over the processors and it is proved that this first step success ensures the existence of a feasible schedule. Then, using this workload assignment as an input, a template schedule construction method is presented. In this work, we review the seminal work and show by using a counter-example that this second step is incomplete. Thus, we propose and prove correct a novel and efficient algorithm to build the template schedule.

We study the implementation of data-flow applications on multi-core processor with on-chip shared multi-banked memory. Specifically, we consider the Kalray MPPA2 processor and three applications coded using the industrial toolchain SCADE Suite. We focus on the runtime environment assuming global static scheduling, time-triggered and non-preemptive execution of tasks. Our contributions include (i) a technique to implement SCADE applications compliant with execution models inspired by PREMs (PRe-dictable Execution Models), (ii) an exhaustive comparison of three execution models with and without isolation, and finally (iii) guidelines for predictable implementation of a data-flow application on multi-core processors with shared on-chip memory.

The demands for high performance computing with a low cost and low power consumption are driving a transition towards multi-core processors in many consumer and industrial applications. However, the adoption of multi-core processors in the domain of real-time systems faces a series of challenges that has been the focus of great research intensity during the last decade. These challenges arise in great part from the non real-time nature of the hardware arbiters that schedule the access to shared resources, such as the main memory. One solution proposed in the literature is called Memory Centric Scheduling, which defines a separate software scheduler for the sections of the tasks that will access the main memory, hence circumventing the low level unpredictable hardware arbiters. Several Memory Centric schedulers and associated theoretical analyses have been proposed, but as far as we know, no actual implementation of the required OS-level underpinnings to support dynamic event-driven Memory Centric Scheduling has been presented before. In this paper we aim to fill this gap, targeting cache based COTS multi-core systems. We will confirm via measurements the main theoretical benefits of Memory Centric Scheduling (e.g. task isolation). Furthermore, we will describe an effective schedulability analysis using concepts from distributed systems.

3D stacked ICs package multiple, independently manufactured dies to reduce total system wire-length, improve timing, and reduce area and power. When designing stacked 3D-ICs, arises the question of the grain at which one should consider system partitioning to optimize the gains. This work uses known MAX-CUT graph partitioning algorithms to split designs from 42k up to 800k gates, with gates clustered from 8 and up to 32768 partitions. It has been found that with 2048 clusters, i.e. 20 to 400 gates per cluster depending on the design, a partitioning of the system allows on average to cut 35% of the nets that account for 73% of the total wire-length in 3D.

Nowadays, most processing platforms make use of cache memories to improve the execution speed of the tasks running on the processors. However, when a processor switches from a task to another, the caches must be reloaded with the context of the upcoming task. This is time consuming and is usually not predictable and thus affects the worst-case execution time of the task. Such unpredictability should be avoided in real-time systems in which the instant at which a result is available is as important as the result itself. In this paper, we present a hardware component named hardware context switch (HwCS) which replaces the standard L1 cache controller of a processor. It divides the cache in two interchangeable layers and enables to save or restore the content of one layer while the second is simultaneously used as a usual cache by the processor. Saving the cache content after a preemption and restoring this content before resuming the execution of the preempted task, makes the preemption overheads negligible in comparison to the task worst-case execution times. It is theoretically proven that the existing scheduling theory can be used “as is” with the HwCS by simply reducing the task deadlines, thereby bridging the gap between theory and practice. The HwCS has been implemented in an uniprocessor system as a proof of concept. The first results show a neat improvements on the processor utilisation for a small cost in silicon surface.

In this work, we investigate the potential benefit of parallelization for both meeting real-time constraints and minimizing power consumption. We consider malleable Gang scheduling of implicit-deadline sporadic tasks upon multiprocessors. By extending schedulability criteria for malleable jobs to DPM/DVFS-enabled multiprocessor platforms, we are able to derive an offline polynomial-time optimal processor/frequency-selection algorithm. Simulations of our algorithm on randomly generated task systems executing on platforms having up to 16 processing cores show that the theoretical power consumption is reduced by a factor of 36 compared to the optimal non-parallel approach.

These last years, we have witnessed a dramatic increase in the number of cores available in computational platforms. Concurrently, a new coding paradigm dividing tasks into smaller execution instances called threads, was developed to take advantage of the inherent parallelism of multiprocessor platforms. However, only few methods were proposed to efficiently schedule hard real-time multi-threaded tasks on multiprocessor. In this paper, we propose techniques optimizing the number of processors needed to schedule such sporadic parallel tasks with constrained deadlines. We first define an optimization problem determining, for each thread, an intermediate (artificial) deadline minimizing the number of processors needed to schedule the whole task set. The scheduling algorithm can then schedule threads as if they were independent sequential sporadic tasks. The second contribution is an efficient and nevertheless optimal algorithm that can be executed online to determine the thread's deadlines. Hence, it can be used in dynamic systems were all tasks and their characteristics are not known a priori. We finally prove that our techniques achieve a resource augmentation bound of 2 when the threads are scheduled with algorithms such as U-EDF, PD2, LLREF, DP-Wrap, etc.

A multiprocessor scheduling algorithm named U-EDF, was presented in [1] for the scheduling of periodic tasks with implicit deadlines. It was claimed that U-EDF is optimal for periodic tasks (i.e., it can meet all deadlines of every schedulable task set) and extensive simulations showed a drastic improvement in the number of task preemptions and migrations in comparison to state-of-the-art optimal algorithms. However, there was no proof of its optimality and U-EDF was not designed to schedule sporadic tasks. In this work, we propose a generalization of U-EDF for the scheduling of sporadic tasks with implicit deadlines, and we prove its optimality. Contrarily to all other existing optimal multiprocessor scheduling algorithms for sporadic tasks, U-EDF is not based on the fairness property. Instead, it extends the main principles of EDF so that it achieves optimality while benefiting from a substantial reduction in the number of preemptions and migrations.

Current trends in the embedded systems field tend to collocate multiple functionalities upon a single computing platform, the aim being to reduce both the size and cost of embedded systems. Nevertheless, it is unlikely that all functionalities share the same level of criticality, and certification of the system has to be achieved using varying degrees of rigorousness. Typically, a task tau_i is guaranteed to meet its temporal constraints up to a criticality level that is equal to its own criticality. When those conditions are no longer met, i.e. when another higher priority task tau_j has its execution time that exceeds its Worst Case Execution Time (WCET) w.r.t. the criticality level of tau_i, a common approach is to suspend tau_i. However, in some cases, it may not be necessary to suspend tasks with a lower criticality immediately as they could still be executed without compromising the deadlines of high criticality tasks. As a step towards this aim, we propose a method, denoted Latest Completion Time (LCT), that allows lower criticality tasks to proceed with their execution as long as they do not prevent higher criticality tasks from meeting their deadlines. Furthermore, we show that tasks suspension can only be temporary, and prove that a particular definition of idle times can be used to reset the system's criticality level. Finally, we study the performances of our LCT mechanism w.r.t. the classical mechanism that suspends a task as soon as the system criticality level becomes higher than its own criticality.

EKG is a multiprocessor scheduling algorithm which is optimal for the scheduling of real-time periodic tasks with implicit deadlines. It consists in a semi-partitioned algorithm which adheres to the deadline partitioning fair (DP-Fair) theory. It was shown in recent studies that the division of the time in slices bounded by two successive deadlines and the systematic execution of migratory tasks in each time slice inherent in DP-Fair algorithms, significantly reduce the practicality of EKG. Nevertheless, its semi-partitioned approach allows to bound the number of migrating tasks and increases the locality of the tasks in memories, thereby lowering the time overheads imposed by task preemptions and migrations. Hence, we propose two techniques with the aim of reducing the amount of preemptions and migrations incurred by the system when scheduled with EKG, while maintaining the advantages of its semi-partitioned approach. The first improvement consists in a swapping algorithm which exchanges execution time between tasks and time slices. The second one aims at decreasing the number of time slices needed to ensure that all job deadlines are respected. Both have a strong impact on the number of preemptions and migrations while keeping the optimality of EKG.

Abstract-Over the past two decades, numerous optimal scheduling algorithms for real-time systems on multiprocessor platforms have been proposed for the Liu & Layland task model. However, recent studies showed that even if optimal algorithms can theoretically schedule any feasible task set, suboptimal algorithms usually perform better when executed on real computation platforms. This can be explained by the runtime overheads that such optimal algorithms induce. We have observed that all current optimal online multiprocessor real-time scheduling algorithms are (completely or partially) based on the notion of fairness. The respect of this fairness can be the cause of numerous preemptions and migrations. We therefore propose a new algorithm -named U-EDF- which releases the property of fairness and instead use an EDF-like scheduling policy. The simulation results are really encouraging since they show that, in average, U-EDF produces less than one preemption and one migration per job released during the schedule. Furthermore, we strongly believe in the optimality of our algorithm since all tested task sets were correctly scheduled under U-EDF.

In this paper we study the partitioning approach for multiprocessor real-time scheduling. This approach seems to be the easiest since, once the partitioning of the task set has been done, the problem reduces to well understood uniprocessor issues. Meanwhile, there is no optimal and polynomial solution to partition tasks on processors. In this paper we analyze partitioning algorithms from several points of view such that for a given task set and specific constraints (processor number, task set type, etc.) we should be able to identify the best heuristic and the best schedulability test. We also analyze the influence of the heuristics on the performance of the uniprocessor tests and the impact of a specific task order on the schedulability. A study on performance difference between Fixed Priority schedulers and EDF in the case of partitioned scheduling is also considered.

In this paper, we address the scheduling problem of multi-mode real-time systems upon uniform multiprocessor platforms. We propose two transition protocols, specified together with their schedulability test, and provide the reader with two distinct upper bounds for the length of the transient phases during mode transitions, respectively for the cases where jobs priorities are known and unknown beforehand.

We consider the global and preemptive scheduling problem of multi-mode real-time systems upon identical multiprocessor platforms. Since it is a multi-mode system, the system can change from one mode to another such that the current task set is replaced with a new task set. Ensuring that deadlines are met requires not only that a schedulability test is performed on tasks in each mode but also that (i) a protocol for transitioning from one mode to another is specified and (ii) a schedulability test for each transition is performed. We propose two protocols which ensure that all the expected requirements are met during every transition between every pair of operating modes of the system. Moreover, we prove the correctness of our proposed algorithms by extending the theory about the makespan determination problem.

In this paper, we address the global and preemptive energy-aware scheduling problem of sporadic constrained-deadline tasks on DVFS-identical multiprocessor platforms. We propose an online slack reclamation scheme which profits from the discrepancy between the worst- and actual-case execution time of the tasks by slowing down the speed of the processors in order to save energy. Our algorithm called MORA takes into account the application-specific consumption profile of the tasks. We demonstrate that MORA does not jeopardize the system schedulability and we show by performing simulations that it can save up to 32% of energy (in average) compared to execution without using any energy-aware algorithm.

The global EDF scheduling of sporadic task systems upon uniform multiprocessor platforms is studied. A sufficient schedulability test is presented and proved correct. It is shown that this test generalizes the previously-known exact uniprocessor, and sufficient identical multiprocessor, EDF- schedulability tests.

Feasibility analysis algorithms are based on particular metrics such as processor utilization, load factor, processor demand, response-times, etc. The design of efficient algorithms for computing these metrics is a major issue in real-time scheduling theory. In this paper we propose two FPTASs (fully-polynomial time approximation schemes) for checking feasibility of static-priority tasks subjected to release jitters executed upon a uniprocessor platform. We then use these FPTASs for computing two upper bounds of worst-case response-times. Lastly, we show that these bounds do not achieve constant error bounds in comparison with values computed by an exact worst-case response-time analysis (performed in pseudo-polynomial time), and we present numerical experiments.

In this paper we study the global scheduling of periodic task systems upon uniform multiprocessor platforms. We first show two very general properties which are well-known for uniprocessor platforms and which remain for multiprocessor one: (i) under few and not so restrictive assumptions, we show that any feasible schedules of periodic task system are periodic from some point and (ii) for the specific case of synchronous periodic task systems, we show that the schedule repeats from the origin. We then present our main result: any feasible schedules of asynchronous periodic task sets using a fixed-priority scheduler are periodic from a specific point. Moreover, we characterize that point and we provide a feasibility interval for those systems.

In this paper we tackle the problem of scheduling a periodic real time system on identical multiprocessor platforms, moreover the tasks considered may fail with a given probability. For each task we compute its duplication rate in order to (1) given a maximum tolerated probability of failure, minimize the size of the platform such at least one replica of each job meets its deadline (and does not fail) using a variant of EDF namely EDF(k)or (2) given the size of the platform, achieve the best possible reliability with the same constraints. Thanks to our probabilistic approach, no assumption is made on the number of failures which can occur. We propose several approaches to duplicate tasks and we show that we are able to find solutions always very close to the optimal one

Scheduling stochastic workloads is a difficult task. In order to design efficient scheduling algorithms for such workloads, it is required to have a good in-depth knowledge of basic random scheduling strategies. This paper analyzes the distribution of sequential jobs and the system behavior in heterogeneous computational grid environments where the brokering is done in such a way that each computing element has a probability to be chosen proportional to its number of CPUs and (new from the previous paper) its relative speed. We provide the asymptotic behavior for several metrics (queue-sizes, slowdowns, etc.) or, in some cases, an approximation of this behavior. We study these metrics for a variety of workload configurations (load, distribution, etc.). We compare our probabilistic analysis to simulations in order to validate our results. These results provide a good understanding of the system behavior for each metric proposed. This enables us to design advanced and efficient algorithms for more complex cases.

Each processor in a uniform multiprocessor machine is characterized by a speed or computing capacity, with the interpretation that a job executing on a processor with speed s for t time units completes (s /spl times/ t) units of execution. The scheduling of systems of periodic tasks on uniform multiprocessor platforms using the rate-monotonic scheduling algorithm is considered here. A simple, sufficient test is presented for determining whether a given periodic task system will be successfully scheduled by algorithm upon a particular uniform multiprocessor platform-this test generalizes earlier results concerning rate-monotonic scheduling upon identical multiprocessor platforms.

Each processor in a uniform multiprocessor machine is characterized by a speed or computing capacity, with the interpretation that a job executing on a processor with speed s for t time units completes (s /spl times/ t) units of execution. The earliest deadline first (EDF) scheduling of hard-real-time systems upon uniform multiprocessor machines is considered. It is known that online algorithms tend to perform very poorly in scheduling such hard-real-time systems on multiprocessors; resource-augmentation techniques are presented here that permit online algorithms in general (EDF in particular) to perform better than may be expected given these inherent limitations. It is shown that EDF scheduling upon uniform multiprocessors is robust with respect to both job execution requirements and processor computing capacity.

The rate-monotonic algorithm is arguably one of the most popular algorithms for scheduling systems of periodic real-time tasks. The rate-monotonic scheduling of systems of periodic tasks on uniform multiprocessor platforms is considered here. A simple, sufficient test is presented for determining whether a given periodic task system will be successfully scheduled by this algorithm upon a particular uniform multiprocessor platform-this test generalizes earlier results concerning rate-monotonic scheduling upon identical multiprocessor platforms.

H. Chetto and M. Chetto (1989) presented an algorithm for the online admission control and run-time scheduling of aperiodic real-time jobs in preemptive uniprocessor environments that are executing systems of periodic hard real-time tasks. This algorithm requires a significant degree of preprocessing of the system of periodic tasks - in general, this preprocessing takes a time that is exponential in the representation of the periodic task system. In this paper, we develop techniques for speeding up the preprocessing phase of the Chetto & Chetto algorithm, by adapting it for implementation in parallel environments. We validate the effectiveness of our parallelization both by theoretical results and through simulation experiments.

Each processor in a uniform multiprocessor machine is characterized by a speed or computing capacity, with the interpretation that a job executing on a processor with speed s for t time units completes (s/spl times/t) units of execution. The on-line scheduling of hard-real-time systems, in which all jobs must complete by specified deadlines, on uniform multiprocessor machines is considered It is known that online algorithms tend to perform very poorly in scheduling such hard-real-time systems on multiprocessors; resource-augmentation techniques are presented here that permit online algorithms to perform better than may be expected given the inherent limitations. Results derived here are applied to the scheduling of periodic task systems on uniform multiprocessor machines.

In this paper we study the problem of scheduling hard real-time periodic task sets with a dynamic and preemptive scheduler. We will focus on the response time notion, its interest and its effective computation for the deadline driven scheduler. We pr