Scheduling Flashcards
when do scheduling decisions happen?
transitions to ready, waiting, terminated
non-preemptive on waiting/terminated only
goals of a scheduling algorithm
high throughput
low turnaround time
low response time
what’s throughput
of processes that finish per unit time
what’s turnaround time
length of time it takes for a process to finish
what’s response time
length of time between request and first response
what are the factors controlling throughput?
cpu/io device utilization
what controls turnaround/response time?
waiting time
what’s cpu utilization?
fraction of time CPU does productive work
what’s waiting time?
time each process waits in the ready queue
FCFS convoy effect?
a job with a long CPU burst prevents many shorter jobs after it from running
what is a consequence of the FCFS convoy effect?
no IO requests are issued, so there is poor IO device utilization
SJF
estimate the next CPU burst and run the process with the shortest one
what’s SRTF?
preemptive SJF scheme: if a process arrives with a shorter burst than the remaining current time, preempt the current process and run the new one
what does SJF optimize?
minimum average waiting time
minimum response time
disadvantage of SJF?
starves jobs with longer burst times
does not minimize avg turnaround time (long job of short bursts)
what’s RR?
pick a quantum and preempt processes that run for longer, moving to the back of a FIFO queue
advantages of RR?
fair allocation of CPU across all jobs
low avg waiting time w/ varying lengths
short jobs finish quickly
good responsiveness with few jobs
disadvantages of RR?
does worse than FCFS for same-sized jobs
context switch costs
direct costs of a context switch?
save/restore registers for syscall
switch address spaces i.e. page table
indirect costs of a context switch?
more misses in cache, TLB, file system’s buffer cache
what condition on the quantum minimizes avg turnaround time?
quantum geq most process times
what’s priority scheduling?
give each process a priority and run the highest priority process
what’s aging?
increasing the priority of a process as it waits to prevent starvation
what’s a multilevel feedback queue?
32 queues, run the highest priority queue with RR within each queue
load calculation?
avg length of run queue + short term sleep queue over last minute
if load is high…
priorities decay more slowly
if p_nice low (like -20)
priority decays more quickly
how to update p_estcpu for a sleeping process?
track sleep time and approximate decay ignoring p_nice and past loads
what’s affinity scheduling?
trying to keep threads on the same core
prevent load imbalance: cost benefit analysis when switching
what’s priority inversion?
a lower priority thread blocks a higher priority thread (e.g. L holds a mutex that H wants)
BVT runs…
the process with the lowest effective virtual time
context switch allowance motivation
too many context switches degrades performance
context switch allowance
run threads for C/w_i before preempting
SVT motivation
if a sleeping process wakes up, its A_i is low and starves other processes
A_i set to _ after _
A_i = max{A_i, SVT} after waking up from voluntary sleep
what’s the SVT defined as?
SVT = min{A_j} across all processes
why do we not SVT after involuntary sleep?
a faulting process needs a chance to catch up
what is a soft realtime thread?
a thread that must run every so often or performance degrades
warp factor calc?
E_i = A_i - (warp_i ? W_i : 0)
how do we prevent a buggy warped process from hogging?
L_i limits CPU time, sets warp_i to false if exceeded
what is U_i?
L_i gets reset every U_i time
lottery scheduling scheme
expected allocation of resources \propto # of tickets
tickets encapsulate resource rights that are
abstract, relative, uniform
ticket transfers are
explicit transfers of tickets from one client to another, used when a client blocks due a dependency
ticket inflation is
an alternative to ticket transfers, a client can escalate its resource rights by creating more tickets
ticket inflation should only be used
between mutually trusting clients
a currency
denotes a group of mutually trusting clients
inflation is locally contained within a currency
compensation tickets
are granted to clients that only consume a fraction of their allocated resource quantum
5.1 fairness
except 10:1, observed ratios are close to allocations
greater variance with larger ratios, but still converge over longer time intervals
5.2 flexible control
dynamically adjust ticket value
allows parallel monte carlo simulations to quickly reach an approximate answer
5.3 client-server
ticket allocations affect response time and throughput
5.4 multimedia
control quality of multiple video servers
distorted by X11’s RR processing
frame rates were close to allocated with -nodisplay
5.6 system overhead
tree-based lottery only generates a random number and performs lg n additions/comparisons to select a winner among n clients
