Software Systems Spring 2005 For today, you should have: 1) read Tanenbaum pages 142--151 2) started Homework 3, including the reading from The Cow Book and Stevens. Outline: 1) Exam 1 solutions and comments 2) scheduling 3) in-class reading exercise 4) Homework 3 For next time you should: 1) read the Lottery Scheduling paper and answer the reading questions below 2) keep working on Homework 3 Exam 1 ------ Overall, pretty good. Average = 45.7 / 56 = 81% 4 in the 50s, 11 in the 40s, 4 in the 30s There is plenty of semester left! Often I don't get to write detailed comments, but I am happy to explain in class or in person. Grading is subjective, but I try to be 1) fair: similar answers get similar credit 2) discriminative: better answers get more credit 3) reasonable: a clear, correct answer should get full credit, even if there is a better answer 4) flexible: if you do something unexpected but valid, I try to give appropriate credit 5) proportionate: if I can figure out what you did wrong, I try to deduct an appropriate amount of credit As a result of 4 and 5, I often give a lot of partial credit for things that are not what I had in mind. As a corollary, you should try to put _something_ down for every question. Part One: Question 3, there were two approaches that worked. Question 5, remember that locality is a property of an access pattern, not a data layout. Data can be contiguous or fragmented. Some people pointed out that there is more data on the outer tracks, but only by (roughly) a factor of 2, so this is a smaller effect than locality for most workloads. Part Two: Question 1: we can't tell exactly how big the cache is from this data, but 2^18 B clearly seems to fit and 2^20 B clearly doesn't. Try to express answers in units scaled so that the number part is between 0.1 and 1000. Question 4: for full credit, you had to mention clustering, since this question is answered in the reading Increased bandwidth is a good answer, although that may be a property of the buses, not the devices. Wear and tear is a good answer, although more for seeking than spinning. Some answers were really corollaries of the decreased access time. Part Two: Question 1: LB model suggests a straight line which is an accelerating curve on a logx scale Question 2: I was hoping for exact answers, but accepted good approximations Question 4: for full credit you had to mention variability in rtt Question 6: there are several assumptions 2 assumptions got full credit, one good one got 3 Homework 3 ---------- Any questions from the reading? Any questions about what you are doing? Any problems downloading and running the programs? Feel free to pursue interesting leads, even if it means you don't do all three experiments. Reading ------- Read the Economist article about Dataslide and answer the following questions: 1) How did they get from a vibration rate of 600 Hz to an average access time of 417 ns? What does this imply about the way data is written and read? 2) If they really can get the vibration frequency up to 100 kHz, what will the average access time be? 3) The company web pages say "Each read-write head' addresses a 'page' of 512 bytes." If that's right, how many heads do we need to address the 72 GB the article mentions? 4) Assuming we have enough heads to address 72 GB, and a vibration rate of 100 kHz, how long would it take to read the entire contents of the surface? 5) What bandwidth would be necessary to handle all that data? Scheduling (continued from notes07) ---------- Round Robin: give each process a little bit of time this is an approximation of SJF in the case where we don't know the durations example: 1 ms and 10 ms again, but we don't know which is which, quantum = 1 ms result: almost as good as SJF, and much better than FIFO pathology: can be worse than FIFO example: two 10 ms processes, quantum = 1 ms pro: generally good when there is large variability in duration con: overhead becomes signficant as quantum gets smaller pessimal when jobs are the same length External priorities: users or the the system might attach priorities to different processes example: interactive jobs get highest priority because response time is important and they tend to have short bursts long-running computationally-intensive processes might get lower priority (but maybe longer quanta) pro: satisfies real time requirements con: burden on users/programmers starvation / bidding wars Multi-level feedback queue: use past behavior to predict future behavior two kinds of learning: 1) predict the duration of the next burst based on past bursts 2) classify process based on long-term behavior Adjust quantum length automatically to reduce overhead for long-running computationally-intensive processes (but why bother?) Tradeoff against the expense of keeping track of accounting information. Non-deterministic scheduling: Example: lottery scheduling. Problem: for any deterministic system you can contruct pathological cases that yield bad performance Solution: a little randomness goes a long way Con: unpredictable execution model for programmers Evaluation techniques for scheduling strategies ----------------------------------------------- 1) Analysis: only works for very simple strategies/models 2) Simulation: useful for checking out wide range of possibilities. depends on workload model or traces 3) Implementation: most reliable, but also depends on workload Which do Waldspurger and Weihl do? What is their workload or workload model? What are their performance metrics? Dependencies ------------ Complication: there are often dependencies among tasks. 1) the sooner you issue an I/O command, the sooner it completes 2) users might not submit the next process until this one completes These dependencies limit the usefulness of simple queueing models. Instead, designers use heuristics like: 1) give processes priority if you expect them to do I/O soon (and why might you suspect them?) 2) degrade the priority of things that have been running for a long time a) they are less likely to be interactive b) the relative cost of delays is declining Real-time scheduling -------------------- When processes arrive, we generally need to know 1) their resource requirements 2) their deadlines 3) sometimes a cost function (how bad would it be if we missed the deadline) The goal of the real time scheduler is either 1) find any schedule that misses no deadlines (or maybe the best such schedule) 2) if not possible, minimize the total cost of all misses Some real-time schedulers involve recurring tasks, in which case they sometimes break the time line into cycles that are the LCM of the cycle times of recurring tasks. In the case where there is guaranteed to be a schedule that misses no deadlines, and the cost of a context switch is zero, there is a simple algorithm that is guaranteed to find a successful schedule: Work on the Process with the Nearest Deadline First Sound familiar? Problem: if the schedule is untenable, this algorithm is often pessimal.