P3L1 Flashcards Preview

CS6200 Final > P3L1 > Flashcards

Flashcards in P3L1 Deck (47):
1

3 Options for scheduler

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

2

FCFS

First Come First Serve (FIFO)

3

SJF

Shortest Job First

4

CPU Scheduler runs when

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

5

runqueue is equal to

scheduling algorithm

6

"Run-to-completion" scheduling

No preemption

7

Metrics for schedulers

throughput
avg job completion time
avg job wait time
cpu utilization

8

Data structure for FCFS

Queue

9

Data structure for SJF

Ordered queue or tree

10

SJF + Preemption

heuristics based on history -> job running time

11

Priority Scheduling

Run highest priority next

12

Data structure(s) for Priority Scheduling

Queues for each priority
Tree with priority

13

How to deal with Priority Scheduling Starvation

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

14

What is Priority Invesion

Priorities inverted due to lock

15

Solution to Priority Inversion

Temp boost priority of mutex owner, lower on release

16

Round Robin Scheduing

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

17

Round Robin w/ Priorities

Include preemption

18

Round Robin w/ interleaving

Timeslicing

19

Timeslice

(aka Time Quantum)
maximum amount of uninterrupted time given to a task

20

Advantages of timeslice

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

21

Timeslice needs to be much greater than

context switch

22

CPU bound tasks prefer

larger timeslices

23

I/O Bound tasks prefer

smaller timeslices

24

CPU Bound Timeslices

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

25

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

26

Multi-Level Feedback Queue

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

27

Linux O(1) Scheduler

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

28

Linux O(1) Scheduler Data Structures

Run queue == 2 array of tasks

29

O(1) Active array

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

30

O(1) Expired array

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

31

O(1) Feedback

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

32

Linux CFS Scheduler

Completely Fair Scheduler

33

Why CFS vs O(1)

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

34

CFS Data structure

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

35

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

36

vruntime progress rate

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

37

CFS Performance

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

38

LLC

Last Level Cache

39

SMP

Shared Memory Processor
Each CPU has LLC

40

Multi-core Processor

Shared LLC

41

NUMA

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

42

HyperThreading

Multiple hardware-supported execution contexts

43

Other names for HyperThreading

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

44

SMT Memory loading

100 cycles

45

SMT Optimal Mix

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

46

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

47

CPI

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