P3L1 - Scheduling

Question 1

What is the role of the CPU Scheduler?

Answer 1

To decide how and when the processes (and their threads) access the shared CPUs

Question 2

T/F: Scheduler concerns itself with both user level tasks and kernel level tasks

Answer 2

True!

Question 3

When do you need to run the scheduler?

Answer 3

Whenever the CPU becomes idle

Question 4

What is a common amount of time given to a task?

Answer 4

Timeslice

Question 5

What are the steps that occur when the scheduler selects a task to be scheduled?

Answer 5

1. Switch to new task
2. Enter user mode
3. Set program counter
4. Execution begins!

Question 6

What is the structure of the ready queue known as?

Answer 6

runqueue

Question 7

_____ scheduling assumes that once a task is assigned to a CPU, it will run on that CPU until its finished

Answer 7

Run to Completion

Question 8

What are some common metrics for comparing schedulers?

Answer 8

1. Throughput
2. Average job completion time
3. Average job wait time
4. CPU utilization

Question 9

_____ algorithm has tasks scheduled in the order in which they arrive?

Answer 9

First come First serve (FCFS)

Question 10

What is an alternative to using execution time when choosing tasks to schedule?

Answer 10

Priority levels

Question 11

When scheduling based on priority levels, which task should run first?

Answer 11

The task with the highest priority level

Question 12

What is an effective way to be able to quickly tell a task’s priority

Answer 12

Maintain a separate runqueue for each priority level

Question 13

What is one dangerous situation that can occur with priority scheduling?

Answer 13

Starvation

Question 14

What is starvation in the context of scheduling?

Answer 14

When low priority tasks are essentially never scheduled because higher priority tasks continually enter the system and take precedence

Question 15

What is one mechanism to protect against starvation?

Answer 15

Priority aging - The priority of a task is not just the numerical property but a function of the actual priority and the amount of time the task has spent in the runqueue

Question 16

What is priority inversion?

Answer 16

When the highest priority task that SHOULD run cannot run because the lowest priority task is holding a mutex it needs

Question 17

What is one way to combat priority inversion?

Answer 17

Temporarily boost the priority of the mutex owner long enough to allow it to complete

Question 18

Define a timeslice?

Answer 18

The maximum amount of uninterrupted time that can be given to a task

Question 19

T/F: A task may run for a smaller amount of time than what the timeslice specifies?

Answer 19

True!

Question 20

What is one use of timeslices?

Answer 20

To allow tasks to be interleaved

Question 21

What are the downsides of timeslicing?

Answer 21

The overhead - We have to interrupt the running task, execute the scheduler ,and have to context switch to the new task

Question 22

How long should a timeslice be?

Answer 22

CPU intensive tasks –> Prefer longer timeslice values

I/O intensive tasks –> Prefer shorter timeslice values

Question 23

T/F: A runqueue data structure is only LOGICALLY a queue?

Answer 23

True! It can be implemented as multiple queues or even a tree

Question 24

____ is a structure that maintains multiple distinct queues, each differentiated by their timeslice values

Answer 24

Multi queue

Question 25

T/F: The topmost level of a multi queue has the larger timeslice value!

Answer 25

False! It holds the lowest

Question 26

How did the Linux O(1) Scheduler get its name?

Answer 26

It can add/select tasks in constant time regardless of the number of tasks in the system

Question 27

How many priority levels does the Linux O(1) scheduler have?

Answer 27

140 priority levels

Question 28

What are levels 0-99 used for in the Linux O(1) scheduler?

Answer 28

real time tasks

Question 29

What are levels 100-139 used for in the Linux O(1) scheduler?

Answer 29

timesharing tasks

Question 30

What is the feedback for the Linux O(1) scheduler?

Answer 30

How long a task spent sleeping during its timeslice

Question 31

How is the runqueue implemented for the Linux O(1) scheduler?

Answer 31

As two arrays - active and expired

Question 32

Which of the two arrays of the Linux O( 1) schedulers runqueue is used for selecting the next task to run?

Answer 32

Active

Question 33

What are some downsides of the Linux O(1) scheduler?

Answer 33

1. A task cannot run again until everything in the active array is complete
2. It makes no fairness guarantees

Question 34

What scheduler replaced the Linux O(1) scheduler?

Answer 34

The CFS (Completely Fair Scheduler)

Question 35

What type of data structure is used for the runquee for the CFS?

Answer 35

A red-black (self balancing) tree

Question 36

How are tasks ordered in the runqueue for CFS?

Answer 36

Based on amount of time that they spent running on the CPU - vruntime

Question 37

How long does selection take for CFS?

Answer 37

Constant time

Question 38

How long does addition take for CFS?

Answer 38

Log(# of tasks)

Question 39

Describe a shared memory multiprocessor

Answer 39

Multiple CPUs each with their own private L1/L2 cache, as well as a LLC which may or may not be shared. Lastly there is a DRAM shared across CPU’s

Question 40

Describe a multicore system

Answer 40

Each CPU can have multiple internal cores each with its own private L1/L2 cache, a shared LLC and DRAM

Question 41

T/F: It makes sense to schedule tasks on CPUs close to memory holding their state?

Answer 41

True! Keeps the cache hot

Question 42

What is the scheduling type known as in which we keep tasks on the CPU closest to the memory node where their state is?

Answer 42

NUMA-aware scheduling

Question 43

What is hyperthreading?

Answer 43

CPU support for multiple execution contexts (2)

Question 44

How do we know if a thread is CPU bound or memory bound?

Answer 44

Use historic information like hardware counters that are updated as the processor executes and keep information about various aspects of execution

Question 45

Is CPI a good metric for informing scheduling decisions?

Answer 45

No, its more or less the same across applications

Question 46

If 4 CPU cores share a bus to memory, what is the worst possible CPI if all 4 cores issue a 4-cycle memory instruction at the same time?

Answer 46

16 for 4*4 cores. One of the instructions will have to wait in line for 12 cycles behind the other instructions before it gets its turn on the memory bus. So therefore it took 16 cycles before the memory instruction was completed.