P3L1 Flashcards
3 Options for scheduler
- Assign tasks immediately (FCFS)
- Assign simple tasks first (SJF)
- Assign complex tasks first
FCFS
First Come First Serve (FIFO)
SJF
Shortest Job First
CPU Scheduler runs when
- CPU become idles
- New tasks become ready
- timeslice expired timeout
runqueue is equal to
scheduling algorithm
“Run-to-completion” scheduling
No preemption
Metrics for schedulers
throughput
avg job completion time
avg job wait time
cpu utilization
Data structure for FCFS
Queue
Data structure for SJF
Ordered queue or tree
SJF + Preemption
heuristics based on history -> job running time
Priority Scheduling
Run highest priority next
Data structure(s) for Priority Scheduling
Queues for each priority
Tree with priority
How to deal with Priority Scheduling Starvation
priority aging function (actual priority, time spent in run queue)
What is Priority Invesion
Priorities inverted due to lock
Solution to Priority Inversion
Temp boost priority of mutex owner, lower on release
Round Robin Scheduing
Pick up first task from queue (task only yields to wait on I/O)
Round Robin w/ Priorities
Include preemption
Round Robin w/ interleaving
Timeslicing
Timeslice
(aka Time Quantum)
maximum amount of uninterrupted time given to a task
Advantages of timeslice
- Shorter tasks finish first
- More responsive
- Lengthy I/O ops initiated sooner
Timeslice needs to be much greater than
context switch
CPU bound tasks prefer
larger timeslices
I/O Bound tasks prefer
smaller timeslices
CPU Bound Timeslices
higher timeslices
a) limits context switching overheads
b) keeps CPU utilization and throughput high
I/O Bound Timeslices
shorter timeslices
a) I/O bound tasks can issue I/O ops earlier
b) keeps CPU + device utilization high
c) better user perceived performance
Multi-Level Feedback Queue
- task enters top most queue
- if task yields voluntarily, stay
- if task uses entire time slice, push down level
Linux O(1) Scheduler
Constant time to select/add task
- Pre-emptive, priority-based
realtime (0-99)
timesharing (100-139)
Linux O(1) Scheduler Data Structures
Run queue == 2 array of tasks
O(1) Active array
- used to pick next task to run
- tasks remain in queue until timeslice expires
O(1) Expired array
- inactive list
- when no more tasks in active array, swap active and expired
O(1) Feedback
sleep time: waiting/idling
- longer sleep: interactive, priority -5 (boost)
- smaller sleep: compute intensive, priority +5 (lowered)
Linux CFS Scheduler
Completely Fair Scheduler
Why CFS vs O(1)
O(1) - performance of interactive tasks suffered, lacked fairness
CFS Data structure
Run queue == Red-Black Tree
Ordered by virtual runtime (ns)
vruntime == time spent on CPU
CFS Scheduling
- 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
vruntime progress rate
depends on priority and niceness
- rate faster for low priority
- rate slower for high priority
CFS Performance
O(1) for select
O(log N) for adding
LLC
Last Level Cache
SMP
Shared Memory Processor
Each CPU has LLC
Multi-core Processor
Shared LLC
NUMA
Non-Uniform Memory Access Platforms
- multiple memory nodes
- access to local mm node faster than access to remote
HyperThreading
Multiple hardware-supported execution contexts
Other names for HyperThreading
- hardware multithreading
- Chip Multithreading (CMT)
- Simultaneous Multithreading (SMT)
SMT Memory loading
100 cycles
SMT Optimal Mix
mix of CPU and memory-intensive threads
- all component (CPU and memory) well utilized
- avoid/limit content on processor
Mechanisms to track SMT ctx_switches
- Hardware counters
- L1, L2,… LLC misses
- IPC (instructions retired)
- Power and energy data
- Software interface and tools
- e.g. oprofile, Linux perf tool
CPI
Cycle Per Instructions
- mixed CPI is good, but not realistic due to real world workloads
