COMP 3430 Operating systems – Chapter 7, 8, 9 reading notes Summer 2021
Chapter 7: Scheduling: Introduction
7.1Workloadassumptions ……………………………… 2 7.2Schedulingmetrics ……………………………….. 2 7.3FirstIn,FirstOut(FIFO)……………………………… 2 7.4Shortestjobfirst ………………………………… 3 7.5ShortestTime-to-CompletionFirst(STCF)…………………….. 3 7.6ANewMetric:ResponseTime ………………………….. 3 7.7RoundRobin…………………………………… 4 7.8IncorporatingI/O ………………………………… 4 7.9NoMoreOracle …………………………………. 4
Chapter 8: Scheduling: The Multi-Level Feedback Queue 5 8.1MLFQ:Basicrules………………………………… 5 8.2Attempt#1:Howtochangepriority ……………………….. 5
Copyright By PowCoder代写 加微信 powcoder
Example1:Asinglelong-runningjob ……………………… 6 Example2andExample3 …………………………… 6 ProblemswithourcurrentMFLQ ……………………….. 6
8.3 Attempt #2: The Priority Boost . . . . 8.4 Attempt #3: Better accounting . . . . 8.5 Tuning MLFQ and other issues . . . .
Chapter 9: Scheduling: proportional share
………………………. 6 ………………………. 7 ………………………. 7
9.1Basicconcept:Ticketsrepresentyourshare……………………. 7 9.2Ticketmechanisms……………………………….. 8 9.3Implementation…………………………………. 8 9.4Anexample…………………………………… 8 9.5Howtoassigntickets? ……………………………… 8 9.6Stridescheduling(notethatthissectionisoptional) . . . . . . . . . . . . . . . . . . . . 9 9.7 The Linux completely fair scheduler (CFS) (note that this section is optional) . . . . . . . 9
Weighting(niceness)……………………………… 9 Usingred-blacktrees……………………………… 9
COMP 3430 Operating systems – Chapter 7, 8, 9 reading notes Summer 2021
Chapter 7: Scheduling: Introduction
In short, we have things that are lining up and wanting to work, how do we decide which of these things actually gets to go next?
7.1 Workload assumptions
7.2 Scheduling metrics
Workload assumptions let us constrain the scope of our problem, it’s an abstraction. We don’t have to think about all of the nitty gritty details of what’s going on within a particular process or job.
Workload assumptions actually let us try stuff out, but we can’t just try stuff out willy-nilly, we need to actually be able to measure stuff.
Turnaround time is a metric that we can use to compare policies.
You might want to go back and remind yourself about what a process is and what the OS does when it’s switching between processes, as the book recommends here.
The assumptions that are stated here are seriously unrealistic. Be able to convince yourself that each of these are unrealistic, and be able to explain why they are unrealistic. (e.g., Why is the workload assumption that all jobs only use the CPU an unrealistic assumption? Why is knowing how long a process is going to take unrealistic? We can time a process, isn’t it going to take the same amount of time the next time we run it? Why or why not?)
Can a process measure its own turnaround time? That is, can a process know when it arrived? Our unrealistic assumption that all processes arrive at the same time (at time 0) lets us assert that the process arrives at time 0, but in a more realistic situation, do you think that a process can know when it “arrived”?
Further, if a process itself can’t know when it arrived, can you (i.e., you, the user that’s actually physically hitting the ENTER key on your keyboard) know when a process has arrived?
7.3 First In, First Out (FIFO)
Look, it’s a queue again. Dang, they show up everywhere in an OS.
FIFO is literally “the first process that arrives gets to go first, the second process that arrives gets to go next”. Remember that we’re running to completion here, all jobs take the same amount of time, and that they all arrive “at the same time”.
COMP 3430 Operating systems – Chapter 7, 8, 9 reading notes
Summer 2021
The authors just finished talking about turnaround time, but now we switch to average turnaround time. Why do you think they did that? Can you reason about the performance of a scheduling policy if you only look at turnaround time for individual processes?
This is more of a statistics question than an OS question, but is the average turnaround time a reasonable way to reduce the turnaround time for all jobs and then compare the performance of a scheduling policy? Can you think of any other ways to reduce turnaround time to compare scheduling policies?
Considering the problem here with the convoy effect, how can you reorder the jobs in figure 7.2 to minimize average turnaround time?
I really like this analogy of grocery store checkouts. The analogy is currently more like a small corner store, though: one CPU, one checkout line. How might this analogy change if you go to a big store (e.g., Superstore, Safeway, or Sobeys)? How many “CPUs” do these big box stores have? Are any of the “CPUs” specialized in any way?
7.4 Shortest job first
“no proofs allowed”.
7.5 Shortest Time-to-Completion First (STCF)
7.6 A New Metric: Response Time
Hey look, here’s a solution to the convoy effect. Do you think this solution still works when you relax the assumptions/constraints on jobs? What if they don’t all arrive at the same time? What if you don’t know in advance how long a job is going to take?
Shortest Time-to-Completion definitely solves this issue with the non-preemptive shortest job first. Can you think of any circumstances where process A in the example in figure 7.5 (pg 6) never gets to run?
Are response time and turnaround time related to one another? Do you think that optimizing for one might affect the other? In other words: if I try to optimize response time, am I (in general) going to change the turnaround time?
COMP 3430 Operating systems – Chapter 7, 8, 9 reading notes
Summer 2021
7.7 Round Robin
Amortization, hey, that’s a word you’ve seen before! Where did you see that? What was the con- text? Is the context the same here?
Oh no! Minimizing response time made turnaround time really bad. Can you think of any ways to adjust how round robin works to try bring down both? Or do you think that response time and turnaround time affect each other like a see-saw (push one side down, the other goes up)?
Our current abstraction only considers jobs that only use the CPU. What other kinds of things do real processes do that might help better inform when a process should be “switched off” instead of just using time slices like with round robin?
7.8 Incorporating I/O
Imagine, for a second, that we incorporate the idea of I/O into plain Round Robin. The scheduling policy is going to schedule processes that are currently blocked on I/O — what would the CPU be doing when a process blocked on I/O gets scheduled by the Round Robin scheduling policy?
The authors sort of omit that adding I/O is effectively mixing preemptive and cooperative. What should a Round Robin scheduling policy do when a process invokes an I/O system call before its time slice is over?
The authors are describing this very abstractly, so try to think about this a little bit more con- cretely: how would you implement a Round Robin scheduling policy that incorporates I/O? Think about which data structure you would choose to manage your workload, and think about what information you need to keep about each job in the workload as it executes (e.g., is it waiting on an I/O operation?). Expand on this idea: what other kinds of properties of a process or job could you consider when implementing your scheduling policy?
7.9 No More Oracle
Oh no, now I feel like we’re taking all the stops out.
“A general purpose OS … knows very little about the length of each job”. Fair enough. Can it? How could it know about how long a job might take? Go beyond this: what kinds of things does an OS know about that can help inform it about scheduling, other than I/O and time to complete?
COMP 3430 Operating systems – Chapter 7, 8, 9 reading notes Summer 2021
Chapter 8: Scheduling: The Multi-Level Feedback Queue
This idea was first described in 1962!
8.1 MLFQ: Basic rules
8.2 Attempt #1: How to change priority
• Jobprioritycanchangeovertime.Thinkagainaboutdesign:doyouneedtostorepriorityasa property of the process?
The answer is no, you don’t. So, uh, ok, where is it, then?
Side note: Look back at struct task_struct (here: https://github.com/torvalds/linux/blob/master/include the only places where the word priority exists in this PCB is in terms of “real-time” processing
(this is very much out of scope for this course).
So we’ve got a list of queues (yo dawg I herd you like data structures), and each queue has a priority level. How would you even begin to arrive at deciding what priority level a job/process gets?
On Linux and macOS, one measurement of priority is called the “nice” level of the process. You can run this command on aviary or rodents:
ps -eo nice,comm
That will print out a list of the currently running processes and how “nice” they are. A lower value of “nice” implies that it’s a higher priority (it’s meaner?), so negative values for nice have a very high priority, and positive values means it’s very nice (lower priority). Processes are launched with a nice value of 0 by default, but you can manually change the nice level of a program (at least on launch) using the nice command (see man nice). You’ll see this near the end of the chapter, but niceness is “advice” about priority that the scheduler can include in its decisions about how to assign priority to a process.
The authors say here that “interactive” commands (ones that repeatedly get blocked waiting for I/O on an input device) get higher priority than those that don’t. How does the OS figure this out? What kinds of statistics might the OS need to keep about a process to know this? When might the OS be able to collect those statistics?
COMP 3430 Operating systems – Chapter 7, 8, 9 reading notes Summer 2021
• Thisapproachonlymovesprocessesdownintermsofpriority(everyoneimmediatelyhashigh- est priority, then your priority is lowered if you don’t seem to have any interactive looking tasks). This goes back to the last section, how does an OS figure out whether or not a process is doing
“interactive” tasks? (hint: when does a process manually give up control to the OS?)
Example 1: A single long-running job
• In example 1 (on pgs 3–4), we go from 8 queues to 3. How do you think we decide how many queues to have in the list?
Example 2 and Example 3
• Beyond that, the examples themselves are (I think) very good visual ideas of how the MLFQ works. Take the time to actually step through these examples!
Problems with our current MFLQ
• Theauthorstellyoutostopand“thinkasdeviouslyasyoucan”.Doit.Stophere(atthebottom of pg 5) and actually try to think about how you might break MFLQ with the rules that have been set up.
• Is starvation a problem in this situation? Seriously, decide for yourself here: would you rather have a system that’s responding to your input more quickly, or would you rather have a system that’s making meaningful progress in all processes? Does this change if you’re running, for ex- ample, a web server that doesn’t have “interactive” features? (e.g., there’s no GUI running on the physical system, there’s no monitor attached to it, there’s no keyboard or mouse attached to it)
• Is this issue of a “smart user” gaming the scheduler a real problem? Can you think of any mali- cious kinds of jobs where a “smart user” would want to take over the CPU in this way?
• “a program may change its behaviour over time;” What kind of a program might do this? What kind of a program would be highly interactive, then not? What kind of a program would be not interactive at all, then suddenly interactive?
8.3 Attempt #2: The Priority Boost
• Ifeellikethissolutionwouldmakefor“bursty”lookingbehaviour—everythingwouldsuddenly get the same level of priority, then slowly get shuffled down again. If the figures the authors were
COMP 3430 Operating systems – Chapter 7, 8, 9 reading notes Summer 2021
showing here were longer, I feel like you’d start to see a pattern with something that looks like “saw teeth”. The authors don’t show it this way, though. I actually don’t get figure 8.6, the figure on the right doesn’t actually match to me what they describe (no process is ever boosted to the
top queue, but instead the “gamed” process just moves down).
8.4 Attempt #3: Better accounting
• Now we’re adding time tracking: just how much time has this process had on the CPU? We’ve now got a few different pieces of information here: priority, interactivity in terms of I/O, and how much time the process has spent on the processor. Can you think of any other measure- ments that you can make about a process as its running that might help inform scheduling in the future?
8.5 Tuning MLFQ and other issues
• ThisismainlyaboutbeingabletovarythesettingsofarealMLFQscheduler,butalsotellingus a little bit about how MLFQs are real and used in real operating systems.
Take a tiny bit of time to figure out how you configure a scheduler in, for example, Linux.
Chapter 9: Scheduling: proportional share
• ThinkingabouttheproblemsthattheauthorsidentifiedwiththeMLFQ,what’sthemainprob- lem that fair-share scheduling is trying to solve?
• “every so often, hold a lottery to determine which process should get to run next; processes that should run more often should be given more chances to win the lottery.” — that sounds an awful lot like “higher priority”, and that sounds an awful lot like a “high priority queue” in a MLFQ. Can you convince yourself yet that there’s a difference?
9.1 Basic concept: Tickets represent your share
• Way outside the scope of this course: how much do you think the choice of source for random
numbers affects the performance of this kind of a scheduler?
COMP 3430 Operating systems – Chapter 7, 8, 9 reading notes Summer 2021
9.2 Ticket mechanisms
• Makesurethatyoucandistinguishherebetweena“user”anda“job”!
• I am not convinced about the utility of this idea of currencies. The idea is similar to real-life currency: USD (US dollars) and CAD (Canadian dollars) have a different value. One US family and one Canadian family go to England, and the parents send their kids to the mall (which only accepts GBP) with their own currencies. The kids then have to go to the money changer and get GBP. Each are allocated a certain proportion of USD and CAD, and that proportion is ultimately translated into GBP. But why is this a useful mechanism? The authors don’t really help us out with this.
• Tickettransferseemstomakelogicalsense(whenprocessesareworkingtogether,theythem- selves know more about what they need their peers to do than the scheduler itself could know). Can you think about any ways that ticket transfer could be gamed?
9.3 Implementation
• WhatkindofaworldarewelivinginwhenatextbooklinkstoStackoverflow????
• Ireallydon’tcareforthedesignofthisimplementation.Theauthorssayit’ssimple,thengoon to describe this overly complicated system that involves counting while stepping through a list. How would you design this policy?
9.4 An example
• Doesthewaythatfairnessiscalculatedheremakesense?We’recalculatingaratio,andsaying that (in this specific example) “the first job finished in half the time of the second job”. This makes sense when both jobs have the same runtime. Can you calculate fairness in this way when jobs have different runtimes?
9.5 How to assign tickets?
COMP 3430 Operating systems – Chapter 7, 8, 9 reading notes Summer 2021
9.6 Stride scheduling (note that this section is optional)
• Thisseemsverycomplicateddespitebeingdescribedas“straightforward”.Theimportantbits here are that we’re keeping track of how long each process has run globally compared to other processes. The code snippet on pg 6 does a pretty decent job of breaking down what actually happens to any individual job, combined with figure 9.3 on pg 7.
9.7 The Linux completely fair scheduler (CFS) (note that this section is optional)
• “…schedulingusesabout5%ofoveralldatacenterCPUtime.”Thisisoneofthosethingsthat’s weird to think about: The scheduler itself is just code (probably C) that someone has written, and actually runs on the CPU much in the same way that your programs do. With that in mind, it’s someone’s job to actually optimize schedulers to make them be faster, and therefore make sure that user programs (like ours) get to spend more time on the CPU.
• TheideaofcountinghowmuchtimeaprocesshasspentrunningontheCPUgoesalmostallthe way back to the beginning of this block of chapters. Thinking about the different approaches that you’ve seen so far (e.g., FCFS, SJF, round robin, MLFQ), which does CFS most closely resem- ble? Does it resemble a hybrid of any of these approaches?
Weighting (niceness)
• Sonicenessisn’tdirectlythepriorityofaprocess,butratheradviceaboutthepriorityofapro- cess. The advice is then mapped to a weight, then the weights are used to compute how much vruntime a process “consumes” (see equation 9.2 on pg 10).
Using red-black trees
• Thisisafun“Ican’tsleepandit’s3amandI’mboredandforsomereasonthinkingaboutdata structures and operating systems” kind of a problem: Actually measure the difference between using a red-black tree and a plain list to do lookups here. Of course, nobody is ever going to do think that, so nobody will ever do this, but…
– Plus: that we can make real statements about the efficiency of lists (𝑂(𝑛)) and balanced trees (𝑂(log(𝑛))) makes the effort to do this particularly worthless.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com