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

Result code in 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>

Alternative codes found

RIV/68407700:21730/22:00362206

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

O - Miscellaneous

CEP classification

—

OECD FORD branch

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

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2022

Confidentiality

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