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