PERTEMUAN VIII (SISTEM TERDISTRIBUSI)

BAB 5
 SINKRONISASI

5.5 REKSA PENGECUALIAN

            Mendasar untuk sistem terdistribusi adalah konkurensi dan kolaborasi
diantara beberapa proses. Dalam banyak kasus, hal ini juga berarti bahwa proses akan membutuhkan untuk secara bersamaan mengakses sumber daya yang sama. Untuk mencegah akses yang bersamaan tersebut merusak sumber daya, atau membuatnya tidak konsisten, solusi yang diperlukan untuk memberikan saling eksklusif akses oleh proses. Pada bagian ini, kita melihat beberapa membagikan algoritma yang lebih penting yang telah diusulkan. Sebuah survei terbaru algoritma didistribusikan untuk saling pengecualian disediakan oleh Saxena dan Rai (2003). Tua, tapi masih relevan adalah Velazquez (1993).

5.5.1 Sebuah Algoritma Terpusat

            Cara yang paling mudah untuk mencapai bersama. pengecualian dalam terdistribusi sistem untuk mensimulasikan bagaimana hal itu dilakukan dalam suatu sistem satu-prosesor. Salah satu proses terpilih sebagai koordinator. Setiap kali suatu proses ingin mengakses sumber daya bersama, ia akan mengirimkan pesan permintaan kepada koordinator menyatakan Bentuk sumber daya ingin mengakses dan meminta izin. Jika tidak ada proses lain yang sedang mengakses sumber daya itu, koordinator mengirimkan kembali balasan pemberian izin, seperti yang ditunjukkan pada Gbr.6-14 (a). Ketika jawaban tiba, proses meminta bisa pergi ke depan.

            Ketika proses 1 selesai dengan sumber daya, ia akan mengirimkan pesan ke koordinator melepaskan akses eksklusif, seperti yang ditunjukkan dalam Gbr.6-14 (c). Koordinator mengambil item pertama dari antrian permintaan ditangguhkan dan mengirimkan proses bahwa memberikan pesan. Jika proses masih diblokir (yaitu, ini adalah pesan pertama untuk itu), itu unblocks dan mengakses sumber daya. Jika pesan eksplisit telah dikirim menyangkal izin, proses harus jajak pendapat untuk lalu lintas masuk atau blok nanti. Either way, ketika melihat hibah, dapat pergi ke depan juga.

Sangat mudah untuk melihat bahwa algoritma menjamin saling pengecualian: koordinator hanya memungkinkan satu proses pada suatu waktu untuk sumber daya. Hal ini juga adil, karena permintaan yang diberikan dalam urutan di mana mereka diterima. Proses Tidak pernah menunggu selamanya (tidak ada kelaparan). Skema ini mudah dilaksanakan, juga, dan hanya membutuhkan tiga pesan per penggunaan sumber daya (request, hibah, release). Kesederhanaan itu membuat menarik solusi untuk situasi praktis.

Pendekatan terpusat juga memiliki kekurangan. Koordinator adalah satu
titik kegagalan, jadi jika crash, seluruh sistem mungkin turun. Jika proses normal
blok setelah melakukan permintaan, mereka tidak bisa membedakan koordinator mati dari "ijin ditolak" karena dalam kedua kasus tidak ada pesan datang kembali. Selain itu, dalam sistem besar, koordinator tunggal dapat menjadi penyebab penurunan performa. Namun demikian, manfaat yang berasal dari kesederhanaan melebihi dalam banyak kasus potensi kelemahan

5.5.2 Algoritma Terdistribusi

            Bagi banyak orang, memiliki algoritma sekutu probabilistik yang benar hanya tidak cukup baik. Jadi peneliti telah mencari algoritma deterministik pengecualian didistribusikan bersama. 1.978 makalah Lamport pada sinkronisasi jam disajikan yang pertama. Ricart dan Agrawala (1981) membuatnya lebih efisien. Dalam bagian ini kita akan menjelaskan metode mereka.

            Algoritma Ricart dan Agrawala mensyaratkan bahwa harus ada pemesanan total dari semua peristiwa dalam sistem. Artinya, untuk setiap sepasang peristiwa, seperti pesan, itu harus jelas mana yang benar-benar terjadi pertama kali. Algoritma Lamport yang disajikan dalam Sec. 6.2.1 adalah salah satu cara untuk mencapai pemesanan ini dan dapat digunakan untuk memberikan cap waktu untuk saling pengecualian didistribusikan.

            Algoritma ini bekerja sebagai berikut. Ketika sebuah proses ingin mengakses sumber daya bersama, itu membangun sebuah pesan yang berisi nama sumber daya, nomor proses nya, dan arus (logis) waktu. Ini kemudian mengirimkan pesan ke semua proses lainnya, konseptual termasuk dirinya sendiri. Pengiriman pesan diasumsikan handal, yaitu, tidak ada pesan yang hilang.

            Ketika sebuah proses menerima pesan permintaan dari proses lain, tindakan itu mengambil tergantung pada negara sendiri sehubungan dengan sumber daya yang disebutkan dalam pesan.

Tiga kasus yang berbeda harus dibedakan secara jelas:

1.    Jika penerima tidak mengakses sumber daya dan tidak ingin mengakses
itu, ia akan mengirimkan kembali pesan OK ke pengirim.

2.    Jika penerima telah memiliki akses ke sumber daya, itu hanya tidak
menjawab. Sebaliknya, itu antrian permintaan.

3.    Jika penerima ingin mengakses sumber daya juga tapi belum
melakukannya, itu membandingkan timestamp dari pesan yang masuk dengan saya. salah satu yang terkandung dalam pesan yang telah dikirim orang. yang terendah satu menang. Jika pesan yang masuk memiliki timestamp yang lebih rendah, penerima mengirimkan kembali pesan OK. Jika pesan sendiri memiliki lebih rendah timestamp, antrian penerima permintaan yang masuk dan mengirimkan apa-apa.

Setelah mengirimkan permintaan meminta izin, proses duduk kembali dan menunggu sampai orang lain telah diberi izin. Segera setelah semua izin berada di, mungkin pergi ke depan. Ketika selesai, ia akan mengirimkan pesan OK untuk semua proses pada perusahaan antrian dan menghapus mereka semua dari antrian.

            Mari kita mencoba untuk memahami mengapa algoritma bekerja. Jika ada konflik, maka jelas bekerja. Namun, anggaplah bahwa dua proses mencoba untuk mengakses secara bersamaan sumber daya, seperti yang ditunjukkan pada Gambar. 6-15 (a).

Gambar 6-15. (a) Dua proses ingin mengakses sumber daya bersama pada saat yang sama saat. (b) 0 Proses memiliki timestamp terendah. sehingga menang. (c) Ketika proses 0 dilakukan, ia mengirimkan sebuah OK juga, jadi 2 sekarang dapat pergi ke depan.

            Proses 0 mengirimkan semua permintaan dengan timestamp 8, sementara pada saat yang sama, Proses 2 mengirimkan semua permintaan dengan timestamp 12. Proses 1 tidak tertarik di sumber daya, sehingga mengirimkan OK untuk kedua pengirim. Proses 0 dan 2 baik melihat konflik dan membandingkan cap waktu. Proses 2 melihat bahwa ia telah kehilangan, sehingga memberikan izin ke 0 dengan mengirimkan OK. Proses 0 sekarang antrian permintaan dari 2 untuk nanti pengolahan dan mengakses sumber daya, seperti yang ditunjukkan pada Gambar. 6-15 (b). Ketika selesai, menghilangkan permintaan dari 2 dari antrian dan mengirim pesan OK untuk memproses 2, yang memungkinkan kedua untuk pergi ke depan, seperti yang ditunjukkan pada Gambar. 6-15 (c). Algoritma ini bekerja karena dalam kasus konflik, timestamp terendah menang dan semua orang setuju pada Urutan cap waktu

Perhatikan bahwa situasi pada Gambar. 6-15 akan menjadi dasarnya berbeda jika Proses 2 telah mengirimkan pesannya di awal waktu sehingga proses sudah 0 dan diberikan izin sebelum membuat permintaan sendiri. Dalam hal ini, akan memiliki 2 menyadari bahwa itu sendiri sudah akses ke sumber daya pada saat permintaan, dan antri bukannya mengirimkan balasan.

Seperti dengan algoritma terpusat dibahas di atas, saling pengecualian adalah dijamin tanpa kebuntuan atau kelaparan. Jumlah pesan yang dibutuhkan per entri sekarang 2 (n - 1), di mana jumlah proses dalam sistem adalah n. Terbaik dari semua, tidak ada single point of failure ada.

Sayangnya, titik tunggal kegagalan telah digantikan oleh poin n kegagalan. Jika proses apapun crash, maka akan gagal untuk menanggapi permintaan. Keheningan ini akan diartikan (salah) sebagai penolakan izin, sehingga memblokir semua berikutnya upaya oleh semua proses untuk memasukkan semua daerah kritis. Karena probabilitas dari satu proses n gagal setidaknya n kali lebih besar sebagai koordinator tunggal gagal, kami telah berhasil mengganti algoritma miskin dengan yang lebih dari n kali buruk dan membutuhkan lalu lintas jaringan yang jauh lebih banyak.

Algoritma dapat ditambal oleh trik yang sama yang kita diusulkan sebelumnya. Ketika permintaan datang, penerima selalu mengirimkan balasan, baik pemberian atau menyangkal izin. Setiap kali baik permintaan atau balasan hilang, waktu pengirim keluar dan terus mencoba sampai baik balasan datang kembali atau pengirim menyimpulkan bahwa tujuan sudah mati. Setelah permintaan ditolak, pengirim harus memblokir menunggu untuk pesan OK berikutnya.

Masalah lain dengan algoritma ini adalah bahwa baik komunikasi multicast primitif harus digunakan. atau proses masing-masing harus menjaga daftar anggota grup sendiri, termasuk proses memasuki kelompok, meninggalkan kelompok, dan menabrak. Metode ini bekerja terbaik dengan kelompok-kelompok kecil dari proses yang tidak pernah berubah mereka kelompok keanggotaan.

Akhirnya, ingat bahwa salah satu masalah dengan algoritma terpusat adalah bahwa sehingga menangani semua permintaan dapat menyebabkan kemacetan. Dalam algoritma terdistribusi, semua proses yang terlibat dalam semua keputusan yang menyangkut mengakses sumber daya bersama. Jika satu proses tidak dapat menangani beban, tidak mungkin bahwa memaksa semua orang untuk melakukan hal yang sama secara paralel akan banyak membantu.

Berbagai perbaikan kecil yang mungkin untuk algoritma ini. Misalnya, mendapatkan izin dari setiap orang benar-benar berlebihan. Semua yang diperlukan adalah suatu metode untuk mencegah dua proses mengakses sumber daya pada saat yang sama. Algoritma dapat dimodifikasi untuk memberikan izin ketika telah dikumpulkan izin dari sederhana sebagian besar proses lainnya, bukan dari mereka semua. Tentu saja, dalam variasi ini, setelah proses telah memberikan izin untuk satu proses, tidak bisa memberikan izin yang sama untuk proses lain sampai yang pertama selesai.

Namun demikian, algoritma ini lebih lambat, lebih rumit, lebih mahal,
dan kurang kuat bahwa yang terpusat aslinya. Mengapa repot-repot belajar di bawah kondisi ini? Untuk satu hal, itu menunjukkan bahwa algoritma didistribusikan setidaknya mungkin, sesuatu yang tidak jelas ketika kita mulai. Juga, dengan menunjukkan kekurangan, kita dapat merangsang teori masa depan untuk mencoba untuk menghasilkan algoritma yang benar-benar berguna. Akhirnya, seperti makan bayam dan belajar Latin SMA, beberapa hal yang dikatakan baik untuk Anda dalam beberapa cara abstrak

Algoritma Token Ring

Algoritma Token ring menggunakan sebuah jaringan bus dengan proses yang tidak berurutan. Melaui perangkat lunak, ring logika disusun dengan setiap proses ditetapkan posisinya dalam ring.

Posisi ring dapat ditentukan dengan menggunakan urutan nomor alamat jaringan atau dengan cara lain, namun yang terpenting adalah setiap  proses harus tahu siapa  proses sesudahnya.

Pada saat ring diinialisasi, proses 0 diberi token yang nantinya di sirkulasi dalam jaringan. Token ini berpindah dari  proses K ke proses  K+1 dengan pesan point-to-point. Ketika proses memperoleh token dari tetangganya, proses memeriksa apakah proses situ sedang berusaha memasuki critical region.

-     Jika ingin masuk, proses memasuki critical region, mengerjakan semua yang diperlukan dan meninggalkan critical region.

-     Setelah keluar, proses melewatkan token ke ring. Proses tidak mengijinkan memasuki critical region yang kedua kalinya dengan token yang sama.

Jika proses yang mempunyai token tetapi tidak ingin memasuki critical region, proses segera melewatkan token. Konsekuensinya, jika tak ada proses yang ingin masuk critical region, token berputar dengan kecepatan tinggi mengelilingi ring.

Kelebihan dan kekurangan dari algoritma token ring

kelebihan:

-     Algoritma ini menjamin hanya satu proses masuk critical region, karena hanya satu proses yang dapat mempunyai token

-     Startvation tidak terjadi karena adanya pengurutan proses

Kekurangan

-     Jika token hilang, token harus dibangitkan lagi, dan mendeteksi token hilang adalah sulit, karena interval waktu kemunculan token tidak dibatasi.

-     Proses yang crash akan menimbulkan kesulitan.

Perbandingan tiga algoritma

Algoritma terpusat merupakan algoritma yang efisien dan lebih mudah dari ketiga algoritma tersebut. Hanya ada tiga proses yang dibutuhkan untuk keluar masuk daerah kritis adalah reguest, grant, release. Pada algoritma tersebar lebih sensitive pada kejadian crash

5.6 DISTRIBUTED TRANSACTIONS

Transaksi Tersebar adalah eksekusi program yang mengakses data yang digunakan bersama di banyak situs, menjamin semua situs yang terlibat transaksi mencapai keputusan konsisten menganai kommit atau abort.

Sebuah transaksi klien menjadi terdistribusi jika ia melibatkan beberapa operasi pada beberapa server. Ada dua cara dimana transaksi terdistribusi dibentuk, yakni nested transaction dan flat transaction. Biasanya transaksi flat atau nested mengakses objek yang berada pada satu server tunggal. Namun, dalam kebanyakan hal, sebuah transaksi ,apakah itu nested atau flat, akan mengakses objek yang ditempatkan pada server yang berbeda-beda. Dalam hal ini, kita gunakan terminologi distributed transaction untuk merujuk pada transaksi flat maupun nested yang mengakses objek yang dikelola oleh lebih dari satu komputer server. Ketika distributed transaction diperkenalkan di akhir-akhirnya, atmocity property dari transaksi mensyaratkan bahwa baik semua server yang terlibat mengikatkan diri pada transaksi ataupun semua server tersebut justru menghentikan transaksi. Untuk memenuhi tujuan ini, sebuah server mengambil alih peran koordinator yang melibatkan pemastian outcome yang sama pada setiap server. Cara yang ditempuh oleh koordiantor untuk melakukan hal ini, bergantung pada protokol yang dipilih. Sebuah protokol yang dikenal sebagai “two-phase commit protocol” merupakan protokol yang biasa digunakan. Protokol ini memungkinkan server untuk berkomunikasi satu dengan yang lainnya untuk mencapai kesepakatan bersama baik dalam commit maupun abort.

Kontrol konkurensi dalam transaksi terdistribusi berdasar pada metode .Masing-masing server menerapkan kendali konkurensi local pada objeknya masing-masing, yang mana kendali ini memastikan bahwa transaksi terserialisasi secara lokal.

5.6.1 The Transaction  Model

One Phase Commit Protocol

• Coordinator mengirimkan pesan commit atau abort pada semua partisipan
• Proses diulang terus menerus sampe semua sudah membalas
• Masalah : Tidak mungkin melakukan abort setelah ada permintaan untuk commit

Ø  Solusi : Two Phase Commit

Two Phase Commit Protocol

Fase 1 (voting)

Coordinator mengirimkan request canCommit pada setiap partisipan kemudian partisipan memilih yes/no dan mengirim balik pada coordinator. Jika yes, maka menyimpan obyek pada penyimpanan permanen.

Fase 2

Coordinator mengumpulkan hasil voting, jika semua setuju coordinator memutuskan untuk commit (menjalankan) dan mengirimkan do Commit pada semua partisipan. Selain itu, coordinator memutuskan abort dan mengirimkan do Abort pada semua partisipan yang memilih yes. Partisipan yang memilih yes menunggu do Commit/doAbort dari coordinator Setelah menerima salah satu dari pesan diatas, partisipan menjalankan perintah sesuai dengan pesan yang diterima Jika dilakukan perintah commit, maka partisipan mengirimkan pesan have Committed pada coordinator sebagai konfirmasi bahwa proses sudah dilaksanakan.

Masalah pada Two Phase Commit

• Susah memastikan semua partisipan sudah melakukan vote dan mendapatkan hasil yang sama
• Jika proses mengalami kegagalan (terjadi network partitioning), maka tidak akan didapatkan konsensus, karena partisipan yang lain akan saling menunggu (blocking)

Ø  Solusi : three phase commit

Three Phase Commit

Mencoba mengatasi masalah blocking (menunggu) yaitu dengan menggunakan asumsi tidak lebih dari k site fail (k adalah angka yang sudah disetujui). Coordinator memastikan bahwa paling tidak k site lain tahu bahwa coordinator akan melakukan commit. Jika coordinator fail, site yang lain melakukan election coordinator baru dan melihat status Terakhir dan menentukan keputusan yang akan diambil (commit/abort).

Masalah pada Three Phase Commit

• Susah implementasinya
• Harus memastikan bahwa state harus tetap konsisten meskipun terdapat perbedaan hasil (transaksi di commit di satu site dan abort di site yang lain sebagai akibat dari network partitioning)
• Terlalu banyak overhead

5.6.2 Classification of Transactions

Pada dasarnya transaksi adalah serangkaian operasi yang memenuhi sifat ACID. Jenis transaksi ini juga disebut flat transaction. Flat transaction adalah jenis yang paling sederhana dari transaksi, dan yang paling sering digunakan. Namun, flat transaction memiliki sejumlah keterbatasan yang telah membawa model alternatif. Di bawah ini kami membahas dua kelas penting: nested transactions and distributed transactions.

Ø  Some Limitations of Flat Transactions

Keterbatasan utama dari flat transaction adalah bahwa mereka tidak memungkinkan hasil parsial yang akan dilakukan atau dibatalkan. Dengan kata lain, kekuatan milik atomicity flat transaction juga sebagiandari kelemahannya.

Sebagai contoh, kita biasamenemukan bahwa itu sudah cukup sulit untukpenerbangan cadangan dari JFK ke Nairobi. Aborting seluruh transaksi akan berarti bahwa kita harus membuat upaya kedua untuk memesan tempat duduk pada penerbangan itu, yang saat itu mungkin gagal.

Pada flat transaction, sebuah client membuat request lebih dari satu server. Sebagai contoh pada gambar berikut, transaksi T merupakan transaksi flat yang melibatkan operasi-operasi terhapdap objek-objek pada server X, Y, dan Z. Sebuah flat transaction melengkapi tiap-tiap requestnya sebelum bernangkat ke transaksi selanjutnya. Oleh karenanya, tipa-tiap trnasaksi mengakses objek server secara sekuensial. Ketika sebuah server dikunci, maka transaksi hanya bias menunggu satu objek saja pada satu waktu.

Ø  Nested Transactions

Beberapa keterbatasan yang disebutkan di atas dapat dipecahkan dengan memanfaatkan transaksi bersarang. Transaksi bersarang dibangun dari sejumlah sub-transaksi. Transaksi tingkat atas dapat garpu dari anak-anak yang berjalan secara paralel dengan satu sama lain, pada mesin yang berbeda, untuk mendapatkan kinerja atau menyederhanakan pemrograman . Masing-masing anak juga dapat melakukan satu atau lebih subtransaksi, atau garpu dari anak-anaknya sendiri.

Pada nested transaction, transaksi yang beradapada level atas dapat membuka beberapa sub-transaksi dan tiap-tiap sub-transaksi tersebut dapat juga membuka sub-transaksi lagi seterusnya sampai beberapa tingkat. Gambar 1.2 menunjukkan trnasaksi klien T yang membuka dua sub transaksi T1 dan T2, yang mengakses objek pada server X dan Y. Sub-transaksi T1 dan T2 tersebut membuka sub-transaksilagi, yakni T11, T12, T21, dan T22 yagn mengakses objek pada server M, N, dan P. Dalam kasus transakasi bertingka seperti ini, sub transaksi yang beradapada level yang sama dapat berjalan secara serrempak (konkuren), sehingga T1 dan T2 konkuren, dan karena mereka melibatkan objek pada server yang berbeda, maka mereka dapat nerjalan secara paralel

5.6.3 Implementation

Taruhlah sebuah transaksi terdistribusi, dimana sebuah klien mentransfer $10 dari account A ke account C dan kemudian mentransfer $20 dari account B ke D. Account B dan D berada pada server yang terpisah X dan Y, sementara account C dan D berada pada server Z. Jika transaksi ini disusun sebagai satu set berisi empat transaksi nested, sebagaimana pada Gambar, maka keempat request (dua deposit dan dua withdraw) dapat berjalan secara parallel dan dampak secara keseluruhan dapat mempengaruhi kinerja yang lebih baik dari pada sebuah transaksi sederhana berisi empat transaksi yang berjalan secara sekuensial.