skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: A Soft-Real-Time-Optimal Semi-Clustered Scheduler with a Constant Tardiness Bound
Different global and semi-partitioned schedulers have been proposed that are soft-real-time (SRT) optimal for sporadic task systems, meaning they can guarantee bounded deadline tardiness. However, under known analyses, tardiness bounds increase with respect to the number of processors, which reduces the applicability of these schedulers in systems with a large number of processors. In this paper, a semi-clustered scheduler, SC-EDF, is presented that has a constant tardiness bound. SC-EDF partitions tasks into clusters, each of which may include one fractional processor. Each cluster is scheduled by G-EDF, and the fractional processors are realized using Pfair scheduling techniques.  more » « less
Award ID(s):
1837337 1717589
PAR ID:
10205876
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Proceedings of the 26th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications
Page Range / eLocation ID:
1 to 10
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Proceedings of the 27th International Conference on Real-Time Networks and Systems)
    Semi-partitioned scheduling is an approach to multiprocessor real-time scheduling where most tasks are fixed to processors, while a small subset of tasks is allowed to migrate. This approach offers reduced overhead compared to global scheduling, and can reduce processor capacity loss compared to partitioned scheduling. Prior work has resulted in a number of semi-partitioned scheduling algorithms, but their correctness typically hinges on a complex intertwining of offline task assignment and online execution. This brittleness has resulted in few proposed semi-partitioned scheduling algorithms that support dynamic task systems, where tasks may join or leave the system at runtime, and few that are optimal in any sense. This paper introduces EDF-sc, the first semi-partitioned scheduling algorithm that is optimal for scheduling (static) soft real-time (SRT) sporadic task systems and allows tasks to dynamically join and leave. The SRT notion of optimality provided by EDF-sc requires deadline tardiness to be bounded for any task system that does not cause over-utilization. In the event that all tasks can be assigned as fixed, EDF-sc behaves exactly as partitioned EDF. Heuristics are provided that give EDF-sc the novel ability to stabilize the workload to approach the partitioned case as tasks join and leave the system. 
    more » « less
  2. ; (, Proceedings of the 29th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications)
    The fixed preemption point (FPP) model has been studied as an alternative to fully preemptive and non-preemptive models, as restricting preemptions to specific, predictable locations within a task’s execution can simplify overhead analysis without disallowing preemptions entirely. Prior work has produced response-time analyses for global Earliest Deadline First (G-EDF) scheduling under the FPP model. However, scheduling decisions based solely on task deadlines may be too coarsegrained and may not lead to the lowest response times. In this paper, we propose global FPP EDF-like (G-FPP-EL) scheduling, which assigns a priority point in time for each non-preemptive region of a task. We adapt compliant-vector analysis (CVA) to our model and present general response-time bounds for G-FPPEL schedulers. We then demonstrate that it is possible to design G-FPP-EL schedulers acheiving response-time bounds optimal under CVA and argue that such schedulers should replace global FPP EDF. 
    more » « less
  3. ; (, Proceedings of the 41st IEEE Real-Time Systems Symposium)
    null (Ed.)
    A gap exists between the theory of EDF scheduling on identical multiprocessors with arbitrary processor affinities (APA) and practical EDF scheduling as embodied by the SCHED_DEADLINE (SD) scheduler in Linux. This is because the EDF variant proposed in theory for APA, called Strong APA EDF, introduces affinity-related complexities that are not applicable under global EDF, the original target of SD. SD instead treats affinities as a secondary concern. It is shown herein that this treatment comes at the price of causing SD to be fundamentally broken with regard to soft real-time (SRT)- optimality with APA. This result resolves a longstanding open question regarding this matter. It also suggests that Strong APA EDF, which has been proven to be SRT-optimal, is necessary for practical EDF scheduling with APA. However, non-preemptive sections are typically required in practice, and prior work on Strong APA EDF is limited to fully preemptive systems. In this paper, this prior work is extended for the first time to deal with non-preemptivity, which introduces non-trivial nuances with APA. As a byproduct of considering non-preemptivity, it is shown that the SRT-optimality of EDF in this context carries over to a significantly expanded class of schedulers 
    more » « less
  4. ; ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Mancuso, Renato (Ed.)
    The classic Earliest Deadline First (EDF) algorithm is widely studied and used due to its simplicity and strong theoretical performance, but has not been rigorously analyzed for systems where jobs may execute critical sections protected by shared locks. Analyzing such systems is often challenging due to unpredictable delays caused by contention. In this paper, we propose a straightforward generalization of EDF, called EDF-Block. In this generalization, the critical sections are executed non-preemptively, but scheduling and lock acquisition priorities are based on EDF. We establish lower bounds on the speed augmentation required for any non-clairvoyant scheduler (EDF-Block is an example of non-clairvoyant schedulers) and for EDF-Block, showing that EDF-Block requires at least 4.11× speed augmentation for jobs and 4× for tasks. We then provide an upper bound analysis, demonstrating that EDF-Block requires speedup of at most 6 to schedule all feasible job and task sets. 
    more » « less
  5. ; (, 2018 IEEE Real-Time Systems Symposium (RTSS))
    Modern operating systems allow task migrations to be restricted by specifying per-task processor affinity masks. Such a mask specifies the set of processor cores upon which a task can be scheduled. In this paper, a semi-partitioned scheduler, AM-Red (affinity mask reduction), is presented for scheduling implicit-deadline sporadic tasks with arbitrary affinity masks on an identical multiprocessor. AM-Red is obtained by applying an affinity-mask-reduction method that produces affinities in accordance with those specified, without compromising feasibility, but with only a linear number of migrating tasks. It functions by employing a tunable frame of size |F|. For any choice of |F|, AM-Red is soft-real-time optimal, with tardiness bounded by |F|, but the frequency of task migrations is proportional to |F|. If |F| divides all task periods, then AM-Red is also hard-real-time-optimal (tardiness is zero). AM-Red is the first optimal scheduler proposed for arbitrary affinity masks without future knowledge of all job releases. Experiments are presented that show that AM-Red is implementable with low overhead and yields reasonable tardiness and task-migration frequency. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email