Embedded Systems

Assignment 9

Jan Hendrik Dithmar

2031259

Pascal Gwosdek

2505221

Assignment 9  Dithmar (2031259), Gwosdek (2505221)

9.1 Scheduling

First of all, we give the set of tasks by using d_{i} instead of D_{i}:

J_{1} J_{2} J_{3} J_{4}
a_{i} 0 4 2 6
C_{i} 6 2 4 2
d_{i} 18 8 9 10

Now we state the tree by using this set of tasks:

J_{1}  J_{2}  J_{3} J_{2}  J_{3}  J_{4} 6  6  6 8  10  8  J_{1}  J_{2} J_{1}  J_{4} J_{1} 12  8 14  1016 ↯ J_{3} ↯ J_{3}  ↯ J_{3}  ↯ J_{2}  ↯ J_{2}  ↯ J_{4}

9.2 Scheduling

a. 1. In the first step, we have to modify the activation times. Using the

algorithm gives the following: • a_{A}^{∗} = a_{A} = 0

• selecting task B. •

a_{B}^{∗} = max({a_{H}^{∗} + C_{H}|H → B} ∪ a_{B})
= max({a_{A}^{∗} + C_{A}} ∪ {a_{B}})
= max({2, 0})
a_{B}^{∗} = 2

• selecting task C. •

a_{C}^{∗} = max({a_{H}^{∗} + C_{H}|H → C} ∪ {a_{C}})
= max({2, 5, 0})
a_{C}^{∗} = 5

• selecting task D. •

a_{D}^{∗} = max({a_{H}^{∗} + C_{H}|H → D} ∪ {a_{D}})
= max({2, 5, 8, 0})
a_{D}^{∗} = 8

• selecting task E. •

a_{E}^{∗} = max({a_{H}^{∗} + C_{H}|H → E} ∪ {a_{E}})
= max({2, 5, 8, 13, 0})
a_{E}^{∗} = 13

• selecting task F. •

a_{F}^{∗} = max({a_{H}^{∗} + C_{H}|H → F } ∪ {a_{F} })
= max({2, 5, 8, 13, 14, 0})
a_{F}^{∗} = 14

• selecting task G. •

a_{G}^{∗} = max({a_{H}^{∗} + C_{H}|H → G} ∪ {a_{G}})
= max({2, 5, 8, 13, 14, 19, 0})
a_{G}^{∗} = 19

2. In the second step, we have to modify the deadlines. Using the

algorithm, we get the following:

• d_{G}^{∗} = d_{G} = 25 d_{G} = 25 since d_{G} = a_{G} + D_{G} = 0 + 25 = 25.

• selecting task F. •

d_{F}^{∗} = min({d_{H}^{∗} − C_{H}|F → H} ∪ {d_{F} })
= min({d_{G}^{∗} − C_{G}} ∪ {d_{F} })
= min({20, 25})
d_{F}^{∗} = 20

• selecting task E. •

d_{E}^{∗} = min({d_{H}^{∗} − C_{H}|E → H} ∪ {d_{E}})
= min({18, 20, 25})
d_{E}^{∗} = 18

• selecting task D. •

d_{D}^{∗} = min({d_{H}^{∗} − C_{H}|D → H} ∪ {d_{D}})
= min({17, 18, 20, 25})
d_{D}^{∗} = 17

• selecting task C. •

d_{C}^{∗} = min({d_{H}^{∗} − C_{H}|C → H} ∪ {d_{C}})
= min({12, 17, 18, 20, 25})
d_{C}^{∗} = 12

• selecting task B. •

d_{B}^{∗} = min({d_{H}^{∗} − C_{H}|B → H} ∪ {d_{B}})
= min({9, 12, 17, 18, 20, 25})
d_{B}^{∗} = 9

• selecting task A. •

d_{A}^{∗} = min({d_{H}^{∗} − C_{H}|A → H} ∪ {d_{A}})
= min({6, 9, 12, 17, 18, 20, 25})
d_{A}^{∗} = 6

We now have a new task set J^{∗}, which looks like this:

A B C D E F G
a_{i}^{∗} 0 2 5 8 13 14 19
C_{i} 2 3 3 5 1 2 5
d_{i}^{∗} 6 9 12 17 18 20 25

b. We use the results from the previous exercise to run EDF, obtaining an EDF-schedule for J^{∗}: (the schedule is depicted on the next page)

A _{0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25} B _{0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25} C _{0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25} D _{0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25} E _{0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25} F _{0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25} G _{0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25}
Embedded Systems  Page 5  SS 2007

9.3 Fault tree analysis

a. • Determine formula of the fault tree:

fault = ((C ∨ E) ∧ A) ∨ (B ∧ (A ∨ (D ∧ ¬E)))

• Get DNF of fault:

((C ∨ E) ∧ A) ∨ (B ∧ (A ∨ (D ∧ ¬E)))
= (C ∧ A) ∨ (E ∧ A) ∨ (B ∧ A) ∨ (B ∧ D ∧ ¬E)

• Minimize:

The term is already minimal (wrt. the DNF). The prime implicants are:

– (C ∧ A): ”Hauptrechner fails and this is not recognized”

– (E ∧ A): ”Hauptrechner fails and the switch does not trigger the Fehlererkennung”

– (B ∧ A): ”Both Hauptrechner and Reserverechner fail”

– (B ∧ D ∧ ¬E): ”’false positive’. Reserverechner fails, Hauptrechner is said to have failed and the switch triggers Fehlererkennung”

b. We can immediately compute the probability of a prime implicant to occur:

P (C ∧ A) =^{ind.} P (C) · P (A) = 0.006 · 0.1 = 0.0006
P (E ∧ A) =^{ind.} P (E) · P (A) = 0.05 · 0.1 = 0.005
P (B ∧ A) =^{ind.} P (B) · P (A) = 0.1 · 0.1 = 0.01
P (B ∧ D ∧ ¬E) =^{ind.} P (B) · P (D) · P (¬E)
= P (B) · P (D) · (1 − P (E))
= 0.1 · 0.02 · (1 − 0.05) = 0.002 · 0.95 = 0.0019

⟹ The lower bound of reliability if (1 − 0.01) = 0.99 = 99%