Operating Systems CMPSC 473
CPU Virtualization – Scheduling
Lectures 13, 14: March 4, 9, 2021 Instructor: Bhuvan Urgaonkar
T1 T2 Time
A OS B OS A
Q1: what if the process does something undesirable here?
•
OS support
– Trap handlers, signal handling, saving priv. regs in PCB
– Virtual memory, page tables
• Hardware support
– Trap mechanism, CPU modes, saving unpriv. regs in stack
– MMU, TLB, page tables
T1 T2 Time
A OS B OS A
Q2: how does the OS get to start running here?
• OS support •
– Interrupt handlers, saving priv. regs in PCB
– Per-process kernel stack
Hardware support
– Interrupt mechanism, saving unpriv. regs in stack
T1 T2 Time
A OS B OS A
• OS support
– Saving (restoring) priv. regs in (from) PCB
• Hardware support
– Saving (restoring) unpriv. regs in (from) stack
Q3: how do we ensure that A resumes execution at T2 as if it had not been
taken off the CPU at T1?
T1 T2 T3 Time
A OS B OS A
Q4: How does the OS decide which process to run next?
• The CPU scheduler
Scheduling states of a process/thread
Lock Disk
Running Ready
Waiting
Timer interrupt
Lock Disk
Running
Ready Waiting
Lock Disk
Running Ready
Waiting
I/O system call
Lock Disk
Running
Ready Waiting
Lets pick the second process in the ready queue
OS (scheduler)
Lock Disk
Running
Ready Waiting
Administrative Matters
Administrative Matters
• Exam 1:
– During class on March 16
– Syllabus: lectures 1-14
– How to prepare?
• Go over all slides and accompanying textbook sections
• Go over all quizzes done in lectures
• Solve the “Sample Exam” available under Quizzes on Canvas (will be available soon after this lecture)
• Exam 1:
Administrative Matters
– Class will be divided into 7 sections each of which will take its exam using the assigned zoom session; each section will be proctored by one of the teaching staff
• Detailsforthcoming
– You will find the exam under “Quizzes” on Canvas. Many questions will be of the true/false or multiple choice/answer type. Some will require file uploads
• Forsometrue/falseormultiplechoice/answerproblems,wewillaskyouto provide a 1-2 sentence justification for your answer. Your justification needs to be on the right track for you to get points
• For multiple answer problems, you must choose ALL correct choices to get any points
• You may type your solution and upload the file. Alternatively, you may take a picture of your handwritten solution and upload the image
• Exam 1:
Administrative Matters
– Make sure you submit the exam on time, else you will get a 0
– Nomakeupexams–ifyoucan’ttaketheexam,talktomeabout alternatives (likely more work in a project)
– If you need extra time, make sure we know
Administrative Matters
• Duringtheexam:violatinganyofthefollowing=>0points
– YouwillbeaskedtosignthefollowingAcademicIntegrityStatementand Honor Code.
• This will be a closed-book and closed-notes exam. You are not permitted to access any “cheat sheets” or textbooks during the exam, and you are not allowed to search online for hints or clarifications. Please do not access the internet on any device during the exam. If we suspect you are in violation of these policies, we will file an academic integrity violation.
• In your exam, in the indicated box please type in a sentence saying “I have read the instructions for this exam and agree to abide by the honor code.”
– You are to keep your webcam on at all times so the proctor can see You are required to have a camera turned on from the start of the exam.
Administrative Matters
• During the exam
– Your video stream should ideally look like the image below
– (the proctor should be able to see you working on the exam).
– The proctor may also periodically ask you to share your screen and/or reorient your webcam.
– Please keep your computer volume up so that you can hear announcements.
– Muteyourselfduringtheexam.Ifyouhaveanyquestions,pleaseuse the Chat window in Zoom to type your question in plain text.
Quiz 14.1
• Whatistheschedulingstateofaprocessafteritissuesadisk read operation that will take several msec to be serviced?
– Ready
– Running
– Waiting/blocked – Terminated
– New
Quiz 14.2
• Can the single-level page table ever require less memory than a k-level page table (k > 1)?
– Never
– It always requires less memory
– Depends (on what?)
Quiz 14.3
• We have learnt that, in addition to the VPN->PPN translation, there is variety of other information stored in a page table: valid bit, permissions, kernel/user accessibility. Another similar piece of information is the so-called “dirty” bit which is set if a store occurs within a page. What benefit do you think this brings?
Quiz 14.4
• We have learnt that, in addition to the VPN->PPN translation, there is variety of other information stored in a page table: valid bit, permissions, kernel/user accessibility. Another similar piece of information is the so-called “dirty” bit which is set if a store occurs within a page. What do you think is the purpose of this bit?
• Beonthelookoutforevenmoresuchinformation,e.g., “reference” bits that are used by page replacement algorithms
Quiz 14.5
• Consider information stored within page tables other than address translation (permissions, reference, dirty, valid). Select all that apply for a k-level page table (k > 1):
– These bits need to be stored at each level
– These bits need to be stored only at level 1
– These bits need to be stored only at level k
Quiz 14.6 (advanced, not on syllabus)
• Whichofthefollowingistrueinasystemwithasoftware- managed TLB:
– TheCPUimplementsatrapforaTLBmiss
– TheOSimplementsatraphandlerforaTLBmiss – The OS decides which entries will reside in the TLB – TheOScanchoosetheformatofpagetableentries
Quiz 14.7 (advanced, not on syllabus)
• How can a process associate read-write-execute permissions with portions of its address space at a granularity finer than a page?
• PCB:
Aside: Linux data structures
https://elixir.bootlin.com/linux/latest/source/include/linux/sched.h – L649
• Kernel idle loop:
https://elixir.bootlin.com/linux/latest/source/kernel/sched/idle.c#L17 0
• Scheduler: …
• Context switching: …
•
CPU scheduler: important concerns
Optimization metric/criterion
• Latency metrics:
• Turnaround/completion time: time between when a “job” is submitted and when it finishes
• Response time: time between when a process desires the CPU and when it gets to run on the CPU
• Throughputmetrics:amountof“work”perunittime
• e.g., IPC
• e.g., # of requests or processes finishing per unit time
• “Fairness”
• Proportional-share
• Max-min
• Many others
• Combinationsofthese
• Overheadsofthealgorithmitself • Runtime and space complexity
• Overheads
– Picking the next process to run
– Process arrival, process departure
• Howdoesitdoforthesemetrics?
– Response time
– Throughput
– Fairness
• Pros:
– Simple to implement! Low overheads – Doeswellfor“batch”jobs
• When is it not a good scheduling algorithm?
FIFO/FCFS
Shortest-Job-First (SJF) Scheduling
• Associatewitheachprocessthelengthofitsnext CPU burst. Use these lengths to schedule the process with the shortest time
• SJFisoptimalforavg.waitingtime–gives minimum average waiting time for a given set of processes
– In class: Compute average waiting time for a simple example with FCFS and RR
– Exercise: Prove the optimality claimed above
Why Pre-emption is Necessary
• To improve CPU utilization
– Mostprocessesarenotreadyatalltimesduringtheirlifetimes – E.g.,thinkofatexteditorwaitingforinputfromthekeyboard – Also improves I/O utilization
• To improve responsiveness
– Many processes would prefer to receive CPU quickly when they need it
• Modern CPU schedulers are pre-emptive
SJF: Variations on the theme • Non-preemptive: once CPU given to the process it cannot be
preempted until completes its CPU burst – the SJF we already saw
• Preemptive: if a new process arrives with CPU length less than remaining time of current executing process, preempt
• This scheme is known as Shortest-Remaining-Time-First (SRTF) • Also called Shortest Remaining Processing Time (SRPT)
• Overheads?
• Compare using unordered linked list vs. ordered list vs. heap
• Why SJF/SRTF may not be practical
• CPU requirement of a process rarely known in advance
Round Robin (RR)
• EachprocessgetsasmallunitofCPUtime(time quantum), usually 1-10 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.
• If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units.
• Performance
– q large => FCFS
– q small => q must be large with respect to context switch, otherwise overhead is too high
Proportional-Share Schedulers
• A generalization of round robin
• Process Pi given a CPU weight wi > 0
• Theschedulerneedstoensurethefollowing
– forall i, j, |Ti(t1, t2)/Tj(t1,t2) – wi/wj| ≤ e
– Given Pi and Pj were backlogged during [t1,t2]
Lottery Scheduling
• Perhapsthesimplestproportional-sharescheduler
• Createlotteryticketsequaltothesumoftheweightsofall processes
• Draw a lottery ticket and schedule the process that owns that ticket
Lottery Scheduling Example
P1=6 P2=9
1 4 7 10 13 2 5 8 11 14 3 6 9 12 15
9
Schedule P2
Lottery Scheduling Example
P1=6 P2=9
1 4 7 10 13 2 5 8 11 14 3 6 9 12 15
3
Schedule P1
Lottery Scheduling Example
P1=6 P2=9
1 4 7 10 13 2 5 8 11 14 3 6 9 12 15
11
• As t ∞, processes will get their share (unless they were blocked a lot)
• Problem with Lottery scheduling: Only probabilistic guarantee
• What does the scheduler have to do
– When a new process arrives?
– When a process terminates?
Schedule P2
Lottery Scheduling
• Exercise:Calculatethetimecomplexityoftheoperations Lottery scheduling will involve
Multi-Level Feedback Queue (MLFQ)
• SeeChapter8ofOSTEP
• Optionalreading,notonsyllabus
• Very old idea, a great example of heuristics that
– Try to combine conflicting goals of good response times for interactive jobs and fairness
– Learn dynamically the nature of a job (whether it is interactive)
Interlude: the “big” ideas so far (and to come)
• Locality
• “Nofreelunch”
– Space-timetradeoffs
• Softwarevs.hardwareimplementationimplications
– Whenever possible, implement common work in h/w and leave specialized work to OS
• Use simple heuristics to “learn” workload properties and/or adapt to uncertainty
– Optimizeforthecommoncase
• Avoid context switching when possible