Multitasking and Scheduling

Question 1

What are the three possible states of a process?

Answer 1

Ready, running and Blocked

Question 2

What does the scheduler decide

Answer 2

“The scheduler decides which process from the set of ready processes will get the CPU next”

Question 3

What is a context switch

Answer 3

A context switch is the name given when one process stores its state and “yeilds” for another process to execute

Question 4

What are the two reasons a context switch may take place

Answer 4

Pre-emptive switching where the OS choses to switch between processes
Interrupt driven switching where Hardware of Software Interrupts trigger a switch between processes

Question 5

What is the main issue with Context Switching

Answer 5

It has overhear, for a context switch to occur it needs to:

+ Save/restore program counter
+ Save/restore stack register(s)
+ Save/restore status register
+ Save/restore general purpose registers
+ Save/restore memory map
+ Save/restore I/O status ← outstanding requests
+ Invalidate Memory Cache
+ Invalidate Working set of pages

Question 6

What does the quantum in round-robin scheduling describe

Answer 6

The allowance of CPU time one process gets in one cycle

Question 7

What are the tradeoffs between Short and Long Quantum in round-robin scheduling

Answer 7

Long Quantum:
+ Long response time
+ Good Efficiency
Short Quantum:
+ Fast response time
+ High overhead from context switching

Question 8

What is the large drawback of lottery scheduling

Answer 8

There are no guarantees that a given process will get CPU timed as it uses random ticket selection

Question 9

What are the two different approaches to deadlines for real-time systems

Answer 9

Soft real-time systems such as multimedia controllers where its acceptable to be slightly off
Hard real-time systems where it’s not ok to be off at all

Question 10

What are the key features of RIOS

Answer 10

+ Minimalist but practical
+ Fixed priorites
+ Preemptive multitasking
+ Bounded stack usage
+ Small and understandable

Question 11

Where do tasks execute when scheduling with RIOS

Answer 11

Within interupt service routines

Question 12

What must we be careful about calling within RIOS tasks

Answer 12

We must be careful about calling non-rentrant functions within RIOS tasks, as these may be interrupted.

Say we need to use printf() in multiple places, we should create our own task which prints from a queue and is the only task using printf(), and then any function which wish to print should push to this.

Question 13

What is the deadline of a task

Answer 13

The latest time by which a task has to be completed

Question 14

What does it mean for a task to be periodic

Answer 14

It means that the task repeats itself at a regular interval of time

Question 15

What does it mean for a task to be aperiodic

Answer 15

It means that the task does have a regular interval of time between when it needs to be ran

Question 16

How can CPU Utilization be calculated (U), and what constraint always exists on this

Answer 16

U=C_total - C_idle <= 1

Where
- C_total is the total CPU time available, such as 100%
- C_idle is the Fraction of CPU time spent in idle task or sleeping

Question 17

What assumptions are made when analysing the scheduling of tasks

Answer 17

1. Tasks are periodic
2. The deadline for a task is its next invocation
3. Context switches take no time

Question 18

When analysing the scheduling of tasks, how do we handle Aperiodic tasks

Answer 18

We use polling, and assume the worst case for every tick

Question 19

Given a set of tasks T₁…T_n with periodicity p_i and fixed CPU time c_i for task i, how do we calculate the load (U) of this set of tasks. And when are these tasks schedulable

Answer 19

U=∑ⁿ_i=1c_i / p_i

This U value must be less than 1 for the system to be schedulable

Question 20

What two methods can we use to assign priority to tasks

Answer 20

Fixed (static) priority which is assigned at compile time

Dynamic priority which changes during runtime

Question 21

What is the advantage of Fixed Priority scheduling over Dynamic Priority scheduling

Answer 21

Fixed Priority has very simple code, and is well understood meaning we can have high confidence in its behaviour

Question 22

What is the optimal priority scheme for fixed priority scheduling

Answer 22

Rate Monotonic Scheduling

Question 23

What are the requirements for Rate Monotonic Scheduling

Answer 23

Tasks are independent
Tasks have fixed CPU requirement
Context switching is free
Deadline of a given task is its period

Question 24

For RMS tasks must be independent

Answer 24

No task can block another task

Question 25

for RMS tasks must have a fixed CPU requirement, what do we do if a task has a variable CPU requirement

Answer 25

We assume it to take the worst-case amount of time

Question 26

For RMS we assume context switching to be free (when its not), how do we get around this

Answer 26

We include the time taken to context switch in the task time

Question 27

How do we assign the fixed priorities for RMS

Answer 27

We give the most frequent task the highest priority

Question 28

What must U=∑ⁿ_i=1c_i / p_i be less than for RMS to be able to guarantee scheduling for

Answer 28

∑ⁿ_i=1c_i / p_i must be less than n(2^1/n-1)

Question 29

As n approaches infinity, what can we approximate the upper bound for RMS to be effective as

Answer 29

69%

Question 30

When assigning priority for RMS, what does a priority of 0 mean

Answer 30

0 means that the task is of the highest priority

Question 31

Assign the priority for the following tasks with RMS:

• Task A, Importance: Very High, Frequency: 2Hz
• Task B, Importance: High, Frequency: 0.5Hz
• Task C, Importance: Medium, Frequency: 50Hz

Answer 31

Priority:
C: 0 (Highest)
A: 1
B: 2

Question 32

RMS is effective when U<=69% (generalisation but diligaf), what can be done such that we don’t “waste” the other 30% of CPU time

Answer 32

We can either use it to run non-real-time tasks with a “low priority” or optimise the task periods such that a regular execution pattern is achieved

Question 33

If tasks are harmoic, what can we guarantee after observing one successful period of tasks

Answer 33

That all future periods will take the same form

Question 34

How do we make a given task set harmonic

Answer 34

Reduce the deadlines of tasks (make the deadlines stricter) such that any task period is a multiple of the period of any higher priority task

Question 35

For a set of tasks T, with task periods p_i, what must hold for the task set to be harmonic

Answer 35

For each task t_i in T
- For every other task t_j in T / {t_i}
- p_j < p_i or p_j=p_i * n given n is taken from the set of natural numbers

Question 36

Give one example restriction which would make the following periods harmonic
1. 17ms
2. 31ms
3. 130ms

Answer 36

1. 15ms
2. 30ms
3. 120ms

Question 37

What CPU utilization can be reached with a harmonic task set

Answer 37

100% Utilization

Question 38

What do we use instead of periods for Dynamic Priority Scheduling

Answer 38

We use Deadlines in place of periods, this is useful if the deadline is earlier than the next period

Question 39

What is EDF and how does it work

Answer 39

Earliest Deadline First allows dynamic changes of priority and runs the most urgent task first
This can allow preemtion

Question 40

What can we use to calculate the U value for EDF

Answer 40

U= ∑ⁿ_i=1c_i/p_i ≤ 1
Where c_i is the CPU time needed to complete the task and p_i is the period of the task

Question 41

What are some of the drawbacks of using EDF in place of RMS

Answer 41

The Scheduler is more complicated
The Scheduler has more overhead
EDF is not stable under overload

Question 42

What can EDF handle which RMS cannot

Answer 42

+ Changing the importance of tasks
+ New tasks at runtime
+ Variable execution time