Compositional Real-Time Scheduling FrameworkOutlineTraditional Scheduling FrameworkHierarchical Scheduling Framework (HFS)Compositional Scheduling FrameworkVM Scheduler’s ViewpointProblems & Approach IOS Scheduler’s ViewpointProblems & Approach IICompositional Real-time Scheduling FrameworkScheduling Component ModelingResource ModelingResource ModelingSchedulability AnalysisResource Demand BoundDemand Bound Function - EDFResource Supply BoundResource Supply BoundResource Supply BoundSupply Bound FunctionSchedulability Conditions (EDF)Schedulability Condition - EDFSchedulability Condition - RMUtilization BoundsUtilization BoundsUtilization Bound - EDFEDF Utilization Bound - IntuitionEDF Utilization Bound - IntuitionEDF Utilization Bound - IntuitionEDF Utilization Bound - IntuitionEDF Utilization Bound - IntuitionUtilization Bound - RMComponent AbstractionComponent AbstractionComponent Abstraction (Example)Component Abstraction (Example)Component Timing AbstractionCompositional Real-Time GuaranteesCompositional Real-Time GuaranteesAbstraction OverheadAbstraction Overhead BoundAbstraction OverheadAbstraction OverheadSummaryFuture WorkReferencesOctober 3, 2005 CIS 700 1Compositional Real-Time Scheduling FrameworkInsik ShinOctober 3, 2005CIS 7002Outline• Compositional scheduling framework– Scheduling component model– Periodic resource model • Schedulability analysis• Utilization bound• Component timing abstractionOctober 3, 2005CIS 7003Traditional Scheduling Framework• Single real-time task in a single applicationCPUOS SchedulerTask Task TaskApplication Application ApplicationHierarchical Scheduling Framework (HFS)October 3, 2005CIS 7004• Multiple real-time tasks with a scheduler in a single application, forming a hierarchy of schedulingCPUOS SchedulerApplicationSchedulerTask TaskApplicationSchedulerTask TaskApplicationSchedulerTask TaskOctober 3, 2005CIS 7005Compositional Scheduling FrameworkCPUOS SchedulerJava Virtual MachineJ1(50,3) J2(75,5)VM SchedulerMultimediaT2(33,10)Digital ControllerT1(25,5)October 3, 2005CIS 7006VM Scheduler’s ViewpointCPUOS SchedulerMultimediaT2(33,10)Digital ControllerT1(25,5)Java Virtual MachineJ1(50,3) J2(75,5)VM SchedulerCPU ShareReal-Time Guarantee on CPU SupplyOctober 3, 2005CIS 7007Problems & Approach I• Resource supply modeling– Characterize temporal property of resource allocations• we propose a periodic resource model– Analyze schedulability with a new resource modelOctober 3, 2005CIS 7008OS Scheduler’s ViewpointCPUOS SchedulerJava Virtual MachineJ1(50,3) J2(75,5)VM SchedulerMultimediaT2(33,10)Digital ControllerT1(25,5)Real-Time TaskReal-Time DemandOctober 3, 2005CIS 7009Problems & Approach II• Real-time demand composition– Combine multiple real-time requirements into a single real-time requirementReal-Time ConstraintReal-Time ConstraintReal-Time ConstraintEDF / RMT1 (p1, e1) T2 (p2, e2) T (p, e)Compositional Real-time Scheduling FrameworkOctober 3, 2005CIS 70010•Goal – to support compositionalityfor timeliness aspect– to achieve system-level schedulability analysis usingthe results of component-levelschedulability analysis • Scheduling component modelingOctober 3, 2005CIS 70011Scheduling Component Modeling• Scheduling– assigns resources to workloads by scheduling algorithms• Scheduling Component Model : C(W,R,A)– W : workload model– R : resource model– A : scheduling algorithmResourceSchedulerWorkloadPeriodic Task WorkloadPeriodic TaskEDF / RM???October 3, 2005CIS 70012Resource Modeling• Dedicated resource : always available at full capacity• Shared resource : not a dedicated resource– Time-sharing : available at some times– Non-time-sharing : available at fractional capacity0time0time0timeOctober 3, 2005CIS 70013Resource Modeling• Time-sharing resources– Bounded-delay resource model [Mok et al., ’01]characterizes a time-sharing resource w.r.t. a non-time-sharing resource– Periodic resource model Γ(Π,Θ) [Shin & Lee, RTSS ’03]characterizes periodic resource allocations 0 1 2 3 4 5 6 7 8 9 timeOctober 3, 2005CIS 70014Schedulability Analysis• A workload set is schedulable under a scheduling algorithm with available resources if its real-time requirements are satisfiable• Schedulability analysis determines whether resource demand,which a workload set requires under a scheduling algorithmresource supply,which availableresources provide≤schedulerresourceworkload workloadOctober 3, 2005CIS 70015Resource Demand Bound• Resource demand bound during an interval of length t– dbf(W,A,t) computes the maximum possibleresource demand that W requires under algorithm A during a time interval of length t• Periodic task model T(p,e) [Liu & Layland, ’73]– i.e., T(3,2)0 1 2 3 4 5 6 7 8 9 10 tdemandOctober 3, 2005CIS 70016Demand Bound Function - EDF• For a periodic workload set W= {Ti(pi,ei)}, –dbf (W,A,t) for EDF algorithm [Baruah et al.,‘90]–Example: W = {T1(3,2), T2(4,1)}iWTiepti⋅⎥⎦⎥⎢⎣⎢=∑∈ t)EDF,(W, dbf0 1 2 3 4 5 6 7 8 9 10 tdemandOctober 3, 2005CIS 70017Resource Supply Bound• Resource supply during an interval of length t– sbfR(t) : the minimum possible resource supply by resource R over all intervals of length t• For a single periodic resource model, i.e.,Γ(3,2)– we can identify the worst-case resource allocationOctober 3, 2005CIS 70018Resource Supply Bound• supply = • supply = • sbfR(i) = 130 time0 time1R(3,2)iR(3,2)October 3, 2005CIS 70019Resource Supply Bound• Resource supply during an interval of length t– sbfR(t) : the minimum possible resource supply by resource R over all intervals of length t• For a single periodic resource model, i.e.,Γ(3,2)– we can identify the worst-case resource allocation0 1 2 3 4 5 6 7 8 9 10 tsupplyOctober 3, 2005CIS 70020Supply Bound Function• Resource supply during an interval of length t– sbfΓ(t) : the minimum possible resource supply by resource R over all intervals of length t• For a single periodic resource model Γ(Π,Θ)[]otherwise)1(,2)1( if)1())(1()t(sbfΘ−Π+Θ−Π+∈⎩⎨⎧Θ−Θ−Π+−=Γkktkkt0 1 2 3 4 5