Implementierung Und Parallele Verarbeitung Von Kommunikationssoftware

ISBN-13: 9783815420508 / Niemiecki / Miękka / 1993 / 196 str.

Michael Rupprecht

Opis

Die vorliegende Arbeit entstand wahrend meiner Tatigkeit als wissenschaftlicher Mitarbeiter am Lehrstuhl fur Informatik IV (Prof. Dr. O. Spaniol) der Rheinisch Westfalischen Technischen Hochschule Aachen. Herrn Prof. Dr. Otto Spaniol, der durch seine Anregungen, seine konstruktive Kritik und durch die mir gewahrten Freiheiten viel zum Gelingen dieser Arbeit beigetragen hat, gilt mein personlicher Dank. Herrn Prof. Dr. Wolfgang Effelsberg (Universitat Mannheim) danke ich besonders herzlich fur seine Bereitschaft zur Ubernahme des Korreferats und fur sein Interesse an meiner Arbeit. Danken mochte ich auch allen meinen Kollegen am Lehrstuhl und den Studenten, die auf die eine oder andere Weise einen Beitrag zum Entstehen und Gelingen der Arbeit geleistet haben und hier nicht alle genannt werden konnen. Besonders hervorheben mochte ich jedoch Herrn Kai Jakobs und Herrn Prof. Dr. Peter Martini, die mir insbesondere in der Anfangsphase bei der Auffindung meines wissenschaftlichen und beruflichen Weges hilfreich waren und Herrn Bernd Heinrichs und Herrn Christian Engel, die mir in ahnlicher Weise in der Schlussphase dieser Arbeit sehr geholfen haben. Ganz besonderes danken mochte ich den Menschen, die in anderer Weise beim Gelingen und beim Abschluss dieser Arbeit fur mich sehr wichtig waren. Namentlich erwahnen mochte ich hier nur meine Frau Cordula Rupprecht, die wahrscheinlich mehr zu dieser Arbeit beigetragen hat, als ich bis heute begriffen habe und meinem Vater, der durch mich nicht nur Probleme mit dem Korrekturlesen dieser Arbeit hatte."

Spis treści

1. Einleitung.- 2. Implementierung von Protokollen.- 2.1. Hardware-Realisierung.- 2.2. Software-Realisierung.- 2.2.1. Von der Spezifikation zur Software.- 2.2.1.1. Manuell kodierte Software.- 2.2.1.2. Benutzung einer Implementierungssprache und/oder eines entsprechend Implementierungswerkzeugs.- 2.2.1.3. Automatische Erzeugung des Codes.- 2.2.2. Betriebssystem.- 2.2.2.1. Prozeßablaufkontrolle.- 2.2.2.2. Interprozesskommunikation.- 2.2.2.3. I/O-Kontrolle.- 2.2.2.4. Speicherverwaltung.- 2.2.2.5. Timer-Verwaltung.- 2.2.2.6. Multiprozessorsystem.- 2.2.3. Aufbau von Kommunikationssoftware.- 2.2.3.1. Vertikale Ordnung.- 2.2.3.2. Horizontale Ordnung.- 2.2.3.3. Vergleich.- 2.2.4. Hardware-Anforderungen.- 2.3. Messung der Leistungsfähigkeit von Protokollimplementierungen.- 2.3.1. Nettodatenrate.- 2.3.2. Reaktionszeiten.- 2.4. Arbeiten zur Steigerung der Leistungsfähigkeit von Protokollimplementierungen.- 2.4.1. Standardkonforme Ansätze.- 2.4.1.1. Verbesserung der Methoden bei einer Software-Realisierung.- 2.4.1.2. Höhere Taktraten, neuere Technologien.- 2.4.1.3. Direkte Umsetzung in VLSI-Schaltungen.- 2.4.1.4. Multiprozessorarchitekturen für die Protokollverarbeitung.- 2.4.2. Nicht standardkonforme Ansätze.- 2.4.3. Parallele Verarbeitung von Kommunikationssoftware.- 2.4.3.1. Pipeline-Controller.- 2.4.3.2. Mehrere Prozessoren.- 2.4.3.3. Multiport-Speicher.- 2.4.3.4. Universeller Multiprozessor/Multiport-Speicher-Controller.- 2.4.3.5. Universeller Multiprozessor Controller.- 2.4.4. Die Verwendung von Transputern.- 2.4.5. Zusammenfassung.- 3. Spezifikation von Protokollen.- 3.1. Methoden zur Spezifikation.- 3.1.1. Nicht formale Protokollspezifikationstechniken.- 3.1.2. Formale Protokollspezifikationstechniken.- 3.2. Petrinetze.- 3.2.1. Grundbegriffe.- 3.2.2. Stellen/Transitionsnetze.- 3.3. Erweiterungen.- 3.3.1. Verbotskanten.- 3.3.2. Abräumkanten.- 3.3.3. Zeitbehaftete Petrinetze.- 3.3.4. Individuelle Marken und Prädikate.- 3.4. Produktnetze.- 3.4.1. Individuelle Marken.- 3.4.2. Markierung.- 3.4.3. Kapazität.- 3.4.4. Kantenanschrift.- 3.4.5. Zulässige Interpretationen.- 3.4.6. Schwellenmarkierung.- 3.4.7. Prädikate.- 3.4.8. Spezielle Kanten.- 3.4.9. Die Aktiviertheit einer Transition.- 3.4.10. Das Schalten einer Transition.- 3.4.11. Beispiel.- 3.4.12. Vereinfachung der graphischen Darstellung.- 4. Protokollimplementierung auf der Basis von Petrinetzen.- 4.1. Petrinetze als Programmiersprache.- 4.1.1. S/T-Netze.- 4.1.2. Produktnetze.- 4.1.3. Scheduler/Task-Konzept.- 4.1.4. Zusammenfassung.- 4.2. Funktionales Konzept der MDMA-Architektur.- 4.2.1. Aktionseinheiten.- 4.2.2. Globaler Datenspeicher.- 4.2.3. Entscheidungseinheit.- 4.2.4. Markenspeicher.- 4.2.5. Suchmodul.- 4.2.6. Sortierer.- 4.2.7. Suchspeicher.- 4.2.8. Zusammenfassung.- 4.3. Eingeschränktes Produktnetz.- 4.3.1. Problem: Testen aller gültigen Interpretationen.- 4.3.2. Problem: dynamische Speicherverwaltung.- 4.3.3. Lösung: Kapazität = 1.- 4.3.4. Lösung: Kapazität > 1.- 4.3.5. Formale Definition.- 4.3.5.1. Einfach-Marken-Stelle.- 4.3.5.2. Mehrfach-Marken-Stelle.- 4.3.6. Beispiele.- 4.3.7. Entflechtung.- 4.3.7.1. Entflechtung einer Eingangskante.- 4.3.7.2. Entflechtung einer Ausgangskante.- 4.3.7.3. Entflechtung der Verbots- und Abräumkanten.- 4.3.7.4. Beispiel.- 4.3.7.5. Schematisierte Kantenanschrift.- 4.3.7.6. Verbotsstellen im eingeschränkten, entflochtenen Produktnetz.- 4.3.8. Beispiel.- 4.3.9. PENCIL/C-Produktnetz.- 4.3.10. Zusammenfassung.- 5. Die Programmiersprache PENCIL.- 5.1. PENCIL/C als Erweiterung von C.- 5.1.1. Syntax — Definition.- 5.1.1.1. Transitionen.- 5.1.1.2. Stellen.- 5.1.2. Deklaration von Einfachstellen.- 5.1.3. Deklaration von Mehrfachstellen.- 5.1.4. Verwendung der Einfachstellen in der Aktivierungsfunktion.- 5.1.5. Verwendung des Transitionsrumpfes.- 5.1.6. Weitere Anmerkung zur Sprache PENCIL/C.- 5.1.6.1. Verwendung von Zeigertypen.- 5.1.6.2. Beschränkung der Markenanzahl.- 5.1.6.3. Ausführungsprioritäten.- 5.1.7. Beispiel.- 6. Die Verwendung von PENCIL.- 6.1. Umsetzung anderer Spezifikationsspachen in PENCIL.- 6.1.1. Erweiterte endliche Automaten.- 6.1.2. LOTOS.- 6.2. Granularität.- 6.2.1. Verschmelzen von Stellen.- 6.2.2. Verschmelzen von Transitionen.- 6.2.3. Vergröbern.- 6.2.4. Prädikatsvereinfachung.- 6.2.5. Zusammenfassung.- 6.3. Parallelität.- 6.3.1. Das Verschmelzen von Stellen und Transitionen.- 6.3.2. Erweiterte endliche Automaten.- 6.3.3. Betriebssystem.- 6.3.4. Parallelität innerhalb einer Verbindung.- 6.3.5. Parallelität des Referenzmodells.- 6.3.6. Parallelität der Verbindungen untereinander.- 6.3.7. Kommunikation zwischen Prozessen.- 6.3.8. Pipeline-Verarbeitung und identische Teilnetze.- 6.3.9. Zusammenfassung.- 7. Die MDMA-Architektur.- 7.1. Funktionsweise der Entscheidungseinheit.- 7.1.1. Quittung.- 7.1.2. Zeigerliste.- 7.1.3. Stellenliste.- 7.1.4. Transitionsliste.- 7.1.5. Auftragsliste.- 7.1.6. Auftrag.- 7.1.7. Aktivierungsbedingungen.- 7.1.8. Zusammenfassung.- 7.2. Modifikation der MDMA-Architektur.- 7.2.1. Vorteil: Reduzierung der Kopiervorgänge.- 7.2.2. Vorteil: Parallele Ausführung der Sortiererfunktionalität.- 7.2.3. Vorteil: Vereinfachte Auftragsvergabe.- 7.2.4. Vorteil: Reduzierter Synchronisationsaufwand.- 7.2.5. Zusammenfassung.- 7.3. Kommunikation.- 7.3.1. Synchronisation.- 7.3.2. Kommunikation zwischen Aktions- und Entscheidungseinheit.- 7.3.2.1. Vergabe von Aufträgen.- 7.3.2.2. Quittieren einer Schaltfunktion.- 7.3.2.3. Status der Warteschlangen.- 7.3.3. Externe Ereignisse.- 7.4. Hardware-Realisierung der MDMA-Architektur.- 7.4.1. Realisierung des MDMA-Konzepts mit der Basisarchitektur.- 7.4.2. Alternative Implementierung von PENCIL/C.- 7.4.3. Transputer.- 7.4.4. Spezialisierte MDMA Hardware-Architektur.- 7.4.4.1. Markenspeicher.- 7.4.4.2. Warteschlangen.- 7.5. Reaktionszeiten.- 7.5.1. Lösung für eine feste Kundenanzahl.- 7.5.2. Lösung mit veränderlicher Kundenanzahl.- 7.5.3. Lösung für ein Multiprozessorsystem.- 7.5.4. Auswertung.- 7.5.5. Zusammenfassung.- 7.6. Zusammenfassung.- 8. Ausblick und Schlußwort.- 9. Literatur.- 10. Anhang.- 10.1. Mathematische Symbole.- 10.1.1. Relationen.- 10.1.2. Quantoren.- 10.1.3. Logische Operatoren.- 10.1.4. Mengen.- 10.2. Schreibweisen für Petrinetze.- 10.3. Begriffe.- 10.4. Syntaxerweiterungen.