Transcription
Sporadic Server Scheduling in LinuxTheory vs. PracticeMark StanovichTheodore BakerAndy Wang
Real-Time Scheduling Theory Analysis techniques to design a system tomeet timing constraintsSchedulability analysis–Workload models–Processor models–Scheduling algorithms
Real-Time Scheduling Theory Analysis techniques to design a system tomeet timing constraintsSchedulability analysis–Workload models–Processor models–Scheduling algorithms
Periodic TaskTask {T, C, D}jobs (j1, j2, j3, )Deadline DPeriod TtimeComputation timeWCET CRelease time4
Periodic Tasksched setscheduler(SCHED FIFO)clock nanosleep()
Periodic TaskAssumptions WCET is reliable Arrivals are periodicNot realistic for most tasks
Polling ServerReplenishment periodtimeJob arrivalsInitialbudgettime
Polling ServerType of aperiodic server CPU time no worse than an equivalentperiodic task Can be modeled as a periodic task Budget consumed as CPU time is used WCET Initial BudgetPeriod Replenishment PeriodCPU time forfeited if not usedReplenish budget every period
Polling ServerGood Bounds CPU timeAnalyzable workloadSimplicityCan be better Faster response time if budget is not forfeited
Sporadic ServerReplenishment periodtimeJob arrivalsInitialbudgettimereplenishments
Sporadic Server Originally proposed by Sprunt et. al. Parameters–Initial budget–Replenishment period Bounds CPU interference for other tasks Fits into the periodic task workload model Better avg. response time than polling server
Sporadic ServerScheduling algorithm for fixed-task-prioritysystems Can be used in UNIX priority modelSCHED SPORADIC is a version of SSdefined in POSIX definition
ImplementationLinux 2.6.38 Softirq threading patch ported from earlier RTpatchSporadic server implementationUniprocessor
Sporadic Server PerformanceMetrics Interference for lower priority tasks Average response time
An experimentASends UDP packet withcurrent timestampBReceives UDP packetsCalculate response time based onarrival at UDP layerMeasure CPU time for 10 secondburst
Measuring CPU Time Regher's “hourglass” technique Constantly read time stamp counter –Detect preemptions by larger gaps–Sum execution chunksHourglass thread lower than SS thread–Measures interference from SS thread
Measuring CPU TimeNetwork receive thread Sporadic and polling server Budget 1 msecPeriod 10 msecSCHED FIFOHourglass thread SCHED FIFO Lower priority than network receive thread
CPU Utilization
Response Time
Interference SS budget limited to CPU demand Additional overheads lower priority tasks –Context switch time–Cache eviction and reloadingNot in theoretical workload modelGuarantees of theory require interference tobe included in the analysis
Polling Server aperiodic job arrivalSSbudget 2 CStime aperiodic job CPU timetime21
Sporadic Server aperiodic job arrival aperiodic job CPU time replenishment periodSSbudget 2 CStime max repltime22
Over Provisioning All context switch time may not be used– e.g., one replenishment per periodAccount for CS time on-line–Charge SS for each preemption
CPU Utilization
Response Time
Response Time
Analysis Light load– Sporadic Server Low response time– Polling Server High response time Heavy load– Sporadic Server High response time Dropped packets– Polling Server Low response time No dropped packets27
Can we get the best of both?Sporadic ServerLight loadsPolling ServerHeavy loads28
Hybrid Server How to switch–Ensure bounded interference–SS with 1 replenishment is same as pollingserver–Coalesce replenishments Push replenishments further into the futureSwitching point–Server has work but no budget
Sporadic Servertime
Sporadic Servertime31
Response Time
CPU Utilization
SwitchingImmediate coalescing may be too extreme CPU time could be used for better response timeGradual approach Coalesce a few replenishments
Sporadic Servertime35
Sporadic Servertime36
Sporadic Servertime37
Response Time
CPU Utilization
Conclusion Theoretical analysis provides solid guarantees Implementation must match abstract models Additional interference terms need to beconsideredSS can fit into the theoretical analysis
Deferrable Server
Deferrable ServerBandwidth Preserving Allow server to retain budget Periodically replenish budget WCET ! Budget
Response Time
Replenishment Policyreplenishmentreplenishment periodinitialbudgettimearrival time(work available for server)44
Bandwidth Preservationreplenishmentreplenishment periodinitialbudgettimearrival time(work available for server)45
Sporadic Servertime46
Real-Time Scheduling Theory . Schedulability analysis - Workload models - Processor models - Scheduling algorithms . time Period T Computation time WCET C Deadline D Task jobs (j 1, j 2, j 3, ) Release time 4 Task {T, C, D} Periodic Task . . systems Can be used in .
