P3L1

Question 1

3 Options for scheduler

Answer 1

1. Assign tasks immediately (FCFS)
2. Assign simple tasks first (SJF)
3. Assign complex tasks first

Question 2

FCFS

Answer 2

First Come First Serve (FIFO)

Question 3

SJF

Answer 3

Shortest Job First

Question 4

CPU Scheduler runs when

Answer 4

1. CPU become idles
2. New tasks become ready
3. timeslice expired timeout

Question 5

runqueue is equal to

Answer 5

scheduling algorithm

Question 6

“Run-to-completion” scheduling

Answer 6

No preemption

Question 7

Metrics for schedulers

Answer 7

throughput
avg job completion time
avg job wait time
cpu utilization

Question 8

Data structure for FCFS

Answer 8

Queue

Question 9

Data structure for SJF

Answer 9

Ordered queue or tree

Question 10

SJF + Preemption

Answer 10

heuristics based on history -> job running time

Question 11

Priority Scheduling

Answer 11

Run highest priority next

Question 12

Data structure(s) for Priority Scheduling

Answer 12

Queues for each priority

Tree with priority

Question 13

How to deal with Priority Scheduling Starvation

Answer 13

priority aging function (actual priority, time spent in run queue)

Question 14

What is Priority Invesion

Answer 14

Priorities inverted due to lock

Question 15

Solution to Priority Inversion

Answer 15

Temp boost priority of mutex owner, lower on release

Question 16

Round Robin Scheduing

Answer 16

Pick up first task from queue (task only yields to wait on I/O)

Question 17

Round Robin w/ Priorities

Answer 17

Include preemption

Question 18

Round Robin w/ interleaving

Answer 18

Timeslicing

Question 19

Timeslice

Answer 19

(aka Time Quantum)

maximum amount of uninterrupted time given to a task

Question 20

Advantages of timeslice

Answer 20

• Shorter tasks finish first
• More responsive
• Lengthy I/O ops initiated sooner

Question 21

Timeslice needs to be much greater than

Answer 21

context switch

Question 22

CPU bound tasks prefer

Answer 22

larger timeslices

Question 23

I/O Bound tasks prefer

Answer 23

smaller timeslices

Question 24

CPU Bound Timeslices

Answer 24

higher timeslices

a) limits context switching overheads
b) keeps CPU utilization and throughput high

Question 25

I/O Bound Timeslices

Answer 25

shorter timeslices a) I/O bound tasks can issue I/O ops earlier b) keeps CPU + device utilization high c) better user perceived performance

Question 26

Multi-Level Feedback Queue

Answer 26

1. task enters top most queue 2. if task yields voluntarily, stay 3. if task uses entire time slice, push down level

Question 27

Linux O(1) Scheduler

Answer 27

Constant time to select/add task - Pre-emptive, priority-based realtime (0-99) timesharing (100-139)

Question 28

Linux O(1) Scheduler Data Structures

Answer 28

Run queue == 2 array of tasks

Question 29

O(1) Active array

Answer 29

- used to pick next task to run | - tasks remain in queue until timeslice expires

Question 30

O(1) Expired array

Answer 30

- inactive list | - when no more tasks in active array, swap active and expired

Question 31

O(1) Feedback

Answer 31

sleep time: waiting/idling - longer sleep: interactive, priority -5 (boost) - smaller sleep: compute intensive, priority +5 (lowered)

Question 32

Linux CFS Scheduler

Answer 32

Completely Fair Scheduler

Question 33

Why CFS vs O(1)

Answer 33

O(1) - performance of interactive tasks suffered, lacked fairness

Question 34

CFS Data structure

Answer 34

Run queue == Red-Black Tree Ordered by virtual runtime (ns) vruntime == time spent on CPU

Question 35

CFS Scheduling

Answer 35

- always pick left-most node - periodically adjust vruntime - compare to leftmost vruntime - if smaller, continue running - if larger, pre-empt and place appropriately in the tree

Question 36

vruntime progress rate

Answer 36

depends on priority and niceness - rate faster for low priority - rate slower for high priority

Question 37

CFS Performance

Answer 37

O(1) for select | O(log N) for adding

Question 38

LLC

Answer 38

Last Level Cache

Question 39

SMP

Answer 39

Shared Memory Processor | Each CPU has LLC

Question 40

Multi-core Processor

Answer 40

Shared LLC

Question 41

NUMA

Answer 41

Non-Uniform Memory Access Platforms - multiple memory nodes - access to local mm node faster than access to remote

Question 42

HyperThreading

Answer 42

Multiple hardware-supported execution contexts

Question 43

Other names for HyperThreading

Answer 43

- hardware multithreading - Chip Multithreading (CMT) - Simultaneous Multithreading (SMT)

Question 44

SMT Memory loading

Answer 44

100 cycles

Question 45

SMT Optimal Mix

Answer 45

mix of CPU and memory-intensive threads - all component (CPU and memory) well utilized - avoid/limit content on processor

Question 46

Mechanisms to track SMT ctx_switches

Answer 46

- Hardware counters - L1, L2,... LLC misses - IPC (instructions retired) - Power and energy data - Software interface and tools - e.g. oprofile, Linux perf tool

Question 47

CPI

Answer 47

Cycle Per Instructions | - mixed CPI is good, but not realistic due to real world workloads