BAB I PENDAHULUAN
1.1
Latar Belakang
Teknologi informasi merupakan teknologi yang digunakan untuk mengolah, memproses, mendapatkan, menyusun, menyimpan dan memanipulasi data dalam berbagai cara untuk menghasilkan informasi yang berkualitas. Informasi berkualitas yang dimaksud adalah informasi yang relevan, akurat dan tepat waktu. Untuk mendapatkan informasi berkualitas, teknologi ini umumnya menggunakan seperangkat komputer yang dihubungkan dalam suatu sistem jaringan. Komputerkomputer tersebut saling berhubungan agar dapat melakukan kegiatan, seperti pertukaran data dan melakukan komunikasi. Jadi, jaringan komputer pada dasarnya bertujuan agar sebuah komputer dapat berkomunikasi dengan komputer lainya, yaitu dalam hal mengkomunikasikan data. Komunikasi data akan berjalan lancar jika memiliki sumber data, media transmisi data, penerima data, dan salah satu ilmu yang menjamin agar komunikasi data dapat berjalan dan menghasilkan solusi yang logis, benar dan optimal. Kajian akan hal ini erat kaitannya dengan bidang ilmu matematika dalam bidang teknologi informasi dan komputer. Sebelum jaringan komputer populer, pengguna komputer hanya mengenal sistem terdistribusi. Terdapat hal yang cukup membingungkan dalam pemakaian istilah jaringan komputer dan sistem terdistribusi (distributed system). Sistem terdistribusi adalah sebuah sistem dimana komponen software atau hardware terletak di dalam jaringan komputer dan saling berkomunikasi menggunakan message passing (yaitu, sebuah teknik untuk melakukan sinkronisasi dan komunikasi antara proses-proses yang saling berinteraksi). Pendapat lain mengatakan sistem terdistribusi adalah sebuah sistem yang terdiri dari beberapa komponen yang terdapat di dalam sebuah jaringan komputer. Beberapa contoh sistem terdistribusi adalah Internet, mobile computing, sistem otomasi bank dan sebagainya. Salah satu keuntungan penggunaan sistem terdistribusi adalah 1
ketangguhan sistem dimana kemungkinan adanya kegagalan proses tunggal yang tidak diketahui namun tidak membuat kegagalan pada sistem keseluruhan. Setiap komponen/perangkat dapat mengalami kegagalan, namun dengan menggunakan sistem terdistribusi komponen atau perangkat lain tetap berjalan dengan baik. Topik penelitian dalam penelitian ini adalah mengkaji masalah konflik akses (masalah mutual exclsion) yang terjadi pada sistem terdistribusi. Algoritma Distributed Mutual Exclusion harus berurusan dengan penundaan pesan yang tidak terduga. Oleh sebab itu, diperlukan beberapa pendekatan, diantaranya: a) Pendekatan berbasis Token b) Pendekatan berbasis Non-Token c) pendekatan berbasis Himpunan Korum Pembahasan dalam penelitian ini lebih mengutamakan algoritma Distributed Mutual Exclusion dengan pendekatan berbasis korum yang merupakan salah satu bentuk dari sistem himpunan. Dalam konteks pembahasan ini, sistem himpunan yang dimaksud adalah penerapan metode himpunan yang digunakan untuk memecahkan masalah, dengan pemahaman bahwa terdapat sistem lain yang lebih besar atau lebih luas dari setiap sistem sehingga elemen yang berada didalamnya saling berkaitan. Sinkronisasi yang berbasis sistem himpunan korum merupakan hal penting dari algoritma terdistribusi karena secara signifikan mentolerir kegagalan node dan komunikasi yang dapat menyebabkan partisi jaringan. Maekawa (1985) mengemukakan bahwa Distributed Mutual Exclusion adalah contoh klasik dari sebuah algoritma terdistribusi berbasis korum. Dalam sistem korum, jika sebuah proses menerima izin dari himpunan korum, maka proses tersebut dapat memasuki critical section. Oleh karena itu, untuk menjamin keamanan maka haruslah paling banyak satu proses dapat berada di critical section pada suatu waktu. Dengan demikian setiap dua korum harus memiliki irisan yang tidak kosong (non-empty intersection) dan setiap node hanya
2
dapat memberikan izin untuk satu simpul. Molina dan Barbara (1985) dalam jurnal berjudul How to assign votes in a distributed sistem, memberikan penjelasan bahwa himpunan korum disebut koteri. Pada penelitian terakhir menyangkut masalah resolusi konflik akses dalam sistem terdistribusi, Armin lawi, et al. (2005) memperkenalkan masalah baru tentang h-out of k-Mutual Exclusion dan pada tahun 2006 memberikan pemahaman lebih tentang sebuah sistem korum yang baru disebut (m,h,k)-koteri, kemudian dikembangkan oleh Joung (2010) dengan menerapkan (n,m,k,d)sumberdaya teralokasi yang mendasar pada sistem korum yang lebih general yaitu (m,h,k)-koteri. Teori ini memberikan solusi masalah resolusi konflik akses pada sumberdaya teralokasi dalam sistem terdistribusi yang diinisialisasi dengan masalah Distributed Mutual Exclusion yang berbasis korum dan memiliki mekanisme kerja dengan pertukaran pesan yang lebih efisien. 1.2
Rumusan Masalah
Berdasarkan latar belakang tersebut, maka dibentuk rumusan masalahnya sebagai berikut: 1. Bagaimana mendefinisikan alokasi sumberdaya berbeda secara umum pada sistem terdistribusi. 2. Bagaimana merancang struktur sistem himpunan korum untuk mengatasi masalah pada sumberdaya teralokasi secara berbeda. 3. Bagaimana mengimplementasi sistem korum untuk menyelesaikan masalah alokasi sumberdaya. 1.3
Batasan Penelitian
Message passing (pertukaran pesan) yaitu komunikasi antar proses untuk menggunakan sumberdaya yang dibutuhkan. Proses ini menyediakan dua operasi yaitu mengirim pesan dan menerima pesan. Shared memory merupakan kapasitas memory yang dapat diakses dan digunakan secara bersamaan oleh sejumlah program berbeda sehingga program tersebut dapat berbagi data dan menghindari
3
terjadinya salinan informasi yang sama yang mengacu pada penggunaan RAM dan komputasi pararel adalah salah satu teknik memanfaatkan komputer independen secara bersamaan yang kemudian dihubungkan dengan jaringan dan mampu bekerja secara pararel untuk menyelesaikan suatu masalah. Agar pembahasan lebih terfokus maka penulisan ini dibatasi hanya pada sistem terdistribusi dengan mekanisme message passing, tidak membahas sistem dengan mekanisme shared memory dan mekanisme komputasi pararel.
4
BAB II TINJAUAN PUSTAKA 2.1
Sistem Komputasi Terdistribusi
Sistem koputasi terdistribusi merupakan sebuah sistem komputer yang komponennya berada pada jaringan komputer, yang saling berkomunikasi dan melakukan koordinasi dengan cara message passing. Dengan kata lain sistem ini melibatkan lebih dari satu komputer dalam suatu bentuk jaringan sistem terdistribusi yang dapat digambarkan sebagai graf komunikasi. Graf adalah suatu himpunan yang terdiri dari simpul dan sisi, dimana sisi menghubungkan simpul-simpul yang ada. Panjang pendeknya garis dan lengkung atau lurusnya garis dalam suatu graf tidak berpengaruh terhadap perhitungan dalam graf komunikasi. Definisi 2.1 Sistem terdistribusi dapat digambarkan sebagai sebuah graf komunikasi G = (P,E) dengan P = {ui}, i = 1,2,…,n adalah himpunan proses atau simpul (node) yang saling terhubung menggunakan media jaringan komunikasi E = {eij}1 ≤ i≠ j ≤ n.(Najafi, S. 2008)
u1
u2 u3
u6 u5
u4
Gambar 1. Graf Komunikasi u1 dan u2 saling komunikasi sehingga sisinya berupa (u1,u2) atau e12 u2 dan u3 saling komunikasi sehingga sisinya berupa (u2,u3) atau e23 u3 dan u4 saling komunikasi sehingga sisinya berupa (u3,u4) atau e34 u4 dan u5 saling komunikasi sehingga sisinya berupa (u4,u5) atau e45 u5 dan u6 saling komunikasi sehingga sisinya berupa (u5,u6) atau e56 5
u6 dan u1 saling komunikasi sehingga sisinya berupa (u6,u1) atau e61 Pada sistem terdistribusi, setiap proses saling berkomunikasi dan berkoordinasi dengan cara mengirim pesan (message passing) dan memungkinkan proses mengakses sumberdaya R = {r1, r2,…, rm} dimana sumberdaya ini berfungsi
untuk
meningkatkan
kecepatan
komputasi,
ketersediaan
dan
meningkatkan kehandalan data yang digunakan secara bersama. (Lawi, et al. 2006; Joung,Y. 2010) 2.2
Masalah Alokasi Sumberdaya Terdistribusi
Dalam sistem terdistribusi pembagian sumberdaya diatur berdasarkan proses yang akan mengakses. Sumberdaya yang ada terbatas dan perlu dikelolah, dengan kata lain satu sumberdaya mungkin digunakan untuk satu proses untuk satu periode pengaksesan. Oleh karena itu, apabila satu sumberdaya telah diberikan kepada suatu proses, maka proses lain harus menunggu sumberdaya tersebut dilepaskan sehingga dapat diakses oleh proses yang lain. (Lawi, et al. 2006; Joung,Y. 2010; Tanenbaum, A. 2006; Harada T. 2001 ) Definisi 2.2 Mutual Exclusion (mutex) adalah kondisi dalam sistem terdistribusi dimana hanya terdapat paling banyak satu proses yang dapat mengakses sumberdaya. Keberadaan mutual exclusion berfungsi untuk mencegah penggunaan secara bersamaan sumberdaya tertentu. Hal ini terjadi akibat adanya interaksi (komunikasi) antara proses-proses yang berjalan dan memungkinkan adanya kompetisi antar proses. (Rafidianto, dkk. 2009) Dalam membuktikan sebuah algoritma yang berhasil mengatasi masalah akses mutex dalam memproses sumberdaya tunggal r harus memenuhi syarat berikut (Lawi, et al. 2006) : 1. Syarat safety: Terdapat hanya satu proses yang dapat mengakses sumberdaya dalam setiap waktu.
6
2. Syarat liveness: Semua proses yang ingin mengakses sumberdaya pada akhirnya akan berhasil. Definisi 2.3 d-mutual exclusion adalah kondisi yang menjamin bahwa terdapat paling banyak d proses yang dapat mengakses bagian kritis (critical section) pada satu waktu dalam sistem terdistribusi. Dengan cara yang sama, dapat dilakukan perluasan yang lebih mengenai syarat safety dengan mempertahankan kesamaan dari syarat liveness. Syarat safety: Hanya terdapat paling banyak d proses yang dapat mengakses sumberdaya dalam setiap waktu. Definisi 2.4 Grup mutual exclusion adalah suatu situasi yang menjamin hanya ada satu sumberdaya dapat diakses secara bersama oleh beberapa proses secara bersamaan tetapi dari grup yang sama bukan proses dari grup yang berbeda. Syarat safety: Paling banyak satu sumberdaya r∈R yang dapat diakses oleh beberapa proses secara bersamaan. Definisi 2.5 Masalah Writer-Reader merupakan kondisi beberapa proses yang harus mengakses sumberdaya yang sama pada suatu waktu, sebagian membaca (readers) dan sebagian lagi menulis (writers). Tetapi, tidak ada proses yang dapat mengakses sumberdaya untuk menulis atau membaca saat terdapat proses lain yang sedang menulis. Agar data dalam berkas tetap konsisten, maka setiap kali berkas tersebut ditulis, maka maksimal satu proses menulis yang dapat berlangsung, tetapi saat proses menulis sedang berlangsung, maka tidak boleh ada satupun proses membaca.
7
1. Syarat safety writing: Paling banyak satu proses yang dapat menulis pada sumberdaya. 2. Syarat safety reading: Jika ada beberapa proses ingin membaca sumberdaya yang sementara dibaca (tidak sementara ditulis), maka proses-proses tersebut dapat membaca secara bersamaan. 2.3
Sistem Himpunan Korum
Definisi 2.6 Himpunan C ⊆ 2P yang memuat subset - subset tidak kosong dari P adalah koteri atas P jika dan hanya jika: 1. Minimalitas : (∀ Q ,Q’∈C) [Q⊄Q’]. (Q,Q’∈C disebut korum) 2. Irisan
: (∀ Q,Q’∈C)[Q∩Q’≠∅] .
Contoh : 1. Misalkan Himpunan {{1,2,3}, {2,4,5}, {4,5,6}} tidak dapat disebut koteri atas P = {1,2,3,4,5,6} karena himpunan (korum) pertama dan ketiga tidak saling beririsan. 2. Himpunan {1,2,3} dan {1,3} tidak dapat disebut koteri atas P = {1,2,3} karena himpunan (korum) pertama adalah superset himpunan kedua. 3. Misalkan C1 = {{1,2}, {2,3}}, C2 = {{2,4}, {3,4}, {1,4} adalah koteri atas P = {1,2,3,4} maka himpunan {1,2}, {2,3}, {2,4}, {3,4} dan {1,4} disebut korum
Berikut diberikan dua contoh konstruksi sistem koteri: Definisi 2.7 (Majority Koteri). Sistem himpunan M disebut Majority koteri atas himpunan titik P jika dan hanya jika M = {Q | |Q| = ⎡
!!! !
⎤ dan Q ⊆ P}.( Jrjiang .
2005) Contoh 3. Misalkan terdapat himpunan P ={1,2,3,4,5} maka n = 5, ⎡(n+1)/2⎤ =3. Sehingga diperoleh:
8
M = {{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4},{1,3,5}, {1,4,5}, {2,3,4}, {2,3,5},{2,4,5}, {3,4,5}} adalah majority koteri dengan korum berukuran ⎡(n+1)/2⎤ = 3. Definisi 2.8 (Grid Korum). Misalkan P adalah himpunan titik-titik yang diatur dalam bujur sangkar berukuran k x k. Korum Grid adalah gabungan dari titiktitik pada baris penuh dan kolom yang saling berpotongan. Jumlah anggota P adalah n = k2 dan |Q| = 2k-1. ( Jrjiang .2005) Contoh 4. Misalkan diberikan k = 3 bilangan bulat, sehingga akan diperoleh ukuran kotak grid 3 x 3.
Gambar 2. Konstruksi Grid Cotrie n = k2= 32= 9 dan |Q| = 2k-1= 2 x 3 -1 = 5 Sehingga diperoleh: Grid ={{1,2,3,4,7}, {1,2,3,5,8}, {1,2,3,6,9}, {1,4,5,6,7}, {1,4,7,8,9}, {2,4,5,6,8}, {2,5,7,8,9}, {3,4,5,6,9}, {3,6,7,8,9}} 2.4
Perluasan Sistem Himpunan Korum
Berikut akan dijabarkan penjelasan tentang perluasan alami dari koteri dengan mengembangkan sifat-sifat umum koteri sehingga akan diperoleh sifat yang dapat digunakan secara umum. Definisi 2.9 (k-koteri). Himpunan tidak kosong C ⊆ 2P adalah k-koteri atas P jika memenuhi:
9
1.
Saling Lepas: Untuk setiap h
2.
Irisan: ∀ K ⊆ Q, l>k K = {Q1 ,…, Ql}⊆ C, maka terdapat paling sedikit pasang {Qi,Qj} ⊆ K sedemikian sehingga Qi ∩ Qj ≠ ∅, 1 ≤ i≠ j ≤ l.
3.
Minimalitas: Qi ⊄ Qj , ∀ Qi ,Qj ∈ C, i≠ j.
Untuk sistem korum 1-koterie disebut koteri. Contoh 5. C = {{1,2},{1,3},{2,4}{3,4}} adalah 2-koteri atas P = {1,2,3,4} karena setiap korum Q dalam C selalu dapat ditemukan korum lain yang saling lepas dengan Q. Definisi 2.10 (Sistem Korum). Q = (P, 𝒞) adalah sebuah sistem korum dengan P adalah himpunan tidak kosong dan 𝒞 adalah himpunan yang berisi himpunan bagian dari P yang saling beririsan. Himpunan P disebut sebagai himpunan semesta dan himpunan 𝒞 disebut sebagai koteri yang berisi korum dari sistem. Sistem korum dapat dipresentasikan kedalam sebuah matriks keterkaitan dengan entitas 1 dan 0. Definisi 2.11 (Matriks Korum) Matriks korum dari sebuah sistem korum (P,𝒞) adalah matriks berukuran m x n dimana m = |𝑃| dan n = |𝒞| ditulis 𝒞 = (𝒸!,! ) yang diperoleh sebagai berikut: elemen dari P disebut sebagai p1, p2,… pn dan korum pada 𝒞 disebut sebagai Q1, Q2, …Qm dengan entri-entrinya sebagai berikut 𝒸!" =
1, 𝑗𝑖𝑘𝑎 𝑝! ∈ 𝑄! 0, 𝑗𝑖𝑘𝑎 𝑝! ∉ 𝑄!
Contoh 6. Diberikan sistem korum (P,𝒞) dengan himpunan koteri 𝒞 = {{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}} atas P = {1, 2, 3, 4} dengan 𝑚 = 4 dan 𝑛 = 6.
10
Matriks korum dari sistem (P,𝒞) adalah matriks 𝒞 = (𝒸!,! ) dibentuk seperti pada matriks berikut. 1
C1 C2 C3 C4 C5 C6
1 1 1 0 0 0
2
1 0 0 1 1 0
3
0 1 0 1 0 1
4
0 0 1 0 1 1
Matriks korum 𝒞 = (𝒸!,! ) Definisi 2.12 (Bikoteri). Pasangan koleksi himpunan B= {C1,C2} dimana C1 dan C2 adalah himpunan bagian dari 2P, adalah sebuah bikoteri atas P jika dan hanya jika memenuhi: a) Irisan: ∀ Q ∈ C1 dan ∀Q’ ∈ C2 , Q∩Q’≠∅ b) Minimalitas: ∀Q,Q’∈ Ci (i = 1,2)Q ⊄ Q’. Contoh 7. P = {1,2,3,4} B = {C1,C2} adalah sebuah bikoteri atas P = {1,2,3,4} C1 = {{1,2,3},{1,2,4},{1,3,4},{2,3,4}} C2 = {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}} 2.5
Area Critical Section
Akses sebuah proses ke sumberdaya dapat digambarkan sebagai suatu daerah kritis (critical section). Saat proses ingin mengakses sumberdaya, maka proses terlebih dahulu masuk ke area yang disebut Waiting Section dan setelah menggunakan sumberdaya maka proses akan mengeksekusi Exit Section, dan proses tersebut dapat keluar dari area mengeksekusi sumberdaya sehingga tidak dapat lagi melakukan eksekusi.
11
End
Start
Non Critical Section
Exit Section
Waiting Section
Critical Section
Sumberdaya
Gambar 3. Alur siklus proses
2.5.1 Algoritma Penyelesaian Masalah Mutual Exclusion Dasar operasi dari algoritma terdistribusi adalah pengurutan kejadian yang terjadi secara terus menerus, contohnya jika diinginkan pernyataan bahwa proses p dalam sistem i terjadi sebelum atau sesudah proses p dalam sistem j. Dengan kata lain, diperlukan adanya kejelasan dalam pengurutan proses. Dari masalah tersebut, Lamport mengusulkan pengurutan proses kedalam suatu bentuk pengurutan waktu dengan metode penandaan (stempel) waktu. Lamport mengembangkan algoritma mutual exclusion terdistribusi terhadap sumberdaya yang hanya boleh diakses oleh suatu proses dalam satu waktu. Algoritma ini bertindak secara adil dengan cara interaksi antar proses melalui pertukaran pesan (message). Oleh karena itu, sebuah kejadian dapat diidentikkan dengan pengiriman pesan yang kemudian akan dicatat dalam bentuk urutan stempel waktu.
Kejadian dimana suatu proses akan mengakses
sumberdaya disebut sedang memasuki critical section (CS). Algoritma ini mengeksekusi permintaan CS dalam urutan waktu yang semakin meningkat dan menempatkan permintaan tersebut kedalam antrian
12
permintaan (request_queuei) yang terurut total berdasarkan stempel waktu masing-masing. (Kshemkalyani, A. 2008; Tanenbaum, A. 2006) Saat suatu proses mengirimkan pesan permintaan maka proses tersebut menambah nilai stempel waktu dengan 1. Pesan permintaan dikirim dalam bentuk (ti,pi) dimana ti merupakan banyaknya pengiriman pesan permintaan yang dilakukan oleh proses p dan pi merupakan proses dengan stempel waktu i.
Algoritma: 1. Algoritma meminta (request) bagian kritis: 1) Bila proses pi akan mengeksekusi CS, maka proses pi akan memberi pesan REQUEST (ti,pi) ke semua proses lain dan menempatkan pesan permintaan kedalam request_queuei. 2) Ketika sebuah proses lain pj yang menerima pesan REQUEST (ti,pi) maka pesan permintaan dari pi masuk request_queuej dan memberikan pesan REPLY ke pi. 2. Algoritma mengeksekusi bagian kritis. Proses pi memasuki CS ketika dua kondisi berikut berlaku: 1) pi menerima pesan dengan stempel waktu lebih besar dari (ti,pi) dari semua proses lain. 2) Permintaan pi berada di bagian paling atas dalam antrian (request_queuei). 3. Algoritma keluar dari bagian kritis 1) Saat proses pi keluar dari CS, maka pi akan menghapus pesan permintaannya pada bagian paling atas dalam request_queuei dan memberikan pesan RELEASE ke semua proses lain. 2) Ketika proses pj menerima pesan RELEASE dari proses pi, maka pj akan menghapus permintaan pi dari request_queuej.
13
Contoh 8. Ilustrasi dari Algoritma Lamport
(1,1)
p1 (1,2)
p2 p3 Gambar 4. p1 dan p2 akan memasuki CS Pada gambar diatas, proses p1 dan p2 akan mengakses CS dan mengirimkan pesan REQUEST ke proses lain. Maka stempel waktu
proses p1 adalah (1,1) dan
stempel waktu untuk proses p2 adalah (1,2). p1 masuk CS (1,1)
p1 (1,2)
p2
p3 Gambar 5. p1 memasuki CS Gambar diatas mengilustrasikan bahwa masing-masing proses menerima pesan REPLAY dari proses lain. Pada proses p1 pesan permintaannya berada paling atas pada request_queue tetapi proses p2 memiliki pesan permintaan tidak pada bagian paling atas dari request_queue sehingga p1 yang dapat memasuki CS.
14
p1 masuk CS (1,1)
p1
p1 keluar CS
(1,1) (1,2)
(1,2)
p2
p3 (1,1) (1,2)
Gambar 6. p1 keluar CS Pada Gambar 6, menggambarkan p1 keluar dari CS dan mengirimkan pesan RELEASE ke proses lain. p1 masuk CS (1,1)
p1
p1 keluar CS
(1,1) (1,2)
(1,2)
p2
p3 (1,1) (1,2)
p2 masuk CS
Gambar 7. p2 masuk CS Pada gambar diatas, p2 telah menerima pesan balasan dari proses lain, juga menerima pesan RELEASE dari proses p1, p2 memperbaharui keadaan request_queuei dan pesan permintaannya berada pada bagian paling atas, sehingga p2 dapat memasuki CS.
15
2.6
Perluasan Masalah Alokasi Sumberdaya Terdistribusi
Perluasan masalah sistem terdistribusi dengan alokasi sumberdaya terbatas dapat didefinisikan menjadi sebuah masalah sistem terdistribusi yang lebih general dengan akses ke sumberdaya bersama dibatasi. Jumlah proses adalah n dan jumlah kelompok/jenis sumberdaya adalah m, jumlah kelompok yang dapat diakses secara bersamaan paling k dan untuk setiap kelompok, paling banyak terdapat d proses yang dapat mengakses sumberdaya. Masalah tersebut dapat dikatakan sebagai (n, m, k, d)-sumberdaya teralokasi yang merupakan generalisasi masalah d-mutual exclusion dan grup mutual exclusion sebagai berikut. Masalah (n, 1, 1, 1)-sumberdaya teralokasi bertepatan dengan masalah mutual exclusion, masalah (n, 1, 1, d) – sumberdaya teralokasi bertepatan dengan k-mutual exclusion, dan masalah (n, m, 1, d)- sumberdaya teralokasi bertepatan dengan grup mutual exclusion. (Joung, 2010 ; Lawi et al, 2006) 1. (n, 1, 1, 1)-sumberdaya teralokasi 1) Paling banyak 1 dari m sumberdaya yang dapat diakses oleh beberapa proses dalam satu waktu. 2) Paling banyak 1 proses yang dapat mengakses sumberdaya 2. (n, 1, 1, d)-sumberdaya teralokasi 1) Paling banyak 1 dari m sumberdaya yang dapat diakses oleh beberapa proses pada satu waktu 2) Paling banyak d proses yang dapat mengakses sumberdaya 3. (n, m, 1, 1)-sumberdaya teralokasi 1) Terdapat m jumlah sumberdaya yang dapat diakses 2) Paling banyak 1 dari m sumberdaya yang dapat diakses oleh beberapa proses pada satu waktu 3) Paling banyak 1 proses yang dapat mengakses sumberdaya 4. (n, m, 1, ∞)- alokasi sumberdaya 1) Terdapat m jumlah sumberdaya yang dapat diakses
16
2) Paling banyak 1 dari m sumberdaya yang dapat diakses oleh beberapa proses satu waktu 3) Tidak terdapat batasan pada jumlah proses yang dapat mengakses sumberdaya 5. (n, m, 1, d)- alokasi sumberdaya 1) Terdapat m jumlah sumberdaya yang dapat diakses 2) Paling banyak 1 dari m sumberdaya yang dapat diakses oleh beberapa proses satu waktu 3) Paling banyak d jumlah proses yang dapat mengakses sumberdaya 6.
(n, m, k, d)- alokasi sumberdaya 1) Terdapat m jumlah sumberdaya yang dapat diakses 2) Paling banyak k dari m sumberdaya yang dapat diakses oleh beberapa proses secara bersamaan pada satu waktu 3) Paling banyak d jumlah proses yang dapat mengakses sumberdaya
17
BAB III TUJUAN DAN MANFAAT
3.1 Tujuan Penelitian Pada rumusan masalah disajikan beberapa pertanyaan terkain proses penelitian. Proses penelitian yang dilakukan menjawab rumusan masalah tersebut merupakan tujuan dari penelitian ini. Dengan demikianm tujuan dari penelitian ini adalah: 1. Mengkaji definisi matematis untuk masalah alokasi sumberdaya berbeda yang secara umum dapat diimplementasi pada sistem terdistribusi. 2. Mengkaji struktur sistem himpunan korum untuk mengatasi masalah pada sumberdaya teralokasi secara berbeda. 3. Mengimplementasi sistem korum untuk menyelesaikan masalah alokasi sumberdaya.
3.2 Manfaat dan Urgensi Penelitian Manfaat dari penulisan yaitu mengkaji masalah resolusi konflik akses secara umum yang teralokasi secara berbeda pada sistem terdistribusi serta dapat mengkaji struktur sistem himpunan korum untuk mengatasi masalah pada sumberdaya teralokasi secara berbeda. Lebih lanjut, sistem korum yang dibentuk secara umum dapat diimplementasi untuk menyelesaikan masalah-masalah alokasi sumberdaya. Penelitian ini sangat penting dilakukan dalam rangkan meningkatkan alokasi sumberdaya pada system terdistribusi. Apalagi saat ini system komputasi
18
parallel dan terdistribusi sangat massif digunakan dalam berbahai bidang disilin ilmu. Alokasi sumberdaya yang dimaksud baik eksternal dan internal system.
3.3 Luaran Penelitian Target luaran (output) penelitian diarahkan untuk memperoleh konstruksi teoritis bernilai aplikasi tinggi dalam mempercepat pencapaian produk IPTEK. Secara khusus diformulasikan sebagai berikut: 1. Satu makalah dipublikasikan pada jurnal nasional/prosiding nasional; 2. Satu makalah dipublikasikan pada prosiding internasional; 3. Poster tentang algoritma berbasis korum untuk masalah alokasi sumber daya pada system terdistribusi; 4. Bahan ajar yang dipakai untuk mahasiswa S1 dan S2; 5. Laporan Penelitian sebagai pengembangan bahan ajar.
19
BAB IV METODE PENELITIAN
Penelitian ini bersifat pengembangan keilmuan dengan hasil kajiannya berupa teori baru berkaitan dengan berbagai masalah alokasi sumber daya dan konflik akses yang dapat diterapkan pada Sistem Komputasi Terdistribusi. Oleh karena itu, penelitian akan dilakukan terdiri dengan langkah-langkah sebagai berikut:
4.1 Subyek Penelitian Penilitian ini dimulai dengan kajian pustaka atau kajian teoritik. Subjek penelitian adalah membangun sifat-sifat dari mutual exclusion dengan solusi menggunakan sistem korum. 4.2 Obyek Penelitian Objek penelitian adalah proses-proses data yang digambarkan sebagai titik atau simpul pada sistem korum. Setiap proses tersebut akan saling berkomunikasi dengan membandingkan stempel waktu yang dimiliki untuk menentukan proses mana yang dapat mengakses sumberdaya. 4.3 Instrumen penelitian Data penelitian berupa kumpulan teori-teori tentang sifat-sifat Mutual Exclusion. Datadata diperoleh dari jurnal-jurnal yang ada, baik ditulis oleh peneliti sendiri maupun kolaborasi dengan peneliti-peneliti lain terutama Jepang. Instrument penelitian akan menggunakan logbook. Pada logbook akan dicatat semua aktivitas penelitian mulai dari pelaksanaan, hasil yang diperoleh dan pengeluaran dana.
4.4 Desain Penelitian Berdasarkan target luaran, penelitian ini dilaksanakan secara bertahap dengan perencanaan waktu 2 (dua) tahun. Tahap-tahap penelitian dilakukan per tahun dengan uraian seperti berikut. Pada tahun pertama dilakukan beberapa tahap sebagai berikut:
20
4.4.1
Tahap Inisiasi
Pada tahap ini dilakukan persiapan pelaksaan penelitian. Persiapan yang dimaksud misalnya, menyiapkan log book penelitian, menyelesaikan urusan administrasi, serta koordinasi pelaksanaan penelitian kepada semua pihak yang terkait. Pada tahap ini akan dilakukan juga kajian tentang jenis-jenis Mutual Exclusion dan kaitannya dengan Sistem Korum sebagai solusi. 4.4.2
Tahap Investigasi
Pada tahap ini dilakukan investigasi tentang sifat-sifat yang dapat dibentuk dari sistem korum agar dapat memenuhi syarat safety yang dimiliki mutual exclusion, terutama dalam pencapaian untuk memodelkan mutual exclusion yang lebih umum. Sifat safety merupakan sifat yang akan menjamin bahwa hanya terdapat satu proses yang mengakses sumberdaya 4.4.3
Tahap Verifikasi
Pada tahap akhir dari tahun pertama akan diperoleh beberapa sifat baru dari mutual exclusion termasuk sistem korum yang dapat menjamin pemenuhannya. Hasilnya akan dipublikasikan pada jurnal internasional yang bereputasi sangat baik. Pada tahun kedua dilakukan penerapan hasil-hasil yang diperoleh ditahun pertama, pada tahap ini juga akan dilakukan kerjasama penelitian dengan dengan Professor Takaichi Yoshida dari Kyushu Institute of Technology dan presentasi hasil penelitian dalam skala nasional atau Internasional.
21
4.5 Alur Penelitian Untuk lebih jelasnya tahap-tahap penelitian di tahun kedua dapat dilihat pada diagram alir penelitian seperti berikut.
Start
Sistem Terdistribusi
Sistem Himpunan
(n,1,1,1)-Alokasi sumberdaya ≡ Mutex
Koteri
(n,1,1,d)-Alokasi sumberdaya ≡ d-mutex
d-‐koteri
(n,m,1,d)-Alokasi sumberdaya ≡ grup mutex
(m,1,d)-‐koteri
(n,m,h,d)-‐Alokasi sumberdaya ≡ grup d-‐mutex
(m,k,d)-‐koteri
(n,m,h,di)-‐Alokasi sumberdaya ≡ grup di-‐mutex
(m,k,di)-‐koteri
End
22
BAB V HASIL YANG TELAH DICAPAI
5.1 Masalah Alokasi Sumberdaya Terdistribusi Masalah sumberdaya teralokasi merupakan salah satu masalah fundamental untuk resolusi konflik pada sistem terdistribusi. Masalah ini muncul saat proses-proses dalam sistem terdistribusi membutuhkan sumberdaya sehingga proses tersebut dapat saling bekerjasama, namun mereka saling bersaing satu dengan yang lain untuk dapat mengakses sumberdaya. Masalah mutual exclusion yang menjadi pembahasan awal dalam penelitian ini merupakan salah satu masalah utama sumberdaya teralokasi. Mutual exclusion memberikan sebuah penjelasan mendasar dalam sistem terdistribusi, yakni berupa proses yang akan mengakses secara intensif sehingga harus memiliki izin sebelum mengakses sumberdaya tersebut. Masalah ini betujuan untuk menyelaraskan (sinkronisasi) akses-akses proses dalam sistem terdistribusi terhadap sumberdaya tunggal yang tidak dapat dibagi (single indivisible resource). Kinerja utama algoritma terdistribusi diukur berdasarkan jumlah pesan yang dipertukarkan (message complexity) dalam sistem terdistribusi. Salah satu metode dalam mengefisienkan jumlah pesan untuk algoritma sistem terdistribusi adalah dengan menggunakan struktur himpunan terhadap proses-proses disebut korum. Secara khusus merupakan struktur kuorum yang berbasis izin (permissionbased). Korum adalah himpunan bagian dari proses-proses dalam sistem terdistribusi dengan sifat tertentu. Korum memiliki sifat saling beririsan satu dengan yang lain yang dapat menyelesaikan masalah alokasi sumberdaya. Berdasarkan penjelasan yang diberikan sebelumnya, terdapat beberapa perluasan masalah mutual exclusion diantaranya adalah k-mutual exclusion yaitu kondisi yang menjamin bahwa terdapat paling banyak k proses yang dapat mengakses bagian kritis (critical section) pada satu waktu dalam sistem terdistribusi dan grup mutual exclusion adalah suatu situasi yang menjamin bahwa 23
ada satu sumberdaya dapat diakses secara bersama oleh beberapa proses secara bersamaan tetapi dari grup yang sama bukan proses grup dari yang berbeda. 5.2 Sistem Korum untuk Alokasi Sumberdaya Terdistribusi Dalam pendekatan mutual exclusion berbasis korum, setiap proses mengirimkan pesan request untuk mengakses sumberdaya hanya kehimpunan bagian dari proses tersebut tapi tidak dari semua proses. Dengan jaminan sifat dari korum, ketika dua proses secara bersamaan meminta akses ke sumberdaya, maka setidaknya terdapat satu proses yang menunggu dan menerima pesan request, proses ini bertanggung jawab untuk memastikan bahwa hanya satu proses yang mengeksekusi sumberdaya setiap waktu. 5.2.1 (n, 1, 1, 1)-sumberdaya teralokasi Dari definisi, mutual exclusion atau mutex merupakan masalah mendasar dalam sistem terdistribusi dimana paling banyak satu proses yang dapat menggunakan sumberdaya pada satu waktu. Masalah ini dapat diselesaikan dengan mekanisme kerja mutex berbasis korum. Mutex pada dasarnya berlangsung jika hanya terdapat satu proses yang dapat menggunakan sumberdaya, maka dengan menggunakan sistem korum dapat ditunjukkan bahwa sistem korum yang memenuhi adalah 1koteri atau disebut koteri saja. Misalkan diberikan himpunan P = {1, 2, 3} akan terbentuk koteri atas P yaitu C = {{1, 2}, {1, 3}, {2, 3}} yang merupakan 1-koteri. Cara kerja mutex berbasis korum adalah dengan memilih korum Q∈C dan mengirimkan pesan permintaan pada setiap proses dalam Q, karena adanya sifat saling beririsan, maka pesan permintaan juga akan tersampaikan pada korum yang lain dan dapat mengakses sumberdaya saat korum Q mendapat izin dari semua proses dalam korum, sehingga proses lain yang akan mengakses sumberdaya akan menunggu Q mengirimkan pesan keluar dari sumberdaya. Sehingga jelas bahwa 1-koteri atau dapat dituliskan (1,1,1)-koteri memenuhi masalah mutex, dengan paling banyak 1 dari m sumberdaya yang dapat diakses dan paling banyak 1 proses yang dapat mengakses sumberdaya. Untuk 24
banyak grup yaitu m sumberdaya untuk (1,1)-koteri, dapat disebut sebagai m-
proses mutual exclusion yang akan sama jika menggunakan solusi (m,1,1)-koteri. Koteri pada (m, 1, 1)-koteri adalah 1-koteri dan 1-koteri C dapat diubah menjadi (m, 1, 1)-koteri, Tm(C) = (C1, ..., Cm) dengan cara memisahkan masing-masing koteri sebanyak m 5.2.2 (n, 1, 1, d)-sumberdaya teralokasi Untuk menyelesaikan masalah d-mutex berbasis korum, maka digunakan definisi
k-koteri dengan k pada k-koteri menunjuk pada paling banyak grup d pada mutex yang dapat mengakses sumberdaya. Contoh 9: C = {{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}} adalah 2-koteri atas P={1,2,3,4} karena terdapat maksimal 2 korum yang saling lepas yaitu {1,4}, {2,3} atau {1,3},{2,3} atau {1,2},{3,4}. Dari contoh yang diberikan dapat dilihat bahwa hanya terdapat 1 jenis sumberdaya, dengan 1 kelompok yang dapat diakses dan paling banyak terdapat 2 proses yang dapat mengakses sumberdaya, sehingga contoh diatas dapat pula disebut (1,1,k)-koteri, dengan k = 2 Dengan sifat saling iris menjamin paling banyak k sumberdaya yang dapat digunakan oleh beberapa proses dan sifat saling lepas menjamin paling banyak k sumberdaya yang dapat digunakan, sehingga kedua sifat ini dapat memenuhi sifat safety d-mutex. 5.2.3 (n, m, 1, ∞)-sumberdaya teralokasi dan (n,m,1,d)-sumberdaya teralokasi Grup mutex adalah generalisasi dari mutual exclusion dimana sumberdaya yang akan diakses lebih dari satu. Saat tidak terdapat batasan pada jumlah proses yang dapat mengakses sumberdaya maka d = ∞ disebut grup mutex, dan saat jumlah proses yang dapat mengakses sumberdaya paling banyak d pada grup yang sama pada satu waktu tetapi tidak dua proses dari grup berbeda, maka disebut grup dmutex. Penyelesaian masalah ini dapat menggunakan definisi dari k-koteri dengan banyak proses yaitu sebesar m.
25
Contoh 10: 1) Misalkan P = {1, 2, 3, 4}. Maka 𝒞={C,C,C}, dimana 𝒞={{1, 2}, {3, 4}}, {{1, 3}, {2, 4}}, {{2, 3}, {1,4}}, adalah sebuah k-koteri dengan (3, 2)-koteri. 2) Misalkan P = {1,2} Maka 𝒞 = (C, C, C) dimana 𝒞 = {{1}, {2}}, {{1}, {2}}, {{1}, {2}} juga merupakan sebuah k-koteri dengan (3, 2)-koteri. Definisi 5.1 [Derajat Koteri]. Derajat koteri C, dilambangkan deg(C), adalah jumlah maksimum korum yang saling disjoint di C. Derajat suatu (m, 1)-koteri 𝒞, dilambangkan deg(𝒞), didefinisikan sebagai derajat minimal koteri dalam 𝒞. 𝒞 disebut berderajat seragam k (uniform degree k) jika semua derajat koterinya sama dengan k. Contoh 11. (m,1,k)-koteri digunakan untuk menyatakan (m,1)-koteri berderajat seragam k. 𝒞 = {{1, 2}, {3, 4}}, {{1, 3}, {2, 4}}, {{2, 3}, {1, 4}} adalah sebuah (3, 1, 2)-koteri atas P = {1, 2, 3, 4}. Dapat dilihat bahwa pada koteri 𝒞 pada masing-masing koteri memiliki derajat k = 2 sehingga disebut berderajat seragam 2. Dengan demikian, disimpulkan bahwa terdapat satu dari m sumberdaya yang dapat diakses/digunakan oleh paling banyak 2 proses secara bersamaan pada satu waktu. Untuk lebih lanjut, berikut akan diberikan penjelasan tentang hubungan (m, 1, k)-koteri dengan (n, m,1,d)-alokasi sumberdaya: 1. Misalkan P, |P| = n, adalah himpunan proses yang akan mengakses sumberdaya, dan misalkan 𝒞 = (C1, ..., Cm) menjadi (m, 1, k)-koteri atas P. Setiap grup dari proses di P disebut sebagai koteri, sehingga saat sebuah proses dari grup j ingin menggunakan sumberdaya bersama, maka korum Q ∈ Cj harus menerima izin dari setiap anggota korum dalam koteri tersebut.
26
2. Proses yang telah berhasil menerima izin, harus mengembalikan setelah selesai menggunakan sumberdaya Karena setiap anggota korum hanya memiliki satu izin untuk diberikan, maka sifat-sifat berikut menjamin terjadinya grup mutex dan grup d-mutex: 1. Irisan 𝒞 menjamin bahwa tidak ada proses dari grup berbeda yang dapat mengakses sumberdaya secara bersamaan. 2. Derajat dari 𝒞 memastikan ada sebanyak d proses (tidak lebih) yang secara bersamaan dapat mengakses sumberdaya. 3. Sifat minimalitas digunakan untuk meningkatkan efisiensi, jika Q1 ⊂ Q2, maka proses yang dapat menerima Q2 maka dapat pula menerima Q1. Berikut disajikan gambar sebagai bentuk ilustrasi: 1. Mutex: Paling banyak terdapat satu proses mengakses sumberdaya
p1
p2
...
pn
R
2. k- Mutex: Paling banyak terdapat k proses mengakses sumberdaya p1
p2
p3
...
p4
pn
R
3.
Grup Mutex: Beberapa proses dari grup yang sama mengakses paling banyak satu sumberdaya
p1
p2
p3
p4
...
pn
R2 R1
...
Rn 27
4. Grup k-Mute: Terdapat k proses dari grup yang sama dapat mengakses paling banyak satu sumberdaya p1
p2
p3
p4
...
pn
sebanyak k proses
R1
R2
...
Rn
5.2.4 (n,m,k,d)-sumberdaya teralokasi Pembahasan yang lebih luas tentang masalah sistem terdistribusi dapat didefinisikan secara general (umum) dengan jumlah sumberdaya (m) dengan akses yang terbatas berarti hanya ada satu dari m sumberdaya menjadi h sumberdaya yang dapat diakses pada setiap waktu. Masalah ini disebut (m,k,d)sumberdaya teralokasi yang dapat diselesaikan dengan menggunakan sebuah sistem korum baru yang disebut (m,h,k)-koteri. Definisi 5.2 [(m,h,k)-koteri]. Pasangan koleksi himpunan M = (C1 ,…, Cm) dimana Ci adalah k-koteri atas P, ∀ Ci ∈ M adalah sebuah (m,h,k)-koteri atas P jika dan hanya jika memenuhi: Saling Lepas: ∀ L = (𝐶!! ,…, 𝐶ℓ𝓁! ) ∈ M, dengan ℓ𝓁 < 𝑚 maka terdapat elemen C ∈ M yang lain sedemikian sehingga C dan Ci saling lepas ∀ 1 ≤ i ≤ ℓ𝓁. Bikoteri : ∀H = (𝐶!! ,…, 𝐶!! ) ⊆ M, terdapat paling sedikit satu pasangan (𝐶!! , 𝐶!! ) membentuk bikoteri, ∀1 ≤ i ≠ j ≤ h.
Contoh 12: Diberikan (4,2,2)-koteri atas P = {1, …, 16} sebagai berikut, yang merupakan sebuah (m,h,k)-koteri C1 = {{1,2,5,7}, {3,4,6,8}} C2 = {{5,6,9,11}, {7,8,10,12}}
28
C3 = {{9,10,13,15}, {11,12,14,16}} C4 = {{1,3,13,14}, {2,4,15,16}}
5.2.4.1 Konstruksi (m,h,k)-koteri Pertama, asumsikan 𝑛 = 2ℎ𝑘 ! dan 𝑚 = 2ℎ, lalu himpunan 𝒫 dipartisi menjadi 𝑚 himpunan bagian 𝑃! , … , 𝑃! . Bentuk k-koteri 𝐶! pada partisi himpunan 𝑃! , dengan membuat k himpunan saling lepas atau disebut korum 𝑄!" , 1 ≤ j ≤ k , 1 ≤ 𝑖 ≤ 𝑚 , dengan ! 𝑄!" = 𝑝!" ∈ 𝑃! ,
1 ≤ 𝑠 ≤ 𝑘
dan !!! 𝑄(!!!)! = 𝑝!" ∈ 𝑃!!! , 1 ≤ 𝑠 ≤ 𝑘 ∗ Sehingga akan terbentuk koteri 𝐶! = 𝑄!" = 𝑄!" ∪ 𝑄(!!!)! , dengan ∗ 𝑄!" = 𝑄!" ∪
!!! 𝑝!" ∈ 𝑃!!! ⋯ ⋯ ⋯ (1)
Dimana, 1.
∗ 𝑄!" = 2𝑘
jika 𝑄!" = 𝑘
2.
∗ 𝑄!" = 2𝑘 + 1
jika 𝑄!" = 𝑘 + 1
⋮ 3.
∗ 𝑄!" = 2𝑘 + 𝑛
jika 𝑄!" = 𝑘 + 𝑛
Misalkan M = (C1 ,…, Cm) dimana Ci = {Qi1 ,…, Qik} akan dibentuk Lemma berikut.
5.2.5 (n,m,k,di)-sumberdaya teralokasi 29
Untuk masalah sumberdaya teralokasi dengan banyak derajat yang tidak seragam dalam sistem terdistribusi akan diselesaikan secara umum dengan menggunakan (m,h,ki)-koteri. Definisi 5.3 [(m,h,ki)-koteri]. Sebuah koleksi himpunan M = (C1, ..., Cm), Ci adalah ki-koteri atas P, 1 ≤ ki < n dikatakan menjadi (m, h, ki)-koteri atas P jika kondisi disjoint dan bikoteri terpenuhi.
Contoh 14: Diberikan (4,2,2)-koteri atas P = {1, …, 16} sebagai berikut, yang merupakan sebuah (m,h,ki)-koteri C1 = {{1,2,5,7,9},{3,4,6,8,10}} C2 = {{5,6,11,14,17},{7,8,12,15,18}{9,10,13,16,19}} C3 = {{11,12,13,20,23},{14,15,16,21,24},{17,18,19,22,25}} C4 = {{1,3,20,21,22},{2,4,23,24,25}}
5.2.5.1 Konstruksi (m,h,ki)-koteri (m,h,ki)-koteri dapat dibentuk dengan memodifikasi bentuk konstruksi dari simple uniform 𝑛 = 𝑡ℎ
(m,h,k)-koteri ! !!! 𝑘!
dengan
mengasumsikan
𝑚 = 𝑡ℎ
dan
𝑘!!! mod 𝑚 . Partisi himpunan 𝒫 kedalam ki, ki ⊆ 𝑄!" untuk
membentuk ki koteri, Sehingga 𝐶! = {𝑄!" }, dimana ! 𝑄!" = 𝑝!" ∈ 𝑃! , 1 ≤ 𝑠 ≤ 𝑘
dan !!! 𝑄(!!!)! = 𝑝!" ∈ 𝑃!!! , 1 𝑠 𝑘
30
dengan 𝑄 !!! ! = 𝑘!!" ∗ Koteri 𝐶! = 𝑄!" = 𝑄!" ∪ 𝑄(!!!)! ,
∗ 𝑄!" = 𝑄!" ∪
!!! 𝑝!" ∈ 𝑃!!! , 1 𝑠 𝑘 !!!!!!!
Sehingga akan diperoleh 1.
∗ 𝑄!" ∩ 𝑄∗!!!
!!
= ∅ , 1 𝑗, 𝑗′ 𝑘!
2.
∗ 𝑄!" ∩ 𝑄∗!!!
!!
≠ ∅ , 1 ≤ 𝑣 < 𝑡 dan 1 𝑗, 𝑗′ 𝑘!
Contoh 15: Akan dikonstruksi (m,h,ki)-koteri dengan 𝑚 = 2ℎ, m = 4, h = 2 dan k = {2,3,3,2} sebagai berikut 1. Partisi 𝒫 sebanyak 10 himpunan bagian dengan masing-masing ukuran 2, 3, 3, dan 2. Atur kedalam masing-masing koteri. C1 = {{1,2},{3,4}} C2 = {{5,6},{7,8},{9,10}} C3 = {{11,12,13},{14,15,16},{17,18,19}} C4 = {{20,21,22},{23,24,25} 2. Sisipkan satu anggota dari setiap Qj di Ci+1 kedalam Ci C1 = {{1,2,5,7,9},{3,4,6,8,10}} C2 = {{5,6,11,14,17},{7,8,12,15,18}{9,10,13,16,19}} C3 = {{11,12,13,20,23},{14,15,16,21,24},{17,18,19,22,25}}
31
C4 = {{1,3,20,21,22},{2,4,23,24,25}} Pasangan C1 dan C3, C2 dan C4 saling disjoint karena setiap elemen yang terdapat pada masing-masing pasangan himpunan saling lepas. Pasangan C1 dan C3, C2 dan C4 adalah bikoteri karena terdapat elemen yang saling beririsan dengan pasangan himpunannya. Masalah (n,m,k,d)-sumberdaya teralokasi dapat diselesaikan dengan menggunakan sistem koteri yang disebut (m,h,k)-koteri karena d-mutual exclusion dan k-akses bersama dapat dijamin dengan adanya syarat dari k-koteri dan bikoteri. Permasalahan ini juga bebas dari deadlock dan starvation karena jaminan eksekusi sumberdaya yang pada akhirnya akan berhasil dari algoritma Lamport dengan metode penandaan waktu (tsi, pi). Jaminan serupa berlangsung pada (n,m,k,di)-sumberdaya teralokasi dengan sistem koteri yang disebut (m,h,ki)koteri. 5.3 Koteri Seimbang, Biasa dan Seragam Bentuk dari suatu koteri memiliki hubungan dengan sistem terdistribusi. Misalkan 𝒞 = (C1 , ...,Cm) adalah (m, 1, d)-koteri atas P. 1. 𝒞 disebut seimbang (balance) jika semua koteri memiliki ukuran yang sama. 2. 𝒞 disebut biasa (regular) jika semua elemen di P termuat dalam jumlah yang sama dari korum; ∀ p, q ∈ P: |np| = |nq|. Dimana np = {Q | Q ∈ Ci,p ∈ Q}, demikian pula untuk nq. 3. 𝒞 disebut seragam (uniform) jika semua korum memiliki ukuran yang sama. Saat menggunakan (m, 1, d)-koteri dengan pemilihan korum untuk (n, m, 1, d)-sumberdaya teralokasi, maka syarat-syarat diatas mengidentifikasikan hubungan sebagai berikut:
32
1. Syarat seimbang (balance) memungkinkan setiap grup memiliki kesempatan yang sama dalam mengakses sumberdaya. 2. Syarat regular (regular) memungkinkan setiap proses untuk berbagi tugas yang sama. 3. Syarat seragam (uniform) memungkinkan jumlah pesan yang diperlukan setiap kali mengakses ke bagian kritis harus terpisah dari korum yang terproses. Contoh 16: Diberikan (3, 1, 2)-koteri atas P = {1, 2, 3, 4} berikut: C1 = {{1, 2}, {3, 4}} C2 = {{1, 3},{2, 4}} C3 = {{2, 3}, {1,4}} Koteri diatas merupakan contoh dari koteri yang seimbang, seragam dan regular.
33
BAB IV KESIMPULAN
Berdasarkan hasil penelitian, maka dapat disimpulkan: 1. Masalah Mutual Exclusion dapat diperluas menjadi masalah yang lebih umum (general) hingga dapat menjadi suatu masalah yang disebut (n,m,k,di)-sumberdaya teralokasi yaitu dengan cara merelaksasi syarat safety dan syarat liveness. 2. Permasalahan
sumberdaya
teralokasi
dapat
diselesaikan
dengan
menerapkan solusi dari suatu sistem himpunan yang disebut koteri. 3. Untuk mengetahui suatu sistem korum berjalan dengan baik, maka dapat dilakukan perhitungan bersifat kombinatorial yang disebut muatan dan rasio keseimbangan.
34
DAFTAR PUSTAKA
Garcia-Molina, H., Barbara, D. 1985. How to assign votes in a distributed system. Journal of the ACM 32(4), pages: 841–860. Harada Takashi, Yamashita Masafumi. 2001. Coterie join operation and tree structured k-coteries. IEEE Transaction on Parallel and Distributed Systems, Volume 12, Number 9. Holzman, Ron., Marcus, Yosi., Peleg, David. 1997. Load Balancing in Quorum Systems. SIAM Journal of Discrete Mathematics. Volume 10, Number 2, pages: 223-245. Joung, Yuh-Jzer. 2010. On quorum sistem for group resources allocation, Distributed Computing. Volume 22, number 3, pages: 197-214. Kshemkalyani Ajay, Singhal Mukesh. 2008. Distributed Computing Principles, Algorithm and Sistem. Cambridge University Press. Lawi, A., Oda, K., and Yoshida, T. 2006. Quorum based distributed conflict resolution algorithm for bounded capacity resources. Lecture Notes in Computer Science (LNCS), Vol. 4331, SpringerVerlag-Berlin, pp. 135–144. Malkhi, Dahlia., K. Reiter, Michael., Wool, Avishai., N. Wright, Rebecca. 2001. Probabilistic Quorum Systems. Information and Computation. Volume 170. Pages: 184–206. Najafi, S. 2008. A New GA - Based and Graph Theory Supported Distribution System Planning, Vol. 2, No. 8. ISSN – 1453 – 1119. Naor, Moni., Avishai, Wool. 1994. The Load, Capacity, Availability of Quorum System. Dept. Applied Mathematics and Computer Science, The Wizmann Institute Rehovot 76100, Israel. Weizmann Science Press of Israel.
35
Rafidianto, Rizki Muh., Gemilang Route, Kurniawan Yoga, dkk. 2009. Tugas Studi
Kasus
Sistem
Operasi
Mutual
Exclusion.
(Online),
(http://routeterritory.files.wordpress.com/2009/04/mutual-exclusion.pdf diunduh 10 Februari 2013). Tanenbaum, A, and Steen, M.V. October 2006. Distributed Systems: Principles and Paradigms, Second Edition. Prentice Hall. Tel, G. October 2000. Introduction to Distributed Algorithms. Cambridge University Press.
36
