A SMART Scheduler for Multimedia Applications ============================================= What problems do multimedia applications have? Video jitter Audio/video sync problems With SVR4 real-time scheduler, can starve normal processes What are demands of multimedia applications? Soft real-time constraints High resource demands (e.g., CPU-intensive video codecs) Dynamically adaptive (e.g., reduce frame rate or resolution) Coexistence with conventional computations Don't turn your computer into a TV set! Dynamic environment (people start/stop programs, etc.) User preferences If watching video while waiting for compile, don't slow compile If compiling in background during videoconference, don't drop frames Key idea: Separate *importance* from *urgency* Figure out which processes are important enough to run Run whichever of these is most urgent What does application interface look like? Can specify *time constraints* and *notifications* time constraint = deadline + estimate of CPU required before deadline notification = notify-time + notify-handler notify-time - time after which to notify notify-handler - entry for upcall (basically a signal handler) Why might applications use the notify-time? What does user interface look like? long priocntl (idtype_t idtype, id_t id, int cmd, /* arg */ ...); Set two properties for each thread: priority and share Perhaps could have some GUI for users to set these more conveniently Importance of an application measured as "value-tuple". What's this? value-tuple: What is priority? Parameter set by user BVFT - roughly when process's quantum would end if scheduled now (This is why we talked about weighted fair queuing earlier...) How are tuples ordered? priority takes absolute precedence at same priority, order by BVFT What is "biased virtual finishing time" (BVFT)? Each task has "virtual time", which advances as (time consumed)/(share) - Share is basically the same as weight in weighted fair queuing: High-weight packet queue sends multiple bits in one clock cycle Hish-share process consumes multiple ticks of CPU in one virtual tick Each priority has a queue; each queue has a "queue virtual time" Let S be sum of shares of all processes on queue Queue virtual time advances as (time consumed for proc on queue)/S Basic idea: When task's VT is same as its Queue's VT, task got fair share Virtual finishing time is time process would finish if scheduled If V is proc's virtual time, Q is quantum, and S is share VFT = V + (Q/S) What happens when you add a process to a queue? Assign it the queue virtual time at time the it joins (Makes sense, since initially it will vacuously have had its fair share) What about the B (biased) in BVFT? What is this bias? A per-process additive constant B to skew VFT; initially 0 BVFT = VFT + B/S What's the point here? This is to capture urgency vs. importance trade-off During load spike, it's okay to delay non-RT or non-interactive task But over long term rate should be the same, so max value of B is bounded Say a task goes to sleep? Should you just leave it on the queue? Bad idea -- will accumulate very large amounts of "credit" Solution? Leave on the queue until deadline, or for system default period How to remove from queue? Want to save difference between task and queue Say process sleeps after using E time (E < quantum Q), B total bias v = BVFT - ((Q - E)/S) - B/S delta = v - (queue virtual time) Save value delta. When process rejoins the queue, set: BVFT = (queue virtual time) + delta + Q/S Note that bias has gone back to zero Means interactive procs that sleep for input get priority restored How does SMART scheduling algorithm work? - If task with best value-tuple is conventional, run it - Consider all real-time tasks with better value-tuple than best conventional - For each such RT task, starting from the best value-tuple Can you run it without missing deadlines of tasks w. better value-tuples? Yes? Add to *schedulable* set Run task with earliest deadline in *schedulable* set - Send signal to tasks that won't meet their deadlines Go over Fig. 1 example (p. 132) How does this fit into Solaris scheduling framework? How do results look? Fig 5.: Why no dhrystone for SVR4-RT?