Ò Hard to accurately estimate n ò Interrupts ò Cache misses ò Disk accesses ò Variable execution time depending on inputs Ò Audio application needs to deliver a frame every nth of a second ò Too many or too few frames unpleasant to hear Ò If I know it takes n ticks to process a frame of audio, just schedule my application n ticks before the deadline ![]() Ò Different model: need to do a modest amount of work by a deadline Ò Unclear how CPU topologies are addressedĬFS Summary ò Simple idea: logically a queue of runnable tasks, ordered by who has had the least CPU time ò Implemented with a tree for fast lookup, reinsertion ò Global clock counts virtual ticks ò Priorities and other features/tweaks implemented by playing games with length of a virtual tick ò Virtual ticks vary in wall-clock length per-process Other refinements ò Per group or user scheduling ò Real to virtual tick ratio becomes a function of number of both global and user’s/group’s tasks Ò When a GUI task is runnable, generally goes to the front ò Dramatically lower vclock value than CPU-bound jobs ò Reminder: “front” is left side of tree GUI program strategy ò Just like O(1) scheduler, CFS takes blocked programs out of the timeline ò Virtual clock continues ticking while tasks are blocked ò Increasingly large deficit between task and global vclock Interactive latency ò Recall: GUI programs are I/O bound ò We want them to be responsive to user input ò Need to be scheduled as soon as input is available ò Will only run for a short time Ò Result: Higher-priority tasks run longer, low-priority tasks make some progress Ò In CFS, priorities weigh the length of a task’s “tick” ò Example: ò For a high-priority task, a virtual, task-local tick may last for 10 actual clock ticks ò For a low-priority task, a virtual, task-local tick may only last for 1 actual clock tick What happened to priorities? ò Priorities let me be deliberately unfair ò This is a useful feature Ò Strategies: ò Could initialize to current time (start at right) ò Could get half of parent’s deficit ![]() Ò Global vclock ticks once every 4 real ticks ò Each task scheduled for one real tick advances local clock by one tickĮdge case 1 ò What about a new task? ò If task ticks start at zero, doesn’t it get to unfairly run for a long time? Ò No more runqueues ò Just a single tree-structured timeline More details ò Task’s ticks make key in RB-tree ò Fewest tick count get serviced first Ò Each task counts how many clock ticks it has had ò Example: 4 tasks Ò log(n) time for: ò Picking next task (i.e., search for left-most task) ò Putting the task back when it is done (i.e., insertion) ò Remember: n is total number of tasks on systemĭetails ò Global virtual clock: ticks at a fraction of real time ò Fraction is number of total tasks Ò Always pick the “neediest” task to run ò Until it is no longer neediest ò Then re-insert old task in the timelineīut lists are inefficient ò Duh! That’s why we really use a tree ò Red-black tree: 9/10 Linux developers recommend it Ò Elegance: Structure (and complexity) of solution matches problemĬFS idea ò Back to a simple list of tasks (conceptually) ò Ordered by how much time they’ve had ò Least time to most time Ò Software engineering observation: ò Kernel developers better understood scheduling issues and workload characteristics, could make more informed design choice batch jobs? ò CPU topologies? ò Per-user fairness? ò Alice has one task and Bob has 49 why should Bob get 98% of CPU time?Įditorial ò Real issue: O(1) scheduler bookkeeping is complicated ò Heuristics for various issues makes it more complicated ò Heuristics can end up working at cross-purposes Ò Other advanced scheduling issues ò Real-time scheduling ò Kernel preemption ò Priority laundering ò Security attack trick developed at Stony Brookįair Scheduling ò Simple idea: 50 tasks, each should get 2% of CPU time ò Do we really want this? ò What about priorities? ò Interactive vs. Ò Today: Completely Fair Scheduler (CFS) – new hotness ![]() ![]() ò O(1) scheduler – older Linux scheduler Last time… ò Scheduling overview, key trade-offs, etc.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |