Minggu, 12 Oktober 2014

Testing for Serializability

Serializability adalah suatu aturan untuk menjadwalkan proses-proses transaksi yang dijalankan hampir bersamaan dengan tetap menjaga konsistensi data seolah-olah proses dari transaksi-transaksi tersebut dijalankan secara serial.

Instruksi pada operasi serializability, yaitu read dan write. Diasumsikan bahwa transaksi dapat melakukan perhitungan terhadap data dalam buffer lokal di antara instruksi read dan write.
Terdapat dua bentuk Schedule Equivalence (Ekivalensi Penjadwalan) :
  • Conflict Serializalibility 
  • View Serializability
Pada saat mendesain skema kontrol konkurensi, harus menunjukan bahwa jadwal yang dibuat oleh skema tersebut adalah serializable. Terdapat metode simpel dan efisien untuk menentukan conflict serializability dari suatu jadwal. Misalkan sebuah jadwal S. Dapat dibuat suatu grafik langsung yang diberi nama grafik preseden (presedence graph). Grafik preseden terdiri dari sepasang G = (V,E), dimana V adalah serangkaian simpul dan E adalah serangkaian tepian / busur.
Serangkaian simpul terdiri dari semua transaksi yang berperan serta di dalam penjadwalan. Serangkaian tepian / busur terdiri dari semua bentuk Ti -> Tj untuk masing-masing dari ketiga kondisi berikut :
  1. Ti eksekusi write (Q) sebelum Tj eksekusi read (Q)
  2. Ti eksekusi read (Q) sebelum Tj eksekusi write (Q)
  3. Ti eksekusi write (Q) sebelum Tj eksekusi write(Q)



Jika bentuk Ti -> Tj ada di dalam grafik preseden, maka di setiap jadwal S’ serial yang ekivalen ke jadwal S, Ti harus muncul sebelum Tj.

Tidak ada komentar:

Posting Komentar