,
*
I
-.
d
PERBAIKAN DAN EVALUASI KINERJA ALGORITMA
READ-COMMIT ORDER CONCURRENCY CONTROL (ROCC)
SULASNO
PROGRAM PASCASARJANA TNSTITUT PERTANIAN BOGOR BOGOR 2006
1
SURAT PERNYATAAN Dengan ini menyatakan bahwa tesis saya yang berjudul : Perbaikan dan Evalusi Kinerja Algoritma Rend-commit Order Concurrency Control (ROCC) adalah merupakan hasil karya saya sendiri dan belum pernah dipublikasikan. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupuil tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam daftar pustaka di bagian akhir tesis ini.
Bogor, Pebruari 2006
ABSTRAK SULASNO. Perbaikan dan Evaluasi Kinerja Algoritma Read-comnzit Order
Concurrency Control (ROCC). Dibiinbing ole11 FAHREN BUKHAFU dan KUDANG BORO SEMINAR.
Concurrency control (CC) inerupakan suatu mekanisme untuk mengatur eksekusi transaksi-transaksi yang terjadi dalam basis data. CC pada produk komersial menggunakan Strict Two Phase Locking (Strict 2PL). Strict 2PL masih mempunyai masalah yang disebut dengan deadlock.
Read-com~izitOrder Concunency Control (ROCC) merupakan suatu CC baru yang diharapkan dapat ~nemberikankinerja yang tinggi dan memperbaharui CC yang telah ada. Namun ROCC yang telah dikembangkan masih terdzpat kelemahan terutama yang berkaitan dengan masih terdapatnya
restart terhadap eksekusi
transaksi yang bersifat seriulizable. Untuk itu pada penelitian ini, teIah dilakukan perbaikan algoritma ROCC (ROCCM), serta evaluasi kinerja algoritma ROCC,
ROCCM dan Strict ZPL, melalui simulasi. Hasil simulasi memperlihatkan bahwa ROCCM, mempunyai throughput yang lebih baik, bila dibandingkan dengan ROCC dan Strict 2PL. Melalui perbaikan algoritma validasi intervening yang terdapat pada ROCC, inaka dihasilkan algoritma
ROCCM yang mempunyai kinerja lebih baik. Kata kunci : program peilgendali konkurensi, kinerja, simulasi.
ABSTRACT SULASNO. Revision and evaluation of performance Read-commit Order Concurrency Control (ROCC) algorithm. Supervised by FAHREN BUKHARI and KUDANG BORO SEMINAR. 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. Unfortunately Strict 2PL cannot meet a very high performance of a database system, due to Strict 2PL thrashing behavior caused by blocking. The Read-commit Order Concurrency Control (ROCC) is a new method of CC for high performance database systems. Unfortunately ROCC that has been developed still has weakness, it has a restart for serializable execution. Modified ROCC (ROCCM) is done by reengineering validation algorithm to minimize restart to increase throughput. The
performance of ROCC, ROCCM, and Strict 2PL is analized by a
simulation program. Our simulation result shows that ROCCM produces much higher system throughput compared with ROCC, and Strict 2PL. Key words : concurrency control, performance, simulation.
OHak cipta milik Sulasno, tahun 2006 Hak cipta dilindungi Dilarang rnengutip dun menzperbanyak tanpa ijin tertulis dari Institut Perlanian Bogor, sebigian atau seluruhnya dalam benttik apaptln, baik cetak, fotokopi, microfilm, dan sebagainya
v
PERBAIKAN DAN EVALUASI KINERJA ALGORITMA READ-COMMIT ORDER CONCURRENCY CONTROL
(ROCC)
SULASNO
Tesis Sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Program Studi Ilmu Komputer
PROGRAM PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2006
Judul
: Perbaikan dan Evaluasi Kinerja Algoritma
Rearl-comnzit Order Coitcr~rrencyControl (ROCC) Nama
:Sulasno
NIM
: G651024074
Disetujui, Konlisi Pembimbing
Ir. Fahren Bukhari, M.Sc. Anggota
Ketua
Diketahui,
frida Manuwoto, M.Sc.
Tanggal Ujian : 3 Maret 2006
Tanggal Lulus : 1 3 APR 2006
vii
PRAKATA Puji dan Syukur Penulis panjatkan ke Hadirat Allah SWT atas segala karunia-Nya sehingga karya ilmiah ini berhasil diselesaikan. Tema yang dipilih dalam penelitian yang dilaksanakan sejak bulan Agustus 2004 ini ialah algoritma concurrency control dengan judul : "Perbaikan dan Evaluasi Kineja Algoritma Read-commit Order Concurrency Control (ROCC)". Terima kasih penulis ucapkan kepada Bapak Ir. Fahren Bukhari, M.Sc. dan Bapak Dr. Ir. Kudang Boro Seminar, M.Sc. yang telah banyak memberi saran. Disamping itu penghargaan disampaikan kepada seluruh staf Bidang Sistem dan Jaringan Komputer, Pusat Pengembangan Informatika Nuklir, Badan Tenaga Nuklir Nasional Jakarta, yang telah banyak memberikan semangat dalam melakukan penelitian ini. Ucapan terima kasih juga disampaikan kepada rekan-rekan mahasiswa program pascasarjana ilmu komputer IPB, terutama angkatan kedua yang telah memberikan kerjasama yang baik selama mengikuti kuliah sampai dengan penyusunan tesis ini. Akhirnya ucapan teriina kasih disampaikan kepada istri tercinta dan putralputriku atas segala doa dan dukungannya. Semoga karya ilmiah ini bermanfaat. Bogor, Pebruari 2006 Sulasno
DAFTAR RIWAYAT HIDUP Penulis dilahirkan di Kebumen Jawa Tengah pada tanggal 20 Mei 1967 sebagai anak ke empat dari pasangan Amad Kasim dan Ibu Khosiyah (Alm). Pendidikan Sarjana ditempuh dari Jurusan Teknik Informatika Universitas Budi L u h u Jakarta, lulus pada tahun 1996. Kesempatan untuk n~elanjutkanprogram Pascasarjana pada program studi Ilmu Kon~puter,FMIPA, IPB, diperoleh pada tahun 2002 dengan biaya sendiri. Penulis bekerja di Pusat Pengembangan Informatika Nuklir, Badan Tenaga Nuklir Nasional (BATAN) Jakarta sejak tahun 1990. Tanggung jawab yang dipegang meliputi pengeinbangan dan pengelolan sistem komputer untuk server (hardware dan
sofma~.e),baik untuk jaringan LAN maupun untuk website.
DAFTAR IS1
Halaman DAFTAR TABEL ....................................................................
xi
DAFTAR GAMBAR .................................................................
xii
DAFTAR LAMPIRAN ..............................................................
xu1
I . PENDAHULUAN ..................................................................
...
1
I.1. Latar Belakang.........................................................
..
1.2 Tujuan Penelltian ......................................................
2
1.3. Ruang Linglup .........................................................
2
I1. TINJAUAN PUSTAKA ......................................................... 11.1. Basis Data dan Dalabase Manageirzent System (DBMS) ........ 11.2. Sistem Basis Data ..................................................... 113. Transaksi ................................................................ ..
11.4. Serializabzlzly.......................................................... 11.5. Conczrrrency Conll.01 (CC) .......................................... IL6 . Two Phase Locking (2PL) ........................................... 11.7. Strict Two Phase Locking (Strict 2PL) ............................ 11.8. Read-conznzit Order Concurrel~cyControl (ROCC) ............ 111. METODE PENELITIAN .......................................................
15
111.1. Metode Perbaikan Algoritma ROCC ..............................
15
111.2. Metode Evaluasi Kinerja .............................................
15
IV. HASIL DAN PEMBAHASAN.. .............................................. IV.1. Algoritina ROCCM.. .............,. ................................ IV.2. Pelaltsailaan Simulasi.. .............................................. .
.
IV.3. I-Ias~lS~~uulasi. ....................................................... IV.4. Evaluasi Kineqja Algorit~na........................................
V. KESIMPULAN ....................................................................
V. 1. Kesimpula~............................................................ V.2. Saran ....................................................................
DAFTAR PUSTAKA.. ..............................................................
DAFTAR TABEL Halaman Tabel 1. Ko~npatibilitasmodus lock ...............................................
7
Tabel 2 . Parameter-parameter input simulasi ....................................
16
Tabel 3 . Nilai parameter input default pada pelaksanaan simulasi ............
26
Tabel 4 . Rekapitulasi hasil simulasi ...............................................
29
DAFTAR GAMBAR
Gambar 1. Komponen sistenl basis data terpusat .............................. Gambar 2 . Contoh eksekusi transaksi secara serial ........................... Gainbar 3 . Coiltoh eksekusi transaksi secara seriulizable .................... Ganlbar 4 . Grafik Strict 2PL .................................................... Gambar 5 . Contoh eksekusi transaksi pada Strict 2PL ...................... Gainbar 6 . Contoh deadlockpada Strict 2PL .................................. Gambar 7. Format elen~enRC-queue ........................................... Ga~nbar8 . RC-queue pada ROCC .............................................. Gan~bar9. Komponen ROCC ................................................... Ganlbar 10. RC-queue dengan eksekusi serializuble pada ROCC ........... Gambar 11. Acyclic SG............................................................ Gambar 12. RC-queue pada algoritma ROCCM .............................. Gambar 13. Model logical queuing untuk ROCC dan ROCCM pada simulator .............................................................. Gambar 14. Model logical queuing untuk Strict 2PL pada simulator ......
. .
Gainbar 15. Has11 snnulasi ........................................................
DAFTAR LAMPIRAN
Halaman La~npiran1. Hasil uji t-student perbedaan throughput algoritma ROCC dan ROCCM ...........................................................
32
Lanlpiran 2 . Listing program roccm.cpp ...........................................
33
La~llpiran3 . Listing program roccn1.h .............................................
47
Latnpiran 4 . Listing program rocc.cpp .............................................
49
Lanlpiran 5 . Listing program r0cc.h .................................................
62
1.1. L a t a r Belakang Transaksi dalam suatu sistem basis data merupakan sekumpulan operasi read dan write. Operasi read digunakan untuk membaca data, sedangkan write merupakan operasi menulis atau mengubah data. Pada basis data dengan pengguna tunggal (single tlser), eksekusi transaksi dapat dilakukan tanpa ada gangguan dari pengguna lain. Na~nunpada basis data dengan pengguna banyak
(iizulti-user),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 (Connoly et al. 2002). Secara umum mekanisme CC dibagi ~nenjadi2 jenis
yaitu
optimistic dan
pessinzistic (Ozsu & Valduriez 1999). Optiiizistic ~nengasumsikanbahwa konflik antar transaksi jarang terjadi, sehingga mengijinkan transaksi-transaksi yang datang dapat langsung diproses tanpa harus nienunggu validasi terlebih dahulu.
Pessinzistic mengasumsikan bahwa konflik antar transaksi sering terjadi, karena itu setiap transaksi harus melalui validasi terlebih dahulu. Dengan adanya CC, diharapkan eksekusi transaksi-transaksi yang ada dalam basis data dapat dikelola, sehingga konsistensi basis data dapat tetap terjaga. Menurut Shi dan Perrizo (2004), CC yang telah banyak digunakan pada produk komersial adalah Two Phase Locking (2PL). 2PL merupakan jenis CC yang
pessinzistic. Pada 2PL setiap transaksi harus mendapatkan kunci (lock) untuk item data yang ingin diakses, dan melepas kembali kunci tersebut apabila transaksi selesai dilakukan. Dengan demikian sebuah item data tidak dapat diakses oleh suatu transaksi, jika item data tersebut telah dikunci oleh transaksi lain. Salah satu jenis dari 2PL yang telah banyak digunakan adalab Stricf 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
2 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 (2004), telah mengembangkan C C optinzistic baru yaitu Read-
conzmit Order Concurrency Control (ROCC) yang diharapkan dapat memperbaharui C C yang telah ada. Namun R O C C 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, akan dilakukan perbaikan algoritma ROCC, serta evaluasi kinerja algorittna ROCC, R O C C yang telah diperbaiki (ROCCM), dan Strict 2PL melalui simulasi 1.2. Tujuan Penelitian
Penelitian ini bertujuan untuk melakukan perbaikan algoritma ROCC, serta melakukan evaluasi kinerja. Evaluasi kinerja dilakukan terhadap algoritma ROCCM, algoritma ROCC, maupun algoritma yang telah banyak dipakai pada produk komersial yaitu Strict 2PL. Evaluasi kinerja dilakukan melalui simulator yang diterapkan pada basis data terpusat. Hal tersebut disesuaikan dengan karakteristik algoritma yang lebih cocok diaplikasikan pada basis data terpusat. 1.3. Ruang lingkup
Penelitian perbaikan algoritma ROCC, hanya dilakukan terhadap masalah
reslart, yaitu masih terdapatnya masalah tersebut yang seharusnya tidak dilakukan terhadap eksekusi serializable. Disamping itu evaluasi kinerja, hanya dilakukan melalui pemodelan simulasi pada basis data terpusat. Berdasar hasil sitnulasi, dilakukan evaluasi terhadap kinerja untuk algoritma-algoritma C C tersebut.
11. TINJAUAN PUSTAKA
11.1. Basis Data dan Database Mariagentetzf Systet~i(DBMS) Menurut Elmasri dan Navathe (2000), Basis data adalah kumpulan data yang saling berhubungan, sedangkan database tnanagentent systenzs (DBMS) adalah suatu kumpulan dari program-program yang memungkinkan para pengguna untuk membuat dan mengelola sebuah basis data. Oleh karena itu, DBMS merupakan perangkat lunak sistem yang memberikan fasilitas pendefinisian (dehing), pengkontruksian (constructing), pemanipulasian (manipulating) basis data untuk berbagai aplikasi basis data. Pendefinisian basis data memerlukan tipe data, struktur dan batasan-batasan untuk sebuah data yang akan disimpan dalam basis data. Pengkonstruksian basis data adalah proses penyi~npanandata pada media penyimpanan yang dikendalikan oleh DBMS. Pemanipulasian basis data diantaranya berisi fungsi-fungsi seperti querying pada sebuah basis data untuk mengakses ulang data, update basis data, dan membuat laporan-laporan (reports) dari suatu data.
11.2. Sistem Basis data Menurut Bernstein el al. (1987), sistem basis data (database system, DBS) adalah sekumpulan modul hardware dan sofhoare yang mendukung perintahperintah untuk mengakses basis data. Perintah-perintah untuk mengakses basis data meliputi read dan write. Operator read (r(x)) lnerupakan perintah untuk mengakses item data x, sedangkan write (iv(x))
merupakan perintah untuk
~nengubahnilai item data x. DBS harus mendukung operasi-operasi transaksi yaitu: start, comn~it,dan abort. Start adalah permulaan eksekusi suatu transaksi baru. Berhentinya suatu transaksi ditandai dengan operasi corntnit atau abort. Operasi comnzit mengindikasikan bahwa suatu transaksi berhasil dieksekusi sampai selesai, sedangkan abort menunjukkaan bahwa suatu transaksi tidak berhasil dieksekusi sa~npaiselesai, dan semua operasi yang sudah dieksekusi akan dibatalkan (undo). Menurut Bernstein et al. (1987), sebuah DBS berisi empat komponen yaitu : transaction nlanager (TM), scheduler (SC), recovery manager (RM), dan cache
4
manager (CM). Model DBS pada basis data terpusat diperlihatkan pada Gainbar 1. Pada Gambar 1, TM berguna untuk menerirna permintaan operasi basis data dan operasi transaksi yang kemudian akan disampaikan kepada SC, sedangkan SC adalah kutilpulan program yang mengendalikan eksekusi transaksitransaksi secara concurrent. SC harus bisa mengeksekusi transaksi-transaksi secara serializable. RM bertanggung jawab untuk menjamin semua isi basis data adalah merupakan efek dari transaksi yang telah contnzil bukan dari efek pada transaksi yang mengalami abort. CM berguna untuk mengatur perpindahan data antara memori dan media penyimpanan (disk).
+ Tra,wocrio,?h4anager (TM)
Se/>ad?der(SC)
I
= I
Data hfa,o,rager
(DM)
Recovery illo,ioger (RM)
Cacite Atorroger (CM)
Dotobose (DB)
Gambar 1 Komponen sistem basis data terpusat (Bernstein et al. 1987).
11.3. Transaksi Menurut Bernstein et a1.(1987) transaksi dalaln basis data merupakan eksekusi dari satu atau lebih program untuk mengakses atau melakukan perubahan basis data, termasuk di dalamnya operasi basis data (readswrite)dan operasi transaksi
(start, conznzit, abort). Menurut Connoly dan Beg (2002) suatu transaksi memiliki empat karakteristik yaitu :
1. Atornic Jika operasi dari transaksi dalam basis data berhasil dieksekusi semuanya, maka semua perubahan terhadap basis data harus disimpan secara
permanen, tetapi sebaliknya bila terdapat kegagalan pada salah satu operasi yang terjadi, lnaka semua perubahan yang ada pada basis data akan dibatalkan. 2. Consistensy Transaksi yang telah dilakukan, harus menjaga basis data tetap dalaln kondisi konsisten. 3. Independency
Setiap transaksi harus bersifat independent dan tidak boleh saling mempengaruhi. 4. Durability Perubahan yang berhasil dilakukan oleh sebuah transaksi harus dapat disi~npansecara permanen dalam basis data. Empat Karakteristik tersebut disingkat dengan ACID 11.4. Serializabilily Menurut Bernstein er al. (I987), ketika dua atau lebih transaksi yang dieksekusi secara coiiczrrrent, maka dapat mengakibatkan transaksi satu mernpengaruhi transaksi lainnya. Hal ini dapat menimbulkan basis data tidak konsisten. Salah sat11 cara untuk menghindari ha1 tersebut di atas, maka transaksitransaksi tersebut harus dieksekusi setara dengan serial. Sebuah eksekusi dikatakan serial, jika untuk setiap transaksi, seluruh operasi dari transaksi yang sama, dieksekusi sebelum operasi dari transaksi yang lain. Dalam pandangan pengguna (user) eksekusi serial dipandang sebagai operasi transaksi yang diproses oleh DBS secara aton~ic. Proses eksekusi dikatakan serializable apabila menghasilkan keluaran yang salna dan mempunyai efek yang sama pada basis data, jika transaksi-transaksi-tersebut dieksekusi secara serial. Gambar 2 di bawah ini, memperlihatkan contoh eksekusi transaksi, yang dilakukan secara serial. Gambar 3 memperIihatkan contoh eksekusi transaksi yang dilakukan secara serializable. Dari Galnbar 2, terlihat bahwa pada eksekusi serial, transaksi dieksekusi satu per satu. Dengan de~nikiantransaksi tersebut tidak akan tumpang tindih, sedangkan pada eksekusi secara serializable (Gambar 3) mempunyai hasil
akhir seperti pada eksekusi yang dilakukan secara serial walaupun transkasi T, dan
T2 dieksekusi
secara bersalnaan (concurrent)
Gambar 2 Contoh eksekusi transaksi setara serial.
Garnbar 3 Contoh eksekusi transaksi se.cara serializable
Concurrency
control
(CC)
rnerupakan
suatu
aktivitas
untuk
mengkoordinasikan proses-proses dala~nmengakses atau melakukan perubahan pada basis data yang beroperasi secara bersamaan (Bernstein el 01. 1987). Ozsu dan Valduriez (1999) membagi CC rllenjadi 2 jenis yaitu pessifnistic dan
optinzistic. Pada optir~zisfictransaksi-transaksi yang datang dapat langsung diproses tanpa harus menunggu validasi terlebil~dahulu, yang mempunyai urutan operasinya adalah read, conrptcte, validate, write. Padapessinzistic setiap transaksi yang akan melakukan akses basis data harus melalui proses validasi terlebih dahulu, sehingga urutan operasinya adalah validate, read, conzpute, dan write. 11.6. Two Plzuse Locking (2PL)
Two Plrusc Locking (2PL) merupakan jenis CC yang pessi?~zistic.Pada CC jenis irli mekanisme perolehan lock dan pelepasan lock (unlock) untuk suatu item data dilakukan dalam dua tahap yaitu :
1. Growing phase : Suatu transaksi boleh mendapatkan lock tetapi tidak boleh rnelepaskan lock yang telah diperoleh.
2. Shringking phase : Suatu transaksi boleh melepas lock tetapi tidak diperbolehkan rnelakukan permintaan lock baru Pada saat permulaan eksekusi, suatu transaksi berada dalam growing phase Tetapi pada saat transaksi mulai melepas lock, maka transaksi tersebut berada dalam shringkingphase. Terdapat dua macam modus lock yaitu : 1. Shared lock (read lock) : lock yang diberikan pada transaksi yang
melakukan operasi readterhadap item data dalam basis data. 2.
Exclusive lock (write lock) : lock yang diberikan pada transaksi yang melakukan operasi write terhadap item data dalam basis data.
Dua modus lock tersebut kompatibel apabila dua atau lebih transaksi
bisa
mendapatkan lock dari item data yang sama dalam waktu yang bersamaan. Jika modus lock yang diinginkan oleh suatu transaksi tidak kompatibel maka transaksi tersebut harus menunggu sampai lock tersebut dilepas. Tabel 1 di bawah ini mernperlihatkan kompatibilitas setiap modus lock Tabel 1 Kompatibilitas modus lock
8
11.7. Strict Two Pliuse Loclritzg (Strict 2PL) Strict 2PL merupakan CC yang menggunakan mekanisme lock, yang banyak dipakai pada produk komersial. Menurut Elmasri dan Navathe (2000), pada mekanisme CC menggunakan cara ini, suatu transaksi selama eksekusi akan nlelakukan permintaan lock suatu item data; dan mengakses atau memodifikasi data. Hal ini dilakukan berulang-ulang sampai akses atau modifikasi suatu item data selesai dilakukan pada suatu transaksi.
Pada akhir eksekusi, transaksi
melepas selnua lock untuk semua item data secara bersamaan. Grafik Strict 2PL diperlihatkan pada Gambar 4. Dari Gambar 4 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) Locking
4
Gambar 4 Grafik Strict 2PL (Elmasri & Navathe 2000). 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. Gambar 5 memperlihatkan eksekusi transaksi menggunakan CC ini. Dari Gambar tersebut dapat dijelaskan bahwa transaksi TI akan melepas semua Iock setelah eksekusi operasi dari transaksi telah diselesaikan semua. Selama lock suatu item data belum dilepas oleh TI maka apabila Tz membutuhkan Iock suatu item data, harus menunggu. Pada Strict 2PL bisa terjadi deadlock, karena suatu transaksi masih memegang lock suatu item data, setelah proses modifikasi telah selesai, seperti diperlihatkan pada Gambar 6.
Lock (A) Read (A)
-
Lock (C) Read(C) C:=C+2 IWire (C)
.~
rr'?;le (A) rvr;re (B) Unlock (A) U!rloc!@) Lock(A) R#od/A) A:=A+Z r m e (A) Unlock (C) U,ilock(A)
Gambar 5 Contoh eksekusi transaksi pada Strict 2PL.
Wuklu
I
r,
T:
Lock (A) Lock (8)
Read (A) Read (B) A:=A+lOO B:=B+lOO
r%.;1e (4 IWire (B)
Lock (B) D i b l a k o l e h T: Lock (A) Diblak oleln T,
Gambar 6 Contoh deadlock pada Strict 2PL. Dari Gambar 6 dapat dijelaskan bahwa, transaksi T, dan transaksi
T2
tidak
dapat diproses, karena masing-masing saling menunggu salah satu dari dua transaksi tersebut untuk melepas lock. Dalam situasi seperti ini salah satu dari dua transaksi yang ada (TI atau T2 ) harus dipaksa untuk melepas lock. Jika T, yang melepas lock maka transaksi ini harus melakukan roll-back dan memulai operasi transaksi baru.
11.8. Read-cor~mzitOrder Concurrericy Coriirol (ROCC) ROCC merupakan jenis CC yang optitnistic. Pada ROCC, suatu transaksi boleh mengiri~nlebih dari satu access reguest message (ARM) yang berisi satu atau lebih operasi akses. Ketika sebuah request message datang, maka elemen
10 baru yang berhubungan dengan inforinasi dari request n~essagetersebut, akan dibangkitkan dalam RC-quezce. RC-qtrezre mempunyai elemen yang terdiri dari tujuhfield yaitu : Tid, validated (V), conzmit (C), restart (R), rend, write, dan next, yang diperlihatkan pada
Gambar 7. Tid berisi id dari transaksi. Read berisi nilai itein data yang dibaca. Write berisi nilai itein data yang ditulis. ValidatedJeld bernilai satu jika suatu transaksi tidak memerlukan validasi atau telah sukses dari proses validasi, dan bernilai 0 jika suatu transaksi inemerlukan proses validasi atau belum dilakukan validasi. Jika cortznzitjield bernilai 1, mengindikasikan bahwa request message tersebut bertipe coi~zmit,dan bernilai 0 jika reqzcest rizessage tersebut bukan bertipe conzi1tit. Restart Jeld akan bernilai 1 , jika transaksi tersebut merupakan transaksi yang mengalami restart, dan bernilai 0 jika transaksi tersebut bukan atau belum mengalami restart. Nextpointer akan menunjuk ke eletnen berikutnya yang merepresentasikan bahwa elemen tersebut datang sebelumnya. Pointer padaelemen yang datang pertama kali di set ke NULL. RC-quezre adalah struktur data yang digunakan oleh ROCC untuk melakukan validasi. I ~ i d IV
IC k
keuds I ~ r i t e s 1 Next
I
Ga~nbar7 Format elemen RC-quezte (Shi & Perrizo 2004). 11.8.1. Algoritma validasi intervenitzg
Proses validasi pada algoritma ROCC dimulai ketika ada request message yang datang bertipe conznzit. Proses penelusuran untuk mencari elemen yang operasinya konflik pada queue, dimulai dari elemen read pertarna dari transaksi yang sedang dilakukan validasi ("First'? yang dibandingkan dengan elernen 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 diternukanfilst-down reached element, maka "First" akan digabungkan dengan first-down reached element. Gabungan kedua elemen tersebut, dianggap sebagai "First" yang baru.
II Jikafirst-down reached elen~entyang ditemukan adalah elemen co~nt~zit dari transaksi yang salna, illaka proses validasi dianggap sukses. Tetapi apabila yang ditemukan bukan elemen cotiltt~it dari transaksi yang sama, maka proses penelusuran dilakukan terus untuk inenemukan elemen yang operasinya konflik sampai ditetnukanfirst-down reached elenlent berikutnya. Apabila penelusuran dari elemen "First" menemukan operasi elelnen yang konflik, ~ n a k a"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 comtnit, untuk mencari elemen dari transaksi lain yang operasinya konflik dengan elemen conznzit ("Second'? sampai ditemukan elemen dari transaksi yang sama @-st-up reached elernent). Apabila pada saat penelusuran dari "Second" tidak inenemukan elemen yang konflik sampai ditemukanfirst-zrp reached element, maka "Second" akan digabungkan dengan first-tip reached elentent. Gabungan kedua elemen tersebut dianggap sabagai "Second" yang baru. Apabilafirst-up reached eletneprt adalah "First" maka proses validasi dianggap sukses. Tetapi jika bukan "First", maka "Second' akan dibandingkan terus sampai menemukanfirst-up reached elernent berikutnya. Apabila pada saat penelusuran ditemukan operasi elemen yang konflik maka proses validasi dianggap gagal. Jika suatu transaksi gagal dalam proses validasi, maka transaksi tersebut akan dilakukan restart. Scheduler akan menghapus semua elemen dari transaksi tersebut. Setelah itu akan dibangkitkan sebuah restart eletnent dan menempatkan di dalam RC-qrtezce. Restart elerttent terdiri dari seinua item data yang akan dibaca (read) dan semua item data yang akan diubah (write) oleh transaksi yang mengalami kegagalan dalam proses validasi. Pseudocode algoritma validasi intervening pada ROCC, diuraikan dalam penjelasan di bawah ini (Shi & Perrizo 2004). Sebagai inisial "First" = NULL, dan"Second" = NULL. Algoritma tersebut akan dieksekusi apabila request niessage yang datang bertipe commit. Setelah pseztdocode
algoritma validasi
intervening, di bawah algoritma tersebut, diilustrasikan implementasinya pada RC-queue yang diperlihatkan pada Gambar 8. Ilustrasi implementasi algoritma validasi yang terdapat pada Gambar 8 berakhir dengan restart. Hal tersebut terjadi
karena pada saat penelusuran ditemukan operasi elemen yang konflik baik dari elemen "First" maupun dari elemen conzntit. "First" = XULL; "Second" =NULL; Locate the transaction'sfirst read eleinent in the RC-quezre; Iffnot fotmd, return validated =true; "First" = the first read ele~lient; While (I) { Coinpare "First" with aN the elenzents of other transaction behind it until it reached all elenzent of the sanie transaction first-down-reached eleinent); If (There is no eleilzent conflict) //inoving doion to look for upper side conflict { Merge the "First" element with the first-down-reached eleniet; Rei~tovethe "First" elenzentfront the RC-Queue; I f f Thejirst-down-reached elentent is the coinniit elentent) Return validated = true; Else "First" = the first-do~vn-reached-eletnent; J
Else i/ There is uper-sided-conflict; . { Insert "First" into the RC-queue right before the conflicting element; Remove the original "First"fi.0111the RC-qzteue; "Second" = Collznzit element; While (I) //i~zovingup to look for the lower-sided conflict; {Co~npare"Second" with all the elenzent of other trunsactions before it zrntil it reaches an ele~i~ent of the saine transaction first-trp-reached elenzent); If(there is no eleinent conflict) {Merge the "Second" elelllent to the first-up-reached elenzent; Renzove tile "Secoiid"elen~entfrom the RC-queue; I f (thefirst-up-reched elelltent is the first) Return validated=trzre; Else "Second" =first-up-reached eleilzent;
I
Else //there is also Lower-sided-conflict, the validationfails. {Remove all elentents of the transactionfront the RC-queue Retzrrn validated=false;
I
Pada Gambar 8 diperlihatkan keadaan RC-queue dengan empat transaksi yang terdapat pada quezre. Transaksi yang terdapat pada urutan pertama adalah TI yang mengirim readreqzrest untuk melnbaca objekx, y, z, (rib), rib), rie)). Kemudian disusul dengan transaksi T2yang telah berhasil dilakukan validasi dengan operasi
read untuk item data v (rz(v)), operasi read untuk item data
zi
(r2(u)), dan
operasi write untuk item data x 'vz(x)), berikutnya adalah transaksi T3juga telah sukses dilakukan validasi dengan operasi read ontuk item data z (r3(z)), operasi read untuk item data
ZL
(r3(u)), dan operasi write untuk item data v (w3(*.
Akhirnya TI mengirirn cottititit request untuk mengubah item data z yaitu wIk). Langkah melakukan validasi pada RC-queue Gambar 8, dimulai dari bagian atas (front) yaitu dengan cara mencari transaksi yang operasi elemennya konflik
dengan "First". Penelusuran dari "First" menemukan elemen dari transaksi lain yang operasinya konflik, yaitu operasi write item data x, dari transaksi T2 (wz(x)). Kemudian proses validasi dilanjutkan dari elemen commit. "Second" adalah elemen conzniit. "Second" dibandingkan dengan elemen - dari transaksi lain. Penelusuran dari "Second" menemukan operasi item data yang konflik, yaitu operasi read item data z dari transaksi T3 (r&)), sehingga proses validasi untuk transaksi TI padaiiC-queue Gambar 8 dinyatakan gaga].
Gambar 8 RC-queue pada ROCC.
11.8.2. Komponen ROCC
ROCC diimple~nentasikan n~enggunakantiga komponen, yaitu client-side procedure, schedztler-side procedure, dan data-ittanager side procedure (Shi &
Perrizo 2004). Pada Gambar 9 ditunjukkan ketiga komponen tersebut Dari Gambar 9, dapat dijelaskan bahwa
pengguna melakukan transaksi melalui
transaction manager ( T M ) , kemudian diteruskan ke scheduler (SC) untuk
dilakukan penjadwalan dalam mengakses basis data. Apabila berhasil dalam proses penjadwalan yang telah dilakukan oleh SC, maka permintaan transaksi
akan diteruskan ke data nlanager (DM) untuk membacafmengubah data yang dimaksud.
Tnnractian Manager
SC-Side Procedure
DM-Side Procedure Database (DB)
Gainbar 9 Komponen ROCC (Shi & Perrizo 2004)
111. METODE PENELITIAN 111.1. Metode Perbaikan Algoritma R O C C
Bernstein et al. (1987) menjelaskan cara untuk mengenali himpunan transaksi yang dieksekusi (history) yang serializable. Jika sebuah history H dengan transaksi T={T/,Tz, ...T,,} maka serialization graph (SG) dari history H (SG(H)) adalah directed graph dengan node adalah transaksi-transaksi dalam T, yang sudah melakukan coiiznzit dalam H. Edge adalah i;
+ I;. jika salah satu dari
operasi-operasi i; konflik dengan salah satu dari operasi-operasi 2; dalam H, dan
Ti dieksekusi lebih awal dari
q. Sebuah history H adalah serializable, jika SG(H)
adalah acyclic. Modifikasi algoritma R O C C dilakukan dengan cara terlebih dahulu mernbuat SG dari beberapa kondisi RC-qzreue, sehingga ditemukan keadaan dimana terdapt SG yang acyclic tetapi algoritma validasi intervening ~nelakukanrestart. 111.2. Metode Evaluasi Kinerja Penelitian untuk mengukur kinerja ROCC, ROCCM, dan Strict 2PL dilakukan dengan si~iiulasi yang
berbasis pada Shi dan Perrizo (2004).
Pelaksanaan simulasi dilakukan dengan menggunakan simulator. Simulator dibangun dengan bahasa pemrogra~nan C Builder Version 6.0 dengan cara ~nelakukan modifikasi program simulator dari penelitian sebelumnya yang dilakukan oleh Shi dan Perrizo (2004). Spesifikasi komputer yang digunakan pada pelaksanaan simulasi, menggunakan sistem operasi Windows MilIeniurn, lnemori = 512 Mlyte, prosessor
= Intel
Pentiur~z4 2.66 GHz, serta hardisk = 40
Gbyte. Silnulasi yang dilakukan dengan parameter-parameter input yang sama pada ketiga algoritma tersebut. Paremeter-parameter simulasi diperlihatkan pada Tabel 2. Pernberian nilai parameter input untuk simulasi ini, tidak berdasarkan pada data sesungguhnya, tetapi merupakan asumsi-asumsi yang diambil dari penelitian sebelumnya yang telah dilakukan oleh Shi dan Perrizo (2004).
Tabel 2. Parameter-parameter input simulasi
~nisialisasitransaksi baru dari suatu terminal.
Hasil simulasi yang tampil adalah tlzrozcghput, response tinie, dan restart ratio untuk ketiga algoritma yang dievaluasi. Throughput dalam ha1 ini adalah jumlah transaksi yang dapat diselesaikan per satuan waktu. Restart ratio adalah jumlah rata-rata transaksi yang mengalami restart per satuan waktu. Respon tittle adalah waktu di antara ketika sebuah terminal mengirim sebuah transaksi baru dan ketika hasil transaksi baru tersebut dike~nbalikanke terminal. Hasil simulasi diuji dengan uji t-stzrdent menggunakan selang kepercayaan (conJidence interval) 95% (Law & Kelton 1991).
IV. HASIL DAN PEMBAHASAN IV.l. Algoritlna ROCCM Teorema yang diketnukaltan oleh Shi dan Perrizo (2004), mengungkapkan bahwa R O C C menghasilkan eksekusi transaksi yang serializable. Karena jika terdapat eksekusi yang tidak serializable, maka ada cycle dalam serialization
graph (SG) dalam RC-queue. Sebagai asumsi, terdapat sebuah cycle dala~nRCqt~ezleyang terdiri dari TI 3Tz ...T,,+TI, ~ n a k adalam transaksi-transaksi tersebut, terdapat konflik antara TI darl T2, sel-ta terdapat konflik antara T, dan T,. Algorit~navalidasi illtel-vening yang terdapat pada ROCC, akan ~nembatalkan transaksi yang lne~npunyaidua elemen yang keduatlya konflik dengan elemen transaksi lain yang terletak di antara elelnen yang konflik tersebut. Dengall demikian, cycle aka11dihentikan, karena transaksi yang dibatalkan akan dilakukan
restart.
Ga~nbar10 RC-qztelre dengan eksekusi serializable pada R O C C
Garnbar 1 1 Acyclic SG,
Dari hasil penelitian yang telah dilakukan, terdapat keadaan RC-quetre dengan eksekusi serializable, tetapi terdapat transaksi yang Inengalami restart pada saat dilakukan proses validasi oleh ROCC, seperti yang diilustrasikan pada Gambar
18 10. Pada Gambar 10, transaksi yang datang pertama kali adalah TI yang aka11 ~nengakses item data x (rl')),
item data y (r,(y), dan item data z (rl(z,).
Selanjutnya setelah transaksi TI terdapat transaksi
fi yang telah dilakukan validasi
dimana transaksi TZ terselmt melakukan perubahan nilai item data x yaitu wz6). Setelah transaksi T2 terdapat transaksi T3 yang hanya ingin mengakses item datay (r30). Akhirnya transkasi TI akan melakukan perubahan nilai item data z hv&)).
Proses validasi dimulai dari elemen read pertama kali untuk transaksi TI ("First'?, yang menemukan operasi elenien yang konflik yaitu item data x dari
operasi w&) pada transaksi T2. Kerena ditemukan elemen yang konflik dengan "First" dari transaksi Tz, maka proses validasi selanjutnya dimulai dari bagian
bawah dengan membandingkan elemen coniniit ("Second'? dari transaksi TI dengan transaksi sebelumnya. Penelusuran dari "Second", menemukan elemen yang konflik, yaitu operasi read untuk item data z, dari transaksi T3 (I-3(~)).Pada kondisi ini transaksi TI mengalami restart, padahal eksekusi transaksi adalah merupakan eksekusi yang serializable. SG pada Gambar 11 merupakan ilustrasi dari eksekusi transaksi untuk RCqueue pada Gambar 10. Dari Gambar 11 tersebut dapat diketahui bahwa tidak
terdapat cycle dalam SG tersebut, yang menunjukkan bahwa eksekusi lransaksinya bersifat serializable. Perbaikan algoritma ROCC menjadi ROCCM, dilakukan dengan mengubah cara validasi yang dilakukan oleh algoritma validasi intervening. Proses validasi pada algoritma ROCCM akan diuraikan dalam penjelasan di bawah ini. "First" adalah elemen operasi read dari transaksi yang melakukan conimit. "Conibine" adalah kumpulan elemen yang operasinya konflik dengan elemen coninzit ("Second'y maupun operasinya konflik dengan elemen "Combine "
sebelumnya. Sebagai inisialisasi awal "Cornbine"
=
(1. Langkah-langkah untuk
melakukan validasi setelah suahi transaksi mengirimkan coniniit request, pada ROCCM selengkapnya adalah sebagai berikut : 1. Bandingkan "First" dengan elemen dari transaksi lain yang terdapat di
antara "First" sampai elemen contniit. Bila pada saat penelusuran ditemukan elemen read dari transaksi yang sama (first-down reached
19 elentet~l)maka gabungkan elemen "Firsi" ke dalam elemen transaksi
yang sama berikutnya. Kemudian bandingkan
"First" hasil gabungan
tersebut, dengan elemen dari transaksi lain yang terdapat di antara "First" sampai elemen coninzit. Proses penelusuran dilakukan terus untuk menemukan elemen yang konflik atau elemen read berikutnya. Bila dari transaksi transaksi berikutnya yang ditemukan, adalab elemen cor~zn~it 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 sebeluln elemen dari transaksi lain yang
konflik. Hapus elemen "First" yang asli dari RC-qzceue. 3. Bandingkan "Second" atau "Con~bine" dengan elemen dari transaksi lain
yang terdapat di antara "Second" sampai ditemukan elemen dari transaksi yang sama ("First-up reached elenzent'y. Setiap elemen yang konflik, lakukan insert ke "Con~bine". 4. Bandingkan "Conzbine " dengan "First-zip reached element" Jika terdapat
konflik maka validasi dinyatakan gaga]. Jika tidak terdapat konflik lakukan pengecekan apakah "First-up reached elenzenl" adalah "First", jika merupakan "First maka validasi dinyatakan sukses, tetapi jika bukan elemen "First" lanjutkan langkah 5. 5. Gabungkan "SeconG' dengan
"First-up reached element" hapus
"Second" asli dari RC-quezre. Lanjutkan langkah 3. Pseudocode algoritma validasi pada ROCCM selengkapnya terdapat pada
urian di bawah ini. Pada algoritma validasi ROCCM, tersebut, proses penelusuran dari elemen "First" sama dengan aigoritma validasi pada ROCC. Perbedaannya terdapat pada proses penelusuran dari elemen con~njityaitu terdapat proses membandingkan antara elemen corlzn~itatau elemen "Combine" dengan elemen yang terdapat di antara elemen commit tersebut sarnpai ditemukan elemen transaksi yang sama rFirst-up reached elenlent'?. Jika ditemukan elemen yang konflik dengan elemen conlmit atau "Combine" maka elemen dari transaksi lain yang terdapat konflik, akan dilakukan insert ke "Conlbine ". Kemudian dilakukan pembandingan "Con~bine"dengan "First-up reached element" Jika terdapat
20
konflik maka validasi dinyatakan gagal. Jika tidak terdapat konflik lakukan pengecekan apakah "First-zip reached element" adalah "First", jika merupakan "First" maka validasi dinyatakan sukses, tetapi jika bukan elemen "First ", maka "Second"
digabungkan dengan
"First-zip reached elentent"
dun proses
penelusuran berjalan terus untuk menemukan elemen yang operasinya konflik dengan "Second" atau "Con~bine",sampai ditemukan elemen dari transaksi yang sama. Algoritma selengkapnya adalah sebagai berikut : "First" = NULL; "Second" =NULL; "Conzbine "=NULL; Locate the transaction 'sfirst read element in the RC-queue; If(notfound) return validated =true.. "First" = the first read elentent; While (1) J Conzpare "First" wifh all the elenzents ofother transaction behind it until it reached an elernent of the sanze transaction first-down-reached elenzent); If(T1~ereis no elenzent conflict)//nzoving down to lookfor tipper side conflict {Merge the "First" elenzent with the first-down-reached elemet; . Rernove the "First" elenzent from the RC-Q~ceue; If(Tlzefirst-down-reached element is the commit elenzent) Return validated = true; Else "First" = the first-down-reached-elert~ent;
I
Else // There is liper-sided-conflict; {Insert "First" into the RC-queue right before the conflicting element; Rmnove the original "First"fr0rn the RC-queue; "Second" = Conzmit elenzent; While (I) /hzzoving up to lookfor the lower-sided conflict; {Con~pare"Second" wirfz all the elenlent of other transactions before it until it reaches an elenzent of the same transaction first-lip-reached element); Insert elerncnt conflict with "Second" or Contbine" to "Cotnbine; {Conzparefirst-up-reachen eletizcnt" with "Combirze"; If(There is no elernent co~zflict) {Merge the "Second" element ~viththe first-up-reached element; Remove the "Second" elementfronz the RC-qzieue; I f the first-up-reached elenzent is the "First'y Return validated =hue; Else "Second" = the first-up-reached elernent;
I
Else //there is also Lo)ver-sided-conflict, the validationfails. {Remove all elenzents of the transaction~omthe RC-queue Return validated=false;
I
I
Pada algoritma validasi ROCCM di atas, yang tercetak tebal merupakan bagian modifikasi dari algoritma sebelumnya. Ilustrasi inlplementasi algorit~naROCCM, untuk beberapa kondisi RC-queue diperlihatkan pada Gambar 12.a, 12.b, dan 12.c. Pada Gambar 12.a diperlihatkan keadaan RC-queue dengan empat transaksi yang terdapat pada queue. Transaksi yang terdapat pada urutan pertama adalah TI dengan operasi rl'),
r,(yl, r&).
Kemudian disusul dengan transaksi T2 yang telah dilakukan validasi dengan operasi-operasi r2(w), r2(u), dan wz(x), berikutnya adalah transaksi T3 juga telah sukses dilakukan validasi dengan operasi-operasi r&), I&), w~(v).
(c) Gambar 12 RC-queue pada algoritma ROCCM: (a) hasil validasi tidak restart, (b) dan (c) hasil validasi restart.
Akhirnya TI mengirim col~znzitrequest untuk mengubah item data z yaitu wle). Langkah melakukan validasi pada RC-quezie Gambar 12.a, dimulai dari bagian atas pant) yaitu dengan cara mencari transaksi yang operasi elemennya konflik dengan "First". Penelusuran dari "First" menemukan elemen dari transaksi lain yang operasinya konflik yaitu operasi write item data x, dari transaksi T2 (102()1). Kemudian proses validasi dilanjutkan dari bagian bawah. "Second" adalah elemen conmit. "Second" dibandingkan dengan elemen dari transaksi lain, yang menemukan operasi item data yang konflik, yaitu operasi read item data z dari transaksi T3, sehingga elemen yang disalin ke "Combine" adalah item data dari operasi readtransaksi T3 yaitu 2,s dan item data pada operasi write dari transaksi T3 yaitu v, sehingga elemen-elemen serta operasinya yang terdapat pada "Con7bilie" adalah r3(z), r3(s), w3(v). Penelusuran berikutnya metnbandingkan
"Second" dengan transaksi di
atasnya, karena tidak ada operasi elemen yang konflik dengan "Second" maka kemudian dibandingkan dengan "Combine yang juga tidak menemukan konflik. "
Karena tidak ada operasi elelnen yang konflik berikutnya yang ditemukan, sampai ditemukan elemen "First", maka akhirnya "Cornbine" dibandingkan dengan "First" yang juga tidak rnenemukan konflik sehingga proses validasi untuk keadaan RC-qrtezie Gambar 12.a dinyatakan sukses, dengan T/ dapat melakukan operasi perubahan item data z. Hasil validasi yang dilakukan pada RC-queue Gambar 12.b, berhasil menemukan konflik dengan "First" untuk transaksi TI, yaitu operasi item data x (M~(x))
dari transaksi TI. Selanjutnya proses validasi dari elemen cornnzit untuk
transaksi TI, berhasil menemukan konflik yaitu operasi item data y (w4(y)) dari transaksi T4, sehingga 1v4(yl disalin ke "Conzbine". Terakhir "Combine" dibandingkan dengan "First" yang berhasil menemukan konflik yaitu operasi item data y (,vl(y), yang konflik dengan r&),
sehingga transaksi TI mengalami
restart. Proses validasi pada RC-queue Gambar 12.c dimulai dari "Firsf" yang dibandingkan dengan elemen dari transaksi lain yang terdapat di antara "First" sampai elemen conzr~ityang lnenemukan elemen konflik yaitu operasi read item
data x (rz(x)) dari transaksi T2. Ke~nudianproses validasi dilanjutkan dari bawah dengan lnelnbandingkan "Second" dengan transaksi lain, yang dalam ha1 ini mene~nukankonflik yaitu operasi read item data z (r&) dari transaksi T4, maka seluruh elemen pada transaksi T4, yaitu elemen read z (r4(4))dan elemen write u 'v4(u)) akan disalin dan digabungkan ke "Combine". Penelusuran berikutnya membandingkan
"Second" dengan transaksi di
atasnya, dalam ha1 ini karena tidak ada elemen yang konflik dengan "Second" kemudian operasi elemen transaksi tersebut dibandingkan dengan "Combine" yang menemukan konflik, yaitu operasi read item data tr pada transaksi T3 (r3(u)). Elemen-elemen dari transaksi tersebut (elemen read u ( r 3 0 ) dan elemen write (w3(1v)))disalin dan digabungkan ke dalam "Coinbine". Penelusuran terhadap elemen transaksi berikutnya tidak menemukan konflik dengan "Second" tetapi mene~nukan operasi elemen yang konflik dengan "Coiitbine!' yaitu item data iv dari operasi rzfiv) transaksi T2, sehingga dalam ha1 ini elemen r2(1v), r2(v), dun wz6) disalin dan digabungkan ke "Cornbine" sehingga elemen "Combine" ~nenjadi (rdfir), w4(z); r3(u), w3(w); r2(w), rz(v), 1v2($) Akhirnya "First" dibandingkan dengan "Cornbine" yang menemukan konflik yaitu operasi item data x (w2(x)konflik dengan UJ/(X)) , sehingga transaksi
TI pada RC-queue Ga~nbar12.c mengalami restart. IV.2. Pelaksanaan Simulasi IV.2.1. Asurnsi-asumsi simulasi
Simulator yang digunakan untuk mengukur kinerja CC tersebut, menggunakan model antrian tertutup pada suatu sistem basis data terpusat, seperti diperlihatkan pada Gambar 13 dan Gambar 14. Pada simulator terdapat sejumlah terminal, untuk membangkitkan transaksi. Selanjutnya terdapat batasan transaksi yang aktif pada suatu saat di dalam sistem (ntpl). Apabila transaksi yang dibangkitkan oleh sejumlah terminal melebihi batasan transaksi yang diijinkan oleh sistem (melebihi nlpl), 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 yang dibangkitkan oleh terminal masuk ke cc queue (concurrency control queue) dan
24 membuat permintaan operasi akses basis data melalui CC. Jika 1010s dari operasi yang dilakukan oleh CC, selanjutnya transaksi tersebut mengakses data. Jika data tersebut ada di b~rJferniaka eksekusi dilanjutkan ke CPU. Tetapi jika data tersebut tidak terdapat di bzrJfer maka eksekusi akan dilewatkan ke disk untuk mengakses data untuk seterusnya dilanjutkan ke CPU. Untuk mengakses disk serta diproses pada cpu harus melalui antrian di disk serta CPU yaitu disk-queue dan cpu- qzleue. Pada simulasi diasumsikan juga, bahwa sebuah transaksi melakukan operasi read terlebih dahulu sebelum melaksanakan operasi write. Diasumsikan juga jaringan yang digunakan adalah jaringan Local Area Nehvork (LAN) dalam keadaan handal pada saat transmisi data dari terminal ke server. Jalur think nlemberikan 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 qzlelre sampai permintaan akses data dapat diproses. Jika CC menetapkan untuk melakukan restart suatu transaksi, maka transaksi tersebut akan dilakukan restart dan selanjutnya dimasukkan ke dalam ready queue. Jika suatu transaksi telah kornplit (selesai) maka CC akan succes Itlessage ke terminal. memberikan co~i~nzit
IV.2.2. Model Simulasi Pada simulator terdapat dua model logical queuing yaitu yang pertama model antrian untuk ROCCM dan ROCC yang diambil dari penelitian sebelumnya (Shi & Perrizo 2004), serta yang kedua model antrian untuk Strict 2PL. Gambar 13 di
bawah ini memperlihatkan model antrian yang pertama pada simulator. Pada
Gambar
13
diperlihatkan
terdapat
sejumlah
terminal
untuk
membangkitkan transaksi. Ketika suatu transaksi baru diinisialisasi, sistem akan melewatkan transaksi pada ready queue untuk diteruskan ke cc queue. Transaksi yang 1010s validasi akan dilanjutkan untuk mengakses data di bzcfer atau disk. Setelah mendapatkan data operasi transaksi diteruskan ke cpu. Setelah dieksekusi oleh cpu terdapat pemberian nilai int-think dan ext-think Transaksi yang gagal validasi akan dilakukan restart dan kembali masuk ready queue. Eksekusi transaksi yang telah komplit akan dilaporkan ke terminal.
Gambar 13 Model logical queuing untuk ROCCM dan ROCC pada simulator (Shi & Perrizo 2004). Gambar 14 memperlihatkan model antrian untuk Strict 2PL pada simulator. Model tersebut merupakan modifikasi dari model logical qziezring penelitian sebelumnya dan ditambahkan dengan jalur transaksi yang mengalami blocked serta blocked queue untuk menampung transaksi yang mengalami blocked. Eksekusi antrian hampir sama dengan model antrian pada ROCC dan ROCCM. Perbedaannya pada model antrian Strict 2PL adalah terdapat block queue untuk menalnpung transaksi yang mengalami blocked untuk kemudian diteruskan ke cc qzreue. Parameter input defaut yang digunakan pada pelaksanaan simulasi diperlihatkan pada Tabel 3.
Gambar 14 Model logical queuing untuk Strict 2PL pada simulator (modifikasi dari model Shi dan Perrizo (2004)). Tabel 3 Nilai parameter input default pada pelaksanaan silnulasi No
Parameter
Nilai
1
db-size
1000 pages
2
mar_trar?s
10 pages
3
rrzi~z-trans
4 pages
4
~vritegrob
0,25
5
int-think
I ms
6
ext-think
1 ms
7
max-reg
3
8
mean-time
5
9
corrtrrzit-nurn
800
10
hit-ratio
0,s
11
obj-io
35 ms
12
obj-cpu
15 ms
13
nzirrz_cpzr
4
14
n~ini-disk
8
15
nlpl
5,10,25,50,75,100,200
27
IV.3. Hasil Simulasi Pelaksanaan simulasi dengan parameter input seperti pada Tabel 3, dimaksudkan untuk mengetahui kinerja ketiga algoritma yang diuji, berdasarkan nilai parameter daii penelitian sebelu~llnya(Shi & Perrizo 2004). Hasil simulasi pada fhrorighput dapat dilihat pada Gambar 15.a serta Tabel 4. Melalui Gambar 15.a tersebut, dapat diketahui bahwa ROCCM mempunyai nilai yang lebih tinggi, bila dibandingkan dengan algoritma ROCC dan Strict
2PL. Uji t-student pada sainple dengan derajat bebas (d' = (n1+n2-2)yang melniliki
.. rata-rata x dan y, serta variance s? dan sz 2 d~hitung dengan persamaan di bawah ini :
Pada pengujian dengan menggunakan derajat bebas 8 (5
+
5 -2) dan 95 %
con$dence interval, jika -1.86 < t < 1.86 maka perbedaan tidak nyata. Hasil pengujian dengan uji t-student menunjukkan bahwa perbedaan fhroughput antara
ROCC dan ROCCM, cukup nyata pada tizpl di atas 50 (Lampiran 3). Dari Gambar 15.a juga dapat diketahui bahwa throz~glipritStrict 2PL ada pada posisi terendah. Hasil simulasi pada restart ratio, dapat dilihat pada Gambar 15.b maupun Tabel 4. Gambar 15.b memperlihatkan perbedaan restart ratio ketiga algoritma yang diuji. Dari gambar tersebut, dapat diketahui bahwa resturt ratio ROCC berada pada posisi tertinggi terutama pada nip1 = 200. Gambar 15.c, memperlihatkan hasil simulasi dalam ha1 response time. Melalui gambar tersebut, dapat diketahui bahwa response titile antara ROCCM dan
ROCC, secara umum ha~npirsama pada berbagai ii7pl. Pada Tabel 4, ditunjukkan rekapitulasi kinerja algoritma pada throughput,
restart ratio dan response tiiiie. Pada tabel tersebut T adalah throughput, RR adalah response time, dan RT adalah restart ratio. Melalui tabel tersebut, juga dapat diketahui bahwa perbedaan nilai kinerja antara ROCC dan ROCCM pada
28
nzpl = 10 me~npunyainilai yang kecil. Tetapi nilai-nilai tersebut akan selnakin jauh berbeda seiring dengan naiknya jumlah mpl.
Gambar 15 Hasil simulasi: (a) throughput, (b) restart ratio, (c) response finze.
29
Tabel 4 Rekapitulasi hasil simulasi
IV.4. Evalusi kinerja algoritma Bargava (1999) mengemukakan bahwa salah satu cara untuk evaluasi terhadap kinerja sebuah algoritma CC adalah
melakukan
dengan melakukan
evaluasi terhadap throzrghptit, response tinie, dun restart ratio. Dari hasil simulasi yang ditampilkan pada eksperimen ini, dapat jelaskan bahwa algoritma ROCCM mempunyai troughput yang lebih tinggi. Sernentara itu restart ratio berada di bawah ROCC. Selain itu ROCCM mempunyai response tiwe yang hampir sama dengan ROCC. Throughput ROCC secara umurn 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 tirtze ROCC hampir sama dengan ROCCM yang mempunyai response tittle lebih cepat bila dibandingkan dengan Strict 2PL. Sementara itu, Strict 2PL mempunyai throughput yang lebih rendah bila dibandingkan dengan ROCCM dan ROCC. Restart ratio pada algoritma ini cukup rendah.
V. KESIMPULAN DAN SARAN
V.1. Kesi~npuIan Melalui penelitian perbaikan dan evaluasi kinerja algorit~naROCC dapat disi~npulkan: 1. Secara umum throtrghput ROCCM
lebih tinggi, bila dibandingkan
dengan ROCC dan Strict 2PL. 2. Restart ratio ROCCM lebih rendah dari ROCC. 3. Response time ROCCM tidak jauh berbeda dengan ROCC.
4. Dengan ~nelakukanperbaikan algoritma ROCC, restart ratio yang terjadi akan berkurang sehingga lnenaikkan kinerja algoritma tersebut. V. 2. Saran Pada penelitian ini algorit~naROCCM hanya dibandingkan 'dengan ROCC dan Strict 2PL. Penelitian lebih lanjut dapat dilakukan dengan ~nembandingkan algorit~naCC lainnya untuk mendapatkan hasil yang lebih lengkap. ROCC dan
ROCCM dapat dikembangkan pada DBMS untuk aplikasi pada transaksi yang banyak ~nelakukanoperasi read dari pada operasi ~vrite.
31 DAPTAR PUSTAKA Bargava B. 1999. Concurrency Control in Database Systems. IEEE Transaction on Knowledge and Data Engineering 1l(1): 3-1 6.
http :l/citeseer.ist.psu.edulbhargava99concurrency.html. [ 28 Oktober 20051.
Bernstein PA, Hadzilacos V, Goodman N. 1987. Concurrency Control and Recovery in Database Systeirt. New York: Addison-Wesley Publishing
Company. hlm. 25-37. Connoly T, Begg C. 2002. Database Systenl : A Practical Approach to Design, Iittplernentation, and Managenlent. New York : Addison -Wesley
Publishing Company. him. 14-18. Ellnasri R, Navathe S B. 2000. Fundarnental of Database Systems. New York : Addison -Wesley Publishing Company. hlm. 662-668. Law AM, Kelton WD. 1991. Sirritllation Modelling and Analysis. Ed ke-2. Singapore: Mc Graw Hill Inc. him. 289. Ozsu MT, Valduriez P. 1999. Principle of DistribzttedDatabase Systenzs, Ed ke-2. New Jersey: Prentice Hall. hlm. 300-3006. Shi VTS, Perrizo W. 2004. Read-commit Order for Concurrency Control in Centralized High Performance Database Systems. Inforntation Jozdrnal of International Infornlatior Insitute 7(1): 95-106.
Silberschatz A, Henry F K, Sudarshan S. 1997. Database Systent Concepts. Ed ke-3. New York : McGraw -Hill. hlm. 13-14.
Lampiran 1 Hasil Uji t-student perbedaan throzrghput antara algoritma ROCC dan ROCCM
Keterangan :
- Derajat bebas (dj = (n~i-nz-2) =(5 + 5 -2) =8
Lampirail 2 Listing program roccm.cpp #include
#pragma hdrstop #include "ROCCM.hV #include "Unitl.hU gpragma package (smart-init) //-/-------------------------------------------------------------//PURPOSE: construct of Class Rocc, //initilize the paramters when a new object is created //DATA STRUCTURES: Variable G - GENERATOR type, declared in //common.h (IN) //CALLING SEQUENCE: when a new object is created by using 'new'
//----------------------------------------------------------------
Roccm::Roccm~/*in*/const GENERATOR &G):MySimu(G) //PRE : assign G //POST: g==G I
g=G;//initialize the parameter 'g' which is from user interface
I //----------------------------------------------------------------
//PURPOSE: default construct of Class Roccm, //no parameters are initilized as a new object is created //DATA STRUCTURES: //CALLING SEQUENCE: called when a new object is created by using //'new' Roccm: : Roccm I )
I //---------------------------------------------------------------//PURPOSE: destruct of Class Roccm, //release the object memory //DATA STRUCTURES: //CALLING SEQUENCE: called when a new object is released by //'delete' //----------------------------------------------------------------
Roccm: : - R O C (~I ~ i
I //----------------------------------------------------------------
//PURPOSE: Execute a operation of accessing disk resource //Generate a CPU facility accessing event if data items are in //BUFFER //Generate a DISK facility accessing event if data items are not //in BUFFER //DATA STRUCTURES: Variable token - inttype, token id of a //transaction (IN) //Variable trans - Roccm-TRANS type, declared in R0ccm.h // Variable e - EVENT type, declared in R0ccm.h
//CALLING SEQUENCE: called when a transaction accesses disk //resources //----------------------------------------------------------------
void Roccm: : accessDisk (/*in*/int token) //PRE: Assign Oacess-nums==t->accessQ.size() // t->accessQ is empty // t-2workStatus is updated to COMMIT if all read requests are
// //
finished Add events to eventList
[ ROCCM-TRANS *t=&trans[tokenl; //make read or write disk schedules t->access-nums=t->accessQ.sizeO; //the size of items while(!t->accessQ.emptyO) ( int res=t->accessQ.frontO; //get items t->accessQ.pop-front(); if(t->workStatus!=COMMIT & & isInBuffer0) //read only I e.fd=CPU-Q; e.type=ARRIVAL; else I e.fd?DISK-Q[diskID(res)l; e.type=REQUEST; )
e.Token.id=token; e.Token.pty=O; e.Token.mParam.updated=false; e.clock=getTime I ) ; schedule (el ;
i if(t->workStatus==COMMIT) //finish updating resource ( t->iqorkStatus=UPDATE; return; if(++t->request-id==t-5maxXrequests) / / finish all read requests, become COMMIT status
t->workStatus=COMMIT; else //assign the next request to accessQ t->accessQ=t->requestQ[t->request-id];
I bool Roccm::diskFinished(int token) return .(--trans[token].access-nums==O)
;
1 bool Roccm::isUpdated(int token) I
return (trans[token] .workStatus==UPDATE); 1 //----------------------------------------------------------------
//PURPOSE: generate a CC-Q event when facility of CPU finish its //service to a token //DATA STRUCTURES: Variable token - int type, token id of a //transaction(IN)
//Variable e - EVENT type, declared in simu.h //CALLING SEQUENCE: when CPU facility departure a token //---------------------------------------------------------------void Roccm::cpu(/*in*/int token) //PRE: assign token, and O workStatus==ACTIVE) e.clock+=expon(g.int-think-time); //think time e.Token.id=token; e.Token.pty=O; schedule (e); 1 //----------------------------------------------------------------
//PURPOSE: execute concurrency control(R0CC) algorithm //DATA STRUCTURES: Variable token - int type, token id of a //transaction(IN) //Variable trans[] - ROCC-TRANS type, declared in R0ccm.h //Variable RCQ - listCRC-QUEUE> type, declared in R0ccm.h //CALLING SEQUENCE: called when CC facility departure a token //ALGORITHM: //---------------------------------------------------------------void Roccm::cc(/*in*/int token) //PRE: Assign token, Orequest-id; //check work status switch(t->workstatus) ( case INITIAL: generate1 (t); case RESTART: t->workStatus=ACTIVE; case ACTIVE: I rcq.type=-READM; RCQM.push-back(rcq); accessDisk(token); break; i case COMMIT: ( rcq.type=-COMMITM; RCQM.push-back(rcq); if (validate(token)) //successful,update resource ( if(!t->writeQ.emptyl))//it is not read only
update (token); else 1 commit(token); refreshRCQ0 ;
//read only, commit directly //refresh RCQ
1 else //unsuccessful, restart the trasaction ( restart(token); //restart delRCQ-Token (token); )
break; )
case UPDATE:
//updated transaction
(
commit (token); refreshRCQ ( ) ;
//cornit the transaction //refresh the RCQ
1 )
//PURPOSE: Refresh RCQ when a tranasaction is commited. //Deleting a token from RCQ if it commit point is on the top of //RCQ //DATA STRUCTURE: Variable RCQ - RC-QUEUE type, declared in //Roccm.h //CALLING SEQUENCE: called when a transction commited //----------------------------------------------------------------
void Roccm::refreshRCQO //POST: remove the front of RCQ, if the transaction was validated (
while ( RCQM.front 0.type==-VALIDATEDM) RCQM.pop-front 0 ;
//PURPOSE: judge if two concurrent transactions conflict, RW & WW //confliction //DATA STRUCTURES:Variable readQl list<> type,read resources of //transaction1 (IN) //Variable writeQl - list<> type,write resources of //transaction1 ( I N ) //Variable readQ2 - listo type,read resources of //transaction2 (IN) //Variable writeQ2 - list<> type,write resources of //transaction2(IN) //CALLING SEQUENCE: called when a transaction accesses disk //resources //----------------------------------------------------------------
-
boo1 Roccm::conflicted(/*in*/list readQl, /*in*/list writeQl,/*in'/list readQ2, /*in*/list writeQZ,list tempQ 1 //PRE: Assign readQl,readQ2,writeQ11writeQ2 //writeQl is a subset of readQ1, writeQ2 is a subset of readQ2 //POST:Return 1, if (readQltwriteQ1) is conflict with / / (readQZtwriteQ2)
//
Return 0, otherwise
//compare readQi & writeQ2 if(!readQl.empty() & & !writeQZ.emptyO) for ( itrl=readQl.begin( ) ;itrl ! = readQ1 .end( ) ;itrl++) for( itr2=writeQZ.beginO;itr2!=writeQZ.endO;itr2++) if(*itrl==*itrZ) return 1; //read & & write conflicted //compare readQ2 & writeQl if(!readQ2.emptyO & & !writeQl.emptyO) for( itrl=readQZ.beginO;itrl!=readQZ.end~);itrl+t) for( itr2=writeQi.beginO;itr2!=writeQl.end();itr2++) if(*itrl==*itr2) return 1; //write & & read conflicted //compare tempQ & writeQl if (!tempQ.empty0 & & !writeQl.emptyO ) for( itri=tempQ.beginO;itrl!=tempQ.end();itrl++) for( itr2=writeQl.beginO;itr2!=~riteQl.endO;itrZ++) if(*itrl==*itrZ) return 1; //write & & read conflicte //compare tempQ & writeQ2 if (!tempQ.emptyO & & !i.iriteQZ.emptyO) for( itrl=tempQ.beginO ;itrl!=ternpQ.endO ;itri++) for( itr2=writeQZ.beginO;itrZ!=writeQ2.end();itr2++) if(*itrl==*itr2) return i;//write & & read conflicte //compare tempQ & read02 if(!tempQ.empty() & & !readQZ.emp-yO) for( itrl=tempQ.beginO ;itrl!=teapQ.end();itrl++l for( itr2=readQ2.beginO;itr2!=readQ2.endO;itrZ+t) ifl*itrl==*itr2) return 1; //write & & read conflicte return 0; //no conflicted 1
//----------------------------------------------------------------
//PURPOSE: update resource //DATA STRUCTURES:Variable token - int type, token id of a //transaction(IN) //Variable trans[] - ROCC-TRANS type, declared in R0ccm.h //CALLING SEQUENCE: called when a transaction update the resources //----------------------------------------------------------------
void Roccm: :update(int token) //PRE: assign OwriteQ is empty (
ROCCM-TRANS *t=&trans [token]; if(t->writeQ.empty()) return; t->accessQ=t->writeQ; accessDisk(t0ken); 1
3S //PURPOSE: combine the requesc resources into readQ and writeQ //DATA STRUCTURES:Variable trans[] - ROCC-TRANS type, declared in / /Roccm.h //Variable rcq - RC-QUEUE type,declared in Roccm.h(IN) //A element of rcq //Variable readQ - list type, declared in <list> (OUT) //read resoures of the transac~ion //Variable writeQ - write resources of the transaction(0UT) //CALLING SEQUENCE: called when a transaction combine its //request (s) //----------------------------------------------------------------
void Roccm::combineRequests~/-in*/RCM-QUEUE rcq, /*out*/list &readQ,list&writeQ) //PRE: Assign token ,request-id(O<=request-id<=max-requests). //POST: Combine t->requestQIrcq.request-id] into readQ if it is //read request point //Combine t->writeQ into writeQ if it is update request point //Combine all resources(read & write) into readQ & writeQ, if it //is validated point { ROCCM-TRANS *t=&trans[rcq.tokenl; list::iterator itr; list::iterator itr2; list writeQl; / / for(itr2=writeQl.begin();itr2!=writeQl.endO;itr2++) / if(*itr!=*itr2) (//combineRequests(*itr,readQ2,writeQ2); // 1 switch(rcq.type) [ case -READM: ( //all read resources are combined,just read request point for( itr=t->requestQ[rcq.request-idl.begin0; itr!=t->requestQ[rcq.request-idl.endO;itr++) readQ.push-back(*itr); break; case -COMMITM: [ / / commit point , writeQ=t->writeQ; break;
ncc validated
)
case -VALIDATEDM: (
1 for( itr=t->writeQ.begin(); itr!=t->writeQ.endO;itr++) writeQ.push-back(=itr); break;
//--------------------------------------------------------------//PURPOSE: combine the current request resources into //requestQ(readQ or writeQ1
//DATA STRUCTURES:Variable trans[] - ROCC-TRANS type, declared in //Roccm.h //Variable rcq - RC-QUEUE type,declared in Roccm.h(IN) //A element of rcq //Variable requestQ - list type,declared in <list> (OUT) //CALLING SEQUENCE: called when.a transaction comhines the current //request //---------------------------------------------------------------void Roccm::combineOneRequest(/*in*/RCM~QUEUErcq, /*out*/list &requestQ) //PRE: Assign request-id(O<=request-id<=max_requests). //POST:Combining t->requestQ[rcq.request-id] into requestQ, if it //is read point //Combining t->writeQ into requestQ, if it is commit or validate //point. {
ROCCM-TRANS *t=&trans[rcq.tokenl; list::iterator itr; switch(rcq.type) ( case -READM: { //all read resources are combined,just read request point for( itr=t->requestQIrcq.request~idl.beginO; itr!=t->requestQ[rcq.request-idl.end();itr++) requestQ.push-back(*itr); break;
I case -COMMITM: case -VALIDATEDM:
//stuck point ,updated resources
I
requestQ=t->writeQ; break;
I t
I //---------------------------------------------------------------//PURPOSE: validate the transaction //DATA STRUCTURES: Variable token - int type, token id of a //transaction(IN) //CALLING SEQUENCE: called when CC validate a transaction
boo1 Roccm::validate(int token) //PRE: Assign token //POST:return 1, if the transaction has no conflict with others //return 0 , if the transaction has conflict with others (
//check to see if have a circle conflict //stop at conflict point in the RCQ list::iterator itr; //if(downToUpConflicted(token,itr) ) // if (upToDownConflicted(token,itr))
if (upToDownConflicted(token,itr) if(downToUpConflicted(token, itr) ) return 0; //circle conflicted
..
//PURPOSE: Find the conflict point in RCQ from up to down and //stop at conflict point if it has, otherwise stop at commit point //DATA STRUCTURES:Variable token - int type, token id of a //transaction(IN) //Variable itr - interator type,the cursor of RCQ (OUT) //CALLING SEQUENCE: called when a transaction is validated //---------------------------------------------------------------boo1 Roccm::upToDownConflicted(int token,list::iterator &itr) //PRE: Assign token //POST: Return 1 ,itr. conflict happen. //Return 0, itr. otherwise commit point. //Remove read points of the transaction in RCQ, if no //conflict (
list readQ,writeQ/*,tempQ*/; //skip the first point RCM-QUEUE rcq; for (itr=RCQM.begin();itr!=RCQM.endO ;itr+t) if((*itr).token==token) //find the first request point break; for(itr=itr;itr!=RCQM.endO;itr++] (
if ( (*itr).token==token) //find the token if ( (*itr). type==-COMMITM) ( //the last request(write request), no upToDown conflict [ updateRCQ-Typelitr); //set validated flag in RCQ return 0;
1 //read requests combineOneRequest(*itr,readQ);
rcq=*itr; //protect *itr itr--=RCQM.erase(itr); //delete this point from RCQ
t
else if ((*itr). type==-VALIDATEDM) / / cornbineRequests(*itr,readQ2,writeQl); //possible conflict point, readQl & writeQ2 { writeQ.clear0; combineOneRequest(*itr,writeQ); listemptyQ;emptyQ.clearO; if(conflicted(emptyQ,readQ,emptyQ,emptyQ,writeQ)) // if(conflicted(readQ,emptyQ,emptyQ,writeQ) ) ( rcq. type=-VALIDATEDM; RCQM.insert (itr,rcq); return 1;
I 1
I return 0 ; \
//------------------------------------------------------------//PURPOSE: Find the conflict point in RCQ from down to up and
//stop at conflict point if it has, otherwise stop at up to down //conflict point //DATA STRUCTURES:Variable token - int type, token id of a //transaction (IN) //Variable itr - interator type,the cursor of RCQ (IN) //CALLING SEQUENCE: called when a transaction is validated //---------------------------------------------------------------boo1 Roccm::downToUpConflicted(int token,list::iteratog itr) //PRE: Assign token, itr //POST: Return 1, if conflict exist //Return 0, no conflict exist //Remove read points of the transaction in RCQ, if no conflict list readQl,writeQl, list::iterator itrtemp; itrtemp = itr;
readQZ,writeQ2,ternpQ;
for(itr=RCQM.endO;itr!=itrtemp;itr--) (
if( (*itr).token!=token) (
listemptyQ;emptyQ.clearO; tempQ.push-back ( ( (*itr). token!=token)) ; if ((*itr) .type== -READM) (if(conflicted(tempQ,emptyQ,writeQl,emptyQ,writeQ2)) (
combineRequests(*itr,readQ2,writeQ2);
tempQ.clear ( ) ; 1 )
(
combineRequests(*itr,readQ2,writeQ2); tempQ.clear 0 ; )
if ((*itr).type== VALIDATEDM (
&&
-READMI
if(conflicted(tempQ,emptyQ,writeQ1,emptyQrwriteQ2)) (
combineRequests(*itr,readQ2,writeQ2);
tempQ.clear ( ) ;
i i if ((*itr).type== -VALIDATEDM (
&L
-COMMITM)
if(conflicted(tempQremptyQ,writeQ1,readQ2,writeQ2)) (
combineRequests(*itr,readQ2,writeQ2);
tempQ.clear ( )
;
1
1 tempQ.clear ( ) ;
else //other request points ( combineRequests (*itr,readQ1,writeQ1); //ckeck to see if conflicted
listemptyQ;emptyQ.ciear();
if (conflicted(emptyQ,readQl,writeQl,readQ2,writeQ2)) return 1; else //no conflict, erase the request from RCQ itr--=RCQM.erase(itr); )
1
return 0; )//---------------------------------------------------------------
//PURPOSE: update the element type of RCQ //DATA STRUCTURES:Variable RCQ - list type,declared in //Roccm.h //Variable itr - iterator type (IN) //CALLING SEQUENCE: when RCQ is updated //--------------------------------------------------------------void Roccm::updateRCQ-Typeilist::iterator itr) //PRE: Assign itr //POST: (*itr).type==-VALIDATED
i RCM-QUEUE rcq=(*itr); rcq.type=-VALTDATEDM; itr=RCQM.insert(RCQM.erase(itr),rcq); 1
//----------------------------------------------------------------
//PURPOSE: Execute the operation of commit of the transaction int type, token id of a //DATA STRUCTURES:Variable token //transaction(IN) //Variable trans[] - ROCC-TRANS type, declared in R0ccm.h //Variable e - EVENT type, declared in simu.h //Variable sysStabled boolean type, declared in mysimu.h //Variable activeTrans - int tyep, declared in mysimu.h //Variable tokenQ - list type, declared in mysimu.h //CALLING SEQUENCE: called when a transaction is commited //---------------------------------------------------------------void Roccm::commit(int token) //PRE: Assign token //POST: Commit a transaction / / - reuse the transaction id, generate a new resource / / - t->id go into token queue, or go into readyQ if readyQ is //empty // - enable a new transaction go into system // - increase commited transaction numbers // - activeTrans==activeTrans-1; ( //initial the transaciton,and reuse its t->id ROCCM-TRANS *t=&trans[tokenl; t->id=token; t->workStatus=INiTIAL;
-
-
//make a schedule token into readyQ if(idleServer(READY-Q)) I e . fd=READY-Q; e.type=ARRIVAL; e.clock=getTimeO; e.Token.id=token; e.Token.pty=O; schedule (e);
43 if(sysStab1ed) printText("Warning: ReadyQ is empty");
1 else //otherwise go into tokenQ tokenQ.push-back (token); if(activeTrans==mpl & & !idleServer(READY-Q)) //make a DEPARTURE schedule and a new token go into the system //wake up readyQ ( e . fdCREADY-Q; e.type=DEPARTURE; e.clock=getTirne( ) ; e.Token=getServerToken(READY-Q,l); schedule (e); 1 if (sysstabled) calcCommit (t->start-time1 ; activelrans--; 1 //---------------------------------------------------------------//PURPOSE: Execute the operation of restart of the transaction //DATA STRUCTURES:Variable token - int type, token id of a //transaction (IN) //Variable trans[] - ROCC-TRANS type, declared in R0ccm.h //Variable e - EVENT type, declared in simu.h //Variable sysStabled - boolean type, declared in rnysimu.h //Variable activeTrans int tyep, declared in mysimu.h //CALLING SEQUENCE: calle when a transaction is restarted //----------------------------------------------------------------
-
void Roccm::restart(int token) //PRE: Assign token //POST: - restart a transaction,that is make a READY-Q ARRIVAL //event. // - it's id and request resources do not change. // - increase restart numbers // - enable a new transaction go into System // - remove the flag point from RCQ // - activeTrans==activeTrans-1; ROCCM TRANS *t=&trans[tokenl; t->accessQ=t->requestQLOi;
t->request-id=O; //make a schedule into readyQ e.fd=READY-Q; e.type=ARRIVAL; e.clock=getTime 0 ; e.Token.id=token; e.Token.pty=O; schedule(e) ; if(activeTrans == mpl & & !idleServer(READY-Q)) //make a DEPARTURE schedule and a new token go into the system { e.fd=READY-Q; e.type=DEPARTURE; e.clock=getTime ( ) ; e.~oken=getServerToken(READY-Q,l);
schedule (el;
i if(sysStab1ed) calcRestart0;
//---------------------------------------------------------------.
//PURPOSE: Remove all point of the token from RCQ //DATA STRUCTURES:Variable token int type, token id of a //transaction (IN) //Variable RCQ - list type, declared in R0ccm.h //CALLING SEQUENCE:called when a transaction is restarted //---------------------------------------------------------------
-
void Roccm: : delRCQ-Token (int token) //!?RE: Assign token //POST: all flag points of the token is deleted from RCQ I
//delete the token from the RCQ for(list::iterator itr=RCQM.begin(); itr!=RCQM.end();itr++) if( (*itr).token==token) itr--=RCQM.erase(itr);
I
//PURPOSE: get a disk id number //DATA STRUCTURES:Variable res[l - ROCC-RESOURCE type, declared in //Roccm. //Variable n - int type. id of the item n //CALLING SEQUENCE:called when a transaction is restarted //---------------------------------------------------------------int Roccm: :diskID(int n) //POST: return a disk id for item n (
return res [nl .disk-id;
t //---------------------------------------------------------------//PURPOSE: Generate token id for all transactions as well as //initialize //DATA STRUCTURES:Variable tokenQ - listtype,saves token id //of all transactions //Variable trans[] - ROCC-TRANS type, declared in R0ccm.h //save the attributes of transactions //Variable res[] - ROCC-RESOURCE type, declared in R0ccm.h //CALLING SEQUENCE:called at the beginning of simulating //-_--------------------------------------------------------------
void R0ccm::generateO //POST:Add token id into tokenQ and trans[l.id // Assign resl].disk-id randomly // RCQ is empty. {
//initialize random seed time-t T; srandl lunsianed) time(&T));
t++;
tokenQ.push-back (t->id]; //next transaction
t //initialize resource array for(int i=O;i
;
//clear RCQ
I
//PURPOSE: Initialize the attributes of a transaction. //DATA STRUCTURES:Pointer *t - ROCC-TRANS type,declared in r0oc.h // Pointer to trans [I (INOUT) //CALLING SEQUENCE:called when a transaction is committed or first //time go into system //---------------------------------------------------------------*ti void Roccm: : generate1 (/*~~ou~*/RoccM-TRANS //PRE: Assign t which pointers to translt->id] //POST:initilize trans[t->id]. // t->workStatus==INITIAL // .. t->acces-nums==O // t->accessQ is assigned (
//work status t->access-nums=O; //the accessing item numbers of a request t->r.iorkStatus=INITIAL;
//generate the request resources for(int i=O;irequestQ[il.clearO; //clear requestQ array //clear accessQ t->accessQ.clear~l; //clear writeQ t->writeQ.clear0; //initialize request-id t->request-id=O; generateRes(t); //generate resources randomly t->accessQ=t->requestQ[OI; //initialize accessQ
I //----------------------------------------------------------------
//PURPOSE: Generate read&write resources of a transaction randomly //DATA STRUCTURES:Pointer *t - ROCC-TRANS type,declared in r0oc.h // Pointer to trans [I (INOUT) //CALLING SEQUENCE:called when a transaction is commited or first //time go into the system /y---------------------------------------------------------------void Roccm::generateRes(/*inout*/ROCCM-TRANS //PRE: Assign t which pointers to trans[] //POST: t->requestQ[] is assigned // t->writeQ is assigned // t->max-requests==g.max-requests // t->request-id==0
*t)
(
//generate the resources of transaction between max-size and //min-size list transResQ=randomResources(l; //generate request
int one-request-nums; int accessRes; for(int j=O;j
*
~~
for(int i =O;iwriteQ.push-back(accessRes); t->requestQ[t->request-id].push-back(accessRes);
I if(!t->requestQIt->request-idl.empty0) break;
transResQ=tempQ;
I t->request-id++; 1
t->max-requests=t->request-id; //put the rest resource into t->requestQ while(!transResQ.emptyO) 1 accessRes=transResQ.front(); transResQ.pop-front(); t->request@[t->request~id-l].push~back(accessRes); 1 t->request-id=O;
i //---------------------------------------------------------------//PURPOSE: get start-time-stamp of a transaction //DATA STRUCTUXES: Variable token - int type, token id of a //transaction !IN) //CALLING SEQUENCE: called when a transaction is generated //---------------------------------------------------------------void Roccm::getStartTime(int token) //PRE : Assigc token //POST: trans[cokenl.start-time== the current time of system i trans[token].start-time=getTimeO; )
Lampiran 3 Listing program roccm.h
ifndef BOCCWH Kdefine ROCCMH //---------------------------------------------------------------#include "MySimu.hV #include "Fi1el.h" Itinclude "rocc.h" class ROCCM-TRANS:public TRANS (
public: list requestQ[MAX-REQUESTSl;//read requests list accessQ; //resource queue for one time accessing disk list writeQ; //update or write resources i; struct ROCCM-RESOURCE 1
int disk-id;
//the disk id to which the res belong
)i
enum RCQM-TYPE!-READM,-COMMITM,-VALIDATEDM); struct RCM-QUEUE ! int token; inc request-id; RCQM-TYPE type; 1;
//associated token //the request id of the transaction //the type of operation
class Roccm : public MySimu i public: Roccrn(c0nst GENERATOR & G ) ; //constructor Roccm ( ) ; -Roccrn ( ) ; //destructor private: void generate(); //Randomly generate the id of transactions //generate one transaction void generatel(R0CCM-TRANS *t); void generateRes(R0CCM-TRANS *t); void cpu (int token); //the operation of cpu void cc(int token); //the operation of cc //access disk resources void accessDisk (int token); boo1 validate(int token); //delete the token from RCQ void delRCQ-Token(int token); void update (int token); //update resources of the token //restart a tranasction void restart(int token); //commit a transaction void commit (int token)i //the disk id of a res n int diskID(int n); void combineRequests(RCM-QUEUE rcq, list &readQ,list&writeQ);
//combine all requests for a transaction void combineOneRequestl/*in*/~CM-QUEUE rcq,/*outi/list &requestQ); //combine one request for a transaction bool conflicted(list readQl,list writeQl,list readQ2,list writeQ2,listtempQ); //check if resources are conflicted bool upToDownConflictedlint token,/*inout*/list::iterator &itr); //check if conflicted happen in RCQ from up to down bool downToUpConflictedlint token,/*in*/list::iterator itr); //check if conflicted happen in RCQ ffrom down to up void updateRCQ Type(list::iterator itr); //update the type of RCQ element into validated void getStartTime(int token); void refreshRCQ 1) ;
//delete useless token from RCQ
bool diskFinishedlint token); bool isupdatedlint token); list RCQM;
//RC queue
ROCCM-TRANS trans[MAXSIZE-TRANS]; //transactions array ROCCM-RESOURCE res[MAXSIZE-DB]; //database resources
I; #endif
Lampiran 4 Listing program rocc.cpp #include #pragma hdrstop #include "rocc.hU #include "unit1.h" #pragma package (smart-initl //---------------------------------------------------------------. //PURPOSE: construct of Class Rocc, //initilize the paramters when a new object is created //DATA STRUCTURES: Variable G - GENERATOR type, declared in //common.h (IN) //CALLING SEQUENCE: when a new object is created by using 'new' //---------------------------------------------------------------Rocc::Rocci/"in*/const GENERATOR &Gl:MySimu(G) //PRE : assign G //POST: g==G ! g=G;//initialize the parameter 'g' which is from user interface ! //-----------------------------------:----------------------------
//PURPOSE: default construct of Class Rocc, //no paramerers are initilized as a new object is created //DATA STRUCTURES: //CALLING SEQUENCE: called when a new object is created by using //'newv //--------------------------------------------------------------Rocc: : Rocc ( !
i //PURPOSE: destruct of Class Rocc, //release che object memory //DATA STRUCTURES: //CALLING SEQUENCE: called when a new object is released by //'delete'
//------------------------------------------------------------
ROCC: : - R O C (~I
L i //---------------------------------------------------------------//PURPOSE: Execute a operation of accessing disk resource //Generate a CPU facility accessing event if data items are in //BUFFER //Generate a DISK facility accessing event if data items are not //in BUFFER //DATA STRUCTURES: Variable token - int type, token id of a //transaction (IN) //Variable trans - ROCC-TRANS type, declared in r0cc.h //Variable e - EVENT type, declared in r0cc.h //CALLING SEQUENCE: called when a transaction accesses disk
void Rocc::accessDisk(/*in*/int token) //?RE: Assign Oacess-nums==t->accessQ.size() //t->accessQ is empty //t->workstatus is updated to COMMIT if all read requests are //finished //Add events to eventList (ROCC-TRANS *t=&trans[token]; //make read or write disk schedules t->access nums=t->accessQ.sizeO; //the size of items while ( ! t-Yaccess~. empty ( ) ) lint res=t->accessQ.frontO; //get items t->accessQ.pop-front(); if(t->workStatus!=COMMIT & & isInBuffer0) //read only ( e.fd=CPU-Q; e.type=ARRIVAL;
I else [ e.fd=DISK QIdiskID1res)J; e .t y p e = ~ ~ a u ~ s ~ ;
I e.Token.id=token; e.Token.pty=O; e.Token.mParam.updated=false; e.clock=getTimeO; schedule (e);
I if(t->workStatus==COMMIT) //finish updating resource [ t->workStatus=UPDATE; return; 1 if(++t->request-id==t->rnax-requests1 / / finish all read requests, become COMMIT status
t->workStatus=COMMIT; else //assign the next request to accessQ t->accessQ=t-XequestQlt->request-id]; 1 boo1 Rocc::diskFinished(int token) return (--trans[token].access~nums==Ol; )
boo1 Rocc::isUpdated(int token)
I return (trans[tokenl.workStatus==UPDATE);
1 //---------------------------------------------------------------//PURPOSE: generate a CC-Q event when facility of CPU finish its //service to a token //DATA STRUCTURES: Variable token - int type, token id of a //transaction(IN) //Variable e EVENT type, declared in simu.h
-
//CALLING SEQUENCE: when CPU facility departure a token //------------------------------------------------------------void Rocc::cpu(/*in*/int token) //PRE: assign token, and 0 workStatus==ACTIvE) e.clock+=expon(g.int-think-time); //think time e.Token.id=token; e.Token.pty=O; schedule (e); 1
,, //PURPOSE: execute concurrency control(R0CC) algorithm //DATA STRUCTURES: Variable token - int type, token id of a //transaction (IN) //Variable trans[] - ROCC-TRANS type, declared in r0cc.h //Variable RCQ - list type, declared in r0cc.h //CALLING SEQUENCE: called when CC facility departure a token //---------------------------------------------------------------void Rocc::cc(/*in*/int token) //PRE: Assign token, Orequest-id;
//check work status switch(t->workstatus) ( case INITIAL: generatel it); case RESTART: t->workStatus=ACTIVE; case ACTIVE: ( rcq.type=-READ; RCQ.push-backlrcq) ; accessDisk(token); break; 1 case COMMIT: ( rcq.type=-COMMIT; RCQ.push-back (rcq); if (validate(token)) //successful,update resource {
if(!t->writeQ.empty())//it is not read only
update (token); else commit (token); refreshRCQ 0;
//read only, commit directly //refresh RCQ
! else //unsuccessful, restart the trasaction ( restart (token); //restart delRCQ-Token (token); break;
case UPDATE:
//updated transaction
i c o m i t (token); refreshRCQ ( ) ;
//cornit the transaction //refresh the RCQ
1
,,
//PURPOSE: Refresh RCQ when a tranasaction is commited. // Deleting a token from RCQ if it commit point is on the top of RCQ //DATA STRUCTURE: Variable RCQ - RC-QUEUE type, declared in r0cc.h //CALLING SEQUENCE: called when a transction commited //----------------------------------------------------------------
void Rocc::refreshRCQ() //.POST: remove the front of RCQ, if the transaction was validated (
//----------------------------------------------------------------
//PURPOSE: judge if two concurrent transactions conflict, RW G NW //confliction //DATA STRUCTURES:Variable readQl - list<> type,read resources of //transactionl(IN) //Variable writeQl - list<> type,write resources of //transaction1(IN) //Variable readQ2 - list<> type,read resources of //transactionZ(IN) //Variable writeQ2 - list<> type,write resources of //transaction2(IN) //CALLING SEQUENCE: called when a transaction accesses disk //resources //---------------------------------------------------------------boo1 Rocc::conflicted(/*in*/list readQ1, /*in*/list writeQl,/*in*/list readQ2, /*in*/list writeQ2) //PRE: Assign readQl,readQZ,writeQl,writeQZ //writeQl is a subset of readQ1, writeQ2 is a subset of readQ2 //POST:Return 1, if (readQl+writeQl) is conflict with / / (readQZiwriteQ2) // Return 0, otherwise ( list::iterator itrl,itr2; //compare readQl & writeQ2 if(!readQl.empty() & & !writeQZ.emptyO) for( itrl=readQl.begin(!;itrl!= readQl.endO;itrl++) for( itr2=writeQ2.beginO;itr2!=writeQ2.endO ;itr2++) if(*itrl==*itr2) return 1; //read & & write conflicted
for( itrl=readQ2.beginO;itrl!=readQ2.endO;itrl++) for( itr2=writeQl.beginO;itr2!=writeQl.endO;itr2++) if(*itrl==*itrZ) return 1; //write & & read conflicted return 0;
//no conflicted
I //---------------------------------------------------------------//PURPOSE: update resource //DATA STRUCTURES:Variable token - int type, token id of a //transaction (IN) //Variable trans[] - ROCC-TRANS type, declared in r0cc.h //CALLING SEQUENCE: called when a transaction update the resources //---------------------------------------------------------------void Rocc: :update(int token) //PRE: assign Owrite0 is empty i ROCC-TRANS *t=&trans[token];
if(t->writeQ.emptyO) return; t->accessQ=t->writeQ; accessDisk (token); 1 //----------------------------------------------------------------
//PURPOSE: combine the request resources into readQ and writeQ //DATA ST8UCTURES:Variable trans[] - ROCC-TRANS type, declared in //rocc.h //Variable rcq - RC-QUEUE type,declared in rocc.h(IN) //A element of rcq //Variable readQ - list type, declared in <list> LOUT) //read resoures of the transaction //Variable writeQ - write resources of the transaction(OUT1 //CALLING SEQUENCE: called when a transaction combine its //request ( s ) //---------------------------------------------------------------void Rocc::combineRequests(/*in*/RC-QUEUE rcq, /*out*/list &readQ,list&writeQ) //PRE: Assign token ,request-id(O<=request-id<--ax-requests). //POST: Combine t->requestQfrcq.request-id] into readQ if it is //read request point //Combine t->write(! into writeQ if it is update request point //Combine all resourcesLread & write) into readQ & writeQ, if it //is validated point ( ROCC-TRANS *t=&trans[rcq.tokenl; list::iterator itr; switch (rcq.type1 ( case -READ: ( //all read resources are combined,just read request point for( itr=t->requestQ[rcq.request-idl.begin0; itr!=t->requestQ[rcq.request-id].end();itr++)
readQ.push-back(*itr); break; 1 case -COMMIT: [ / / commit point , not validated writeQ=t->writeQ;
break; 1 case -VALIDATED: ( for(int i=O;imax-requests;icc) for( itr=t->requestQ[i].begin();itr!= t- >requestQ[il .end();itrt+) readQ.push-back(*itr); for( itr=t->writeQ.beginO; itr!=t->writeQ.end();itr++) writeQ.push-back(*itr); break; 1
//---------------------------------------------------------------//PURPOSE: combine the current request resources into //requesrQ(readQ or writeQ) //DATA STRUCTURES:Variable trans[] - ROCC-TRANS type, declared in //rocc.h //Variable rcq - RC-QUEUE type,declared in rocc.h(IN) //A element of rcq //Variable requestQ - list type,declared in <list> (OUT)//CALLING SEQUENCE: called when a transaction combines the current //requesr: //---------------------------------------------------------------void Rocc::combineOneRequest(/*in*/RC~QUEUErcq, /*out*/list &requestQ) //PRE: Assign request~id(0<=request~id~=rnaxXrequests). //POST:Combining t->requestQ[rcq.request-id] into requestQ, if it //is read point //Combining t->writeQ into requestQ, if it is commit or validate //point. ( ROCC-TRANS *t=&trans[rcq.tokenl; list::iterator itr;
type) switch (rcq. .( case -READ: ( //all read resources are combined,iust read request point
break; 1 case -COMMIT: case -VALIDATED:
//stuck point ,updated resources
(
requestQ=t->writeQ; break; 1
1 t //---------------------------------------------------------------//PURPOSE: validate the transaction //DATA STRUCTURES: Variable token - int type, token id of a //transaction (IN) //CALLING SEQUENCE: called when CC validate a transaction
//-------------------------------------------------------------
bool Rocc: : valida~elint token) //PRE: Assic?. token //POST:retur?. 1, if the transaction has no conflict with others //return 0, if the transaction has conflict with others
I //check ~2 see if have a circle conflict //stop ac conflict point in the RCQ listEUE>::iterator itr; if (upToDcunConflicted(token,itr)) ifldo~~ToUpConflicted(token,itr)) ret.xrn 0; //circle conflicted return 1; )
//----------------------------------------------------------------
//PURPOSE: Find the conflict point in RCQ from up to down and //stopat ccxflict point if it has, otherwise stop at commit point token - int type, token id of a //DATA STRUC:URES:Variable //transactic2(IN) //Variable irr - interator type,the cursor of RCQ (OUT) //CALLING SEWENCE: called when a transaction is validated //---------------------------------------------------------------bool Rocc::c?ToDownConflicted~int token,list::iterator &itr) //PRE: A s s i ~ 7token //POST: Retcrn 1 ,itr. conflict happen. //Return 0, itr. otherwise commit point. //Remove rea5 points of the transaction in RCQ, if no conflict ( list readQ,writeQ; //skip ttc first point //protect the former value of *itr RC-QUEUE rcq; for (itr=F.ZQ.beginO;itr!=RCQ.end();itr++) if ( ("ixr).token==token) break; for(itr=irr;itr!=RCQ.end();itr++) ( if((*irr).token==token) //find the token ( if(:*itr).type==-COMMIT) //the last request(write request), no upToDown conflict ( .>pdateRCQ-Type (itr); //set validated flag in RCQ return 0; 1 //read requests co~3ineOneRequest(*it??, readQ); rcc=*itr; //protect *itr itr--=RCQ.erase(itr); //delete this point from RCQ
I else if ((*itr).type==-VALIDATED) //possLble conflict point, readQl ( wri:eQ.clearO; coi;jineOneRequest(*itr,writeQ);
&
writeQ2
lisremptyQ;emptyQ.clearO; if(conflicted(readQ,emptyQ,emptyQ,writeQ)) {
rcq.type=-VALIDATED; 3CQ. insert (itr,rcq); return 1;
1 i return 0; 1 //---------------------------------------------------------------//PUxPOSE: Find the conflict point in RCQ from down to up and //stop at conflict point if it has, otherwise stop at up to down //conflict point //DATA STRUCTURES:Variable token - int type, token id of a //transaction(IN) //Variable itr - interator type,the cursor of RCQ (IN) //CALLING SEQUENCE: called when a transaction is validated .//---------------------------------------------------------------.
boo1 Rocc::downToUpConflicted(int token,list::iterator itr) //PRE: Assign token, itr //POST: Return 1, if conflict exist //Recurn 0, no conflict exist //Remove read points of the transaction in RCQ, if no conflict 1 list readQl,writeQl, readQ2,writeQZ; fcr(itr=itr;itr!=RCQ.endO;itr++) ( if ( (*itr).token!=token) combineRequests(*itr,readQZ,writeQZ);
else [ readQl.clear0; writeQl.clear0; combineRequests(*itr,readQi,writeQi); //ckeck to see if conflicted if(conflicted(readQ1,writeQl,readQZ,writeQZ)) return 1; else //no conflict, erase the request from RCQ itr--=RCQ.erase(itr); 1 1 return 0; 1
//---------------------------------------------------------------//PURPOSE: update the element type of RCQ //DATA STRUCTURES:Variable RCQ - list type,declared in //rocc.h //Variable itr - iterator type (IN) //CALLING SEQUENCE: when RCQ is updated //---------------------------------------------------------------void Rocc::updateRCQ-Type(list::iterator itr) //PRE: 3-ssign itr //POST: (*itr).type==-VALIDATED
r RC-QUEUE rcq=(*itr); rcq.type=-VALIDATED; itr=~CQ. insert (RCQ.erase (itrLrcq); i
//------------------------------------------------------------//PURPOSE: Execute the operation of commit of the transaction //DATA STRUCTURES:Variable token - int type, token id of a //transaction(IN) //Variable trans[] - ROCC-TRANS type, declared in r0cc.h //Variable e - EVENT type, declared in simu.h //Variable sysstabled - boolean type, declared in mysimu.h //Variable activeTrans - int tyep, declared in mysimu.h //Variable tokenQ - list type, declared in mysimu.h //CALLING SEQUENCE: called when a transaction is commited //---------------------------------------------------------------
void Rocc: :commit(int token) //PRE: Assign token //POST: Commit a transaction // - reuse the transaction id, generate a new resource // - t->id go into token queue, or go into readyQ if readyQ //is empty // - enable a new transaction go into system // - increase commited transaction numbers // - activeTrans==activeTrans-1; [ //initial the transaciton,and reuse its t->id ROCC-TRANS *t=&trans[token]; t->id=token; t->workStatus=INITIAL; //make a schedule token into readyQ if (idleserver(READY-Q)) ( e.fd=REAUY-Q; e.type=ARRIVAL; e.clock=getTime(); e.Token.id=token; e.Token.pty=O; schedule (e); if(sysStab1ed) printText("Warning: ReadyQ is empty"); 1 else //otherwise go into tokenQ tckenQ.push-back(token);
if(activeTrans==mpl & & !idleServer(READY-Q)) //make a DEPARTURE schedule and a new token go into the system //wake up readyQ ( e. fd=READY-Q; e.type=DEPARTURE; e.clock=getTime ( ) ; e.Token=getServerToken(READY-Q,1) ; schedule (e);
//---------------------------------------------------------------//PURPOSE: Execute the operation of restart of the transaction //DATA STRUCTURES:Variable token - int type, token id of a //transaction (IN) //Variable trans[] - ROCC-TRANS type, declared in r0cc.h //Variable e - EVENT type, declared in simu.h
//Variable sysstabled - boolean type, declared in mysimu.h //Variable activeTrans - int tyep, declared in mysimu.h //CALLING SEQUENCE: calle when a transaction is restarted //----------------------------------------------------------------
void Rocc::restart(int token1 //PRE: Assign token //POST: - restart a transaction,that is make a READY-Q ARRIVAL //event. // - it's id and request resources do not change. // - increase restart numbers // - enable a new transaction go into system // - remove the flag point from RCQ //
-
activeTrans==activeTrans-1;
ROCC-TRANS *t=&trans[tokenl; t->id=token; t->workStatus=RESTART; t->accessQ=t->requestQ[Ol;
t->request-id=O; //make a schedule into readyQ e.fd=READY-Q; e.type=ARRIVAL; e .clock=getTime(I; e.Token.id=token; e.Token.pty=O; schedule(e); if(active2rans == mpl & & !idleServer(READY-QH //make a DEPARTURE schedule and a new token go into the system ( e.fd=READY-Q; e.type=DEPARTURE; e.clock=getTimeO; e.Token=getServerToken(READY-Q,11 ; schedule (el; if(sysStabled1 calcRestart 0 ; activeTrans--; 1 //---------------------------------------------------------------//PURPOSE: Remove all point of the token from RCQ //DATA STRUCTURES:Variable token - int type, token id of a //transaction(IN) //Variable RCQ - list type, declared in r0cc.h //CALLING SEQUENCE:called when a transaction is restarted. //---------------------------------------------------------------void Rocc::delRCQ-Token(int token) //PRE: Assign token //POST: all flag points of the token is deleted from RCQ 1
//delete the token from the RCQ itr=RCQ.beginO; itr!=RCQ.end();itr++) if ((*itr).token==tokenl itr--=RCQ.erase(itr) ; 1 for(list::iterator
//-------------------------------------------------------------
//PURPOSE: get a disk id number //DATA STRUC1URES::'ariable res[l - ROCC-RESOURCE type, declared in //rocc. //Variable r! - in: type. id of the item n //CALLING SEQUENCZ:called when a transaction is restarted
//----------------------------------------------------------------
int Rocc: :diskID(lnt n) //POST: return a disk id for item n 1 return res [n].disk-id; 1
//---------------------------------------------------------------//PURPOSE: Generace token id for all transactions as well as //initialize //DATA STRUCTURES:'Jariable tokenQ - listtype,saves token id //of all transactisns //Variable trans[: - ROCC-TRANS type, declared in r0cc.h //save the attribczes of transactions //Variable res[l - ROCC-RESOURCE type, declared in r0cc.h //CALLING SEQUENCE:called at the beginning of simulating //----------------------------------------------------------------
void R0cc::genera:sO //POST:Add token t3 into tokenQ and trans[l.id //Assign res [I .dis:.:-id randomly //RCQ is emp:y. (
//inirializi random seed time-c T; srand( iunsi2ned) time(&T)); ROCC-TXRNS -:=&trans [Ol ; for(in: i=O;lid=i; //assign t->id :okenC.push-backit->id); t++; //next transaction )
//initialize resource array for(ins i=O;i
--------------
//PURPOSE: Initialize the attributes of a transaction. //DATA STRUCTURES:lointer *t - ROCC-TRANS type,declared in r0oc.h //Pointer to trans [I (INOUT) //CALLING SEQUENCS:called when a transaction is committed or first //time go inco syscem //---------------------------------------------------------------void Rocc::genera~el(/*inout*/ROCC-TRANS *t) //PRE: Assign t which pointers to transit->id1 //POST:initilize crans[t->id]. // t->workStacus==INITIAL // t->acces-n~ns==O
60 //
t->accessQ is assigned
(
t->workStatus=INITIAL; //work status t->access~nums=O;//the accessing item numbers of a request //generate the request resources for (int i=O;irequestQ [il .clear( ) ; //clear reyuestQ array //clear accessQ t->accessQ.clearO; t->writeQ.clearl); //clear writeQ t->request-id=0; generateRes (tl ;
//initialize request-id
t->accessQ=t->requestQ[Ol;
//initialize accessQ
i //---------------------------------------------------------------//PURPOSE: Generate read&write resources of a transaction randomly //DATA STRUCTURES:Pointer *t - ROCC-TRANS type,declared in ro0c.h // pointer to trans [ I (INOUT) //CALLING SEQUENCE:called when a transaction is commited or first //time go into the system //---------------------------------------------------------------void Rocc::genera~eRes(/*inout*/ROCC_TRANS *t) //PRE: Assign t which pointers to trans[] //POST: t->requestQ[] is assigned // t->writeQ is assigned // t->max-requests==g.max-requests // t->request-id==O
//generate the resources of transaction between max-size and //min-size list transResQ=randomResourcesO; //generate request int one-request-nums; int accessRes; for(int j=O;j tempQ=transResQ; for(int i =O;iwriteQ.push-back(accessRes); t->requestQ[t->request-id].push_back(accessRes); 1
if ( ! t->requestQ [t->request-id].empty( ) transResQ=tempQ;
//put the rest resource into t->requestQ while(!transResQ.empty()) ( accessRes=transResQ.frontO;
)
break;
//---------------------------------------------------------------//PURPOSE: get start-time-stamp of a transaction //DATA STRUCTURES: Variable token - int type, token id o f a //transaction(IN) //CALLING SEQUENCE: called when a transaction is generated //---------------------------------------------------------------void Rocc::getStartTime(int token) //PRE : Assign token //POST: trans[tokenl.start-time== the current time of system {
I
trans [token] . start-time=getTime 0 ;
Lampiran 5 Lisling program r0cc.h Rifndef rocch #define rocch //----------------------------------------------------------------Kinclude "mysimu.h" #include "filel .h" class ROCC-TRANS:public TRANS public: list requestQ[MAX-REQUESTSl;//read requests list accessQ;//resource queue for one time accessing disk list writeQ; //update or write resources );
struct ROCC-RESOURCE 1
int disk-id;
//the disk id to which the res belong
);
enum RCQ-TYPE(-READ,-COMMIT,-VALIDATED); struct RC-QUEUE I
int token; int request-id; RCQ-TYPE type;
//associated token //the request id of the transaction //the type of operation
1;
class Rocc : public MySimu i public: Rocclconst GENERATOR GG); Rocc ( ) ; -Rocc l ) ;
//constructor //default constructor //desrructor
private: void generatell; //Randomly generate the id of transactions void generatel(R0CC-TRANS *tl; //generate one transaction void generateRes(R0CC-TRANS *t); //generate one tran. resource //the operation of cpu void cpu(int token); //the operation of cc void cc (int token); //access disk resources void accessDisk(int token); boo1 validate(int token); //validate the oper. of trans. //delete the token from RCQ void delRCQ-Tokenlint tokenl; //update res. of the token void update lint token1 ; void restart lint token); //restart a tranasction //commit a transaction void comit(int token); //the disk id of a res n int diskID(int n ) ; void combineRequests(RC-QUEUE rcq, list GreadQ,list&writeQ];
//combine all requests for a transaction void combineOneRequest(/*in*/RC-QUEUE rcq,/*outi/list
&requestQ); //combine one request for a transaction bool conflicted(list readQl,list writeQl,list readQZ,list writeQ2); //check if resources are conflicted bool upToDownConflicted(int token,/*inout*/list::i'ierator &itr); //check if conflicted happen in RCQ from up to down bool downToUpConflicted(int token,/*in*/list::iterator itr); //check if conflicted happen in RCQ ffrom down to up void updateRCQ-Type(list::iterator itr); //update the type of RCQ element into validated void void bool bool
getgtartTime(int token); refreshRCQ0; //delete useless token from RCQ diskFinished(int token); isUpdated(int token);
list RCQ;
//RC queue
ROCC-TRANS trans[MAXSIZE-TRANS]; //transactions array ROCC-RESOURCE res[MAXSIZE-DB]; //database resources 1;
