OutlineReal Time SchedulersAssumptionsTask ModelDefinitionsSlide 6Rate MonotonicSlide 8Earliest Deadline FirstEDFProportional ShareCommon Proportional Share CompetitorsSlide 14Slide 15Lottery SchedulingLottery Scheduling Waldspurger and Weihl (OSDI 94)Basic IdeaFairnessExample List-based LotteryBells and WhistlesKernel ObjectsPowerPoint PresentationSlide 25CompensationTicket TransferControl ScenariosOther Kinds of ResourcesScheduling: Beyond “Ordinary” UniprocessorsRR and System ThroughputSlide 32Multiprocessor SchedulingArchitecturesEffect of WorkloadAffinity SchedulingProcessor PartitioningProcess Control Claims Typical speed-up profileCo-SchedulingSlide 40CM*’s VersionDesignNetworks of WorkstationsHarvesting Idle CyclesIssuesMotivation for Cycle SharingWhich Tasks?Finding DestinationWhen to MoveHow - Negotiation PhaseHow - Execution PhaseRemote System CallsHow - Process MigrationMigration based on Virtual MachinesIsolation Between V.M.sEncapsulationProcessor Scheduling & Energy ManagementExploiting IdlenessDynamic Voltage ScalinglpARM SystemImplementation of Voltage Scheduling AlgorithmsInterval Scheduling (Speed Setting)Based on Earliest Deadline FirstIntuitionSlide 65Slide 66Slide 67Recent AdvancesOutline•Objective for today’s lecture:Advanced topics in schedulingReal Time Schedulers•Real-time schedulers must support regular, periodic execution of tasks (e.g., continuous media).–CPU Reservations•“I need to execute for X out of every Y units.”•Scheduler exercises admission control at reservation time: application must handle failure of a reservation request.–Proportional Share•“I need 1/n of resources”–Time Constraints•“Run this before my deadline at time T.”Assumptions•Tasks are periodic with constant interval between requests, Ti (request rate 1/Ti)•Each task must be completed before the next request for it occurs•Tasks are independent•Worst-case run-time for each task is constant (max), Ci•Any non-periodic tasks are specialTask Modeltime12T1T1T2C1 = 1C2 = 1Definitions•Deadline is time of next request•Overflow at time t if t is deadline of unfulfilled request•Feasible schedule - for a given set of tasks, a scheduling algorithm produces a schedule so no overflow ever occurs.•Critical instant for a task - time at which a request will have largest response time.–Occurs when task is requested simultaneously with all tasks of higher priorityTask Modeltime12TiTiT2C1 = 1deadlineoverflowCritical instantRate Monotonic•Assign priorities to tasks according to their request rates, independent of run times•Optimal in the sense that no other fixed priority assignment rule can schedule a task set which can not be scheduled by rate monotonic.•If feasible (fixed) priority assignment exists for some task set, rate monotonic is feasible for that task set.Rate Monotonictime12Ti=2T2=5C1 = 1C2 = 1Earliest Deadline First•Dynamic algorithm•Priorities are assigned to tasks according to the deadlines of their current request•With EDF there is no idle time prior to an overflow•For a given set of m tasks, EDF is feasible iffC1/T1 + C2/T2 + … + Cm/Tm  1•If a set of tasks can be scheduled by any algorithm, it can be scheduled by EDFEDFtime12TiTi=2T2=5C1 = 1C2 = 10T0=4C0 = 1Released attime t0Released attime t2Released attime t4¼ + ½ + 1/5 < 1Proportional Share•Goals: to integrate real-time and non-real-time tasks, to police ill-behaved tasks, to give every process a well-defined share of the processor.•Each client, i, gets a weight wi•Instantaneous share fi (t) = wi /( wj )•Service time (fi constant in interval) Si(t0, t1) = fi (t)  t•Set of active clients varies fi varies over timeSi(t0 , t1) = fi () djA(t)t0t1Common Proportional Share Competitors•Weighted Round Robin – RR with quantum times equal to shareRR:WRR:•Fair Share –adjustments to priorities to reflect share allocation (compatible with multilevel feedback algorithms)Linux10203020Common Proportional Share Competitors•Weighted Round Robin – RR with quantum times equal to shareRR:WRR:•Fair Share –adjustments to priorities to reflect share allocation (compatible with multilevel feedback algorithms)Linux10201010Common Proportional Share Competitors•Weighted Round Robin – RR with quantum times equal to shareRR:WRR:•Fair Share –adjustments to priorities to reflect share allocation (compatible with multilevel feedback algorithms)Linux01010Lottery Scheduling•Lottery scheduling [Waldspurger96] is another scheduling technique.•Elegant approach to periodic execution, priority, and proportional resource allocation.–Give Wp “lottery tickets” to each process p.–GetNextToRun selects “winning ticket” randomly.•If ΣWp = N, then each process gets CPU share Wp/N ... ...probabilistically, and over a sufficiently long time interval.–Flexible: tickets are transferable to allow application-level adjustment of CPU shares.–Simple, clean, fast.•Random choices are often a simple and efficient way to produce the desired overall behavior (probabilistically).Lottery SchedulingWaldspurger and Weihl (OSDI 94)•Goal: responsive control over the relative rates of computation•Claims:–Support for modular resource management–Generalizable to diverse resources–Efficient implementation of proportional-share resource management: consumption rates of resources by active computations are proportional to relative shares allocatedBasic Idea•Resource rights are represented by lottery tickets–Give Wp “lottery tickets” to each process p.–abstract, relative (vary dynamically wrt contention), uniform (handle heterogeneity)–responsiveness: adjusting relative # tickets gets immediately reflected in next lottery•At allocation time: hold a lottery;Resource goes to the computation holding the winning ticket.–GetNextToRun selects “winning ticket” randomly..Fairness•Expected allocation is proportional to # tickets held - actual allocation becomes closer over time.•Number of lotteries won by clientE[w] = n p where p = t/T•Response time (# lotteriesto wait for first win)E[n] = 1/pw # winst # ticketsT total # tickets n # lotteriesExample List-based Lottery102512T = 20Random(0, 19) = 15101217Summing:Bells and Whistles•Ticket transfers - objects that can be explicitly passed in messages–Can be used to solve priority inversions•Ticket inflation–Create more - used