15.3 On-Request-Invalidierung
15.3.1 Versionsnummern und Invalidierungsvektoren
Ein einfacher Ansatz zur Erkennung invalidierter Seiten, der u.a. für DEC VaxCluster eingesetzt wird [KLS86], ist die Verwendung einer Versionsnummer bzw. eines Änderungszählers pro Seite (page sequence number). Die Versionsnummer wird im Seitenkopf geführt und bei jeder Änderung inkrementiert. Bei Freigabe der Schreibsperre für eine erfolgreich durchgeführte Änderung wird der aktuelle Wert der Versionsnummer dem GLM mitgeteilt und in der globalen Sperrtabelle gespeichert. Bei der Anforderung einer Sperre ist zunächst zu prüfen, ob eine Kopie der Seite lokal gepuffert ist und - wenn ja - mit welcher Versionsnummer. Der GLM kann dann bei der Sperrbearbeitung durch Zeitstempelvergleich feststellen, ob die Kopie invalidiert ist oder nicht, und das Ergebnis mit der Sperrgewährung mitteilen.
Beispiel 15-1
Abb. 15-5: On-Request-Invalidierung mit Versionsnummern
- Im Beispiel von Abb. 15-5 ist die Seite B zunächst ungeändert im Hauptspeicher der beiden Rechnern R1 und R3 gepuffert. Nachdem der GLM einer Transaktion in R3 eine Schreibsperre gewährt hat, liegt in der globalen Sperrtabelle der in Abb. 15-5a gezeigte Sperreintrag für B vor. Es ist darin vermerkt, daß eine X-Sperre an Rechner R3 gewährt ist; das Feld für die Versionsnummer (VN) ist unbelegt, da noch keine Änderung erfolgte. Nach erfolgreicher Änderung der Seite in R3 wird dort die Versionsnummer von 17 auf 18 erhöht und dieser Wert mit Freigabe der X-Sperre dem GLM mitgeteilt, der die Versionsnummer in die globale Sperrtabelle übernimmt (Abb. 15-5b). Bei einer Sperranforderung von R1 wird dem GLM mitgeteilt, daß die lokale Kopie von B die Versionsnummer 17 aufweist. Der GLM erkennt damit die Pufferinvalidierung in R1 und teilt dies bei der Gewährung der X-Sperre R1 mit, woraufhin die Seite eliminiert wird (Abb. 15-5c). Die aktuelle Version der Seite kann bei Force von Platte eingelesen werden, da hierbei R3 vor Freigabe der Schreibsperre die geänderte Seite ausschreiben mußte.
Die On-Request-Invalidierung kann alternativ mit sogenannten Invalidierungsvektoren realisiert werden [Ra86b]. Diese Invalidierungsvektoren werden für geänderte Seiten anstelle der Versionsnummern in der globalen Sperrtabelle geführt und bestehen aus je einem Invalidierungsbit pro Rechner. Das Invalidierungsbit für einen Rechner zeigt an, ob dort möglicherweise eine invalidierte Seite vorliegt. Der Wert I(j) =1 bedeutet dabei, daß für die betreffende Seite eine Invalidierung in Rechner j möglich ist, für I(j) = 0 ist sie dagegen ausgeschlossen. Diese Information kann geführt werden, da nach einer Seitenänderung zunächst nur der ändernde Rechner eine aktuelle Version der Seite hat. Für alle anderen Rechner, welche die ungeänderte Seitenversion gepuffert haben, liegt dagegen eine Invalidierung vor. Da der Aufwand der genauen Pufferbelegung nicht geführt werden soll, ist dem GLM nicht bekannt, welche Rechner tatsächlich Kopien der Seiten halten. Daher wird das Invalidierungsbit für alle Rechner außer dem ändernden gesetzt, um eine mögliche Invalidierung anzuzeigen. Dies ist ausreichend, da beim Anfordern einer Sperre geprüft wird, ob eine Kopie der Seite vorliegt. Ist dies der Fall und ist das Invalidierungsbit für den Rechner gesetzt, so liegt eine Invalidierung vor. Der Vorteil gegenüber der Verwendung von Versionsnummern liegt vor allem darin, daß in den Seiten selbst keine Invalidierungsangaben mehr zu führen sind. Dies macht diesen Ansatz auch besser geeignet zur Kohärenzkontrolle bezüglich feineren Objektgranularitäten als Seiten, z.B. zur Objektpufferung in objekt-orientierten DBS.
Beispiel 15-2
- Abb. 15-6 zeigt die Bearbeitung der Sperranforderungen aus dem vorherigen Beispiel, wenn anstelle von Versionsnummern Invalidierungsvektoren eingesetzt werden. Man erkennt, daß die Versionsnummern bei den Seiten selbst nicht mehr erforderlich sind. Der Invalidierungsvektor I hat für die unterstellten drei Rechner den für ungeänderte Seiten gültigen Initialwert 000. Nach Änderung der Seite in R3 wird I nach 110 abgeändert, da zu diesem Zeitpunkt nur R3 eine gültige Version von B besitzt, eine etwaige Kopie der Seite in R1 und R2 jedoch veraltet ist. Bei der folgenden Sperranforderung von R1 wird aufgrund des gesetzten Invalidierungsbits für diesen Rechner die Invalidierung erkannt. Der GLM setzt das Invalidierungsbit für R1 zurück, wodurch I den Wert 010 annimmt, da R1 die invalidierte Seite entfernt und die aktuelle Version von B erhält (bei Force durch Einlesen von Platte).
- Abb. 15-6: On-Request-Invalidierung mit Invalidierungsvektoren
Die in der globalen Sperrtabelle vorliegenden Angaben zur Kohärenzkontrolle sind im Falle der On-Request-Invalidierung auch dann zu führen, wenn für die betreffenden Seiten zeitweilig keine Sperranforderungen vorliegen. Damit stellt sich das Problem, die Größe der globalen Sperrtabelle zu begrenzen. Wenn in der globalen Sperrtabelle die genaue Pufferbelegung aller Rechner geführt würde, könnte ein Sperreintrag gelöscht werden, sobald die Seite in keinem der Rechner mehr gepuffert ist. Wird aus Aufwandsgründen auf die Wartung der genauen Pufferbelegung verzichtet, können in periodischen Abständen Sperreinträge gelöscht werden, auf die schon längere Zeit nicht mehr zugegriffen wurde. Damit dadurch keine relevanten Informationen verlorengehen, kann der GLM zuvor die betroffenen Seiten in einer Broadcast-Nachricht bekanntgeben, so daß die Rechner bei ihnen noch vorliegende, veraltete Kopien entfernen können. Diese Broadcast-Nachrichten verursachen nur einen geringen Aufwand und beeinflussen nicht die Antwortzeiten laufender Transaktionen.