WWW.ABSTRACT.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Abstract, dissertation, book
 
<< HOME
CONTACTS



Pages:   || 2 | 3 | 4 | 5 |   ...   | 10 |

«Implementierung eines Echtzeit-IPC-Pfades mit Unterbrechungspunkten für L4/Fiasco René Reusner Juli 2005 Technische Universität Dresden Fakultät ...»

-- [ Page 1 ] --

Diplomarbeit

Implementierung eines Echtzeit-IPC-Pfades

mit Unterbrechungspunkten

für L4/Fiasco

René Reusner

Juli 2005

Technische Universität Dresden

Fakultät Informatik

Institut für Systemarchitektur

Professur Betriebssysteme

Betreuender Hochschullehrer: Prof. Dr. rer. nat. Hermann Härtig

Betreuender Mitarbeiter: Dr.-Ing. Michael Hohmuth

Erklärung

Hiermit erkläre ich, dass ich diese Arbeit selbstständig erstellt und keine anderen als die angegebenen Hilfsmittel benutzt habe.

Dresden, den 31. Juli 2005 René Reusner Inhaltsverzeichnis 1 Aufgabenstellung 11 2 Einleitung 13

2.1 Gliederung............................................ 14

2.2 Danksagung............................................ 14 3 Hintergrund 15

3.1 Fiasco............................................... 15

3.2 Aufbau von Fiasco........................................ 15

3.3 Synchronisation in Fiasco..................................... 18

3.4 IPC-Architektur.......................................... 20 4 Analyse der Verzögerungszeiten 25

4.1 Hardware............................................. 25

4.2 Software.............................................. 27

4.3 Zusammenfassung........................................ 30

–  –  –

7.1 Geschwindigkeitsvergleich bisheriger und neuer IPC-Pfad................... 61 1 Aufgabenstellung 2 Einleitung Mikrokerne sind kleine Betriebssystemkerne, die nur die notwendigen Grundfunktionen bereitstellen. Die höheren Funktionen des Betriebssystems werden durch Server bereit gestellt, welche sich in separate Adressräumen befinden. Es soll dadurch eine größere Modularität, Flexibilität und Sicherheit erreicht werden.

Ein Mikrokern der 1. Generation war Mach [ABB+ 86]. Mach entstand, indem man aus einem monolithischen System immer mehr Funktionen in Nutzerprogramme auslagerte und nur noch diese Funktionen im Kernel lies, welche nicht sicher auf Nutzerebene implementiert werden können. Mikrokerne der ersten Generation zeigten erhebliche Geschwindigkeitsdefizite, so dass in späteren Versionen wieder Funktionen zurück in den Kern verlagert wurden.

Mikrokerne der 2. Generation wurden unter Berücksichtigung von Geschwindigkeit [Lie93] und Minimalismus entworfen. Es wird dem Kern nur das hinzugefügt, dass nicht sicher im Nutzerbereich implementiert werden kann. Die Mikrokerne der 2. Generation zeigten, dass man mit ihnen auch effiziente Systeme bauen kann.

Der L4-Kern [Lie96] ist ein Mikrokern der 2. Generation. Er ist ein Nachfolger des L3-Systems [Lie88]. Der L4 Mikrokern stellt folgende Mechanismen zur Verfügung.

• Adressräume: Adressräume bilden die Schutzdomäne. Sie enthalten einen oder mehrere Threads.

Adressräume werden rekursiv durch Pager konstruiert, mit Sigma0 als initialen Adressraum. Bei einem Seitenfehler in einem Adressraum, generiert der Kern eine Nachricht an seinen Pager. Dieser kann dann in diesen Adressraum eine Seite einblenden, um den Seitenfehler aufzulösen. Damit ist es möglich, eine Hierarchie von Adressräumen rekursiv aufzubauen.

• Threads: Threads sind die Aktivitätsträger. Die Threads werden entsprechend ihrer Prioritäten vom Scheduler eingeplant und ausgeführt. Alle bisherigen L4-Implementationen verwenden Kernthreads, die dem Kern, im Gegensatz zu Threads auf Nutzerebene, bekannt sind. Die Threads werden im Kern durch eine Kontrollstruktur, dem Thread-Kontroll-Block (TCB), repräsentiert.

• IPC: Threads können miteinander mittels Interprozesskommunikation, engl. Inter Process Communication, kurz IPC, kommunizieren. Die L4-IPC bietet als Operationen das Senden send, das Empfangen receive und wait, und das kombinierte Senden und Empfangen, reply_wait und call an. Alle IPC-Operationen sind synchron, d.h. die Nachrichtenübertragung findet erst statt, wenn Sender und Empfänger bereit sind. Um nicht erfolgreiche IPC-Operationen nach einer bestimmten Zeit abzubrechen, können Timeouts gesetzt werden. Nachrichten können aus einfachen Registerwerten, Speicherinhalten und Flexpages1 [HWL96] bestehen. Für die Behandlung von IPCs ist der IPC-Codepfad des Kerns zuständig.

Ein L4-Mikrokern-System besteht aus dem L4-Kern, mehreren Servern, welche die Dienste wie Dateisysteme, Netzwerkdienste und grafische Oberfläche zur Verfügung stellen, sowie den Nutzerprogrammen.

Flexpages sind Speicherseiten, welche im Adressraum des Empfängers eingeblendet werden können.

2 Einleitung

Die Nutzerprogramme kommunizieren über IPC mit diesen Servern, wenn sie einen bestimmten Dienst in Anspruch nehmen wollen. Daher ist die IPC-Performance entscheidend für ein effizientes System.

Heute bezeichnet L4 eine Mikrokernfamilie. Es existieren verschiedene L4-Schnittstellen. Es gibt die originale Schnittstelle, V2 genannt, und die experimentellen Schnittstellen X.0 [Lie99] und X.2 [Tea05]. Weiterhin gibt es noch eine hoch experimentelle Schnittstelle L4.sec [Kau05], die besonders Rechte- und Ressourceprobleme adressiert.





2.1 Gliederung

In dieser Arbeit wird ein neuer IPC-Pfad für den L4-kompatiblen und echtzeitfähigen Mikrokern Fiasco implementiert. Im nachfolgendem Kapitel gebe ich einen Überblick über den Fiasco-Kern. Insbesondere umfasst dies alle Aspekte des Kerns, welche für die IPC-Performance und Echtzeit entscheidend sind. Eine kurze Erläuterung der vorhandenen IPC-Implementation wird auch gegeben. Im 3. Kapitel gehe ich auf die Eigenschaften von Hardware und Software, im Hinblick auf Echtzeit, ein. Das 4. Kapitel beschreibt den Entwurf des neuen IPC-Pfades und geht dabei auf verschiedene Probleme ein. Die Implementierung und einige damit verbundene Probleme werden im 5. Kapitel kurz erläutert. Die Auswertung im Hinblick auf Performance und Echtzeitfähigkeiten, im Vergleich zum bisherigen Kern, erfolgt im 6. Kapitel. Im 7. Kapitel erfolgt eine kurze Zusammenfassung, welche Ziele wurden erreicht und welche Probleme bestehen noch.

2.2 Danksagung

Hier möchte ich mich bei Prof. Dr. Hermann Härtig für die Möglichkeit bedanken, in der Betriebssystemgruppe zu arbeiten. Mein besonderer Dank gilt auch meinem Betreuer, Dr.-Ing. Michael Hohmuth. Weiterhin möchte ich mich bei Jean Wolter, Dr.-Ing. Frank Mehnert, Dietrich Clauß, Bernhard Kauer und Adam Lackorzynski bedanken.

3 Hintergrund

3.1 Fiasco Fiasco [Hoh98, Hoh02a] ist ein L4-kompatibler und echtzeitfähiger Mikrokern, entworfen und implementiert von Michael Hohmuth. Es war der erste L4-Kern, welche in einer Hochsprache geschrieben wurde und bei dessen Entwurf besonders Wert auf sehr gute Echtzeiteigenschaften gelegt wurde. Der Fiasco-Kern implementiert die V2, X0 und X.2-Schnittstelle. Es gibt auch eine stark abgeänderte Version, welche die L4.sec Schnittstelle implementiert.

Fiasco läuft auf IA-32, IA-64 [War02] und ARM [War03]. Eine x86-64 und Power-PC Portierung sind in Arbeit. Desweiteren Fiasco als Nutzerprogramm auf einem Linuxsystem [Ste02] verfügbar. Fiasco ist in C++ implementiert. Michael Peter implementierte zusätzlich einen IPC-Shortcut in Assembler [Pet02].

Fiasco ist ein Echtzeitkern und garantiert kurze und begrenzte Verzögerungszeiten bei der Zustellung von Ereignissen. Um dies zu erreichen, ist der Kern sehr oft unterbrechbar, nur kurze kritische Abschnitte werden durch das Sperren von Interrupts geschützt. Für größere kritische Abschnitte nutzt Fiasco nichtblockierende Synchronisation, deren Details in [Hoh02b] erläutert werden.

Einen anderen Ansatz als die L4-Kerne, insbesondere Fiasco geht der Fluke-Mikrokern. Der Fluke-Kern bietet nur atomare Operationen an, längere Systemaufrufe werden in mehrere atomare Teiloperationen aufgespalten [BF98]. Der Zustand zwischen diesen Operationen wird vollständig zum Nutzer exportiert, so dass der Kern sich keine Zustände im Kern merken muss.

3.2 Aufbau von Fiasco Adressräume Adressräume bilden die Schutzdomäne und enthalten einen oder mehrere Threads, die Aktivitätsträger. Die V2-Schnittstelle unterstützt maximal 128 Threads pro Adressraum, die V4-Spezifikation setzt keine solche Grenze. Für das Einblenden und Entfernen von Flexpages in anderen Adressräumen, verwaltet der Kern eine Mapping-Datenbank, wo für jede physische Speicherseite ein Mapping-Baum angelegt wird. Wird eine Flexpage entfernt, wird über diesen Baum iteriert, und die Seite wird aus betroffenen Unterbäumen entfernt, oder deren Rechte modifiziert.

Der Adressraum ist auf der IA-32 Architektur in einen, drei Gigabyte großen, Nutzeradressraum und in einen, ein Gigabyte großen, Kernadressraum aufgeteilt. Der Kernadressraum ist für den Nutzer nicht zugreifbar und ist in jedem Adressraum eingeblendet.

Er enthält den TCB-Bereich und die IO-Bitmap, sowie die Region für den verfügbaren physischen Kernspeicher, siehe Abb. 3.1. In einigen unbenutzten Einträgen des Seitenverzeichnis, werden auch Task-spezifische Variablen eingetragen.

3 Hintergrund

–  –  –

Threads Threads sind die Aktivitätsträger, und können erzeugt, verändert und gelöscht werden. In der V2 und X0Spezifikation erfolgt dies über den thread_ex_regs-Systemaufruf. In der X.2-Spezifikation dient thread_ex_regs nur zum Modifizieren von Threads, Erzeugen und Löschen erfolgt durch Thread_control-Systemaufruf.

Jeder Thread wird durch seinen TCB repräsentiert, welcher im TCB-Bereich des Kernadressraumes zu finden ist. Der TCB besteht aus einem Thread-Objekt, welches Thread-spezifische Variablen enthält, und dem Kernstack dieses Threads.

Fiasco implementiert das “Prozessmodell”, d.h. jeder Thread besitzt einen Kernstack. Darauf wird der aktuelle Zustand des Threads automatisch gesichert, ein Umschalten der Threads erfolgt durch Umschalten des Kernstacks. Dadurch ist unterbrechbarer Kerncode sehr einfach zu implementieren, da der Zustand des Threads jederzeit auf dem Stack gespeichert ist. Der Gegensatz dazu ist das “Interruptmodell“. Hier gibt es nur einen Kernstack pro CPU. Der Zustand eines Threads muss beim Kontextwechsel explizit in einer Continuation1 gesichert werden. Daher kann dieser Thread nur an dafür vorbereiteten Punkten unterbrochen werden.

Die Klasse Thread ist von den Klassen Receiver und Sender abgeleitet, siehe auch Abb. 3.2. Diese beiden Klassen entsprechen der Empfänger- und Senderrolle einer IPC-Operation. Die Klasse Receiver ist weiterhin von Context abgeleitet. Die Klasse Context ist der Ausführungskontext. Sie stellt den den Scheduler (schedule)und Funktionen zum Umschalten des Ausführungskontextes (switch_to, switch_exec) zur Verfügung.

Details sind in [Hoh02a] zu finden.

Ein Thread kann sich in verschiedenen Zuständen befinden, diese werden durch eine Kombination von Flags im Zustandswort der Context-Klasse beschrieben.

Continuation: Eine Datenstruktur, welche die benötigte Informationen enthält, um den Zustand des Threads wiederherzustellen und die Operation fortzusetzen.

–  –  –

Abbildung 3.2: Übersicht über die benötigten Klassen und deren Beziehungen.

Interrupts Interrupts werden in L4 auf IPC abgebildet. Ein Thread kann sich mit einem Interrupt assoziieren. Er bekommt eine Nachricht zugestellt, wenn dieser Interrupt ausgelöst wurde. Unterbrechungen werden durch Interruptdeskriptoren, die Klasse Irq, dargestellt Die Klasse Irq ist von Sender abgeleitet, und besitzt damit auch die Fähigkeit, IPC-Nachrichten zu verschicken. Die Klasse Dirq leitet von Irq ab, und ihre hit-Methode ist für die Zustellung der Nachricht zuständig, welche aufgerufen wird, wenn ein Interrupt auftritt.

Scheduling

Scheduling umfasst den Bereich des Kerns, welcher sich mit der Auswahl und Ausführung von Threads befasst. Der Scheduler wird durch die schedule-Funktion implementiert. Die Scheduling-Informationen wie Priorität, Zeitdauer und Besitzer dieser Zeitscheibe, sind im Scheduling-Kontext, repräsentiert durch die Klasse Sched_context, getrennt vom TCB abgelegt.

Neben dem normalen Scheduling-Kontext, der im TCB des Threads aggregiert ist, kann ein Thread über zusätzliche Real-Time-Scheduling-Kontexte verfügen. Ein Zeiger im TCB zeigt stets auf den aktiven Sched_context dieses Threads. Details dazu können in [Ste04] nachgelesen werden. Wenn ein Real-Time-SchedulingKontext abgelaufen ist, wird eine Preemption-IPC an den Preempter des Besitzer-Threads generiert.

Es werden 256 Prioritäten zur Verfügung gestellt. Der Scheduler wählt immer den Thread mit der höchsten Priorität aus. Threads mit gleicher Priorität werden nacheinander, mit einer Round-Robin-Strategie, ausgeführt.

3 Hintergrund Zeitgeber Die schedule() Funktion wird am Ende einer Zeitscheibe durch den Zeitgeber aufgerufen, um einen neuen Thread auszuwählen. Der Zeitgeber kann auf IA-32 drei verschiedene Quellen nutzen, den PIT2, die CMOS Echtzeituhr (RTC) und die Local-APIC3 der CPU. Der APIC-Timer kann als periodischer oder als One-ShotTimer konfiguriert werden. Bei den periodischen Zeitgebern, beträgt die Frequenz 1000Hz (PIT) oder 1023Hz (RTC), so dass die Zeitgeber-Routine rund jede Millisekunde aufgerufen wird. Bei dem One-Shot-Timer wird immer nur ein Interrupt ausgelöst. Der Zeitgeber wird dann auf das nächste Ereignis neu programmiert. Dies kann das Ende der neuen Zeitscheibe oder der Ablauf eines Timeouts sein. Der “One-Shot-Timer” bietet eine Genauigkeit für Timeouts im Bereich von Mikrosekunden an. Man kann die Timeouts auf eine Mikrosekunde spezifizieren, jedoch begrenzen die Verzögerungszeiten des Kerns die erreichbare Genauigkeit.

Ready-Liste

Die Bereitwarteschlange (Ready-Liste) enthält alle ausführbaren Threads. Es gibt jedoch eine Ausnahme, der aktuell aktive Thread muss nicht in der Ready-Liste enthalten sein. Ferner können in der Ready-Liste auch nichtbereite Threads enthalten sein. Sobald der Scheduler beim Iterieren über die Ready-Liste einen solchen blockierten Thread entdeckt, wird dieser nachträglich aus dieser Liste entfernt.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 10 |


Similar works:

«Prom.-Nr. 1.993 Betriehswirtschaftliche Auswirkungen und Erfolg der Bodenmeliorationen in einer Gemeinde des Aargauer Tafeljuras VON DER EIDGENÖSSISCHEN TECHNISCHEN HOCHSCHULE IN ZÜRICH ZUR ERLANGUNG DER WÜRDE EINE S DOKTORS DER TECHNISCHEN WISSENSCHAFTEN GENEHMIGTE PROMOTIONSARBEIT VORGELEGT VON WILI.I SOMMERAUER DIPL.ING.-AGR. VON ZÜRICH Referent: Herr Prof. Dr. Osk. Howald Korreferent: Herr Dip!.-Ing. E. Tanner VERBANDSDRUCKEREI AG BERN 1951 Zusammenfassung Die wichtigsten Ergebnisse...»

«MOUSE BIOMETHODOLOGY Marcel I. Perret-Gentil, DVM, MS University Veterinarian & Director Laboratory Animal Resources Center The University of Texas at San Antonio (210) 458-6173 larc@utsa.edu PURPOSE OF THIS DOCUMENT This is a handout that accompanies a hands-on mouse biomethodology workshop in the Laboratory Animal Resources Center (LARC). OBJECTIVES A. Instruct participants in methods of safe, humane handling and restraint. B. Instruct participants in substance administration to include...»

«Masterarbeit zur Erlangung des Mastertitel der Technischen Fakultät der Albert-Ludwigs-Universität Freiburg im Breisgau Mitigating Feature Exclusion to Improve Hypernymy Recognition Max Lotstein 17.07.2015 Albert-Ludwigs-Universität Freiburg im Breisgau Technische Fakultät Institut für Informatik Dekan Prof. Dr. Hannah Bast Referenten Prof. Dr. Joschka Bödecker Datum der Promotion (only necessary for final publication) 07.01.2015 “I, for one, welcome our new computer overlords.” -Ken...»

«LUDWIG-MAXIMILIANS-UNIVERSITÄT MÜNCHEN Department “Institut für Informatik” Lehrund Forschungseinheit Medieninformatik Prof. Dr. Heinrich Hußmann Diploma Thesis Conception and Implementation of a Visual Editor for Topic Maps Thorsten Witt wittt@cip.ifi.lmu.de Bearbeitungszeitraum: 1. 04. 2009 bis 30. 09. 2009 Betreuer: Prof. Dr. François Bry, Dipl.-Inf. Ralf S. Engelschall (Capgemini-sd&m) Verantw. Hochschullehrer: Prof. Dr. François Bry Abstract Topic Maps offer mechanisms to index...»

«Thermo mechanical investigations and predictions for oxygen transport membrane materials Von der Fakultät für Georessourcen und Materialtechnik der Rheinisch -Westfälischen Technischen Hochschule Aachen zur Erlangung des akademischen Grades eines Doktors der Ingenieurwissenschaften genehmigte Dissertation vorgelegt von Master of Mechanical Engineering Goran Pećanac aus Split, Republik Kroatien Berichter: Univ.-Prof. Jochen M. Schneider, Ph.D. Univ.-Prof. Dr.-Ing. Tilmann Beck Tag der...»

«Schlussbericht zu dem IGF-Vorhaben Beherrschung stark korrelierter Logistikund Produktions-Prozesse (AutokorrelierteAuftragsstroeme) der Forschungsstelle(n) (1) Technische Universität Dresden, ITLA, Professur für Technische Logistik (3) Universität der Bundeswehr München, Institut für Technische Informatik Das IGF-Vorhaben 17344BR der Forschungsvereinigung Logistik wurde über die im Rahmen des Programms zur Förderung der Industriellen Gemeinschaftsforschung (IGF) vom aufgrund eines...»

«Prof. Deborah Mutnick English Composition 16C.001 Office: H459; Hours MW 1-2 p.m. MW 10-11:15; 11:15-12:50 Email: deborah.mutnick@liu.edu Fall 2013 Phone: 718.488.1110 Room H215 Pathways to Freedom Stories of Struggle and Protest in Brooklyn and Beyond Course Description Welcome to English 16C, a composition course that will introduce you to key aspects of academic writing (inquiry, analysis, synthesis, and argument); critical thinking (Abstract reasoning, evaluation, thesis development);...»

«SÉRIE ANTROPOLOGIA Continuity, integration and expanding horizons Stanley J. Tambiah (interviewed by Mariza Peirano) Brasília Stanley J. Tambiah is the Esther and Sidney Rabb Professor of Anthropology at Harvard University. He received his undergraduate education at the University of Ceylon (Sri Lanka) and his Ph.D. from Cornell University (1954). Having served as a UNESCO technical assistance expert in Thailand from 1960 to 1963, he joined the faculty at the University of Cambridge, where he...»

«“Interaction between water related informal processes and water management: the example of Hyderabad, India” Von der Fakultät für Georessourcen und Materialtechnik der Rheinisch -Westfälischen Technischen Hochschule Aachen zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaften genehmigte Dissertation vorgelegt von M.A. Kilian Alexander Christ aus Heidenheim Berichter: Univ.-Prof. Dr. rer. nat. Dr. h. c. (USST) Rafig Azzam Univ.-Prof. Dr. phil. Martina...»

«Lehrstuhl für Bildverstehen und wissensbasierte Systeme Institut für Informatik Technische Universität München Integration of Programming and Learning in a Control Language for Autonomous Robots Performing Everyday Activities Alexandra Kirsch Vollständiger Abdruck der von der Fakultät für Informatik der Technischen Universität München zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaften (Dr. rer. nat.) genehmigten Dissertation. Vorsitzender: Univ.-Prof. Dr....»

«Landau’s “Grundlagen der Analysis” from Automath to lambda-delta Ferruccio Guidi Technical Report UBLCS-2009-16 September 2009 Department of Computer Science University of Bologna Mura Anteo Zamboni 7 40127 Bologna (Italy) The University of Bologna Department of Computer Science Research Technical Reports are available in PDF and gzipped PostScript formats via anonymous FTP from the area ftp.cs.unibo.it:/pub/TR/UBLCS or via WWW at URL http://www.cs.unibo.it/. Plain-text abstracts...»

«CMOS-Chip Based Printing System for Combinatorial Synthesis Vom Fachbereich Maschinenbau an der Technischen Universität Darmstadt zur Erlangung des akademischen Grades eines Doktor-Ingenieurs (Dr.-Ing.) genehmigte Dissertation vorgelegt von Master of Science Yun-Chien Cheng aus Taiwan Berichterstatter: Prof. Dr.-Ing. Edgar Dörsam Mitberichterstatter: Prof. Dr. Katja Schmitz Datum der Einreichung: 30.04.2012 Datum der mündlichen Prüfung: 04.07.2012 Darmstadt August 2012 D17 CMOS-Chip Based...»





 
<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.