### A Look into Stochastic Scheduling of Mixed Criticality Real

```Probabilistic Results for Mixed
Criticality Real-Time Scheduling
Sathish Gopalakrishnan
Example
Platform
Single Processor
Preemptive
Simpler case: Independent Job Model
independent (one-shot) jobs {1 , … ,  }
Job  characterized by
∈ ℚ+
∈ ℚ+
∈ 1, … ,
 Release Time
 Criticality
=  1 , … ,   , … ,
∈ ℚ+  Assumption ?
Job Criticality
• In overload, jobs with higher criticality have
infinite marginal utility of execution over
lower criticality ones
Execution behaviours
MC-Schedulability/Scheduling
MC-Schedulability
MC-Scheduling
Need to find a scheduling policy…
Approach: Worst Case Reservation (WCR)
Scheduling
Performance Metric? How to quantify
the quality of the solution ?
Resource Augmentation  Processor speed
up factor
1
Processor is
a unit
capacity bin
WCR
Optimal (Oracle)
• If system criticality level
= 1: all criticality 1 jobs
execute and are
allowed to fully utilize
the processor
• If system criticality level
= 2: all criticality 2 jobs
execute and are
allowed to fully utilize
the processor
WCR
• If system criticality level
= 1: all criticality 1 jobs
execute and are
allowed to fully utilize
the processor
• If system criticality level
= 2: all jobs execute and
are allowed to fully
utilize the processor
WCR-Schedulability
If an instance is WCR-schedulable on a processor  it
is MC-schedulable on the same processor
Conversely, if an instance with  criticality levels is MCschedulable on a given processor  it is WCRschedulable on a processor that is  times as fast, and
this factor is tight.
Own Criticality Based Priority (OCBP)
Construct fixed priority table offline.
At each scheduling decision point, dispatch
the job with the highest priority.
Priorities assigned using Audsley’s/Lawler’s
method.
OCBP – Speed up factor
The root of the equation   = 1 +
−1
= (/ ln ) 
improvement of (ln ) asymptotically over WCR
For dual-criticality systems:  = 2   ∈ LO, HI
2 =
5+1
2
=  The Golden ration
Deterministic results are based on
Probabilistic execution times to guide
execution time allocation
Mutually independent
Open Questions
• What is a policy that minimizes expected lateness?
– Based on expected criticality level.
– Lateness: Response Time – Deadline.
• What is a policy that minimizes tardiness/lateness ratio?