Semester Ganjil 2014 Fak. Teknik Jurusan Teknik Informatika Universitas Pasundan Caca E. Supriana, S.Si.,MT.
[email protected]
Two‐Phase Locking Techniques y Locking adalah sebuah operasi yang mengamankan (a)
izin untuk Baca (Read) atau (b) izin untuk Tulis (Write) item data untuk transaksi Contoh: Lock (X) (Write) item data untuk transaksi. Contoh: Lock (X). Item data X terkunci dalam nama transaksi yang meminta. y Unlocking adalah sebuah operasi yang menghilangkan hak akses ini dari item data. Contoh: Unlock (X). Item data X dibuat tersedia untuk semua transaksi lainnya. y Lock dan Unlock adalah operasi Atomik. adalah operasi Atomik 2
y Dua mode kunci (a) shared (read) dan (b) eksklusif
(write). y Mode Shared: berbagi lock (X). Lebih dari satu M d Sh d b b i l k (X) L bih d i transaksi dapat menerapkan berbagi kunci pada X untuk membaca nilainya tetapi tidak ada menulis kunci dapat diterapkan pada X oleh transaksi lainnya. y Mode Eksklusif: Menulis lock (X). Hanya satu y menulis kunci pada X dapat ada pada setiap waktu dan tidak ada kunci bersama dapat diterapkan oleh transaksi lain pada X. transaksi lain pada X 3
y Lock Manager: Mengelola kunci pada item data. y Lock Table: Kunci manajer menggunakannya untuk
menyimpan mengidentifikasi transaksi mengunci i id ifik i k i i item data, data barang, modus kunci dan pointer ke item data berikutnya terkunci Salah satu cara item data berikutnya terkunci. Salah satu cara sederhana untuk menerapkan tabel kunci adalah melalui linked list.
Transaction ID Data item id lock mode Ptr to next data item T1 X1 Read Next
4
Database membutuhkan semua transaksi harus dibentuk dengan baik. Sebuah transaksi yang baik akan terbentuk jika: y Transaksi harus mengunci item data sebelum membaca atau menulis. membaca atau menulis y Transaksi tidak harus mengunci item data yang sudah terkunci dan tidak harus mencoba untuk membuka item data yang bebas (unlocked).
5
Lock operation B: if LOCK (X) = 0 (*item is unlocked*) then h LOCK OC (X) ( ) ← 1 (*lock (*l k the h item*) i *) else begin wait (until lock (X) = 0) and the lock manager wakes up the transaction); goto B end;
6
Unlock operation LOCK (X) ← 0 (*unlock the item*) if any transactions i are waiting i i then h wake up one of the waiting the transactions;
7
Read operation B: if LOCK (X) = “unlocked” then begin LOCK (X) ← “read‐locked”; no_of_reads f d (X) ← 1; end else if LOCK ((X)) ← “read‐locked” then no_of_reads (X) ← no_of_reads (X) +1 else begin wait (until LOCK (X) = “unlocked” and the h lock l k manager wakes k up the h transaction); i ) go to B end; 8
Write lock operation B: if LOCK (X) = “unlocked” then begin LOCK (X) ← “write‐locked”; no of reads (X) ← 1; no_of_reads end else if LOCK (X) ← “write‐locked” then no_of_reads (X) ← no_of_reads (X) +1 else begin wait (until LOCK (X) = “unlocked” and th lock the l k manager wakes k up the th transaction); t ti ) go to B end;; 9
Unlock operation if LOCK (X) write locked then if LOCK (X) = “write‐locked” then begin LOCK (X) ← “unlocked”; wakes up one of the transactions, if any end d else if LOCK (X) ← “read‐locked” then begin g no_of_reads (X) ← no_of_reads (X) ‐1 if no_of_reads (X) = 0 then b i begin LOCK (X) = “unlocked”; wake up p one off the transactions, iff anyy end end;
10
Lock conversion Lock upgrade: existing read lock to write lock if Ti has a read‐lock (X) and Tj has no read‐lock (X) (i ≠ j) then convertt read‐lock d l k (X) to t write‐lock it l k (X) else force Ti to wait until Tj unlocks X
Lock downgrade: existing write lock to read lock Ti has a write‐lock (X) (*no transaction can have any lock on X*) convertt write‐lock it l k (X) to t read‐lock d l k (X)
11
Algorithm y Dua Tahap: (a) Locking (growing) (b) Unlocking
(shrinking). y Tahap Locking (growing) : Sebuah transaksi berlaku kunci (membaca atau menulis) pada item data yang diinginkan satu per satu. y Tahap Unlocking (shrinking): Sebuah transaksi membuka item datanya dikunci satu per satu. y Persyaratan: Untuk transaksi kedua fase harus saling eksklusif, yaitu selama fase mengunci membuka fase tidak harus mulai dan selama unlocking fase fase penguncian tidak harus dimulai. i tid k h di l i 12
13
Algoritma untuk Two‐Phase Locking Techniques Algoritma untuk Two Phase Locking Techniques T1
T2
Result
read_lock (Y); read lock (Y);
read_lock (X); read lock (X);
Initial values: Y=30; X=20
read_item (Y);
read_item (X);
Result of serial execution
unlock (Y);
unlock (X);
T1 followed by T2
write_lock (X);
Write_lock (Y);
X=50, Y=80. 5
read_item (X);
read_item (Y);
Result of serial execution
X:=X+Y;
Y:=X+Y;
T2 followed by T1
write_item (X);
write_item (Y);
X=70, Y=50
unlock (X);
unlock (Y); 14
T1
T2
read_lock (Y); read_item (Y); unlock (Y);
Result X=50; Y=50 Nonserializable because it. violated two‐phase policy.
read_lock (X); read lock (X); read_item (X); unlock (X); write_lock (Y); read_item (Y); d ( ) Y:=X+Y; write_item (Y); unlock (Y);
Time
write_lock (X); read_item (X); X:=X+Y; write_item (X); it it (X) unlock (X); 15
T’1
T’2
read_lock (Y); read item (Y); read_item (Y); write_lock (X); unlock (Y); read_item (X); X X Y X:=X+Y; write_item (X); unlock (X);
read_lock (X); read item (X); read_item (X); Write_lock (Y); unlock (X); read_item (Y); Y X Y Y:=X+Y; write_item (Y); unlock (Y);
T1 and T2 follow two‐phase policy but they are subject to deadlock, which must be dealt with.
16
y Kebijakan dua tahap menghasilkan dua algoritma
penguncian (a) Dasar dan (b) Konservatif. y Konservatif: Mencegah kebuntuan dengan mengunci semua item data yang diinginkan sebelum transaksi dimulai eksekusi. y Dasar: Transaksi mengunci item data secara bertahap. Hal Dasar: Transaksi mengunci item data secara bertahap Hal ini dapat menyebabkan kebuntuan yang harus ditangani. y Ketat (Strict): Sebuah versi yang lebih ketat dari algoritma d dasar di mana unlocking dilakukan setelah transaksi di l ki dil k k l h k i berakhir (melakukan atau dibatalkan dan roll‐back). Ini adalah yang paling umum digunakan pada algoritma penguncian dua fase. i d f 17
Deadlock & Starvation Deadlock T’1
T’2
read_lock (Y); d l k( ) read_item (Y);
T1 and T2 did follow two‐phase d d d f ll h policy but they are deadlock read_lock (X); read item (Y); read_item (Y);
write_lock (X); (waits for X)
write_lock (Y); (waits for Y)
Deadlock (T’1 and T’2)
18
Starvation y Starvation terjadi ketika transaksi tertentu secara
konsisten menunggu atau restart dan tidak pernah mendapat kesempatan untuk melangkah lebih jauh. Dalam resolusi kebuntuan adalah mungkin bahwa transaksi yang sama dapat secara konsisten terpilih sebagai korban dan roll back sebagai korban dan roll‐back. y Keterbatasan ini melekat dalam semua mekanisme p j penjadwalan berbasis prioritas. Dalam skema Wound‐ p Wait transaksi yang lebih muda mungkin selalu dibatalkan dengan transaksi lebih tua yang telah lama berjalan yang dapat menciptakan starvation. 19
Timestamp y Sebuah variabel monoton yang meningkat (integer)
yang menunjukkan usia operasi atau transaksi. Sebuah nilai timestamp yang lebih besar menunjukkan peristiwa atau operasi yang lebih baru. y Algoritma berbasis Timestamp menggunakan timestamp untuk serialisasi pelaksanaan transaksi konkuren.
20
Timestamp based concurrency control algorithm Timestamp based concurrency control algorithm Basic Timestamp Ordering 1. Transaction T issues a write_item(X) write item(X) operation:
a. If read_TS(X) > TS(T) or if write_TS(X) > TS(T), then an younger transaction has already read the data item so abort and roll‐back roll back T and reject the operation. b. If the condition in part (a) does not exist, then execute write_item(X) write item(X) of T and set write_TS(X) write TS(X) to TS(T). 2. Transaction T issues a read_item(X) operation: a. If write_TS(X) i TS(X) > TS(T), TS(T) then h an younger transaction has already written to the data item so abort and roll‐back T and reject the operation. b If write_TS(X) b. i TS(X) ≤ TS(T), TS(T) then h execute read_item(X) d i (X) of T and set read_TS(X) to the larger of TS(T) and the current read_TS(X).
21
Strict Timestamp Ordering
1. Transaction T issues a write_item(X) operation: a If TS(T) > read_TS(X), a. read TS(X) then delay T until the transaction T’ that wrote or read X has terminated (committed or aborted). 2 Transaction T issues a read_item(X) 2. read item(X) operation: a. If TS(T) > write_TS(X), then delay T until the transaction T’ that wrote or read X has terminated (committed or aborted). aborted)
22
Thomas’s Write Rule
1. 2.
3.
If read_TS(X) > TS(T) then abort and roll‐back T and reject j the operation. p If write_TS(X) > TS(T), then just ignore the write operation and continue execution. This is because the most recent writes counts in case of two consecutive writes. If the conditions given in 1 and 2 above do not occur, then execute write_item(X) ( ) of T and set write_TS(X) ( ) to TS(T).
23
