Post on 06-Apr-2015
transcript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
Geoinformation
Mehrbenutzerzugriff auf GIS-Daten
Vorlesung 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
1
• Geodatenserver• mehrere Benutzer
– Transaktionen T• Anfragen, Methoden, Programme
– Items „A“• Variable, Tupel, Relation, Objekt
• Modi– Lesen (an und für sich unproblematisch)– Schreiben
• Erforderlich:– Synchronisation– Protokolle
Szenario
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
2
Programm (P): Read A; A:=A+1; Write A;
5 + 1 + 1 =/= 6 !
Problemfall
A in Datenbank
T1
:
A im Arbeitsspeicher T1
T2
:
A imArbeitsspeicher T2
5
Read A
A:=A+1 Write ARead
AA:=A+
1
Write A
5 6655
5 6 6665
5 665
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
3
Lösung: Sperren (Lock und Unlock)
Sperren verschafft dem Prozess P exklusiven Zugriff auf das Item A.
P : Read A;
Write A;A:=A+1;
Lock A; Unlock A
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
4
Problem: Gegenseitige Blockade („Deadlock“)
T 1:
Lock B; Unlock B;Unlock A;Lock A;
T 2:
Lock A; Unlock A;Unlock B;Lock B;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
5
Vermeidung von Deadlocks:
Protokolle des Laufzeitsystems:a. alle Ressourcen werden auf einmal angefordert und gleichzeitig
gewährt(falls nicht alle Ressourcen verfügbar, kommt der Prozess in die Warteschlange)
b. die Ressourcen unterliegen einer linearen Ordnung, und bei der Bedarfsanmeldung wird diese Reihenfolge eingehalten
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
6
Aber wie steuert man Nebenläufigkeit?
• wird erst T1 ganz und dann T2 ganz ausgeführt, heisst diese Reihenfolge seriell
• Problem: welche Überlappung ist zulässig?• eine Reihenfolge heisst serialisierbar, wenn sie einer seriellen
Reihenfolge äquivalent ist• wie erkennt man Serialisierbarkeit?
T 1:
A:=A-10;
Read B;
Write B;Read A;
Write A; B:=B+10;
T 2:
B:=B-20;
Read C;
Write C;Read B;
Write B; C:=C+20;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
7
Beispiele
A 3x
T 1
A:=A-10
Read B
Write B
Read A
Write A
B:=B+10
T 2T 1T 2T 1T 2
B:=B-20
Read C
Write C
Read B
Write B
C:=C+20
A:=A-10
Read B
Write B
Read A
Write A
B:=B+10
B:=B-20
Read C
Write C
Read B
Write B
C:=C+20
A:=A-10
Lock A
Lock BUnlock A
B:=B-20Lock BUnlock B
B:=B+10 Lock C
Unlock BC:=C+20Unlock C
seriell serialisierbar nicht serialisierbar
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
8
Prüfung auf Serialisierbarkeit (a posteriori)
Algorithmus:Input: Eine überlappte Ausführung von Transformationen
T1,...,Tk
Output: Prüfung der Serialisierbarkeit.
Methode: Konstruiere einen Graphen mit den Knoten a1, a2, ... an
wobei jedes ai eine der beiden folgenden Formen hat: Tj: Lock Am oder Tj: Unlock Am
Wenn ein Lock Am auf einen Unlock Am folgt, werden diese beiden Knoten miteinander verbunden.
Die Reihenfolge ist serialisierbar, wenn der entstandene
Graph azyklisch ist; eine serielle Reihenfolge kann durch eine
geeignete Durchlaufstrategie ermittelt werden.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
Serialisierbar
9
T1
Unlock B
Lock B
Unlock A
Lock A...
.
.
.
.
.
.
Lock B
Unlock B
Lock A
T2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
10
Serialisierbarkeit a priori durch Zwei-Phasen-Protokoll
Zwei-Phasen-Protokoll
• in jeder Transaktion T gehen alle Sperrungen (Locks) den Freigaben (Unlocks) voraus
Vorteil: leicht zu überprüfenNachteil: ev. großräumige Sperrung
T2: Lock B; Unlock B;Unlock A;Lock A;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
11
Beispiel
T2: Lock B; Unlock B;Unlock A;Lock A;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
12
Verfeinerungen
• differenziere zwischen Read und Write-Locks• berücksichtige hierarchische Strukturen
– Aggregierte Objekte– B-Bäume
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
13
Baum-Protokoll 1 (knoten-orientiert)
A
B C
GF
ED
• Lock eines Knotens setzt Verfügung (Lock) über den Vaterknoten voraus– Ausnahme: 1. Lock einer
Transaktion• Kein Knoten wird durch die
gleiche Transaktion mehrmals gesperrt
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
14
Baum-Protokoll 1 (knoten-orientiert)
A 36x T2T1 T3
(1)(2)
(4)(3)
(9)(8)
(5)
(10)
(6)(7)
(12)(11)
(14)(13)
(16)(15)
(18)(17)
Lock DLock B
Unlock B
Lock A
Lock C
Lock E
Lock B
Unlock DLock F
Lock E
Unlock A
Unlock C
Unlock B
Unlock E
Lock G
Unlock F
Unlock G
Unlock E
A
B C
GF
ED
A
B
D
BB C
ED
F
A
G
C
EE
F
B
G
E
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
15
• Anwendungsbeispiel: B-Baum• 3 Modi:
– Warn, Lock und Unlock • Warnungen sind untereinander nicht exklusiv
– mehrere Prozesse können den gleichen Knoten warnen– ein gewarnter Knoten kann von einem anderen nicht mit Lock
gesperrt werden• Die Transaktion T beginnt mit der Warnung der Wurzel des
Baumes• Sperrung eines Knotens setzt Warnung des Vaterknotens
voraus• ein Knoten kann nur entsperrt oder entwarnt werden, nachdem
alle Sperrungen / Warnungen auf Kinder entfernt wurden• 2-Phasen-Protokoll: alle Warnungen und Sperrungen gehen
allen Freigaben voraus
Warn-Protokoll (Teilbaum-orientiert)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
16
A
B C
GFED
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
17
A 36x
Warn-Protokoll (Beispiel)
T2T1
Warn B
Warn A
Lock DLock C
Unlock D
Warn C
T3
(1)(2)
(4)(3)
(9)(8)
(5)
(10)
(6)(7)
(12)(11)
(14)(13)
(16)(15)
(18)(17)
Unlock B
Unlock A
Unlock A
Unlock C
Lock B
Unlock B
Unlock C
Lock F
Warn AWarn A
Unlock F
Unlock A
A
B C
GFED
C
D
C
D
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
17
A 36x
Warn-Protokoll (Beispiel)
T2T1
Warn B
Warn A
Lock DLock C
Unlock D
Warn C
T3
(1)(2)
(4)(3)
(9)(8)
(5)
(10)
(6)(7)
(12)(11)
(14)(13)
(16)(15)
(18)(17)
Unlock B
Unlock A
Unlock A
Unlock C
Lock B
Unlock B
Unlock C
Lock F
Warn AWarn A
Unlock F
Unlock A
A
B C
GFED
C
D
C
D
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
17
A 36x
Warn-Protokoll (Beispiel)
T2T1
Warn B
Warn A
Lock DLock C
Unlock D
Warn C
T3
(1)(2)
(4)(3)
(9)(8)
(5)
(10)
(6)(7)
(12)(11)
(14)(13)
(16)(15)
(18)(17)
Unlock B
Unlock A
Unlock A
Unlock C
Lock B
Unlock B
Unlock C
Lock F
Warn AWarn A
Unlock F
Unlock A
A
B C
GFED
C
D
C
D
B
F
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
17
A 36x
Warn-Protokoll (Beispiel)
T2T1
Warn B
Warn A
Lock DLock C
Unlock D
Warn C
T3
(1)(2)
(4)(3)
(9)(8)
(5)
(10)
(6)(7)
(12)(11)
(14)(13)
(16)(15)
(18)(17)
Unlock B
Unlock A
Unlock A
Unlock C
Lock B
Unlock B
Unlock C
Lock F
Warn AWarn A
Unlock F
Unlock A
A
B C
GFED
C
D
C
D
B
F
B
F
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
17
A 36x
Warn-Protokoll (Beispiel)
T2T1
Warn B
Warn A
Lock DLock C
Unlock D
Warn C
T3
(1)(2)
(4)(3)
(9)(8)
(5)
(10)
(6)(7)
(12)(11)
(14)(13)
(16)(15)
(18)(17)
Unlock B
Unlock A
Unlock A
Unlock C
Lock B
Unlock B
Unlock C
Lock F
Warn AWarn A
Unlock F
Unlock A
A
B C
GFED
C
D
C
D
B
F
B
F
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Geoinformation3
17
A 36x
Warn-Protokoll (Beispiel)
T2T1
Warn B
Warn A
Lock DLock C
Unlock D
Warn C
T3
(1)(2)
(4)(3)
(9)(8)
(5)
(10)
(6)(7)
(12)(11)
(14)(13)
(16)(15)
(18)(17)
Unlock B
Unlock A
Unlock A
Unlock C
Lock B
Unlock B
Unlock C
Lock F
Warn AWarn A
Unlock F
Unlock A
A
B C
GFED
C
D
C
D
B
F
B
F