Implementing Mixed-Criticality Systems Upon a Preemptive Varying-Speed Processor

Abstract

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.

Department(s)

Computer Science

Comments

Creative Commons Attribution 3.0 Germany (CC BY 3.0 DE)

Keywords and Phrases

Mixed Criticalities; Varying-Speed Processor; Preemptive Uniprocessor Scheduling

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2014 Leibniz-Zentrum für Informatik, All rights reserved.

Publication Date

01 Jan 2014

Link to Full Text

Share

 
COinS