Efficient Algorithm for Jitter Minimization in Time-Triggered Periodic Mixed-Criticality Message Scheduling Problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00304028" target="_blank" >RIV/68407700:21230/16:00304028 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/16:00304028

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Efficient Algorithm for Jitter Minimization in Time-Triggered Periodic Mixed-Criticality Message Scheduling Problem

Popis výsledku v původním jazyce

The current research in real-time scheduling focuses mostly on the certification of functionalities with respect to safety requirements under conservative assumptions or to achieve efflcient resource utilization but with optimistic assumptions. With growing system complexity, the safety certifi- cation is becoming hard, especially in event-triggered environments. In time-triggered environments, the network nodes are synchronized by clocks and follow a static schedule hence they are easily certifiable. However, the timetriggered paradigm has two disadvantages. The first one is its general non- exibility (e.g. message retransmission, effi- cient resource usage) and the second one is the need for an efflcient scheduling algorithm producing the schedule. In this paper, we propose a solution to both of these issues. To address the first disadvantage, we propose a method for non-preemptive message retransmission in time-triggered environments while preserving the efflcient use of resources. Based on the message criticality we allow a certain number of retransmissions. The observed prolongation of the processing time of a highly critical message is compensated by skipping transmission of less critical messages. Static schedules then contain all alternatives caused by the retransmissions that can occur during a run time execution. Schedules conform with certification requirements imposed on the highly critical messages while preserving the efflcient use of resources. To address the second disadvantage, we propose a novel heuristic scheduling algorithm with an unscheduling step for solving large instances of periodic message scheduling problem. The message periodicity is assumed to be a power of two and the objective is to minimize the maximal jitter. The efflciency of the approach is demonstrated on problem instances with up to 2000 messages.

Název v anglickém jazyce

Efficient Algorithm for Jitter Minimization in Time-Triggered Periodic Mixed-Criticality Message Scheduling Problem

Popis výsledku anglicky

The current research in real-time scheduling focuses mostly on the certification of functionalities with respect to safety requirements under conservative assumptions or to achieve efflcient resource utilization but with optimistic assumptions. With growing system complexity, the safety certifi- cation is becoming hard, especially in event-triggered environments. In time-triggered environments, the network nodes are synchronized by clocks and follow a static schedule hence they are easily certifiable. However, the timetriggered paradigm has two disadvantages. The first one is its general non- exibility (e.g. message retransmission, effi- cient resource usage) and the second one is the need for an efflcient scheduling algorithm producing the schedule. In this paper, we propose a solution to both of these issues. To address the first disadvantage, we propose a method for non-preemptive message retransmission in time-triggered environments while preserving the efflcient use of resources. Based on the message criticality we allow a certain number of retransmissions. The observed prolongation of the processing time of a highly critical message is compensated by skipping transmission of less critical messages. Static schedules then contain all alternatives caused by the retransmissions that can occur during a run time execution. Schedules conform with certification requirements imposed on the highly critical messages while preserving the efflcient use of resources. To address the second disadvantage, we propose a novel heuristic scheduling algorithm with an unscheduling step for solving large instances of periodic message scheduling problem. The message periodicity is assumed to be a power of two and the objective is to minimize the maximal jitter. The efflciency of the approach is demonstrated on problem instances with up to 2000 messages.

Druh

D - Stať ve sborníku

CEP obor

BB - Aplikovaná statistika, operační výzkum

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2016

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 statě ve sborníku

ACM International Conference Proceeding Series

ISBN

978-1-4503-4787-7

ISSN

—

e-ISSN

—

Počet stran výsledku

9

Strana od-do

23-31

Název nakladatele

ACM

Místo vydání

New York

Místo konání akce

Brest

Datum konání akce

19. 10. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000391255400003