Korrekte Zugriffe zu verteilten Daten

ISBN-13: 9783540122821 / Niemiecki / Miękka / 1983 / 203 str.

H. Bender

Opis

Eine unabdingbare Voraussetzung fur den Betrieb universeller verteilter DV-Systeme ist eine dezentral durchgefuhrte Zugriffssynchronisation. Diese muss fur global konkurrierende Zugriffe zu verteilten Daten das Korrektheitskriterium der Serialisierbarkeit garantieren. Es gibt zwar eine weitgehend ausgereifte Theorie fur die Serialisierbarkeit und teilweise auch fur die (zentrale) Zugriffssynchronisation, aber eine Theorie zur dezentralen Verwaltung steht noch aus. Das Kernproblem ist, dass es keinen global einheitlich beobachtbaren Systemzustand eines verteilten Systems gibt und dass trotzdem global gultige Entscheidungen zu treffen sind. In. der vorliegenden Arbeit wird nun ein neuer, systematischer Ansatz vorgestellt, der dieses Problem fur die Zugriffssynchro nisation lost und der stets nur eine raumlich und zeitlich exakt begrenzte Kooperation verteilter Verwaltungsinstanzen erfordert. Zwei neue darauf aufbauende Verfahren zur dezentra len Zugriffssynchronisation werden beschrieben. Ihre Korrekt heit wird formal nachgewiesen. Das erste der neuen Verfahren wurde auch experimentell untersucht, sodass hierfur quantitative Leistungsaussagen gemacht werden konnen. Der vorliegende Band entspricht meiner von der Fakultat fur Informatik der Universitat Karlsruhe genehmigten Dissertation. Die mundliche prufung fand am 3.11.1982 statt. Mehreren Mitgliedern der Fakultat fur Informatik habe ich fur ihren Beitrag zum Gelingen dieser Arbeit zu danken: Herrn Prof. Dr. H. Wettstein fur wichtige Diskussionsbeitrage und fur die Ubernahme des Erstreferats, Herrn Prof. Dr. G. Kruger fur die Ubernahme des Korreferats und Herrn Heinz Zoller fur seine unterstutzung bei der Durchfuhrung der Experimente. Herzlicher Dank gebuhrt auch meiner Ehefrau Inge fur ihre Geduld und Unterstutzung wahrend der Anfertiqung dieser Arbeit."

Spis treści

1. Einleitung.- 2. Grundlagen und Begriffe.- 2.1. Systemmodell, verteilte Daten.- 2.2. Zugriffe, Transaktionen.- 2.3. Zugriffsfolgen.- 2.4. Unverträglichkeiten, Konflikte.- 2.5. Korrektheit konkurrierender Transaktionen.- 2.6. Zugriffssynchronisation.- 2.6.1. Sperren.- 2.6.2. Scheduling von Zugriffsoperationen.- 2.6.3. Optimistische Verfahren.- 2.7. Besonderheiten dezentraler Zugriffssynchronisation….- 2.7.1. Sperren.- 2.7.2. Scheduling.- 2.7.3. Optimistische Zugriffssynchronisation.- 2.8. Aufwandsideale.- 2.8.1. Vorausdeklaration.- 2.8.2. Sukzessive Zugriffsanforderungen.- 3. Bisherige Ansätze zur Zugriffssynchronisation in verteilten Systemen.- 3.1. Universelle Verfahren.- 3.2. Spezialisierte Verfahren.- 3.2.1. Globaler Ausschlu?.- 3.2.2. Vorausdeklaration der benötigten Objekte.- 3.2.3. N-fach verteilte Kopien.- 3.2.4. Vorausanalyse aller Transaktionen.- 3.3. Polgerungen.- 4. Ein neuer Ansatz zur dezentralen Zugriffssynchronisation.- 4.1 Grundmodell.- 4.1.1. Voraussetzungen und Annahmen.- 4.1.2. Systemstruktur.- 4.2 Prinzipien und Konzepte.- 4.2.1. Vereinfachte Zugriffssynchronisation.- 4.2.1.1. Direktes Erzeugen einer azyklischen Vorgängerrelation.- 4.2.1.2. Erzwingen einer azyklischen Blockaderelation.- 4.2.2. Dezentrale Festlegung global einheitlicher Rangziffern.- 5. Verfahren I: Direktes Erzeugen einer azyklischen Vorgängerrelation.- 5.1. Ablaufbeschreibung.- 5.2. Beweise.- 5.3. Vereinfachung für reine Lesezugriffe.- 5.4. Realisierung.- 6. Verfahren II: Verhinderung globaler Verklemmungen.- 6.1. Ablaufbeschreibung.- 6.2. Sicherstellung fairer Bedienung.- 6.3. Beweise.- 6.4. Realisierung.- 7. Erweiterungen.- 7.1. Sukzessive Zugriffsanforderungen.- 7.1.1Verfahren I.- 7.1.2Verfahren II.- 7.1.2.1 Ma?nahmen der Transaktionsverwalter….- 7.1.2.2 Ma?nahmen der Zugriffsverwalter.- 7.1.2.3 Besonderheiten.- 7.2 Konversion der Zugriffsart beim Verfahren II.- 7.2.1 Ma?nahmen der Transaktionsverwalter.- 7.2.2 Ma?nahmen der Zugriffsverwalter.- 7.2.3 Besonderheiten.- 7.3 Mehrere Objekte je Speicherort.- 7.3.1 Verfahren I.- 7.3.2 Verfahren II.- 7.3.2.1 Ma?nahmen der Transaktionsverwalter….- 7.3.2.2 Ma?nahmen der Zugriffsverwalter.- 7.4 Verteilte Kopien.- 7.4.1 Erweiterungen für das Verfahren I.- 7.4.1.1 Ma?nahmen der Transaktionsverwalter.- 7.4.1.2 Ma?nahmen der Zugriffsverwalter.- 7.4.2 Verfahren II.- 7.4.2.1 Ma?nahmen der Transaktionsverwalter….- 7.4.2.2 Ma?nahmen der Zugriffsverwalter.- 7.4.2.3 Besonderheiten.- 7.5 Einfügen und Löschen von Objekten.- 7.5.1 Einfügen neuer Objekte.- 7.5.1.1 Ma?nahmen der Transaktionsverwalter.- 7.5.1.2 Ma?nahmen der Zugriffsverwalter.- 7.5.2 L?schen von Objekten.- 7.5.2.1 Ma?nahmen der Transaktionsverwalter.- 7.5.2.2 Ma?nahmen der Zugriffsverwalter.- 7.6 Ausfallbetrachtungen.- 7.6.1 Ausfall eines Zugriffsverwalters.- 7.6.2 Ausfall eines Transaktionsverwalters.- 7.6.3 Ausfälle im Transportsystem.- 8. Experimentelle Untersuchungen.- 8.1 Modell.- 8.2 Parameter.- 8.3 Ergebnisse.- 9. Zusammenfassung und Ausblick.- 10. Anhang.- 10.1 Realisierung von Verfahren I.- 10.1.1 Allgemeine Vereinbarungen.- 10.1.1.1 Proze?kommunikation.- 10.1.1.2 Globale Datentypen.- 10.1.2 Gliederung der Transaktionsverwalter.- 10.1.3 Gliederung der Zugriffsverwalter.- 10.1.3.1 Berücksichtigung von Laufzeiteffekten.- 10.1.3.2 Verwaltungsdaten.- 10.1.3.4 Funktionen und Prozeduren.- 10.1.3.4 Prozesse.- 10.2 Realisierung von Verfahren II.- 10.2.1 Allgemeine Vereinbarungen.- 10.2.2 Gliederung der Transaktionsverwalter.- 10.2.3 Gliederung der Zugriffsverwalter.- 10.2.3.1 Berücksichtigungvon Lauf zeiteffekten.- 10.2.3.2 Verwaltungsdaten.- 10.2.3.3 Funktionen und Prozeduren.- 10.2.3.4 Prozesse.- 11. Literatur.