Uniprocessing scheduling

Question 1

what is Rate monotonic scheduling

Answer 1

rate monotonic is a preemptive scheduling algorithm that schedule task according to their priority

Question 2

what is RTOS

Answer 2

RTOS are systems in which correctness does not only depend on the correctness of the result but also at the time which the result was produced

Question 3

types of RTOS

Answer 3

Hard real-time system : catastrophique consequences , air craft
firm real time system : deadline misses must be limited
soft-real-time system: deadline misses is not important

Question 4

define a periodic task

Answer 4

a periodic task : 𝜏 i = (Oi , Ti , Di , Ci )
composed of imfinite number of jobs {ii,1 , ji,2 … ji,n}
ji,n is the n-th job of the task i

Question 5

sporadic task vs periodic task

Answer 5

the difference between them lies in the inner absolute deadline

Question 6

what are scheduling algorithms

Answer 6

they are algorithm used for distributing resources among parties that synchronously needs them, its purpose is to minimize the starvation

Question 7

what are the three kinds of scheduling algorithms

Answer 7

FTP where the job inherits the task’s priority, FJT, the job is assigned priorities, fixed DP

Question 8

FTP priority assignement

Answer 8

aperiodic task is said to be FTP-optimal if there exists a scheduling using FTP

Question 9

what are the important phenomenen in FTP arbitrary deadline that are impossible for RM and DM

Answer 9

the first phenomem is that first task can be active simultaneously
The second phenomena are that the first task is not always the optimal

Question 10

the feasability interveal

Answer 10

is an interval, if not deadline is missed during this interval then no dealing would be missed during the whole system lifetime

Question 11

Feasibility interval for constrained deadline

Answer 11

[0 , max Di{i…..n}] which reflects the lemma of the critical instant

Question 12

Feasibility Interval for arbitrary deadline

Answer 12

Rappel 1 λi est le premier idle point (apr`es 0) dans l’ordonnancement synchrone du
sous-ensemble de tˆache {τ1…τi}, et [0, λi
[ est la plus grande level-i busy p´eriode.

Rappel 2 Une busy p´eriode ´el´ementaire est un intervalle de temps [a, b[ tel que a et
b sont des idle points et l’intervalle ]a, b[ ne contient aucun idle points.

Rappel 3 Une level-i busy p´eriode est une busy p´eriode ´el´ementaire en consid´erant
l’ordonnancement des tˆaches {τ1…τi} ou τiex´ecute au moins un job. Th´eoreme Pour un systeme de tˆache synchrone a deadline arbitraire, un intervalle
de faisabilit´e correct est donn´e par : [0, λn[

Preuve Il s’agit d’une cons´equence direct de λ1 < λ2 < … < λn λn
λn est la plus petite solution à l’équation :
𝜆n = n ∑ i=1 ⌈ 𝜆n / Ti ⌉ Ci

and can be computed through fixed-point iteration.
w0 def = n ∑ i=1 Ci , wk+1 def = n ∑ i=1 ⌈ wk /Ti ⌉ Ci

Question 13

what is idle point and busy period

Answer 13

X is considered an idl point if all the tasks occurred before x, have accomplished their execution
and busy period [a,b], if a and b are idl points and (a,b), contain no idl point

Question 14

what is asynchronous operation

Answer 14

it is a nonblocking operation where it may discover the completion later on by other mechanism

Question 15

how to prove the feasibility of FTP systemen using rm

Answer 15

A synchronous constrained deadline system is FTP-schedulable iff r 1 i ≤ Di ∀i

if this condition is not accomplished then we check with this one :
U(𝜏) ≤ 0.69
then we go for the equation provided by audsley :

w0  = Ci , (initialization) 
wk+1 = Ci + ∑ i–1 j=1 ⌈ wk Tj ⌉ Cj (iteration).

Question 16

the optimality of edf

Answer 16

the optimality is edf is stronger than the optimality if RM/Dm since it concerns jobs set andn ot task set