distributed concurency control
TRANSCRIPT
LAPORAN MATA KULIAH
Sistem Basis Data Terdistribusi
”Distributed Concurency Control”
Oleh
Ari Dwi WahyuningsihFetri MardyaniSalmi HidayahTommi Fajerin
PROGRAM STUDI TEKNIK INFORMATIKA
FAKULTAS ILMU KOMPUTER
UNIVERSITAS SRIWIJAYA
2011
A. CONCURENCY
Konkurensi merupakan landasan unum perancangan sistem operasi. Proses-proses
disebut konkuren jika proses-proses berada pada saat yang sama. Pada proses-proses
konkuren yang berinteraks mempunyai beberapa masalah yang harus
diselesaikan:
1. Mutual Exclusion
2. Sinkronisasi
3. Deadlock
4. Startvation
Prinsip-prinsip Konkurensi meliputi hal-hal sbb:
Alokasi wkatu pemroses untuk proses-proses
Pemakaian bersama dan persaingan untuk mendapatkan sumber daya
Komunikasi antarproses
Sinkronisasi aktivitas banyak proses.
Konkurensi dapat muncul pada tiga konteks berbeda, antara lain:
Banyak aplikasi (multiple application)
Aplikasi terstruktur
Struktur sistem operasi
Kesulitan-kesulitan yang ditimbulkan konkurensi yaitu kecepatan eksekusi proses-proses
di sistem tidak dapat diprediksi.
Beragam kemungkinan yang terjadi tidak dapat diprediksi, seperti:
1. Kecepatan proses pada sistem tergantung pada beberapa hal, antara lain:
o Aktivitas proses-proses lain
o Cara sistem operasi menangani interupsi
o Kebijaksanaan penjadwalan yang dilakukan oleh sistem operasi.
2. Beberapa kesulitan yang dapat muncul, di antaranya adalah:
o Pemakaian bersama sumber daya globla
o Pengelolaan alokasi sumber daya agar optimal
o Pencarian kesalahan pemrograman.
3. Proses-proses konkuren mengharuskn beberapa hal yang harus ditangani, antara lain:
o Sistem operasi harus mengetahui proses-proses yang aktif
o Sistem operasi harus mengalokasikan dan mendealokasikan beragam sumber
daya untuk tiap proses aktif. Sumber daya yang harus dikelola, antara lain
waktu memproses, memori,berkas-berkas, dan perangkat I/O
o Sistem operasi harus memproteksi data dan sumber daya fisik masingmasing
proses dari gangguan proses-proses lain.
o Hasil-hasil proses harus independen terhadap kecepatan relatif prosesproses
lain dimana eksekusi dilakukan.
Mutual Exclusion
Mutual exclusion adalah jaminan hanya satu proses yang mengakses sumber daya
pada satu interval waktu tertentu. Sering terjadi pada peralatan pencetakan (printer).
Daemon printer adalah proses yang melakukan penjadwalan dan pengendalian
pencetakan berkas-berkas di printer. Ruang disk ini disebut direktori spooler. Direktori
spooler membagi disk menjadi sejumlah slot. Slot-slot diisi berkas yang akan dicetak.
Terdapat variabel in yang menunjuk slot bebas pada ruang disk yang akan dipakai untuk
menyimpan berkas yang ingin dijadwalkan untuk dicetak. Bagian program yang sedang
mengakses memory atau sumber daya yang dipakai bersama disebut critical section. Jika
proses pada critical section memblokir proses-proses lain dalam antrian, maka akan
terjadi startvation dan deadlock. Kesuksesan proses-proses konkurensi memerlukan
pendefinisian critical section dan memaksakan mutual exclusion di antara proses-proses
konkuren yang sedang berjalan. Pemaksaan mutual exclusion merupakan landasan
pemrosesan konkuren. Fasilitas atau kemampuan menyediakan dukungan mutual
exclusion harus memenuhi kriteria sbb:
Mutual exclusion harus dijamin, bahwa tidak ada proses lain, kecuali dirinya
sendiri. Di sini terjadi proses tunggal.
Proses yang berada di noncritical section, dilarang mem-blocked prosesproses
lain yang ingin masuk critical section. Hal ini bisa terjadi startvation.
Harus dijamin bhwa proses yang ingin masuk critical section tidak menunggu
selama waktu yang tak terhingga. Ini bisa mengakibatkan masalah deadlock dan
antrian proses bertambah panjang.
Ketika tidak ada proses pada critical section, maka proses yang ingin masuk
critical section harus ijinkan masuk tanpa waktu tunda.
Tidak ada asumsi mengenai kecepatan relatif proses atau jumlah yang ada.
Proses hanya tinggal pada critical section selama satu waktu yang berhingga
Beberapa metode yang diusulkan untuk menjamin Mutual Exclusion, antara lain:
Metode Variable Lock
Metode ini sederhana ketika proses masuk critical section lebih dahulu
memeriksa variable lock.
o Jika variable lock bernilai 0, proses men-set variable lockny menjadi 1
kemudian masuk ke dalam critical section.
o Jika variable lock bernilai 1, maka proses menunggu sampai nilai variable
lock nya menjadi 0.
Metode ini tidak menjamin proses tidak masuk critical section yang telah
dimasuki proses lain.
Metode bergantian secara ketat
Metode ini mengasumsikan dapat mengalir masuk critical section secara
bergantian terus-menerus. Metode ini melakukan refleksi terhadap variabel
yang berfungsi untuk memenuhi critical section.
Sinkronisasi
Sinkronisasi diperlukan untuk menghindari terjadinya ketidak-konsistenan data
akibat adanya akses data secara konkuren. Proses-proses disebut konkuren jika proses-
proses itu ada dan berjalan pada waktu yang sama, proses-proses konkuren ini bisa
bersifat independen atau bisa juga saling berinteraksi. Proses-proses konkuren yang
saling berinteraksi memerlukan sinkronisasi agar terkendali dan juga menghasilkan
output yang benar.
Starvation
kejadian deadlock yang berlangsung secara terus-menerus dan tiada akhir dapat
menyebabkan terjadinya starvation. Akan tetapi, deadlock bukanlah satu-satunya
penyebab terjadinya starvation. Lalu lintas yang didominasi oleh kendaraan kendaraan
dari satu arah pun dapat menyebabkan terjadinya starvation. Akibat yang terjadi adalah
kendaraan dari arah lain menjadi terus menunggu giliran untuk berjalan hingga akhirnya
mengalami starvation.
Starvation adalah kondisi yang biasanya terjadi setelah deadlock. Proses yang
kekurangan resource (karena terjadi deadlock) tidak akan pernah mendapat resource
yang dibutuhkan sehingga mengalami starvation (kelaparan). Namun, starvation juga
bisa terjadi tanpa deadlock. Hal ini ketika terdapat kesalahan dalam sistem sehingga
terjadi ketimpangan dalam pembagian resouce. Satu proses selalu mendapat resource,
sedangkan proses yang lain tidak pernah mendapatkannya.
Starvation adalah keadaan dimana satu atau beberapa proses 'kelaparan' karena
terus dan terus menunggu kebutuhan sumber dayanya dipenuhi. Namun, karena
sumber daya tersebut tidak tersedia atau dialokasikan untuk proses lain, akhirnya proses
yang membutuhkan tidak bisa memilikinya. Kondisi seperti ini merupakan akibat dari
keadaan menunggu yang berkepanjangan.
Contoh ilustrasi sederhana dari starvation adalah suatu client yang sedang
berinteraksi dengan sebuah server dalam waktu yang lama mengakibatkan server
tersebut tidak dapat melayani client yang lain.
B. CONCURENCY CONTROL
Concurrency control adalah sistem manajemen database (DBMS) konsep yang
digunakan untuk mengatasi konflik dengan serentak mengakses atau mengubah data
yang dapat dilakukan dengan sistem multi-user. Concurrency control, bila diterapkan ke
DBMS, dimaksudkan untuk mengkoordinasikan bersamaan saat transaksi melestarikan
integritas data
Untuk menggambarkan konsep kontrol concurrency misalnya dua wisatawan
yang pergi ke kios elektronik pada saat yang sama untuk membeli tiket kereta api untuk
tujuan yang sama pada kereta yang sama. Hanya ada satu kursi di kiri pelatih, tetapi
tanpa kontrol concurrency, mungkin wisatawan yang baik akan berakhir membeli tiket
untuk satu kursi. Namun, dengan kontrol concurrency, database ini tidak akan terjadi..
Kedua wisatawan akan masih dapat mengakses database kereta tempat duduk, tetapi
concurrency kontrol akan menjaga keakuratan data dan memungkinkan hanya satu jalan
untuk membeli kursi.
Terdapat beberapa masalah-masalah umum yang muncul pada DBMS, yaitu:
1. Lost update problem (Masalah hilangnya data yang diupdate).
2. Uncommited dependency problem / dirty real (Masalah kebergantungan
terhadap transaksi yang belum commit).
3. Inconsistent analisys problem (masalah analisa yang tidak konsisten).
Tujuan Concurrency Control
Jika sistem yang diberikan belum mengalami kegagalan, semua mekanisme
konkurensi harus menjamin konsistensi dari item data tetap terpelihara, dan setiap
kegiatan dapat diatasi dengan waktu yang terbatas. Mekanisme kontrol konkurensi yang
baik untuk DBMS harus :
1. Tahan terhadap kegagalan komunikasi dan lokasi
2. Dapat dilakukannya proses parallel untuk kebutuhan kerja yang maksimal.
3. Menghasilkan proses komputasi yang sederhana dan media penyimpanannya
lebih efisien.
4. Memiliki kinerja yang memuaskan pada sebuah lingkungan jaringan karena
komunikasi tunda yang sangat baik.
5. Menempatkan beberapa batasan pada struktur dari suatu kegiatan yang
beresiko.
Concurrency Control Locking Strategi
Pessimistic Locking
concurrency kontrol strategi ini melibatkan menjaga sebuah entitas dalam
database terkunci seluruh waktu itu ada dalam database memori. Ini mencegah atau
membatasi user dari mengubah data entitas yang terkunci. Ada dua jenis kunci yang
jatuh di bawah kategori pesimistis penguncian: menulis dan membaca kunci kunci.
Dengan menulis kunci, tetapi semua pemegang kunci dicegah membaca, memperbarui,
atau menghapus entitas. Kunci dengan membaca, pengguna lain dapat membaca
entitas, tetapi tidak ada seorangpun kecuali untuk mengunci dudukan dapat
memperbarui atau menghapusnya. Penguncian Pesimistis memberikan jaminan bahwa
data ada perubahan aman. Namun, ia menjadi kurang bersemangat karena jumlah
serentak atau jumlah entitas yang terlibat dalam transaksi meningkat karena memiliki
potensi untuk menunggu kunci untuk melepaskan akan meningkat.
Optimistic Locking
Strategi ini dapat digunakan ketika kejadian yang bersamaan transaksi, atau
collisions, diharapkan menjadi jarang. Dalam kontras dengan penguncian pesimis,
optimis penguncian tidak mencoba untuk mencegah dari collisions terjadi. Sebaliknya,
ini bertujuan untuk mendeteksi collisions tersebut dan mereka pada kesempatan kali
ketika terjadi. Penguncian optimis dapat mengatasi masalah yang menunggu kunci untuk
melepaskan, tetapi kemudian pengguna memiliki potensi untuk mengalami collisions
ketika mencoba untuk meng-update data.
Serializability dan Recoverability
Tujuan protokol concurrency control adalah untuk menjadwalkan transaksi
sedemikian rupa sehingga dapat menghindar dari berbagai gangguan, dan juga
mencegah tipe-tipe masalah yang digambarkan pada sesi sebelumnya. Satu solusi yang
jelas adalah mengijinkan hanya satu transaksi yang berjalan dalam satu waktu. Satu
transaksi berstatus commit sebelum transaksi berikutnya diijinkan mulai. Namun, tujuan
dari DBMS multi user juga untuk memaksimalkan derajat concurrency atau paralelisme
dalam sebuah sistem, sehingga transaksi yang dapat berjalan tanpa mengganggu satu
sama lain dapat berjalan secara paralel. Contohnya, transaksi yang mengakses bagian
berbeda pada database dapat dijadwalkan bersama tanpa gangguan. Dalam bagian ini,
kita memeriksa serializability sebagai sebuah cara untuk membantu mengidentifikasi
eksekusi transaksi tersebut yang dijamin untuk memastikan konsistensi.
C. TEKNIK CONCURENCY CONTROL
Ada dua teknik concurrency control utama yang mengijinkan transaksi untuk
berjalan dengan aman dalam subjek paralel untuk constraint tertentu, yaitu locking dan
metode timestamp tertentu. Locking dan timestamping adalah pendekatan konservatif
karena mereka menyebabkan transaksi ditunda dalam kasus mereka konflik dengan
transaksi lain pada beberapa waktu di masa yang akan datang. Metode optimistik,
didasarkan pada premis bahwa konflik itu jarang ditemui, jadi mereka mengijinkan
transaksi untuk lanjut tidak tersinkronisasi dan hanya mengecek konflik di bagian akhir,
ketika transaksi melakukan operasi commit.
1. Locking
Salah satu cara untuk menjamin terjadi serialisasi adalah dengan menerapkan
protocol penguncian (locking protocol) pada tiap data yang akan diakses. Setiap
transaksi harus melakukan penguncian pada data yang akan diakses, bergantung pada
kebutuhan operasi yang akan dilakukan.
A. Lock – Based Protocol
Salah satu cara menjamin serializabiliy adalah dengan mensyaratkan bahwa
akses item-item data harus dilakukan dengan menerapkan eksklusivitas. Artinya, selama
sebuah transaksi sedang mengakses sebuah item data, maka tidak ada transaksi lain
yang boleh melakukan perubahan terhadap item data tersebut. Metode yang umum
digunakan untuk mengimplementasikan hal ini adalah dengan kewajiban melakukan
penguncian pada suatu item data sebelum data tersebut diakses.
2 jenis mode lock – based protocol yang digunakan dalam mekanismenya :
a. Bersama (shared)
Mode ini dilambangkan dengan S. Jika sebuah transaksi dapat melakukan
penguncian dengan mode ini pada suatu data item, maka transaksi tersebut
hanya dapat melakukan pembacaan tapi tidak dapat melakukan perubahan
terhadap nilai item tersebut.
b. Tunggal (Exclusive)
Mode ini dilambangkan dengan X. Jika sebuah transaksi dapat melakukan
penguncian dengan mode ini pada suatu item, maka transaksi tersbut dapat
melakukan pembacaan dan perubahan pada nilai item tersebut.
Setiap transaksi harus mengajukan permintaan penguncian (locking) dengan
mode tertentu terhadap data Q, sesuai jenis operasi yang akan dilakukan transaksi.
Permintaan ini akan dilayani oleh modul Concurency-Control dalam sebuah DBMS.
Transaksi tersebut baru dapat melanjutkan/mengerjakan operasi terhadap item data Q
tersebut, jika modul ini telah menyerahkan hak penguncian terhadap item data Q
kepada transaksi tersebut.
S X
S True false true
X False false true
true true
Bila suatu transaksi hanya melakukan pembacaan saja, secara otomatis ia
memerlukan kunci S " baca (S)
Bila transaksi tersebut ingin memodifikasi record maka secara otomatis ia
memerlukan kunci S " memodifikasi (X)
Bila transaksi tersebut sudah menggunakan kunci S, setelah itu ia akan
memodifikasi record, maka kunci S akan dinaikan ke level kunci X.
Kunci X dan kunci S akan dilepaskan pada saat synchpoint (synchronization
point). Synchpoint menyatakan akhir dari suatu transaksi dimana basis data berada
pada state yang konsisten. Bila synchpoint ditetapkan maka:
Semua modifikasi program menjalankan operasi commit atau rollback.
Semua kunci dari record dilepaskan.
Contoh :
Dua buah transaksi T1 dan T2 dimana T1 berfungsi melakukan pentransferan dana
dari rekening B ke rekening A sebesar Rp. 100.000,-.
Penyelesaian :
Dengan menyertakan perintah-perintah penguncian, maka operasi dalam transaksi
T1 dapat kita sajikan sbb :
T1 : lock-X(B)read(B) B ← B – 100000write(B) unlock(B) lock-X (A) read(A) A ← A + 100000write(A)unlock(A)
Transaksi T2 hanya menampilkan total saldo dari kedua rekening tersebut, A dan
B kita nyatakan:
T2 : lock-S(A)r ead(A) unlock(A) lock-S(B)read(B)write(B)display (A+B)
T1 T2 Modul Concurrency
Control
lock-X (B)
Read(B)B ← B – 100000Write(B)Unlock (B)
grant-X(B, T1)
Lock-X(A)
Read(A)A ← A + 100000Write(A)Unlock(A)
Lock-S(A) read (A)unlock(A)lock-S(B)
read(B)unlock(B)display (A+B)
grant-S (A, T2)
grant-S (B, T2)
grant-X(A, T1)
Keterangan :
Schedule di atas menunjukkan aksi-aksi dan juga dilaksanakan oleh kedua transaksi
tsb dan juga titik dimana hak penguncian diberikan oleh modul Concurency Control
dalam DBMS.
Schedule konkuren di atas menghasilkan informasi yang tidak akurat, maka kita
akan melakukan perubahan pada letak perintah pelepasan penguncian (unlock)
dengan menundanya hingga akhir transaksi.
Transaksinya menjadi T3 dan T4
T3 : lock-X(B)read(B)B ← B – 100000write(B)Lock-X(A)read(A)A ← A + 100000write (A)unlock (B)unlock (A)
T4 : lock-S (A)read (A) lock-S (B)read (B)write (B)
unlock (A)unlock (B)display (A+B)
Jika kedua transaksi tersebut dieksekusi secara konkuren dengan potongan
schedule sbb:
T3 T4lock-X(B)read(B)B ← B – 100000write(B)
lock-X (A)
lock-S (A)read (A)lock-S (B)
Secara teoritis, schedule ini akan memberikan hasil yang akurat sesuai dengan
hasil yang diberikan oleh schedule serial. Baik T3 maupun T4 tidak dapat di eksekusi
lock-S(B) mengakibatkan T4 menunggu T3 untuk melepaskan penguncian terhadap B,
sementara eksekusi lock-X(A) mengakibatkan T3 menunggu T4 melepaskan penguncian
terhadap A.Kondisi seperti ini disebut deadlock. Dan untuk mengatasi masalah ini T3
atau T4 harus di roll back dan melepaskan kuncian.
B. Locking Protocol Dua Fase
Pada banyak kasus, two-phase locking protocol banyak dipergunakan untuk
menjaga sifat serializable dari suatu penjadwalan, namun protokol ini belum dapat
menjamin bahwa tidak akan terjadi deadlock karena masih ada transaksi yang berada
dalam status menunggu ( wait()).
Fase atau tahapan yang harus dilalui transaksi pada protocol ini :
a. Fase Pertumbuhan (Growing phase)
Fase dimana sebuah transaksi hanya boleh melakukan penguncian pada data.
Pada fase ini, transaksi tidak boleh melakukan pembebasan pada data lain.Fase
pelepasan (Shrinking Phase)
Sebuah transaksi dapat melepaskan sejumlah penguncian, tetapi belum
melakukan penguncian yang baru.
b. Fase Pelepasan (Shrinking Phase)
Fase dimana sebuah transaksi melakukan pembebasan pada data. Pada fase ini,
transaksi tidak boleh melakukan penguncian pada data lain.
Inti dari protocol ini adalah, suatu transaksi jangan pernah melepaskan kunci
sebelum operasi selesai, aturannya :
Satu transaksi harus meminta sebuah kunci untuk suatu iterasi sebelum
melaksanakan operasi pada item tersebut. Kunci yang diminta dapat berupa
write lock maupun read lock, tergantung kebutuhan.
Sekali transaksi melepaskan kunci, maka transaksi tersebut tidak dapat meminta
kunci yang baru.
Ada 2 jenis mekanisme Locking Protocol 2 fase :a. Locking Protocol Dua Fase yang Ketat (Strict two – phase locking protocol)
Semua penguncian dengan metode exclusive dari sebuah transaksi harus tetap
dipegang hingga transaksi berada dalam status berhasil sempurna (commited).
Ketentuan ini menjamin bahwa setiap data yang ditulis oleh transaksi yang belum
berstatus berhasil sempurna (commited) terus dikunci dalam mode exclusive, untuk
mencegah transaksi lainnya melakukan pembacaan terhadap item data tersebut.
b. Locking Protocol Dua Fase yang Padat (trigorous phase locking protocol)
Jenis mekanisme ini menghendaki semua penguncian (baik yang mode exclusive
maupun shared) tetap diterapkan hingga transaksi berstatus berhasil sempurna
(commited). Mudah diperiksa, bahwa dengan mekanisme ini, transaksi – transaksi dapat
dikerjakan secara serial sesuai urutan yang ditunjukkan oleh perintah commit.
Contoh :
T5 : read (a1)read (a2)
…read (an)write (a1)
T6 : read (a1)read (a2)
write (a1 +a2)
Jika menerapkan Locking Dua fase, maka T5 harus mengunci a1 dalam mode
exclusive. Akibatnya semua eksekusi konkuren dari kedua transaksi menjadi eksekusi
serial. Jika T5 melakukan penguncian dengan mode exclusive di saat penulisan a1,, maka
kondisi konkurensi akan lebih baik, karena T5 dan T6 dapat mengakses a1 dan a2 secara
simultan .
T5 T6
Lock-S (a1)
Lock-S (a2)
Lock-S (a3) Lock-S (a4)
Lock-S (an) Upgdrade (a1)
Lock-S (a1)
Lock-S (a2)
Unlock (a1) Unlock (a2)
2. Time Stamp Protocol
Salah satu alternatif concurrency control yang dapat menghilangkan deadlock
adalah time stamping. Secara umum, timestamping (TS) adalah penanda waktu saat
transaksi terjadi. Hal ini untuk mengurutkan eksekusi transaksi agar sama dengan
eksekusi serial.
Time stamp dapat berupa:
a. waktu sistem saat transaksi dimulai,
b. penghitung logik (logical counter) yang terus bertambah nilainya tiap kali
terjadi transaksi baru.
Jika timestamp transaksi a lebih kecil daripada timestamp transaksi b , atau
TS(Ta) < TS(Tb), maka transaksi a (Ta) selalu dilaksanakan sebelum transaksi b (Tb).
Contoh :
Misal rekaman pada basis data memuat TS 168, yang mengidentifikasikan
transaksi dengn TS 168 adalah transaksi yang terkemudian yang sukses
mengupdate rekaman yang bersangkutan. Maka jika ada transaksi dengan TS 170
mencoba mengupdate rekaman yang sama, maka update ini akan diijinkan,
karena TS yang dimiliki lebih kemudian dari TS pada rekaman. Saat transaksi ini
dilakukan, TS pada rekaman akan diatur menjadi 170. Sekarang, jika transaksi
yang akan mengupdate rekaman tersebut memiliki TS 165, maka update ditolak
karena TS-nya < TS di rekaman.
Selain transaksi, item data juga memiliki nilai time stamp. Untuk setiap item
data Q, ada 2 nilai time stamp, yaitu:
1. Read time stamp atau R-timestamp(Q), yang menunjukkan nilai TS terbesar dari
setiap transaksi yang berhasil menjalankan operasi read(Q).
2. Write time stamp atau W-timestamp(Q), yang menunjukkan nilai TS terbesar
dari setiap transaksi yang berhasil menjalankan operasi write(Q).
a. Timestamp Ordering Protocol
Protokol ini menjamin bahwa tiap operasi read dan write yang memiliki konflik
dieksekusi sesuai urutan TS.
Untuk transaksi Ta yang menjalankan operasi read(Q)
Jika TS(Ta) < W-TS(Q) maka transaksi Ta perlu membaca kembali nilai
Q yang telah ditulis dan transaksi Ta akan dibatalkan (rollback).
Jika TS(Ta) ≥ W-TS(Q) maka operasi read dieksekusi, dan R-TS(Q) diisi
dengan nilai terbesar diantara TS(Ta) dan R-TS(Q).
Untuk transaksi Ta yang menjalankan operasi write(Q):
jika TS(Ta) < R-TS(Q) maka nilai Q yang baru dihasilkan Ta tidak akan
dimanfaatkan lagi, dan sistem berasumsi bahwa nilai tersebut tidak
pernah dihasilkan. Karena itu operasi write ditolak, dan transaksi Ta
di rollback.
TS(Ta) < W-TS(Q) maka itu berarti transaksi Ta sedang berusaha
melakukan penulisan nilai Q yang kadaluarsa. Maka operasi wrwite
ini akan ditolak dan transaksi Ta akan di rollback.
Di luar kondisi a dan b di atas, operasi write dieksekusi dan W-TS(Q)
diberi nilai baru yang sama dengan TS(Ta).
Terhadap transaksi Ta yang di rollback, akan diberikan sebuah
timestamp yang baru dan diulang kembali.
Properti timestamp:
a. Uniqueness : masing-masing timestamp suatu transaksi adalah unik.
b. Monotonicity : 2 timestamp yang dihasilkan transaksi yang sama
meningkat secara monoton.
Cara pemberian nilai timestamp:
a. Global (systemwide) monotonically increasing number
b. Local (site) monotonically increasing number.
Untuk menggambarkan protokol ini, kita memperhatikan transaksi T7 dan T8.
Transaksi T7 menampilkan nilai saldo rekening A dan B dan didefinisikan sbb:
T7 : read (B)read (A)display (A+B)
Transaksi T8 yang mentrasfer dari rekening A ke rekening B dan kemudian
menampilkan isi keduanya.
T8 : read (B)B ← B – 100000write (B)
read (A)A ← A + 100000write (A)
display (A+B)Dalam menentukan schedule dengan protokol timestamp, kita mengasumsikan
bahwa sebuah transaksi diberikan sebuah timestamp segera sebelum instruksi pertama.
Karena itu, dalam schedule berikut ini, TS(T7) < Ts(T8) dan schedule ini mungkin
dieksekusi dengan menggunakan protokol Timestamping Ordering.
T7 T8
read (B)
read (A)
Display (A+B)
read (B)B ← B – 100000write (B)
read (A)A ←A + 100000write (A)display (A+B)
3. Validation Based Control
3 fase eksekusi yang harus dilalui oleh transaksi :
1. Read dan eksekusi: Transaksi melakukan operasi write hanya pada
variabel lokal temporer tanpa melakukanperubahan ke basis data aktual
2. Validasi: Transaksi membentuk uji validasi untukmenentukan apkah
transaksi tersebutdapat melakukan penyalinan / pengubahan ke basis
data dari variabel lokal temporere yang nilainya diperoleh dari operasi
write tanpa menyebabkan pelanggaran serializability.
3. Write : Jika fase validasi transaksi berhasil, maka perubahan
sesungguhnya dilakukan ke basis data. Jika validasi tidak berhasil, maka
Ti akan di-roll back.
Semua fase dalam eksekusi transaksi konkuren dapat terjadi pada waktu
bersamaan.
Setiap transaksi Ti akanmemiliki 3 timestamp
Start(Ti) : wkatu dimana Ti memuliaieksekusinya
Validation(Ti): waktu dimana Ti, selesai melakukan Fase pembacaan dan
memulai fase validasi
Finish(Ti) : waktu dimana Ti menyelesaikan fase penulisan
Urutan serializability ditentukan dengan teknik pengurutan timestamp dengan
menggunakan nilai timestamp validation (Ti ), oleh karena itu nilai TS(Ti) = Validation(Ti).
Jika untuk semua transaksi Ti dengan TS (Ti) < TS (Tj) salah satu dari dua kondisi
berikut harus dapat dipenuhi :
finish(Ti) < start(Tj) , karena Ti menyelesaikan eksekusinya sebelum Tj
dimulai
start(Tj) < finish(Ti) < validation(Tj) dan thimpunan item data yang ditulis
Ti dtidak beririsan dengan himpunan item data yang dibaca oleh Tj.
kemudian validasi Tj dikatakan berhasil, jika tidak validasi gagal dan Tj di
batalkan.
T7 T8
Read (B)
Read(A)<validasi>Display (A+B)
Read (B)B ← B – 100000Read (A) A ← A + 100000
<validasi>Write (B)Write(A)
D. DEADLOCK
Permasalahan deadlock terjadi karena sekumpulan proses-proses yang di-blok
dimana setiap proses membawa sebuah sumber daya dan menunggu mendapatkan
sumber daya yang dibawa oleh proses lain. Misalnya sistem mempunyai 2 tape drive dan
terdapat dua proses P1 dan P2 yang masing masing membawa satu tape drive dan
masing-masing memerlukan tape drive yang dibawa proses lain sehingga terjadi
keadaan saling menunggu resource dan sistem di-blok.
Contoh lain, misalnya terdapat semaphore A dan B yang diinisialisasi 1 dan terdapat dua
proses P0 dan P1 masing-masing membawa semaphore A dan B. Kemudian P0 dan P1
meminta semaphore B dan A dengan menjalankan operasi wait. Hal ini mengakibatkan
proses di-blok dan terjadi deadlock.
P0 P1
wait (A); wait(B);
wait (B); wait(A);
Karakteristik Deadlock
Deadlock terjadi bila terdapat empat kondisi berikut ini secara simultan.
a. Mutual Exclusion : hanya satu proses pada satu waktu yang dapat menggunakan
sumber daya.
b. Genggam dan Tunggu (Hold and Wait) : suatu proses membawa sedikitnya satu
sumber daya menunggu mendapatkan tambahan sumber daya baru yang dibawa
oleh proses
c. Non-Preemption : sebuah sumber daya dapat dibebaskan dengan sukarela oleh
proses yang memegangnya setelah proses menyelesaikan task.
d. Menunggu Secara Sirkuler (Circular Wait) : Terdapat sekumpulan proses {P0, P1,
…, P0} yang menunggu sumber daya dimana P0 menunggu sumber daya yang
dibawa P1, P1 menunggu sumber daya yang dibawa P2, dan seterusnya, Pn–1
menunggu sumber daya yang dibawa oleh Pn, dan Pn menunggu sumber daya
yang dibawa P0.
Ketiga syarat pertama merupakan syarat perlu (necessary conditions) bagi terjadinya
deadlock. Keberadaan deadlock selalu berarti terpenuhi kondisi-kondisi diatas, tak
mungkin terjadi deadlock bila tidak ada ketiga kondisi itu. Deadlock terjadi berarti
terdapat ketiga kondisi itu, tetapi adanya ketiga kondisi itu belum berarti terjadi
deadlock. Deadlock baru benar-benar terjadi bila syarat keempat terpenuhi. Kondisi
keempat merupakan keharusan bagi terjadinya peristiwa deadlock. Bila salah satu saja
dari kondisi tidak terpenuhi maka deadlock tidak terjadi.
Resource Allocation Graph
Deadlock dapat digambarkan lebih presisi dengan menggunakan graph berarah yang
disebut resource allocation graph. Graph terdiri dari himpunan titik V dan garis E.
Himpunan titik (vertex) V dibagi menjadi dua tipe yaitu himpunan proses yang aktif pada
sistem P = {P1, P2, ..., Pn} dan tipe sumber daya pada sistem R = {R1, R2, ..., Rm}
Garis berarah dari proses Pi ke tipe sumber daya Rj dinotasikan dengan Pi → Rj
artinya proses Pi meminta satu anggota dari tipe sumber daya Rj dan sedang menunggu
sumber daya tersebut. Garis berarah dari tipe sumber daya Rj ke proses Pi dinotasikan
dengan Rj → Pi artinya satu anggota tipe sumber daya Rj dialokasikan ke proses Pi. Garis
berarah Pi → Rj disebut request edge dan garis berarah Rj → Pi disebut assignment
edge.
Notasi-notasi yang digunakan pada resource allocation graph adalah :
Proses
Tipe sumber daya dengan 4 anggota
Pi meminta anggota dari Rj
Pi membawa satu anggota Rj
Contoh resource allocation graph
Resource allocation graph yang tidak terjadi deadlock
Dimana keadaan sistem adalah sebagai berikut :
Himpunan P, R dan E :
P = {P1, P2, P3}
R = {R1, R2, R3, R4}
E = {P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3}
Anggota sumber daya :
Satu anggota dari tipe sumber daya R1.
Dua anggota dari tipe sumber daya R2.
Satu anggota dari tipe sumber daya R3.
Tiga anggota dari tipe sumber daya R4.
Status proses :
Proses P1 membawa satu anggota tipe sumber daya R2 dan menunggu
satu anggota tipe sumber daya R1.
Proses P2 membawa satu anggota R1 dan R2 dan menunggu satu
anggota tipe sumber daya R3.
Proses P3 membawa satu anggota R3.
Fakta dasar dari resource allocation graph menunjukkan bahwa :
Apabila pada graph tidak terdapat siklus maka tidak ada proses dalam sistem
yang Deadlock
Apabila pada graph terdapat siklus sistem kemungkinan deadlock dengan
ketentuan:
Jika pada setiap tipe sumber daya hanya terdapat satu anggota
maka terjadi deadlock
Jika pada setiap tipe sumber daya terdapat beberapa anggota maka
kemungkinan terjadi deadlock
Untuk ilustrasi konsep diatas kita lihat kembali resource allocation graph tidak terdapat
siklus, jadi tidak terjadi deadlock pada sistem. Misalnya proses P3 meminta satu anggota
dari tipe sumber daya R2. Karena tidak tersedia anggota tipe sumber daya tersebut,
request edge P3 → R2 ditambahkan ke graph seperti pada tersebut. Pada kasus ini,
terdapat dua siklus pada sistem, yaitu :
P1 → R1 → P2 → R3 → P3 → R2 → P1
P2 → R3 → P3 → R2 → P2
Proses P1, P2 dan P3 terjadi deadlock. Proses P2 menunggu sumber daya R3 yang
dibawa proses P3. Proses P3 sebaliknya menunggu proses P1 atau P2 melepas sumber
daya R2. Proses P1 menunggu proses P2 melepas sumber daya R1.
Resource allocation graph yang terjadi deadlock
Pada contoh resource allocation graph yang terjadi seadlock terdapat siklus :
P1 → R1 → P3 → R3 → P1
Akan tetapi pada sistem tidak terjadi deadlock. Terlihat bahwa proses P4 kemungkinan
melepas tipe sumber daya R2. Sumber daya tersebut kemudian dapat dialokasikan
untuk
P3 dan akan menghapus siklus.
METODE MENANGANI DEADLOCK
Terdapat tiga metode untuk menangani permasalahan deadlock yaitu :
Menggunakan protocol untuk menjamin bahwa sistem tidak pernah memasuki
status deadlock
Mengijinkan sistem memasuki status deadlock dan kemudian memperbaikinya.
Mengabaikan permasalahan dan seakan-akan deadlock tidak pernah terjadi
pada sistem. Model ini yang banyak digunakan pada sistem operasi termasuk
UNIX.
MENCEGAH DEADLOCK
Metode ini berkaitan dengan pengkondisian sistem agar menghilangkan
kemungkinan terjadinya deadlock. Pencegahan merupakan solusi yang bersih
dipandang dari sudut tercegahnya deadlock. Metode ini sering menghasilkan utilisasi
sumber daya yang buruk. Pencegahan deadlock merupakan metode yang banyak
dipakai. Untuk mencegah deadlock dilakukan dengan meniadakan salah satu dari syarat
perlu sebagai berikut :
Mencegah Mutual Exclusion
Mutual exclusion benar-benar tak dapat dihindari. Hal ini dikarenakan tidak ada
sumber daya yang dapat digunakan bersama-sama, jadi sistem harus membawa
sumber daya yang tidak dapat digunakan bersama-sama.
Mencegah Hold and Wait
Untuk mencegah hold and wait, sistem harus menjamin bila suatu proses
meminta sumber daya, maka proses tersebut tidak sedang memegang sumber
daya yang lain. Proses harus meminta dan dialokasikan semua sumber daya
yang diperlukan sebelum proses memulai eksekusi atau mengijinkan proses
meminta sumber daya hanya jika proses tidak membawa sumber daya lain.
Model ini mempunyai utilitas sumber daya yang rendah dan kemungkinan
terjadi starvation jika proses membutuhkan sumber daya yang popular sehingga
terjadi keadaan menunggu yang tidak terbatas karena setidaknya satu dari
sumber daya yang dibutuhkannya dialokasikan untuk proses yang lain.
Mencegah Non Preemption
Peniadaan non preemption mencegah proses-proses lain harus menunggu.
Seluruh proses menjadi preemption, sehingga tidak ada tunggu menunggu. Cara
mencegah kondisi non preemption :
Jika suatu proses yang membawa beberapa sumber daya meminta sumber
daya lain yang tidak dapat segera dipenuhi untuk dialokasikan pada proses
tersebut, maka semua sumber daya yang sedang dibawa proses tersebut
harus dibebaskan.
Proses yang sedang dalam keadaan menunggu, sumber daya yang
dibawanya ditunda dan ditambahkan pada daftar sumber daya.
Proses akan di restart hanya jika dapat memperoleh sumber daya yang
lama dan sumber daya baru yang diminta.
Mencegah Kondisi Menunggu Sirkular
Sistem mempunyai total permintaan global untuk semua tipe sumber daya.
Proses dapat meminta proses kapanpun menginginkan, tapi permintaan harus
dibuat terurut secara numerik. Setiap proses yang membutuhkan sumber daya
dan memintanya maka nomor urut akan dinaikkan. Cara ini tidak akan
menimbulkan siklus. Masalah yang timbul adalah tidak ada cara pengurutan
nomor sumber daya yang memuaskan semua pihak.
MENGHINDARI DEADLOCK
Metode alternatif untuk menghindari deadlock adalah digunakan informasi
tambahan tentang bagaimana sumber daya diminta. Misalnya pada sistem dengan satu
tape drive dan satu printer, proses P pertama meminta tape drive dan kemudian printer
sebelum melepaskan kedua sumber daya tersebut. Sebaliknya proses Q pertama
meminta printer kemudian tape drive. Dengan mengetahui urutan permintaan dan
pelepasan sumber daya untuk setiap proses, dapat diputuskan bahwa untuk setiap
permintaan apakah proses harus menunggu atau tidak. Setiap permintaan ke system
harus dipertimbangkan apakah sumber daya tersedia, sumber daya sedang dialokasikan
untuk proses dan permintaan kemudian serta pelepasan oleh proses untuk menentukan
apakah permintaan dapat dipenuhi atau harus menunggu untuk menghindari deadlock.
Model yang sederhana dan sangat penting dibutuhkan adalah setiap proses
menentukan jumlah maksimum sumber daya dari setiap tipe yang mungkin diperlukan.
Algoritma deadlock avoidance secara dinamis memeriksa status sumber daya yang
dialokasikan untuk menjamin tidak pernah terjadi kondisi menunggu sirkular. Status
alokasi sumber daya ditentukan oleh jumlah sumber daya yang tersedia dan yang
dialokasikan dan maksimum permintaan oleh proses-proses. Untuk penghindaran
deadlock diperlukan pengertian mengenai state selamat (safe state) dan state tak
selamat (unsafe state).
Ketika suatu proses meminta sumber daya yang tersedia, sistem harus
menentukan apakah alokasi sumber daya pada proses mengakibatkan sistem dalam
state selamat. Sistem dikatakan dalam state selamat jika sistem dapat mengalokasikan
sumber daya untuk setiap proses secara berurutan dan menghindari deadlock. Urutan
proses <P1, P2, …, Pn> selamat jika untuk setiap Pi, sumber daya yang masih diminta Pi
masih memenuhi sumber daya yang tersedia dan sumber daya yang dibawa oleh setiap
Pj, dimana j < i. Jika sumber daya yang diperlukan Pi tidak dapat segera disediakan, maka
Pi dapat menunggu sampai semua Pj selesai. Ketika Pj selesai, Pi dapan memperoleh
sumber daya yang diperlukan, mengeksekusi, mengembalikan sumber daya yang
dialokasikan dan terminasi. Ketika Pi selesai, Pi+1 dapat memperoleh sumber daya yang
diperlukan dan seterusnya. Jika sistem dalam state selamat maka tidak terjadi deadlock,
sedangkan jika sistem dalam state tidak selamat (unsafe state) maka kemungkinan
terjadi deadlock
seperti Gambar di bawah ini metode menghindari deadlock menjamin bahwa sistem
tidak
pernah memasuki state tidak selamat.
Untuk menggambarkan sistem dapat berpindah dari state selamat ke state tidak
selamat dapat dilihat ilustrasi berikut ini. Misalnya sistem mempunyai 12 magnetic tape
drive dan 3 proses P0, P1 dan P2. Proses P0 membutuhkan 10 tape drive, proses P1
membutuhkan 4 dan proses P2 membutuhkan 9 tape drive. Misalnya pada waktu t0,
proses P0 membawa 5 tape drive, P1 membawa 2 dan P2 membawa 2 tape drive
sehingga terdapat 3 tape drive yang tidak digunakan.
Kebutuhan Maksimum Kebutuhan Sekarang
P0 10 5
P1 4 2
P2 9 2
Pada waktu t0, sistem dalam state selamat. Urutan < P1, P0, P2> memenuhi
kondisi selamat karena P1 dapat segera dialokasikan semua tape drive dan kemudian
mengembalikan semua tape drive sehingga sistem tersedia 5 tape drive. Kemudian P0
dapat memperoleh semua tape drive dan mengembalikan semua sehingga system
tersedia 10 tape drive dan terakhir proses P2 dapat memperoleh semua tape drive dan
mengembalikan semua tape drive sehingga system tersedia 12 tape drive.
Sistem dapat berubah dari state selamat ke state tidak selamat. Misalnya pada
waktu t1, proses P2 meminta tambahan alokasi 1 tape drive. Sistem menjadi tidak
selamat. Pada saat ini, hanya proses P1 yang mendapatkan semua tape drive dan
kemudian mengembalikan semua tape drive sehingga hanya tersedia 4 tape
drive.Karena proses P0 sudah dialokasikan 5 tape drive tetapi membutuhkan maksimum
10 tape drive sehingga meminta 5 tape drive lagi. Karena tidak tersedia, proses P0 harus
menunggu demikian juga P2 sehingga system menjadi deadlock.
MENDETEKSI DEADLOCK
Jika sistem tidak menyediakan algoritma mencegah deadlock dan menghindari
deadlock, maka terjadi deadlock. Pada lingkungan ini sistem harus menyediakan :
Algoritma yang menguji state sistem untuk menentukan apakah deadlock telah
terjadi.
Algoritma untuk memperbaiki dari deadlock.
1. Satu Anggota untuk Setiap Tipe Sumber Daya
Jika semua sumber daya hanya mempunyai satu anggota, kita dapat menentukan
lgoritma mendeteksi deadlock menggunakan bentuk resource allocation graph yang
disebut wait-for graph.
Garis dari Pi → Pj pada wait-for graph menandakan bahwa proses Pi menunggu j
melepaskan sumber daya yang dibutuhkan Pi. Garis Pi → Pj terdapat pada wait-for raph
jika dan anya jika resource allocation graph berisi dua garis Pi → Rq dan Rq → Pj ntuk
beberapa sumber daya Rq seperti Gambar di bawah ini
Secara periodik sistem menggunakan algoritma yang mencari siklus pada graph.
lgoritma untuk mendeteksi siklus pada graph membutuhkan operasi n2 dimana n dalah
jumlah titik pada graph.
2. Beberapa Anggota untuk Setiap Tipe Sumber Daya
Untuk Tipe sumber daya yang mempunyai beberapa anggota digunakan
algoritma yang sejenis dengan algoritma Banker dengan struktur daya seperti di bawah
ini :
Available : vector panjang m menandakan jumlah sumber daya yang tersedia
untuk etiap tipe sumber daya.
Allocation : matrik n x m yang mendefinisikan jumlah sumber daya untuk setiap
ipe sumber daya yang sedang dialokasikan untuk setiap proses.
Request : matrik n x m yang mendefinisikan permintaan setiap proses. Jika
Request I, j] = k, maka proses Pi meminta k anggota tipe sumber daya Rj.
Algoritma mendeteksi deadlock mempunyai urutan berikut :
1. Work dan Finish adalah vektor panjang m dan n. Inisialisasi Work =
Available. untuk i = 1, 2, …, n, jika Allocationi ≠ 0, maka Finish[i] = false; sebaliknya
finish[i] = true.
2. Cari indeks i yang memenuhi kondisi berikut :
(a) Finish[i] == false
(b) Requesti ≤ Work
Jika tidak terdapat i ke langkah 4.
3. Work = Work + Allocationi
Finish[i] = true
Ke langkah 2.
4. Jika Finish[i] == false, untuk beberapa i, 1 ≤ i ≤ n, maka sistem berada pada state
deadlock state. Jika Finish[i] == false, maka Pi deadlock
Algoritma ini memerlukan operasi O(m x n2) untuk mendeteksi apakah sistem
berada pada state deadlock. Untuk menggambarkan algoritma deteksi, misalnya sistem
terdapat 5 proses P0 sampai P4 dan 3 tipe sumber daya A, B dan C. Tipe sumber daya A
mempunyai 7 anggota, tipe sumber daya B mempunyai 2 anggota dan tipe sumber daya
C mempunyai 6 anggota. Pada waktu T0, state sumber daya yang dialokasikan adalah :
Sistem tidak berada pada state deadlock karena urutan <P0, P2, P3, P1, P4>
menghasilkan Finish[i] = true untuk semua i. Misalnya saat ini proses P2 membutuhkan
tambahan satu anggota tipe sumber daya C. Matrik Request dimodifikasi sebagai berikut
Sistem sekarang berada pada state deadlock. Meskipun proses P0 dapat membawa
sumber daya, jumlah sumber daya yang tersedia tidak dapat memenuhi permintaan
proses lain. Sehingga terjadi deadlock pada proses P1, P2, P3 dan P4.
PERBAIKAN DARI DEADLOCK
Terdapat dua pilihan untuk membebaskan deadlock. Satu solusi sederhana
adalah dengan menghentikan satu atau beberapa proses untuk membebaskan kondisi
menunggu sirkular. Pilihan kedua adalah menunda beberapa sumber daya dari satu atau
lebih proses yang deadlock.
Terminasi Proses
Untuk memperbaiki deadlock dengan terminasi proses, dapat diguankan salah satu dari
dua metode di bawah ini :
Menghentikan (abort) semua proses yang deadlock
Menghentikan satu proses setiap waktu sampai siklus deadlock hilang.
Untuk menentukan urutan proses yang harus dihentikan ada beberapa faktor yang harus
diperhatikan :
Prioritas proses.
Berapa lama proses dijalankan dan berapa lama lagi selesai.
Sumber daya yang digunakan proses.
Sumber daya proses yang diperlukan untuk menyelesaikan task.
Berapa proses yang perlu diterminasi.
Apakah proses interaktif atau batch.
Menunda Sumber Daya
Untuk menghilangkan deadlock dengan menunda sumber daya, sumber daya dari proses
harus ditunda dan memberikan sumber daya tersebut ke proses lain sampai siklus
deadlock hilang.
Jika penundaan dibutuhkan untuk menghilangkan deadlock, terdapat tiga hal
yang perlu diperhatikan :
Pilihlah korban (sumber daya) yang mempunyai biaya minimal.
Lakukan rollback yaitu memulai kembali (restart) proses pada state yang
selamat.
Harus dijamin starvation tidak akan terjadi karena kemungkinan beberapa
proses selalu terpilih sebagai korban termasuk jumlah rollback sebagai faktor
biaya.
MANAJEMEN DEADLOCK TERDISTRIBUSI
Algoritma pengendalian konkurensi berbasis kunci ( dan beberapa algoritma
berbasis penandaan ( timestamp) yang mengharuskan transakasi untuk menunggu) akan
menghasilkan deadlock. Didalam lingkungan DDBMS, pendeteksian deadlock akan lebih
rumit lagi jika pengaturan kunci tidak terpusat., seperti contoh berikut
Contoh 2.2 Deadlock Terdistribusi
Diketahui tiga transaksi T1, T2, dan T3 dengan:
T1 ada pada lokasi S1 dan membuat perantara pada lokasi S2
T2 ada pada lokasi S2 dan membuat perantara pada lokasi S3
T3 ada pada lokasi S3 dan membuat perantara pada lokasi S1
Transaksi – transaksi tersebut melakukan pengaturan penguncian Shared (read /
baca) dan Exclusive(write / tulis) seperti digambarkan di bawah, di mana read_lock (Ti,xj)
menandakan penguncian baca oleh transaksi Ti pada item data xj dan write_lock (Ti,xj)
menandakan penguncian tulis oleh transaksi Ti pada item data x j
Time S1 S2 S3
t1 read_lock(T1.x1) write_lock(T2.y2) read_lock(T3.y3)
t2 write_lock(T1.y1) write_lock(T2.y2)
t3 write_lock(T3.x1) write_lock(T1.y2) write_lock(T2.y3)
wait-for-graphs (WFGs) untuk setiap lokasi, seperti ditunjukkan pada gambar berikut
Gambar 1 Wait-for-graphs untuk lokasi S1, S2, dan S3
Gambar 2 Kombinasi wait-for-graphs untuk lokasi S1, S2, S3
Tidak ada siklus di dalam WFGs yang individu, dan tidak terlihat adanya deadlock
pada WFGs individual ini. Namun, jika di lakukan kombinasi WFGs, seperti digambarkan
dalam Gambar 2.3 dapat lihat deadlock itu ada: ada suatu siklus dari:
T3 → T1 → T2 → T3
Contoh 2.3.1 menunjukkan DDBMS tidak cocok bila setiap lokasi membangun WFG
lokalnya sendiri untuk mengecek suatu deadlock, Hal ini membutuhkan WFG global yang
merupakan gabungan dari semua WFG lokal. Ada tiga metode yang digunakan untuk
menangani pendeteksian deadlock dalam DDBMSs: pemusatan ( Centralized ) , hirarki (
hierarchi) , dan Pendistribusian pendeteksian deadlock ( distributed).
Pendeteksian Deadlock Terpusat ( Centralized Deadlock Detection )
Dengan Pendeteksian deadlock terpusat, sebuah lokasi ditunjuk sebagai
Deadlock Detection Coordinator (DDC) yang bertanggung jawab atas pembangunan dan
pemeliharaan WFG global. Secara berkala, setiap manajer kunci mengirimkan WFG
lokalnya ke DDC. DDC kemudian membangun WFG global dan memeriksa apakah ada
siklus di dalamnya. Jika ada satu atau lebih siklus, DDC harus menghancurkan setiap
siklus dengan memilih transaksi untuk rolledback (di putar ulang ) dan restarted (kembali
ke awal). DDC harus menginformasikan semua lokasi yang terlibat dalam pemrosesan
transaksi – transaksi yang di rolledback dan di restarted tersebut.
Untuk meminimalkan jumlah data yang dikirim, seorang manajer kunci hanya
perlu mengirimkan perubahan yang terjadi di WFG lokal sejak pengiriman data yang
terakhir. Perubahan ini akan menyebabkan penambahan atau pengurangan terakhir di
WFG lokal. Kekurangan pada pendekatan ini adalah sistem mungkin kurang dapat
diandalkan, saat terjadinya kegagalan di lokasi pusat.
Pendeteksian Deadlock Hirarki ( Hierarchical Deadlock Detection )Dengan pendeteksian deadlock hirarki, lokasi – lokasi yang berada dalam
jaringan diatur ke dalam suatu bentuk hirarki. Setiap lokasi mengirimkan WFG lokal nya
ke lokasi pendeteksian deadlock di atasnya secara hirarki (Menasce dan Muntz, 1979).
Gambar 3 menggambarkan suatu hirarki untuk delapan lokasi, S1 sampai dengan
S8. Level 1 adalah daun yang merupakan lokasi – lokasi yang tergabung, di mana lokal
deteksi deadlock berada. Level 2 yang di variabelkan dengan DD ij mendeteksi deadlock
yang melibatkan lokasi yang berdekatan dengan i dan j. Level 3 mendeteksi deadlock
antara empat lokasi yang bersebelahan. Akar dari pohon hirarki adalah detektor
deadlock global yang akan mendeteksi deadlock diantaranya,, sebagai contoh, lokasi S1
dan S8
Gambar 3 Pendeteksian Deadlock Hirarki
Pendekatan ini mengurangi ketergantungan pada suatu pemusatan lokasi, yang
akan mengurangi biaya komunikasi. Namun hal ini lebih sulit untuk dilaksanakan, di
karenakan oleh keberadaan dari suatu lokasi dan juga pada kegagalan komunikasi antar
lokasi tersebut.
Pendeteksian Deadlock Terdistribusi ( Distributed Deadlock Detection )
Ada berbagai macam algoritma pendeteksian deadlock terdistribusi, tapi ada
satu metode yang paling banyak digunakan yang telah dikembangkan oleh Obermarck
(1982). Pada pendekatan ini, sebuah simpul eksternal Text ditambahkan ke WFG lokal
untuk mengindikasikan adanya suatu perwakilan transaksi di satu lokasi yang jauh.
Saat sebuah Transaksi T1 pada lokasi S1 ,membuat suatu perwakilan transaksi
pada lokasi S2 , kemudian akhir dari simpul pada lokasl WFG ditambahkan dari T1 ke
simpul Text yang baru, Demikian pun sebaliknya pada lokasi S2 diakhir simpul
ditambahkan pada local WFGnya yaitu dari Text ke simpul T1 .
Sebagai contoh, WFG global yang ditunjukkan dalam Gambar 2.3.4 akan
menunjukan WFGs lokal pada S1, S2, dan S3 yang ditunjukkan dalam Gambar 2.5 Sudut
WFG lokal yang menghubungkan ke Text diberi label sesuai dengan site yang terlibat.
Sebagai contoh, sudut yang menghubungkan T1 dan Text pada S1 lokasi diberi label S2.
Sebagai wakil dari sudut yang diciptakan oleh T1 transaksi pada lokasi S2.
Jika suatu WFG lokal mengandung sebuah siklus yang tidak melibatkan simpul Text maka
lokasi dan DDBMS dalam keadaan deadlock. Tetapi keberadaan Text dapat juga
mengakibatkan deadlock pada transaksi global yaitu pada saat WFG lokal mengandung
sebuah siklus yang menyertakan simpul Text..
Namun saat simpul Text menjadi perwakilan transaksi yang berbeda keberadaan simpul
tersebut tidak mengakibatkan terjadinya deadlock pada transaksi global, tapi siklus dari
bentuk tersebut akan muncul pada WFG jika ada sebuah deadlock Untuk menentukan
ada atau tidaknya sebuah deadlock , beberapa bentuk graph harus di gabungkan . Jika
Lokasi S1 , memiliki potensial untuk terjadinya deadlock , local WFG akan memiliki
format:
Text →Ti → Tj → …→ Tk → Text
Untuk mencegah lokasi saling mengirimkan WFG mereka kepada yang lain,
sebuah strategi sederhana mengalokasikan sebuah timestamp ke setiap transaksi dan
mengharuskan lokasi S1 melakukan transmisi WFG nya hanya ke lokasi dimana transaksi
Tk sedang menunggu, Sk , dinyatakan jika ts(Ti) < ts(Tk). Diasumsikan bahwa ts(Ti) <
ts(Tk), lalu untuk memeriksa apakah ada deadlock , lokasi S1 akan melakukan transmisi
ke WFG lokal di lokasi Sk . Lokasi Sk sekarang menginformasikannya ke lokal WFGnya dan
memeriksa apakah ada siklus yang tidak mengikutsertakan Text dalam graph yang sudah
diperluas.
Jika tidak ada siklus maka proses akan dilanjutkan sampai sebuah siklus muncul,
misalnya ada sebuah atau beberapa transaksi yang di rolledback atau di restart bersama
dengan semua perwakilan transaksinya, atau semua WFG global di bangun dan tidak
siklus yang terdeteksi.
Pada kasus ini tidak ada deadlock pada system. Obermack membuktikan jika ada
sebuah deadlock global , maka prosedur ini pada akhirnya akan menyebabkan muncul
sebuah siklus di beberapa lokasi .
Gambar 4 Pendeteksian Deadlock Terdistribusi
Tiga WFGs lokal dalam gambar 20.5 berisi siklus:
S1: Text → T3 → T1 → Text
S2: Text → T1 → T2 →Text
S3: Text → T2 → T3 →Text
Dalam contoh ini, dapat dilakukan pengiriman WFG lokal untuk lokasi S1 ke lokasi di
mana transaksi T1 sedang menunggu: yaitu lokasi S2. WFG lokal pada S2 diperluas untuk
meliputi informasi ini dan menjadi sebagai berikut:
S2: Text →T3 →T1 →T2 →Text
Ini masih berpotensi deadlock, maka dilakukan pengiriman WFG ini ke lokasi di mana
transaksi T2 sedang menunggu: yaitu lokasi S3. WGF lokal pada S3 diperluas untuk:
S3: Text →T3→ T1→ T2 →T3→ Text
WFG global ini berisi suatu siklus yang tidak melibatkan simpul Text, maka dapat
disimpulkan bahwa terdapat deadlock dan protocol recovery harus dilibatkan untuk
memperbaiki keadaan tersebut. Metode pendeteksian deadlock terdistribusi berpotensi
lebih baik dari pada terpusat atau hirarki, namun sejak tak ada satu pun lokasi berisi
semua informasi yang diperlukan untuk mendeteksi deadclock, hubung komunikasi
antar lokasi sangat di perlukan.
KESIMPULAN
Concurrency Control adalah proses pengelolaan operasi-operasi yang berjalan
bersamaan dalam database dengan tidak saling menggangu satu sama lain. Kebutuhan
Concurrency Control dalam management transaksi untuk multiuser menjadi penting,
mengingat sistem untuk multiuser memungkinkan terjadinya akses bersama terhadap
sebuah database. Akses bersama relative mudah jika seluruh user hanya membaca data,
sehingga tidak ada yang melakukan interfensi satu dengan lainnya. Akan tetapi, pada
saat dua atau lebih user mengakses database secara simultan dan paling sedikit satu
user melakukan update, maka akan terjadi interfensi yang dapat mengakibatkan
ketidakkonsistenan data pada database.
Mekanisme kontrol konkurensi yang baik untuk DBMS harus tahan terhadap
kegagalan komunikasi dan lokasi, dapat dilakukannya proses parallel untuk kebutuhan
kerja yang maksimal, menghasilkan proses komputasi yang sederhana dan media
penyimpanannya lebih efisien, memiliki kinerja yang memuaskan pada sebuah
lingkungan jaringan karena komunikasi tunda yang sangat baik, dan menempatkan
beberapa batasan pada struktur dari suatu kegiatan yang beresiko.
Disamping itu, terdapat beberapa masalah umum yang timbul dalam DBMS
sehingga dibutuhkan concurrency control. Permasalahan tersebut, yaitu Lost update
problem (Masalah hilangnya data yang diupdate), Uncommited dependency problem /
dirty real (Masalah kebergantungan terhadap transaksi yang belum commit),
Inconsistent analisys problem (masalah analisa yang tidak konsisten). Masalah pada
concurrency control didalam lingkungan terdistribusi dapat disolusikan dengan
beberapa pendekatan, yaitu Locking (Penguncian), Timestamping (Penandaan).