add new repoHEADmaster

1 files changed, 323 insertions, 0 deletions

diff --git a/Master/Masterarbeit/thesis/tex/fundamentals.tex b/Master/Masterarbeit/thesis/tex/fundamentals.tex
new file mode 100644
index 0000000..f5d19ec
--- /dev/null
+++ b/Master/Masterarbeit/thesis/tex/fundamentals.tex
@@ -0,0 +1,323 @@
+\setchapterpreamble[u]{%
+	\dictum[Johann Wolfgang von Goethe]{Der echte Schüler lernt aus dem Bekannten das Unbekannte entwickeln und nähert sich dem Meister.}\bigskip}
+\chapter{Grundlagen}
+\label{chp:fundamentals}
+Dieses Kapitel beschäftigt sich mit den Grundlagen, auf denen das in Kapitel \ref{chp:concept} vorgestellte Konzept basiert.
+%===============================================================================================
+\section{Multitasking}
+In diesem Abschnitt erfolgt eine theoretische Betrachtung eines Allzweckbetriebssystems (engl. General-Purpose) mit Multitasking-Fähigkeit. Die Betrachtung erfolgt unabhängig von einem speziellen Betriebssystem, da die vorgestellten Konzepte in verschiedenen Systemen in ähnlicher Weise vorhanden sind.
+
+Der Begriff \textit{Task}\index{Task} bezeichnet hierbei eine abstrakte Ablaufeinheit oder ein abstraktes Programm. In dieser Arbeit steht Task für beliebige konkrete Implementierungen in Betriebssystemen wie Prozesse oder Threads. Er ermöglicht somit eine allgemeingültige Betrachtung der Konzepte.
+
+Multitasking bezeichnet hierbei die Fähigkeit eines Betriebssystems mehrere Aufgaben auf einer oder mehreren CPUs quasi-parallel auszuführen. Entscheidend ist hierbei der Begriff der Quasi-Parallelität. In einem System kann zu einem Zeitpunkt nur eine Task pro Prozessor ausgeführt werden. D. h. auf einem System mit nur einem CPU-Kern können zwei Tasks nicht gleichzeitig arbeiten. Um es dem Benutzer trotzdem zu ermöglichen, mit mehreren Programmen \textit{gleichzeitig} zu arbeiten, verfügen gängige Allzweckbetriebssysteme über Mutlitasking-Mechanismen, die den Anschein einer parallelen Verarbeitung erwecken. Diese Mechanismen sorgen dafür, dass alle Tasks in einer fairen Verteilung die CPU verwenden dürfen. Dabei erfolgt diese Zuteilung bzw. Entzug der CPU sowohl für den Benutzer als auch für die Tasks transparent durch das Betriebssystem.
+
+Der Begriff Allzweckbetriebssystem charakterisiert hierbei ein Betriebssystem, auf dem verschiedene Tasks arbeiten können, die unterschiedliche Aufgaben erledigen. Das Betriebssystem verfügt im voraus über keine Kenntnis darüber, zu welchem Zeitpunkt welche Task arbeiten soll. Es versucht dabei, jeder Task gleich viel Rechenzeit auf dem Prozessor zukommen zu lassen. Diese Betrachtung bleibt auch für Mehrprozessorsysteme gültig, da hier bei abstrakter Betrachtung dem Betriebssystem lediglich mehrere Prozessoren zur Verfügung stehen, auf die es Tasks verteilen kann.
+%===============================================================================================
+\subsection{Taskzustände}
+Aus dem vorigen Abschnitt ergeben sich schon zwei mögliche Zustände, die eine Task annehmen kann, arbeitend oder wartend. Für die Betrachtungen in dieser Arbeit ist noch ein dritter Zustand, blockiert, von Bedeutung. Hierbei hat sich die Verwendung der englischen Bezeichnungen eingebürgert.
+\begin{description}
+\item [Running] Genau eine Task pro CPU befindet sich im Zustand Running. Sie führt gerade ihren Programmcode auf der CPU aus.
+\item [Ready] Eine Task in diesem Zustand ist bereit ihre Anweisungen auf der CPU auszuführen und wartet auf Zuteilung durch das Betriebssystem
+\item [Blocked] In diesem Zustand wartet eine Task auf ein externes Ereignis, z. B. der Abschluss einer lang dauernden IO-Operation auf einem Peripheriegerät oder die Freigabe einer Ressource wie z. B. eines Mutex durch eine andere Task. Die Erläuterung des Begriffs Mutex erfolgt später in diesem Kapitel.
+\end{description}
+%===============================================================================================
+\subsection{Taskscheduler}
+Eine Komponente des Betriebssystems, der Task-Scheduler, entscheidet, welche Task als nächste ausgeführt wird. Zum Treffen dieser Entscheidung existieren vielfältige Algorithmen. Grundsätzlich lassen sich dabei kooperative und preemptive Verfahren unterscheiden. 
+%===============================================================================================
+\subsubsection*{Kooperatives Scheduling}
+Diese Verfahren folgen dem Ansatz \textit{run-to-completion}. Eine laufende Task bleibt solange auf der CPU aktiv, bis sie sich selbst beendet, also all ihre Operation ausgeführt hat, oder die CPU selbst mittels eines Betriebssystemaufrufs freigibt. Derartige Verfahren sind vergleichsweise einfach zu implementieren. Allerdings finden sie heute nur noch in bestimmten Nischen Verwendung. Ihr Hauptnachteil besteht darin, dass eine Task durch intensive CPU-Nutzung andere Tasks an deren Ausführung hindern kann.
+%===============================================================================================
+\subsubsection*{Preemptives Scheduling}
+Der Hauptunterschied zwischen preemptiven Verfahren und kooperativen liegt, dass bei preemptiven der Scheduler die aktuelle Task jederzeit von der CPU verdrängen und eine andere Task zur Ausführung bringen kann. Dazu muss der Scheduler regelmäßig aufgerufen werden, obwohl er selbst zu diesem Zeitpunkt nicht auf der CPU läuft. Um dieses Problem zu lösen, verwenden die meisten Systeme einen zyklischen Hardwaretimer. Ist der Timer abgelaufen, führt der Prozessor die entsprechende ISR aus. Diese ISR ist Teil des Betriebssystems und aktiviert den Scheduler. Dieser entscheidet nun, ob die gerade aktive Task weiter ausgeführt wird oder eine andere zur Ausführung kommt. Bei den meisten Allzweckbetriebssystemen steht jeder Tasks ein gewisses Zeitkontingent, auch \textit{quantum} nach \cite{Tan92} oder Zeitscheibe genannt, für die CPU-Nutzung zur Verfügung.
+
+Im einfachsten Fall verfügt der Scheduler über eine Liste der Tasks, die bereit zur Ausführung sind. Bei jedem zyklischen Aufruf des Schedulers überprüft dieser, ob die aktuell laufende Task ihr quantum erreicht hat. Falls sie es nicht erreicht hat, bleibt sie die laufende Task des Systems. Falls sie es erreicht hat, führt der Scheduler einen Wechsel der aktuell laufenden Task durch. Dazu speichert er den Kontext der aktuell laufenden Task und fügt diese an das Ende der Taskliste an. Jetzt stellt er den Kontext der vordersten Task der Taskliste wieder her und bringt diese als aktuell laufende Task zur Ausführung. Dieses Verfahren trägt auch die Bezeichnung \textit{Round-Robin}-Scheduling.
+
+Mittels der Erweiterung dieses Verfahrens auf mehrere Listen mit bereiten Tasks lässt sich dieses Verfahren um das Konzept der Priorität erweitern. Dazu durchläuft der Scheduler die Bereitlisten in einer festen Reihenfolge, die Liste mit den Tasks der höchsten Priorität zuerst und die Liste der Tasks mit den niedrigsten Prioritäten zuletzt. Daraus ergeben sich unterschiedliche Prioritätsklassen für Tasks, je nachdem in welcher Bereitliste sie sich befinden. Auf der Suche nach der nächsten aktiven Task durchläuft der Scheduler zuerst die höchste Prioritätsklasse. Die erste bereite Task dieser Klasse wird die aktive. Befindet sich keine bereite Task in dieser Liste, durchläuft er die Liste mit der nächst niedrigeren Priorität. Befindet sich auch in dieser Liste keine bereite Task, durchsucht er die nächst niedrigere. So durchsucht der Scheduler alle Prioritätsklassen bis er eine bereite Task findet. In der niedrigsten Prioritätsklasse befindet sich bei den meisten Betriebssystemen eine Task, die immer bereit ist, die sog. Idle-Task. Diese wird nur ausgeführt, wenn keine andere Task bereit ist.
+
+Die meisten Betriebssystem stellen Systemaufrufe bereit, mit denen der Programmierer festlegen kann, zu welchen Prioritätsklassen bestimmte Tasks gehören.
+
+Sind nun Tasks mit hoher Priorität oft bereit und nutzen die CPU sehr intensiv, entsteht daraus der Effekt, dass Tasks niedriger Priorität nicht mehr zum Zuge kommen. Für ein Allzweckbetriebssystem ist dieser Effekt unerwünscht, weshalb auch hier vielfältige Verfahren zum Einsatz kommen, um diesen zu verhindern. Hierbei kommen oftmals statistische oder Zufallsverfahren zum Einsatz, die dafür sorgen sollen, dass gelegentlich auch Tasks niedriger Priorität laufen, obwohl Tasks höherer Priorität bereit sind. Dies führt zu einem nicht deterministischen Verhalten des System. Wie der nächste Abschnitt veranschaulicht, stellt dieser Nichtdeterminismus für Systeme, bei denen es auf zeitlich präzises Verhalten der Tasks ankommt, ein Problem dar.
+%===============================================================================================
+\section{Real-Time Linux}
+\label{sec:realtimelinux}
+\index{Real-Time Linux}
+Dieser Abschnitt befasst sich mit der Eignung von Linux als Echtzeitbetriebssystem. Dazu muss vorab der Begriff \textit{Echtzeitsystem} im wissenschaftlichen Kontext definiert werden. Danach folgt eine Liste von Anforderungen, die ein Echtzeitbetriebssystem nach aktuellem Stand der Wissenschaft erfüllen muss. Abschließend werden zwei Ansätze vorgestellt, die Linux befähigen sollen, möglichst viele dieser Anforderungen zu erfüllen, die der Standard Linux Kernel als Allzweckkernel (engl. General-Purpose Kernel) bzw. andere Allzweckbetriebssysteme nicht erfüllen können. 
+%===============================================================================================
+\subsection{Echtzeitsysteme}
+Generell unterscheidet die Literatur zwei Arten von Echtzeitsystem, weiche Echtzeitsysteme (engl. Soft Real-Time Systems) und harte Echtzeitsysteme (engl. Hard Real-Time Systems) \cite{But11}, \cite{Mantegazza:2000:RRT:348554.348564}. Weiche Echtzeitsysteme zeichnen sich dadurch aus, dass Tasks zum größten Teil nach dem vorgegebenen Plan ausgeführt werden. D. h. alle Tasks halten im Durchschnitt ihre Deadlines ein. Der Begriff \textit{Deadline} bezeichnet hierbei einen Zeitpunkt, zu dem eine Task erfolgreich abgeschlossen sein muss, um die korrekte Funktion des Gesamtsystems zu gewährleisten. Bei weichen Echtzeitsystemen stellt ein einmaliges Verpassen einer Deadline kein kritisches Ereignis dar. Als Beispiel hierfür dient die Wiedergabe von Videodaten. Der gelegentliche Verlust eines Frames im Datenstrom kann mittels Interpolation zwischen dem vorherigen und nachfolgenden Frame kompensiert werden. Solange die Verluste ein gewisses Maß nicht überschreiten, bleibt die Wiedergabe auf einem akzeptablen Niveau.
+
+Im Gegensatz dazu stehen harte Echtzeitsysteme, bei denen das Überschreiten der Deadline einer Task, zu katastrophalen Folgen führen kann. Zu harten Echtzeitsystemen zählen beispielsweise Steuerungen in nuklearen Anlagen, Flugzeugen oder medizinischen Anlagen.
+
+Daraus folgt, dass sich die Korrektheit eines Echtzeitsystems aus der Korrektheit der Berechnungen und der Korrektheit in der Zeit, in der die Berechnungen erfolgen, zusammensetzt. Die Silbe \textit{Echt--} besagt hierbei, dass das System die gleiche Zeitbasis verwendet wie seine Umwelt, mit der es interagiert.
+%===============================================================================================
+\subsection{Forderungen an Echtzeitsysteme}
+\label{sec:fun:rt_req}
+\cite{But11} stellt folgende Anforderungen an Echtzeitsysteme
+\begin{description}
+\item[Rechtzeitigkeit] (engl. timeliness) bezeichnet die o. g. Einbeziehung der Zeitdomäne in die Definition von Korrektheit für ein Echtzeitsystem
+\item[Vorhersagbarkeit] Das zeitliche Verhalten der Tasks eines Systems muss aus der Definition der Tasks vorhersagbar sein.
+\item[Effizienz] Da die meisten Echtzeitsysteme auf Hardware mit eingeschränkten Ressourcen bzgl. Speicher und Rechenleistung basieren, ist ein effizienter Umgang mit diesen Ressourcen notwendig, um die gewünschte Verarbeitungsgeschwindigkeit zu erzielen.
+\item [Robustheit] Auch unter Spitzenlast muss ein Echtzeitsystem noch funktionieren. Ggf. muss eine spezielle Behandlung von Überlastsituationen vorgesehen werden.
+\item [Wartbarkeit] Eine modulare Architektur soll die Anpassung eines Echtzeitsystems an geänderte Vorgaben bzw. Anforderungen erleichtern.
+\end{description}
+Zur Erfüllung dieser Anforderung tragen die verwendete Hardware, der Kernel des Betriebssystems sowie die Echtzeitanwendung selbst bei. Dabei existieren auf allen drei vorgenannten Ebenen Faktoren, die der Erfüllung dieser Forderungen entgegen wirken.
+Die nachfolgende Liste benennt diese Faktoren und beschreibt nach \cite{But11}, welche negativen Einflüsse sie auf das Echtzeitverhalten des Systems haben, und skizziert Ansätze zu deren Vermeidung.
+\begin{description}
+\item[DMA] \index{DMA} Hierbei handelt es sich um ein Verfahren, das die Gesamtperformance eines Systems verbessern soll. Dabei erhält Hardware außerhalb des Prozessors direkten Zugriff auf den Hauptspeicher, abgekürzt RAM\index{RAM}. Dadurch soll der Prozessor nicht mit dem Datenaustausch zwischen Gerät und Speicher belastet werden. In den meisten Fällen verwendet DMA eine Methode namens \textit{cycle stealing} für den Transfer von Daten. Da der Hauptspeicher nur von einem Gerät, entweder dem Prozessor oder dem externen Gerät, zu einem Zeitpunkt angesteuert werden kann, sperrt diese Methode für eine bestimmte Anzahl von Speicherzyklen den Zugriff durch den Prozessor. Innerhalb dieser Sperre greift das externe Gerät auf den Speicher zu und der Prozessor muss ggf. warten, bis der Speicherzugriff beendet ist. Da sich nicht vorhersagen lässt, wann ein externes Gerät DMA-Zugriffe durchführt und damit den Prozessor blockiert, trägt diese Methode zur Nichtvorhersagbarkeit eines Systems bei.
+
+Abhilfe schafft hier nur die Verwendung einer anderen Methode für den DMA-Zugriff, also die Verwendung einer anderen Hardware-Architektur.
+
+\item[Cache\phantomsection\label{sec:fund:cache}] \index{Cache} Auch hierbei handelt es sich um ein Hardwareelement, das die Ausführungsgeschwindigkeit des Gesamtsystems verbessern soll. Es bezeichnet einen im Vergleich zum RAM kleinen und schnellen Speicher zwischen Prozessor und RAM. Er bedient zur Zwischenspeicherung von Daten, um kürzere Zugriffszeiten auf diese Daten zu ermöglichen. Da der Cache wesentlich kleiner ist, als das RAM, kann er nicht alle Daten enthalten. Benötigt der Prozessor ein Datum, das nicht im Cache vorhanden ist, kommt es zu einem sog. \textit{cache miss}, auch \textit{cache fault} genannt. Dies verursacht eine Verzögerung, da das Datum erst aus dem RAM in den Cache geladen wird und dann in den Prozessor. Da dieses Verfahren transparent ist, lässt sich nicht feststellen oder vorhersagen, wann cache faults auftreten. Auch wenn statistische Analysen zeigen, dass die meisten Speicherzugriffe eines Programms nur einen kleinen Teil des Speichers betreffen, lässt sich der Einfluss von cache faults nur schwer bestimmen. Weiterhin führen häufige Preemptionen zu cache faults, da plötzlich auf andere Speicherbereiche zugegriffen wird, die mit geringerer Wahrscheinlichkeit im Cache vorliegen. \cite{But11} zitiert eine Ausarbeitung nach der in einem speziellen Fall die WCET durch Cache-Einflüsse im preemptiven Modus um 33\% gegenüber dem nicht-preemptiven Modus verschlechtert.
+
+\item[Interrupts] Auch Interrupts durch externe Geräte können unvorhersagbare Verzögerungen in einem System auslösen. In herkömmlichen Systemen unterbricht ein Interrupt die laufende Task und führt die zugehörige ISR\index{ISR} des Interrupts aus, in der alle nötigen Operationen ausgeführt werden. Dies ermöglicht die Kapselung der Details des Geräts innerhalb eines sog. Treibers. In einem Echtzeitsystem kann die Abarbeitung einer Task aber wichtiger sein als die Abarbeitung einer ISR. Da sich die Häufigkeit von Interrupts nicht vorhersagen lässt und ISRs eine höhere Priorität als Tasks besitzen, führt dies zu einem nicht vorhersagbaren Verhalten der Tasks. \cite{But11} nennt folgende drei mögliche Lösungsansätze, um diese Situation zu verbessern:
+\begin{enumerate}
+\item Deaktivierung aller externen Interrupts und direkter Zugriff auf die Hardware durch die Tasks. Dieses Verfahren stellt zwar die Vorhersagbarkeit des Verhaltens der Tasks sicher, bringt aber auch gravierende Nachteile mit sich. Der Zugriff auf die Hardware erfolgt im Polling-Betrieb und verbraucht damit sehr viel Rechenzeit. Weiterhin verlagern sich die Details des Hardwarezugriffs direkt in die Taskimplementierung bzw. eine separate Bibliothek.
+
+\item Deaktivierung aller externen Interrupts mit Ausnahme eines Timer-Interrupts. Mithilfe dieses Timers kommuniziert der Kernel in zyklischen Tasks mit der Hardware. Auch hier lässt sich der Aufwand für die Kommunikation vorher bestimmen und in die Analysen mit einbeziehen. Allerdings verbraucht auch dieser Ansatz viel Rechenzeit mit Polling.
+
+\item \label{sec:fun:rtintc} Aktivierung aller externen Interrupts und Minimierung der ISRs. Dabei löst die ISR eines Interrupts nur ein entsprechendes internes Event aus, das von einer separaten Task abgearbeitet wird. Diese Task unterliegt dem normalen Scheduling und besitzt eine Priotität. Somit lässt sich durch entsprechende Anpassung der Priorität das Verhalten der Interrupt-Abarbeitung in das gewünschte Verhalten des Systems integrieren und vorhersagen.
+\end{enumerate}
+
+\item[Systemaufrufe] Auch Aufrufe von Kernel-Routinen durch Tasks tragen zur Ausführungszeit der Tasks bei. Deshalb muss das zeitliche Verhalten von Kernel-Routinen bekannt sein, um die WCET der Tasks bestimmen zu können. Ebenso verzögert jeder nicht-preemptive Teil des Kernel evtl. die Aktivierung oder Ausführung einer kritischen Task. Demnach sollte jede Kernel-Routine preemptiv sein.
+
+\item[Synchronisation] Da herkömmliche Semaphoren-Konzepte zu dem Problem der Prioritätsinvertierung führen können, was für Echtzeitsysteme inakzeptabel ist, fordert \cite{But11} auch hierfür eine Lösung. Der separate Abschnitt \nameref{sec:fund:pip} widmet sich der Beschreibung des Problems und einer möglichen Lösung.
+
+\item[Speicherverwaltung\phantomsection\label{sec:fund:swap}] Besonders negativen Einfluss auf die Vorhersagbarkeit hat das Konzept des Auslagerns von RAM auf Festplattenspeicher, engl. swapping oder paging. Auch hier können zu beliebigen Zeitpunkte sehr lange Verzögerungen durch Zugriffe auf die Festplatte entstehen, die die Abarbeitung kritischer Tasks verzögern. Diese Funktionalität stellt das Betriebssystem bereit, deshalb muss ein Echtzeitbetriebssystem Möglichkeiten zur Steuerung oder Unterdrückung von swapping bieten.
+
+\item[Programmierung] Die hohe Komplexität der Anwendungen erfordert in der Regel die Verwendung einer Programmiersprache. Neben speziellen Programmiersprachen für Echtzeitsysteme finden auch herkömmliche Programmiersprachen Verwendung. Da diese keine Möglichkeiten zur expliziten Formulierung des zeitlichen Verhaltens bieten, muss sich der Programmierer hier Einschränkungen unterwerfen, die Echtzeit-Programmiersprachen erzwingen. Diese Einschränkungen umfassen folgende Punkte:
+\begin{description}
+\item[Dynamischen Speicher] Auf die Verwendung von dynamischen Zeigern, Objekten, Arrays oder Zeichenketten (engl. strings) ist zu verzichten.
+\item[Rekursion] Auch auf rekursive Aufrufe ist zu verzichten
+\item[Schleifen] Echtzeit-Programmiersprachen zwingen den Programmierer zu einer Angaben der maximalen Anzahl von Durchläufen bei allen Schleifenkonstrukten. Ohne diese implizite Angabe muss der Programmierer auf die maximale Anzahl der Schleifendurchläufe achten.
+\end{description}
+
+\end{description}
+Die vorgenannten Faktoren erschweren die WCET-Analyse\index{WCET} eines Programms. Darunter versteht man die Berechnung der Zeitspanne, die ein System im ungünstigsten Fall für die Abarbeitung eines Tasks oder bestimmten Programmteils benötigt.
+
+An dieser Stelle folgt die Betrachtung von zwei alternativen Ansätzen, um die Echtzeitfähigkeit von Linux zu verbessern. Die Betrachtung orientiert sich an der vorhergehenden Liste zur Vermeidung negativer Einflüsse auf das Echtzeitverhalten eines Systems.
+%===============================================================================================
+\subsection{RTAI}
+\label{sec:fun:rtai}
+\index{RTAI}
+Dieser Abschnitt beschreibt RTAI, einen Ansatz, der das Betriebssystem Linux für harte Echtzeitaufgaben geeignet machen soll. Die Grundidee dabei ist, dass Linux selbst die Task mit niedrigster Priorität eines kleinen Echtzeitbetriebssystems darstellt. Linux wird dabei nur ausgeführt, wenn keine anderen Echtzeittasks mit höherer Priorität ausgeführt werden. Zur Kommunikation mit dem restlichen System ergänzt RTAI den Linux Kernel um eine Hardwareabstraktionsschicht. Unter RTAI werden Echtzeittasks als Kernelmodule implementiert und geladen.
+\cite{Mit07} vergleicht die Leistungsfähigkeit von RTAI mit der von \nameref{sec:fun:PREEMPTRT} im Hinblick auf ihre jeweilige Eignung für harte Echtzeitaufgaben. Die Vorteil von RTAI liegt in kürzeren Verzögerungen und der Möglichkeit auch ausserhalb des Kernels direkt auf Interrupts zuzugreifen. Danach eignen sich beide Ansätze für die Lösung der Aufgabenstellung dieser Arbeit. RTAI findet jedoch in der weiteren Arbeit keine Beachtung mehr, da das verwendete System auf der nachfolgend vorgestellten Alternative \nameref{sec:fun:PREEMPTRT} basiert.
+%===============================================================================================
+\subsection{PREEMPT\_RT}
+\label{sec:fun:PREEMPTRT}
+\index{PREEMPT\_RT}
+Dieser Abschnitt beschreibt PREEMPT\_RT, einen Patch, der den Linux Kernel selbst echtzeitfähig macht. Die Entwicklungen im Rahmen von PREEMPT\_RT umfassen u. a. Echtzeitscheduler mit festen Prioritäten, Prioritätsvererbung und Veränderungen des Kernels, die ihn fast an jeder Stelle unterbrechbar machen. Außerdem erweitert PREEMPT\_RT den Linux Kernel um hochauflösende Timer. Eine detaillierte Beschreibung der Entwicklung von PREEMPT\_RT über die Zeit lässt sich in \cite{Dietrich_theevolution} nachlesen. Einer der wichtigsten Punkte von PREEMPT\_RT stellt dabei die Ersetzung sog. spinlocks durch Mutexe dar. Spinlocks verwenden Polling und sind damit nicht unterbrechbar. Diese Ersetzung ermöglicht die Einrichtung vieler kleiner kritischer Abschnitte im Kernel anstatt des sog. \textit{Big Kernel Lock (BKL)}. Weiterhin ermöglichen Kernel-Mutexe die Verwendung von separaten Tasks zur Interruptbehandlung wie von \cite{But11} in Alternative \ref{sec:fun:rtintc} zu echtzeitfähiger Interruptbehandlung vorgeschlagen. Diese Interrupt-Tasks nehmen am Scheduling teil und wichtige Echtzeittask können diese unterbrechen. Die hochauflösenden Timer sind mittlerweile fester Bestandteil des Linux Standardkernels.
+
+So erfüllt PREEMPT\_RT wichtige Anforderungen an Echtzeitsysteme auf konzeptioneller Ebene bereits im Kernel und vermeidet so eine zusätzliche Abstraktionsschicht. Alle Vorteile von PREEMPT\_RT sind über POSIX-kompatible Schnittstellen verwendbar, was ebenfalls der Forderung nach Wartbarkeit entgegenkommt.
+%===============================================================================================
+\section{Prioritätsvererbung}
+\label{sec:fund:pip}
+Das Konzept der Prioritätsvererbung dient zur Lösung des Problems der Prioritätsinvertierung ,engl. priority inversion. Dieses Problem beschreibt ein Phänomen, bei dem eine Task mit höherer Priorität durch eine Tasks mit geringerer Priorität verzögert wird. Dies kann zur Nichteinhaltung der Deadline der Task mit höherer Priorität führen. Dies wiederum kann zur Fehlfunktion des Gesamtsystems führen. Dass dieses Phänomen in der Realität vorkommt, belegt \cite{Ree97}. Dort wird erläutert, wie eine Prioritätsinvertierung die Pathfinder Mission auf dem Mars behinderte.
+
+Eine zentrale Rolle bei diesem Problem spielen geteilte Ressourcen (engl. shared ressources), auf die mehrere Tasks zugreifen. Um hier die Konsistenz der Daten zu gewährleisten, muss der Zugriff auf die Ressource in sequentieller Reihenfolge ablaufen. Zur Synchronisation der Tasks beim Zugriff auf geteilte Ressourcen dienen beispielsweise sog. Semaphoren oder Mutexe, die vom Betriebssystem bereit gestellt werden. Der Zeitraum des Zugriffs einer Task auf die geteilte Ressource trägt die Bezeichnung \textit{kritischer Abschnitt} (engl. critical section). Die Synchronisationsmechanismen sollen sicherstellen, dass sich immer nur eine Task innerhalb eines kritischen Abschnitts befindet. Befindet sich eine Task innerhalb eines kritischen Abschnitts, müssen weitere Tasks, die den kritischen Abschnitt betreten wollen, warten bis die erste Task den kritischen Abschnitt verlässt. Beim Verlassen entsperrt die Task den kritischen Abschnitt.
+
+Allgemein lässt sich die Entstehung einer Prioritätsinvertierung wie folgt beschreiben:
+\begin{enumerate}
+\item Eine Task L mit niedriger Priorität ist aktiv, betritt einen kritischen Abschnitt C und sperrt ihn.
+\item Eine Task H mit hoher Priorität wird aktiviert und verdrängt Task L. Task H möchte den kritischen Abschnitt C betreten, der von L gesperrt wurde. Task H wird aufgrund der Sperre von C blockiert.
+\item Eine Task M mit mittlerer Priorität wird aktiviert und verhindert, dass Task L die Sperre von C freigeben kann. Task M bleibt über die Deadline von H hinaus aktiv und verursacht so die Verletzung der Deadline einer Task mit höherer Priorität. Somit wurden die Prioritäten von H und M invertiert.
+\end{enumerate}
+\begin{figure}[hbtp]
+\centering
+\begin{minipage}[b]{.5\linewidth}
+\includegraphics[width=\linewidth]{prio_inv.eps}
+\end{minipage}
+\caption{Prioritätsinvertierung}
+\label{fig:fun:prioinv}
+\end{figure}
+Die Abbildung \ref{fig:fun:prioinv} veranschaulicht die Prioritätsinvertierung in ihrem zeitlichen Verlauf.
+
+Eine Lösung für dieses Problem besteht in der Prioritätsvererbung, engl. priority inheritance, nach \cite{SRL90}. Danach erbt eine Task, die sich aktuell in einem kritischen Abschnitt befindet, kurzzeitig die höchste Priorität der wartenden Tasks für diesen kritischen Abschnitt. In Abbildung \ref{fig:fun:pip} lässt sich erkennen, dass Task L in dem Moment, in dem H auf C wartet, die hohe Priorität von H erbt. Somit liegt die Priorität von L ab diesem Zeitpunkt über der von M, so dass L nicht mehr im kritischen Abschnitt C verdrängt wird. Task L beendet ihre Operationen und entsperrt C. Die auf C wartende Task H wird sofort aktiviert. Diese kann nun C betreten, ihre Operationen abarbeiten und ihre Deadline einhalten.
+
+Die Unterstützung von Prioritätsvererbung erfordert umfassende Änderungen an den herkömmlichen Synchronisationsmechanismen der Betriebssysteme. Mutex-Objekte benötigen eine Möglichkeit zur Speicherung der Task, die sie aktuell sperrt. Ebenso müssen sämtliche relevanten Systemaufrufe diese Funktionen unterstützen. Weiterhin muss das Betriebssystem die dynamische Prioritätsänderung einer Task unterstützen.
+
+Als weiteres Verfahren zur Vermeidung von Prioritätsinvertierung sei \textit{priority ceiling} genannt. Da dieses Verfahren für diese Arbeit keine Rolle spielt, beschränkt sie sich auf die Nennung.
+\begin{figure}[hbtp]
+\centering
+\begin{minipage}[b]{.5\linewidth}
+\includegraphics[width=\linewidth]{prio_pip.eps}
+\end{minipage}
+\caption{Prioritätsvererbung}
+\label{fig:fun:pip}
+\end{figure}
+%===============================================================================================
+\section{Objektrepräsentation}
+\label{sec:fund:objrepr}
+Dieser Abschnitt betrachtet ausgewählte Möglichkeiten zur Repräsentation von strukturierten Daten und Objekten zwecks der Übertragung zwischen verschiedenen Rechnern.
+%===============================================================================================
+\subsection{SOAP}
+\label{sec:soap}
+\index{SOAP}
+Bei SOAP handelt es sich um ein Protokoll zur Repräsentation von strukturierten Daten im XML-Format. Es findet hauptsächlich beim Zugriff auf Webservices Verwendung. Hierbei handelt es sich um eine Schnittstellentechnik, die einen plattformunabhängigen Zugriff auf Daten oder Funktionen anderer Rechner bietet. In der Praxis verwendet SOAP oftmals HTTP als zugrundeliegendes Protokoll. Die genaue Beschreibung von SOAP findet sich in \cite{soap12}.
+
+Ein großer Vorteil von SOAP im Vergleich zu anderen Techniken liegt in der sog. losen Kopplung der System. Dies bedeutet, dass die Systeme, die am Datenaustausch beteiligt sind, sehr wenig Information von einander benötigen. Als Beispiel hierfür dient die sog. Endianess des jeweiligen Systems. Hierunter versteht man die Reihenfolge der einzelnen Bytes von Datenwörtern mit mehr als einem Byte im Arbeitsspeicher des Systems. Dafür existieren zwei mögliche Alternativen:
+\begin{description}
+\item[Big endian] Das Byte mit den höchstwertigen Bits befindet sich an der kleinsten Adresse.
+\item[Little endian]  Das Byte mit den kleinstwertigen Bits befindet an der kleinsten Adresse.
+\end{description}
+Somit ergeben sich zwei Darstellungen eines ganzzahligen Wertes mit 32 Bit, also 4 Byte:
+\begin{description}
+\item[Big endian] Byte4,Byte3,Byte2,Byte1
+\item[Little endian]  Byte1,Byte2,Byte3,Byte4
+\end{description}
+Bei der Übertragung eines Datenwortes bestehend aus mehreren Bytes muss also bekannt sein, um welche Repräsentation es sich handelt, um ggf. die Reihenfolge der Bytes zu korrigieren.
+
+Durch die textuelle Darstellung des Wertes im XML-Format umgeht SOAP dieses Problem. Hieraus ergeben sich allerdings auch einige Nachteile gegenüber der Darstellung in nativer Form. So steigt beispielsweise der Platzbedarf bei der Speicherung und Übertragung. Wie oben erwähnt benötigt ein Ganzzahlwert von 32 bit Breite, wie z. B. 1.000.000, 4 Byte. In diesem Beispiel 00 0F 42 40 in hexadezimaler Schreibweise. Der gleiche Werte in textueller Darstellung benötigt dagegen 7 Byte, 1 Byte pro Zeichen. Der Punkt als Trennzeichen dient hier nur der Lesbarkeit und ist nicht Bestandteil des Datums.
+
+Ebenso steigt der Aufwand bei der Verarbeitung des Wertes. Während bei der Verarbeitung der nativen Werte ggf. nur die Reihenfolge der Bytes anzupassen ist, erfordert die textuelle Darstellung wesentlich mehr Aufwand. Auf der Seite des Senders muss das Datum aus der nativen Darstellung in eine Zeichenkette umgewandelt werden und auf der Empfänger muss umgekehrt die Zeichenkette in eine Zahl umgewandelt werden.
+
+Für den Zugriff auf Funktionalität eines entfernten Rechners existiert eine Technik mit dem Namen XML-RPC \index{XML-RPC}. Hierbei handelt es sich um ein Request-Response-Verfahren bei dem der Client eine XML-Nachricht an den Server sendet, die den Funktionsaufruf und die Parameter beschreibt. Die Antwort des Servers enthält den Rückgabewert der aufgerufenen Funktion. Hierbei finden oftmals elementare und zusammengesetzte Datentypen nach dem SOAP als sog. Datentransferobjekte (DTO\index{DTO}) Verwendung. Datentransferobjekte repräsentieren allerdings nur die Daten eines Objekts, nicht aber seine Funktionalität, die in objektorientierten Entwürfen sehr oft vorhanden ist. In dieser Stelle soll nicht näher auf die Webservice-Technologie eingegangen werden. Der wichtige Aspekt für diese Arbeit liegt in der Beschränkung der Datentransferobjekte auf den Datenanteil eines Objekts. 
+%===============================================================================================
+\subsection{Objektserialisierung}
+\label{sec:serializedobjects}
+Zur Übertragung kompletter Objekte, d. h. Daten und Funktionalität, bieten viele Programmiersprachen die Möglichkeit der Serialisierung in einem Bytestrom im Gegensatz zu einem XML-Dokument. Dabei erfolgt die Speicherung des Objekts in einem Bytestrom z. B. einer Datei, aus dem es auf dem gleichen oder einem anderen Rechner wieder geladen werden kann. Hierbei geht allerdings die lose Kopplung verloren. D. h. es bestehen Einschränkungen bei der Wahl des speichernden und des ladenden Systems. Diese betreffen beispielsweise Endianess und Programmiersprache, die identisch sein müssen. Auch müssen beim Serialisieren und Deserialisieren die Klassendefinitionen überein stimmen. Besitzt die verwendete Programmiersprache keine eingebaute Objektserialisierung muss der Entwickler ggf. auf Bibliotheken zurückgreifen oder eine eigene Lösung implementieren. Die Spezifikation der Objektserialisierung der Programmiersprache Java findet sich in \cite{JOSS}.
+%===============================================================================================
+\subsection{Binäre Repräsentation}
+\label{sec:elf}
+Bei ELF \index{ELF} handelt es sich um ein binäres Dateiformat für ausführbare Dateien oder dynamisch ladbare Bibliotheken, sog. shared objects (SO\index{shared object}). Es enthält u. a.
+\begin{itemize}
+\item Informationen über die Prozessorarchitektur, für die das SO erstellt wurde.
+\item eine Tabelle mit Symbolen, die das SO enthält
+\item die Daten in binärer Form
+\item den ausführbaren Maschinencode
+\end{itemize}
+Aus dieser Auflistung lässt sich erkennen, dass eine ELF-Datei alle Informationen enthält, um ein Objekt zu beschreiben, nämlich Daten und Code. Eine detaillierte Beschreibung des ELF-Formats findet sich in \cite{TIS95}.
+
+Allerdings besteht hier eine sehr enge Kopplung zwischen beiden Systemen. Das Zielsystem muss genau mit dem System übereinstimmen, für das die ELF-Datei erzeugt wurde. Unterscheidet sich beispielsweise der Befehlssatz des Prozessors, kann der Code der ELF-Datei nicht korrekt ausgeführt werden. 
+
+ELF-Dateien lassen sich mit dem Linker für die Zielplattform erzeugen und mit dem Laufzeitsystem des jeweiligen Zielsystems laden. Für allen gängigen Unix und Linux-Varianten, die auf ELF basieren, existieren beispielsweise Funktionen, um shared objects zur Laufzeit eines Programmes zu laden.
+%===============================================================================================
+\section{CAN}
+\label{sec:fun:CAN}
+\index{CAN}
+Dieser Abschnitt bietet zuerst eine Beschreibung des CAN Busses, die für das Verständnis der weiteren Betrachtungen in dieser Arbeit nötig ist. Die Beschreibung beschränkt sich dabei auf die für diese Arbeit relevanten Aspekte. Eine vollständige Beschreibung des CAN Busses liefert \cite{bosch91can}.
+
+Anschließend erfolgt eine genauere Betrachtung des Verhaltens des Busses bei möglichst großer Auslastung.
+\subsection{Allgemeine Beschreibung}
+Bei CAN handelt es sich um einen seriellen Bus zur Datenübertragung über drei elektrische Leitungen (CAN\_HIGH, CAN\_LOW und CAN\_GROUND). Die Firma Bosch entwickelte CAN ursprünglich zur Vernetzung von ECUs in Kraftfahrzeugen. Alle an den Bus angeschlossenen ECUs teilen sich diese Leitungen, was eine Broadcast-Übertragung ermöglicht. Das bedeutet, dass ein Teilnehmer Daten versendet und alle anderen Teilnehmer diese Daten empfangen. Zu einem Zeitpunkt kann nur ein Sender aktiv sein.
+
+Die Übertragungsraten reichen von 125 kBit/s (Lowspeed) bis 1 MBit/s (Highspeed), mögliche Leitungslängen betragen zwischen 40 m bei Highspeed und 500 m bei Lowspeed.
+
+Die Datenübertragung auf dem CAN-Bus erfolgt immer in Form eines kompletten \textit{Frames}, im weiteren Verlauf der Arbeit auch Nachricht oder engl. message genannt. Dabei handelt es sich um eine definierte Abfolge von Bits, die auf dem Bus gesendet werden. Bestimmte Bitmuster beschreiben den Beginn und das Ende eines Frames. CAN unterscheidet folgende Frametypen:
+\begin{description}
+\item[Datenframe] Dient zur Übertragung von Daten durch das sendende Steuergerät
+\item[Remoteframe] Dient zur Anforderung von Daten durch das sendende Steuergerät
+\item[Errorframe] Das sendende Steuergerät hat einen Fehler im Netzwerk festgestellt
+\item[Overloadframe] Zwangspause zwischen Daten- und Remoteframes
+\end{description}
+Im Folgenden beschränkt sich die Betrachtung auf Datenframes. CAN unterscheidet grundsätzlich zwei Formate für Datenframes:
+\begin{description}
+\item[Standard] Die Länge der ID beträgt 11 Bit (siehe unten).
+\item[Extended] Die Länge der ID beträgt 29 Bit (siehe unten).
+\end{description}
+
+\begin{table}[htb]
+\begin{center}
+\begin{tabular}{|l|l|}
+\hline \textbf{Bitlänge} & \textbf{Bezeichnung} \\ 
+\hline 1 & SOF \\ 
+\hline 11 & ID \\ 
+\hline 1 & RTR \\ 
+\hline 1 & Identifier Extension \\ 
+\hline 1 & reserved \\ 
+\hline 1 & DLC \\ 
+\hline 0-64 & Data \\ 
+\hline 15 & CRC \\ 
+\hline 1 & CRC delimiter \\ 
+\hline 1 & ACK slot \\ 
+\hline 1 & ACK delimiter \\ 
+\hline 7 & End Of Frame \\ 
+\hline 3 & IFS \\ 
+\hline 
+\end{tabular}
+\caption{Format CAN Standarddatenframe}\label{tab:canformat}
+\end{center}
+\end{table}
+
+Das Feld ID dient dabei mehreren Zwecken.
+\begin{itemize}
+\item Es identifiziert einen Frame eindeutig
+\item Empfänger können anhand der ID für sie uninteressante Nachrichten filtern
+\item Die Priorität einer Nachricht entspricht ihrer ID
+\end{itemize}
+Wollen zwei Teilnehmer gleichzeitig Daten versenden, löst CAN diese Kollision mittels eines CSMA/CR\index{CSMA/CR}-Verfahrens namens Arbitrierung\index{Arbitrierung} oder auch Bit-Arbitrierung, das im Folgenden beschrieben wird.
+
+Sollen zu einem Zeitpunkt zwei Frames auf dem selben CAN-Bus versandt werden, stellt die Arbitrierung fest, welcher Frame die höhere Priorität besitzt und dieser höher-priore Frame wird auf dem Bus versandt. Eine numerisch kleinere ID bedeutet hierbei eine höhere Priorität. Bei der Arbitrierung senden alle Knoten, die einen Frame senden wollen, bitweise die ID des Frames auf den Bus. Sie beginnen alle mit dem MSB. Aufgrund der elektrischen Verschaltung des Bus als \textit{wired-AND}, also eine verdrahtete logische UND-Verknüpfung, liegt auf dem Bus ein logischer 0-Pegel, wenn nur ein Knoten eine 0 sendet. Stellt ein Knoten fest, dass er eine 1 gesendet hat, aber auf dem Bus ein 0-Pegel liegt, weiß er, dass die ID seiner Nachricht nicht die niedrigste ist und gibt den Sendeversuch auf. So scheiden Bit für Bit immer mehr Knoten aus, bis am Ende der Knoten mit der höchst-prioren Nachricht seinen Frame verschickt. Nach der vollständigen Übertragung des Frames beginnt eine neue Arbitrierung mit allen Knoten, die nun einen Frame senden möchten. Daraus lässt sich auch erkennen, dass der CAN-Bus nicht preemptiv ist. D. h. eine Nachricht, deren Versand begonnen wurde, wird zu Ende übertragen. Sollte während der Übertragung eine Nachricht höherer Priorität bereit zum Senden werden, muss sie die nächste Arbitrierung abwarten und verdrängt die aktuelle Übertragung nicht.
+
+Einen weiteren wichtigen Aspekt des CAN-Bus stellt das Bitstopfen oder engl. bit stuffing dar. Es dient zur Taktrückgewinnung bzw. Synchronisation zwischen den Knoten, da der CAN-Bus über keine Taktleitung verfügt. Deshalb müssen ausreichend oft Flankenwechsel in den Signalen vorkommen, nach denen sich die anderen Knoten synchronisieren. Um diese Flankenwechsel zu gewährleisten, wird nach 5 gleichartigen Bits ein inverses Bit in den Datenstrom eingefügt, das selbst wieder in das bit stuffing einbezogen wird. Dieser Vorgang findet im Allgemeinen direkt in der CAN-Hardware statt und ist transparent für darüber liegende Protokollschichten bzw. Applikationen. Die Abbildung \ref{fig:res:bitstuffing} zeigt ein konkretes Beispiel für dieses Verfahren.
+%==============================================================================================
+\subsection{Antwortzeiten}
+\label{sec:fun:rta}
+Dieser Abschnitt analysiert die maximalen Antwortzeiten (engl. worst case response time, WCRT\index{WCRT}) von Nachrichten auf dem CAN Bus. Diese Analyse geht von einem zyklischen Versand der Nachrichten in einem bestimmten Zeitintervall aus. Die Antwortzeit einer CAN-Nachricht bezeichnet hierbei die Zeitspanne vom Beginn eines Zyklus, also dem Zeitpunkt an dem die Nachricht versandt werden soll, bis zum vollständigen Versand der Nachricht auf dem Bus. Der Zeitpunkt, an dem eine Nachricht versandt werden soll und der Zeitpunkt, an dem sie tatsächlich auf dem Bus versendet wird, sind nicht zwangsläufig identisch. Diese Tatsache liegt darin begründet, dass CAN-Nachrichten unterschiedliche Prioritäten besitzen. Sollen zu einem Zeitpunkt zwei Nachrichten unterschiedlicher Priorität versandt werden, erfolgt zuerst der Versand der Nachricht mit höherer Priorität, danach der Versand der nieder-prioren Nachricht. Dies führt zu einer Verzögerung der nieder-prioren Nachricht, um die Zeitspanne, die der Versand der höher-prioren Nachricht benötigt.
+
+Wie der nachfolgende Abschnitt zeigt, hängt die Zeit, die der Versand einer CAN-Nachricht dauert, von variablen Faktoren ab, die sich nicht vorhersagen lassen. Deshalb gehen Literatur und Praxis vom schlechtesten Fall, also maximal möglicher Dauer, aus, um sichere Aussagen zu treffen.
+
+Die Zeitdauer für das Versenden von CAN Botschaften in einem Zyklus hängt von deren Anzahl ab. Es existiert allerdings eine Obergrenze für die Anzahl der Nachrichten, die in einem Zyklus versendet werden können. Die maximale Länge einer CAN Botschaft mit Standard Identifier beträgt 111 Bit %\ref{sec:fun:CAN}
+ plus stuffing Bits innerhalb der ersten 98 Bits, Start of Frame bis CRC inklusive. Diese Stopfbits stellen den variablen Anteil an der Übertragungsdauer dar.
+
+Nach \cite{springerlink:10.1007/s11241-007-9012-7} berechnet sich die maximale Anzahl Bits $N$ einer Nachricht nach der Formel $N=g+8*DLC+13+\lfloor \frac{g+8*DLC-1}{4} \rfloor$. $\lfloor \frac{a}{b} \rfloor$ bezeichnet hierbei einen Ganzzahloperator, der zur nächst kleineren ganzen Zahl von $\frac{a}{b}$ abrundet, also die Nachkommastellen abschneidet. Für einen Standarddatenframe mit 11 bit Identifier gilt $g=34$. Damit lässt sich die Formel zu $N=55+10*DLC$ vereinfachen. Somit ergibt sich im schlechtesten Fall eine Länge von $55+10*8=135$ Bits für eine Standarddatennachricht. Bei einer Übertragungsrate von 1 Mbit/s auf dem CAN Bus ergibt sich eine Bitdauer von 1 $\mu s$, also maximal 135 $\mu s$ für eine Standarddatennachricht. In einer Zykluszeit von 1 ms = 1000 $\mu s$ können somit im schlechtesten Fall maximal $\lfloor \frac{1000}{135} \rfloor =7$ Standarddatennachrichten mit jeweils 8 Byte Daten verschickt werden.
+
+Allgemein hängt die Übertragungsdauer $t_{msg}$ einer Nachricht von ihrer Länge in Bit $N$ und der Bitdauer $\tau_{bit}$ des Busses ab. Sie berechnet sich als $t_{msg}=N*\tau_{bit}$.
+
+Für einen Satz von $n$ Botschaften beträgt die Gesamtübertragungsdauer $t_{total}=\sum\limits_{i=1}^n t_{n}$
+
+Unter der Voraussetzung, dass die Zykluszeit einer Nachricht auch ihre Deadline darstellt, ermöglicht ein Verfahren nach \cite{springerlink:10.1007/s11241-007-9012-7} eine Überprüfung im Vorfeld, ob ein Satz von CAN-Nachrichten unter Einhaltung aller Deadlines versandt werden kann. Ein solches Verfahren trägt die Bezeichnung \textit{Schedulability Test} und basiert auf einer sog. Response Time Analysis, abgekürzt RTA \index{RTA}. Der Schedulability Test nach \cite{springerlink:10.1007/s11241-007-9012-7} verbessert nach Angaben der Verfasser ein vorheriges Verfahren, das unter gewissen Umständen zu optimistische Ergebnisse liefert, da jenes die Nicht-Preemptivität des CAN-Busses nicht konsequent beachtet.
+
+Die WCRT eine Nachricht $m$ trägt im Folgenden die Bezeichnung $R_m$. \cite{springerlink:10.1007/s11241-007-9012-7} geben folgende Gleichung zur Berechnung von $R_m$ an:
+\begin{equation}
+\label{eq:rm}
+R_m=\max\limits_{q=0\dots Q_{m}-1}\left( R_m\left( q\right) \right) 
+\end{equation}
+Wobei $q$ den Index einer bestimmten Instanz von $m$ bezeichnet und $Q_m$ die Anzahl der zu betrachtenden Instanzen von $m$. Somit ist die WCRT der Nachricht $m$ das Maximum der relevanten Antwortzeiten von $m$.
+Zur Bestimmung von $R_m\left( q\right) $ geben \cite{springerlink:10.1007/s11241-007-9012-7} folgende Gleichung an:
+\begin{equation}
+R_m\left( q\right) =J_m+\omega_m\left( q\right) -qT_m+C_m
+\end{equation}
+Dabei bezeichnet $J_m$ den Jitter von $m$. Damit ist die Zeitspanne vom Eintritt des Ereignisses, das den Versand von $m$ auslöst, bis zum tatsächlichen Einreihen von $m$ in die Sendewarteschlange gemeint. $\omega_m\left( q\right)$ stellt die Verzögerung dar, die die Instanz $q$ der Nachricht $m$ erfährt. $T_m$ bezeichnet die Zykluszeit von $m$ und $C_m$ die Übertragungsdauer von $m$ auf dem Bus.
+$\omega_m\left( q\right)$ lässt sich nach \cite{springerlink:10.1007/s11241-007-9012-7} mit folgender rekurrenten Gleichung berechnen:
+\begin{equation}
+\label{eq:omega_rek}
+\omega_m^{n+1}\left( q\right)=B_m+qC_m+\sum\limits_{\forall k \in hp \left( m\right) }
+\lceil \frac{\omega_m^n+J_k+\tau_{bit}}{T_k}\rceil C_k
+\end{equation}
+$hp \left( m\right)$ bezeichnet hierbei die Menge aller Nachrichten mit höherer Priorität als $m$ und $\lceil\frac{a}{b}\rceil$ einen Aufrundungsoperator, der zur nächsten Ganzzahl größer oder gleich $\frac{a}{b}$ aufrundet.
+Die Blockiert-Zeit $B_m$ einer Nachricht $m$ durch eine nieder-priore Nachricht, die gerade versandt wird, berechnet sich nach
+\begin{equation}
+B_m=\max\limits_{k\in lp \left( m\right) }\left( C_k\right) 
+\end{equation}
+mit $lp\left( m\right)$ als der Menge der Nachrichten mit kleinerer Priorität als $m$.
+Die Rekurrenz in Gleichung \ref{eq:omega_rek} startet mit $\omega_m^0\left( q\right) =B_m+qC_m$ für $q=0$ oder $\omega^{0}_m\left( q\right) = \omega_m \left(q-1\right)+C_m$ für $q>0$.
+
+Sie endet wenn $\omega_m^{n+1}\left( q\right) = \omega_m^{n}\left( q\right)$, also wenn die Verzögerung der Instanz $q$ von $m$ konvergiert. Die Rekurrenz endet auch im negativen Fall, wenn die Deadline $D_m$ von $m$ überschritten wird. In diesem Fall gilt $J_m +\omega_{m}^{n+1}\left( q\right) -qT_m+C_m > D_m$
+
+Die Anzahl der Instanzen $Q_m$ von $m$, die in Gleichung \ref{eq:rm} zu beachten sind, ergibt sich ebenfalls nach \cite{springerlink:10.1007/s11241-007-9012-7} aus der Gleichung
+\begin{equation}
+Q_m=\lceil\frac{t_m+J_m}{T_m}\rceil
+\end{equation}.
+Zur Berechnung von $t_m$ geben \cite{springerlink:10.1007/s11241-007-9012-7} ebenfalls eine rekurrente Gleichung
+\begin{equation}
+\label{eq:tm}
+t^{n+1}_m = B_m + \sum\limits_{\forall k \in hep\left( m\right) }\lceil \frac{t^n_m+J_k}{Tk} \rceil C_k
+\end{equation}
+an. $hep\left( m\right)$ bezeichnet die Menge aller Nachrichten mit gleicher oder höherer Priorität als $m$. Hier startet die Rekurrenz mit $t^0_m=C_m$ und endet, wenn $t^{n+1}_m=t^{n}_m$ konvergiert. Nach \cite{springerlink:10.1007/s11241-007-9012-7} konvergiert $t_m$, wenn die Busauslastung $U_m$ durch Nachrichten mit einer Priorität größer oder gleich der von $m$ kleiner als 1 ist.
+\begin{equation}
+U_m=\sum\limits_{\forall k \in hep \left( m\right) }\frac{C_k}{T_k}<1
+\end{equation}
+$t_m$ bezeichnet hierbei die Länge einer sog. \textit{busy period} des Priotitätslevels $m$. \cite{springerlink:10.1007/s11241-007-9012-7} definieren eine busy period als eine Zeitspanne mit folgenden Eigenschaften:
+\begin{enumerate}
+\item Sie startet an einem Zeitpunkt $t^s$, an dem eine Nachricht mit der Priorität von $m$ oder höher in die Sendewarteschlange eingefügt wird und keine Nachricht der Priorität von $m$ oder höher vor $t^s$ in die Warteschlange eingefügt wurde.
+\item Ein zusammenhängendes Zeitinterval, in dem keine Nachricht mit einer Priorität kleiner der von $m$ die Übertragung starten und die Arbitrierung gewinnen kann.
+\item Sie endet zum Zeitpunk $t^e$, zu dem der Bus unbenutzt ist und die nächste Übertragung und Arbitrierung beginnt. Dies gilt unter der Voraussetzung, dass keine Nachrichten der Priorität von $m$ oder höher vor $t^e$ in die Sendewarteschlange eingefügt wurden.
+\end{enumerate}
+Formal lässt sich eine busy period als halboffenes Interval zwischen $t^s$ und $t^e$ darstellen: $\left[ t^s, t^e \right)$. Innerhalb einer busy period des Prioritätslevels $m$ werden also alle Nachrichten der Priorität $m$ oder höher versendet, wenn sie vor dem Ende der busy period in die Warteschlange eingefügt wurden. Diese Nachrichten stören nachfolgende Instanzen der Nachrichten nicht, die am oder nach dem Ende der busy period in die Warteschlange eingefügt werden.
+
+Der Schedulability Test besteht nun darin, die WCRT jeder Nachricht nach Gleichung \ref{eq:rm} zu berechnen. Er gilt für eine Nachricht $m$ als bestanden, wenn $R_m \leq D_m$, andernfalls kann die Nachricht ihre Deadline nicht einhalten. Das Gesamtsystem aller Nachrichten gilt nur dann als \textit{schedulable}, wenn alle Nachrichten ihren Test bestehen.
+
+Dieses Verfahren gilt als pessimistisch, d. h. dass es im Zweifelsfall eine Konfiguration verwirft, die in der Realität u. U. lauffähig wäre. Dieses Verhalten wird auch als \textit{sufficient but not necessary} bezeichnet und stellt sicher, dass nur lauffähige Konfigurationen den Test bestehen.
+
+Der Abschnitt \ref{sec:res:rtaexample} liefert ein Beispiel für die Berechnung dieses Schedulability tests.
+