\documentclass[12pt,a4paper]{article}

\usepackage{amstext}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{cancel}
\usepackage{fancyhdr}
\usepackage{listings}
%\usepackage{gastex}
\usepackage{pstricks}
\usepackage{pst-plot}
%\usepackage{ngerman}
\usepackage{wasysym}

\title{\textsc{Embedded Systems \\ \large Assignment 8}}
\author{\shortstack[c]{Jan Hendrik Dithmar\\ \scriptsize 2031259} \and \shortstack[c]{Pascal Gwosdek\\ \scriptsize 2505221}}
\date{}

\pagestyle{fancy}

\lhead{Assignment 8}
\chead{}
\rhead{Dithmar (2031259), Gwosdek (2505221)}
\lfoot{Embedded Systems}
\cfoot{Page \thepage}
\rfoot{SS 2007}

\begin{document}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\newcommand{\exercise}[1]{\subsection{#1}}
\renewcommand{\theenumi}{\textbf{\alph{enumi}}}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[2]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[#1]{#2}\\[0.2cm]
	\end{figure}
	}

\newcommand{\m}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\+}{\phantom{-}}
\newcommand{\f}{\frac}

\maketitle

\thispagestyle{empty}

\newpage
\setcounter{page}{1}
\setcounter{section}{8}

\exercise{EDD-scheduling}
Here is the schedule: \\[0.5cm]
\begin{pspicture}(0,0)(16,2)
\psaxes[tickstyle=bottom,labelsep=-17pt]{-}(16,0)
\psline{->}(5,1)(5,0)\rput(5,1.5){$d_3$}
\psline{->}(9,1)(9,0)\rput(9,1.5){$d_1$}
\psline{->}(10,1)(10,0)\rput(10,1.5){$d_4$}
\psline{->}(16,1)(16,0)\rput(16,1.5){$d_2$}
\psframe(0,0)(2,0.5)\rput[br](1.2,0.05){$J_3$}
\psframe(2,0)(6,0.5)\rput[br](4.2,0.05){$J_1$}
\psframe(6,0)(9,0.5)\rput[br](7.7,0.05){$J_4$}
\psframe(9,0)(14,0.5)\rput[br](11.2,0.05){$J_2$}
\end{pspicture}
\ \\
$$\left.
\begin{array}{c}
L_3 = 3 \\
L_1 = 3 \\
L_4 = 1 \\
L_2 = 2
\end{array}
\right\} \Rightarrow L_{max}=3$$
If we swap $J_1$ and $J_4$, we get: \\[0.5cm]
\begin{pspicture}(0,0)(16,2)
\psaxes[tickstyle=bottom,labelsep=-17pt]{-}(16,0)
\psline{->}(5,1)(5,0)\rput(5,1.5){$d_3$}
\psline{->}(9,1)(9,0)\rput(9,1.5){$d_1$}
\psline{->}(10,1)(10,0)\rput(10,1.5){$d_4$}
\psline{->}(16,1)(16,0)\rput(16,1.5){$d_2$}
\psframe(0,0)(2,0.5)\rput[br](1.2,0.05){$J_3$}
\psframe(2,0)(5,0.5)\rput[br](3.7,0.05){$J_4$}
\psframe(5,0)(9,0.5)\rput[br](7.2,0.05){$J_1$}
\psframe(9,0)(14,0.5)\rput[br](11.2,0.05){$J_2$}
\end{pspicture}
\ \\
$$\left.
\begin{array}{c}
L_3 = 3 \\
L_4 = 5 \\
L_1 = 0 \\
L_2 = 2
\end{array}
\right\} \Rightarrow 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}$.

\newpage
\exercise{Scheduling}
\begin{enumerate}
\item First observation: If $a_i=0 \quad \forall i=1,...,n$ we have for $\overline{R}$:
$$\overline{R} = \frac{1}{n} \sum_{i=1}^n f_i$$
To minimize $\overline{R}$, we have to ensure small finishing times $\forall 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. \\[0.5cm]
Algorithm:
\begin{enumerate}[I]
\item Build a FIFO-queue Q
\begin{enumerate}[1.]
\item If we don't have to consider the deadlines, set the deadlines $d_i \quad \forall i=1,...,n$ to $\sum_{i=1}^n C_i$. \\
If the deadlines are important, don't change the $d_i$'s; just take the given values.
\item 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.
\item Delete all the bad paths from the graph.
\item Compute the sum of the finishing times for each path in the dependence graph.
\item Pick the path with the smallest sum of finishing times and build Q by going along this path.
\end{enumerate}
\item Schedule according to Q.
\end{enumerate}
\newpage
\item The algorithm is not deterministic, because the building of the dependence graph is non-deterministic. \\[0.5cm]
Proof:
\begin{itemize}
\item 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$.
\item Let $d_s = d_t = C_s + C_t$ and $f_j = \sum_{i=3}^n C_i \quad \forall j = 3,...,n$ wlog.
\item Let $\sigma$ be a schedule which starts with $J_s$, followed by $J_t$.
$$\Rightarrow \overline{R} = \frac{1}{n} \cdot \left(f_s + f_t + \sum_{i=3}^n f_i\right)$$
\item Let $\sigma^*$ be a schedule which starts with $J_t$, followed by $J_s$.
$$\Rightarrow \overline{R}^* = \frac{1}{n} \cdot \left(f_t^* + f_s^* + \sum_{i=3}^n f_i^*\right)$$
\item For the finishing times we have the following:
$$f_s = C_s \quad \quad f_t = f_s + C_t$$
and
$$f_t^* = C_t \quad \quad f_s^* = f_t^* + C_s$$
\item Looking at that we obviously get the following:
$$f_s + f_t < f_s^* + f_t^*$$
\item Since all other computation times are higher that $C_t$, we have
$$\sum_{i=3}^n f_i \leqslant \sum_{i=3}^n f_i^*$$
\item[$\Rightarrow$] 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$.
\item[$\Rightarrow$] The algorithm is optimal.
\end{itemize}
\end{enumerate}

%\exercise{WCET/VHDL}

%\exercise{WCET/Cache analysis}

\end{document}
