CprE 458/558: Real-Time SystemsBest-Effort SchedulerBest-Effort Scheduler (Contd.)HVDF – Highest Value Density FirstCompetitive Analysis of BE schedulerCompetitive Analysis of BE scheduler (contd.)CprE 458/558: Real-Time Systems (G. Manimaran) 1CprE 458/558: Real-Time Systems Best Effort SchedulingCprE 458/558: Real-Time Systems (G. Manimaran) 2Best-Effort Scheduler•No schedulability check•Schedule construction – online•Overload handling (handling timing faults)–Value based scheduling (chapter 2)–Imprecise computation (chapter 4)–(m,k)-firm task scheduling (chapter 4)•Value based scheduling–Task Ti : <Ci, Pi, Vi> where Vi is the value offered by Ti.–If Ti finishes by di, it offers a value of Vi. Else, it offers a value of 0 (sometimes a negative value).CprE 458/558: Real-Time Systems (G. Manimaran) 3Best-Effort Scheduler (Contd.)•Deadline scheduler (eg., EDF) – good for under/normal load•Value-based scheduler (e.g., HVDF: Highest Value Density First) – good for overload•Hybrid (Adaptive) scheduler --- good for all loads•Heuristics Hi = function(value, deadline). •Several heuristics exist.CprE 458/558: Real-Time Systems (G. Manimaran) 4HVDF – Highest Value Density First•Value density = Vi/Ci (i.e., value per unit computation time).•Higher the value density, higher the importance and hence higher the priority.•HDVF scheduler schedules tasks based on “value density”CprE 458/558: Real-Time Systems (G. Manimaran) 5Competitive Analysis of BE scheduler•The competitive factor, BA , of an on-line scheduling algorithm is defined asWhere S: a given task setVA(S): value produced by given scheduler AVCA(S): value produced by clairvoyant scheduler, the scheduler which knows complete knowledge of all tasks at the beginning itself.Sallfo rBSVSVACAA,)()(CprE 458/558: Real-Time Systems (G. Manimaran) 6Competitive Analysis of BE scheduler (contd.)•The upper bound on the competitive factor for any on-line scheduling isWhere Y = highest value density / lowest value density•When Y = 1 (i.e., Vi = Ci), the competitive factor is 0.25 (for single processor, same as the result discussed in chapter
View Full Document
Unlocking...