Universität Karlsruhe (TH) © 2009 Univ,Karlsruhe, IPD, Prof. LockemannDBI 3 Kapitel 3 Segment- und Puffer- Verwaltung

UniversitätKarlsruhe (TH)

© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 3

Kapitel 3

Segment- und Puffer-Verwaltung

2


Gegenstand des Kapitels

Mengenorientiertes Datenmodell

Datenmodell

Dateien

Dateiverwaltung

Geräteschnittstelle

Anfragebearbeitung

Satzorientiertes Datenmodell

Speicherstruktur

Schneller Transport zwischen Haupt- und Hintergrundspeicher

Hauptspeicherseiten u. Segmente

Segment- u. Pufferverwaltung Bevorratung von Daten im Hauptspeicher (rechtzeitige Bereitstellung vor Benutzung)

Transparenter homogener Speicher Datentypen:

Seite = feste Anzahl von BytesSegment = var. Anzahl von Seiten

Operatoren:Anforderung/Freigabe von SeitenSegmente anlegen/öffnen/schließen

Datentypen:Block = feste Anzahl von BytesDatei = variable Anzahl v. Blöcken

Operatoren: Dateien anlegen/öffnen/schließen Lesen/Schreiben von Blöcken

Geräte-E/A

Satz- u. Satzmengenverwaltung

Satzzugriffsstrukturen

Zugriffsschicht

Vorschau auf zukünftig benötigte Daten

Vermeiden nicht aktuell benötigter Daten

Datentypen:Sätze und Satzmengen

Operatoren:Operatoren auf Sätzen

Datentypen:Satzmengen

Operatoren:Operatoren auf Mengen

Datentypen:phys. Zugriffsstrukturen auf Sätze

Operatoren:seq. Durchlauf, gezielte Suche

Optimaler Einsatz der logischen Ressourcen

Performanz

3


Kapitel 3.1Kapitel 3.1

Struktur: Segmente und SeitenStruktur: Segmente und Seiten

4


Segmente vs. Dateien

Struktur: Segmente mit Seiten Seiten sind nichtflüchtig Keine Differenzierung zwischen

Haupt- und Hintergrundspeicher Verdeckter Datentransport

zwischen Haupt- und Hintergrundspeicher

Performanz: Erzielen einer gleichmäßigen Zugriffszeit, möglichst weit unter den Hintergrundspeicher-zugriffszeiten liegend

Skalierbarkeit durch dynamisches Wachstum und Schrumpfen

Zuverlässigkeit: Verlustfreiheit

Struktur: Dateien mit log. Blöcken

Blöcke sind nichtflüchtig Speicherung im

Hintergrundspeicher, Verarbeitung im Hauptspeicher Kontrollierter Datentransport


Blockbezogene Performanzüberlegungen


Basis-Zuverlässigkeit

5


Segmenttypen (1)

Segmenttyp: Klassifizierung nach zusätzlichen Eigenschaften.

Segmenttyp

Eigenschaft 1 2 3 4 5

Benutzung öffentlich privat privat privat privat

Lebensdauer dauerhaft dauerhaft dauerhaft dauerhaft temporär

Öffnen und Schließen

automatisch explizit durch Benutzer

Wiederherstlg. im Fehlerfall

automatischexplizit d. Benutzer

nicht möglich

steigende Performanz

abnehmender Verwaltungsaufwand

6


Segmenttypen (2)

Segmenttyp: Klassifizierung nach zusätzlichen Eigenschaften.

Segmenttyp

Eigenschaft 1 2 3 4 5

Benutzung öffentlich privat privat privat privat

Lebensdauer dauerhaft dauerhaft dauerhaft dauerhaft temporär

Öffnen und Schließen

automatisch explizit durch Benutzer

Wiederherstlg. im Fehlerfall

automatischexplizit d. Benutzer

nicht möglich

zur Speicherung von Nutzerdaten, die gemeinsamen (konkurrierenden) Zugriff erlauben

zur Speicherung von Systemdaten (Loginformation, Leistungs- und Abrechnungsdaten)

für spezielle Aufgaben, bspw. für die Sortierung einer Zwischenrelation.

7


Abbildung von Segmenten auf Dateien

Struktur: Segmente mit Seiten Seiten sind nichtflüchtig Keine Differenzierung zwischen

Haupt- und Hintergrundspeicher Verdeckter Datentransport


Performanz: Erzielen einer gleichmäßigen Zugriffszeit, möglichst weit unter den Hintergrundspeicher-zugriffszeiten liegend


Zuverlässigkeit: Verlustfreiheit

Struktur: Dateien mit log. Blöcken

Blöcke sind nichtflüchtig Speicherung im

Hintergrundspeicher, Verarbeitung im Hauptspeicher Kontrollierter Datentransport


Blockbezogene Performanzüberlegungen


Basis-Zuverlässigkeit

1:1 oder n:1

1:1

Für Performanzbetrachtungen behalte deshalb im Hinterkopf: Seiten sind Transporteinheiten

Bei einer allgemeineren Beziehung: Zusätzlicher,

hoher Verwaltungsaufwand

8


1

1..

Zusammenhänge

Physische Platte

Partition

Zylinder Spur Sektor

Datei Log. Blockenthält ▶

1..

1..

1

1..

1

enthält ▶

1 1..enthält ▶

1 1..enthält ▶

1 1..

1

1repräsentiert

durch▼

Segment Seiteenthält ▶

1..1..

1

1repräsentiertdurch

▼ 1

liegt in▼

umfasst

▼

umfasst▼

▲gehört zu

▲gehört zu

9


Segmentorganisation

Fazit: Ein Segment ist ein linearer logischer Adressraum mit sichtbaren Seitengrenzen. Operatoren ähnlich wie bei Dateien: Definieren, Freigeben,

Öffnen und Schließen von Segmenten.

Seiten sind die atomaren Zugriffseinheiten für Segmente. Alle Seiten eines Segments haben die selbe Größe.

Innerhalb eines Segments werden Seiten adressiert.

Operatoren auf Seiten komplizierter siehe Pufferverwaltung.

10


Direkte Seitenabbildung (1) Prinzip:

Ein Segment wird auf eine Menge von Blöcken einer Datei abgebildet, die einen zusammenhängenden Adressbereich umfassen (Beispiel: Block 1000 - Block 1800).

Sei k+1 der erste Block, der für das Segment S reserviert ist.

Dann gilt: Seite Pi wird auf Block Bk+i gespeichert.

Beurteilung: Einfache Verwaltung bei Segment:Datei = 1:1. Dagegen bei Segment:Datei = n:1

Reservierung von Blöcken bei Erzeugen eines Segments erforderlich, daher kein dynamisches Wachstum des einzelnen Segments (außer dem letzten) möglich.

Effizienter sequenzieller Zugriff auf eine Folge von Seiten, sofern nicht zu viele Transaktionen verzahnt ablaufen.

11


B2

Bk+2

B3

Bk+3

B4

...

...

Bk+n

Bk

B1

Bk+1

S1

S2

P1 P2 P3 ... Pk P1‘ P2‘ P3‘ ... Pn‘

Segment S1

Segment S2

Direkte Seitenabbildung (2)

12


Indirekte Seitenabbildung (1)

Prinzip (Indirektion): Blöcke werden Seiten nicht direkt (statisch) zugeordnet,

sondern indirekt über eine Seitentabelle. Jedes Segment erhält eine eigene Seitentabelle. Die Seitentabelle zu einem Segment S enthält für jede Seite

von S einen Eintrag; der i-te Eintrag der Seitentabelle enthält die Nummer des Blocks, auf der Seite Pi gespeichert ist.

Enthält die Seitentabelle eine ungültige Blocknummer (bspw. 0), dann ist die entsprechende Seite leer (sie belegt dann auch keinen Block auf der Platte).

13


B2

Bk+2

B3

Bk+3

B4

...

B5

...

Bk+n

Bk

B1

Bk+1

P1 P2 P3 ... Pk P1‘ P2‘ P3‘ ... Pn‘

Segment S1

Segment S2

B2 B4 B5 ... Bk+2 B1 Bk B3 ... Bk+3

Seitentabelle von S1

Seitentabelle von S2


14


Beurteilung: Bessere Lösung bei Segment:Datei = n:1, da dynamische

Speicherausnutzung. Jedoch: Die Seitentabelle muss dauerhaft gespeichert

werden, d.h. sie muss ebenfalls auf Blöcke der Platte abgebildet werden.

Bei großen Segmenten kann ein Seitenzugriff zu zwei Blockzugriffen führen, da ggf. erst der eintragsrelevante Teil der Seitentabelle eingelagert werden muss.

Im schlimmsten Fall führt dies zu doppelten Zugriffskosten im Vergleich zur direkten Seitenadressierung.

Schlechte Leistung bei sequenziellem Zugriff während niedriger Transaktionslast.

Abhilfe: Allokation von Blockgruppen statt einzelner Blöcke. Freispeicherverwaltung erforderlich (üblich: Bitliste).


15



Dynamik: PufferorganisationDynamik: Pufferorganisation

16


Transaktionen in der Architektur

Mengenorientiertes Datenmodell

Anfragebearbeitung

Satzorientiertes Datenmodell

Satz- u. Satzmengenverwaltung

Satzzugriffsstrukturen

Zugriffsschicht

Hauptspeicherseiten u. Segmente

Dateien

Dateiverwaltung

Geräteschnittstelle

Scheduler

Recovery-Verwalter

Segment- u. Pufferverwaltung

Transaktion:Eine vom Benutzer als abgeschlossene Arbeitseinheit definierte Folge von Anfragen (Operatoren auf Mengen)

17


Architektur im Detail – 1. Schritt

Transaktion 1 Transaktion 2 ... Transaktion n

Scheduler

Segment-Verwalter

Schedule 1 Schedule n

Sperren-Verwalter

Puffer- Verwalter

Daten-basis

d4 d43 d17 d15 d2 d58

d5 d9 d26 d69 d6 d16

d46 d68 d55 d32 d97 d49

d25 d20 d67 d30 d49 d37

d19 d34 d10 d24 d25 d94

d63 d82 d49 d92 d57 d8

Daten-seiten

Transaktionsverwaltung

Gesamt-Schedule (verzahnte Transaktionen)

Performanz

18


Systempuffer

Systempuffer: Bereich des Hauptspeichers, der allen Transaktionen gemeinsam für die Pufferung von Blöcken zur Verfügung steht. Über ihn werden alle Lese- und Schreibanforderungen aller

parallelen Transaktionen abgewickelt. Dominierendes Problem:

Große Datenbasen können bis zu 10 TB umfassen! Beispiel: Die Decision-Support-Datenbank von WalMart umfaßt 6 TB; die größte Tabelle hat 4 Mrd. Tupel; jeden Tag werden 200 Millionen Tupel eingefügt/modifiziert.

Große Server-Rechner können bis zu mehreren GB Hauptspeicher besitzen.

Dieser muss den ausführbaren Code der aktiven Anwendungsprogramme (insbesondere des DBMS) sowie den Kern des Betriebsystems speichern.

Der Rest kann für den Systempuffer verwendet werden.

19


Aufgabenstellung

Problem: Da der Systempuffer wesentlich kleiner als die Datenbasis ist, konkurrieren Transaktionen um Platz im Systempuffer.

Ziel der Systempufferverwaltung: Dynamische Verwaltung des Pufferplatzes so dass die Anwendungen soweit wie möglich die Begrenzung des Systempuffers nicht bemerken. Aufgabe: Erzielen einer gleichmäßigen, möglichst weit unter

den Seitenzugriffszeiten liegenden Zugriffszeit.

Grundsätzliche Lösung: Jeweils die Seiten im Systempuffer halten, die die Transaktionen benötigen.

Voraussetzung: Hinreichende Größe des Systempuffers ist für die Leistungsfähigkeit des DBMS von entscheidender Bedeutung.

20


Speicherzuteilungsstrategien (1)

Speicherzuteilung

lokal(transaktionsbezogen) global anwendungsbezogen seitentypbezogen

statischdynamischdynamisch statisch

Lokale Speicherzuteilung Für jede Transaktion wird ein Menge von Seitenrahmen

reserviert. Statisch: einmalige und dann feste Zuteilung.

Wechselnde Anforderungen an den erforderlichen Pufferplatz können nicht zum Ausgleich zwischen den Transaktionen genutzt werden.

Dynamisch: Speicherzuteilung abhängig vom aktuellen Bedarf. Reine Lokalstrategie:

Es wird nicht erkannt, wenn Seiten mehrfach (von unterschiedlichen Transaktionen) eingelagert werden.

21



Speicherzuteilung



Globale Speicherzuteilung Verfügbare Seitenrahmen werden gemeinsam allen

Transaktionen zur Verfügung gestellt. Allokation für die einzelne Transaktion abhängig von deren

Bedarf. Keine reservierten Bereiche im Systempuffer.

22



Speicherzuteilung



Anwendungsbezogene Zuteilung Anwendungen definieren dynamisch Gruppen von

Seitenrahmen, die für bestimmte Zwecke genutzt werden können. Bsp.: Eine Gruppe für CAD-Anwendungen und eine Gruppe

für „klassische“ Anwendungen. Größe der Gruppen entweder statisch festgelegt oder

dynamisch anpassbar. Bei jedem Seitenzugriff wird die Gruppe angegeben, in die

eine Seite eingelagert werden soll.

23



Speicherzuteilung



Seitentypbezogene Zuteilung Der Systempuffer wird in Gruppen eingeteilt, die durch die

Seitentypen vorgegeben sind (pro Typ eine Gruppe). Bsp.: Es werden Gruppen definiert für Datenseiten,

Systemseiten, Seiten für bestimmte Arten von Zugriffsstrukturen (B-Baum, Hashtabelle, usw.)

Größe der Gruppen entweder statisch festgelegt oder dynamisch anpassbar.

Beim Einlagern einer Seite wird die Gruppe anhand des Typs bestimmt.

24



Speicherzuteilung



Zu inflexibel, daher nur selten. Falls statisch: Eine neue Transaktion, die noch wartend ist,

wird gestartet, sobald die notwendige Anzahl von Seitenrahmen verfügbar ist (Preclaiming-Strategie).

Zu inflexibel bei Änderungen des Lastverhaltens.

Gängig: Zwei Anwendungsgruppen:für relativ kurze Datensätze (z.B. relationale Tupel),für große Objekte (BLOB, XML-Objekte, Textobjekte, Bilder).

Jede Gruppe global oder seitentypbezogen.

25



Speicherzuteilung

lokal(transaktionsbezogen) global gruppenbezogen seitentypbezogen


Gängig: Zwei Anwendungsgruppen :für relativ kurze Datensätze (z.B. relationale Tupel),für große Objekte (BLOB, XML-Objekte, Textobjekte, Bilder).

Jede Gruppe global oder seitentypbezogen.

Gegenstand der weiteren Betrachtungen

26



Puffer-OperationenPuffer-Operationen

27


Pufferorganisation

Der Systempuffer besteht aus N im Hauptspeicher angeordneten Pufferrahmen, von denen jeder genau eine Seite speichern kann.

Puffer-Kontrollblock mit einem Eintrag für jeden Rahmen. Für eine zu schreibende Seite wird ein Änderungsvermerk (dirty bit) gesetzt.

Scheduler

Puffer- Verwalter

Daten-basis

d4 d43 d17 d15 d2 d58

d5 d9 d26 d69 d6 d16

d46 d68 d55 d32 d97 d49

d25 d20 d67 d30 d49 d37

d19 d34 d10 d24 d25 d94

d63 d82 d49 d92 d57 d8

Daten-seiten

Segment-Verwalter

28


Externe Pufferoperationen

Mögliche Abfolgen:Nur Lesen: read, unfixÄndern: read, writeErzeugen: allocate, write

Scheduler

Puffer- Verwalter

Daten-basis

d4 d43 d17 d15 d2 d58

d5 d9 d26 d69 d6 d16

d46 d68 d55 d32 d97 d49

d25 d20 d67 d30 d49 d37

d19 d34 d10 d24 d25 d94

d63 d82 d49 d92 d57 d8

Daten-seiten

Segment-Verwalter

read (pageno, t)Sorgt dafür dass Seite pageno im Puffer liegt und fixiert sie dort für Transaktion t.

write (pageno, t)Erklärt Änderung der Seite für abgeschlossen. Pufferverwaltung markiert Seite als dirty.

allocate (pageno, t)Allokiert einen Seitenrahmen für eine neue Seite.

Aus technischen Gründen:unfix (pageno, t)Seite wird von Transaktion t nicht mehr benötigt.

29


Direkter Zugriff auf gepufferte Seiten Bei read und allocate wird dem Aufrufer die Adresse des

Seitenrahmens übergeben, in den die Seite eingelagert wurde.

Der Benutzer liest bzw. schreibt direkt auf dem Seitenrahmen. Vorteil: Keine zusätzliche Indirektionsstufe. Nachteile:

Die eingelagerte oder alloziierte Seite darf vom Puffer-Verwalter nicht im Systempuffer verschoben werden.

Ob die Seite verändert wurde, muss dem Puffer-Verwalter ausdrücklich (durch write) mitgeteilt werden.

Der Puffer-Verwalter besitzt keine Kenntnis darüber, welche Teile der Seite geschrieben wurden. Recovery muss also eine veränderte Seite insgesamt sichern (siehe später!).

Unerlaubte Zugriffe auf eine Seite nach write oder unfix sind möglich.

30


Platte

P480

P123

Systempuffer0 4K 8K 12K

28K

44K

60K

40K

48K

24K20K16K

32K 36K

56K52K

(P123)

(P480)

Adresse:40KAdresse: 48K

Direkter Zugriff auf gepufferte Seiten

write

31


Bei Aufruf wird dem Aufrufer ein Handle übergeben, über den er auf den Seiteninhalt (lesend oder schreibend) zugreifen kann. Er darf nicht direkt auf den Seitenrahmen zugreifen.

Vorteile: Das System entdeckt selbständig Änderungen an der Seite:

Es kann diese mit protokollieren. Recovery muss nur die geänderten Teile der Seite sichern.

Eine Seite kann im Systempuffer verschoben werden. Im Handle kann vermerkt werden, ob die Seite geschrieben

werden darf. Durch die Indirektion können unerlaubte Zugriffe auf eine

Seite nach einem write oder unfix abgefangen werden. Nachteile: Zusätzliche Indirektionsstufe,

Verwaltungsaufwand für Handles.

Indirekter Zugriff auf gepufferte Seiten

32


Platte

P480

P123

Systempuffer0 4K 8K 12K

28K

44K

60K

40K

48K

24K20K16K

32K 36K

56K52K

(P123)

(P480)

Indirekter Zugriff auf gepufferte Seiten

Handle 1

Seite: P480 Adresse: 48K Schreibbar: 1

Seite: P123 Adresse: 40K Schreibbar: 0

Handle 2write

33


Interne Pufferoperationen

fetch (pageno)Kopiert eine nicht gepufferte Seite aus der Datenbasis in den Puffer.

flush (pageno)Kopiert eine nicht fixierte Seite vom Puffer in die Datenbasis sofern die Seite als dirty markiert ist. Die Seite verbleibt im Puffer, wird aber alsclean markiert.

(Beide Operatoren besorgen sich die zu pageno gehörende Blockadresse vom Segmentverwalter.)

pin (pageno)Fixiert eine Seite im Puffer (automatisch mit read und allocate).

unpin (pageno)Löst auf write oder unfix hin die Fixierung der Seite im Puffer.

Scheduler

Puffer- Verwalter

Daten-basis

d4 d43 d17 d15 d2 d58

d5 d9 d26 d69 d6 d16

d46 d68 d55 d32 d97 d49

d25 d20 d67 d30 d49 d37

d19 d34 d10 d24 d25 d94

d63 d82 d49 d92 d57 d8

Daten-seiten

Segment-Verwalter

34


Koordination Scheduler und Pufferverwalter

Scheduler

Puffer- Verwalter

Daten-basis

d4 d43 d17 d15 d2 d58

d5 d9 d26 d69 d6 d16

d46 d68 d55 d32 d97 d49

d25 d20 d67 d30 d49 d37

d19 d34 d10 d24 d25 d94

d63 d82 d49 d92 d57 d8

Daten-seiten

pin(), unpin()

fetch(), flush()

read(), write(), allocate(), unfix()

So unabhängig voneinander als möglich!

Falls fetch erforderlich: zeitlich gekoppelt (synchron)!

Segment-Verwalter entkoppelt!

35


Bearbeiten einer Seitenanforderung (1)

Scheduler

Puffer- Verwalter

Daten-basis

d4 d43 d17 d15 d2 d58

d5 d9 d26 d69 d6 d16

d46 d68 d55 d32 d97 d49

d25 d20 d67 d30 d49 d37

d19 d34 d10 d24 d25 d94

d63 d82 d49 d92 d57 d8

Daten-seiten

pin(), unpin()

fetch(), flush()

read(), write(), allocate(), unfix()

Segment-Verwalter

physische Seitenreferenz

logische Seitenreferenz

36



Gewünschte (read) Seite im Puffer?ja nein (Fehlseitenbedingung)

logische Seitenreferenz ohne physische Seitenreferenz

Lokalisierung der Seite (Bestimmung des Seitenrahmens, in dem die Seite gepuffert ist)

Durchführung der pin-Operation Fortschreiben der

Pufferkontrollblöcke Übergabe der Adresse des

Seitenrahmens an die aufrufende Komponente

Aufwand: 100 Instruktionen

logische Seitenreferenz mit physischer Seitenreferenz

Erfolglose Suche im Puffer Suche nach einem freien

Seitenrahmen; falls keiner vorhanden:

Auswahl einer zu ersetzenden Seite.

Falls die zu ersetzende Seite als dirty markiert:

flush der Seite auf den nichtflüchtigen Speicher

fetch der angeforderten Seite Aufwand: 2500 Instruktionen +

Blockzugriffszeit (20-30 ms)

37


















Kein zeitlicher Zusammenhang mit write!

38


Strategien der Pufferverwaltung
















39



Effizientes Auffinden einer Seite im Puffer (Suchstrategie). Wahl der zu bevorratenden Seiten im Systempuffer

(Einlagerungsstrategie). Auswählen eines (praktisch immer belegten) Pufferrahmens

für eine einzulagernde Seite (Ersetzungsstrategie).

40



Pufferverwaltung: LokalisierenPufferverwaltung: Lokalisieren

41






42


Suchstrategie Bei jeder logischen Seitenreferenz hat die Pufferverwaltung

zunächst festzustellen, ob die angeforderte Seite sich bereits im Systempuffer befindet, und falls ja, wo.

Häufiges Ereignis; daher effizientes Suchverfahren wichtig!Suchstrategie für Seiten im Systempuffer

Direkte Suche in den Seitenrahmen

Indirekte Suche über Hilfsstrukturen

Hashverfahren Puffertabellen Zuordnungstabellen

unsortiert sortiert verkettet

X

43


Hashverfahren (1)Suchstrategie für Seiten im Systempuffer



Suche in Tabelle: Seitennummer Tabellenposition Pufferadresse

Alle Hashverfahren mit direkter Kollisionskontrolle einsetzbar. Bucketverfahren mit Verkettung von Überlaufblöcken. Verkettung von Tabelleneinträgen.

Hashfunktion

44


Hashverfahren

( ) ( )ih P HT k

Pi: Seitennummer PAi: Pufferadresse

Systempuffer

Beispiel Verkettung:

Pj PAj

Pk PAk

Pi PAi //

45


Puffertabelle

Suchstrategie für Seiten im Systempuffer



Suche in Tabelle: Seitenrahmen Seitennummer Pufferadresse

unsortiert: hoher Suchaufwand.

nach Seitennummern sortiert: hoher Wartungsaufwand. gegebenenfalls Repräsentation durch einen balancierten Binärbaum.

Berechnung

46


Zuordnungstabelle

Suchstrategie für Seiten im Systempuffer



Suche in Tabelle: Seitennummer Pufferadresse oder nicht gepuffert

Sehr hoher Such- und Platzaufwand, daher nur bei kleinen Datenbasen anwendbar.

47



Pufferverwaltung: Einlagern/ErsetzenPufferverwaltung: Einlagern/Ersetzen

48






Positiventscheidung: Welche Seiten im Puffer vorhalten?Negativentscheidung: Auf

welche Seiten kann man verzichten? Enger Zusammenhang!

49


Aufgabe Die Größe des Systempuffers legt fest, wie viele Seiten

gleichzeitig im Systempuffer gehalten werden können. Extremfälle:

Bei einer Systempuffergröße von 1 führt jede logische Seitenreferenz zu einer physischen Seitenreferenz.

Passt die gesamte DB in den Systempuffer, dann sind (nach einer Ladephase, in der alle Seiten in den Systempuffer geladen werden) keine physischen Seitenreferenzen mehr notwendig.

Allgemein: Das Ziel der Systempufferverwaltung ist die Minimierung der Zahl der physischen Seitenreferenzen bei gegebener Systempuffergröße und gegebenem Profil der logischen Seitenreferenzen. Dazu wird ein Vorhersagemodell benötigt.

50


Vorhersagemodell (1)

Vorhersagemodell: Schätze zukünftigen logischen Seitenreferenzstring ab. Charakterisierung (Logische) Lokalität:

Menge der in gegebenem Zeitintervall benötigten Seiten Gibt es sehr viele Zugriffe auf wenige ausgeprägte Seiten?

Lokale Lokalität: Verhalten einer einzelnen Transaktion. Globale Lokalität: Verhalten einer Menge von Transaktionen.

Charakterisierung (Logische) Sequenzialität: Menge der in gegebenem Zeitintervall benötigten Seiten Gibt

es eine Abfolge von benötigten Seiten?

51


Einflussfaktoren (1) Äußere Einflussfaktoren:

Datenmodell, Struktur der physischen DB (Dateien, Satzzugriffsstrukturen) Zugriffsverhalten der Anwendungen (Transaktionsmix).

Klassische Anwendungen (debit/credit Transaktionen, Verwaltung betriebswirtschaftlicher und administrativer Daten): Globale Lokalität entsteht vorwiegend durch gemeinsame

Zugriffe mehrerer Transaktionen auf „wichtige“ Seiten. Bestimmte Seiten mit Verwaltungsdaten haben eine wesentlich

höhere Benutzungswahrscheinlichkeit als „normale“ Datenseiten. Die Zugriffe innerhalb einzelner Transaktionen sind

weitgehend sequenziell (hohe lokale Sequenzialität). Inter-transaction locality, intra-transaction sequentiality.

52


Globale Lokalität: Referenzdichte (1)

Relativer Anteil bestimmter Seitentypen in der DB: FPA: Seiten für die Freispeicherverwaltung. DBTT: Seiten für die Adressumsetzung. USER: Benutzerseiten.

Visualisierung der Referenzierungshäufigkeit der Seitentypen: x-Achse: Positionen im logischen Seitenreferenzstring. y-Achse: Relative Häufigkeit der Seitentypen FPA, DBTT,

USER im log. Seitenreferenzstring (seitentyp-spezifische Referenzdichte).

53


Globale Lokalität: Referenzdichte (2) Beispiel MIX40: änderungsintensive Last mit relativ hoher Lokalität. FPA: Seiten für die Freispeicherverwaltung (0.1 % aller Seiten). DBTT: Seiten für die Adressumsetzung (6.1 % aller Seiten). USER: Benutzerseiten (93.8 % aller Seiten).

54


Folgerungen aus Referenzdichte

Die Referenzdichte-Kurve zu MIX40 zeigt, dass die Benutzung von Seiten stark von dem Seitentyp abhängt, und im zeitlichen Verlauf starken Schwankungen unterworfen ist.

Seiten für die Adressumsetzung und für die Freispeicherverwaltung werden überproportional häufig referenziert; reine Benutzerseiten dagegen unterproportional häufig.

Folgerung: Speicherzuteilung und Seitenersetzung sollte abhängig vom Seitentyp erfolgen.

55


Einflussfaktoren (2)

Äußere Einflussfaktoren: Datenmodell, Struktur der physischen DB (Dateien, Satzzugriffsstrukturen) Zugriffsverhalten der Anwendungen (Transaktionsmix).

Nicht-klassische Anwendungen (interaktive Nutzung von Datenbasen, technische Anwendungen bspw. im CAD-Bereich): Hier besteht häufig auch hohe lokale Lokalität durch

Beschränkung einer Transaktion auf eine Teilmenge von Seiten (ein Konstrukteur benötigt bspw. über einen längeren Zeitraum nur die Daten, die das gerade konstruierte Teil beschreiben).

Sequenzielle Zugriffe sind seltener.

56


Vorhersagemodell (2)

Vorherrschende Strategie: Einheitliche Behandlung von globaler und lokaler Lokalität.

Grundlage: Vorhersage durch Pufferverwaltung selbst.

Vorgehensweise: Pufferverwaltung beobachtet Logischen Seitenreferenzstring als zeitliche Folge der logischen Seitenreferenzen aller paralleler Transaktionen.

Nachteil: Zur Abschätzung der zukünftigen logischen Seitenreferenzstrings steht nur der vergangene logische Seitenreferenzstring zur Verfügung.

57


Lokalität: Stacktiefe (1) Modellierung der Lokalität durch LRU-Stacktiefen-

Verteilungen. LRU: Seiten mit Hilfe eines Kellers verwaltet.

jüngste referenzierte Seite an der Kellerspitze. mit zunehmendem Zurückliegen des Referenzzeitpunkts sinkt

die Seite im Keller ab.

Visualisierung: x-Achse: LRU-Stacktiefe (Position im Keller, an der sich eine

Seite befindet). y-Achse: Wahrscheinlichkeit, dass eine Seite sich in einer

bestimmten Stacktiefe befindet.

58


Lokalität: Stacktiefe (2) Beispiel MIX40: änderungsintensive Last mit relativ hoher Lokalität. Logischer Seitenreferenzstring mit 130.366 logischen Seitenreferenzen. Anzahl verschiedener Seiten im String: 3.553 Maximale Anzahl paralleler Transaktionen: 8

59


Lokalität: Stacktiefe (3) Beispiel MIX50: Transaktionsmix mit langen sequentiellen

Lesetransaktionen, kaum Änderungsoperationen. Logischer Seitenreferenzstring mit 99.975 logischen Seitenreferenzen. Anzahl verschiedener Seiten im String: 5.245 Maximale Anzahl paralleler Transaktionen: 8

60


Gegenstand der weiteren Betrachtungen Demand Paging

Ersetzen genau einer Seite bei Auftreten einer Fehlseitenbedingung.

Einzig sinnvolles Vorgehen bei Vorhersage durch Pufferverwaltung selbst.

Prepaging Austausch mehrerer Seiten bei einem Ersetzungsvorgang mit

Einlesen weiterer Seiten über die angeforderte hinaus. Vorhersage durch jede Transaktionen erforderlich. Sinnvoll bei hoher und vorhersagbarer lokaler Sequenzialität

oder Lokalität Unterstützbar durch physische Bündelung der benötigten Seiten

auf benachbarten Blöcken.

Einlagerungsstrategien

61


Seitenersetzungsstrategien (1)

Aufgabe: Festlegen, welche Seiten bei einem Entzug von Seitenrahmen zur Verdrängung ausgewählt werden sollen.

Grundsatz: Falls eine logische Seitenreferenz im Puffer nicht befriedigt werden kann, muss eine Seite zur Ersetzung ausgewählt („verdrängt“) werden, die längere Zeit nicht mehr benötigt wird. Also: Kein flush auf Seite, die bald wieder benötigt wird.

Randbedingung: Faire Behandlung jeder Transaktion.

62


Seitenersetzungsstrategien (2) Strategien beruhen darauf, dass ohne Handle nur das

Fixieren beobachtbar ist. Eine Transaktion fixiert eine Seite so lange, bis sie sie nicht

mehr benötigt.

Randbedingungen:

Fixierte Seiten werden mit Hauptspeicheradressen angesprochen; sie dürfen folglich nicht ersetzt werden. Werden daher in den nachfolgenden Verfahren ignoriert!

Referenzen beziehen sich ausschließlich auf den Fixierungszeitpunkt.

Eine Fixierung wird also als genau eine Referenz gezählt, unabhängig von der Anzahl der Zugriffe auf die Seite über ihre Pufferadresse.

63


Eingrenzung der realisierbaren Ersetzungsstrategien:

Extremstrategien: RANDOM: Wähle zufällig eine Seite zur Ersetzung aus.

OPT: Wähle diejenige Seite zur Ersetzung aus, deren zeitlicher Abstand bis zur nächsten Referenzierung maximal ist.

Klar: OPT ist nicht realisierbar.

Ziel: Ersetzungsstrategien sollten möglichst nahe an OPT heranreichen.

Visualisierung (Fmax: maximale Fehlseitenrate (in %))

Seitenersetzungsstrategien (3)

64


Grundsatz: Abstützen auf den Erwartungswert für eine

Wiederbenutzung. Ersetzung von Seiten, deren Erwartungswert minimal ist.

Zur Bestimmung des Erwartungswerts wird das bisherige Referenzverhalten analysiert und auf das zukünftige Verhalten extrapoliert.

Analysemöglichkeiten: Zeit seit der letzten Einlagerung, Zeit seit der letzten Referenzierung, Anzahl der bisherigen Referenzen.

Jedes dieser Kriterien besitzt für sich allein zu wenig Aussagekraft, daher Kombination von Kriterien wünschenswert.

Praxis der Ersetzung

65


LRU (least recently used) Ersetzungskriterium: Zeit seit der letzten Referenzierung der Seite. Seiten im Systempuffer werden mit Hilfe eines Kellers verwaltet. Bei Referenz kommt die referenzierte Seite an die Kellerspitze. Falls die referenzierte Seite an Position n im Keller war, rutschen alle

Seiten an den Positionen 1 bis n-1 eine Position tiefer. Seite am Kellerboden wird ersetzt.

Ersetzungsverfahren - LRU

C

A

B

C

D

E

F

C

A

B

66


Ersetzungsverfahren - LRU

G

A

B

C

D

E

F

GG

A

B

C

D

E

LRU (least recently used) Ersetzungskriterium: Zeit seit der letzten Referenzierung der Seite. Seiten im Systempuffer werden mit Hilfe eines Kellers verwaltet. Bei Referenz kommt die referenzierte Seite an die Kellerspitze. Falls die referenzierte Seite an Position n im Keller war, rutschen alle

Seiten an den Positionen 1 bis n-1 eine Position tiefer. Seite am Kellerboden wird ersetzt.

F

67


CLOCK (second chance) Im Grundsatz LRU mit einfacherer Implementierung. Ersetzungskriterium: Zeit seit der letzten Referenzierung. Jede Seite mit Benutzt-Bit.

Beim Einlagern einer Seite auf 1 gesetzt. Bei jeder Referenzierung einer Seite auf 1 gesetzt.

Auswahl einer zu ersetzenden Seite: Zyklischer Umlauf bis zur nächsten Seite mit 0. Alle überstrichenen Seiten mit 1 werden auf 0 zurückgesetzt.

Ersetzungsverfahren - CLOCK

G

1 A

0 F 1 B

0 C0 E

0 D

1 A

0 F 0 B

0 C0 E

0 D

1 A

1 F 0 B

1 G0 E

0 D

C

68


LFU (least frequently used) Ersetzungskriterium: Zahl der Referenzen. Jede Seite im Puffer mit Referenzzähler, der bei

Seiteneinlagerung mit 1 initialisiert wird. Bei jeder Seitenreferenz wird der Zähler um 1 erhöht. Ersetzt wird die Seite mit dem niedrigsten Zähler.

Bei gleichen Zählerständen wird eine nach dem LRU-Prinzip ausgewählt

Nachteil: keine Berücksichtigung der Zeit seit der letzten Einlagerung (Alter) der Seiten, daher sind Seiten mit kurzzeitiger, sehr hoher Referenzierung kaum mehr zu verdrängen.

Ersetzungsverfahren - LFU

69


GCLOCK (generalized clock) Kombination aus LFU und CLOCK; anstelle Benutzt-Bit

Referenzzähler. Hochzählen des Referenzzählers um 1 bei Seitenreferenz. Herabzählen um 1 bei Überstreichen. Ausgelagert wird die erste Seite, die nach Herabzählen

einen Referenzzähler = 0 besitzt. Verbesserung gegenüber LFU: Referenzhäufigkeit wird

direkt, Alter indirekt berücksichtigt. Nachteil: Wegen indirekter Berücksichtigung des Alters

tendiert auch GCLOCK dazu, die jüngsten Seiten zu ersetzen, unabhängig von ihrer Wiederbenutzungswahrscheinlichkeit.

Ersetzungsverfahren - GCLOCK

70


Verbesserungen von GCLOCK: Berücksichtigung des Seitentyps bei

Initialisierung der Referenzzähler, Inkrementierung der Referenzzähler bei einer Referenzierung

oder fest-vorgegebenem Wert, auf den die Referenzzähler bei einer

Referenzierung gesetzt werden.

Protokollierung der Ersetzungshäufigkeiten der Seiten: Dynamische Gewichtung der Inkremente und Initialisierung der

Referenzzähler (höhere Gewichte für „wichtige“ Seiten). Durch die dynamische Gewichtung können sehr hohe

Referenzzählerwerte entstehen, die bei einem Lastwechsel nicht mehr mit dem Referenzierungsverhalten der Anwendungen übereinstimmen.

Daher: Periodisches Herabsetzen der Referenzzähler oder Vorgabe von Maximalwerten.

Ersetzungsverfahren - GCLOCK

71


LRD (least reference density) GZ: Anzahl aller logischen Referenzen insgesamt. SZ: Vektor mit einer Komponente für jede Seite; bei

Einlagerung von Seite i wird SZ(i) mit dem aktuellen Wert von GZ initialisiert.

RZ: Vektor mit einer Komponente für jede Seite; RZ(i) ist die Gesamtanzahl der logischen Referenzen von Seite i während aktuellem Pufferaufenthalt.

Berechnung der mittleren Referenzdichte pro Seite i:

RD(i) = RZ(i) / ( 1 + GZ - SZ(i) ) Grundidee von LFU + direktes Einbringen des Alters. Vorteil gegenüber LFU: Junge Seiten haben

Überlebenschancen

Ersetzungsverfahren - LRD (1)

72


GZ+1= 50


2 20 A

4 26 B

1 40 C

3 45 D

3 5 E

6 2 F

1 37 G

3 17 H

RZ SZ RD1/15

1/10

1/6

3/5

1/15

1/8

1/13

1/11

zur Ersetzung gewählt

73


Verbesserung: Periodisches Altern von Seiten, indem nach 1000 logischen Referenzen die RZ-Werte aller älteren Seiten entsprechend zurückgesetzt werden. Seiten mit weit zurückliegender sehr hoher Referenzdichte werden

dadurch schneller verdrängt. Problem: Zur Bestimmung eines zu verdrängenden Elements

muss für jedes Element der Wert von RD(i) berechnet werden Dieser verändert sich dynamisch bei jeder neuen Seitenreferenz Die Ordnung der Elemente bzgl. den Referenzdichten bleibt dabei

(auch für nicht referenzierte Elemente) nicht konstant Beispiel: Man hat zwei Seiten 1 und 2 mit

RZ(1) = 1 und GZ – SZ(1) = 1, also RD(1) = 1/2 RZ(2) = 7 und GZ – SZ(2) = 15, also RD(2) = 7/16 Es gilt also RD(1) > RD(2) Nach dem nächsten Zugriff (beide Seiten nicht referenziert):

RD(1) = 1/3 = 0.333… und RD(2) = 7/17 = 0.41…Nun gilt also plötzlich RD(2) > RD(1)


74



BetriebssystemfragenBetriebssystemfragen

75


Logische Zuordnung von Datenbank zu virtuellem Speicher zu Hauptspeicher (üblich: M < N < D):

Konflikt Systempuffer und virtueller Speicher

Datenbank auf dem Externspeicher

Systempuffer-verwaltung des DBMS

Datenbankseiten im Systempuffer

Seitenwechsel-algorithmus des Betriebsystems

Pufferseiten im Hauptspeicher

M

page faultN

database fault

D

Anzahl der Datenbasisseite

nAnzahl der

Pufferrahmen Anzahl der

Hauptspeicherkacheln

76


Hardware-Realisierung: Datenbank und virtueller Speicher sind auf externem Speicher realisiert.

M

Pufferseiten auf dem Seitenwechsel-speicher

referenzierte Seite

database fault:physische Seitenreferenz

page fault:Ein/ Auslagerungen von Seiten des virtuellen Adressraums

zu ersetzende Seite

D N


Datenbank auf dem Externspeicher

Systempuffer-verwaltung des DBMS

Seitenwechsel-algorithmus des Betriebsystems

Pufferseiten im Hauptspeicher

double page fault

77


Fehlseitenbedingungen:1. Page Fault

Benötigte Seite ist im Systempuffer, aber nicht im Hauptspeicher. Kann auch innerhalb der fix-Phase einer Seite auftreten.

1 Blockzugriff.

2. Database Fault Benötigte Seite ist nicht im Systempuffer, zu ersetzende

Seite ist im Hauptspeicherpuffer. 1 – 2 Blockzugriffe (je nach Änderungsvermerk).

3. Double Page Fault Benötigte Seite ist nicht im Systempuffer, zu ersetzende

Seite ist nicht im Hauptspeicherpuffer. 2 – 3 Blockzugriffe (je nach Änderungsvermerk).


78


Überlast: Eine Transaktion hält zu einem Zeitpunkt zu viele Seiten mit fix-Vermerk.

Folge: Verknappung an Pufferrahmen, die keinen fix-Vermerk besitzen.

1. Seitenflattern im Puffer (Thrashing) hohe relative Häufigkeit von logischen Seitenanforderungen, die

physische Seitenreferenzen zur Folge haben somit wachsende relative Häufigkeit der Seitenersetzung tritt bei großer Zahl paralleler Transaktionen auf Abhilfe:

Dynamische Beschränkung der Parallelität. Dazu müssen Transaktions- und Systempufferverwaltung

zusammenarbeiten. Bei Puffermangel werden keine neuen Transaktionen zugelassen.

2. Betriebsmittel-Verklemmung Pufferrahmen ohne fix-Vermerk erschöpft. Beseitigung der Verklemmung nur durch Zurücksetzen von

Transaktionen!

Systempuffer als Leistungsengpass

79


Die virtuelle Speicherverwaltung in Unix ist ein Beispiel dafür, dass ein Betriebssystem selbst eine Pufferverwaltung bietet (und erzwingt). Dynamische (prozess-)lokale Speicherzuteilung.

Virtueller Speicherbereich von Bytes.

Indirekter Zugriff.

Seitengrenzen sind berechenbar. Daher eine gewisse Kontrolle über Seitentransporte möglich.

Schwäche: Kein Einfluss möglich auf Einlagerungs- und Ersetzungsstrategie.

Virtuelle Speicherverwaltung in Unix (1)

80



Einzel-prozess

Virtueller Speicher

Hauptspeicher Hintergrundspeicher

Seite Blockgleiche Größe

Zuordnung

Zuordnung

81



Einzel-prozess

Virtueller Speicher



Zuordnung

Zuordnung

Ein Prozess besitzt einen virtuellen Speicher. Eine Speicheradresse ist normalerweise 4 Bytes lang, damit sind 4 GB

virtueller Speicher adressierbar. Annahme: Seitengröße = 1024 Bytes = 1 KB. Dann sind alle Adressen

im virtuellen Adressraum, die ganzzahlige Vielfache von 1K (1024) sind, gültige Seitenadressen (0, 1K, 2K, 3K, 4K, ...).

Eine virtuelle Speicheradresse lässt sich daher interpretieren als eine Seitenadresse und ein Offset innerhalb der Seite.Bei Seitengröße = 1K: Seitenadresse(22B) Offset(10B)

82



Einzel-prozess

Virtueller Speicher



Zuordnung

Zuordnung

Haupt- und Hintergrundspeicher werden von allen Prozessen geteilt.

SystempufferSegmente

83



Einzel-prozess

Virtueller Speicher



Zuordnung

Zuordnung

Zuordnungen mittels page table pro Prozess.

Virtuelle Adresse

HspSeite Nr.

Status Block

0 1K 2K 64K 1917 invalid 1206 65K none invalid none 66K 1036 valid 847

128K 17 ...

Gültigkeit der Adresszuordnung

84


Wird auf eine Adresse innerhalb des Bereichs 66K – 67K zugegriffen, dann wird dieser Zugriff auf die Hauptspeicher-Seite 1036 umgelenkt, da der dazu gehörige Eintrag der page table den Status valid besitzt.

Ein Zugriff auf eine Adresse im Bereich 64K – 65K führt dagegen zu einem page fault, da der zugehörige Eintrag invalid ist. Die virtuelle Speicherverwaltung liest Block 1206 von der Platte, kopiert ihn in die Hauptspeicher-Seite 1917 und setzt den Status auf valid.

Ein Zugriff auf eine Adresse im Bereich 65K – 66K oder auf eine Adresse außerhalb des reservierten virtuellen Speichers ( 129K) führt zu einer Speicherverletzung (segmentation fault).


Virtuelle Adresse

Seite Nr.

Status Block

0 1K 2K 64K 1917 invalid 1206 65K none invalid none 66K 1036 valid 847

128K 17 ...

Documents

Universität Karlsruhe (TH) © 2009 Univ,Karlsruhe, IPD, Prof. LockemannDBI 3 Kapitel 3 Segment- und Puffer- Verwaltung