Analyse und Simulation des Schedulingverhaltens von Betriebssystemen mit Hilfe von SystemC

Inhaltsverzeichnis

1 Einleitung
1.1 Motivation der Arbeit
1.2 Zielsetzung
1.3 Aufbau der Arbeit

2 Grundlagen
2.1 Aufgaben von Betriebssystemen
2.2 Das Prozessmodell
2.3 Scheduling
2.3.1 Prozesswechsel
2.3.2 Strategien

3 Stand der Technik
3.1 Cheddar
3.2 FORTISSIMO
3.3 YASA 2
3.4 RTOS Modellierung auf Systemebene
3.5 Scheduling Simulation in SystemC
3.6 Automatische Codegenerierung
3.7 Statische Timinganalyse mit GROMIT
3.8 Fast Timed Software Model
3.9 Zusammenfassung

4 Methode zur Scheduling-Analyse und Simulation
4.1 Scheduling-Analyse
4.1.1 Vorbetrachtungen
4.1.2 Methode
4.1.3 Fehlerbetrachtung
4.1.4 Testverfahren
4.2 Simulation
4.2.1 Hardwareressourcen
4.2.2 Prozesse und Threads
4.2.3 Scheduling
4.2.4 Software-Hardware-Kommunikation
4.2.5 Anwendung auf die Schedulingsimulation

5 Details zur Implementierung
5.1 Messung und Auswertung
5.1.1 Fehlgeschlagene Versuche
5.1.2 Realisierte Zeitmessung
5.1.3 Das Messprogramm
5.1.4 Programmaufruf und Kommandozeilenparameter
5.1.5 Besonderheiten der Betriebssysteme
5.2 Simulation
5.2.1 Hardwareressourcen
5.2.2 Betriebssystem
5.2.3 Anwendung der libsystemcos

6 Ergebnisse
6.1 Windows XP
6.1.1 Interpretation der Messergebnisse
6.1.2 Der Schedulingalgorithmus
6.1.3 Modellierung und Simulation
6.2 QNX
6.2.1 Auswertung der Messergebnisse
6.2.2 Modellierung und Simulation
6.3 Linux
6.3.1 Auswertung der Messergebnisse
6.3.2 Modellierung und Simulation
6.4 Zusammenfassung

7 Bewertung der Ergebnisse
7.1 Vorbetrachtungen
7.1.1 FCFS
7.1.2 Präemptives Prioritätsscheduling
7.1.3 Round-Robin
7.2 Verifikationsmethode
7.2.1 Vorüberlegung
7.2.2 Mathematische Grundlagen
7.3 Ergebnis der Verifikation
7.3.1 Windows XP
7.3.2 QNX
7.3.3 Linux

8 Zusammenfassung und Ausblick
8.1 Rückblick
8.2 Zukünftige Arbeit

Literaturverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

Verzeichnis der Listings

Index

1. Einleitung

1.1 Motivation der Arbeit

Die Aufgaben von eingebetteten Systemen sind heutzutage so vielfältig, dass immer häufiger Teile der Implementierung als komplexe Softwaresysteme realisiert werden. Als Basis hierfür dient meist ein Betriebssystem, z.B. ein Echtzeitbetriebssystem wie QNX [1] aber auch herkömmliche Betriebssysteme wie Windows CE [2] oder Linux. Die Entscheidung für ein bestimmtes Betriebssystem hat unmittelbaren Einfluss auf die Wahl der zugrunde liegenden Hardware (das gilt natürlich auch umgekehrt). Dabei stellt sich stets die Frage nach dem benötigten Speicher, der Echtzeitfähigkeit und nicht zuletzt nach der "kleinstmöglichen" CPU, um den Stromverbrauch und die Abwärme so gering wie möglich zu halten. Um entscheiden zu können, welches Betriebssystem im konkreten Fall am besten geeignet ist, um z.B. Prozessen mit weichen Echtzeitanforderungen gerecht zu werden, ist es notwendig deren Scheduling-Verfahren zu kennen. Nur so kann man Rückschlüsse auf das Zeitverhalten des gesamten Systems ziehen.

Als Beispiel dient folgende Anwendung aus dem Automobilbereich: Das Multimediasystem eines Fahrzeugs soll unter anderem Signale der GPS-Antenne auswerten, die Kartendaten auf einem Display darstellen und nebenbei Musikdateien von einer Festplatte abspielen. Damit das Gerät zu jeder Zeit angemessen schnell auf Nutzereingaben reagiert und es nicht zu Aussetzern beim Abspielen der Musik kommt, ist die einfachste Variante, die CPU des Systems so zu wählen, dass die Aufgaben nur eine sehr geringe Belastung darstellen. Für eine effektive Nutzung der Ressourcen ist das jedoch keine akzeptable Lösung. Vielmehr möchte man einen Prozessor wählen, der optimal genutzt wird. Kennt man nun das Scheduling-Verhalten des in Frage kommenden Betriebssystems, kann man Aussagen darüber treffen, wie groß Puffer oder Caches sein müssen und mit welcher Frequenz die CPU getaktet werden muss, damit der entsprechende Prozess rechtzeitig die Audiodaten bekommt, wenn ihm z.B. nur alle 20 oder 130 Millisekunden Rechenzeit zugewiesen wird.

1.2 Zielsetzung

Die vorliegende Arbeit stellt ein Verfahren vor, mit dem man das Scheduling-Verhalten beliebiger Betriebssysteme mit Hilfe von Messungen in Erfahrung bringen kann. Dazu wird eine Menge von Parametern ermittelt, die Einfluss auf das Zeitverhalten eines Betriebssystems haben. Diese Parameter werden gemessen und ergeben einen Eigenschaftenvektor, der für jedes Betriebssystem charakteristisch ist. Dieser Eigenschaftenvektor beschreibt das Verhalten des Schedulers auf der Systemebene und stellt außerdem die Eingangsparameter für den Simulator dar.

Als Grundlage für die Simulation dient eine Erweiterung der SystemC-Klassen, die es zulässt Betriebssysteme, Prozesse und Hardwareressourcen abstrakt zu beschreiben und als Objekte in einer C++-Umgebung zu instanziieren. Mit den unterschiedlichen Eigenschaftenvektoren lässt sich so das Zeitverhalten von Prozessen in verschiedenen Betriebssystemen simulieren. Es ist also die Aufgabe herauszufinden, welche Parameter in diesem Zusammenhang eine Rolle spielen, diese zu messen oder vorzugeben und schließlich das Scheduling-Verhalten auf der Systemebene zu modellieren und zu simulieren. Dabei wird eine Genauigkeit von wenigen Millisekunden angestrebt, was völlig ausreichend ist, damit man sich in der Planungsphase eines Projektes einen groben Ãœberblick verschaffen und sich für eine Kombination aus Prozessor und Betriebssystem entscheiden kann. Es soll also möglich sein, verschiedene Szenarien durchzuspielen und beispielsweise die optimale Verteilung der Prioritäten der im System laufenden Programme vorzunehmen.

1.3 Aufbau der Arbeit

Die Arbeit ist folgendermaßen gegliedert: Zunächst werden einige grundlegende Zusammenhänge zwischen Betriebssystemen, Prozessen und Schedulingstrategien erläutert. Kapitel 3 gibt Auskunft darüber, welche Ansätze im Bereich der Simulation von Schedulingalgorithmen bereits existieren und wie sich die vorliegende Arbeit in das wissenschaftliche Umfeld einordnen lässt.

Das darauf folgende Kapitel gliedert sich in die Bereiche Analyse und Simulation. Im ersten Teil erfolgt die Beschreibung einer Methode, mit der sich der Schedulingalgorithmus eines Betriebssystems festellen lässt. Dabei werden Faktoren identifiziert, welche in diesem Zusammenhang überhaupt eine Rolle spielen. Der zweite Teil befasst sich mit dem Aufbau der verwendeten Simulationssoftware und deren Integration in die SystemC-Umgebung. Kapitel 5 gibt einen Einblick in die Implementierung der verwendeten Analyse- und Simulationssoftware.

Die Methode zur Schedulinganalyse wurde exemplarisch an drei Betriebssystemen getestet. In Kapitel 6 werden die Ergebnisse der durchgeführten Analyse präsentiert. Weiterhin wird erläutert, wie die charakteristischen Eigenschaften der einzelnen Betriebssysteme in der Schedulingsimulation modelliert wurden. Kapitel 7 stellt eine mathematische Methode vor, mit deren Hilfe sich die Genauigkeit der Simulation im Vergleich zu den Messergebnissen einschätzen lässt.

Abschließend enthält Kapitel 8 einen Rückblick sowie eine Beurteilung, ob die Ziele der Arbeit erreicht wurden. Weiterhin werden Anregungen zur weiteren Forschung an den Betriebssystemen sowie zur Erweiterung der Simulationssoftware gegeben.

[...]