Scheduling

Question 1

when do scheduling decisions happen?

Answer 1

transitions to ready, waiting, terminated
non-preemptive on waiting/terminated only

Question 2

goals of a scheduling algorithm

Answer 2

high throughput
low turnaround time
low response time

Question 3

what’s throughput

Answer 3

of processes that finish per unit time

Question 4

what’s turnaround time

Answer 4

length of time it takes for a process to finish

Question 5

what’s response time

Answer 5

length of time between request and first response

Question 6

what are the factors controlling throughput?

Answer 6

cpu/io device utilization

Question 7

what controls turnaround/response time?

Answer 7

waiting time

Question 8

what’s cpu utilization?

Answer 8

fraction of time CPU does productive work

Question 9

what’s waiting time?

Answer 9

time each process waits in the ready queue

Question 10

FCFS convoy effect?

Answer 10

a job with a long CPU burst prevents many shorter jobs after it from running

Question 11

what is a consequence of the FCFS convoy effect?

Answer 11

no IO requests are issued, so there is poor IO device utilization

Question 12

SJF

Answer 12

estimate the next CPU burst and run the process with the shortest one

Question 13

what’s SRTF?

Answer 13

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

Question 14

what does SJF optimize?

Answer 14

minimum average waiting time
minimum response time

Question 15

disadvantage of SJF?

Answer 15

starves jobs with longer burst times
does not minimize avg turnaround time (long job of short bursts)

Question 16

what’s RR?

Answer 16

pick a quantum and preempt processes that run for longer, moving to the back of a FIFO queue

Question 17

advantages of RR?

Answer 17

fair allocation of CPU across all jobs
low avg waiting time w/ varying lengths
short jobs finish quickly
good responsiveness with few jobs

Question 18

disadvantages of RR?

Answer 18

does worse than FCFS for same-sized jobs
context switch costs

Question 19

direct costs of a context switch?

Answer 19

save/restore registers for syscall
switch address spaces i.e. page table

Question 20

indirect costs of a context switch?

Answer 20

more misses in cache, TLB, file system’s buffer cache

Question 21

what condition on the quantum minimizes avg turnaround time?

Answer 21

quantum geq most process times

Question 22

what’s priority scheduling?

Answer 22

give each process a priority and run the highest priority process

Question 23

what’s aging?

Answer 23

increasing the priority of a process as it waits to prevent starvation

Question 24

what’s a multilevel feedback queue?

Answer 24

32 queues, run the highest priority queue with RR within each queue

Question 25

load calculation?

Answer 25

avg length of run queue + short term sleep queue over last minute

Question 26

if load is high...

Answer 26

priorities decay more slowly

Question 27

if p_nice low (like -20)

Answer 27

priority decays more quickly

Question 28

how to update p_estcpu for a sleeping process?

Answer 28

track sleep time and approximate decay ignoring p_nice and past loads

Question 29

what's affinity scheduling?

Answer 29

trying to keep threads on the same core prevent load imbalance: cost benefit analysis when switching

Question 30

what's priority inversion?

Answer 30

a lower priority thread blocks a higher priority thread (e.g. L holds a mutex that H wants)

Question 31

BVT runs...

Answer 31

the process with the lowest effective virtual time

Question 32

context switch allowance motivation

Answer 32

too many context switches degrades performance

Question 33

context switch allowance

Answer 33

run threads for C/w_i before preempting

Question 34

SVT motivation

Answer 34

if a sleeping process wakes up, its A_i is low and starves other processes

Question 35

A_i set to _ after _

Answer 35

A_i = max{A_i, SVT} after waking up from voluntary sleep

Question 36

what's the SVT defined as?

Answer 36

SVT = min{A_j} across all processes

Question 37

why do we not SVT after involuntary sleep?

Answer 37

a faulting process needs a chance to catch up

Question 38

what is a soft realtime thread?

Answer 38

a thread that must run every so often or performance degrades

Question 39

warp factor calc?

Answer 39

E_i = A_i - (warp_i ? W_i : 0)

Question 40

how do we prevent a buggy warped process from hogging?

Answer 40

L_i limits CPU time, sets warp_i to false if exceeded

Question 41

what is U_i?

Answer 41

L_i gets reset every U_i time

Question 42

lottery scheduling scheme

Answer 42

expected allocation of resources \propto # of tickets

Question 43

tickets encapsulate resource rights that are

Answer 43

abstract, relative, uniform

Question 44

ticket transfers are

Answer 44

explicit transfers of tickets from one client to another, used when a client blocks due a dependency

Question 45

ticket inflation is

Answer 45

an alternative to ticket transfers, a client can escalate its resource rights by creating more tickets

Question 46

ticket inflation should only be used

Answer 46

between mutually trusting clients

Question 47

a currency

Answer 47

denotes a group of mutually trusting clients inflation is locally contained within a currency

Question 48

compensation tickets

Answer 48

are granted to clients that only consume a fraction of their allocated resource quantum

Question 49

5.1 fairness

Answer 49

except 10:1, observed ratios are close to allocations greater variance with larger ratios, but still converge over longer time intervals

Question 50

5.2 flexible control

Answer 50

dynamically adjust ticket value allows parallel monte carlo simulations to quickly reach an approximate answer

Question 51

5.3 client-server

Answer 51

ticket allocations affect response time and throughput

Question 52

5.4 multimedia

Answer 52

control quality of multiple video servers distorted by X11's RR processing frame rates were close to allocated with -nodisplay

Question 53

5.6 system overhead

Answer 53

tree-based lottery only generates a random number and performs lg n additions/comparisons to select a winner among n clients