+--------------------> Proseminar
|
|           Konzepte der parallelen Programmierung
|
|
|                   Verteilte Systeme
|
|                Netzwerkbetriebssysteme, 
|                Verteilte Betriebssysteme, 
|                Topographie
|
|                     Marc Schanne
|                       24.01.96
|
v

Inhaltsverzeichnis

1. Allgemeines
   1. Definitionsversuch Verteiltes System
   2. Einsatzgebiete
   3. Vor- und Nachteile Verteilter Systeme
      Vorteile gegenüber Mainframe-Welt
      Vorteile gegenüber unabhängigen PCs
      Nachteile verteilter Systeme
2. Topographie
   1. Hardware
   2. Logische Topographie
   3. Klassifizierung
3. Netzwerkbetriebssystem
4. Verteiltes Betriebssystem
   1. Transparenz
   2. Flexibilität
   3. Zuverlässigkeit
   4. Performance
   5. Skalierbarkeit
5. Beispiele
6. Bibliographie

1. Allgemeines

1.1 Definitionsversuch Verteiltes System

Grundlegend für die weiteren "Uberlegungen soll hier eine lockere Begriffsdefinition für Verteilte Systeme" gegeben werden: Ein verteiltes System ist eine Sammlung voneinander unabhängiger Computer, die dem Benutzer des Systems den Eindruck vermitteln, es handle sich um einen einzigen Computer."[7]

1.2 Einsatzgebiete

Aus dieser recht allgemein gehaltenen Beschreibung für verteilte Systeme folgt eine Vielzahl von Einsatzgebieten. Ein paar Beispiele - Ort und Anwendung - sollen hier skizziert werden:

• In einer Universität oder der Abteilung einer Firma steht jedem Benutzer eine persön liche Workstation im Netz zur Verfügung. Ausserdem wird dynamisch, nach Bedarf, Rechenleistung zusätzlicher Prozessoren zugewiesen. Das System stellt sich aber als ganzes wie ein klassisches Einprozessor-Timesharing-System dar.
• Als Einsatzort lässt sich auch eine Bank mit einem weltweiten Filialennetz vorstellen. Jede Filiale besitzt einen Grossrechnern für die lokale Verwaltung, der aber über ein Netz mit allen anderen Filialstellen-Computern und dem Zentralrechner im Hauptsitz kommuniziert. So ist es möglich, dass jede Transaktion, unabhängig vom Aufenthalts ort des Kunden, wie in der heimatlichen Filiale verarbeitet werden kann.
• In der Fertigung eines Grossbetriebs arbeiten Roboter, die leistungsstarke Computer für Wahrnehmung, Planung, Kommunikation, und andere Aufgaben enthalten. Jeder Roboter ist zusätzlich mit dem Zentralrechner des Ersatzteilelagers verbunden und wird automatisch mit den nötigen Teilen versorgt.
• Als letztes Beispiel in dieser Reihe soll ein Reisebüro betrachtet werden: Die Daten über Flüge und Reservierungen werden in einer zentralen Datenbank gespeichert, können aber von den vernetzten lokalen PCs aus abgerufen und verändert werden.

1.3 Vor- und Nachteile Verteilter Systeme

Vorteile gegenüber Mainframe-Welt

• Wirtschaftlichkeit: Mikroprozessoren bieten ein besseres Preis-Leistungs-Verhältnis als zentralisierte Systeme.
• Geschwindigkeit: Absolut kann ein verteiltes System mehr Gesamtleistung bieten.
• Inhärente Verteilung (Dezentralisierung): Das Netz besteht aus dezentralen leistungs starken Workstations, nicht nur aus Terminals, die alle Berechnungen auf dem Gross rechner durchführen müssen.
• Zuverlässigkeit: Auch bei Ausfall eines Rechners kann das Gesamtsystem weiterar beiten.
• Inkrementelles Wachstum: Die Rechenleistung kann - abhängig vom Bedarf - schrittweise durch weitere Prozessoren erhöht werden.

Vorteile gegenüber unabhängigen PCs

• Gemeinsame Nutzung von Betriebsmitteln: Auf Pheripheriegeräte oder auch gespei cherte Daten kann gemeinsam zugegriffen werden.
• Kommunikation: Die Kommunikation unter den Benutzern durch netzweite Dienste (z.B. eMail) vereinfacht werden.
• Flexibilität: Es ist eine effektivere Lastverteilung über alle Computer möglich.

Nachteile verteilter Systeme

• Fehlende Software: Das Softwareangebot für verteilte Systeme (Betriebssysteme, Pro grammiersprachen und Applikationen) ist noch nicht gross.
• Netzwerk: "Uberlastungen oder Störungen des Netzwerks können die Performance des ganzen Systems stark beeinflussen. Ein Austausch oder eine Erweiterung des Kommunikationsnetzwerkes ist meist teuer.
• Sicherheit: Auch auf geheime Daten ist einfacher Zugriff möglich.

2 Topographie

2.1 Hardware

Die Hardware eines verteilten Systems kann durch einen Graphen dargestellt werden. Ein zelne Rechner/ Prozessoren (Hier eine Trennung vorzunehemen ist nicht sinnvoll. Alle Verbindungsstrukturen lassen sich sowohl auf autonome Rechner als auch auf einzelnen Prozessoren anwenden.) werden als Knoten und die sie verbindenden Kommunikations kanäle als Kanten gezeichnet. Die Struktur eines Graphen bezeichnet man als Topographie.

Im Folgenden werden einige spezielle regelmässige Verbindungsstrukturen vorgestellt. Diese werden aber (insbesondere bei grösseren Netzen) selten in Reinform aufgebaut. Es meist sinnvoller die Verbindungsstruktur am Nachrichtenaufkommen der einzelnen Rechner auszurichten. So entsteht eine unregelmässige Topographie. Abbildung 1: Busstruktur Abbildung 2: Ring mit 5 Elementen

• Bus-Netzwerke (Abbildung 1) sind wohl die bekannteste und einfachste Verbin dungsstruktur. Alle Rechner werden an die gleiche Leitung angeschlossen. Es ist keine Vermittlung der Daten notwendig: Jeder Rechner erhält alle Daten und filtert die für ihn bestimmten heraus. Wichtig ist, dass immer nur ein Rechner zu einer Zeit Daten senden darf. Dies führt zu einem Synchronisationsproblem. Ausserdem ist die Struktur bei mehreren Computern (>10) oder hohem Kommunikationsaufkommen leicht überlastet.
• Die Anordung der Rechner in einem Ring (Abbildung 2) bedingt die Weiterleitung von Nachrichten bis zum Zielrechner. Je Computer sind nur zwei Verbindungsleitun gen nötig, jedoch ist es möglich, dass eine Information die Hälfte der angeschlossen Rechner durchlaufen muss, bevor das Ziel erreicht ist.
• Bei einem vollständigen Graphen (Abbildung 3) ist jeder Knoten mit jedem ver bunden. Nachrichten werden direkt an den Empfänger geliefert, es ist deshalb keine Weiterleitung im System nötig.
• Gitter sind zwei- (oder auch mehr-) dimensionale Strukturen mit konstanter Anzahl der Verbindungen je Computer. Ungünstig ist die Entfernung zwischen den Compu tern an den Gitterenden. Das kann man umgehen, indem man den Kreis schliesst und zum Torus (Abbildung 4) übergeht.
• Ein m-dimensionaler Hypercube (Abbildung 5) besteht aus n = 2m Knoten. Um ihn zu erweitern, muss man die Struktur verdoppeln und die korrespondierenden Knoten verbinden. Ein Ergänzen einzelner Computer ist nicht möglich. Abbildung 3: Vollständiger Graph Abbildung 4: Gitter und Torus für n = 12 Abbildung 5: Hypercubus der Dimension 2 bis 4
• Der Binärbaum beansprucht nur 3 Verbindungen je Knoten und ist durch einfaches Anhängen leicht erweiterbar. Ein grosses Problem stellt aber der Flaschenhals an der Wurzel dar. Wenn mehrere Teilbäume gleichzeitig versuchen, über die Wurzel zu kommunizieren, kommt es zu Verzögerungen. Die Stern- oder Kettenstruktur sind extreme, entartete Baumformen. (Abbildung 6).
• Im Gegensatz zu den vorher beschriebenen statischen Verbindungsstrukturen ist der Kreuzschienenverteiler (Abbildung 7) ein dynamisches Netzwerk. Mit Schaltern versehen, ermöglicht er zur Laufzeit verschiedenen Verbindungsmuster. Er verbin det n Eingänge mit n Ausgängen. Diese können entweder durch- oder rechtwinklig geschaltet sein.
• Durch Verwendung von Delta-Schaltern - 2x2-Kreuzschienenverteilern - kann ein Delta-Netzwerk (Abbildung 8) gebildet werden. Vorteilhaft ist die geringe Anzahl von nur n=2*log(n) Delta-Schaltern. Nachteilig ist, dass nicht alle Permutationen von Verbindungen gleichzeitig möglich sind. Dadurch kommt es zu Blockierungen.

2.2 Logische Topographie

Analog zur physikalischen Topographie der Hardware kann man auch für die Software, für Prozesse (einfache Applikationen, Serverdienste, etc.) und deren Kommunikationskanäle (Nachrichten) eine Topographie erstellen.

Im `Idealfall' ist diese unabhängig von den physikalischen Gegebenheiten. Dieses Ziel wird aber von den meisten verteilten Systemen nicht vollständig erreicht. Hardwareabhängige Prozesse, die zum Beispiel nur auf einem speziellen Prozessor laufen oder eine bestimmtes Peripheriegerät bedienen, oder Prozesse, die nicht nur über Nachrichten, sondern auch über gemeinsam genutzte Daten im gleichen Speicher kommunizieren, sind örtlich gebunden. Ih re Verteilung wird damit eingeschränkt.

Wenn man die weitgehend flexible logische Topographie auf die Hardware abbildet, entsteht eine Konfiguration des verteilten Systems.

2.3 Klassifizierung

Zusätzlich zur Verbindungsstruktur der Hardware kann man eine weitere Einteilung für parallele und verteilte Computersysteme treffen, die sich haupsächlich auf die Möglichkeiten beim Speicherzugriff stützt: 1. Multiprozessorsysteme (eng gekoppelt: gemeinsam genutzter Speicher) 2. Multirechnersysteme (lose gekoppelt: privater Speicher, autonome Rechner)

Durch ähnliche Klassifikation im Softwarebereich lassen sich 3 wesentliche Kombinationen bilden:

• Bei lose gekoppelter Software auf einer lose gekoppelten Hardware spricht man von einem Netzwerkbetriebssystem (vgl. 3 Netzwerkbetriebssystem);
• eng gekoppelte Software auf der gleichen lose gekoppelter Hardware führt zu einem echten verteilten System (vgl. 4 Verteiltes Betriebssystem);
• und eng gekoppelte Software auf eng gekoppelter Hardware beschreibt Multiprozessor- Timesharing-Systeme, deren wesentlicher Unterschied eine zentrale Prozesswarteschlan ge darstellt (nicht Thema dieses Vortrags).

3 Netzwerkbetriebssystem Ein Netzwerkbetriebssystem ist mehr eine zusätzliche Betriebssystemfunktionsbibliothek als ein vollständiges Betriebssystem. Im Folgenden ist seine Funktionalität kurz zusam mengefasst:

• Es stellt zusätzliche (netzbetreffende) Dienste zur Verfügung.
• Die einzelne Workstation im LAN ist relativ unabhängig.
• Der Benutzer muss explizit netzwerkweite Kommandos eingeben, z.B.: rcp rechner1:datei1 rechner2:datei2 kopiert die Datei 1 auf Rechner 1 in die Datei 2 auf Rechner 2.
• Zusätzlich kann ein Netzwerkbetriebssystem noch einzelne Serverdienste (Fileserver, Netzwerkdrucker, etc.) für die Nutzung durch Clients im Netz zur Verfügung stellen.

4 Verteiltes Betriebssystem

Ziel eines verteilten Betriebssystems ist es, den Eindruck eines `einzigen' Timesharing- Systems zu vermitteln und nicht die Sammlung einzelner Maschinen im Netz. Dieses Ziel wird selten völlig erreicht, und nicht für jede Anwendung ist es auch wirklich sinnvoll.

Im Folgenden sind die wichtigsten Aspekte beim Systemdesign zusammengestellt. Es werden Vor- und Nachteile, sowie Möglichkeiten der Umsetzung angesprochen:

4.1 Transparenz

Transparenz, die einheitliche Systemsicht, kann auf zwei verschiedenen Ebenen realisiert werden. Am einfachsten ist es, die Verteilung vor dem Anwender zu verbergen. Wo, das heisst auf welchen Prozessoren, oder wie (Parallelität) ein Befehl ausgeführt wird, ist für den Benutzer uninteressant.

Auf einer niedrigeren Ebene kann man das System auch für Programme transparent erscheinen lassen. Das heisst, die Schnittstelle für Systemaufrufe kann so entworfen werden, dass die Existenz mehrerer Prozessoren nicht ersichtlich ist.

Transparenz (für Anwender und Programme) kann man auf mehrere Aspekte eines verteilten Systems beziehen:

• Von Ortstransparenz spricht man, wenn nicht erkennbar ist, wo sich die Systemres- sourcen wie etwa CPUs, Drucker, Dateien oder Datenbanken befinden. So darf es z.B. im Namen der Ressourcen keinen Hinweis darauf geben. Namen wie rechner1:datei1 sind nicht sinnvoll.
• Bei Migrationstransparenz können Ressourcen (physikalisch) verlagert werden, ohne dass sich ihr Name ändert.
• Replikationstransparenz verhindert, dass der Anwender erkennen kann, ob und wieviele Kopien einer Datei existieren.
• Verteilte Systeme sind fast immer Multiuser-Systeme. Die Nebenläufigkeitstrans- parenz verhindert automatisch Zugriffskonflikte bei gemeinsamer Nutzung von Res sourcen.
• Um die besondere Struktur eines verteilten Systems - grosse Anzahl parallel nutzba rer CPUs - auszunutzen, wird versucht eine Parallelitätstransparenz zu realisie ren. Aktionen sollen ohne Einwirken des Benutzers parallel ausgeführt werden. Dies auch für Programme transparent zu gestalten -nicht explizit in jeder Anwendung zu programmieren -, ist das Ziel für die Zukunft.

4.2 Flexibilität

Um das zweite Ziel, die Flexibilität des Systems, zu erreichen, tauscht man die derzeit weit verbreiteten monolithischen Kernel (z.B. UNIX), die die gesamte Betriebssystemfunktiona lität enthalten, gegen Microkernel und zusätzliche Server aus.

Der Mikrokernel bietet nur minimale Dienste, wie Interprozesskommunikation, grund legende Speicherverwaltung, Prozessverwaltung, Scheduling auf unterster Ebene und Low- Level-I/O-Routinen. Alle anderen Betriebssystemdienste werden als Server auf Benutzere- bene realisiert. Daraus ergibt sich eine modulare Struktur mit klaren Schnittstellen, die Implementierung, Installation, Fehlersuche, Ergänzen und Entfernen von Komponenten er- leichtert - das System flexibel macht.

4.3 Zuverlässigkeit

Die Zuverlässigkeit eines verteilten Systems soll in drei Aspekte gegliedert werden: 1.Die Verfügbarkeit, die Zeit, während das System zur Verfügung steht, kann bei einem verteilten System durch Redundanz kritischer Komponeten und durch die Ver teilung allgemein verbessert werden. Wenn eine Einzelkomponente ausfällt, bleibt das ganze System intakt. 2.Sicherheit von Daten und Ressourcen ist ein viel schwerwiegenderes Problem. So ist es in einem verteilten System z.B. für einen Server schwierig festzustellen, ob eine Anfrage wirklich vom angegebenen Absender stammt und ob die Operation erlaubt ist. Hier ist beim Systemdesign grösste Sorgfalt geboten. 3.Der dritte Aspekt der Zuverlässigkeit ist die Fehlertoleranz. Was passiert, wenn z.B. ein Server abstürzt und dann sofort neu bootet? Stürzen mit ihm auch die Anwendungen ab? In verteilten Systemen wird versucht, solch einen Fehler vor dem Anwender zu verbergen, so dass das System - vielleicht mit Performaceverlust - dennoch weiterläuft.

4.4 Performance

Um ein praktisch nutzbares System zu entwickeln, muss aber ausser den vorgenannten Aspek ten auch die Performance beachtet werden.

Hier kann es in einem verteilten System zu einer Vielzahl von Problemen kommen. Es muss sowohl der erhöhte Verwaltungsaufwand (im Vergleich zum Einzelprozessor), die Kommunikation zwischen parallelen Prozessen (Antwortezeiten), die Netzwerkkapazität als auch die Ausnutzung des verteilten Systems beachtet werden. Ein Ausweg ist die Granularität der einzelnen Operationen zu betrachten: 1.Fein-granulierte Parallelität: Es existiert eine grosse Anzahl kleiner Berechnun gen mit viel Interaktion. Bei Verteilung der Einzelberechnungen über mehrere Rechner wäre eine erhöhte Kom munikation über das Netzwerk die Folge und die Vorteile der parallen Ausführung schnell aufgebraucht. Hier ist eine Verteilung deshalb wenig sinnvoll. 2.Grob-granulierte Parallelität: Es gibt umfangreiche Berechnungen, eine geringe Interaktionsrate und wenig Daten. Hier ist die Verteilung, eine Ausführung der umfangreicheren Berechnungen auf schnel leren Prozessoren - auch weiter weg - günstiger.

4.5 Skalierbarkeit

Heutige verteilte Systeme sind für den Einsatz mit einigen hundert CPUs ausgelegt. Zukünf tige Systeme werden vielleicht eine ganz andere Grössenordung besitzen. Schon beim Sy stemdesign kann man dies berücksichtigen. Um Engpässe zu vermeiden, sollte man deshalb auf zentralisierte Daten/ Komponenten/ Algorithmen verzichten.

5 Beispiele

Zum Abschluss soll nun noch eine kleine, nichtrepräsentative Auswahl an Netzwerkbetriebs- systemen, verteilten Betriebssystemen und Programmierumgebungen kurz vorgestellt wer den. Für weitere Informationen sei auf entsprechende Literatur verwiesen.

• Athena, ein Projekt am M.I.T., ist ein Netzwerkbetriebssystem, entwickelt für ein grosses Netz von Workstations (bis zu 10000). Aus ihm sind viele bekannte, kommer zielle Softwarepakete entstanden, z.B. das X Window System, Kerberos (Authentifi zierung) und Hesio [2].
• Das Quasi-Realtime Netzwerkbetriebsystem QNX wird seit 1982 weiterentwickelt und bietet neben einem sehr kleinen Mikrokernel in der aktuellen Version 4.X POSIX- Kompatibilität [5].
• NetWare 4.1 von Novell, ein weiteres, und wohl das bekannteste Netzwerkbetriebs system, stellt diverse Serverdienste für ein Computernetz zur Verfügung [14].
• Das Projekt Amoeba - erstes verteiltes Betriebssystem in dieser Auswahl - wur de an der Vrije Universität Amsterdam, Niederlande, 1981 begonnen. Die aktuelle Version 5.X besitzt einen Mikrokernel, der auf jedem Prozessor läuft, und eine Men ge von Servern, für den Grossteil der herkömmlichen Betriebssystem-Funktionalität. Amoeba ist für Systeme mit sehr vielen CPUs, mit je eigenem Speicher, konzipiert und kann auch auf verteilten Systemen auf der Basis von WANs eingesetzt werden [8].
• Mach ist ein weiteres Mikrokernel-System. Entwickelt wurde es als Basis f"ur UNIX und andere Betriebssysteme, deren Emulation über eine Software-Schicht ausserhalb des Kernels realisiert wird. Mach, das auf relativ frühe Systeme zurückgeht, ist auch heute noch eines der wenigen maschinenunabhängigen Multiprozessorsysteme [9].
• Die Entwicklung von Chorus begann 1980 am französischen Forschungsinstitut IN- RIA. Die aktuelle Version 3 bietet neben der guten UNIX-Emulation und einem Sy stem für objektorientierte Programmierung noch spezielle Möglichkeiten für Echtzeit Applikationen: Diese können teilweise im Kernelmodus laufen und die Kontroll möglichkeit des Benutzers über Interrupts und den Scheduling-Algorithmus ist erhöht [10].
• Plan 9 von AT&T ist ein vollständig neu entwickeltes verteiltes Betriebsystem. Viele z.B. aus UNIX bekannte Ansätze sind hier konsequent weitergeführt [12].
• DCE (Distributed Computer Environment) der Open Software Foundation (OSF) ist anders als die vorher beschriebenen Systeme ein Betriebssystemaufsatz für verteilte Programmierung. So ist es möglich, bestehende Computernetze und Betriebssysteme für verteilte Applikationen zu nutzen [11].
• Das Universitätsprojekt PVM (Parallel Virtual Machine) verfolgt ein ähnliches Kon zept. Es simuliert auf einem heterogenen Computernetz einen parallelen Multipro zessor [3].

Bibliographie

1. Bräunl, Th.: Parallele Programmierung. Eine Einführung. pp. 39-56. Braunschweig, Wiesbaden: Vieweg, 1993.
2. Champine, G. A.: M.I.T. project Athena. A model for distributed campus computing. DEC, 1991.
3. Geist, A., Beguelin, A., et al.: PVM: Parallel Virtual Machine. A Users' Guide and Tutorial for Networked Parallel Computing. Cambridge: M.I.T. Press, 1994.
4. Herrtwich, R. G. und Hommel, G.: Kooperation und Konkurrenz. Nebenläufige, verteilte und echtzeitabhängige Programmsysteme. pp. 353-376. Berlin, Heidelberg: Springer-Verlag, 1989.
5. Hildebrand, D.: An Architectural Overview of QNX. QNX Software Systems LTD.
6. Müller-Stoy, P. (Hg): Architektur von Rechensystemen (Tagungsband). pp. 415-427. VDE-Verlag, 1990.
7. Tanenbaum, A. S.: Verteilte Betriebssysteme. pp. 15-50. München: Prentice Hall PTR, 1995.
8. ebd. pp. 441-500.
9. ebd. pp. 501-550.
10. ebd. pp. 551-602.
11. ebd. pp. 603-662.
12. Plan 9 from AT&T Bell Lab. FAQ. AT&T, 1995.
13. http://www.novell.com
14. news:comp.os.qnx

----------------------------------------------------------------
[home] [research] [guestbook] [contact]                   (c) SM