P3L1. Scheduling

Question 1

Name three ways an OS scheduler could choose to schedule tasks and the benefit of each.

Answer 1

1. Assign tasks immediately

• Benefit: Keeps scheduling simple
• Algorithm: First Come First Serve

2. Assign simple tasks first

• Benefit: Mazimize throughtput
• Algorithm: Shortest Job First

3. Assign complex tasks first

• Benefit: Maximize all aspects of the platform (utilization of CPU, devices, memory, etc)
• Algorithm: ?

Question 2

What does a CPU scheduler do?

Answer 2

• Decides how and when processes (and their threads) access shared CPUs.
• Schedules tasks running user-level processes/threads as well as kernel-level threads.

Question 3

When does the CPU scheduler run?

Answer 3

The CPU scheduler runs when:

• CPU becomes idle
• a new task becomes ready
• timeslice expired timeout

Question 4

What happens once the scheduler selects a thread to be scheduled onto the CPU?

Answer 4

The thread is dispatched onto the CPU:

• perform context switch
• enter user mode
• set program counter
• new thread starts executing

Question 5

How does the CPU scheduler choose which task should be run next? And how is this done?

Answer 5

Which task should be selected depends on the scheduling policy/algorithm.

How this is done depends on the runqueue data structure.

The runqueue data structure and the scheduling algorithm are tightly coupled. e.g., certain scheduling policies demand a certain runqueue data structure.

Question 6

What is “run-to-completion” scheduling?

Answer 6

This type of scheduling assumes that as soon as a task is assigned to a CPU it will run until it completes.

Question 7

What is First-Come First-Service (FCFS)?

What kind of runqueue data structure is needed to support it?

Pros/Cons?

Answer 7

Tasks are scheduled in the order of arrival.

To make a decision all the scheduler needs to know the head of the queue and how to dequeue tasks, so a FIFO queue would make a good runqueue data structure.

Pros:

• Simple

Cons:

• Wait time is poor even if there’s only one long task in the system that has arrived in front of other shorter tasks.

Question 8

Say we have a First-Come First-Servce (FCFS) policy with run-to-completion scheduling, and tasks T1, T2, and T2, which take 1 second, 10 seconds, and 1 second to run.

What is the throughput?

What is the average completion time?

What is the average wait time?

Answer 8

Throughput

3 tasks / 12 seconds = 0.25 tasks / second

Average Completion Time

(1 + 11 + 12) / 3 = 8 seconds

T1 completes after 1 second, T2 after 11 seconds, T3 after 12 seconds

Average Wait Time

(0 + 1 + 11) / 3 = 4 seconds

Question 9

What is Shortest Job First (SJF)?

What kind of runqueue data structure is needed to support it?

Pros/Cons?

Answer 9

Schedules tasks in order of their execution time.

The scheduler needs to know the tail of the queue, and also how to insert tasks in a specific order. We could use an ordered queue data structure or a tree where the leftmost node is always the shortest execution time.

Pros:

• TODO

Cons:

• TODO

Question 10

What is the formula for throughput?

Answer 10

jobs completed / time to complete all jobs

Question 11

What is the formula for average completion time?

Answer 11

sum of times to complete each job / jobs completed

Question 12

What is the formula for average wait time?

Answer 12

sum of time each job spent waiting / jobs completed

Question 13

What is preemptive scheduling?

Answer 13

This type of scheduling assumes that when a task is assigned to a CPU it can be interrupted so that another task can be scheduled.

Question 14

When scheduling jobs with the Shortest Job First (SJF) policy, how can the scheduler determine a task’s execution time?

Answer 14

The scheduler can use heuristics based on history of job running time.

• how long did a task run last time?
• how long did a task run last n times? (windowed average)

Question 15

What is Priority scheduling?

What kind of runqueue data structure is needed to support it?

Pros/Cons?

Answer 15

Tasks have different priority levels. The scheduler will run the highest priority task next.

We can support this by having a queue per priority (the scheduler just selects the next job off the appropriate queue) or we can use a tree ordered based on priority.

Pros:

• TODO

Cons:

• Starvation: low priority task stuck in runqueue. We can protect against this with “priority aging” where priority is a function of the task’s actual priority and the time spent in the run queue.

Question 16

What is priority inversion?

Give an example of how this could happen.

Answer 16

Priority inversion is a scenario in scheduling in which a high priority task is indirectly preempted by a lower priority task effectively inverting the relative priorities of the two tasks.

e.g., If the low priority task holds a lock that a higher priority task needs, the low priority task has to be scheduled first, inverting the priorities of the tasks.

Question 17

Say we have a low priority task that holds a lock that a high priority task needs. How can we ensure that the low priority task will run and release the lock soon so the high priority task can obtain the lock?

Answer 17

We can temporarily boost the priority of the mutex owner and then lower again after it releases the lock.

Question 18

What is Round Robin Scheduling?

Answer 18

• pick up first task form queue (like FCFS)
• task may yeild to wait on I/O (unlike FCFS)

Round Robin w/ priorities

• include preemption

Round Robin w/ interleaving

• timeslicing

Question 19

What is a timeslice (aka time quantum)?

Answer 19

The maximum amount of uninterrupted time given to a task.

Using timeslices allows tasks to be interleaved, timesharing the CPU. This is less important for I/O-bound tasks since they are constantly releasing the CPU but for CPU-bound tasks this is critical since it’s the only way we can achieve time sharing.

Question 20

What is Timeslice Scheduling?

Pros/Cons?

Answer 20

We run tasks for a maximum time = timeslice between switching to a new task.

Pros:

+ Shorter tasks finish sooner

+ More responsive

+ Lengthy I/O operations initiated sooner

Cons:

• Overhead (we have to interrupt task, invoke scheduler, context switch to new task) but we can minimize the overhead by ensuring timeslice is > context switch time

Question 21

How long should a timeslice be?

Answer 21

CPU-bound tasks prefer longer timeslices

• limits context switching overhead
• keeps CPU utilization and throughput high

I/O-bound tasks prefer shorter timeslices

• I/O-bound tasks can issue I/O operations earlier
• keeps CPU and device utilization high
• better user-perceived performance

Question 22

What is the formula for calculating CPU utilization?

Answer 22

Over a consistent, recurring interval:

sum of time tasks spend running on the CPU / sum of time tasks spent running on the CPU + sum of time spent context switching between tasks

Question 23

How do we avoid task starvation? (i.e., a task with a low priority never gets a chance to run b/c there are always higher priority tasks in the queue)

Answer 23

TODO

Question 24

How do we know if a task is CPU or I/O intensive?

How do we know how I/O intensive a task is?

Answer 24

• history based heuristics

Question 25

What is the Multi-Level Feedback Queue (MLFQ)?

Answer 25

Created by Fernando Corbato

We create a multi-level runtime queue and follow this algorithm:

1) When a task is first created we put it in the first queue, which has the smallest timeslice.
2) If the task yields voluntarily (e.g., I/O) then we keep it at this level, else if that task uses up the whole timeslice we push it to the next queue, which has a longer timeslice.
3) If a task in the second or third queue yields voluntarily then it gets a priority boost

MLFQ != Priority Queues

• different treatment of threads at each level
• incorporates feedback

Question 26

How does the Linux O(1) Scheduler Work?

Pros/Cons?

Answer 26

O(1) == constant time to select/add task, regardless of task count

premtive, priority-based

TODO

Pros:

• TODO

Cons:

• performance of interactive tasks (b/c tasks don’t get a chance to run again until all tasks on the active queue have run there’s often a “jitter”)
• no fairness guarantees

Question 27

How does the Linux Completely Fair Scheduler (CFS) work?

Pros/Cons?

Answer 27

TODO

Question 28

What is cache affinity and why is it important to CPU scheduling?

Answer 28

We want the OS scheduler to keep a task on the same CPU as much as possible so that the cache is more likely to be hot, which gives us a performance boost.

Question 29

What is a per-CPU runqueue & scheduler and why might it improve performance?

Answer 29

Load balance across CPUs based on queue lenght or CPU idle time.

Can improve cache affinity (liklihood that cache will be hot b/c we’re running the same task there multiple times instead of on a different cpu each time)

Question 30

What is NUMA and NUMA-aware scheduling?

Answer 30

Non-Uniform Memory Access

• multiple memory nodes
• memory node closer to a “socket” of multiple processors
• access to local memory node faster than access to remote memory node

NUMA-aware scheduling

• keep tasks on the CPU closer to memory node where their state is

Question 31

What is hyperthreading?

Answer 31

• multiple hardware-supported execution contexts
• still 1 CPU but context switching is very fast (b/c we just switch the register we use, no need to reload data)

Question 32

What are the pros/cons of co-scheduling compute and memory bound threads?

Answer 32

Pros:

• avoid/limit contention on processor pipeline
• all components (CPU and memory) well utilized

Cons:

• still leads to interference and degredation, but minimal

Question 33

How can we determine if a thread is CPU-bound or memory-bound?

Answer 33

Use historic information

“Sleep time” won’t work b/c the thread is not sleeping when waiting on a memory reference. Software takes too much time to compute so we need some hardware-level information

Instead, hardware counters can help the scheduler estimate the kind of resources a thread needs.