Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor
A mixed criticality (MC) workload consists of components of varying degrees of importance (or "criticalities"); the more critical components typically need to have their correctness validated to greater levels of assurance than the less critical ones. The problem of executing such a MC wor...
Main Authors: | , |
---|---|
Format: | Article |
Language: | English |
Published: |
Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
2014-09-01
|
Series: | Leibniz Transactions on Embedded Systems |
Subjects: | |
Online Access: | https://drops.dagstuhl.de/storage/07lites/lites_vol001/lites_vol001_issue002/LITES-v001-i002-a003/LITES-v001-i002-a003.pdf |
_version_ | 1797208392946679808 |
---|---|
author | Guo, Zhishan Baruah, Sanjoy K. |
author_facet | Guo, Zhishan Baruah, Sanjoy K. |
author_sort | Guo, Zhishan |
collection | DOAJ |
description | A mixed criticality (MC) workload consists of components of varying degrees of importance (or "criticalities"); the more critical components typically need to have their correctness validated to greater levels of assurance than the less critical ones. The problem of executing such a MC workload upon a preemptive processor whose effective speed may vary during run-time, in a manner that is not completely known prior to run-time, is considered.Such a processor is modeled as being characterized by several execution speeds: a normal speed and several levels of degraded speed. Under normal circumstances it will execute at or above its normal speed; conditions during run-time may cause it to execute slower. It is desired that all components of the MC workload execute correctly under normal circumstances. If the processor speed degrades, it should nevertheless remain the case that the more critical components execute correctly (although the less critical ones need not do so).In this work, we derive an optimal algorithm for scheduling MC workloads upon such platforms; achieving optimality does not require that the processor be able to monitor its own run-time speed. For the sub-case of the general problem where there are only two criticality levels defined, we additionally provide an implementation that is asymptotically optimal in terms of run-time efficiency. |
first_indexed | 2024-04-24T09:38:05Z |
format | Article |
id | doaj.art-d9f4853f05c34172b1885e3e686da0fe |
institution | Directory Open Access Journal |
issn | 2199-2002 |
language | English |
last_indexed | 2024-04-24T09:38:05Z |
publishDate | 2014-09-01 |
publisher | Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik |
record_format | Article |
series | Leibniz Transactions on Embedded Systems |
spelling | doaj.art-d9f4853f05c34172b1885e3e686da0fe2024-04-15T07:55:32ZengSchloss Dagstuhl -- Leibniz-Zentrum fuer InformatikLeibniz Transactions on Embedded Systems2199-20022014-09-011203:103:1910.4230/LITES-v001-i002-a00310Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed ProcessorGuo, Zhishan0Baruah, Sanjoy K.1University of North Carolina, Chapel Hill, NC, USAUniversity of North Carolina, Chapel Hill, NC, USAA mixed criticality (MC) workload consists of components of varying degrees of importance (or "criticalities"); the more critical components typically need to have their correctness validated to greater levels of assurance than the less critical ones. The problem of executing such a MC workload upon a preemptive processor whose effective speed may vary during run-time, in a manner that is not completely known prior to run-time, is considered.Such a processor is modeled as being characterized by several execution speeds: a normal speed and several levels of degraded speed. Under normal circumstances it will execute at or above its normal speed; conditions during run-time may cause it to execute slower. It is desired that all components of the MC workload execute correctly under normal circumstances. If the processor speed degrades, it should nevertheless remain the case that the more critical components execute correctly (although the less critical ones need not do so).In this work, we derive an optimal algorithm for scheduling MC workloads upon such platforms; achieving optimality does not require that the processor be able to monitor its own run-time speed. For the sub-case of the general problem where there are only two criticality levels defined, we additionally provide an implementation that is asymptotically optimal in terms of run-time efficiency.https://drops.dagstuhl.de/storage/07lites/lites_vol001/lites_vol001_issue002/LITES-v001-i002-a003/LITES-v001-i002-a003.pdfmixed criticalitiesvarying-speed processorpreemptive uniprocessor scheduling |
spellingShingle | Guo, Zhishan Baruah, Sanjoy K. Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor Leibniz Transactions on Embedded Systems mixed criticalities varying-speed processor preemptive uniprocessor scheduling |
title | Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor |
title_full | Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor |
title_fullStr | Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor |
title_full_unstemmed | Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor |
title_short | Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor |
title_sort | implementing mixed criticality systems upon a preemptive varying speed processor |
topic | mixed criticalities varying-speed processor preemptive uniprocessor scheduling |
url | https://drops.dagstuhl.de/storage/07lites/lites_vol001/lites_vol001_issue002/LITES-v001-i002-a003/LITES-v001-i002-a003.pdf |
work_keys_str_mv | AT guozhishan implementingmixedcriticalitysystemsuponapreemptivevaryingspeedprocessor AT baruahsanjoyk implementingmixedcriticalitysystemsuponapreemptivevaryingspeedprocessor |