Survey on Periodic Scheduling for Time-Triggered Hard Real-Time Systems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21730%2F21%3A00344047" target="_blank" >RIV/68407700:21730/21:00344047 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1145/3431232" target="_blank" >https://doi.org/10.1145/3431232</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3431232" target="_blank" >10.1145/3431232</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Survey on Periodic Scheduling for Time-Triggered Hard Real-Time Systems

Popis výsledku v původním jazyce

This survey covers the basic principles and related works addressing the time-triggered scheduling of periodic tasks with deadlines. The wide range of applications and the increasing complexity of modern real-time systems result in the continually growing interest in this topic. However, the articles in this field appear without systematic notation. To address it, we extend the three-field Graham notation to cover periodic scheduling. Moreover, we formally define three example periodic scheduling problems (PSPs) and provide straightforward implementations of these examples in the Satisfiability Modulo Theories formalism with source codes. Then, we present a summary of the complexity results containing existing polynomially solvable PSPs. We also provide an overview of simple state-of-the-art methods and tricks to solve the PSPs efficiently in terms of time. Next, we survey the existing works on PSP according to the resource environment: scheduling on a single resource, on parallel identical resources, and on dedicated resources. In the survey, we indicate which works propose solution methods for more general PSPs that can be used to solve less general ones. Finally, we present related problems that are not periodic by nature to provide an inspiration for a possible solution for the PSP.

Název v anglickém jazyce

Survey on Periodic Scheduling for Time-Triggered Hard Real-Time Systems

Popis výsledku anglicky

This survey covers the basic principles and related works addressing the time-triggered scheduling of periodic tasks with deadlines. The wide range of applications and the increasing complexity of modern real-time systems result in the continually growing interest in this topic. However, the articles in this field appear without systematic notation. To address it, we extend the three-field Graham notation to cover periodic scheduling. Moreover, we formally define three example periodic scheduling problems (PSPs) and provide straightforward implementations of these examples in the Satisfiability Modulo Theories formalism with source codes. Then, we present a summary of the complexity results containing existing polynomially solvable PSPs. We also provide an overview of simple state-of-the-art methods and tricks to solve the PSPs efficiently in terms of time. Next, we survey the existing works on PSP according to the resource environment: scheduling on a single resource, on parallel identical resources, and on dedicated resources. In the survey, we indicate which works propose solution methods for more general PSPs that can be used to solve less general ones. Finally, we present related problems that are not periodic by nature to provide an inspiration for a possible solution for the PSP.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF15_003%2F0000466" target="_blank" >EF15_003/0000466: Umělá inteligence a uvažování</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ACM Computing Surveys

ISSN

0360-0300

e-ISSN

1557-7341

Svazek periodika

54

Číslo periodika v rámci svazku

March

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

32

Strana od-do

—

Kód UT WoS článku

000644443200023

EID výsledku v databázi Scopus

2-s2.0-85105377610