P3L1: Scheduling

Question 1

What is the role of the CPU scheduler?

Answer 1

The CPU scheduler decides how and when processes and threads access the CPU, i.e., how and when tasks are selected from the ready queue to run on the CPU.

Question 2

Does the CPU scheduler schedule user tasks, kernel tasks, or both?

Answer 2

Both

Question 3

What are four reasons why a task might be added to the ready queue?

Answer 3

1. An I/O operation the task has been waiting on has completed
2. The task has been woken from a wait
3. The task was just created, i.e., a new thread is created by forking
4. The task was ready, ran on the CPU until its timeslice expired, then was interrupted and put back on ready queue

Question 4

When is the CPU scheduler run?

Answer 4

Whenever the CPU becomes idle. This may be because a task completed, or was interrupted.

Question 5

What’s another name for the ready queue?

Answer 5

Run queue

Question 6

What happens when the CPU scheduler selects a task to be scheduled?

Answer 6

The task is dispatched to the CPU. This entails:

1. Context switch, entering the context of new task
2. Enter user mode
3. Set the program counter
4. Go!

Question 7

What are four good metrics for comparing CPU schedulers?

Answer 7

1. Throughput (# of processes executed)
2. Average job completion time
3. Average job wait time
4. CPU utilization (% of CPU resources used)

Question 8

For First-Come-First-Serve scheduling, what data structure should you use for the runqueue?

Answer 8

FIFO queue

Question 9

For Shortest-Job-First scheduling, what data structure should you use for the runqueue?

Answer 9

Ordered queue or a tree

Question 10

How do you calculate throughput?

Answer 10

jobs completed / time_to_complete_all_jobs

Question 11

How do you calculate average completion time?

Answer 11

sum_of_times_to_complete_each_job / jobs_completed

Question 12

How do you calculate average wait time?

Answer 12

sum_of_all_wait_times / jobs_completed

Wait time is the time from when process arrives until it begins executing

Question 13

For Shortest-Job-First scheduling, we need to estimate how long a job will take. What are two heuristics we might use?

Answer 13

1. How long did the job take last time?

2. How long did the job take, on average, over some previous window of time (say, the last n times the job ran)?

Question 14

What is “Run to Completion” scheduling?

Answer 14

Simply when jobs run to completion, i.e., they cannot be interrupted/preempted by the scheduler

Question 15

What is Preemptive scheduling?

Answer 15

When the scheduler can interrupt/preempt processes to run a different processes instead.

For example, a long process arrives first and starts executing. A shorter process arrives later. A “Shortest Job First” scheduler will preempt the long process and run the short process.

Question 16

What is Priority Scheduling?

Answer 16

Scheduling based on some priority level. OS tasks may be given higher priority than user tasks, or interactive user tasks may be given higher priority than background tasks.

Question 17

What are three data structures we could use to implement a runqueue when using a Priority Scheduler?

Answer 17

1. Ordered queue
2. Tree
3. Multiple queues, with each queue assigned a priority level.

Question 18

What is a danger of Priority Scheduling?

Answer 18

Starvation: Low priority tasks may never run

Question 19

How do we protect against starvation when using a Priority Scheduler?

Answer 19

Priority aging: As tasks wait to execute, their priority levels increase. In this case, priority is a function of both the primary priority measure and the age of the task.

Question 20

What is Priority Inversion?

Answer 20

Priority Inversion happens when a low priority job locks a mutex that is needed by a higher priority task, but is preempted by other tasks of intermediate priority.

Say we have P1, P2, and P3 with priorities ordered like P3 < P2 < P1. Also assume P1 and P3 need the same lock to complete.

If P3 arrives first and gets the lock, then is preempted by P2 arriving, P3 doesn’t get to complete. But it still has the lock! So when P1 arrives and tries to get the lock, it’s blocked. So P2 completes, followed by P3. Only then does P1 get the lock and run.

So we wind up with jobs completing in the order P2, P3, P1 (when we would have liked them to complete in order of priority, P1, P2, P3).

Question 21

How do we prevent Priority Inversion?

Answer 21

We can prevent priority inversion by temporarily boosting the priority of mutex owner so that it doesn’t get preempted. This allows it to complete earlier and allows any higher priority jobs that need the mutex to also complete earlier.

Question 22

Describe three variants of Round Robin Scheduling

Answer 22

• In all Round Robin Scheduling systems the process must be allowed to yield the CPU rather than being required to run to completion.
  1. Vanilla Round Robin: Tasks are scheduled first come first serve, but they don’t have to complete before yielding. They may instead yield when waiting, for example, on an I/O operation.
  2. Round Robin with Priority: Tasks are scheduled first come first serve unless a higher priority task arrives, in which case that is scheduled. This includes preemption.
  3. Round Robin with Interleaving: We give each task a timeslice in which it is allowed to run. When it reaches the end of the timeslice, it is interrupted and the next tasks starts.

Question 23

What is a timeslice?

Answer 23

Maximum amount of uninterrupted time given to a task (on the CPU). Also called “time quantum.”

Question 24

What do timeslices allow us to achieve?

Answer 24

Timeslices allow us to interleave CPU-bound tasks.

I/O-bound tasks are always giving up the CPU anyway, but for CPU-bound tasks we need the timeslice mechanism to interleave.

Question 25

What is a CPU-bound task?

Answer 25

A task whose completion time is primarily determined by the speed of the CPU. As opposed to IO-bound tasks, which often have to wait on IO processes.

Question 26

What are the pros and cons of Timeslice Scheduling?

Answer 26

Pros: - Short tasks finish sooner (like Shortest Job First) - More responsive - We can start long IO operations earlier and complete their corresponding tasks sooner Cons: - Overheads! Interrupting, scheduling, and context switching for a job all take time, and we'll do these more often with timeslice scheduling. However, as long as the timeslice length >= the time it takes to context switch, we can usually minimize overheads.

Question 27

What two concerns do we need to balance when deciding how long timeslices should be?

Answer 27

Starting jobs sooner (more responsive) vs. Overheads (context switching)

Question 28

Do CPU-bound tasks prefer a larger or smaller timeslice? Why?

Answer 28

Larger! We're not as worried about responsiveness with CPU-bound tasks, so reducing wait time isn't as much of a benefit. Larger timeslices minimize context-switching, which reduces average completion time and increases throughput.

Question 29

Do IO-bound tasks prefer larger or smaller timeslices?

Answer 29

IO bound tasks prefer a smaller timeslice. This allows IO operations to begin earlier, increasing throughput and reducing wait times.

Question 30

Describe the runqueue data structure we should use with Timeslice Scheduling

Answer 30

We want to use the Multi-Level Feedback Queue. This means: - We create multiple ready queues with different time slices, from shortest to longest. - Shorter time slices are for more IO bound tasks and longer timeslices for CPU bound tasks. - Jobs in the shortest timeslice queue run first! - We assign all new jobs to the shortest timeslice queue. - If a job uses its entire timeslice, we move it to the next queue, with a longer timesplice - If a job repeatedly yields the CPU before using its timeslice, we move it to the shorter timeslice queue This structure uses the behavior of tasks in real time to discover which are more IO bound/CPU bound. Won a Turing Award. Kind of a big deal.

Question 31

Describe the Linux O(1) scheduler

Answer 31

- A preemptive, priority-based scheduler that is able to select tasks in constant time regardless of task count - Tasks are organized into two categories: real-time and timesharing tasks. Real-time are higher priority and timesharing are lower. All User processes are timesharing tasks - Higher priority tasks get longer timeslices, lower priority get shorter timeslices - Uses SLEEP TIME to determine priority. Longer sleep implies interactive process, so longer sleep time gets jobs higher priority. Shorter sleep implies compute-intensive, so gets lower priority. - Maintains two arrays, one of Active Tasks and another of Expired Tasks. Each entry in an array is a list of tasks of the same priority. - Tasks are only moved from Active to Expired when they've consumed their entire timeslice. - Only tasks from Active array are scheduled - Once all Active tasks complete, the two arrays are switched.

Question 32

Why was the Linux O(1) scheduler replaced with the Completely Fair Scheduler?

Answer 32

Linux O(1) was replaced with CFS because workloads changed, beginning to include more time sensitive applications like streaming video. Linux O(1) wouldn't run expired jobs until all active jobs had a chance to execute for their entire timeslice, causing jitter. It also doesn't make any fairness guarantees

Question 33

Intuitively describe "fairness" in CPU scheduling

Answer 33

Over a given time interval, all tasks should be able to run for an amount of time proportional to their priority.

Question 34

Describe the Linux CFS scheduler

Answer 34

- Proposed to address fairness concerns in Linux O(1) - Default scheduler for non-Real Time tasks (Real Time Scheduler handles those) - Uses a Red-Black tree for runqueue data structure - Tasks are ordered in tree according to "virtual run time", with lower run time to left and higher to right - "Virtual Run Time" passes more quickly for lower priority tasks, more slowly for high priority tasks

Question 35

Describe the algorithm used by Completely Fair Scheduling

Answer 35

- Always pick the leftmost node (shortest virtual runtime) - While running, increment vruntime periodically and compare to leftmost vruntime - If smaller, keep running. If larger, preempt and place in tree based on vruntime - Start over Notes: - vruntime progress rate depends on priority and "niceness" - Low priority increment faster, high priority more slowly - This means the high priority runs longer Performance - Selecting a task is O(1) - Adding a task to tree is O(logN)

Question 36

What is a Red-Black tree?

Answer 36

A tree that rebalances itself whenever adding or removing nodes so that all the paths from the root to the leaves are roughly the same distance

Question 37

What is virtual runtime?

Answer 37

The amount of time a job spends running on the CPU

Question 38

What was the main reason the Linux O(1) scheduler was replaced with CFS?

Answer 38

Interactive tasks could wait unpredictable amounts of time to be scheduled

Question 39

What is cache affinity?

Answer 39

This is when we try to keep tasks on the same CPU as much as possible (which maintains a hot cache)

Question 40

How do we achieve cache affinity?

Answer 40

We get cache affinity by using a hierarchical scheduler architecture. - At the top level, a load balancer divides tasks among the CPUs - Then a per-CPU scheduler with a per-CPU runqueue repeatedly schedules tasks for that CPU

Question 41

How does the load balancer in a hierarchical scheduler choose to allocate tasks?

Answer 41

- First uses the length of runqueues on each CPU | - Then, if some CPU is idle, checks other CPUs for work that can be moved to the idle one

Question 42

What is Non-Uniform Memory Access?

Answer 42

In systems with multiple memory nodes, each memory node might be associated with a particular CPU or cluster of CPUs. All CPUs will be able to access this node, but the associated CPU will be able to access it faster.

Question 43

What is NUMA-aware scheduling?

Answer 43

NUMA = Non-Uniform Memory Access When tasks are bound to the CPU that is closest to the memory node that stores the state of those tasks.

Question 44

What is hyperthreading/simultaneous multithreading (SMT)?

Answer 44

CPUs can be built to have multiple sets of registers, each hosting a different thread. The threads still run one at a time, but context-switching between them is very cheap. Also called "chip multithreading" and "hardware multithreading".

Question 45

How does a CPU scheduler on a hyperthreading capable machine decide which threads to put on the same CPU?

Answer 45

By mixing compute-bound and memory-bound threads! If we put compute-bound threads together, they have to alternate. But they could both, ideally, run at every time t, so we're wasting time. This degrades performance and means that memory controller is idle If we put memory-bound threads together, we wind up with idle cycles (run one thread, then the other, then we wait for the first to finish its memory operation).

Question 46

How to identify CPU-bound vs. Memory-bound threads?

Answer 46

We use hardware counters that track cache misses, instructions per cycle (IPC), or power/energy usage, a few of them combined. This gives us a picture of the thread's resource needs. For example, repeated last-level cache misses might indicate that a thread's footprint doesn't fit in cache (memory-bound)

Question 47

Is cycles per instruction (CPI) helpful in identifying CPU-bound vs memory-bound threads, and therefore for hyperthreading scheduling?

Answer 47

Assuming a wide spread of distinct CPI values for different processes, yes. Mixing varying CPI values increases the instructions per cycle our CPU cores are able to execute. However! As it turns out, real threads don't have these distinct, widely spread-out values. So no, it doesn't work.