Eine unabdingbare Voraussetzung für den Betrieb universeller verteilter DV-Systeme ist eine dezentral durchgeführte Zugriffssynchronisation. Diese muß für global konkurrierende Zugriffe zu verteilten Daten das Korrektheitskriterium der Serialisierbarkeit garantieren. Es gibt zwar eine weitgehend ausgereifte Theorie für die Serialisierbarkeit und teilweise auch für die (zentrale) Zugriffssynchronisation, aber eine Theorie zur dezentralen Verwaltung steht noch aus. Das Kernproblem ist, daß es keinen global einheitlich beobachtbaren Systemzustand eines verteilten Systems gibt und daß trotzdem global gültige Entscheidungen zu treffen sind. In. der vorliegenden Arbeit wird nun ein neuer, systematischer Ansatz vorgestellt, der dieses Problem für die Zugriffssynchro nisation löst und der stets nur eine räumlich 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, sodaß hierfür quantitative Leistungsaussagen gemacht werden können. Der vorliegende Band entspricht meiner von der Fakultät für Informatik der Universität Karlsruhe genehmigten Dissertation. Die mündliche prüfung fand am 3.11.1982 statt. Mehreren Mitgliedern der Fakultät für Informatik habe ich für ihren Beitrag zum Gelingen dieser Arbeit zu danken: Herrn Prof. Dr. H. Wettstein für wichtige Diskussionsbeiträge und für die Übernahme des Erstreferats, Herrn Prof. Dr. G. Krüger für die Übernahme des Korreferats und Herrn Heinz Zoller für seine unterstützung bei der Durchführung der Experimente. Herzlicher Dank gebührt auch meiner Ehefrau Inge für ihre Geduld und Unterstützung während der Anfertiqung dieser Arbeit.
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.
Eine unabdingbare Voraussetzung für den Betrieb universeller verteilter DV-Systeme ist eine dezentral durchgeführte Zugriffssynchronisation. Diese muß für global konkurrierende Zugriffe zu verteilten Daten das Korrektheitskriterium der Serialisierbarkeit garantieren. Es gibt zwar eine weitgehend ausgereifte Theorie für die Serialisierbarkeit und teilweise auch für die (zentrale) Zugriffssynchronisation, aber eine Theorie zur dezentralen Verwaltung steht noch aus. Das Kernproblem ist, daß es keinen global einheitlich beobachtbaren Systemzustand eines verteilten Systems gibt und daß trotzdem global gültige Entscheidungen zu treffen sind. In. der vorliegenden Arbeit wird nun ein neuer, systematischer Ansatz vorgestellt, der dieses Problem für die Zugriffssynchro nisation löst und der stets nur eine räumlich 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, sodaß hierfür quantitative Leistungsaussagen gemacht werden können. Der vorliegende Band entspricht meiner von der Fakultät für Informatik der Universität Karlsruhe genehmigten Dissertation. Die mündliche prüfung fand am 3.11.1982 statt. Mehreren Mitgliedern der Fakultät für Informatik habe ich für ihren Beitrag zum Gelingen dieser Arbeit zu danken: Herrn Prof. Dr. H. Wettstein für wichtige Diskussionsbeiträge und für die Übernahme des Erstreferats, Herrn Prof. Dr. G. Krüger für die Übernahme des Korreferats und Herrn Heinz Zoller für seine unterstützung bei der Durchführung der Experimente. Herzlicher Dank gebührt auch meiner Ehefrau Ingefür ihre Geduld und Unterstützung während der Anfertiqung dieser Arbeit.
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.7. Besonderheiten dezentraler Zugriffssynchronisation....- 2.8. Aufwandsideale.- 3. Bisherige Ansätze zur Zugriffssynchronisation in verteilten Systemen.- 3.1. Universelle Verfahren.- 3.2. Spezialisierte Verfahren.- 3.3. Polgerungen.- 4. Ein neuer Ansatz zur dezentralen Zugriffssynchronisation.- 4.1 Grundmodell.- 4.2 Prinzipien und Konzepte.- 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.2 Konversion der Zugriffsart beim Verfahren II.- 7.3 Mehrere Objekte je Speicherort.- 7.4 Verteilte Kopien.- 7.5 Einfügen und Löschen von Objekten.- 7.6 Ausfallbetrachtungen.- 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.2 Realisierung von Verfahren II.- 11. Literatur.
Inhaltsverzeichnis
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.7. Besonderheiten dezentraler Zugriffssynchronisation....- 2.8. Aufwandsideale.- 3. Bisherige Ansätze zur Zugriffssynchronisation in verteilten Systemen.- 3.1. Universelle Verfahren.- 3.2. Spezialisierte Verfahren.- 3.3. Polgerungen.- 4. Ein neuer Ansatz zur dezentralen Zugriffssynchronisation.- 4.1 Grundmodell.- 4.2 Prinzipien und Konzepte.- 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.2 Konversion der Zugriffsart beim Verfahren II.- 7.3 Mehrere Objekte je Speicherort.- 7.4 Verteilte Kopien.- 7.5 Einfügen und Löschen von Objekten.- 7.6 Ausfallbetrachtungen.- 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.2 Realisierung von Verfahren II.- 11. Literatur.
Klappentext
Eine unabdingbare Voraussetzung für den Betrieb universeller verteilter DV-Systeme ist eine dezentral durchgeführte Zugriffssynchronisation. Diese muß für global konkurrierende Zugriffe zu verteilten Daten das Korrektheitskriterium der Serialisierbarkeit garantieren. Es gibt zwar eine weitgehend ausgereifte Theorie für die Serialisierbarkeit und teilweise auch für die (zentrale) Zugriffssynchronisation, aber eine Theorie zur dezentralen Verwaltung steht noch aus. Das Kernproblem ist, daß es keinen global einheitlich beobachtbaren Systemzustand eines verteilten Systems gibt und daß trotzdem global gültige Entscheidungen zu treffen sind. In. der vorliegenden Arbeit wird nun ein neuer, systematischer Ansatz vorgestellt, der dieses Problem für die Zugriffssynchro nisation löst und der stets nur eine räumlich 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, sodaß hierfür quantitative Leistungsaussagen gemacht werden können. Der vorliegende Band entspricht meiner von der Fakultät für Informatik der Universität Karlsruhe genehmigten Dissertation. Die mündliche prüfung fand am 3.11.1982 statt. Mehreren Mitgliedern der Fakultät für Informatik habe ich für ihren Beitrag zum Gelingen dieser Arbeit zu danken: Herrn Prof. Dr. H. Wettstein für wichtige Diskussionsbeiträge und für die Übernahme des Erstreferats, Herrn Prof. Dr. G. Krüger für die Übernahme des Korreferats und Herrn Heinz Zoller für seine unterstützung bei der Durchführung der Experimente. Herzlicher Dank gebührt auch meiner Ehefrau Inge für ihre Geduld und Unterstützung während der Anfertiqung dieser Arbeit.
