Startseite » Informatik » Referate » Detailseite
 

  • Information Engineering

    1 PROLOG Das Unternehmen der Zukunft wird zu einem großem Teil mit Hilfe von Computern geführt werden. PCs und Workstations werden die Nervenenden eines unternehmensweiten Netzwerkes...Referat Information Engineering

    1502 Worte in "deutsch"  als "hilfreich"  bewertet

  • Entwicklung der Programmiersprachen

    Entwicklung der Programmiersprachen Um den Überblick über die Programmiersprachen zu vereinfachen hat man sie in Generationen unterteilt. Jede der Generationen weist für sie...Referate Entwicklung der Programmiersprachen

    776 Worte in "deutsch"  als "hilfreich"  bewertet

  • MPEG Layer 3 (MP3)

    MPEG Layer 3 MPEG Layer 3 ist ein Neues bereits sehr beliebtes Audio Format für den PC / Macintosh, welches sich besonders im Internet an großer Beliebtheit erfreut. Die...MPEG Layer 3 (MP3) Referat

    484 Worte in "deutsch"  als "hilfreich"  bewertet

Concurrency-Probleme






















1 Concurrency - Probleme


1.1 Locking zur Lösung der Probleme


Die Grundidee des Locking ist es, alle Objekte, welche von einer Transaktion benötigt werden, mit einer entsprechenden Marke (diese wird als Lock bzw. Sperre bezeichnet) zu versehen, welche anderen Transaktionen anzeigt, dass dieses Objekt derzeit nicht verfügbar ist.


2 Arten von Locks werden unterschieden:

X - LOCK (EXCLUSIVE LOCKS): Wird durch eine Transaktion A ein Datensatz verändert, so wird dieser für alle anderen Transaktionen gesperrt, bis die Transaktion den Datensatz wieder freigibt. Diese Sperre verhindert, dass andere Transaktionen den Datensatz lesen oder verändern.

S - LOCK: (SHARE LOCKS): Wird durch eine Transaktion ein Datensatz abgefragt, so wird dieser Datensatz für X - Locks gesperrt d.h. dass andere Transaktionen den Datensatz nicht ändern dürfen, Lesezugriffe sind jedoch ohne weiteres erlaubt.


Aus diesen zwei Aussagen ergibt sich folgende Wertetabelle

gefordertes Lock
 gesetztes Lock von Transaktion A
von Transaktion B
 X
 S
 kein
X
 wait B
 wait B
 OK
S
 wait B
 OK
 OK


Bsp.: Angenommen Transaktion A hat einen Datensatz R für ein Änderung (X - Lock) gesperrt, so wird eine Anfrage von Transaktion B für einen Lock auf denselben Datensatz (egal welchen Typs) diese in einen Wartezustand führen.


Bsp.: Hat aber die Transaktion A ein S - Lock auf den Datensatz R, so muss man bei einer Anfrage eines Locks von Transaktion B auf R zwei Fälle unterscheiden:

    bei Anfrage von Transaktion B für ein X - Lock auf R gelangt diese in einen Wartezustand bis der Datensatz wieder freigegeben wird.

    eine Anfrage von Transaktion B für ein S - Lock auf R wird erlaubt.

Das lost update Problem


Das Problem besteht darin, dass "ältere" Änderungen durch zeitlich verschobene Zugriffe verloren gehen können:

Transaktion A
Zeit
Transaktion B
-
|
-
lese Satz R
t1
-

|

-
t2
lese Satz R

|

ändere Satz R
t3
-

|

-
t4
ändere Satz R
-
↓
-



Lösung mittels Locking:

Transaktion A
Zeit
Transaktion B
-
|
-
lese Satz R zum Ändern
(meldet X - Lock auf Satz R an)
t1
|
-

|

-
t2
|
lese Satz R zum Ändern
(möchte X - Lock auf Satz R)

|

ändere Satz R
t3
wartet auf Freigabe von Satz R durch A

|

Synchpoint; Ende Transaktion
(gibt Satz R wieder frei)
t4
|
wartet auf Freigabe von Satz R durch A

|

-
t5
|
lese Satz R zum Ändern
(meldet X - Lock auf Satz R an)
-
↓
-


Mit dem Einlesen des Satzes R zum Zeitpunkt t1 wird dieser mit einem X - Lock gesperrt. Dadurch werden alle weiteren Zugriffe (z.B. Leseanforderung zum Zeitpunkt t2) gesperrt. Erst nach Freigabe der Sperren (Zeitpunkt t4) kann der Datensatz weiter verwendet werden.

Verwendet man allerdings an Stelle der X - Locks in obigem Beispiel S - Locks so treten neue Probleme auf:


Transaktion A
Zeit
Transaktion B
-
|
-
lese Satz R
(meldet S - Lock auf Satz R an)
t1
|
-

|

-
t2
|
lese Satz R
(meldet S - Lock auf Satz R an)

|

ändere Satz R
(möchte X - Lock auf Satz R)
t3
|
-

|

wartet auf Freigabe von Satz R durch B
t4
|
ändere Satz R
(möchte X - Lock auf Satz R)

|

wartet auf Freigabe von Satz R durch B
t5
wartet auf Freigabe von Satz R durch A

|

wartet auf Freigabe von Satz R durch B
↓
wartet auf Freigabe von Satz R durch A


Da Transaktion A beim Lesen seine Änderungsabsicht noch nicht bekanntgibt, wird Transaktion B zum Zeitpunkt t2 der Lesezugriff nicht verwehrt. Die in der Folge angeforderten X - Locks versetzen beide Transaktionen in den Wartezustand, da das von der gegnerischen Transaktion gesetzte S - Lock kein X - Lock zulässt. Diese Situation bezeichnet man als Deadlock. Die Lösung dieses neuen Problems wird später erklärt.


1.3 Das uncommited dependency Problem


Dieses Problem basiert auf der Verwendung von unbestätigten, veränderten Daten und diese müssen Änderungen zurückgenommen werden.


Transaktion A
Zeit
Transaktion B
-
|
-
-
t1
ändere Satz R

|

lese Satz R
t2
-

|

-
t3
Rollback
-
↓
-
Lösung mittels Locking:


Transaktion A
Zeit
Transaktion B
-
|
-
-
t1
|
ändere Satz R
(meldet X - Lock auf Satz an)

|

lese Satz R
(möchte S - Lock auf Satz R)
t2
|
-

|

wartet auf Freigabe von Satz R durch B
t3
|
Rollback; Synchpoint; Ende Transaktion
(gibt Satz R wieder frei)

|

lese Satz R
(meldet S - Lock auf Satz R an)
t4
|
-
-
↓
-


Dadurch, dass die Transaktion A auf die Freigabe des von der Transaktion B gesperrten Datensatzes R wartet, kann sie zu keinem Zeitpunkt (sowohl bei einem Lesen als auch beim Verändern von Datensätzen) mit falschen Daten rechnen.


1.4 Das inconsistent analysis Problem


Bei diesem Problem arbeitet ein Programm mit Daten, die aus einer kurzfristig inkonsistenten Datenbank kommen.

Transaktion A
Zeit
Transaktion B
-
|
-
lies Konto1
Kontostand = 40
t1
|
-

|

-
t2
|
ändere Konto2
Kontostand = 50 + 30 = 80

|

-
t3
|
ändere Konto1
Kontostand = 40 - 30 = 10

|

lies Konto2
Kontostand = 80
t4
|
-
-
↓
-
Lösungsversuch mittels Locking:

Transaktion A
Zeit
Transaktion B
-
|
-
lies Konto1
(meldet S - Lock auf Konto1 an)
t1
|
-

|

-
t2
|
ändere Konto2
(meldet X - Lock auf Konto2 an)

|

-
t3
|
ändere Konto1
(meldet X - Lock auf Konto1 an)

|

lies Konto2
(möchte S - Lock auf Konto2)
t4
|
wartet auf Freigabe von Konto1 durch A

|

wartet auf Freigabe von Konto2 durch B
t5
wartet auf Freigabe von Konto1 durch A
-
↓
-

Auch hier tritt wieder das Problem des Deadlocks auf.

1.5 Problem Deadlock


An den zwei vorherigen Beispielen kann man ersehen, dass das Locking nicht alle Probleme löst. Durch das gegenseitige Locking, warten zwei Transaktionen auf die gegenseitige Freigabe eines Datensatzes, was sich dadurch bemerkbar macht, dass keine Transaktion weiter arbeitet.
Dieses Problem kann nur dann gelöst werden, wenn eine der beiden Transaktionen zurückgenommen wird. Dadurch kann die andere Transaktion ihre Arbeit beenden, worauf die abgebrochene Transaktion neu gestartet wird.

1.6 Techniken zur Vermeidung/Lösung von Deadlocks

Erforderliche Eigenschaften von Transaktionen:

    Atomicity: Eine Transaktion ist eine elementarer Prozeß. Er wird entweder vollständig oder gar nicht durchgeführt.

    Konsistenzkriterium: Eine korrekte Durchführung einer Transaktion muss die Datenbank wieder in einen konsistenten Zustand versetzt

    Dauerhaftigkeit: Wurden von einer Transaktion Änderungen durchgeführt und bestätigt, so gehen diese auch durch einen späteren Fehler nicht mehr verloren.

    Isolation: Alle Änderungen während einer Transaktion dürfen für andere Transaktionen erst nach der Bestätigung sichtbar werden.

    Serialisierbarkeit: Man spricht von serialisierbaren Transaktionen, wenn ein Datenbankzustand, der durch parallel arbeitende Transaktionen erreicht wurde, auch durch die serielle Abarbeitung der gleichen Transaktionen erreicht würde.
Es wird vorausgesetzt, dass die einzelnen Transaktionen voneinander unabhängig sind. Eine Abhängigkeit wäre gegeben, wenn z.B. eine Transaktion A vor einer Transaktion B unbedingt laufen müsste. Damit ist zwar keine beliebige Hintereinanderausführung mehr möglich, aber es ist ein bestimmter, zeitlicher Ablauf gegeben.

Punkt 1 und 2 sind in der Definition der Transaktion enthalten. Punkt 3 wird durch Recovery - Techniken im Falle eines Fehlers gewährleistet.

Zur Einhalten der im Punkt 4 und 5 geforderten Serialisierbarkeit wird das Two - Phase - Locking Protokoll eingesetzt

1.6.1 Two Phase Locking


Wenn eine Transaktion einen gesperrten Datensatz wieder frei gibt, aber ihn danach noch einmal benötigt und ihn somit wieder sperren muss, muss erwartet werden das die Daten schon von einer anderen Transaktion geändert wurden. Um die daraus resultierenden Probleme (uncommitted dependency) zu vermeiden, werden folgende Forderungen aufgestellt:

    Vor jeder Bearbeitung eines Datensatzes wird dieser gesperrt

    Dieser Datensatz wird erst wieder freigegeben, wenn er für die restliche Transaktion nicht mehr benötigt wird.

Eine Transaktion, die beiden Regeln entspricht, arbeitet nach dem "two Phase Locking Protocol (2PL)", und erfüllt die Forderung der Serialisierbarkeit.

1.6.2 Zeitmarkenverfahren (Timestamp technique)


Jede Transaktion erhält bei ihrem Start einen Zeitstempel. Die Abarbeitung erfolgt streng noch dem Prinzip First in - First out (FIFO), d.h. streng nach der Startreihenfolge. Tritt ein Konflikt auf, so wird jene Transaktion neu gestartet die den Konflikt auslöste. Ein Konflikt entsteht z.B. wenn eine "ältere" Transaktion eine Leseanforderung für einen bestimmten Datensatz absetzt, der durch eine "jüngere" verändert werden soll. Dadurch erhält der Benutzer immer die aktuellen und geänderten Daten. Dieses Verfahren dient unter anderem zur Vermeidung von Deadlocks.

1.6.3 Transaktion Retry

Nach Erkennung eines Deadlocks muss eine der Transaktionen abgebrochen und zu einem späteren Zeitpunkt neu gestartet werden. Für die Entscheidung welche der Transaktionen abzubrechen ist gibt es verschiedene Verfahren:

    Wait - Die Protokoll Wound - Wait Protokoll

Bei beiden Verfahren wird jeweils die "jüngere" Transaktion zurückgenommen und zu einem späteren Zeitpunkt ausgeführt. Dazu ist erforderlich, dass jede Transaktion einen eindeutigen Zeitstempel, am Beginn erhält.

Wenn die Transaktion A einen von der Transaktion B bereits gesperrten Datensatz sperren will, passiert folgendes:

    Wait - Die: falls A älter ist als B wartet A, sonst wird A zurückgenommen Wound - Wait: falls A jünger ist als B wartet A, sonst wird B zurückgenommen


Es ergibt sich folgende Wertetabelle:

B hat Satz gesperrt, A fordert Satz an

 Wait - Die
 Wound - Wait

A
 B
 A
 B
A älter als B
 wartet
 -
 -
 zurückgenommen
B älter als A
 zurückgenommen
 -
 wartet
 -
- : arbeitet


Bei diesem System ist sichergestellt, dass kein Deadlock entstehen kann, da jede Transaktion in einer endlichen Zeit und nach endlich vielen Wiederholungen ausgeführt wird. Das Schlimmste was passieren kann, ist dass der Rechner zu langsam ist und jede neu ankommende Transaktion länger abläuft als ihr Vorgänger.

2 Zwei - Phasen - Commit (Two Phase Commit)


Das 2 - Phasen - Commit wird eingesetzt, wenn mehrere Systeme (z.B.: hierarchisches und relationales DB - System) gemeinsam synchronisiert werden müssen. Hier tritt das Problem auf, dass zwischen dem Commit für System1 und dem Commit für System2 ein Fehler auftritt. Beim automatischen Recovery würde in diesem Fall System2 zurückgesetzt werden, die Daten für System1 bleiben bestätigt. Dadurch stimmen die beiden Systeme nicht mehr überein.



    System befindet sich in einem konsistenten Zustand

    Eine Applikation beginnt mit Änderungsanforderungen. Diese Änderungen werden an den Koordinator geschickt. Dieser leitet sie zeitverzögert an die jeweilige Datenbank.

    Applikation hat Änderungen abgeschlossen und setzt einen Synchpoint.

    Darauf leitet der Koordinator Phase 1 von Commit ein. Dazu schickt er eine entsprechende Anforderung an alle Datenbanksysteme.

    Die einzelnen Datenbanksysteme markieren die Commit - Anforderung in ihrem Logfile und bestätigen anschließend dem Koordinator das Commit.

    Nach Eintreffen aller Commit - Bestätigungen protokolliert der Koordinator dies in seinem Logfile und leitet anschließend Commit Phase 2 ein.

    Auch Phase 2 muss von den einzelnen Datenbanksystemen bestätigt werden.

    Nach Erhalt aller Bestätigungen und einem entsprechenden Protokolleintrag meldet der Koordinator einen neuen konsistenten Zustand der Datenbank.


Treten bis zum Zeitpunkt des ersten Logeintrags des Koordinators Fehler auf oder meldet ein Datenbanksystem einen nicht erfolgreichen Abschluß, so fordert der Koordinator alle Datenbanksysteme zu einem Rollback auf. Tritt hingegen nach diesem Zeitpunkt ein Fehler auf, so werden automatisch alle noch ausständigen Phase 2 Commits durchgeführt.

3 Fragen


Wie lauten die zwei Locks, und welche gleichzeitigen Transaktionen sind erlaubt?

X - LOCK (EXCLUSIVE LOCKS): Wird durch eine Transaktion A ein Datensatz verändert, so wird dieser für alle anderen Transaktionen gesperrt, bis die Transaktion den Datensatz wieder freigibt. Diese Sperre verhindert, dass andere Transaktionen den Datensatz lesen oder verändern.

S - LOCK: (SHARE LOCKS): Wird durch eine Transaktion ein Datensatz abgefragt, so wird dieser Datensatz für X - Locks gesperrt d.h. dass andere Transaktionen den Datensatz nicht ändern dürfen, Lesezugriffe sind jedoch ohne weiteres erlaubt.


Was ist ein Deadlock, und wie kann er gelöst werden?

Durch das gegenseitige Locking, warten zwei Transaktionen auf die gegenseitige Freigabe eines Datensatzes, was sich dadurch bemerkbar macht, dass keine Transaktion weiter arbeitet.
Dieses Problem kann nur dann gelöst werden, wenn eine der beiden Transaktionen zurückgenommen wird. Dadurch kann die andere Transaktion ihre Arbeit beenden, worauf die abgebrochene Transaktion neu gestartet wird.

1 Concurrency - Probleme

1.1 Locking zur Lösung der Probleme


Zwei Arten von Locks:
    X - Lock (Exclusive Lock) S - Lock (Share Lock)


Wertetabelle:
gefordertes Lock
 gesetztes Lock von Transaktion A
von Transaktion B
 X
 S
 kein
X
 wait B
 wait B
 OK
S
 wait B
 OK
 OK

1.2 Das lost update Problem


Problem:

Transaktion A
Zeit
Transaktion B
-
|
-
lese Satz R
t1
-

|

-
t2
lese Satz R

|

ändere Satz R
t3
-

|

-
t4
ändere Satz R
-
↓
-


Lösung mittels Locking:

Transaktion A
Zeit
Transaktion B
-
|
-
lese Satz R zum Ändern
(meldet X - Lock auf Satz R an)
t1
|
-

|

-
t2
|
lese Satz R zum Ändern
(möchte X - Lock auf Satz R)

|

ändere Satz R
t3
wartet auf Freigabe von Satz R durch A

|

Synchpoint; Ende Transaktion
(gibt Satz R wieder frei)
t4
|
wartet auf Freigabe von Satz R durch A

|

-
t5
|
lese Satz R zum Ändern
(meldet X - Lock auf Satz R an)
-
↓
-
Zweiter Lösungsweg:

Transaktion A
Zeit
Transaktion B
-
|
-
lese Satz R
(meldet S - Lock auf Satz R an)
t1
|
-

|

-
t2
|
lese Satz R
(meldet S - Lock auf Satz R an)

|

ändere Satz R
(möchte X - Lock auf Satz R)
t3
|
-

|

wartet auf Freigabe von Satz R durch B
t4
|
ändere Satz R
(möchte X - Lock auf Satz R)

|

wartet auf Freigabe von Satz R durch B
t5
wartet auf Freigabe von Satz R durch A

|

wartet auf Freigabe von Satz R durch B
↓
wartet auf Freigabe von Satz R durch A
⇒ Deadlock

1.3 Das uncommited dependency Problem


Problem:

Transaktion A
Zeit
Transaktion B
-
|
-
-
t1
ändere Satz R

|

lese Satz R
t2
-

|

-
t3
Rollback
-
↓
-


Lösung mittels Locking:

Transaktion A
Zeit
Transaktion B
-
|
-
-
t1
|
ändere Satz R
(meldet X - Lock auf Satz an)

|

lese Satz R
(möchte S - Lock auf Satz R)
t2
|
-

|

wartet auf Freigabe von Satz R durch B
t3
|
Rollback; Synchpoint; Ende Transaktion
(gibt Satz R wieder frei)

|

lese Satz R
(meldet S - Lock auf Satz R an)
t4
|
-
-
↓
-

1.4 Das incosistent analysis Problem


Problem:

Transaktion A
Zeit
Transaktion B
-
|
-
lies Konto1; Kontostand = 40
t1
-

|

-
t2
ändere Konto2; Kontostand = 50 + 30 = 80

|

-
t3
ändere Konto1; Kontostand = 40 - 30 = 10

|

lies Konto2; Kontostand = 80
t4
-
-
↓
-


Lösungsversuch mittels Locking:

Transaktion A
Zeit
Transaktion B
-
|
-
lies Konto1
(meldet S - Lock auf Konto1 an)
t1
|
-

|

-
t2
|
ändere Konto2
(meldet X - Lock auf Konto2 an)

|

-
t3
|
ändere Konto1
(meldet X - Lock auf Konto1 an)

|

lies Konto2
(möchte S - Lock auf Konto2)
t4
|
wartet auf Freigabe von Konto1 durch A

|

wartet auf Freigabe von Konto2 durch B
t5
wartet auf Freigabe von Konto1 durch A
-
↓
-
⇒ Deadlock


1.5 Deadlock


1.6 Techniken zur Vermeidung/Lösung von Deadlocks


Erforderliche Eigenschaften von Transaktionen:

    Atomicity Konsistenzkriterium Dauerhaftigkeit Isolation Serialisierbarkeit


1.6.1 Two Phase Locking


1.6.2 Zeitmarkenverfahren


1.6.3 Transaktion Retry


Zwei Protokolle:
    Wait - Die Protokoll Wound - Wait Protokoll


Es ergibt sich folgende Wertetabelle:

B hat Satz gesperrt, A fordert Satz an

 Wait - Die
 Wound - Wait

A
 B
 A
 B
A älter als B
 wartet
 -
 -
 zurückgenommen
B älter als A
 zurückgenommen
 -
 wartet
 -
- : arbeitet

2 Zwei - Phasen - Commit


Anwendung wenn mehrere verschiedene Datenbanksysteme synchronisiert werden müssen.




2640 Worte in "deutsch"  als "hilfreich"  bewertet