Embedded Systems

Assignment 8

Jan Hendrik Dithmar

2031259

Pascal Gwosdek

2505221

Assignment 8  Dithmar (2031259), Gwosdek (2505221)

8.1 EDD-scheduling

Here is the schedule:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 d_{3}  d_{1} d_{4}  d_{2} J^{3}  J^{1}  J^{4}  J^{2}

\begin{matrix}L_{3} = 3 \\ L_{1} = 3 \\ L_{4} = 1 \\ L_{2} = 2 \end{matrix} \} ⇒ L_{max} = 3

If we swap J_{1} and J_{4}, we get:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 d_{3}  d_{1} d_{4}  d_{2} J^{3}  J^{4}  J^{1}  J^{2}

\begin{matrix}L_{3} = 3 \\ L_{4} = 5 \\ L_{1} = 0 \\ L_{2} = 2 \end{matrix} \} ⇒ L_{max} = 5

The maximal lateness is increased. This means that the first schedule is better. Now let’s have a look if we modify the last schedule in such way that we additionally swap J_{3} and J_{4}. Then you can easily see, that L_{4} increases to 7 and L_{3} decreases to 0, which leads to a maximal lateness L_{max} = 7. The problem is now even worser. As the schedule above shows, it is possible to schedule the given set of tasks with respect to the criteria 1 | sync | L_{max}.

8.2 Scheduling

a. First observation: If a_{i} = 0 ∀i = 1, ..., n we have for \overline{R}:

\overline{R} = \frac{1}{n} ∑_{i=1}^{n} f_{i}

To minimize \overline{R}, we have to ensure small finishing times ∀J_{i}, i = 1, ..., n. Due to the fact that there are no deadlines mentioned, we assume that the deadlines of the jobs never hurt us. We describe later in the algorithm what to do if we have to consider the deadlines. To get a very small result for the sum, we have to ensure that each summand is as small as possible. Due to this, we have to take the jobs with the smallest C_{i}’s first.

Algorithm:

I Build a FIFO-queue Q

1. If we don’t have to consider the deadlines, set the deadlines d_{i} ∀i = 1, ..., n to ∑_{i=1}^{n} C_{i}. If the deadlines are important, don’t change the d_{i}’s; just take the given values.

2. Build a dependence graph, s.t. the sum of the computation times along a path is smaller or equal than the deadline of the job you want to add to the graph right now. If you get stuck, mark the path as bad.

3. Delete all the bad paths from the graph.

4. Compute the sum of the finishing times for each path in the dependence graph.

5. Pick the path with the smallest sum of finishing times and build Q by going along this path.

II Schedule according to Q. b. The algorithm is not deterministic, because the building of the depen-

dence graph is non-deterministic.

Proof:

• Let J_{s} be the job with the smallest computation time. Let J_{t} be the job with the computation time which is superior to the computation time of J_{s}. All other computation times are higher than the ones from J_{s} and J_{t}.

• Let d_{s} = d_{t} = C_{s} + C_{t} and f_{j} = ∑_{i=3}^{n} C_{i} ∀j = 3, ..., n wlog.

• Let σ be a schedule which starts with J_{s}, followed by J_{t}.

⇒ \overline{R} = \frac{1}{n} · (f_{s} + f_{t} + ∑_{i=3}^{n} f_{i})

• Let σ^{∗} be a schedule which starts with J_{t}, followed by J_{s}.

⇒ \overline{R}^{∗} = \frac{1}{n} · (f_{t}^{∗} + f_{s}^{∗} + ∑_{i=3}^{n} f_{i}^{∗})

• For the finishing times we have the following:

f_{s} = C_{s} f_{t} = f_{s} + C_{t}

and

f_{t}^{∗} = C_{t} f_{s}^{∗} = f_{t}^{∗} + C_{s}

• Looking at that we obviously get the following:

f_{s} + f_{t} < f_{s}^{∗} + f_{t}^{∗}

• Since all other computation times are higher that C_{t}, we have

∑_{i=3}^{n} f_{i} ⩽ ∑_{i=3}^{n} f_{i}^{∗}

⇒ The sum – and obviously the average response time – is bigger after swapping J_{s} and J_{t} in that way that J_{t} is executed before J_{s}.

⇒ The algorithm is optimal.