CS162

Operating Systems and

Systems Programming
Lecture 10

Scheduling (con’t)
February 25th, 202
Prof. John Kubiatowic
http://cs162.eecs.Berkeley.edu

Acknowledgments: Lecture slides are from the Operating Systems course

taught by John Kubiatowicz at Berkeley, with few minor updates/changes.
When slides are obtained from other sources, a reference will be noted on the
bottom of that slide, in which case a full list of references is provided on the last
slide.






0





 Recall: Scheduling

if ( readyThreads(TCBs) )
nextTCB = selectThread(TCBs)
run( nextTCB )
} else
run_idle_thread()
}

• Discussion of Scheduling:
– Which thread should run on the CPU next
• Scheduling goals, policie
• Look at a number of different schedulers

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 2

{

 Recall: Scheduling Policy Goals/Criteria

• Minimize Response Tim
– Minimize elapsed time to do an operation (or job
– Response time is what the user sees
» Time to echo a keystroke in edito
» Time to compile a progra
» Real-time Tasks: Must meet deadlines imposed by Worl
• Maximize Throughpu
– Maximize operations (or jobs) per secon
– Throughput related to response time, but not identical
» Minimizing response time will lead to more context switching than if you
only maximized throughpu
– Two parts to maximizing throughpu
» Minimize overhead (for example, context-switching
» Efficient use of resources (CPU, disk, memory, etc
• Fairnes
– Share CPU among users in some equitable wa
– Fairness is not minimizing average response time
» Better average response time by making system less fair
2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 3
s

 Recall: Example of RR with Time Quantum = 20

• Example: Process Burst Time
P 53
P 8
P 68
P 2
– The Gantt chart is:
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 28 48 68 88 108 112 125 145 153

– Waiting time for P1=(68-20)+(112-88)=7

P2=(20-0)=20
P3=(28-0)+(88-48)+(125-108)=85
P4=(48-0)+(108-68)=8
– Average waiting time = (72+20+85+88)/4=66¼
– Average completion time = (125+28+153+112)/4 = 104½
• Thus, Round-Robin Pros and Cons
– Better for short jobs, Fair (+)
2/25/2020
– Context-switching time adds up for long jobs (-)
Kubiatowicz CS162 ©UCB Fall 2020 4



4









:

2


 Comparisons between FCFS and Round Robin
• Assuming zero-cost context-switching time, is RR always better than
FCFS
• Simple example: 10 jobs, each take 100s of CPU time
RR scheduler quantum of 1s
All jobs start at the same tim
• Completion Times Job # FIFO RR
1 100 991
2 200 992
… … …
9 900 999
– Both RR and FCFS finish at10the same1000
time 1000
– Average response time is much worse under RR!
» Bad when all jobs same lengt
• Also: Cache state must be shared between all jobs with RR but can be
devoted to each job with FIF
– Total time for RR longer even for zero-cost switch!
2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 5
?



e



 Earlier Example with Different Time Quantum
P2 P4 P1 P3
Best FCFS: [8] [24] [53] [68]
0 8 32 85 153
Quantum P1 P2 P3 P4 Average
Best FCFS 32 0 85 8 31¼
Q=1 84 22 85 57 62
Q=5 82 20 85 58 61¼
Wai
Q=8 80 8 85 56 57¼
Time
Q = 10 82 10 85 68 61¼
Q = 20 72 20 85 88 66¼
Worst FCFS 68 145 0 121 83½
Best FCFS 85 8 153 32 69½
Q=1 137 30 153 81 100½
Q=5 135 28 153 82 99½
Completion
Q=8 133 16 153 80 95½
Time
Q = 10 135 18 153 92 99½
Q = 20 125 28 153 112 104½
Worst FCFS 121 153 68 145 121¾
2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 6
t

 Handling Differences in Importance: Strict Priority Scheduling

Priority 3 Job 1 Job 2 Job 3
Priority 2 Job 4
Priority 1
Priority 0 Job 5 Job 6 Job 7

• Execution Pla
– Always execute highest-priority runable jobs to completio
– Each queue can be processed in RR with some time-quantu
• Problems
– Starvation:
» Lower priority jobs don’t get to run because higher priority job
– Deadlock: Priority Inversio
» Not strictly a problem with priority scheduling, but happens when low priority task has
lock needed by high-priority tas
» Usually involves third, intermediate priority task that keeps running even though high-
priority task should be runnin
• How to fix problems
– Dynamic priorities – adjust base-level priority up or down based on heuristics
about interactivity, locking, burst behavior, etc…
2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 7
:

 Scheduling Fairness
• What about fairness
– Strict fixed-priority scheduling between queues is unfair (run
highest, then next, etc):
» long running jobs may never get CPU
» Urban legend: In Multics, shut down machine, found 10-year-
old job ⇒ Ok, probably not
– Must give long-running jobs a fraction of the CPU even when
there are shorter jobs to run
– Tradeoff: fairness gained by hurting avg response time!

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 8

?

 Scheduling Fairness
• How to implement fairness
– Could give each queue some fraction of the CPU
» What if one long-running job and 100 short-running ones?
» Like express lanes in a supermarket—sometimes express
lanes get so long, get better service by going into one of the
other lines
– Could increase priority of jobs that don’t get service
» What is done in some variants of UNIX
» This is ad hoc—what rate should you increase priorities?
» And, as system gets overloaded, no job gets CPU time, so
everyone increases in priority⇒Interactive jobs suffer

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 9

?

 Lottery Scheduling
• Yet another alternative: Lottery Schedulin
– Give each job some number of lottery tickets
– On each time slice, randomly pick a winning ticket
» NOTE: Not a “real” random number generator; instead
pseudo-random number generators can make sure that every
ticket picked once before repeating
– On average, CPU time is proportional to number of tickets
given to each job
• How to assign tickets
– To help with responsiveness, give short running jobs more
tickets, long running jobs get fewer ticket
– To avoid starvation, every job gets at least one ticket
(everyone makes progress)
• Advantage over strict priority scheduling: behaves gracefully as
load change
– Adding or deleting a job affects all jobs proportionally,
independent of how many tickets each job possesses
2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 10
s

 Lottery Scheduling Example (Cont.)

• Lottery Scheduling Exampl
– Assume short jobs get 10 tickets, long jobs get 1 ticket
# short jobs % of CPU each % of CPU each
# long jobs short jobs gets long jobs gets
1/1 91% 9%
0/2 N/A 50%
2/0 50% N/A
10/1 9.9% 0.99%
1/10 50% 5%
– 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
2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 11
/



 How to Evaluate a Scheduling algorithm?
• Deterministic modelin
– takes a predetermined workload and compute the performance
of each algorithm for that workload
• Queueing model
– Mathematical approach for handling stochastic workloads
• Implementation/Simulation
– Build system which allows actual algorithms to be run against
actual data – most flexible/general

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 12

s

 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 priorit
– Apps that compute a lot should get low(er?) priority, since they won’t notice
intermittent bursts from interactive app
• 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)

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 13

?

 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 d
– 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 CP
– Sometimes called “Shortest Remaining Time to Completion First”
(SRTCF
• These can be applied to whole program or current CPU burs
– Idea is to get short jobs out of the syste
– Big effect on short jobs, only small effect on long one
– Result is better average response time
2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 14
)



m

 Discussion
• SJF/SRTF are the best you can do at minimizing average response
tim
– Provably optimal (SJF among non-preemptive, SRTF among
preemptive
– Since SRTF is always at least as good as SJF, focus on SRT

• Comparison of SRTF with FCF

– What if all jobs the same length
» SRTF becomes the same as FCFS (i.e. FCFS is best can do if all jobs the
same length
– What if jobs have varying length
» SRTF: short jobs not stuck behind long ones

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 15

e

 Example to illustrate benefits of SRTF

A or B C

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/
– If only one at a time, C uses 90% of the disk, A or B could use 100%
of the CP
• With FCFS
– Once A or B get in, keep CPU for two week
• What about RR or SRTF
– Easier to see with a timeline

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 16



O

 SRTF Example continued:

Disk Utilization:
C A B 9/201
C ~ 4.5%

C’s RR 100ms time slice DiskC’sUtilization:

I/O ~90%I/O but lots of
CABAB… C wakeups!

RR 1ms time slice

C’s C’s
I/O I/O
Disk Utilization:
C A A A 90%

SRTF
C’s C’s
I/O I/O
2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 17

 SRTF Further discussion

• Starvatio
– SRTF can lead to starvation if many small jobs
– Large jobs never get to ru
• Somehow need to predict futur
– How can we do this?
– Some systems ask the use
» When you submit a job, have to say how long it will tak
» To stop cheating, system kills job if takes too lon
– But: hard to predict job’s runtime even for non-malicious user
• Bottom line, can’t really know how long job will tak
– However, can use SRTF as a yardstick
for measuring other policie
– Optimal, so can’t do any bette
• SRTF Pros & Con
– Optimal (average response time) (+
– Hard to predict future (-
– Unfair (-)

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 18

n



g

 Predicting the Length of the Next CPU Burst

• Adaptive: Changing policy based on past behavior
– CPU scheduling, in virtual memory, in file systems, et
– Works because programs have predictable behavio
» If program was I/O bound in past, likely in futur
» If computer behavior were random, wouldn’t hel
• Example: SRTF with estimated burst lengt
– 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)

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 19





)





e



r



 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 priorit
» Higher priority queues often considered “foreground” task
– Each queue has its own scheduling algorith
» e.g. foreground – RR, background – FCF
» 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 queu
– If timeout expires, drop one leve
– If timeout doesn’t expire, push up one level (or to top)

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 20





l

 Scheduling Details
Long-Running Compute
Tasks Demoted to
Low Priority

• Result approximates SRTF

– CPU bound jobs drop like a roc
– Short-running I/O bound jobs stay near to
• Scheduling must be done between the queue
– 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

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 21

:






 Scheduling Details
Long-Running Compute
Tasks Demoted to
Low Priority

• Countermeasure: user action that can foil intent of

the OS designer
– For multilevel feedback, put in a bunch of meaningless I/O to keep
job’s priority hig
– 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!

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 22

h








 Case Study: Linux O(1) Scheduler
Kernel/Realtime Tasks User Tasks

0 100 139
• Priority-based scheduler: 140 prioritie
– 40 for “user tasks” (set by “nice”), 100 for “Realtime/Kernel
– Lower priority value ⇒ higher priority (for nice values
– Highest priority value ⇒ Lower priority (for realtime values
– All algorithms O(1
» Timeslices/priorities/interactivity credits all computed when job finishes time slic
» 140-bit bit mask indicates presence or absence of job at given priority leve
• 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 swappe
• Timeslice depends on priority – linearly mapped onto timeslice rang
– Like a multi-level queue (one queue per priority) with different timeslice at
each leve
– Execution split into “Timeslice Granularity” chunks – round robin through
priority

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 23

l

 O(1) Scheduler Continued

• Heuristics
– User-task priority adjusted ±5 based on heuristic
» p->sleep_avg = sleep_time – run_tim
» Higher sleep_avg ⇒ more I/O bound the task, more reward (and vice versa
– Interactive Credi
» Earned when a task sleeps for a “long” tim
» Spend when a task runs for a “long” tim
» IC is used to provide hysteresis to avoid changing interactivity for temporary
changes in behavio
– However, “interactive tasks” get special dispensatio
» To try to maintain interactivit
» Placed back into active queue, unless some other task has been starved for too
long
• Real-Time Task
– Always preempt non-RT task
– No dynamic adjustment of prioritie
– Scheduling schemes
» SCHED_FIFO: preempts other tasks, no timeslice limi
» SCHED_RR: preempts normal tasks, RR scheduling amongst tasks of same
priority

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 24

…

 Linux Completely Fair Scheduler (CFS)

• First appeared in 2.6.23, modified in 2.6.2
• “CFS doesn't track sleeping time and doesn't use heuristics to
identify interactive tasks—it just makes sure every process gets a
fair share of CPU within a set amount of time given the number of
runnable processes on the CPU.
• Inspired by Networking “Fair Queueing
– Each process given their fair share of resource
– Models an “ideal multitasking processor” in which N processes
execute simultaneously as if they truly got 1/N of the processo
» Tries to give each process an equal fraction of the processo
– Priorities reflected by weights such that increasing a task’s priority by
1 always gives the same fractional increase in CPU time – regardless
of current priority

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 25

”

 Real-Time Scheduling (RTS)

• Efficiency is important but predictability is essential
– We need to predict with confidence worst case response times for system
– In RTS, performance guarantees are
» Task- and/or class centric and often ensured a prior
– 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-Tim
– Attempt to meet all deadline
– EDF (Earliest Deadline First), LLF (Least Laxity First),
RMS (Rate-Monotonic Scheduling), DM (Deadline Monotonic Scheduling
• Soft Real-Tim
– Attempt to meet deadlines with high probabilit
– Minimize miss ratio / maximize completion ratio (firm real-time
– Important for multimedia application
– CBS (Constant Bandwidth Server)

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 26

e



:

 Example: Workload Characteristics

• Tasks are preemptable, independent with arbitrary arrival (=release)

time
• Tasks have deadlines (D) and known computation times (C)
• Example Setup:

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 27

s

 Example: Round-Robin Scheduling Doesn’t Work

Time

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 28

 Earliest Deadline First (EDF)
• Tasks periodic with period P and computation C in each period: ( ,
) for each task
• Preemptive priority-based dynamic scheduling
– Each task is assigned a (current) priority based on how close the
absolute deadline is (i.e. +1 = + for each task!
– The scheduler always schedules the active task with the closest absolute
deadlin
T1 = (4,1)

T2 = (5,2)

T3 = (7,2)
0 5 10 15

∑( )
Schedulable when ≤1
𝑖
•
𝑖
𝑃
=1
𝑖
𝑖
𝑖
𝑖
𝑖
𝑖
𝐶
𝑃
𝐶
𝑖
2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 29
𝐷
𝐷
𝑃
𝑛
𝑡
𝑡
e

 Choosing the Right Scheduler

I Care About: Then Choose:

CPU Throughput FCFS

Avg. Response Time SRTF Approximation

I/O Throughput SRTF Approximation

Fairness (CPU Time) Linux CFS

Fairness – Wait Time to Round Robin

Get CPU
Meeting Deadlines EDF

Favoring Important Tasks Priority

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 30
 A Final Word On Scheduling
• When do the details of the scheduling policy and fairness really
matter
– When there aren’t enough resources to go around

• When should you simply buy a faster computer

– (Or network link, or expanded highway, or …
– One approach: Buy it when it will pay
for itself in improved response tim

Respons
time
» Perhaps you’re paying for worse response
time in reduced productivity, customer angst,

100%
etc
» Might think that you should buy a faster X
when X is utilized 100%, but usually, response
time goes to infinity as utilization⇒100%
Utilization
• An interesting implication of this curve
– Most scheduling algorithms work fine in the “linear” portion of the load
curve, fail otherwis
– Argues for buying a faster X when hit “knee” of curve

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 31

…













:



?

 Summary (1 of 2)
• Scheduling Goals
– Minimize Response Time (e.g. for human interaction
– Maximize Throughput (e.g. for large computations
– Fairness (e.g. Proper Sharing of Resources
– Predictability (e.g. Hard/Soft Realtime)
• Round-Robin Scheduling:
– Give each thread a small amount of CPU time when it executes; cycle
between all ready thread
– Pros: Better for short jobs
• Shortest Job First (SJF)/Shortest Remaining Time First (SRTF)
– Run whatever job has the least amount of computation to do/least
remaining amount of computation to d
– Pros: Optimal (average response time)
– Cons: Hard to predict future, Unfai
• Multi-Level Feedback Scheduling
– Multiple queues of different priorities and scheduling algorithm
– Automatic promotion/demotion of process priority in order to
approximate SJF/SRTF

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 32

:

 Summary (2 of 2)
• Lottery Scheduling
– Give each thread a priority-dependent number of tokens (short
tasks⇒more tokens
• Linux CFS Scheduler: Fair fraction of CP
– Approximates a “ideal” multitasking processo
• Realtime Schedulers such as ED
– Guaranteed behavior by meeting deadline
– Realtime tasks defined by tuple of compute time and perio
– Schedulability test: is it possible to meet deadlines with proposed set of
processes?

2/25/2020 Kubiatowicz CS162 ©UCB Fall 2020 33

)