MODIFIKASI DAN EVALUASI KINERJA ALGORITMA READ-COMMIT ORDER CONCURRENCY CONTROL (ROCC)

Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (309-323)

MODIFIKASI DAN EVALUASI KINERJA ALGORITMA READ-COMMIT ORDER CONCURRENCY CONTROL (ROCC) Sulasno*, Suratman∗, Fahren Bukhari**, Kudang Boro Seminar∗∗

ABSTRAK MODIFIKASI DAN EVALUASI KINERJA ALGORITMA READ-COMMIT ORDER CONCURRENCY CONTROL(ROCC).Concurrency control (CC) merupakan suatu mekanisme untuk mengatur eksekusi transaksi-transaksi yang terjadi dalam basis data. CC pada produk komersial menggunakan Strict Two Phase Locking (Strict 2PL)[5]. Strict 2PL masih mempunyai masalah yang disebut dengan deadlock. Read-commit Order Concurrency Control (ROCC) merupakan suatu algoritma CC baru yang diharapkan dapat memberikan kinerja yang tinggi dan memperbaharui CC yang telah ada. Namun ROCC yang telah dikembangkan masih terdapat kelemahan terutama yang berkaitan dengan masih terdapatnya restart terhadap eksekusi transaksi yang bersifat serializable. Untuk itu pada penelitian ini, telah dilakukan modifikasi algoritma validasi yang terdapat pada ROCC (ROCCM) untuk meminimalkan restart sehingga throughput dapat ditingkatkan. Evaluasi kinerja algoritma ROCC, ROCCM dan Strict 2PL, dilakukan melalui simulasi. Hasil simulasi memperlihatkan bahwa ROCCM, mempunyai throughput yang lebih baik, bila dibandingkan dengan ROCC dan Strict 2PL. Kata-kata kunci: concurrency control, kinerja, simulasi

ABSTRACT MODIFICATION AND EVALUATION OF PERFORMANCE READ-COMMIT ORDER CONCURENCY CONTROL (ROCC) ALGORITHM. Concurrency control (CC) is a mechanism to manage simultaneous operations on a database. The commercial databases use Strict Two Phase Locking (Strict 2PL) CC to maintain execution correctness[5]. Unfortunately Strict 2PL cannot meet the very high performance of a database systems, due to Strict 2PL thrashing behavior caused by blocking. The Readcommit Order Concurrency Control (ROCC) is a new method of concurrency control for high performance database systems. Unfortunately ROCC that has been developed still has weakness, it has a restart for serializable execution. Modified ROCC (ROCCM) done by reengineering validation algorithm to minimize restart to increase throughput. The porformace of ROCC, ROCCM, and Strict 2PL is analized by a simulation. Our simulation result shows that ROCCM produces much higher system throughput compared with ROCC, and Strict 2PL. Keywords: concurrency control, performance, simulation

∗

Pusat Pengembangan Informatika Nuklir - BATAN Dosen Tetap Magister Sains Ilmu Komputer, FMIPA, IPB

∗∗

309


PENDAHULUAN Penggunaan sistem informasi, diperlukan untuk mengolah data menjadi informasi yang bermanfaat. Demikian juga penggunaan sistem informasi dalam bidang teknologi nuklir seperti di BATAN, dapat digunakan untuk mengolah data seperti data perpustakaan, data hasil-hasil penelitian, mupun data operasional lainnya menjadi informasi yang diperlukan oleh para pengguna. Pada era internet dewasa ini, sistem informasi sebagian besar telah berubah dari model stand alone menjadi sistem informasi yang berbasis web yang dapat diakses oleh banyak pengguna. Sebagai contoh sistem informasi perpustakaan, jika telah berubah menjadi sistem informasi yang berbasis web yang diletakkan pada media internet atau intranet, maka dapat diakses oleh para pengguna secara bersamaan. Akses data oleh pengguna dapat merupakan suatu akses membaca data (transaksi read), maupun akses untuk menulis data (transaksi write) yang dilakukan melalui basis data dalam sistem informasi yang digunakan. Pada basis data dengan pengguna tunggal (single user), eksekusi transaksi dapat dilakukan tanpa ada gangguan dari pengguna lain. Namun pada basis data dengan pengguna banyak (multiuser), transaksi harus dapat dieksekusi secara bersamaan dan konflik antar transaksi yang terjadi harus dapat diatasi. Konflik antar transaksi terjadi jika dua atau lebih transaksi mangakses item data yang sama, dan paling sedikit satu dari operasi transaksi tersebut adalah operasi write. Concurrency control (CC) merupakan suatu mekanisme untuk mengatur eksekusi transaksi-transaksi yang terjadi dalam basis data. Menurut Shi dan Perrizo[5], CC yang telah banyak dipakai pada produk komersial, adalah Strict Two Phase Locking (Strict 2PL). Pada Strict 2PL setiap transaksi harus mendapatkan kunci dari item data yang ingin diakses, dan pelepasan kembali semua kunci dilakukan secara bersamaan, apabila semua operasi read atau write pada transaksi tersebut selesai dilakukan. Pada Strict 2PL masih terdapat masalah yang disebut dengan deadlock yaitu suatu kondisi yang terjadi, jika ada dua atau lebih transaksi saling menunggu dan saling memblokir. Shi dan Perrizo[5], telah mengembangkan CC optimistic baru yaitu Readcommit Order Concurrency Control (ROCC) yang diharapkan dapat memperbaharui CC yang telah ada. Namun ROCC yang telah dikembangkan masih terdapat kelemahan terutama yang berkaitan dengan masih terdapatnya restart (eksekusi transaksi yang dihentikan untuk kemudian diproses ulang) terhadap eksekusi transaksi yang bersifat serializable. Untuk itu maka pada penelitian ini, telah dilakukan modifikasi algoritma ROCC serta evaluasi kinerja algoritma ROCC, algoritma ROCC yang telah dimodifikasi (ROCCM) dan Strict 2PL melalui simulasi. Penelitian ini bertujuan untuk melakukan modifikasi algoritma ROCC, serta melakukan evaluasi kinerja. Modifikasi algoritma ROCC, hanya dilakukan terhadap masalah restart, yaitu masih terdapatnya masalah tersebut yang seharusnya tidak

310


dilakukan terhadap eksekusi transaksi yang serializable. Evaluasi kinerja dilakukan melalui simulator yang diterapkan pada basis data terpusat terhadap algoritma ROCCM, ROCC, maupun Strict 2PL.

ALGORITMA CONCURRENCY CONTROL (CC) Strict Two Phase Locking (Strict 2PL) Strict 2PL merupakan CC yang menggunakan mekanisme lock. Menurut Elmasri dan Navathe[3], pada mekanisme CC menggunakan cara ini, suatu transaksi selama eksekusi akan melakukan permintaan lock suatu item data terlebih dahulu, untuk kemudian mengakses atau memodifikasi data. Pada akhir eksekusi, transaksi melepas semua lock untuk semua item data secara bersamaan. Grafik Strict 2PL diperlihatkan pada Gambar 1. Locking Release

Execution

Gambar 1 Grafik Strict 2PL[3]. Dari Gambar 1 dapat dijelaskan bahwa release adalah pelepasan lock untuk suatu item data, locking adalah permintaan lock untuk suatu item data, execution adalah operasi pada basis data (read atau write). Jika suatu transaksi tidak mendapatkan lock suatu item data, pada saat permintaan lock, maka transaksi tersebut akan menunggu (blocked) sampai item data tersebut bebas dari lock.

Read-Commit Order Concurrency Control (ROCC) Pada ROCC, suatu transaksi boleh mengirim lebih dari satu access request message yang berisi satu atau lebih operasi akses. Ketika sebuah request message datang, maka elemen baru yang berhubungan dengan informasi dari request message tersebut, akan dibangkitkan dalam RC-queue. RC-queue mempunyai elemen yang terdiri dari tujuh field yaitu : Tid, validated (V), commit (C), restart (R), read, write, dan next, yang diperlihatkan pada Gambar 2. Tid berisi id dari transaksi. Read berisi nilai item data yang dibaca. Write

311


berisi nilai item data yang ditulis. Validated field bernilai 1, jika suatu transaksi tidak memerlukan validasi atau telah sukses dari proses validasi, dan bernilai 0 jika suatu transaksi memerlukan proses validasi atau belum dilakukan validasi. Jika commit field bernilai 1, mengindikasikan bahwa request message tersebut bertipe commit, dan bernilai 0 jika request message tersebut bukan bertipe commit. Restart field akan bernilai 1, jika transaksi tersebut merupakan transaksi yang mengalami restart, dan bernilai 0 jika transaksi tersebut bukan atau belum mengalami restart. Next pointer akan menunjuk ke elemen berikutnya yang merepresentasikan bahwa elemen tersebut datang sebelumnya. Pointer pada elemen yang datang pertama kali di set ke NULL. Tid

V

C

R

Reads

Writes

Next

Gambar 2 Format elemen RC-queue[5]. Proses validasi pada algoritma ROCC dimulai ketika ada request message yang datang bertipe commit. Proses penelusuran untuk mencari elemen yang operasinya konflik pada queue, dimulai dari elemen read pertama dari transaksi yang sedang dilakukan validasi (First) yang dibandingkan dengan elemen lain yang terletak diantara First sampai elemen dari transaksi yang sama berikutnya (first-down reached element). Apabila penelusuran dari elemen First tidak menemukan operasi elemen yang konflik (read-write, write-read, write-write), sampai ditemukan first-down reached element, maka First akan digabungkan dengan first-down reached element. Gabungan kedua elemen tersebut, dianggap sebagai First yang baru. Jika first-down reached element yang ditemukan adalah elemen commit dari transaksi yang sama, maka proses validasi dianggap sukses. Tetapi apabila yang ditemukan bukan elemen commit dari transaksi yang sama, maka proses penelusuran dilakukan terus untuk menemukan elemen yang operasinya konflik sampai ditemukan first-down reached element berikutnya. Apabila penelusuran dari elemen First menemukan operasi elemen yang konflik, maka First dipindahkan ke posisi sebelum elemen dari transaksi lain yang konflik, kemudian First yang asli akan dihapus dari RC-queue. Proses penelusuran selanjutnya dimulai dari elemen commit, untuk mencari elemen dari transaksi lain yang operasinya konflik dengan elemen commit (Second) sampai ditemukan elemen dari transaksi yang sama (first-up reached element). Apabila pada saat penelusuran dari Second tidak menemukan elemen yang konflik sampai ditemukan first-up reached element, maka Second akan digabungkan dengan first-up reached element. Gabungan kedua elemen tersebut dianggap sabagai Second yang baru. Apabila first-up reached element adalah First maka proses validasi dianggap sukses. Tetapi jika bukan First, maka Second akan dibandingkan terus sampai menemukan first-up reached element berikutnya. Apabila pada saat

312


penelusuran ditemukan operasi elemen yang konflik maka proses validasi dianggap gagal sehingga transaksi tersebut akan di restart. Pseudocode algoritma validasi intervening pada ROCC, diuraikan dalam penjelasan di bawah ini[5]. Sebagai inisial First = NULL, dan Second = NULL. Algoritma tersebut dieksekusi apabila request message yang datang bertipe commit. Pseudocode algoritma selengkapnya yaitu : “First” = NULL; “Second” =NULL; Locate the transaction’s first read element in the RC-queue; If (not found) return validated =true; “First” = the first read element; While (1) { Compare “First” with all the elements of other transaction behind it until it reached an element of the same transaction (first-down-reached element); If (There is no element conflict) //moving down to look for upper side conflict { Merge the “First” element with the first-down-reached elemet; Remove the “First” element from the RC-Queue; If ( The first-down-reached element is the commit element) Return validated = true; Else “First” = the first-down-reached-element; } Else // There is uper_sided_conflict; { Insert “First” into the RC-queue right before the conflicting element; Remove the original “First” from the RC-queue; “Second” = Commit element; While (1) //moving up to look for the lower-sided conflict; {Compare “Second” with all the element of other transactions before it until it reaches an element of the same transaction (first-up-reached element); If (there is no element conflict) { Merge the “Second” element to the first-up-reached element; Remove the “Second“element from the RC-queue; If (the first-up-reched element is the first) Return validated=true; Else “Second” = first-up-reached element; } Else // there is also Lower-sided-conflict, the validation fails. { Remove all elements of the transaction from the RC-queue Return validated= false; } } } }

313


METODE PENELITIAN

Metode Modifikasi Algoritma ROCC Bernstein et al.[2] menjelaskan cara untuk mengenali himpunan transaksi yang dieksekusi (history) yang serializable. Jika sebuah history H dengan transaksi T={T1, T2, …Tn} maka serialization graph (SG) dari history H (SG(H)) adalah directed graph dengan node adalah transaksi-transaksi dalam T, yang sudah melakukan commit dalam H. Edge adalah Ti Tj jika salah satu dari operasi-operasi Ti konflik dengan salah satu dari operasi-operasi Tj dalam H, dan Ti dieksekusi lebih awal dari Tj. Sebuah history H adalah serializable, jika SG(H) adalah acyclic. Modifikasi algoritma ROCC dilakukan dengan cara terlebih dahulu membuat SG dari beberapa kondisi RC-queue, sehingga ditemukan keadaan dimana terdapat SG yang acyclic tetapi algoritma validasi intervening melakukan restart.

Metode Evaluasi Kinerja Penelitian untuk mengukur kinerja ROCC, ROCCM, dan Strict 2PL dilakukan dengan simulasi yang berbasis pada Shi dan Perrizo[5]. Pelaksanaan simulasi dilakukan dengan menggunakan simulator. Simulator dibangun dengan pendekatan client-server menggunakan bahasa pemrograman C Builder Version 6.0 dengan cara melakukan modifikasi program simulator dari penelitian sebelumnya yang dilakukan oleh Shi dan Perrizo[5]. Sedangkan spesifikasi komputer yang digunakan pada pelaksanaan simulasi, menggunakan sistem operasi Windows XP, memori 256 Mbyte, prosessor Intel Pentium 4 2.66 GHz, serta hardisk 40 Gbyte. Hasil simulasi yang tampil adalah throughput, response time, dan restart ratio untuk ketiga algoritma yang dievaluasi. Throughput dalam hal ini adalah jumlah transaksi yang dapat diselesaikan per satuan waktu. Restart ratio adalah jumlah ratarata transaksi yang mengalami restart per satuan waktu. Respon time adalah waktu di antara ketika sebuah terminal mengirim sebuah transaksi baru dan ketika hasil transaksi baru tersebut dikembalikan ke terminal. Throughput hasil simulasi diuji dengan uji t-student menggunakan selang kepercayaan (confidence interval) 95% [4].

314


HASIL DAN PEMBAHASAN Algoritma ROCCM Teorema yang dikemukakan oleh Shi dan Perrizo[5], mengungkapkan bahwa ROCC menghasilkan eksekusi transaksi yang serializable. Karena jika terdapat eksekusi yang tidak serializable, maka ada cycle serialization graph (SG) pada RCqueue. Sebagai asumsi terdapat sebuah cycle dalam RC-queue yang terdiri dari T1T2…TnT1, maka dalam transaksi tersebut, terdapat konflik antara T1 dan T2 serta terdapat konflik antara Tn dan T1. Algoritma validasi intervening yang terdapat pada ROCC, akan membatalkan transaksi yang mempunyai dua elemen yang keduanya konflik dengan elemen intervening dari transaksi lain. Maka dengan demikian, cycle akan dihentikan, karena transaksi yang dibatalkan akan dilakukan restart. T1

0

0

0

T2

1

1

0

T3

0

0

0

x,y,z x z NULL

T1

0

1

0

z

Gambar 3. RC-queue dengan eksekusi serializable pada ROCC. T3

T1

T2

Gambar 4. Acyclic SG Dari hasil penelitian yang telah dilakukan, terdapat keadaan RC-queue yang serializable, tetapi mengalami restart pada saat dilakukan proses validasi oleh ROCC, seperti yang diilustrasikan pada Gambar 3. Proses validasi pada Gambar 3, dimulai dari first dimana dalam hal ini menemukan elemen konflik yaitu item data x dari operasi w2(x) pada transaksi T2. Proses validasi selanjutnya dimulai dari bawah dengan membandingkan elemen commit dengan transaksi sebelumnya, yang dalam hal ini menemukan elemen konflik, yaitu operasi read untuk item data z transaksi T3 (r3(z)). Pada kondisi ini transaksi T1 mengalami restart, padahal eksekusi transaksi adalah merupakan eksekusi yang serializable, yang serupa dengan SG Gambar 4.

315


Modifikasi algoritma ROCC menjadi ROCCM, dilakukan dengan mengubah cara validasi yang dilakukan oleh algoritma validasi intervening yang akan diuraikan dalam penjelasan di bawah ini. First adalah elemen operasi read dari transaksi yang melakukan commit. Combine adalah kumpulan elemen yang operasinya konflik dengan elemen commit (Second) maupun operasinya konflik dengan elemen Combine sebelumnya. Sebagai inisialisasi awal Combine = 0. Langkah melakukan validasi setelah suatu transaksi mengirimkan commit request, pada ROCCM selengkapnya adalah sebagai berikut : 1. Bandingkan First dengan elemen dari transaksi lain yang terdapat diantara First sampai elemen commit. Bila pada saat penelusuran menemukan elemen read dari transaksi yang sama (first-down reached element) maka gabungkan elemen First ke dalam elemen transaksi yang sama berikutnya. Kemudian bandingkan First hasil gabungan tersebut, dengan elemen dari transaksi lain yang terdapat diantara First sampai elemen commit. Proses penelusuran dilakukan terus untuk menemukan elemen yang konflik atau elemen read berikutnya. Bila transaksi berikutnya yang ditemukan, adalah elemen commit dari transaksi yang sama, dan tidak terdapat konflik maka validasi dinyatakan sukses. 2. Jika First konflik dengan elemen dari transaksi lain, pindahkan elemen First ke posisi transaksi sebelum elemen dari transaksi lain yang konflik. Hapus elemen First yang asli dari RC-queue. 3. Bandingkan Second atau Combine dengan elemen dari transaksi lain yang terdapat diantara Second sampai ditemukan elemen dari transaksi yang sama (First up reached element). Setiap elemen yang konflik, lakukan insert ke Combine. 4. Bandingkan Combine dengan First up reached element Jika terdapat konflik maka validasi dinyatakan gagal. Jika tidak terdapat konflik lakukan pengecekan apakah First up reached element adalah First, jika merupakan First maka validasi dinyatakan sukses, tetapi jika bukan elemen First lanjutkan langkah 5. 5. Gabungkan Second dengan First up reached element hapus Second asli dari RC-queue. Lanjutkan langkah 3. Pseudocode algoritma selengkapnya adalah sebagai berikut:

316


“First” = NULL; “Second” =NULL;”Combine”=NULL; Locate the transaction’s first read element in the RC-queue; If (not found) return validated =true; “First” = the first read element; While (1) { Compare “First” with all the elements of other transaction behind it until it reached an element of the same transaction (first-down-reached element); If (There is no element conflict) //moving down to look for upper side conflict {Merge the “First” element with the first-down-reached elemet; Remove the “First” element from the RC-Queue; If ( The first-down-reached element is the commit element) Return validated = true; Else “First” = the first-down-reached-element; } Else // There is uper_sided_conflict; {Insert “First” into the RC-queue right before the conflicting element; Remove the original “First” from the RC-queue; “Second” = Commit element; While (1) //moving up to look for the lower-sided conflict; {Compare “Second” with all the element of other transactions before it until it reaches an element of the same transaction (first-up-reached element); Insert element conflict with “Second” or Combine” to “Combine; {Compare first-up-reached element” with “Combine”; If (There is no element conflict) {Merge the “Second” element with the first-up-reached element; Remove the “Second” element from the RC-queue; If (The first-up-reached element is the “First”) Return validated = true; Else “Second” = the first-up-reached element; } Else // there is also Lower-sided-conflict, the validation fails. { Remove all elements of the transaction from the RC-queue Return validated= false; } } } } }

317


Proses Pelaksanaan Simulasi Proses pelaksanaan simulasi dilakukan dengan simulator. Pada Gambar 5 ditunjukkan model simulator umum untuk ROCC, ROCCM, dan Strict 2PL. Garis putus-putus menuju block queue hanya digunakan pada Strict 2PL. Pada simulator diasumsikan terdapat sejumlah terminal, untuk membangkitkan transaksi dan batasan transaksi yang aktif pada suatu saat, di dalam sistem (mpl). Apabila transaksi yang dibangkitkan melebihi mpl, maka transaksi tersebut diletakkan dalam ready queue untuk menunggu transaksi dalam sistem selesai atau ada yang dilakukan abort. Sebaliknya apabila transaksi yang aktif dalam sistem tidak melebihi mpl, maka transaksi tersebut masuk ke cc queue dan membuat permintaan operasi akses basis data melalui CC. Jika lolos dari CC, selanjutnya transaksi tersebut mengakses data. Jika transaksi tersebut merupakan transaksi read dan data tersebut ada di buffer maka eksekusi dilanjutkan ke CPU. Tetapi jika merupakan transaksi write atau transaksi read yang datanya tidak terdapat di buffer, maka eksekusi akan dilewatkan ke disk untuk mengakses data untuk seterusnya dilanjutkan ke CPU. termin

ready queue

RESTA cc

COMM

cc

think

blocked object queue

cpu

ready queue

cpu

ACCE Yes

blocked object cpu cpu

Gambar 5.

disk queue disk COM

cc blocke d

Is in Buffer?

No

disk

RESTA cc

think

ACCES Yes

termi

blocke d

Is in Buffer?

No

disk disk queue disk

Model logical queuing untuk ROCCM, ROCC dan Strict 2PL pada simulator [5].

318


Diasumsikan juga sebuah transaksi melakukan operasi read terlebih dahulu dan jaringan Local Area Network (LAN) dalam keadaan handal pada saat transmisi data. Jalur think memberikan nilai random delay pada waktu mengakses item data. Pada Strict 2PL, jika hasil dari CC memutuskan bahwa suatu transaksi harus di block maka transaksi tersebut dimasukkan dalam block queue sampai permintaan akses data dapat diproses. Nilai parameter input default dapat dilihat pada Tabel 1 di bawah ini.

Tabel 1. Nilai parameter input default pada saat percobaan No 1 2

Parameter db_size max_trans

3

min_trans

4

write_prob

5

int_think

6

ext-think

7 8 9

max_req mean_time commit_nu m hit_ratio obj_io obj_cpu num_cpu num_disk mpl

10 11 12 13 14 15

Arti Ukuran dari basis data Jumlah maksimum objek yang dibaca sebuah transaksi Jumlah minimum objek yang dibaca untuk sebuah transaksi Probabilitas objek yang dibaca dari suatu transaksi yang juga akan ditulis Mean intra-transaction think time diantara dua request dari sebuah transaksi Mean time delay diantara selesainya suatu transaksi dan inisialisasi transaksi baru dari suatu terminal. Jumlah request maksimum dari suatu transaksi Rata-rata berapa kali melakukan ulangan Jumlah transaksi yang commit selama simulasi Perbandingan jumlah data di buffer dan di disk Waktu disk untuk akses sebuah objek Waktu CPU untuk akses sebuah objek Jumlah CPU Jumlah disk Multiprogramming level

Nilai 1000 pages 10 pages 4 pages 0,25 1 ms 1 ms

3 5 800 0,5 35 ms 15 ms 4 8 5,10,25,50, 75,100,200

319


HASIL SIMULASI Pada Gambar 6.a ditunjukkan throughput hasil simulasi, yang memperlihatkan bahwa ROCCM mempunyai nilai yang lebih tinggi, bila dibandingkan dengan algoritma ROCC dan Strict 2PL. Uji t-student pada sample dengan derajat bebas (df) = (n1+n2-2) yang memiliki rata-rata x dan y, serta variance s12 dan s22 dihitung dengan persamaan di bawah ini: 2

t ( n1 + n2 − 2 )

2

s s = x− y/ 1 + 1 n n

Pada pengujian dengan menggunakan derajat bebas 8 (5 + 5 -2) dan 95 % confidence interval, jika -1.86 < t < 1.86 maka perbedaan tidak nyata. Hasil pengujian dengan uji t-student menunjukkan bahwa perbedaan throughput antara ROCC dan ROCCM, cukup nyata pada mpl di atas 50. Dari Gambar 6.a juga dapat diketahui bahwa throughput Strict 2PL ada pada posisi terendah. Hasil simulasi pada restart ratio, dapat dilihat pada Gambar 6.b maupun Tabel 2. Gambar 6.b memperlihatkan perbedaan restart ratio ketiga algoritma yang diuji. Dari gambar tersebut, dapat diketahui bahwa restart ratio ROCC berada pada posisi tertinggi terutama pada mpl = 200.

(a)

(b)

Gambar 6 Hasil simulasi: (a) throughput, (b) restart ratio, (c) response time

320


(c) Gambar 6.c, memperlihatkan hasil simulasi dalam hal response time Melalui gambar tersebut, dapat diketahui bahwa response time antara ROCCM dan ROCC, secara umum hampir sama pada berbagai mpl. Pada Tabel 2, ditunjukkan rekapitulasi kinerja algoritma pada throughput, restart ratio dan response time. Pada tabel tersebut T adalah throughput, RR adalah response time, dan RT adalah restart ratio. Tabel 2. Rekapitulasi hasil simulasi ROCC, ROCCM, dan Strict 2PL MPL 10 30 50 75 100 150 200

T 6.37 17.70 27.29 31.78 32.51 32.34 33.14

ROCCM RR RT 0.02 49.91 0.04 17.52 0.07 11.33 0.11 9.60 0.12 9.12 0.22 8.98 0.24 8.43

T 6.27 17.58 26.27 30.27 30.88 27.04 24.55

ROCC RR 0.02 0.06 0.11 0.16 0.24 0.47 0.70

RT 50.75 17.58 11.53 9.84 9.56 10.10 10.32

T 5.62 10.48 9.23 7.82 6.06 5.04 4.90

Strict 2PL RR 0.00 0.01 0.02 0.05 0.11 0.25 0.40

RT 57.24 30.88 34.99 41.22 49.37 56.91 56.94

Evalusi kinerja Algoritma Bargava[1] mengemukakan bahwa salah satu cara untuk melakukan evaluasi terhadap kinerja sebuah algoritma CC adalah dengan melakukan evaluasi terhadap throughput, response time, dan restart ratio. Dari hasil simulasi yang ditampilkan pada eksperimen ini, dapat jelaskan bahwa algoritma ROCCM mempunyai troughput yang lebih tinggi. Sementara itu restart ratio berada di bawah ROCC. Selain itu

321


ROCCM mempunyai response time yang hampir sama dengan ROCC. Throughput ROCC secara umum berada tepat di bawah ROCCM. Sementara itu ROCC mempunyai angka restart ratio yang lebih tinggi. Dari hasil penelitian yang telah dilakukan dapat dikemukakan bahwa angka response time ROCC hampir sama dengan ROCCM yang mempunyai response time lebih cepat bila dibandingkan dengan Strict 2PL. Selanjutnya, Strict 2PL mempunyai throughput yang lebih rendah bila dibandingkan dengan ROCCM dan ROCC. Restart ratio pada algoritma ini cukup rendah.

KESIMPULAN Melalui penelitian modifikasi dan evaluasi kinerja algoritma ROCC dapat disimpulkan bahwa secara umum throughput ROCCM lebih tinggi, bila dibandingkan dengan ROCC dan Strict 2PL. Dengan melakukan modifikasi algoritma ROCC, restart ratio yang terjadi akan berkurang sehingga menaikkan kinerja algoritma tersebut.

DAFTAR PUSTAKA 1. BARGAVA B, Concurrency Control in Database Systems, IEEE Transaction on Knowledge and Data Engineering, 11 (1999) 3-16. http ://citeseer.ist.psu.edu/bhargava99concurrency.html. [ 28 Oktober 2005]. 2. BERNSTEIN PA, HADZILACOS V, GOODMAN N, Concurrency Control and Recovery in Database Syste,. New York: Addison-Wesley Publishing Company, (1987) 25-37. 3. ELMASRI R, NAVATHE S B, Fundamental of Database Systems. New York Addison -Wesley Publishing Company, (2000) 662–668. 4. LAW AM, KELTON WD, Simulation Modelling and Analysis. 2. Singapore: McGraw-Hill Inc, (1991), 289.

5. SHI VTS, PERRIZO W, Read-commit Order for Concurrency Control in centralized High Performance Database Systems, Information Journal of International Information Insitute, 7 (2004) 95-106. 6. SHI VTS. Read-commit Order Concurrency Control Method for High Performance Database Systems (ROCC). http://www.cs.ndsu.nodak.edu/~vshi/. [26 April 2006].

322


DAFTAR RIWAYAT HIDUP

1.

Nama

: Sulasno

2.

Tempat/Tanggal Lahir

: Kebumen, 20 Mei 1967

3.

Instansi

: PPIN-BATAN

4.

Pekerjaan / Jabatan

: Ka. Sub. Bidang Sistem Komputer

5.

Riwayat Pendidikan

:

• S2 Magister Ilmu Komputer, FMIPA - IPB 6.

Pengalaman Kerja

:

• 1990 – 1997 di PRSG - BATAN • 1997 – Sekarang di PPIN - BATAN 7. Makalah yang pernah disajikan : • Disain Replikasi data master slave • Perancangan model cyber mail untuk e-commerce • Domain Name system (ANS) Intranet

323

MODIFIKASI DAN EVALUASI KINERJA ALGORITMA READ-COMMIT ORDER CONCURRENCY CONTROL (ROCC)

Recommend Documents