|
1. Begriffe
Sequentielles Programm: Eine Liste von Anweisungen, die sequentiell
ausgeführt werden.
Prozess: Die Ausführung eines
sequentiellen Programms
Nebenläufiges Programm: Zwei
oder mehr sequentielle Programme, die als nebenläufige
Prozesse ausgeführt werden. Hier ist Synchronisation
erforderlich. Man unterscheidet folgende zwei Fälle bei
nebenläufigen Prozessen: Prozesse nutzen einen gemeinsamen
Prozessor und Prozesse nutzen unterschiedliche Prozessoren,
d.h. werden echt parallel ausgeführt. Bei Prozessen,
die unterschiedliche Prozessoren benutzen, unterscheidet man
Multiprocessing, Parallel Processing und Distributed Processing.
Bei Multiprocessing haben die Prozessoren
gemeinsamen Speicher.
Unter Parallel Processing versteht
man Prozessoren, die keinen gemeinsamen Speicher haben aber
über ein schnelles, Interkonnektionsnetzwerk verbunden.
Falls Prozessoren keinen gemeinsamen
Speicher haben und über ein Rechnernetz (LAN, MAN, WAN)
miteinander verbunden sind, so spricht man von Distributed
Processing.
Kooperation: Wenn Prozesse zusammenarbeiten,
um ein gemeinsames Ziel zu errechen, so spricht man von Kooperation.
Konkurrenz: Prozesse konkurrieren
um die Benutzung von Ressourcen.
Kooperation und Konkurrenz schließen
einander nicht aus.
Kommunikation: Kommunikation ist der
Austausch von Information zwischen Prozessen.
Synchronisation: Prozesse synchronisieren
sich auf Ereignisse, wobei Prozesse Ereignisse herbeiführen
können. Prozesse können bis zum Eintritt eines Ereignisses
verzögert werden.
2. Kooperationsformen
2.1 Produzenten/Konsumenten-Systeme
Der Konsument nimmt Daten auf, die
vom Produzenten erzeugt wurden. Hier genügt ein unidirektionaler
Kanal.
2.2 Pipeline-Modell
Eine Pipeline kann man sich als ein
unidirektionalen Kanal vorstellen.
2.3 Client/Server-Modell
Der Server bietet seinen Service einer
Menge a priori unbekannter Klienten an. Service bezeichnet
die Software-Instanz, die auf einer oder mehreren Maschinen
ausgeführt wird. Der Server ist eine Maschine, die Service-Software
ausführt. Der Klient ist der Nutzer eines Services.
3. Kommunikationsmuster
3.1 1-to-1
Senden an genau einen Prozess.
3.2 Rundsenden (broadcast)
Senden an alle Prozesse
3.3 Mehrfachsenden (multicast)
Senden an eine Gruppe G von Prozessen. Es gilt : 1 < |G|
< n
4. Kommunikation und Synchronisation: Konzepte
Es gibt zwei Möglichkeiten Kommunikation und Synchronisation
zu realisieren. Der erste Ansatz ist mittels gemeinsamen Speicher.
Techniken dazu sind Semaphore, Monitore und Pfadausdrücke.
Der zweite Ansatz ist Kommunikation und Synchronisation mittels
Nachrichtenaustausch. Da gibt es die Konzepte von Nachrichten,
RPC, Rendezvous und virtuellem gemeinsamen Speicher.
Beispiel: In dem oberen Beispiel findet die Kommunikation
durch Schreiben und Lesen des gemeinsamen Speichers statt.
Synchronisiert wird auf Zustandsänderungen des gemeinsamen
Speichers. Als Synchronisationskonzepte kommen hier zum Einsatz:
Semaphore, Monitore, Pfadausdrücke usw.
Beispiel: Kommunikation und Synchronisation findet durch den
Austausch von Nachrichten statt - Nachrichtenaustausch = Kommunikation
+ Synchronisation. Kommunikation durch das Senden und Empfangen
von Nachrichten. Synchronisiert wird auf Sende und Empfangsereignisse.
Wir verfolgen den Ansatz der Kommunikation
und Synchronisation mittels Nachrichtenaustausch. Auf den
Ansatz "gemeinsamer Speicher" wird hier nicht näher
eingegangen.
5. Basisoperationen für den Nachrichtentransfer
Für den Nachrichtenstransfer gibt es zwei Basisoperationen,
nämlich send und receive.
send expression to destination
Die Nachricht enthält den Wert
von expression. Mit destination spezifiziert man das Ziel
oder die Ziele.
receive variable from source
Die Nachricht wird in variable empfangen.
Source spezifiziert, von welcher Quelle die Nachricht kommen
soll.
Aus der obigen Abbildung ist zu entnehmen, dass die Operationen
nochmals in blockierend und nicht-blockierend unterteilt werden.
Doch zuvor noch grundsätzliche
Gedanken. Wohin kann die Sendevariable kopiert werden?
Beispiel 1:
Beispiel 2:
Die Beispiele zeigen zwei Möglichkeiten.
Beim ersten Beispiel wird die Sendevariable direkt in die
entsprechende Empfangsvariable kopiert. Das zweite Beispiel
zeigt den Fall, in der die Sendevariable in einen Puffer kopiert
wird.
nicht-blockierende Sendeoperation
Der Sender wird nur für die Dauer des Kopierens verzögert.
blockierende Sendeoperation
Der Sender wird so lange verzögert, bis die entsprechende
Empfangsanweisung ausgeführt wird.
blockierende Empfangsoperation
Der ausführende Prozess wird so lange blockiert, bis
Nachricht eingetroffen ist.
nicht-blockierende Empfangsoperation
Der ausführende Prozess wird keinesfalls blockiert. Hier
gibt es zwei Varianten.
Variante 1: Falls eine Nachricht vorhanden ist, wird sie empfangen,
sonst Return Code.
Variante 2: Receive signalisiert die Empfangsbereitschaft.
Wenn die Nachricht eintrifft, wird der Empfangsprozess unterbrochen.
6. Synchroner und asynchroner Nachrichtenaustausch
6.1 Synchroner Nachrichtenaustausch
Beim synchroner Nachrichtenaustausch
benutzen Sender und Empfänger blockierende Sende- und
Empfangsoperationen. Wichtig ist, das hier keine Pufferung
notwendig ist. Denn die Nachricht kann direkt vom Senderadressraum
über das Netzwerk in den Empfängeradressraum kopiert
werden.
Woher weiß aber der Sender,
wann er Nachrichten senden kann bzw. eine Nachricht empfangen
wurde?
Protokoll1: send blockiert bis Bestätigung
für Nachricht empfangen wurde
Prozess P1 und P2 tauschen synchron
Nachrichten. Beide Operationen sind blockierend. Durch die
INPUT(P2) Nachricht, weiß der Sender, dass er die Nachricht
senden darf. Mit ACK bestätigt P2 den Erhalt der Nachricht.
Protokoll 2: send blockiert bis receive
aufgerufen wurde
Bei Protokoll 2 fehlt die ACK, die
Bestätigung für den Erhalt der Nachricht.
6.2 Asynchroner Nachrichtenaustausch
Beim asynchronen Nachrichtenaustausch
benutzt mindestens einer der Prozesse eine nicht-blockierende
Sende- oder Empfangsoperation.
Protokoll 1:
Damit asynchroner Nachrichtenaustausch
überhaupt funktioniert, ist prinzipiell unendlich großer
Puffer erforderlich. Das Protokoll 1 zeigt so einen Fall.
So ist es z.B. möglich, dass P1 mit send unendlich viele
Nachrichten in den Puffer schreibt. Aus diesem unendlich großen
Puffer kann sich P2 bedienen.
Protokoll 2:
Es handelt sich hier um das selbe
Protokoll wie Protokoll 1. Hier ist nur der Fall dargestellt,
in der P2 auf eine Nachricht wartet. Dies kann passieren,
wenn der Puffer leer ist. In dem Augenblick, nachdem P1 etwas
in den Puffer geschrieben hat, kann P2 die Nachricht auslesen
und ist nicht mehr blockiert.
Man stelle sich den realistischen
Fall vor, in der Puffer endlich groß ist. Hier wird
der Sender bei vollem Puffer so lange blockiert, bis wieder
Speicher frei wird. Man spricht von pufferblockierendem Senden.
Ein einfaches Protokoll dazu ist das
Stop-and-wait-Protokoll. Der Puffer kann genau eine Nachricht
aufnehmen. Die Pufferung findet beim Empfänger statt.
Eine Verallgemeinerung des Stop-and-wait-Protokolls ist der
Fenstermechanismus.
Beschreibung des Stop-and-wait-Protokolls:
1. Wenn der Puffer leer ist, so kann
P1 die Nachricht in den Puffer kopieren und wird nicht blockiert.
2. Falls P1 eine Nachricht senden
möchte und der Puffer nicht leer ist, wird er solange
blockiert, bis ein ACK von P2 eintrifft. Mit ACK signalisiert
P2, dass der Puffer überschrieben werden darf.
3. Falls Puffer belegt ist und P2
empfangen möchte, so wird P2 nicht blockiert. Er muss
nur ein ACK an P1 schicken.
4. Falls Puffer leer ist und P2 empfangen
möchte, so wird P2 so lange blockiert bis P1 eine Nachricht
in den Puffer schreibt.
6.3 Synchroner vs. asynchroner Datenaustausch
Bei asynchronem Datenaustausch hat
man ein Maximum an Flexibilität und Parallelität.
Allerdings ist eine Pufferung der Daten notwendig. Ebenfalls
ein Nachteil ist, dass komplexe Programme schwierig zu testen
sind.
Synchroner Datenaustausch erlaubt
einfache und verifizierbare Programme, hat aber den Nachteil
der Einschränkung der Parallelität. Es ist, wie
schon oben erwähnt, keine Pufferung notwendig.
7. Verbindungslose- und verbindungsorientierte Kommunikation
Kommunikation wird in verbindungsorientierte
und verbindungslose Kommunikation unterteilt. Verbindungsorientierte
Kommunikation ist zuverlässig. Verbindungslose Kommunikation
ist im Prinzip unzuverlässig, kann aber auch zuverlässig
gemacht werden.
7.1 Verbindungslose Kommunikation
Bei der verbindungslosen Kommunikation werden die Nachrichten
als isolierte Einheiten übertragen. Es findet keine Flusskontrolle
statt, d.h. Einheiten können sich überholen. Wie
schon erwähnt ist verbindungslose Kommunikation meist
unzuverlässig, aber auch zuverlässige Datagramme
sind möglich.
Wie sieht ein Protokoll bei unzuverlässigen
Datagrammen aus?
Es sind einfachste Protokolle. P1 sendet P2 eine Nachricht.
Diese Nachricht kann verloren gehen, es können Duplikate
entstehen, die Reihenfolge kann verändert werden, die
Daten können unterwegs modifiziert werden. Weder P1 noch
P2 unternehmen etwas, um dies zu ändern.
Wie sieht ein Protokoll bei zuverlässigen
Datagrammen aus?
Hier sind komplexere Protokolle notwendig. Wie kann man Verlust,
Modifikation und Duplikate und Folgefehler erkennen?
Verlust lässt sich dadurch erkennen, dass ein ACK für
jedes übertragene Datagramm fällig wird. P1 sendet
eine Nachricht und startet einen Timer. Nun gibt es zwei Möglichkeiten,
nämlich das die Nachricht selbst verloren geht oder ACK
nicht ankommt. Bei beiden Möglichkeiten sendet P1 nach
Ablauf des Timers die Nachricht nochmals.
Falls ACK verlorengegangen ist, muss P2 Duplikate erkennen.
Dies kann mittels Nachrichten-IDs gelöst werden.
Modifikation wird dadurch erkannt, dass eine Prüfsumme
berechnet wird. Weicht sie vom erwarteten Wert ab, ist ein
Übertragungsfehler passiert.
Folgefehler kann man mittels fortlaufendender Nummerierung
erkenn, z.B. auch durch fortlaufende Nachrichten-IDs.
7.2 Verbindungsorientierte Kommunikation
Bevor eine verbindungsorientierte Kommunikation erfolgen kann,
muss zuerst eine Verbindung aufgebaut werden. Nach dem Datentransfer
wir die Verbindung wieder abgebaut. Verbindungsaufbau, Datentransfer
und Verbindungsabbau wird 3-phasige Interaktion genannt.
Beim Verbindungsaufbau kann die Qualität
des Dienstes ausgehandelt werden. (Quality of Service). Das
sind z.B. Merkmale wie Durchsatz, Verzögerung oder Fehlerwahrscheinlichkeit.
Bei einer verbindungsorientierten
Kommunikation wird zuverlässige Kommunikation in beide
Richtungen betrieben, d.h. kein Verlust, keine Duplikate,
keine Modifikation. Keine Folgefehler, d.h. Flusskontrolle
findet ebenfalls statt. Dies alles erfordert eine vergleichsweise
komplexe Protokolle.
Es sind zusätzliche Primitive
für den Verbindungsaufbau und -abbau nötig:
connect: Senden eines Verbindungswunsches
listen: Empfangen eines Verbindungswunsches
accept: Akzeptieren eines Verbindungswunsches
reject: Ablehnen eines Verbindungswunsches
disconnect: Abbau einer Verbindung usw.
Wichtige Protokollelemente:
Verbindungsaufbau durch das Three-Way-Handshake.
Verbindungsabbau
Fehlerkontrolle: Positive Acknowledgement
and Retransmit (PAR)
Sequenzkontrolle durch Sequenznummern
Fehlererkennung durch Prüfsumme
(z.B. CRC)
Flusskontrolle durch Fenstermechanismus
oder Credits
Zusätzliche Hinweise:
Ein Beispiel für den Fenstermechanismus
ist Sliding Windows.
ACK sind Bestätigungen.
NAK sind negative Bestätigungen.
Ein NAK kann z.B. von P1 an P2 gesendet werden, um anzudeuten,
dass zwar die Dateneinheit empfangen wurde aber die Fehlererkennung
einen Fehler festgestellt hat.
NAK dient hauptsächlich der Beschleunigung. Z.B. könnte
Prozess P2 auch so lange warten und kein ACK senden, bis P1
das fehlerhafte Packet nochmals sendet.
Falls ein Protokoll NAK nicht implementier
hat, so spricht man von Fehlerkontrolle mittels PAR. Es gibt
nur bei erfolgreichem Empfangen ein ACK, d.h. der empfangende
Prozess wartet bis Timeout beim Sender auftritt und er ein
erneutes Senden veranlasst.
Man spricht von Three-Way-Handshake,
falls der Verbindungsaufbau in drei Schritten erfolgt, so
wie dies beim Aufbau einer TCP-Verbindung der Fall ist.
7.3 Verbindungslose- vs. verbindungsorientierte Kommunikation
Argumente für verbindungsorientierte Kommunikation
Einfaches und mächtiges Paradigma.
Es vereinfacht die höheren Schichten und führt somit
zur Entlastung der Endsysteme. Verbindungslose Kommunikation
ist für ein breites Spektrum von Anwendungen geeignet.
Argumente für (unzuverlässige)
verbindungslose Kommunikation
Sie hat hohe Flexibilität und
geringe Komplexität. Für einige Anwendungen (z.B.
Echtzeitanwendungen, digitale Sprachübertragung) ist
hohe Performance wichtiger als fehlerfreie Übertragung.
Falls nur eine relativ kurze Interaktion gewünscht wird,
so ist der Kostenanteil für Auf und Abbau von Verbindungen
hoch. "End-to-End-Arguments".
Was bedeutet "End-To-End-Arguments"?
8. End-to-End-Argumente
In geschichteten Systemen kann die
Realisierung einer Funktion in unteren Schichten überflüssig
sein, oder ihre Realisierung verursacht hohe Kosten.
Bei unzuverlässiger Kommunikation
können Fehler erst in oberen Schichten entdeckt und behandelt
werden. Zuverlässige Kommunikation ist teuere Kommunikation.
Der Grund liegt darin, dass End-to-End Recovery trotzdem notwendig
ist, obwohl viele Funktionen in unteren Schichten realisiert
werden. Dazu zählen z.B. Übertragungsfehler oder
Duplikatserkennung. Die Duplikatsunterdrückung im Server
z.B. erkennt und unterdrückt auch Duplikate des Transportsystems.
Z.B. kann auch eine End-to-End Verschlüsselung die Verschlüsselung
auf der Transport-Ebene überflüssig machen.
Was spricht gegen End-to-End-Argumente?
Wenn bestimmte Funktionen in unteren
Schichten realisiert werden, werden Fehler entdeckt. Das spart
Bandbreite und CPU- und Pufferressourcen.
Die Frage, welche Funktionen wo realisiert
werden sollen, hängt von der Art und Topologie des Netzwerkes
ab. Außerdem spielen Zuverlässigkeitsanforderungen
der Anwendungen eine wichtige Rolle.
Man kann einen Kompromiss schließen.
Das Transportsystem unterstützt zwei Dienstklassen, nämlich
einen allgemeinen zuverlässigen Dienst und einen effizienten
unzuverlässigen Dienst.
|