Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions
We pose the problem of scheduling Mixed Criticality (MC) job systems when there are only two criticality levels, Lo and Hi -referred to as Dual Criticality job systems- on a single processing platform, when job demands are probabilistic and their distributions are known. The current MC models requir...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
2018-05-01
|
| Series: | Leibniz Transactions on Embedded Systems |
| Subjects: | |
| Online Access: | https://drops.dagstuhl.de/storage/07lites/lites_vol005/lites_vol005_issue001/LITES-v005-i001-a001/LITES-v005-i001-a001.pdf |
| _version_ | 1797208400017227776 |
|---|---|
| author | Alahmad, Bader Naim Gopalakrishnan, Sathish |
| author_facet | Alahmad, Bader Naim Gopalakrishnan, Sathish |
| author_sort | Alahmad, Bader Naim |
| collection | DOAJ |
| description | We pose the problem of scheduling Mixed Criticality (MC) job systems when there are only two criticality levels, Lo and Hi -referred to as Dual Criticality job systems- on a single processing platform, when job demands are probabilistic and their distributions are known. The current MC models require that the scheduling policy allocate as little execution time as possible to Lo-criticality jobs if the scenario of execution is of Hi criticality, and drop Lo-criticality jobs entirely as soon as the execution scenario's criticality level can be inferred and is Hi. The work incurred by "incorrectly" scheduling Lo-criticality jobs in cases of Hi realized scenarios might affect the feasibility of Hi criticality jobs; we quantify this work and call it Work Threatening Feasibility (WTF). Our objective is to construct online scheduling policies that minimize the expected WTF for the given instance, and under which the instance is feasible in a probabilistic sense that is consistent with the traditional deterministic definition of MC feasibility. We develop a probabilistic framework for MC scheduling, where feasibility is defined in terms of (chance) constraints on the probabilities that Lo and Hi jobs meet their deadlines. The probabilities are computed over the set of sample paths, or trajectories, induced by executing the policy, and those paths are dependent upon the set of execution scenarios and the given demand distributions. Our goal is to exploit the information provided by job distributions to compute the minimum expected WTF below which the given instance is not feasible in probability, and to compute a (randomized) "efficiently implementable" scheduling policy that realizes the latter quantity. We model the problem as a Constrained Markov Decision Process (CMDP) over a suitable state space and a finite planning horizon, and show that an optimal (non-stationary) Markov randomized scheduling policy exists. We derive an optimal policy by solving a Linear Program (LP). We also carry out quantitative evaluations on select probabilistic MC instances to demonstrate that our approach potentially outperforms current MC scheduling policies. |
| first_indexed | 2024-04-24T09:38:12Z |
| format | Article |
| id | doaj.art-fa03aae17b36480b831bdaef24f414ba |
| institution | Directory Open Access Journal |
| issn | 2199-2002 |
| language | English |
| last_indexed | 2024-04-24T09:38:12Z |
| publishDate | 2018-05-01 |
| publisher | Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik |
| record_format | Article |
| series | Leibniz Transactions on Embedded Systems |
| spelling | doaj.art-fa03aae17b36480b831bdaef24f414ba2024-04-15T07:53:44ZengSchloss Dagstuhl -- Leibniz-Zentrum fuer InformatikLeibniz Transactions on Embedded Systems2199-20022018-05-015101:101:3010.4230/LITES-v005-i001-a001Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand DistributionsAlahmad, Bader Naim0https://orcid.org/0000-0002-6409-1277Gopalakrishnan, Sathish1The University of British Columbia, 2366 Main Mall, Vancouver, BC, Canada V6T 1Z4The University of British Columbia, 2332 Main Mall, Vancouver, BC, Canada V6T 1Z4We pose the problem of scheduling Mixed Criticality (MC) job systems when there are only two criticality levels, Lo and Hi -referred to as Dual Criticality job systems- on a single processing platform, when job demands are probabilistic and their distributions are known. The current MC models require that the scheduling policy allocate as little execution time as possible to Lo-criticality jobs if the scenario of execution is of Hi criticality, and drop Lo-criticality jobs entirely as soon as the execution scenario's criticality level can be inferred and is Hi. The work incurred by "incorrectly" scheduling Lo-criticality jobs in cases of Hi realized scenarios might affect the feasibility of Hi criticality jobs; we quantify this work and call it Work Threatening Feasibility (WTF). Our objective is to construct online scheduling policies that minimize the expected WTF for the given instance, and under which the instance is feasible in a probabilistic sense that is consistent with the traditional deterministic definition of MC feasibility. We develop a probabilistic framework for MC scheduling, where feasibility is defined in terms of (chance) constraints on the probabilities that Lo and Hi jobs meet their deadlines. The probabilities are computed over the set of sample paths, or trajectories, induced by executing the policy, and those paths are dependent upon the set of execution scenarios and the given demand distributions. Our goal is to exploit the information provided by job distributions to compute the minimum expected WTF below which the given instance is not feasible in probability, and to compute a (randomized) "efficiently implementable" scheduling policy that realizes the latter quantity. We model the problem as a Constrained Markov Decision Process (CMDP) over a suitable state space and a finite planning horizon, and show that an optimal (non-stationary) Markov randomized scheduling policy exists. We derive an optimal policy by solving a Linear Program (LP). We also carry out quantitative evaluations on select probabilistic MC instances to demonstrate that our approach potentially outperforms current MC scheduling policies.https://drops.dagstuhl.de/storage/07lites/lites_vol005/lites_vol005_issue001/LITES-v005-i001-a001/LITES-v005-i001-a001.pdfmixed criticalitiesprobability distributionreal time systemsschedulingchance constrained markov decision processlinear programmingrandomized policy |
| spellingShingle | Alahmad, Bader Naim Gopalakrishnan, Sathish Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions Leibniz Transactions on Embedded Systems mixed criticalities probability distribution real time systems scheduling chance constrained markov decision process linear programming randomized policy |
| title | Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions |
| title_full | Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions |
| title_fullStr | Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions |
| title_full_unstemmed | Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions |
| title_short | Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions |
| title_sort | risk aware scheduling of dual criticality job systems using demand distributions |
| topic | mixed criticalities probability distribution real time systems scheduling chance constrained markov decision process linear programming randomized policy |
| url | https://drops.dagstuhl.de/storage/07lites/lites_vol005/lites_vol005_issue001/LITES-v005-i001-a001/LITES-v005-i001-a001.pdf |
| work_keys_str_mv | AT alahmadbadernaim riskawareschedulingofdualcriticalityjobsystemsusingdemanddistributions AT gopalakrishnansathish riskawareschedulingofdualcriticalityjobsystemsusingdemanddistributions |