Real Time Sistemi operativi 2

(RM).

• , <

If we are dealing with a task set which has at least one sporadic task (∃ )

o we cannot analyze the feasibility through the processor utilization.

o We have to go straight to the Response Time Analysis.

If we find out that the task set is feasible we can schedule it by using the Deadline Monotonic (DM)

algorithm (that we will see later on), which is optimal. -71-

Cristina Saccani – Automation Engineering (2019/2020)

Exercise1

• Processor Utilization: 3 1 1

= + + = 0.825

5 8 10

It’s less than 1, we can proceed.

• LL bound:

o We can divide the task set in two subsets with periods in harmonic

relation: { }, { }

= , ; =

1 1 3 3 2

= 2.

So we compute the LL bound by considering

2

= 0.828

2

<

We have that so this task set is feasible.

Let’s try to compute the HB bound anyway: imagine that the LL bound couldn’t give us an answer.

• HB bound: ∏( + ) ≤

∀

o So we get 3 1 1

( + 1) ∙ ( + 1) ∙ ( + 1) ≤ 2

5 8 10

1.6 ∙ 1.125 ∙ 1.1 ≤ 2

. ≤

it's true, the task set is(hardly) feasible.

Notice that we could have grouped tasks (considering subsets with periods in harmonic relation) to

speed up the computation: { }; { }

= , =

1 1 3 3 2

3 1 1

( + + 1) ∙ ( + 1) ≤ 2

5 10 8

1.7 ∙ 1.125 ≤ 2

. ≤

it's true, the task set is feasible. -72-

Cristina Saccani – Automation Engineering (2019/2020)

Exercise 2

• Processor Utilization: 2 2 2

= + + = 0.75

6 8 12

It’s less than 1, we can proceed.

• LL bound:

o We can divide the task set in two subsets with periods in harmonic

relation: { }, { }

= , ; =

1 1 3 2 2

= 2.

So we compute the LL bound by considering

2

= 0.828

2

<

We have that so this task set is feasible.

-73-

Cristina Saccani – Automation Engineering (2019/2020)

(∃ )

, <

Deadline Monotonic algorithm (DM) -

The idea is to assign to each task a fixed priority inversely

.

proportional to its relative deadline,

•

The shorter deadline , the higher priority.

If we have some sporadic tasks (at least one), DM is optimal.

Let’s consider the following example of a feasible schedule:

•

has got a shorter deadline compared to : has got a higher priority.

1 2

• As we can see there are times in which the CPU is not usable and must remain idle because we cannot

execute either or .

1 2

o We cannot reach 100% of the processor utilization.

To test the feasibility we cannot use the bounds anymore since there are periods in which the CPU cannot

execute. -74-

Cristina Saccani – Automation Engineering (2019/2020)

Response Time Analysis

It’s a method based on interferences (pre-emption):

•

Let’s consider two tasks where has got a higher priority

1

compared to .

2

o

Here we can see that must execute later than its

2

activation time: does interference with .

1 2

o

By the time is activated again has finished: so

1 2

there is no further interference.

In this case, the interference by on is given by the

1 2

computation time of .

o

the response time of is equal to

2

= +

That can also be written (in terms of interference) as:

= +

2 1 2

In general, we can say that the response time is

= +

where is given by a higher priority task.

To understand whether a task set is feasible or not,

•

we have to find out the response time and compare it to the task deadline

o ≤

if for all tasks then the task set is feasible.

o If even one single response is larger than the deadline, the task set is unfeasible.

Notice that we don’t need to draw the schedule: we stop as soon as we reach the end of the first instant

of all the tasks.

Let’s consider this other example:

•

The computation time of is spanning over several periods of :

o

the response time of is

= + 3 ∙

There are three activations of before can terminate.

• There is a method to calculate faster the number (3) of interferences that the higher priority task

induces to the lower priority task: we can use the ceiling (we take the least integer greater than or

equal to what is contained into the brackets):

→ ⌈ ⌉

-75-

Cristina Saccani – Automation Engineering (2019/2020)

o / = 2.8,

If we apply that to our case and we suppose that we obtain

⌈2.8⌉

= = 3

⌈ ⌉

The ceiling of this number gives us the number of times interferences with .

[, ]

In general, the interference of (higher priority task) on in the interval is given by

= ⌉

⌈

Since usually, we have more than one task, when we compute the interference induced to a task we have

to consider the interferences induced by all the tasks that have got a higher priority compared to the task

we are analysing: −

= ∑ ⌉

⌈

=

Let’s consider the following example: we have three tasks with different priorities. Consider a DM schedule.

• Let’s write down an interference table:

Tasks Response time Interference

T1 =

1 1

This task will be only blocked by T1: 2

= ⌉

⌈

2,1 1

= + means “interference on T2 from

T2

2 2,1 2 , 1

T1”.

3

= ⌉

⌈

3,1 1

1

This task will be blocked both from T1

= + +

T3 3

3 3,1 3,2 3 and T2. =

⌈ ⌉

3,2 2

2

So we can write: =

1 1

2

= +

⌈ ⌉

2 1 2

1

3 3

= + +

⌈ ⌉ ⌈ ⌉

3 1 2 3

1 2

We can solve this group of equations by iteration: the ceiling is not a linear operation so we cannot simplify

(for example) and immediately calculate it.

3

From an analytical point of view, the iterative solution is given by the following expressions:

−

ℎ >

0

= ∑ ( )

=1 −1

−1

= ∑ ⌈ ⌉ + ( )

{ =1 -76-

Cristina Saccani – Automation Engineering (2019/2020)

To understand what iteration means consider this graphical representation:

•

We have three tasks: has got the highest priority and the

1 3

lowest.

•

Let’s start analysing the lowest priority task, : we have to

3

calculate its response time to compare it with its relative

deadline. We proceed by approximation:

o First approximation: we schedule all the three tasks

without considering any priority.

▪ We calculate the response time as the

simple summation of all the computation

30

times: graphically it is represented by .

Now we have to check all the higher priority tasks:

o

By looking at (highest priority task) we see that

1

cannot execute when is activated again:

3 1

o Second approximation: the new response time of

31

is represented by .

3

o

By looking at we see that cannot execute

2 3

when is activated again:

2

o

Third approximation: the new response time of is

3

32

represented by .

o Since we have reached the point where we don’t pass

any new activation we are done: we have reached the

“fixed point”. There is no further interference.

So, we can conclude that the response time of is

3

= + +

From an analytical point of view, we have found out that

3 3

= + +

⌈ ⌉ ⌈ ⌉

3 1 2 3

1 2

3 ⌉=2

⌈

1

3 ⌉=2

⌈

2

In general,

• ≤

if a fixed point is reached and then this specific task is feasible.

• >

Otherwise, as soon as we stop the analysis and we conclude that the whole task set is

unfeasible. -77-

Cristina Saccani – Automation Engineering (2019/2020)

Let’s see how this method works in practice.

Exercise:

• →

< we cannot look at the bounds. At least one task (actually all of them) is sporadic: we will try

to schedule it with DM.

• Let’s order the tasks based on their priority (DM schedule): we have to look at the relative deadlines.

{ }

= , ,

( ) ( ).

We must do Response Time Analysis (RTA) from top to bottom

2 3

• Let’s calculate the response time:

o

For :

2

= =

▪ < = 4)

Since it finishes before its deadline ( we can continue the analysis: is

2 2

feasible.

o

For : it is subjected to the interference created by

1 2

▪ First approximation:

10

= ∑ = + = 2 + 2 = 4

1 2

=1

Since it’s not greater than the deadline (5) we can proceed.

To verify if this is a fixed point or not we must apply the followi