Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

350 > Scheduling > Flashcards

Scheduling Flashcards

1
Q

when do scheduling decisions happen?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

goals of a scheduling algorithm

A

high throughput
low turnaround time
low response time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

what’s throughput

A

of processes that finish per unit time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

what’s turnaround time

A

length of time it takes for a process to finish

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

what’s response time

A

length of time between request and first response

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

what are the factors controlling throughput?

A

cpu/io device utilization

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

what controls turnaround/response time?

A

waiting time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

what’s cpu utilization?

A

fraction of time CPU does productive work

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

what’s waiting time?

A

time each process waits in the ready queue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

FCFS convoy effect?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

what is a consequence of the FCFS convoy effect?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

SJF

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

what’s SRTF?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

what does SJF optimize?

A

minimum average waiting time
minimum response time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

disadvantage of SJF?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

what’s RR?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

advantages of RR?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

disadvantages of RR?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

direct costs of a context switch?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

indirect costs of a context switch?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

what condition on the quantum minimizes avg turnaround time?

A

quantum geq most process times

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

what’s priority scheduling?

A

give each process a priority and run the highest priority process

23
Q

what’s aging?

A

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

24
Q

what’s a multilevel feedback queue?

A

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

25
Q

load calculation?

A

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

26
Q

if load is high…

A

priorities decay more slowly

27
Q

if p_nice low (like -20)

A

priority decays more quickly

28
Q

how to update p_estcpu for a sleeping process?

A

track sleep time and approximate decay ignoring p_nice and past loads

29
Q

what’s affinity scheduling?

A

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

30
Q

what’s priority inversion?

A

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

31
Q

BVT runs…

A

the process with the lowest effective virtual time

32
Q

context switch allowance motivation

A

too many context switches degrades performance

33
Q

context switch allowance

A

run threads for C/w_i before preempting

34
Q

SVT motivation

A

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

35
Q

A_i set to _ after _

A

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

36
Q

what’s the SVT defined as?

A

SVT = min{A_j} across all processes

37
Q

why do we not SVT after involuntary sleep?

A

a faulting process needs a chance to catch up

38
Q

what is a soft realtime thread?

A

a thread that must run every so often or performance degrades

39
Q

warp factor calc?

A

E_i = A_i - (warp_i ? W_i : 0)

40
Q

how do we prevent a buggy warped process from hogging?

A

L_i limits CPU time, sets warp_i to false if exceeded

41
Q

what is U_i?

A

L_i gets reset every U_i time

42
Q

lottery scheduling scheme

A

expected allocation of resources \propto # of tickets

43
Q

tickets encapsulate resource rights that are

A

abstract, relative, uniform

44
Q

ticket transfers are

A

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

45
Q

ticket inflation is

A

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

46
Q

ticket inflation should only be used

A

between mutually trusting clients

47
Q

a currency

A

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

48
Q

compensation tickets

A

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

49
Q

5.1 fairness

A

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

50
Q

5.2 flexible control

A

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

51
Q

5.3 client-server

A

ticket allocations affect response time and throughput

52
Q

5.4 multimedia

A

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

53
Q

5.6 system overhead

A

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

350 (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions