CS162 Operating Systems and Systems Programming Lecture 11
Scheduling 2:
Case Studies, Real Time, and Forward Progress
February 24, 2022 Prof. and http://cs162.eecs.Berkeley.edu
Copyright By PowCoder代写 加微信 powcoder
Recall: Scheduling
• Question: How is the OS to decide which of several tasks to take off a queue?
• Scheduling: deciding which threads are given access to resources from moment to moment
– Often, we think in terms of CPU time, but could also think about access to resources like network BW or disk access
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Scheduling Policy Goals/Criteria
• Minimize Response Time
– Minimize elapsed time to do an operation (or job)
– Response time is what the user sees:
» Time to echo a keystroke in editor
» Time to compile a program
» Real-time Tasks: Must meet deadlines imposed by World
• MaximizeThroughput
– Maximize operations (or jobs) per second
– Throughput related to response time, but not identical:
» Minimizing response time will lead to more context switching than if you only maximized throughput
– Two parts to maximizing throughput
» Minimize overhead (for example, context-switching) » Efficient use of resources (CPU, disk, memory, etc)
• Fairness
– Share CPU among users in some equitable way
– Fairness is not minimizing average response time:
» Better average response time by making system less fair
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Example of RR with Time Quantum = 20
Example: Process P1 53
Burst Time
The Gantt chart is:
Thus, Round- and Cons:
Waiting time for P2=(20-0)=20
0 20 28 48 68 88 108 112125 145153
P1=(68-20)+(112-88)=72
Better for short jobs, Fair (+) Context-switching time adds up for long jobs (-)
P3=(28-0)+(88-48)+(125-108)=85 P4=(48-0)+(108-68)=88
Average waiting time = (72+20+85+88)/4=661⁄4
Average completion time = (125+28+153+112)/4 = 1041⁄2
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall:What if we Knew the Future?
• Could we always mirror best FCFS?
• Shortest Job First (SJF):
– Run whatever job has least amount of computation to do
– Sometimes called “Shortest Time to Completion First” (STCF) • Shortest Remaining Time First (SRTF):
– Preemptive version of SJF: if job arrives and has a shorter time to completion than the remaining time on the current job, immediately preempt CPU
– Sometimes called “Shortest Remaining Time to Completion First” (SRTCF) • These can be applied to whole program or current CPU burst
– Idea is to get short jobs out of the system
– Big effect on short jobs, only small effect on long ones – Result is better average response time
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Example to illustrate benefits of SRTF
C’s C’s C’s I/O I/O I/O
• Three jobs:
– A, B: both CPU bound, run for week
C: I/O bound, loop 1ms CPU, 9ms disk I/O
– If only one at a time,C uses 90% of the disk,A or B could use 100% of the CPU
• With FCFS:
– Once A or B get in, keep CPU for two weeks
• What about RR or SRTF?
– Easier to see with a timeline
Joseph & Kubiatowicz CS162 © UCB Spring 2022
SRTF Example continued:
Disk Utilization:
9/201 ~ 4.5%
I/O CABAB… C
C’s C’s I/O I/O
C’s C’s I/O I/O
RR 100ms time slice
Disk Utilization: C’s
~90% but lots of I/O
RR 1ms time slice
Disk Utilization: 90%
Joseph & Kubiatowicz CS162 © UCB Spring 2022
SRTF Further discussion
• Starvation
– SRTF can lead to starvation if many small jobs! – Large jobs never get to run
• Somehow need to predict future – How can we do this?
– Some systems ask the user
» When you submit a job, have to say how long it will take
» To stop cheating, system kills job if takes too long
– But: hard to predict job’s runtime even for non-malicious users
• Bottom line, can’t really know how long job will take
– However, can use SRTF as a yardstick for measuring other policies
– Optimal, so can’t do any better • SRTF Pros & Cons
– Optimal (average response time) (+) – Hard to predict future (-)
– Unfair (-)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Predicting the Length of the Next CPU Burst
• Adaptive: Changing policy based on past behavior
– CPU scheduling, in virtual memory, in file systems, etc – Works because programs have predictable behavior
» If program was I/O bound in past, likely in future » If computer behavior were random, wouldn’t help
• Example: SRTF with estimated burst length
– Use an estimator function on previous bursts:
Let tn-1, tn-2, tn-3, etc. be previous CPU burst lengths. Estimate next burst τn = f(tn-1, tn-2, tn-3, …)
– Function f could be one of many different time series estimation schemes (Kalman filters, etc)
– For instance, exponential averaging τn = αtn-1+(1-α)τn-1
with (0<α≤1)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Lottery Scheduling
• Yet another alternative: Lottery Scheduling
– Give each job some number of lottery tickets
– On each time slice, randomly pick a winning ticket
– On average, CPU time is proportional to number of tickets given to each job
• How to assign tickets?
– To approximate SRTF, short running jobs get more, long running jobs get fewer – To avoid starvation, every job gets at least one ticket (everyone makes progress)
• Advantage over strict priority scheduling: behaves gracefully as load changes
– Adding or deleting a job affects all jobs proportionally, independent of how many tickets each job possesses
2/24/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 11.10
Lottery Scheduling Example (Cont.)
• Lottery Scheduling Example
– Assume short jobs get 10 tickets, long jobs get 1 ticket
# short jobs/ # long jobs
% of CPU each short jobs gets
% of CPU each long jobs gets
– What if too many short jobs to give reasonable response time? » If load average is 100, hard to make progress
» One approach: log some user out
Joseph & Kubiatowicz CS162 © UCB Spring 2022
How to Evaluate a Scheduling algorithm?
• Deterministic modeling
– takes a predetermined workload and compute the performance of each algorithm for that workload
• Queueing models
– Mathematical approach for handling stochastic workloads
• Implementation/Simulation:
– Build system which allows actual algorithms to be run against actual data
– Most flexible/general
Joseph & Kubiatowicz CS162 © UCB Spring 2022
How to Handle Simultaneous Mix of Diff Types of Apps?
• Consider mix of interactive and high throughput apps:
– How to best schedule them?
– How to recognize one from the other?
» Do you trust app to say that it is “interactive”?
– Should you schedule the set of apps identically on servers, workstations, pads, and cellphones?
• For instance, is Burst Time (observed) useful to decide which application gets CPU time?
– Short Bursts ⇒ Interactivity ⇒ High Priority?
• Assumptions encoded into many schedulers:
– Apps that sleep a lot and have short bursts must be interactive apps – they should get high priority
– Apps that compute a lot should get low(er?) priority, since they won’t notice intermittent bursts from interactive apps
• Hard to characterize apps:
– What about apps that sleep for a long time, but then compute for a long time? – Or, what about apps that must run under all circumstances (say periodically)
Weighted toward small bursts
2/24/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 11.13
Multi-Level Feedback Scheduling
Long-Running Compute Tasks Demoted to Low Priority
• Another method for exploiting past behavior (first use in CTSS)
– Multiple queues, each with different priority
» Higher priority queues often considered “foreground” tasks
– Each queue has its own scheduling algorithm
» e.g. foreground – RR, background – FCFS
» Sometimes multiple RR priorities with quantum increasing exponentially (highest:1ms, next: 2ms, next: 4ms, etc)
• Adjust each job’s priority as follows (details vary)
– Job starts in highest priority queue
– If timeout expires, drop one level
– If timeout doesn’t expire, push up one level (or to top)
2/24/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 11.14
Scheduling Details
Long-Running Compute Tasks Demoted to Low Priority
• Result approximates SRTF:
– CPU bound jobs drop like a rock
– Short-running I/O bound jobs stay near top
• Scheduling must be done between the queues
– Fixed priority scheduling:
» serve all from highest priority, then next priority, etc.
– Time slice:
» each queue gets a certain amount of CPU time » e.g., 70% to highest, 20% next, 10% lowest
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Scheduling Details
Long-Running Compute Tasks Demoted to Low Priority
• Countermeasure: user action that can foil intent of the OS designers
– For multilevel feedback, put in a bunch of meaningless I/O to keep job’s priority high – Of course, if everyone did this, wouldn’t work!
• Example of Othello program:
– Playing against competitor, so key was to do computing at higher priority the competitors.
» Put in printf’s, ran much faster!
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Case Study: Linux O(1) Scheduler
Kernel/Realtime Tasks
User Tasks
• Priority-based scheduler: 140 priorities
– 40 for “user tasks” (set by “nice”), 100 for “Realtime/Kernel” – Lower priority value ⇒ higher priority (for realtime values) – Highest priority value ⇒ Lower priority (for nice values)
– All algorithms O(1)
» Timeslices/priorities/interactivity credits all computed when job finishes time slice » 140-bit bit mask indicates presence or absence of job at given priority level
• Two separate priority queues: “active” and “expired”
– All tasks in the active queue use up their timeslices and get placed on the expired queue, after which queues swapped
• Timeslice depends on priority – linearly mapped onto timeslice range
– Like a multi-level queue (one queue per priority) with different timeslice at each level
– Execution split into “Timeslice Granularity” chunks – round robin through priority
2/24/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 11.17
Linux O(1) Scheduler
•Lots of ad-hoc heuristics
–Try to boost priority of I/O-bound tasks
–Try to boost priority of starved tasks
Joseph & Kubiatowicz CS162 © UCB Spring 2022
O(1) Scheduler Continued
• Heuristics
– User-task priority adjusted ±5 based on heuristics
» p->sleep_avg = sleep_time – run_time
» Higher sleep_avg ⇒ more I/O bound the task, more reward (and vice versa)
– Interactive Credit
» Earned when a task sleeps for a “long” time
» Spend when a task runs for a “long” time
» IC is used to provide hysteresis to avoid changing interactivity for temporary changes in behavior
– However,“interactive tasks” get special dispensation
» To try to maintain interactivity
» Placed back into active queue, unless some other task has been starved for too long…
• Real-TimeTasks
– Always preempt non-RT tasks
– No dynamic adjustment of priorities – Scheduling schemes:
» SCHED_FIFO: preempts other tasks, no timeslice limit
» SCHED_RR: preempts normal tasks, RR scheduling amongst tasks of same priority
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Administrivia
• Midterm I graded:
– Mean 47.8, Std Dev: 12.8, Low: 17.5, High: 83.0
– Regrade requests before Sunday » We will take reasonable arguments for regrades..!
• Solutions are posted
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Administrivia (Con’t)
• Project 1 final report is due Tuesday March 1st • Also due Tuesday March 1st: Peer evaluations
– These are a required mechanism for evaluating group dynamics – Project scores are a zero-sum game
» In the normal/best case, all partners get the same grade
» In groups with issues, we may take points from non-participating group members and give them to participating group members!
• How does this work?
– You get 20 points/partner to distribute as you want: Example—4 person group, you get 3 x 20 = 60 points
» If all your partners contributed equally, give the 20 points each » Or, you could do something like:
• 22 points partner 1 • 22 points partner 2 • 16 points partner 3
– DO NOT GIVE YOURSELF POINTS!
» You are NOT an unbiased evaluator of your group behavior
Joseph & Kubiatowicz CS162 © UCB Spring 2022
So, Does the OS Schedule Processes or Threads?
• Many textbooks use the “old model”—one thread per process
• Usually it’s really: threads (e.g., in Linux)
• One point to notice: switching threads vs. switching processes incurs different costs:
– Switch threads: Save/restore registers
– Switch processes: Change active address space too! » Expensive
» Disrupts caching
• Recall, However: Simultaneous Multithreading (or “Hyperthreading”)
– Different threads interleaved on a cycle-by-cycle basis and can be in different processes (have different address spaces)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Multi-Core Scheduling
• Algorithmically, not a huge difference from single-core scheduling
• Implementation-wise, helpful to have per-core scheduling data structures – Cache coherence
• Affinity scheduling: once a thread is scheduled on a CPU, OS tries to reschedule it on the same CPU
– Cache reuse
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Spinlocks for multiprocessing
• Spinlock implementation:
int value = 0; // Free
Acquire() {
while (test&set(&value)) {}; // spin while busy
Release() {
value = 0; // atomic store
• Spinlock doesn’t put the calling thread to sleep—it just busy waits
– When might this be preferable?
» Waiting for limited number of threads at a barrier in a multiprocessing (multicore) program » Wait time at barrier would be greatly increased if threads must be woken inside kernel
• Every test&set() is a write, which makes value ping-pong around between core-local caches (using lots of memory!)
– So – really want to use test&test&set() !
• As we discussed in Lecture 8, the extra read eliminates the ping-ponging issues:
// Implementation of test&test&set(): Acquire() {
while(value); // wait until might be free
} while (test&set(&value)); // exit if acquire lock
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Gang Scheduling and Parallel Applications
• When multiple threads work together on a multi-core system, try to schedule them together
– Makes spin-waiting more efficient (inefficient to spin-wait for a thread that’s suspended)
• Alternative: OS informs a parallel program how many processors its threads are scheduled on (Scheduler Activations)
– Application adapts to number of cores that it has scheduled
– “Space sharing” with other parallel programs can be more efficient, because parallel speedup is often sublinear with the number of cores
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Real-Time Scheduling
• Goal: Predictability of Performance!
– We need to predict with confidence worst case response times for systems!
– In RTS, performance guarantees are:
» Task- and/or class centric and often ensured a priori
– In conventional systems, performance is:
» System/throughput oriented with post-processing (… wait and see …)
– Real-time is about enforcing predictability, and does not equal fast computing!!! • Hard real-time: for time-critical safety-oriented systems
– Meet all deadlines (if at all possible)
– Ideally: determine in advance if this is possible
– Earliest Deadline First (EDF), Least Laxity First (LLF),
Rate-Monitonic Scheduling (RMS), Deadline Monotonic Scheduling (DM)
• Soft real-time: for multimedia
– Attempt to meet deadlines with high probability – Constant Bandwidth Server (CBS)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Example:Workload Characteristics
• Tasks are preemptable, independent with arbitrary arrival (=release) times • Tasks have deadlines (D) and known computation times (C)
• Example Setup:
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 11.27
Example: Round- Doesn’t Work
2/24/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 11.28
Earliest Deadline First (EDF)
2/24/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022
EDF Feasibility Testing
2/24/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 11.30
Ensuring Progress
• Starvation: thread fails to make progress for an indefinite period of time
• Starvation (this lecture) ≠ Deadlock (next lecture) because starvation could resolve under right circumstances
– Deadlocks are unresolvable, cyclic requests for resources
• Causes of starvation:
– Scheduling policy never runs a particular thread on the CPU
– Threads wait for each other or are spinning in a way that will never be resolved
• Let’s explore what sorts of problems we might encounter and how to avoid them…
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Strawman: Non-Work-Conserving Scheduler
• A work-conserving scheduler is one that does not leave the CPU idle when there is work to do
• A non-work-conserving scheduler could trivially lead to starvation
• In this class, we’ll assume that the scheduler is work-conserving (unless stated otherwise)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Strawman: Last-Come, First-Served (LCFS)
• Stack (LIFO) as a scheduling data structure – Late arrivals get fast service
– Early ones wait – extremely unfair
– In the worst case – starvation
• When would this occur?
– When arrival rate (offered load) exceeds service rate (delivered load) – Queue builds up faster than it drains
• Queue can build in FIFO too, but “serviced in the order received”…
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Is FCFS Prone to Starvation?
Scheduled Task (process, thread)
• If a task never yields (e.g., goes into an infinite loop), then other tasks don’t get to run
• Problem with all non-preemptive schedulers…
• And early personal OSes such as original MacOS,Windows 3.1, etc
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 11.34
Scheduling Queue
Is Round Robin (RR) Prone to Starvation?
• Each of N processes gets ~1/N of CPU (in window)
– With quantum length Q ms, process waits at most (N-1)*Q ms to run again
– So a process can’t be kept waiting indefinitely
• So RR is fair in terms of waiting time
– Not necessarily in terms of throughput… (if you give up your time slot early, you don’t get the time back!)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Is Priority Scheduling Prone to Starvation?
Priority 3
Priority 2
Priority 1
Priority 0
• Recall: Priority Scheduler always runs the thread with highest priority
– Low priority thread might never run! – Starvation…
• But there are more serious problems as well…
– Priority inversion: even high priority threads might become starved
2/24/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022
Priority Inversion
Priority 3
Priority 2
Priority 1
• At this point, which job does the scheduler choose?
• Job 3 (Highest priority)
Joseph & Kubiatowicz CS162 © UCB Sp
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com