Vorlesung: 1 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Studiengang Informatik FHDWStudiengang Informatik FHDW

Vorlesung: Betriebssysteme II

4. Quartal 2004

Vorlesung: 2 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Verteilter gemeinsamer SpeicherVerteilter gemeinsamer Speicher

Motivation:

Wofür könnte „gemeinsamer Speicher“ benötigt werden?Welche Möglichkeiten für die Realisierung existieren?Welche Alternativen existieren?Nennen Sie typische Problemstellungen bei der Realisierung von „gemeinsamen Speicher“.

Rückblick: Speicherverwaltung ohne Verteilung!

Vorlesung: 3 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Verteilter gemeinsamer SpeicherVerteilter gemeinsamer Speicher

Gemeinsame Nutzung von Daten ist ein grund-legendes Ziel verteilter Systeme und Anwen-dungen.Möglichkeiten:

Daten per Nachricht transferieren (engl.: message-passing),verteilter gemeinsamer Speicher (engl.: distributed shared memory, DSM).

DSM erlaubt den Zugriff auf Speicherstellen, obwohl die beteiligten Computer physikalisch getrennte Speicher haben.Auf die Daten wird zugegriffen, als ob sie im üblichen Adressraum des Prozesses wären.

Vorlesung: 4 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Verteilter gemeinsamer Speicher (2)Verteilter gemeinsamer Speicher (2)

DSM verhält sich wie ein virtuelles Speichersystem, jedoch können Speicherseiten auch auf anderen Computern liegen.DSM ist besonders für parallele und verteilte Algorithmen nützlich, in welchen gemeinsame Daten direkt referenziert werden.Wird DSM nicht direkt durch die Hardware unterstützt, wird ein Laufzeitsystem benötigt, das auf dem lokalen Speicher der einzelnen Rechner aufsetzt.

Vorlesung: 5 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Verteilter gemeinsamer Speicher (3)Verteilter gemeinsamer Speicher (3)

Das DSM-Laufzeitsystem verwendet dann Nachrichtenaustausch zur Bereitstellung der Daten aus dem gemeinsamen Speicher.Der Nachrichtenaustausch erfolgt transparent für die Prozesse, die den verteilten gemeinsamen Speicher nutzen.

Vorlesung: 6 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Verteilter gemeinsamer Speicher (4)Verteilter gemeinsamer Speicher (4)

Hauptgründe für die Entwicklung von DSM-Systemen:

Die meisten parallelen Programme waren für SIMD oder massiv parallele Rechner entwickelt worden.Bei der Portierung dieser Programme auf Multicomputersysteme ist es einfacher, den gemeinsamen Speicher auf Multicomputern verteilt nachzubilden, als die Software auf die Kommunikation mittels Nachrichtenaustausch umzustellen.Bei der Programmierung auf einem DSM ist das Pro-grammierparadigma von parallelen oder paralle-lisierbaren Programmiersprachen direkt verwendbar.Verteilte Objektsysteme können direkt auf DSM abgebildet werden ohne einen RMI-Mechanismus (remote method invocation) zu benötigen.

Vorlesung: 7 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Vergleich RPC und DSMVergleich RPC und DSM

Kriterium Nachrichtenaustausch DSM

Variablen „marshalled“, verschickt,„demarshalled“

Zugriff wie auf jede an-dere lokal gespeicherteVariable

Zugriffsrechte private Adreßräume Überschreibungen mög-lich

Heterogenität der Da-tenobjekte

unterschiedliche Daten-repräsentation möglich

homogene Sicht not-wendig

Synchronisation Sperren, Transaktionen,kausale Ordnung

Memory Management,Semaphore, Monitore,kritische Regionen

Nebenläufigkeit, Persi-stenz

Klient und Server müs-sen zeitgleich laufen,keine Persistenz erfor-derlich

Prozesse können zeit-lich entkoppelt laufen,Persistenz erforderlich

Vorlesung: 8 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Verteilter gemeinsamer Speicher (5)Verteilter gemeinsamer Speicher (5)

Im kleinen Maßstab (ca. 10 Rechner), können DSM-Programme genauso effizient wie Programme, die auf Nachrichtenaustausch basieren, implementiert werden.Bei der Programmierung wird mittels DSM der Systemoverhead für den Programmierer versteckt.Der Aufwand der Kommunikation kann nicht direkt beeinflusst werden. Er hängt vom Algorithmus, dessen Datenverteilung und dessen momentanen Zustand ab.Es gibt abgeschwächte DSM-Konzepte, welche die vollständige Transparenz aufbrechen.

Vorlesung: 9 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

ImplementierungsvariantenImplementierungsvarianten

Blockbasiert, kontrolliert durch die MMUSpezielle Hardware behandelt die load und store Maschinenbefehle auf DSM-Adressen (z.B. Dash Multicomputer).Liegt ein Zugriff auf eine physikalisch entfernte Adresse vor, sorgt die MMU für eine hardwaregestützte Anforderung der Daten.Dies geschieht wie in Prozessorcachesystemen auf Blockbasis, d.h. ein bis wenige Speicherworte.

Vorlesung: 10 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Implementierungsvarianten (2)Implementierungsvarianten (2)

Seitenbasiert, kontrolliert durch das BetriebssystemDer DSM wird als Region mit identischen Adressen im virtuellen Adreßraum jedes beteiligten Prozesses implementiert.Die Konsistenz leistet der Betriebssystemkern im Rahmen seines Seitenfehleralgorithmus.Vertreter dieser Kategorie sind eine ganze Anzahl verteilter Betriebssysteme (z.B. Ivy).Erfolgt der tatsächliche Speicherzugriff hardwareunterstützt, nennt man die Rechner NUMA-Maschinen.

Vorlesung: 11 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Implementierungsvarianten (3)Implementierungsvarianten (3)

Objektbasiert, kontrolliert durch ein LaufzeitsystemNicht der gesamte Speicher wird transparent zugreifbar gehaltenGemeinsame Variablen werden speziell behandelt.Sie sind dazu vom Programmierer speziell zu kennzeichnen (z.B. Munin).Einige verteilte, objektorientierte Sprachen/-erweite-rungen oder Koordinationssprachen, wie Linda, implementieren DSM durch Bibliotheksaufrufe an ein Laufzeitsystem.Die DSM-Aufrufe werden vom Compiler an den entsprechenden Stellen automatisch eingesetzt.

Vorlesung: 12 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Spektrum von Shared-Memory-AnsätzenSpektrum von Shared-Memory-Ansätzen

Vorlesung: 13 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

KonsistenzmodelleKonsistenzmodelle

Um bei DSM verschiedene Kopien einer Speichereinheit ohne großen Aufwand konsistent zu halten, muss man auf mehrere schreibbare Kopien verzichten.Die Leistung geht dann bei nebenläufigen Schreibzugriffen zurück.

Bei hardwarebasierten Systemen ist dies sekundär.Bei Systemen mit Netzwerkkommunikation kann man aus Effizienzgründen oft nicht auf mehrere schreibbare Kopien verzichten.Daraus folgt ein erhöhter Aufwand, Konsistenz zu wahren. Um die semantischen Konsistenzeigenschaften zu beschreiben, definiert man Konsistenzmodelle.

Vorlesung: 14 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Konsistenzmodelle (2)Konsistenzmodelle (2)

Ein Konsistenzmodell ist eine Vereinbarung zwischen der übergeordneten, benutzenden Software und dem verteilten Speicher.Arbeitet die Software konform zu der Vereinbarung, ist auch garantiert, dass der Speicher richtig arbeitet.Je komplexer die Vereinbarung,

um so effizienter läuft das DSM-System,um so aufwendiger und restriktiver wird die Programmierung.

Vorlesung: 15 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Strikte KonsistenzStrikte Konsistenz

DefinitionStrikte KonsistenzJeder Lesezugriff auf die Speicherstelle x liefert den Wert der global zeitlich letzten Schreib-operation auf x.

Dies bedeutet, dass jeder Speicherzugriff im DSM genauso ablaufen soll, als ob es sich um ein lokales System handelt.

Vorlesung: 16 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Strikte Konsistenz (2)Strikte Konsistenz (2)

Beispiel:Die Speicherstelle x sei bei Rechner B gespeichert.Rechner A liest x zum Zeitpunkt t1.Eine Nanosekunde später schreibt B auf x.Sind A und B etwa 3 Meter auseinander, müsste der Lesezugriff zehnmal schneller als die Lichtgeschwindigkeit übertragen werden, um das richtige Ergebnis zu liefern.

Vorlesung: 17 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

ImplementierungImplementierung

Über alle Ereignisse ist eine absolute globale Zeitordnung sicherzustellen.

Es können z.B. alle Speicherzugriffe werden in eine Transaktion gekapselt werdenoder Sperren werden rigorose verwendet.

Beide Realisierungen verhindern nebenläufige Zugriffe.

Vorlesung: 18 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Sequentielle KonsistenzSequentielle Konsistenz

DefinitionSequentielle KonsistenzDie Speicheroperationen verschiedener Prozesse geschehen in beliebiger sequentieller Reihenfolge.Alle Lese- und Schreiboperationen eines Pro-zesses erscheinen in der programmierten Reihen-folge.

Hier sehen also alle Prozesse die gleiche Reihenfolge von Speicherreferenzen.Der Zeitpunkt der Sichtbarkeit spielt keine Rolle, es kann eine beliebige Verzögerung unter den Prozessen vor-kommen.

Vorlesung: 19 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Sequentielle Konsistenz (2)Sequentielle Konsistenz (2)

Schreibweise:R(x)=a Lesen der Speicherstelle x liefert den Wert a.

W(x)=a Speicherstelle x wird mit dem Wert abeschrieben.

Alle Speicherstellen sind mit 0 initialisiert.

Beispiel für zwei sequentielle konsistente Programmergebnisse:

Vorlesung: 20 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Sequentielle Konsistenz (3)Sequentielle Konsistenz (3)

Komplexeres Beispiel: 3 Prozesse arbeiten mit den gemeinsamen Variablen a, b, c.P1: a=1; print (b,c);P2: b=1; print (a,c);P3: c=1; print (b,c);Vier mögliche Reihenfolgen sequentielle Konsistenz:

Vorlesung: 21 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Sequentielle Konsistenz (4)Sequentielle Konsistenz (4)

Um die sequentiell konsistente Ausführung zu prüfen, bildet man z.B. die Signatur.Die Signatur ist die Konkatenation der Ausgaben der Prozesse als Tupel <P1, P2, P3>.Für das Beispiel:

Signatur:001011 101011 110101 111111

Nicht alle 64 möglichen Signaturen entsprechen einer sequentiellen Ausführung und sind erlaubt.Z. B. ist die Signatur 000000 ungültig.

Vorlesung: 22 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

ImplementierungImplementierung

Z. B. in einem seitenbasierten System:Schreibbare Seiten werden repliziert.Keine Speicheroperation wird begonnen, bevor nicht alle vorhergehenden beendet sind.Aktualisierungen werden über einen zuverlässigen, total geordneten Broadcast oder Multicast propagiert.

Sequentielle Konsistenz ist nicht sehr effizient:Es wurde nachgewiesen, dass (Lesezeit + Schreibzeit) immer größer als die kürzeste Pakettransferzeit ist.D. h. man kann Lesezugriffe auf Kosten der Schreibzugriffe optimieren und umgekehrt, aber nie beide Zugriffsformen zusammen.

Für effizientere Implementierungen von DSM benötigt man schwächere Konsistenzmodelle.

Vorlesung: 23 Betriebssysteme II 2004 Prof. Dr. G. Hellberg

Kausale KonsistenzKausale Konsistenz