WaP: Computing the Execution Probability of Jobs with Replication in Mixed-Criticality Schedules

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00362206" target="_blank" >RIV/68407700:21230/22:00362206 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/22:00362206

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

WaP: Computing the Execution Probability of Jobs with Replication in Mixed-Criticality Schedules

Popis výsledku v původním jazyce

This extended abstract represents the journal paper published in [13]. In that paper, we study the computation of the execution probability of jobs with uncertain execution times in a static mixed-criticality schedule. In contrast to the majority of research in mixed-criticality systems that work with task models where the jobs are gradually revealed to the scheduler, we assume a time-triggered environment where the offline scheduler generates a static schedule [14], [15], [17]. The execution time of the mixed-criticality jobs is not known in advance and is revealed during the online execution. An online execution policy is designed to handle the prolongations of execution times and escalations of the system mode. The policy may eventually reject some of the low-criticality jobs under some execution scenarios, thus affecting the execution probability of the jobs. This paper deals with the complexity and the method for analysis of the execution probability of mixed-criticality jobs in a static schedule. To overcome the rigidity of static scheduling, we introduce job replication, i.e., scheduling multiple time slots for a single job, as a new mechanism for increasing the execution probability of jobs. We show that the general problem with job replication becomes as hard as the counting variant of 3-SAT problem. To compute the execution probability, we propose an algorithm utilizing the framework of Bayesian networks. The proposed methodology demonstrates an interesting connection between schedules with uncertain execution and probabilistic graphical models.

Název v anglickém jazyce

WaP: Computing the Execution Probability of Jobs with Replication in Mixed-Criticality Schedules

Popis výsledku anglicky

This extended abstract represents the journal paper published in [13]. In that paper, we study the computation of the execution probability of jobs with uncertain execution times in a static mixed-criticality schedule. In contrast to the majority of research in mixed-criticality systems that work with task models where the jobs are gradually revealed to the scheduler, we assume a time-triggered environment where the offline scheduler generates a static schedule [14], [15], [17]. The execution time of the mixed-criticality jobs is not known in advance and is revealed during the online execution. An online execution policy is designed to handle the prolongations of execution times and escalations of the system mode. The policy may eventually reject some of the low-criticality jobs under some execution scenarios, thus affecting the execution probability of the jobs. This paper deals with the complexity and the method for analysis of the execution probability of mixed-criticality jobs in a static schedule. To overcome the rigidity of static scheduling, we introduce job replication, i.e., scheduling multiple time slots for a single job, as a new mechanism for increasing the execution probability of jobs. We show that the general problem with job replication becomes as hard as the counting variant of 3-SAT problem. To compute the execution probability, we propose an algorithm utilizing the framework of Bayesian networks. The proposed methodology demonstrates an interesting connection between schedules with uncertain execution and probabilistic graphical models.

Druh

O - Ostatní výsledky

CEP obor

—

OECD FORD obor

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

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2022

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ů