Report

Probabilistic Results for Mixed Criticality Real-Time Scheduling Bader N. Alahmad Sathish Gopalakrishnan Example Platform Single Processor Preemptive Simpler case: Independent Job Model independent (one-shot) jobs {1 , … , } Job characterized by ∈ ℚ+ ∈ ℚ+ ∈ 1, … , Release Time Absolute Deadline Criticality = 1 , … , , … , ∈ ℚ+ Assumption ? Job Criticality • Codifies (potential) overload conditions • 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 adversarial/worst-case behaviour. 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? – Tardiness ratio: Response Time/Deadline. • What is a policy that minimizes the probability of a deadline miss? Current Investigation Finite Horizon Bandit Process Dynamic Allocation Indexes (DAI) e.g., Gittins Index for multi-armed bandit processes Model as Markov Decision Processes Class of Optimal Stopping Problems Dropping times and time(s) to engage in job execution are random ?