AdministriviaErrataLinux 2.6 ($<,$2.6.23)SchedulerLinux task listsRecall Limitations of BSD schedulerLottery scheduling href {http://www.usenix.org/publications/library/proceedings/osdi/full_papers/waldspurger.pdf}{[Waldspurger'94]}Grace under load changeLottery ticket transferLottery ticket transferCompensation ticketsLimitations of lottery schedulingStride scheduling href {http://www.scs.stanford.edu/10wi-cs140/sched/readings/stride.pdf}{[Waldspurger'95]}Stride scheduling exampleStride vs. lotteryStride vs. lotterySimulation resultsStride ticket transferStride ticket transferScaling pass valueSleep/wakeupSleep/wakeupStride error revisitedStride error revisitedStride error revisitedHierarchical stride exampleBVT href {http://www.scs.stanford.edu/10wi-cs140/sched/readings/bvt.pdf}{[Duda]}Process weightsBVT exampleSleep/wakeupgcc wakes up after I/OReal-time threadsRunning warpedWarped thread hogging CPUGoogle exampleSMART href {http://www.scs.stanford.edu/10wi-cs140/sched/readings/smart.pdf}{[Nieh]}SMART thread propertiesBVFT high-level overviewSMART AlgorithmDistributed schedulingThe universality of schedulingHow to allocate resourcesPostscriptAdministrivia• Project 1 due Thursday 4:15pm- Show up to lecture for free extension to midnight- SCPD can just watch lecture before midnight• If you need longer, email cs140 -sta ff.- Put “extension” in the subject- Tell us where you are, andhow much longer you need.- We will give short extensions to people who don’t abuse this•Section Friday to go ov e r project 2• Project 2 Due Thursday, Fe b. 4• Midterm following Tuesday, Fe b. 9• Midterm will be open book, open notes- Feel free to bring textbook, printouts of slides- Laptop computers or other electronic devices prohibited1/36Errata• Fair queuing isn’t SJF scheduling for networks• SJF has three limitations- Can’t see the future- Optimizes response time but not turnaround time- Not fair• The network setting does address the first two• But SJF still unfair- Would starve long packets on the network- So obviously not same asfair queuing• Today’s lecture will discuss CPU schedulers like FQ2/36Linux 2.6 (< 2.6.23) Scheduler• Linux ≤ 2.4 scheduler had several drawbacks- O(n) operations for n processes (e.g., re-calculate “goodness” ofall processes. Decaying pestcpu in BSD similarly O(n).)- On SMPs: No affinity (bad for cache), global run-queue lock• Linux 2.6 goal: Be O(1) for all operations• 140 Priority levels- 1–100 for real-time tasks (configured by administrator)- 101–140 for user tasks (depend on nice & behavior)• Also keeps per-process 4-entry “load estimator”- How much CPU consumed in each of the last 4 seconds- Adjusts priority of user procs by ±5 based on behavior3/36Linux task lists• Keeps one active/expired array pair per CPU- Avoids global lock and helps with affinity- SMP load balancer can move procs between CPUs• Run highest-priority task in active array- After task uses quantum, place it in expired list- Swap expired/active pointers when active list empty• Bitmap cache for empty/non-empty state of e a c h list4/36Recall Limitations of BSD s c he duler• Mostly apply to Linux scheduler, too• Hard to have isolation / prevent interference- Priorities are absolute• Can’t donate CPU (e.g., to server on RPC)• No flexible control- E.g., In monte carlo simulations, error is 1/√N after N trials- Want to get quick estimate from new computation- Leave a bunch running for a while to get more accurate results• Multimedia applications- Often fall back to degraded quality levels depending onresources- Want to control quality of different streams5/36Lottery scheduling [Waldspurger’94]• Inspired by economics & free markets• Issue lottery tickets to processes- Let pihave titickets- Let T be total # of tickets, T =∑iti- Chance of winning next quantum is ti/T.- Note lottery tickets not used up, more like season tickets• Control avg. proportion of CPU for e a c h process• Can also group processes hierarchically for c o ntrol- Subdivide lottery tickets allocated to a particular process- Modeled as currencies, funded through other currencies6/36Grace under loa d change• Adding/deleting jobs affects all proportionally• Example- 4 jobs, 1 ticket each, each job 1/4 of CPU- Delete one job, each remaining one gets 1/3 of CPU• A little bit like priority scheduling- More tickets means higher priority- But with even one ticket, won’t starve- Don’t have to worry about absolute priority problem(e.g., where adding one high-priority job starves everyone)7/36Lottery ticket transferserverclientrequesttktresponse• Can transfer tickets to other processes• Perfect for IPC (Inter-Process Communication)- Client sends request to server- Client will block until server sends response- So temporarily donate tickets to server• Also avoids priority inversion• How do ticket donation and priority donation differ?8/36Lottery ticket transferserverclientrequesttktresponse• Can transfer tickets to other processes• Perfect for IPC (Inter-Process Communication)- Client sends request to server- Client will block until server sends response- So temporarily donate tickets to server• Also avoids priority inversion• How do ticket donation and priority donation differ?- Consider case of 1,000 equally important processes- With priority, no difference between 1 and 1,000 donations- With tickets, recipient amasses more and more tickets8/36Compensation tickets• What if process only uses fractio n f of quantum?- Say A and B have same number of lottery tickets- Proc. A uses full quantum, proc. B uses f fraction- Each wins the lottery as often- B gets fraction f of B’s CPU time. No fair!• Solution: Compensation tickets- Say B uses fraction f of quantum- Inflate B’s tickets by 1/ f until it next wins CPU- E.g., if B always uses half a quantum, it should gets scheduledtwice as often on average- Helps maximize I/O utilization (remember matrix multiply vs.grep from last lecture)9/36Limitations of lottery scheduling• Unpredictable latencies• Expected errors O(sqrt(na)) for naallocations- E.g., process A should have had 1/3 of CPU yet after 1 minutehas had only 19 seconds- Absolute error – absolute value of A’s error (1 sec)- Relative error – A’s error considering only 2 procs, A and B• Prob. of ge tting k of n quanta is binomial distribution-(nk)pk(1 − p)n−khp = fraction tickets owned,(nk)=n!(k!(n−k)!)i- For
View Full Document
Unlocking...