26 Search Results for "Brandenburg, Björn B."

Volume

LIPIcs, Volume 196

33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)

ECRTS 2021, July 5-9, 2021, Virtual Conference

Editors: Björn B. Brandenburg

Document
DOI: 10.4230/LIPIcs.ECRTS.2024.2
SlackCheck: A Linux Kernel Module to Verify Temporal Properties of a Task Schedule

Authors: Michele Castrovilli and Enrico Bini

Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)

Abstract
The Linux Kernel offers several scheduling classes. From SCHED_DEADLINE down to SCHED_FIFO, SCHED_RR and SCHED_OTHER, the scheduling classes can provide different responsiveness to very diverse user workloads. Still, Linux does not offer any mechanism to take some action upon the violation of temporal constraints at runtime. The lack of such a feature is also due to the difficulty of extending the established notion of deadline to workloads which are not releasing periodic/sporadic jobs. Exploiting the notion of supply functions for any resource schedule, we implemented SlackCheck, a kernel module which is capable to verify at runtime if a given task is assigned a desired amount of resource or not. SlackCheck adds a constant-time check at every scheduling decision and leverages the recent availability of a Runtime Verification engine in the kernel.
Cite as

Michele Castrovilli and Enrico Bini. SlackCheck: A Linux Kernel Module to Verify Temporal Properties of a Task Schedule. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 2:1-2:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{castrovilli_et_al:LIPIcs.ECRTS.2024.2,
  author =	{Castrovilli, Michele and Bini, Enrico},
  title =	{{SlackCheck: A Linux Kernel Module to Verify Temporal Properties of a Task Schedule}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{2:1--2:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-324-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{298},
  editor =	{Pellizzoni, Rodolfo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.2},
  URN =		{urn:nbn:de:0030-drops-203054},
  doi =		{10.4230/LIPIcs.ECRTS.2024.2},
  annote =	{Keywords: Linux scheduler, Runtime verification, bounded-delay resource partition, supply function, service curve, real-time calculus, network calculus}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2024.3
Reachability-Based Response-Time Analysis of Preemptive Tasks Under Global Scheduling

Authors: Pourya Gohari, Jeroen Voeten, and Mitra Nasri

Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)

Abstract
Global scheduling reduces the average response times as it can use the available computing cores more efficiently for scheduling ready tasks. However, this flexibility poses challenges in accurately quantifying interference scenarios, often resulting in either conservative response-time analyses or scalability issues. In this paper, we present a new response-time analysis for preemptive periodic tasks (or job sets) subject to release jitter under global job-level fixed-priority (JLFP) scheduling. Our analysis relies on the notion of schedule-abstraction graph (SAG), a reachability-based response-time analysis known for its potential accuracy and efficiency. Up to this point, SAG was limited to non-preemptive tasks due to the complexity of handling preemption when the number of preemptions and the moments they occur are not known beforehand. In this paper, we introduce the concept of time partitions and demonstrate how it facilitates the extension of SAG for preemptive tasks. Moreover, our paper provides the first response-time analysis for the global EDF(k) policy - a JLFP scheduling policy introduced in 2003 to address the Dhall’s effect. Our experiments show that our analysis is significantly more accurate compared to the state-of-the-art analyses. For example, we identify 12 times more schedulable task sets than existing tests for the global EDF policy (e.g., for systems with 6 to 16 tasks, 70% utilization, and 4 cores) with an average runtime of 30 minutes. We show that EDF(k) outperforms global RM and EDF by scheduling on average 24.9% more task sets (e.g., for systems with 2 to 10 cores and 70% utilization). Moreover, for the first time, we show that global JLFP scheduling policies (particularly, global EDF(k)) are able to schedule task sets that are not schedulable using well-known partitioning heuristics.
Cite as

Pourya Gohari, Jeroen Voeten, and Mitra Nasri. Reachability-Based Response-Time Analysis of Preemptive Tasks Under Global Scheduling. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gohari_et_al:LIPIcs.ECRTS.2024.3,
  author =	{Gohari, Pourya and Voeten, Jeroen and Nasri, Mitra},
  title =	{{Reachability-Based Response-Time Analysis of Preemptive Tasks Under Global Scheduling}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{3:1--3:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-324-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{298},
  editor =	{Pellizzoni, Rodolfo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.3},
  URN =		{urn:nbn:de:0030-drops-203064},
  doi =		{10.4230/LIPIcs.ECRTS.2024.3},
  annote =	{Keywords: Response-time analysis, global scheduling, preemptive, job-level fixed-priority scheduling policy, multicore, schedule-abstraction graph}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2024.4
Tighter Worst-Case Response Time Bounds for Jitter-Based Self-Suspension Analysis

Authors: Mario Günzel, Georg von der Brüggen, and Jian-Jia Chen

Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)

Abstract
Tasks are called self-suspending if they can yield their ready state (specifically, releasing the processor while having highest priority) despite being incomplete, for instance, to offload computation to an external device or when waiting on access rights for shared resources or data. This self-suspending behavior requires special treatment when applying analytical results to compute worst-case response time bounds. One typical treatment is modeling self-suspension as release jitter in a so-called jitter-based analysis. The state of the art, when considering task-level fixed-priority scheduling, individually quantifies the jitter term of each higher-priority task by its worst-case response time minus its worst-case execution time. This work tightens the jitter term by taking the execution behavior of the other higher-priority tasks into account. Our improved jitter-based analysis analytically dominates the previous jitter-based analysis. Moreover, an evaluation for synthetically generated sporadic tasks demonstrates that this jitter term results in tighter worst-case response time bounds for self-suspending tasks. We observe an improvement for up to 55.89 % of the tasksets compared to the previous jitter-based analysis.
Cite as

Mario Günzel, Georg von der Brüggen, and Jian-Jia Chen. Tighter Worst-Case Response Time Bounds for Jitter-Based Self-Suspension Analysis. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 4:1-4:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gunzel_et_al:LIPIcs.ECRTS.2024.4,
  author =	{G\"{u}nzel, Mario and von der Br\"{u}ggen, Georg and Chen, Jian-Jia},
  title =	{{Tighter Worst-Case Response Time Bounds for Jitter-Based Self-Suspension Analysis}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{4:1--4:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-324-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{298},
  editor =	{Pellizzoni, Rodolfo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.4},
  URN =		{urn:nbn:de:0030-drops-203074},
  doi =		{10.4230/LIPIcs.ECRTS.2024.4},
  annote =	{Keywords: Worst-Case Response Time, WCRT, Jitter, Self-Suspension, Analysis}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2024.8
Deadline Miss Early Detection Method for DAG Tasks Considering Variable Execution Time

Authors: Hayate Toba and Takuya Azumi

Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)

Abstract
Autonomous driving systems must guarantee safety, which requires strict real-time performance. A series of processes, from sensor data input to vehicle control command output, must be completed by the end-to-end deadline. If a deadline miss occurs, the system must quickly transition to a safe state. To improve safety, an early detection method for deadline misses was proposed. The proposed method represents the autonomous driving system as a directed acyclic graph (DAG) with a mixture of timer-driven and event-driven nodes. It assigns appropriate time constraints for each node based on the end-to-end deadline. However, the existing methods assume the worst-case execution time (WCET) for calculating the time constraints of each node and do not consider the execution time variation of nodes, making the detection of deadline misses pessimistic. This paper proposes a deadline miss early detection method to determine the possibility of deadline misses quantitatively at the beginning of each node execution in a DAG task. It calculates the time constraints of each node using probabilistic execution time, which treats execution time as a random variable. Experimental evaluation shows that the proposed method reduces pessimism, which is a problem of conventional methods using WCET, and then achieves more accurate early detection of deadline misses. The evaluation also indicates that the execution time of static analysis required for deadline miss early detection is within a practical level.
Cite as

Hayate Toba and Takuya Azumi. Deadline Miss Early Detection Method for DAG Tasks Considering Variable Execution Time. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{toba_et_al:LIPIcs.ECRTS.2024.8,
  author =	{Toba, Hayate and Azumi, Takuya},
  title =	{{Deadline Miss Early Detection Method for DAG Tasks Considering Variable Execution Time}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{8:1--8:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-324-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{298},
  editor =	{Pellizzoni, Rodolfo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.8},
  URN =		{urn:nbn:de:0030-drops-203116},
  doi =		{10.4230/LIPIcs.ECRTS.2024.8},
  annote =	{Keywords: Autonomous driving system, deadline miss early detection, DAG, event-driven task, timer-driven task, probabilistic execution time}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2024.10
Crêpe: Clock-Reconfiguration-Aware Preemption Control in Real-Time Systems with Devices

Authors: Eva Dengler and Peter Wägemann

Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)

Abstract
The domain of energy-constrained real-time systems that are operated on modern embedded system-on-chip (SoC) platforms brings numerous novel challenges for optimal resource minimization. These modern hardware platforms offer a heterogeneous variety of features to configure the tradeoff between temporal performance and energy efficiency, which goes beyond the state-of-the-art of existing dynamic-voltage-frequency-scaling (DVFS) scheduling schemes. The control center for configuring this tradeoff on platforms are complex clock subsystems that are intertwined with requirements of the SoC’s components (e.g., transceiver/memory/sensor devices). That is, several devices have precedence constraints with respect to specific clock sources and their settings. The challenge of dynamically adapting the various clock sources to select resource-optimal configurations becomes especially challenging in the presence of asynchronous preemptions, which are inherent to systems that use devices. In this paper, we present Crêpe, an approach to clock-reconfiguration-aware preemption control: Crêpe has an understanding of the target platform’s clock subsystem, its sleep states, and penalties to reconfigure clock sources for adapting clock frequencies. Crêpe’s hardware model is combined with an awareness of the application’s device requirements for each executed task, as well as possible interrupts that cause preemptions during runtime. Using these software/hardware constraints, Crêpe employs, in its offline phase, a mathematical formalization in order to select energy-minimal configurations while meeting given deadlines. This optimizing formalization, processed by standard mathematical solver tools, accounts for potentially occurring interrupts and the respective clock reconfigurations, which are then forwarded as alternative schedules to Crêpe’s runtime system. During runtime, the dispatcher assesses these offline-determined alternative schedules and reconfigures the clock sources for energy minimization. We developed an implementation based on a widely-used SoC platform (i.e., ESP32-C3) and an automated testbed for comprehensive energy-consumption evaluations to validate Crêpe’s claim of selecting resource-optimal settings under worst-case considerations.
Cite as

Eva Dengler and Peter Wägemann. Crêpe: Clock-Reconfiguration-Aware Preemption Control in Real-Time Systems with Devices. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 10:1-10:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dengler_et_al:LIPIcs.ECRTS.2024.10,
  author =	{Dengler, Eva and W\"{a}gemann, Peter},
  title =	{{Cr\^{e}pe: Clock-Reconfiguration-Aware Preemption Control in Real-Time Systems with Devices}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{10:1--10:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-324-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{298},
  editor =	{Pellizzoni, Rodolfo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.10},
  URN =		{urn:nbn:de:0030-drops-203135},
  doi =		{10.4230/LIPIcs.ECRTS.2024.10},
  annote =	{Keywords: energy-constrained real-time systems, time/energy tradeoff, system-on-chip, energy-aware real-time scheduling, resource minimization, preemption control, worst-case energy consumption (WCEC), worst-case execution time (WCET), static whole-system analysis}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2024.14
GCAPS: GPU Context-Aware Preemptive Priority-Based Scheduling for Real-Time Tasks

Authors: Yidi Wang, Cong Liu, Daniel Wong, and Hyoseung Kim

Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)

Abstract
Scheduling real-time tasks that utilize GPUs with analyzable guarantees poses a significant challenge due to the intricate interaction between CPU and GPU resources, as well as the complex GPU hardware and software stack. While much research has been conducted in the real-time research community, several limitations persist, including the absence or limited availability of GPU-level preemption, extended blocking times, and/or the need for extensive modifications to program code. In this paper, we propose GCAPS, a GPU Context-Aware Preemptive Scheduling approach for real-time GPU tasks. Our approach exerts control over GPU context scheduling at the device driver level and enables preemption of GPU execution based on task priorities by simply adding one-line macros to GPU segment boundaries. In addition, we provide a comprehensive response time analysis of GPU-using tasks for both our proposed approach as well as the default Nvidia GPU driver scheduling that follows a work-conserving round-robin policy. Through empirical evaluations and case studies, we demonstrate the effectiveness of the proposed approaches in improving taskset schedulability and response time. The results highlight significant improvements over prior work as well as the default scheduling approach, with up to 40% higher schedulability, while also achieving predictable worst-case behavior on Nvidia Jetson embedded platforms.
Cite as

Yidi Wang, Cong Liu, Daniel Wong, and Hyoseung Kim. GCAPS: GPU Context-Aware Preemptive Priority-Based Scheduling for Real-Time Tasks. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ECRTS.2024.14,
  author =	{Wang, Yidi and Liu, Cong and Wong, Daniel and Kim, Hyoseung},
  title =	{{GCAPS: GPU Context-Aware Preemptive Priority-Based Scheduling for Real-Time Tasks}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{14:1--14:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-324-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{298},
  editor =	{Pellizzoni, Rodolfo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.14},
  URN =		{urn:nbn:de:0030-drops-203170},
  doi =		{10.4230/LIPIcs.ECRTS.2024.14},
  annote =	{Keywords: Real-time systems, GPU scheduling}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2024.15
Predictable GPU Sharing in Component-Based Real-Time Systems

Authors: Syed W. Ali, Zelin Tong, Joseph Goh, and James H. Anderson

Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)

Abstract
This paper presents a real-time locking protocol whose design was motivated by the goal of enabling safe GPU sharing in time-sliced component-based systems. This locking protocol enables a GPU to be shared concurrently across, and utilized within, isolated components with predictable execution times. It relies on a novel resizing technique where GPU work is dimensioned on-the-fly to run on partitions of an NVIDIA GPU. This technique can be applied to any component that internally utilizes global CPU scheduling. The proposed locking protocol enables increased GPU parallelism and reduces GPU capacity loss with analytically provable benefits.
Cite as

Syed W. Ali, Zelin Tong, Joseph Goh, and James H. Anderson. Predictable GPU Sharing in Component-Based Real-Time Systems. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ali_et_al:LIPIcs.ECRTS.2024.15,
  author =	{Ali, Syed W. and Tong, Zelin and Goh, Joseph and Anderson, James H.},
  title =	{{Predictable GPU Sharing in Component-Based Real-Time Systems}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{15:1--15:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-324-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{298},
  editor =	{Pellizzoni, Rodolfo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.15},
  URN =		{urn:nbn:de:0030-drops-203183},
  doi =		{10.4230/LIPIcs.ECRTS.2024.15},
  annote =	{Keywords: GPU locking protocols, real-time locking protocols, priority-inversion blocking, component-based systems}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2024.16
Analysis of TSN Time-Aware Shapers Using Schedule Abstraction Graphs

Authors: Srinidhi Srinivasan, Geoffrey Nelissen, Reinder J. Bril, and Nirvana Meratnia

Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)

Abstract
IEEE Time-Sensitive Networking (TSN) is one of the main solutions considered by the industry to support time-sensitive communication in data-intensive safety-critical and mission-critical applications such as autonomous driving and smart manufacturing. IEEE TSN standardizes several mechanisms to support real-time traffic on Ethernet networks. Time-Aware Shapers (TAS) (IEEE 802.1Qbv) is the standardized mechanisms of TSN that is usually considered to provide the most deterministic behavior for packet forwarding. TAS regulates when traffic classes may forward incoming packets to the egress of a TSN switch using gates that are opened and closed according to a time-triggered schedule. State-of-the-art solutions to configure or analyze TAS do not allow for multiple traffic classes to have their TAS gates opened at the same time according to any arbitrary schedule. In this paper, we present the first response-time analysis for traffic shaped with TAS where no restriction is enforced on the gate schedule. The proposed analysis is exact. It is a non-trivial variant of the schedule abstraction graph analysis framework [Nasri and Brandenburg, 2017]. Experiments confirm the usefulness of the proposed analysis and show that it is promising for doing design-space exploration where non-conventional TAS gates configurations are investigated to, for instance, improve average-case performance without degrading the worst-case.
Cite as

Srinidhi Srinivasan, Geoffrey Nelissen, Reinder J. Bril, and Nirvana Meratnia. Analysis of TSN Time-Aware Shapers Using Schedule Abstraction Graphs. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 16:1-16:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{srinivasan_et_al:LIPIcs.ECRTS.2024.16,
  author =	{Srinivasan, Srinidhi and Nelissen, Geoffrey and Bril, Reinder J. and Meratnia, Nirvana},
  title =	{{Analysis of TSN Time-Aware Shapers Using Schedule Abstraction Graphs}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{16:1--16:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-324-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{298},
  editor =	{Pellizzoni, Rodolfo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.16},
  URN =		{urn:nbn:de:0030-drops-203198},
  doi =		{10.4230/LIPIcs.ECRTS.2024.16},
  annote =	{Keywords: TSN, Time-Aware Shapers, TAS, SAG, Schedule Abstraction, latency}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2024.17
Response Time Analysis for Fixed-Priority Preemptive Uniform Multiprocessor Systems

Authors: Binqi Sun, Tomasz Kloda, and Marco Caccamo

Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)

Abstract
We present a response time analysis for global fixed-priority preemptive scheduling of constrained-deadline tasks upon a uniform multiprocessor where each processor can be characterized by a different speed. A fixed-priority scheduler assigns the jobs with the highest priorities to the fastest processors. Since determining whether all tasks can meet their deadlines is generally intractable even with identical processors, we propose two sufficient schedulability tests that calculate upper bounds on the task’s worst-case response time within polynomial and pseudo-polynomial time. The proposed tests leverage the linear programming model to upper bound the interference of the higher-priority tasks. Furthermore, we identify specific conditions and platforms upon which the problem can be solved more efficiently within linear time. These formulations are used to iteratively evaluate and refine possible solutions until a safe upper bound on the task’s worst-case response time is found. Additionally, we demonstrate that, with specific minor modifications, the proposed tests are compatible with Audsley’s optimal priority assignment. Experimental evaluations performed on synthetic task sets show that the proposed approach outperforms the state-of-the-art methods.
Cite as

Binqi Sun, Tomasz Kloda, and Marco Caccamo. Response Time Analysis for Fixed-Priority Preemptive Uniform Multiprocessor Systems. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 17:1-17:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sun_et_al:LIPIcs.ECRTS.2024.17,
  author =	{Sun, Binqi and Kloda, Tomasz and Caccamo, Marco},
  title =	{{Response Time Analysis for Fixed-Priority Preemptive Uniform Multiprocessor Systems}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{17:1--17:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-324-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{298},
  editor =	{Pellizzoni, Rodolfo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.17},
  URN =		{urn:nbn:de:0030-drops-203201},
  doi =		{10.4230/LIPIcs.ECRTS.2024.17},
  annote =	{Keywords: Real-time scheduling, Uniform multiprocessor, Response time analysis}
}
Document
Artifact
DOI: 10.4230/DARTS.10.1.1
Predictable GPU Sharing in Component-Based Real-Time Systems (Artifact)

Authors: Syed W. Ali, Zelin Tong, Joseph Goh, and James H. Anderson

Published in: DARTS, Volume 10, Issue 1, Special Issue of the 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)

Abstract
This paper presents a real-time locking protocol whose design was motivated by the goal of enabling safe GPU sharing in time-sliced component-based systems. This locking protocol enables a GPU to be shared concurrently across, and utilized within, isolated components with predictable execution times. It relies on a novel resizing technique where GPU work is dimensioned on-the-fly to run on partitions of an NVIDIA GPU. This technique can be applied to any component that internally utilizes global CPU scheduling. The proposed locking protocol enables increased GPU parallelism and reduces GPU capacity loss with analytically provable benefits.
Cite as

Syed W. Ali, Zelin Tong, Joseph Goh, and James H. Anderson. Predictable GPU Sharing in Component-Based Real-Time Systems (Artifact). In Special Issue of the 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Dagstuhl Artifacts Series (DARTS), Volume 10, Issue 1, pp. 1:1-1:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{ali_et_al:DARTS.10.1.1,
  author =	{Ali, Syed W. and Tong, Zelin and Goh, Joseph and Anderson, James H.},
  title =	{{Predictable GPU Sharing in Component-Based Real-Time Systems (Artifact)}},
  pages =	{1:1--1:5},
  journal =	{Dagstuhl Artifacts Series},
  ISBN =	{978-3-95977-327-0},
  ISSN =	{2509-8195},
  year =	{2024},
  volume =	{10},
  number =	{1},
  editor =	{Ali, Syed W. and Tong, Zelin and Goh, Joseph and Anderson, James H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.10.1.1},
  URN =		{urn:nbn:de:0030-drops-203236},
  doi =		{10.4230/DARTS.10.1.1},
  annote =	{Keywords: GPU locking protocols, real-time locking protocols, priority-inversion blocking, component-based systems}
}
Document
Artifact
DOI: 10.4230/DARTS.8.1.7
Foundational Response-Time Analysis as Explainable Evidence of Timeliness (Artifact)

Authors: Marco Maida, Sergey Bozhko, and Björn B. Brandenburg

Published in: DARTS, Volume 8, Issue 1, Special Issue of the 34th Euromicro Conference on Real-Time Systems (ECRTS 2022)

Abstract
This artifact provides the means to validate and reproduce the results of the associated paper “Foundational Response-Time Analysis as Explainable Evidence of Timeliness”. The artifact demonstrates how to (i) generate task sets needed to run the experiments, (ii) prepare and run POET on the generated input, (iii) plot the figures presented in the paper, and (iv) visually inspect the generated certificates.
Cite as

Marco Maida, Sergey Bozhko, and Björn B. Brandenburg. Foundational Response-Time Analysis as Explainable Evidence of Timeliness (Artifact). In Special Issue of the 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Dagstuhl Artifacts Series (DARTS), Volume 8, Issue 1, pp. 7:1-7:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{maida_et_al:DARTS.8.1.7,
  author =	{Maida, Marco and Bozhko, Sergey and Brandenburg, Bj\"{o}rn B.},
  title =	{{Foundational Response-Time Analysis as Explainable Evidence of Timeliness (Artifact)}},
  pages =	{7:1--7:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2022},
  volume =	{8},
  number =	{1},
  editor =	{Maida, Marco and Bozhko, Sergey and Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.8.1.7},
  URN =		{urn:nbn:de:0030-drops-165038},
  doi =		{10.4230/DARTS.8.1.7},
  annote =	{Keywords: hard real-time systems, response-time analysis, uniprocessor, Coq, Prosa, fixed priority, EDF, preemptive, non-preemptive, verification}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2022.19
Foundational Response-Time Analysis as Explainable Evidence of Timeliness

Authors: Marco Maida, Sergey Bozhko, and Björn B. Brandenburg

Published in: LIPIcs, Volume 231, 34th Euromicro Conference on Real-Time Systems (ECRTS 2022)

Abstract
The paper introduces foundational response-time analysis (RTA) as a means to produce strong and independently checkable evidence of temporal correctness. In a foundational RTA, each response-time bound calculated comes with an auto-generated certificate of correctness - a short and human-inspectable sequence of machine-checked proofs that formally show the claimed bound to hold. In other words, a foundational RTA yields explainable results that can be independently verified (e.g., by a certification authority) in a rigorous manner (with an automated proof checker). Consequently, the analysis tool itself does not need to be verified nor trusted. As a proof of concept, the paper presents POET, the first foundational RTA tool. POET generates certificates based on Prosa, the to-date largest verified framework for schedulability analysis, which is based on Coq. The trusted computing base is hence reduced to the Coq proof checker and its dependencies. POET currently supports two scheduling policies (earliest-deadline-first, fixed-priority), two preemption models (fully preemptive, fully non-preemptive), arbitrary deadlines, periodic and sporadic tasks, and tasks characterized by arbitrary arrival curves. The paper describes the challenges inherent in the development of a foundational RTA tool, discusses key design choices, and reports on its scalability.
Cite as

Marco Maida, Sergey Bozhko, and Björn B. Brandenburg. Foundational Response-Time Analysis as Explainable Evidence of Timeliness. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 19:1-19:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{maida_et_al:LIPIcs.ECRTS.2022.19,
  author =	{Maida, Marco and Bozhko, Sergey and Brandenburg, Bj\"{o}rn B.},
  title =	{{Foundational Response-Time Analysis as Explainable Evidence of Timeliness}},
  booktitle =	{34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
  pages =	{19:1--19:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-239-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{231},
  editor =	{Maggio, Martina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.19},
  URN =		{urn:nbn:de:0030-drops-163363},
  doi =		{10.4230/LIPIcs.ECRTS.2022.19},
  annote =	{Keywords: hard real-time systems, response-time analysis, uniprocessor, Coq, Prosa, fixed priority, EDF, preemptive, non-preemptive, verification}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ECRTS.2021
LIPIcs, Volume 196, ECRTS 2021, Complete Volume

Authors: Björn B. Brandenburg

Published in: LIPIcs, Volume 196, 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)

Abstract
LIPIcs, Volume 196, ECRTS 2021, Complete Volume
Cite as

33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 1-370, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Proceedings{brandenburg:LIPIcs.ECRTS.2021,
  title =	{{LIPIcs, Volume 196, ECRTS 2021, Complete Volume}},
  booktitle =	{33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)},
  pages =	{1--370},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-192-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{196},
  editor =	{Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2021},
  URN =		{urn:nbn:de:0030-drops-139309},
  doi =		{10.4230/LIPIcs.ECRTS.2021},
  annote =	{Keywords: LIPIcs, Volume 196, ECRTS 2021, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ECRTS.2021.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Björn B. Brandenburg

Published in: LIPIcs, Volume 196, 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{brandenburg:LIPIcs.ECRTS.2021.0,
  author =	{Brandenburg, Bj\"{o}rn B.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)},
  pages =	{0:i--0:xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-192-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{196},
  editor =	{Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2021.0},
  URN =		{urn:nbn:de:0030-drops-139317},
  doi =		{10.4230/LIPIcs.ECRTS.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
  • Refine by Author
  • 15 Brandenburg, Björn B.
  • 5 Nasri, Mitra
  • 4 Bozhko, Sergey
  • 4 Nelissen, Geoffrey
  • 2 Ali, Syed W.
  • Show More...

  • Refine by Classification
  • 20 Computer systems organization → Real-time systems
  • 7 Software and its engineering → Real-time schedulability
  • 5 Computer systems organization → Embedded and cyber-physical systems
  • 4 Software and its engineering → Scheduling
  • 2 Computer systems organization → Embedded systems
  • Show More...

  • Refine by Keyword
  • 6 response-time analysis
  • 5 preemptive
  • 4 Coq
  • 4 EDF
  • 4 Prosa
  • Show More...

  • Refine by Type
  • 25 document
  • 1 volume

  • Refine by Publication Year
  • 10 2024
  • 4 2019
  • 3 2018
  • 3 2020
  • 3 2021
  • Show More...

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact