Scheduling

Question 1

What does a scheduler do? What are its main components? What happens when a task is scheduled?

Answer 1

Scheduler puts threads on the CPU for execution.
Has a run queue and scheduling algorithm
Steps: Perform context switch, Enter user mode, Set PC, Execute

Question 2

What is a ready queue and how do tasks end up there?

Answer 2

A ready queue is where tasks a ready to be put on the CPU. They end up there by:

1. Initiating an I/O request
2. Having their time slice on the CPU expire
3. Being forked by a parent thread
4. Initiated a wait

Question 3

What is run to completion scheduling?

Answer 3

Once a tasks has been scheduled on the CPU, it runs until completion

Question 4

What is First-Come-First-Served?

Answer 4

Tasks are scheduled onto CPU based on when it arrives. Use FIFO queue

Question 5

What is Shortest Job First?

Answer 5

Exactly what it sounds like, you can use an ordered queue or a tree

Question 6

What is preemptive scheduling?

Answer 6

Unlike run-to-completion scheduling, tasks can be interrupted. (SJF - if a shorter job enters the queue, interrupt current one)

Question 7

How does the scheduler know how long a task will take to run?

Answer 7

History, last run time, windowed average of last n times

Question 8

What is priority scheduling?

Answer 8

Run the task with the highest priority next - can use preemption if higher priority comes into the queue. Can have a queue for each priority level

Question 9

What is thread starvation?

Answer 9

When a lower priority task is stuck in the run queue because higher priority tasks keep showing up

Question 10

What is priority aging?

Answer 10

A technique used to combat thread starvation - set priority to some function of (assigned priority, time in queue)

Question 11

What is priority inversion?

Answer 11

When a lower priority thread holds a mutex needed by a higher priority thread. Higher priority thread will be kept waiting and lower thread will finish first

Question 12

How to combat priority inversion?

Answer 12

Temporarily boost the priority of mutex owner (the lower priority task) to match that of the thread that is waiting until mutex is released

Question 13

What is round-robin scheduling?

Answer 13

Every task gets an equal time slice and the scheduler places them on the CPU in order.

Question 14

Pros and Cons of RR Scheduling with time slices

Answer 14

+ shorter tasks finish sooner (w/o heuristics), more responsive, length I/O ops initiated sooner
- high overheads when timeslice expires

Question 15

How to choose a timeslice based on I/O vs CPU bound

Answer 15

Want time(context switching)&raquo_space; timeslice. CPU Bounds = want larger time slice, I/O Bound == smaller slices

Question 16

What data structure can we use to determine if a task is CPU or I/O bound and assign it an appropriate timeslice?

Answer 16

Use Multi-level Feedback Queue (MLFQ)

Question 17

What is a multi-level feedback queue?

Answer 17

Have different levels for different time slices. Tasks enter at smallest slice. If they don’t yield before the slice expires, they stay there, if they do yield, they move down

Question 18

Describe the O(1) Linux Scheduler

Answer 18

Has two priority level buckets (real time and user). Time slice based on priority, feedback based on how long it took to run in the past. Real time always has higher priority than user and gets longer slices. Longer wait times means the thread is more interactive, so gets longer timeslice in the future.

Question 19

Describe the run queue of the O(1) Scheduler

Answer 19

Has two run queues - active and expired. Tasks stay in active queue until their timeslices have completely expired (might take multiple runs). When there are no more tasks ini active array, the arrays are swapped.

Question 20

Why was the O(1) Scheduler replaced?

Answer 20

It did not work well for real time applications and as apps moved to more and more responsive tasking, the jittering became a problem

Question 21

What is the Completely Fair Scheduler (CFS)?

Answer 21

Scheduler for linux non-real time tasks. Based on vruntime. Red-black tree with tasks based on vruntime. Smallest runtime task gets scheduled on CPU. Once it’s no longer the smallest, switch it out for another. vruntime increases more slowly for higher priority based tasks

Question 22

Types of CPUs

Answer 22

Shared Memory Multiprocessor (SMP) - each CPU has its own private cache. LLC may or may not be shared by CPUs. Multi-core systems - CPU has internal cores with their own caches, LLC shared by all cores.

Question 23

Scheduling on multi-core systems

Answer 23

Want to maximize cache-affinity (keep tasks on same CPU to keep cache hot) - have individual run queue / scheduler

Question 24

What is hyperthreading?

Answer 24

Hardware support for multiple execution contexts - can switch threads more easily. Want to schedule a CPU bound and an I/O bound thread together

Question 25

How to make sure to schedule a CPU- and I/O Bound thread together (hyperthreading)

Answer 25

Use hardware counters - high CPI == memory bound, low CPI == CPU bound

Question 26

rewatch last couple of lectures

Answer 26

lecture