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: Reducing Response-Time Bounds via Global Fixed Preemption Point EDF-like Scheduling
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
Award ID(s):
2038855
PAR ID:
10480324
Author(s) / Creator(s):
;
Publisher / Repository:
IEEE Computer Society Press
Date Published:
Journal Name:
Proceedings of the 29th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications
ISBN:
979-8-3503-3786-0
Format(s):
Medium: X
Location:
Niigata, Japan
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Proceedings of the 26th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications)
    null (Ed.)
    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
  2. ; (, 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
  3. ; ; ; ; (, 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
  4. ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Pellizzoni, Rodolfo (Ed.)
    The goal of a real-time locking protocol is to reduce any priority-inversion blocking (pi-blocking) a task may incur while waiting to access a shared resource. For mutual-exclusion sharing on an m-processor platform, the best existing lower bound on per-task pi-blocking under suspension-oblivious analysis is a (trivial) lower bound of (m-1) request lengths under any job-level fixed-priority (JLFP) scheduler. Surprisingly, most asymptotically optimal locking protocols achieve a per-task pi-blocking upper bound of (2m-1) request lengths under JLFP scheduling, even though a range of very different mechanisms are used in these protocols. This paper closes the gap between these existing lower and upper bounds by establishing a lower bound of (2m-2) request lengths under global fixed-priority (G-FP) and global earliest-deadline-first (G-EDF) scheduling. This paper also shows that worst-case per-task pi-blocking can be arbitrarily close to (2m-1) request lengths for locking protocols that satisfy a certain property that is met by most (if not all) existing locking protocols. These results imply that most known asymptotically optimal locking protocols are almost truly optimal (not just asymptotic) under G-FP and G-EDF scheduling. 
    more » « less
  5. ; ; ; ; ; ; (, Leibniz Transactions on Embedded Systems (LITES))
    Brandenburg, Björn B (Ed.)
    Safety-critical embedded systems such as autonomous vehicles typically have only very limited computational capabilities on board that must be carefully managed to provide required enhanced functionalities. As these systems become more complex and inter-connected, some parts may need to be secured to prevent unauthorized access, or isolated to ensure correctness. We propose the multi-phase secure (MPS) task model as a natural extension of the widely used sporadic task model for modeling both the timing and the security (and isolation) requirements for such systems. Under MPS, task phases reflect execution using different security mechanisms which each have associated execution time costs for startup and teardown. We develop corresponding limited-preemption EDF scheduling algorithms and associated pseudo-polynomial schedulability tests for constrained-deadline MPS tasks. In doing so, we provide a correction to a long-standing schedulability condition for EDF under limited-preemption. Evaluation shows that the proposed tests are efficient to compute for bounded utilizations. We empirically demonstrate that the MPS model successfully schedules more task sets compared to non-preemptive approaches. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email