2014/01/01 by Zhishan Guo, Guo, Zhishan, Sanjoy Baruah +1
Computer Science · #Embedded Systems Design Techniques #Mixed criticalities #Petri Nets in System Modeling #Preemptive uniprocessor scheduling #Real-Time Systems Scheduling #Software and its engineering → Real-time schedulability #Varying-speed processor
paper · doi:10.4230/lites-v001-i002-a003
openalex publication_date 2014/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.