Aufgabe 10.1 (35 Punkte)

Sei folgende Historie von fünf verzahnt ausgeführten Transaktionen auf drei Daten (x, y und z) gegeben:

	1.	2.	3.	4.	5.	6.	7.	8.	9.	10.	11.	12.	13.
$T_1$			$r(x)$			$w(z)$				$w(x)$
$T_2$	$r(x)$						$w(x)$		$w(z)$			$w(y)$
$T_3$								$w(x)$			$w(z)$		$r(y)$
$T_4$		$r(x)$		$w(x)$
$T_5$					$r(y)$

Die Historie werde mit Hilfe eines Schedulers verarbeitet, welcher auf dem Zwei-Phasen-Sperrprotokoll basiert. Dabei soll das strikte Zwei-Phasen-Sperrprotokoll zum Einsatz kommen, bei dem alle gesetzten Sperren erst am Ende der Transaktion, also nach der letzten Operation, freigegeben werden.

Welche Transaktionen müssen während der Verarbeitung warten? Geben Sie hierbei die wartende Transaktion, die blockierte Ressource und die blockierende Transaktion an.

Hinweis: Wenn eine Transaktion ein Datum erst liest und später schreibt, fordert der Scheduler bereits beim Lesezugriff eine Schreibsperre für das Datum an.

Musterlösung vom 06.07.2008:

Die Historie und die Zugriffe der Transaktionen auf die Ressourcen des Zwei-Phasen-Sperrprotokolls:

Transaktionen					Ressourcen
$T_1$	$T_2$	$T_3$	$T_4$	$T_5$	x	y	z
	bot
	$wl(x)$
	$r(x)$				$T_2$: write
			bot
			$wl(x)$		$T_2$: write
					$T_4$: wait
bot
$wl(x)$					$T_2$: write
					$T_4$: wait
					$T_1$: wait
				bot
				$rl(y)$
				$r(y)$		$T_5$: read
				eot
				$ul(y)$		free
				commit
	$w(x)$	bot
		$wl(x)$			$T_2$: write
					$T_4$: wait
					$T_1$: wait
					$T_3$: wait
	$wl(z)$						$T_2$: write
	$w(z)$
	$wl(y)$					$T_2$: write
	$w(y)$
	eot
	$ul(x)$				$T_4$: wait	free	free
	$ul(z)$				$T_1$: wait
	$ul(y)$				$T_3$: wait
	commit				$T_4$: write
					$T_1$: wait
					$T_3$: wait
			$r(x)$
			$w(x)$
			eot
			$ul(x)$		$T_1$: wait
					$T_3$: wait
			commit		$T_1$: write
					$T_3$: wait
$r(x)$
$wl(z)$							$T_1$: write
$w(z)$
$w(x)$
eot
$ul(x)$					$T_3$: wait		free
$ul(z)$
commit					$T_3$: write
		$w(x)$
		$wl(z)$					$T_3$: write
		$w(z)$
		$rl(y)$				$T_3$: read
		$r(y)$
		eot
		$ul(x)$			free	free	free
		$ul(z)$
		$ul(y)$
		commit