PERTEMUAN IX (SISTEM TERDISTRIBUSI)

SISTEM TERDISTRIBUSI

CHAPTER 6

CONSISTENCY AND REPLICATION

6.1 PENDAHULUAN

Pada bagian ini, kita mulai dengan membahas alasan penting untuk ingin melakukan replikasi data di tempat pertama. Perhatian khusus diberikan untuk benda replikasi, karena hal ini merupakan topik yang semakin penting dalam sistem terdistribusi modern. Akhirnya, kita membahas replikasi sebagai teknik untuk mencapai skalabilitas, dan memotivasi mengapa penalaran tentang konsistensi sangat penting.

6.1.1 Alasan untuk Replikasi

Ada dua alasan utama untuk replikasi data: keandalan dan kinerja. Pertama, data yang direplikasi untuk meningkatkan keandalan sistem. Jika sistem file telah direplikasi dimungkinkan untuk terus bekerja setelah satu replika crash hanya dengan beralih ke salah satu replika lainnya. Juga, dengan mempertahankan beberapa salinan, menjadi mungkin untuk memberikan perlindungan yang lebih baik terhadap data yang rusak. Sebagai contoh, bayangkan ada tiga salinan dari sebuah file, dan setiap membaca dan menulis operasi dilakukan pada setiap salinan. Kita bisa menjaga diri terhadap satu, gagal operasi menulis, dengan mempertimbangkan nilai yang dikembalikan oleh setidaknya dua salinan sebagai yang benar.

Alasan lain untuk replikasi data adalah kinerja. Replikasi untuk kinerja adalah penting ketika sistem terdistribusi perlu skala dalam jumlah dan wilayah geografis. Scaling dalam jumlah terjadi, misalnya, ketika peningkatan jumlah proses perlu untuk mengakses data yang dikelola oleh server tunggal. Dalam hal ini, kinerja dapat ditingkatkan dengan mereplikasi server dan kemudian membagi pekerjaan. Kami sudah datang di seperti contoh dalam Bab. 1. ketika kita singkat dibahas kelompok direplikasi server Web.

Scaling sehubungan dengan ukuran wilayah geografis mungkin juga memerlukan replikasi. Ide dasarnya adalah bahwa dengan menempatkan salinan data dalam kedekatan proses menggunakan mereka, waktu untuk mengakses data berkurang. Akibatnya, kinerja seperti yang dirasakan oleh proses yang meningkat. Contoh ini juga menggambarkan bahwa manfaat dari replikasi untuk kinerja mungkin sulit untuk mengevaluasi. Meskipun proses klien mungkin menganggap kinerja yang lebih baik, mungkin juga menjadi kasus bahwa bandwidth jaringan yang lebih kini dikonsumsi menjaga semua replika up-to-date. Kita kembali ke seperti trade-off ketika membahas protokol distribusi.

Jika replikasi membantu untuk meningkatkan keandalan dan kinerja, yang bisa melawan itu? Sayangnya, ada harga yang harus dibayar ketika data direplikasi. Masalah dengan replikasi adalah bahwa memiliki beberapa salinan dapat menyebabkan masalah konsistensi. Setiap kali salinan dimodifikasi, salinan itu menjadi berbeda dari yang lain. Akibatnya, modifikasi harus dilakukan pada semua salinan untuk memastikan konsistensi. Tepatnya kapan dan bagaimana modifikasi perlu dilakukan menentukan harga replikasi.
Untuk memahami masalah, pertimbangkan untuk meningkatkan waktu akses ke halaman Web. Jika tidak ada tindakan khusus dilakukan, mengambil halaman dari server Web remote kadang-kadang malam mengambil detik untuk menyelesaikan. Untuk meningkatkan kinerja, Web browser sering lokal menyimpan salinan yang sebelumnya diambil halaman web (yaitu, mereka cache halaman Web). Jika pengguna membutuhkan halaman itu lagi, browser secara otomatis mengembalikan salinan lokal. Waktu akses seperti yang dirasakan oleh pengguna yang sangat baik. Namun, jika pengguna selalu ingin memiliki versi terbaru dari halaman, ia mungkin dalam untuk nasib buruk. Masalahnya adalah bahwa jika halaman telah dimodifikasi sementara itu, modifikasi tidak akan telah disebarkan ke salinan cache, membuat mereka salinan out-of-date.

Salah satu solusi untuk masalah kembali kepada pengguna adalah untuk melarang browser untuk menyimpan salinan lokal di tempat pertama, efektif membiarkan server sepenuhnya bertanggung jawab atas replikasi. Namun, solusi ini mungkin masih menyebabkan waktu akses miskin jika tidak ada replika ditempatkan dekat pengguna. Solusi lain adalah untuk membiarkan server Web membatalkan atau memperbarui setiap salinan cache, tetapi hal ini membutuhkan bahwa server melacak semua cache dan mengirim mereka pesan. Hal ini, pada gilirannya, dapat menurunkan kinerja keseluruhan server. Kita kembali ke masalah performa dibandingkan skalabilitas di bawah ini.

6.1.2 Object Replikasi

Untuk lebih memahami peran sistem terdistribusi sehubungan dengan pengelolaan (shared) data yang direplikasi, hal ini berguna untuk mempertimbangkan objek bukan data saja. Obyek mendapatkan manfaat dari encapsulating data dan operasi pada data. Dengan demikian, akan lebih mudah untuk menarik garis antara operasi yang spesifik untuk beberapa data, dan operasi yang biasanya data independen. Yang kedua jenis operasi biasanya milik sebuah sistem terdistribusi tujuan umum, seperti yang dilaksanakan oleh banyak sistem middleware dibahas dalam buku ini.

Pertimbangkan sebuah remote object terdistribusi yang dibagi oleh beberapa klien, seperti ditunjukkan pada Gambar. 6-1. Sebelum kita bahkan bisa memikirkan mereplikasi objek remote di beberapa mesin, kita perlu memecahkan masalah bagaimana melindungi objek terhadap akses simultan oleh beberapa klien. Pada dasarnya ada dua solusi untuk masalah ini (lihat, misalnya, Briot dkk., 1998).

Solusi pertama adalah bahwa obyek itu sendiri dapat menangani pemanggilan bersamaan. Sebagai contoh, kami menjelaskan bahwa obyek Java dapat dibangun sebagai monitor dengan menyatakan metode obyek yang akan disinkronisasi. Asumsikan bahwa dua klien secara bersamaan memanggil metode dari objek yang sama, yang mengarah ke dua benang bersamaan pada server di mana obyek berada. Dalam java, jika metode obyek telah disinkronkan, hanya satu dari dua benang dibiarkan berlanjut sementara yang lain diblokir sampai pemberitahuan lebih lanjut. Perbedaan tingkat concurrency mungkin ada, tapi masalah penting adalah bahwa obyek itu sendiri mengimplementasikan cara untuk menangani pemanggilan bersamaan. Prinsip ini ditunjukkan pada Gambar. 6-2 (a).
Solusi kedua adalah bahwa benda itu benar-benar terlindungi terhadap doa bersamaan, malah, server di mana obyek berada dibuat bertanggung jawab untuk kontrol konkurensi. Secara khusus, dengan menggunakan adaptor objek yang tepat, maka ada kemungkinan untuk memastikan bahwa pemanggilan bersamaan tidak akan meninggalkan obyek dalam keadaan rusak. Misalnya, seperti adaptor objek adalah salah satu yang menggunakan satu thread per objek, efektif serialisasi semua akses ke setiap objek yang dikelolanya, seperti ditunjukkan pada Gambar. 6-2 (b).

Replikasi objek remote bersama tanpa mengambil langkah-langkah khusus mengenai penanganan doa bersamaan dapat menyebabkan masalah konsistensi. Masalah ini disebabkan oleh fakta bahwa replika perlu sinkronisasi tambahan untuk memastikan bahwa pemanggilan bersamaan dilakukan dalam urutan yang benar pada setiap replika. Sebuah contoh dari masalah sinkronisasi ini adalah direplikasi database rekening bank, dibahas dalam Sec. 5.2. Sekali lagi, pada dasarnya ada dua pendekatan untuk mengatasi masalah ini.
Pendekatan pertama adalah bahwa benda itu adalah menyadari fakta bahwa hal itu dapat direplikasi. Dalam hal ini, objek bertanggung jawab untuk memastikan bahwa replika tetap konsisten di hadapan doa bersamaan. Pendekatan ini sangat sejalan dengan benda-benda yang menangani pemanggilan bersamaan sendiri. Sistem terdistribusi yang mendasari objek tersebut pada dasarnya tidak perlu memberikan dukungan umum untuk replikasi. Dukungan dapat dibatasi untuk menyediakan server dan adaptor yang membantu dalam membangun objek replikasi-sadar, seperti ditunjukkan pada Gambar. 6-3 (a).

Contoh sistem seperti ini, yang akan kita bahas dalam Bab. 9, adalah SOS (Shapiro et al., 1989) dan Globe (van Steen et al., 1999a). keuntungan benda replikasi-sadar adalah bahwa adalah mungkin untuk mengadopsi strategi replikasi obyek tertentu, mirip dengan kasus di mana objek bersamaan dapat memiliki cara sendiri untuk menangani pemanggilan bersamaan.

Yang kedua, lebih umum, pendekatan untuk menangani konsistensi dengan benda bersamaan adalah untuk membuat sistem terdistribusi bertanggung jawab untuk mengelola replikasi, seperti ditunjukkan pada Gambar. 6-3 (b). khususnya, sistem terdistribusi memastikan bahwa pemanggilan bersamaan dilewatkan ke berbagai replika dalam urutan yang benar. Pendekatan ini diikuti, misalnya, dalam Piranha (Maffeis, 1997), yang menyediakan fasilitas untuk fault-tolerant, benar-benar-memerintahkan, dan kausal-memerintahkan pemanggilan objek dalam CORBA. Keuntungan membiarkan sistem terdistribusi mengurus manajemen replika adalah kesederhanaan untuk pengembang aplikasi. Kadang-kadang sulit untuk mengadopsi solusi-objek tertentu, yang dapat menjadi kelemahan. Sebagaimana akan kita lihat, solusi tersebut sering dibutuhkan dalam menghadapi memecahkan masalah skalabilitas.

6.1.3 Replikasi Sebagai Teknik Skala

Replikasi dan caching untuk kinerja secara luas diterapkan sebagai teknik scaling. Masalah skalabilitas umumnya muncul dalam bentuk masalah kinerja. Menempatkan salinan data dan objek dekat dengan proses yang menggunakan kemudian dapat meningkatkan kinerja melalui pengurangan waktu akses, dan dengan demikian memecahkan masalah skalabilitas.

Sebuah trade-off mungkin perlu dibuat adalah bahwa menjaga salinan up-to-date mungkin membutuhkan bandwidth jaringan yang lebih. Pertimbangkan P proses yang mengakses replika N kali per detik lokal, sedangkan replika itu sendiri adalah pembaruan M kali per detik. Asumsikan bahwa update completetely menyegarkan versi replika lokal. Jika N << M, yaitu akses untuk memperbarui rasio sangat rendah, kita memiliki situasi di mana banyak versi terbaru dari replika lokal tidak akan diakses oleh P, rendering jaringan komunikasi bagi versi tidak berguna. Dalam hal ini, mungkin lebih baik untuk tidak menginstal replika dekat lokal untuk P, atau menerapkan strategi yang berbeda untuk memperbarui replika. Kita kembali ke masalah ini di bawah ini.

Masalah yang lebih serius, bagaimanapun, adalah bahwa menjaga beberapa salinan konsisten mungkin sendiri akan dikenakan masalah skalabilitas yang serius. Secara intuitif, koleksi salinan konsisten ketika salinan selalu sama. Ini berarti bahwa operasi baca dilakukan pada menyalin setiap akan selalu mengembalikan hasil yang sama. Akibatnya, ketika sebuah operasi update dilakukan pada satu salinan, pembaruan harus disebarkan ke semua salinan sebelum operasi berikutnya berlangsung, tidak peduli di mana operasi copy yang iniated atau dilakukan.

Jenis konsistensi kadang-kadang informal (dan tepat) disebut sebagai konsistensi ketat seperti yang disediakan oleh apa yang juga disebut replikasi sinkron (buretta, 1997). (Di bagian berikutnya, kami akan memberikan definisi yang tepat dari konsistensi dan memperkenalkan berbagai model konsistensi). Gagasan utama adalah bahwa update dilakukan pada semua salinan sebagai operasi atom tunggal, atau transaksi. Sayangnya, melaksanakan atomicity melibatkan sejumlah besar replika yang mungkin tersebar luas di jaringan skala besar secara inheren sulit ketika operasi juga diperlukan untuk menyelesaikan dengan cepat.

Kesulitan datang dari kenyataan bahwa kita perlu untuk menyinkronkan semua replika. Inessence, ini berarti bahwa semua replika harus terlebih dahulu mencapai kesepakatan tentang kapan tepatnya pembaruan yang akan dilakukan secara lokal. Misalnya, replika mungkin perlu memutuskan pada pemesanan global operasi menggunakan. Lamport cap, atau membiarkan koordinator menetapkan perintah tersebut. Sinkronisasi global hanya mengambil banyak waktu komunikasi, terutama ketika replika yang tersebar di seluruh jaringan luas.

Kita sekarang dihadapkan pada sebuah dilema. Di satu sisi, masalah skalabilitas dapat diatasi dengan menerapkan replikasi dan caching, yang mengarah ke perbaikan kinerja. Pada urutan keras, untuk menyimpan semua salinan konsisten biasanya membutuhkan synchorination global, yang secara inheren mahal dalam hal kinerja. Obat ini mungkin lebih buruk daripada penyakitnya.

Dalam banyak kasus, satu-satunya solusi yang nyata adalah untuk melonggarkan kendala konsistensi. Dengan kata lain, jika kita dapat bersantai persyaratan bahwa pembaruan perlu dilakukan sebagai operasi atom, kita mungkin dapat menghindari (instanneous) sinkronisasi global, dan dengan demikian dapat memperoleh kinerja. Harga yang dibayarkan adalah bahwa salinan mungkin tidak selalu menjadi everyhere sama. Ternyata, sampai sejauh mana konsistensi dapat dikendurkan sangat tergantung pada akses dan pola update data direplikasi, serta pada tujuan untuk mana data tersebut digunakan.

Pada bagian berikut, pertama kita mempertimbangkan berbagai model konsistensi memberikan definisi yang tepat tentang apa sebenarnya berarti konsistensi. Kami kemudian contine dengan diskusi kita dari protokol distribusi dan konsistensi. Pendekatan yang berbeda untuk mengklasifikasi konsistensi dan replikasi dapat ditemukan dalam (abu-abu dkk .., 1996;. Dan Wiesmann dkk, 2000).

6.2 MODEL KONSISTENSI DATA-CENTRIC

Secara tradisional, konsistensi selalu dibahas dalam konteks membaca dan menulis operasi pada data bersama, tersedia dengan cara (didistribusikan) berbagi memori, (didistribusikan) berbagi basis data, atau (terdistribusi) sistem file. Pada bagian ini, kita menggunakan menyimpan data istilah yang lebih luas. Sebuah toko data dapat didistribusikan secara fisik di beberapa meachines. Secara khusus, setiap proses yang dapat mengakses dat dari toko diasumsikan memiliki lokal (atau sekitar) salinan yang tersedia dari seluruh toko. Operasi tulis yang disebarkan ke salinan lain, seperti yang ditunjukkan pada gambar 6-4. Sebuah operasi data yang diklasifikasikan sebagai operasi penulisan ketika perubahan data, dan dinyatakan diklasifikasikan sebagai operasi baca.

Sebuah model konsistensi adalah suatu kontrak antara proses dan menyimpan data. Ia mengatakan bahwa jika proses setuju untuk mematuhi aturan-aturan tertentu, toko berjanji untuk bekerja dengan benar. Biasanya, sebuah proses yang melakukan operasi baca pada item data, mengharapkan operasi untuk mengembalikan nilai yang menunjukkan hasil dari menulis operasi terakhir pada data.

Dengan tidak adanya jam global, sulit untuk mendefinisikan dengan tepat yang menulis operasi adalah yang terakhir. Sebagai alternatif, kita perlu menyediakan definisi lain, yang mengarah ke berbagai model konsistensi. Setiap model efektif membatasi nilai-nilai bahwa operasi baca pada item data dapat kembali. Seperti yang diharapkan, orang-orang dengan pembatasan kecil yang mudah digunakan, sedangkan mereka dengan pembatasan utama kadang-kadang sulit. Trade-off adalah, tentu saja, bahwa mudah menggunakan model tidak melakukan hampir serta yang sulit. Seperti yang hidup. Untuk informasi tambahan mengenai model konsistensi, lihat (mosberger, 1993, dan Adve dan Gharachorloo.1996).

6.2.1Strict Consistency

Model Konsistensi ini menitik beratkan pada proses Read dan Write dalam kaitan dengan Read dan Write operasi pada data yang di-share. Hal ini disebut sebagai data store.contoh ; shared filesystem, memory space, database. Setiap proses dapat mengakses data dari media penyimpanan sesungguhnya memiliki salinan (copy) data dari media penyimpanan yang sesungguhnya secara lokal. Konsistensi model terjadi antara proses dan penyimpanan data, jika proses berjalan sebagaimana mestinya maka penyimpanan data berfungsi sebagaimana mestinya juga.

Model konsistensi dapat membatasi nilai pada saat proses Read sehingga proses pengembalian data data dapat dilakukan. Beberapa diantaranya dibatasi, semakin terbatas pembatasan nilai yang ada semakin mudah diterapkan.

Pembatasan konsistensi meliputi beberapa tahap. Apapun proses bacaan pada satu item data data x kembalikan satu nilai sesuai dengan hasil dari yang paling terbaru dituliskan item data x. Pembatasan ini membutuhkan model konsistensi. Ini mengasumsikankeberadaan dari waktu global absolut, dan sangat mungkin di implementasikan.

Sebagai ilustrasi perilaku proses R(x) untuk proses Read pada data x yang memunculkan hasil k. Di mana W(x) merupakan proses Write.

gGambar 6.2 (a) pembatasan konsistensi (b) tidak menggunakan pembatasan konsistensi

6.2.2.Sequential Consistency and Linearizability

Sequential consistency (Lamport, 1979): digunakan untuk shared memory pada sistem multiprosesor. Dalam data store dikatakan sequentialy consistent apabila memeenuhi kondisi berikut ; Hasil dari tiap eksekusi adalah sama jika operasi read dan write untuk seluruh proses di data store diekseskusi pada beberapa perintah yang terurut (sequential) dan operasi untuk setiap proses terlihat pada urutan yang diperintah secara spesifik oleh program. Sebagai ilustrasi ada 4 proses mengeksekusi data yang sama yaitu x. Digambar proses P1 melakukan operasi W(x)a terhadap x. Begitupula untuk proses P2 dengan meerubah nilai dari x menjadi b. Proses P3 dan P4 awalnya membaca nilai b, kemudian membaca nilai a. Dengan kata lain proses write p2 terlihat mengambil posisi sebelum P1.

Gambar 6.2 (a)konsistensi secara terurut, namun konsisten (b) tidak menggunakan keterurutan konsistens

Urutan dalam urutan yang ditentukan oleh program. Selain itu, jika if Ts_°, (x) <1s₀p₂(y), maka operasi OP 1 (x) harus mendahului OP 2 (y) dalam urutan ini.
Perhatikan bahwa menyimpan data lincarizable juga berurutan konsisten. Para berbeda terletak pada kenyataan bahwa kita mengambil memesan sesuai dengan seperangkat jam disinkronisasi ke rekening. Dalam prakteknya, linearizability terutama digunakan untuk membantu verifikasi formal algoritma konkuren (Herlihy dan Wing, 1991). Penambahan kendala yang memesan sesuai dengan timestanms juga harus dipertahankan, membuat ibu linearizability mahal untuk diterapkan daripada konsistensi sekuensial, seperti pada (Attiya dan Welch, 1994).

Process P1	Process P2	Process P3
x = 1; print ( y, z);	y = 1; print (x, z);	z = 1; print (x, y);

Konsistensi Sequential sebanding dengan serializability dalam kasus transaksi. tions. seperti yang kita bahas di bab sebelumnya THC. Ingat bahwa koleksi sedang melaksanakan transaksi adalah serializahle jika hasil akhir bisa juga telah diperoleh dengan menjalankansatu transaksi setelah lain dalam beberapa berurutan. Perbedaan utama adalah bahwa granularity: konsistensi sekuensial didefinisikan dalam hal membaca dan menulis operasi, sedangkan scrializability didefinisikan dalam hal transaksi, yang agregat operasi tersebut.

Gambar 6-7. Tiga bersamaan mengeksekusi prozesses.

Untuk membuat gagasan konsistensi sekuensial lebih konkret, pertimbangkan tiga proses secara bersamaan mengeksekusi Pi, P2, dan P3, ditunjukkan pada Gambar. 6-7 (Dubois et al., 1938). Item data dalam contoh ini dibentuk oleh tiga variabel bilangan bulat x. y, dan z. yang disimpan dalam (mungkin didistribusikan) bersama berurutan menyimpan data yang konsisten. Kami berasumsi bahwa setiap variabel diinisialisasi ke 0. Dalam contoh ini, tugas sesuai 10 operasi tulis. sedangkan pernyataan print sesuai dengan operasi baca simultan dari dua argumen. Semua pernyataan diasumsikan ia terpisahkan.

Berbagai urutan eksekusi interleaved yang mungkin. Dengan enam laporan independen. ada potensi 720 (6!) urutan eksekusi mungkin, meskipun beberapa program yang melanggar perintah. Pertimbangkan 120 (5!) Urutan yang dimulai dengan x = 1. Setengah dari ini memiliki cetak (x, z) sebelum y = 1 dan dengan demikian melanggar perintah Program. Setengah juga memiliki cetak (t, y) sebelum z = 1 dan juga melanggar perintah Program. Hanya 1/4 dari 120 urutan. atau 30, adalah valid. Lain 30 urutan valid adalah POSSI 卢 ble dimulai dengan y = 1 dan 30 yang lain dapat dimulai dengan z = 1, untuk total 90 urutan eksekusi yang valid. Empat di antaranya ditunjukkan pada Gambar. 6-8.

x = 1; print ((y, z); y = 1; print (x, z); z = 1; print (x, y); Prints:  001011 Signature:    001011         (a)

x = 1; y = 1; print (x,z); print(y, z); z = 1; print (x, y); Prints: 101011 Signature:    101011         (b)

y = 1; z = 1; print (x, y); print (x, z); x = 1; print (y, z); Prints: 010111 Signature:    110101       (c)

y = 1; x = 1; z = 1; print (x, z); print (y, z); print (x, y); Prints: 111111 Signature:    111111       (d)

Dalam Gambar. 6-8 (a). tiga proses dijalankan dalam rangka, P1 pertama, kemudian P2. kemudian P3. Tiga contoh lain menunjukkan berbeda, tetapi sama-sama sah, interleavings dari laporan pada waktunya. Masing-masing dari tiga proses mencetak dua variabel. Karena sumbu vertikal adalah waktu.

Gambar 643. Empat urutan eksekusi berlaku untuk proses

Hanya nilai setiap variabel dapat mengambil adalah nilai awal (0). atau nilai yang diberikan (I), setiap proses menghasilkan string 2-bit. Angka-angka setelah Cetakan output aktual yang muncul pada perangkat output.

Jika kita menggabungkan output dari Pi. P2, dan P3 agar, kita mendapatkan string 6-bit yang mencirikan suatu interleaving tertentu pernyataan. Ini adalah string terdaftar sebagai Signature pada Gambar. 6-8. Di bawah ini kita akan menggolongkan setiap pemesanan dengan tanda tangan bukan oleh printout-nya.

Tidak semua pattents tanda tangan 64 diperbolehkan. Sebagai contoh sepele. 000000 tidak diperbolehkan, karena itu akan berarti bahwa laporan cetak berlari sebelum pernyataan penugasan, melanggar persyaratan bahwa laporan dijalankan dalam rangka Program. Sebuah contoh yang lebih halus adalah 001.001. Dua bit pertama. 00. berarti bahwa b dan c berdua 0 ketika P, melakukan pencetakan. Situasi ini terjadi hanya ketika Pi mengeksekusi kedua pernyataan sebelum P2 atau Ps dimulai. Selanjutnya dua bit. 10. berarti P2 yang harus dijalankan setelah PI dimulai sebelum P3 telah dimulai. Dua hits terakhir, 01. berarti P3 yang harus selesai sebelum P, mulai, tapi kami telah melihat bahwa P, harus pergi dulu. Oleh karena itu, 001.001 tidak diperbolehkan.

Singkatnya, 90 yang berbeda orderings pernyataan yang valid menghasilkan berbagai dif 卢 hasil program yang beda (kurang dari 64, meskipun) yang diperbolehkan di bawah asumsi 卢 tion konsistensi sekuensial. Kontrak antara proses dan distrib usikan 卢 bersama menyimpan data, adalah bahwa proses harus menerima semua hasil ini sebagai valid. Dengan kata lain, proses harus menerima empat hasil yang ditunjukkan pada Gambar. 6-8 dan semua hasil yang valid lain sebagai jawaban yang tepat, dan harus bekerja dengan benar jika salah satu dari mereka terjadi. Sebuah program yang bekerja untuk beberapa hasil dan bukan untuk orang lain melanggar kontrak dengan menyimpan data dan tidak benar.

Ada berbagai cara untuk secara resmi menyatakan konsistensi sekuensial (dan model lainnya). Pendekatan yang umum adalah sebagai berikut (Ahatnad et al, 1992;. Mizuno et al .. 1995). Setiap proses P, memiliki eksekusi Ey terkait. yang merupakan sebuah seq membaca dan menulis operasi oleh proses Pi dilakukan pada data store S. Urutan ini mematuhi perintah program yang terkait dengan?,.

Misalnya. eksekusi dari empat proses dalam Gambar. 6-6 (a) diberikan sebagai:

Li: (x) a

E2: 1112 (x) b

E3: R3 (x) b, R3 (x) a

E4: R4 (x) b. R.2 (x la

Untuk mendapatkan urutan relatif di mana operasi tampaknya dieksekusi, kita harus menggabungkan string operasi di 拢 1 menjadi sebuah string tunggal. H. dimana setiap operasi muncul di Ei muncul dalam 11 kali. Nya juga disebut sejarah. Intuitif. H memberi perintah bahwa operasi akan dilakukan seandainya ada sebuah toko tunggal terpusat. Semua nilai-nilai hukum untuk H harus mematuhi dua kendala.

Agar Program I. harus dipertahankan. 2. Data koherensi harus dihormati.

Kendala pertama berarti bahwa jika operasi membaca atau menulis. OPI, muncul sebelum operasi lain. 0P1, di salah satu string di E. OP! juga harus muncul sebelum 01'2 di H. Jika kendala ini berlaku untuk semua panci operasi, yang dihasilkan H tidak akan menunjukkan operasi dalam urutan yang melanggar salah satu program.

Kendala kedua THC, yang kita sebut sebagai koherensi data, berarti bahwa membaca R (x) untuk beberapa item data harus selalu mengembalikan nilai yang paling baru-baru ini ditulis dengan x: yaitu. nilai v ditulis oleh terbaru W (x) ip sebelum R (x). Data koherensi memeriksa dalam isolasi setiap item data dan urutan operasi di atasnya, tanpa memperhatikan data lainnya. Konsistensi, sebaliknya, berkaitan dengan menulis ke dif 卢 item data beda dan pemesanan mereka. Ketika khusus berurusan dengan memori bersama didistribusikan, dan lokasi memori bukan item data, koherensi data disebut koherensi memori.

Kembali ke empat proses dari Gambar. 6.6 (a), dapat dilihat bahwa nilai hukum untuk H : H = W1 (x) b, R3 (x) b, R4 (x) b, lY2 (x) a, R3 (x) o, R4 (x) a

Di sisi lain, untuk eksekusi dari empat proses dalam Gambar. 6-6 (b), tidak ada sejarah hukum dapat ditemukan karena tidak mungkin dalam sistem berurutan konsisten untuk membiarkan proses P3 pertama melakukan R) (x) b, dan kemudian R3 (x), sementara proses P4 membaca nilai-nilai dan bin urutan yang berbeda.

Untuk contoh lebih rumit mungkin ada beberapa nilai-nilai hukum H. Perilaku program dikatakan benar jika urutan operasi sesuai dengan beberapa nilai hukum H:

Meskipun konsistensi sekuensial adalah model programmer-anak, ia memiliki seri 卢 masalah kinerja ous. Lipton dan Sandberg (1988) membuktikan bahwa jika waktu membaca adalah r, waktu menulis adalah w, dan waktu transfer paket minimal antara nodesis 1, maka selalu benar bahwa r + w Dengan kata lain, untuk setiap berurutan con 卢 sistcnt toko, mengubah protokol untuk meningkatkan kinerja baca tulis membuat per 卢 kinerja buruk, dan sebaliknya. Untuk alasan ini, para peneliti telah meneliti model lain (lemah).

6.2.3Consistency Causal

Modelkonsistensikausal(Hutto danAhamad. /99)) merupakankonsistensi yangberurutanbahwa hal itumembuat perbedaan antaraperistiwayangberpotensikausalterkaitdengan waktu. Sudah diketahuikausalitasxroseketika membahascapvektordalam bab sebelumnya. JikaBacaradisebabkanataudipengaruhi olehsuatu peristiwasebelumnya, kausalitasA.mensyaratkan bahwaorang lainpertama melihatA.

Pertimbangkancontohmemori. MisalkanresesbahwaPrmenulisvariabel x. Kemudianmembacanx dany. Berikutpembacaanx danpenulisanyberpotensikausalterkait karenaperhitunganymungkintelah tergantung padanilaixdibaca olehP2nilaiditulis olehPI). Disisi lain, jika duaprosessecara spontan dansimultanmenulis duavariabel yang berbeda, makakausaltidak terkait. Ketika adamembacakemudian diikutiolehmenulis.duaperistiwayangberpotensikausalterkait. Demikian pula, membacasebuahkausal berkaitandenganmenulisyang menyediakandatareadmendapat.Operasiyang tidakkausal berkaitandikatakanbersamaan.Untukmenyimpan datayangdianggapkausalkonsisten. perlu bahwatokomematuhikondisiberikut:Menulisyangberpotensikausalterkaitharus dilihatoleh prosesIRTurutan yang sama. Bersamaan menulisdapat dilihatdalam urutan yang berbedapada mesin yang berbeda.

Sebagaicontohkonsistensikausal, pertimbangkan Gambar. 6-9. Di sinikita memilikirentetan kejadianyangdiperbolehkandengan toko-kausal yang konsisten, tetapi yangdilarangdengan tokoberurutankonsisten atautokosr/jettyyang konsisten. Yangperlu diperhatikan adalahbahwamenulisW2(x)b danW1 (x) cyang bersamaan, sehinggatidak diperlukanbahwa semuaproseslihatkemudian, dalam urutan yang sama.

Gambar6-9. urutan inidiperbolehkandengan tokosantaikonsisten, tapi tidak denganberurutanatau ketatkonsistentoko.

Sekarang perhatikancontoh kedua. Dalam Gambar. 6-10(a) kita memilikiW2(x) hberpotensitergantung padaWir.rthkarenabmungkin merupakanhasil dariperhitunganyang melibatkannilaidibaca olehR2(x) o. Duamenulis adalahkausalterkait, sehingga semuaprosesharusSeemereka dalamurutanSaint. Oleh karena itu. Gambar. 6.10(a) tidak benar. Disisi lain, pada Gambar. 6-10(b) membacatelah dihapus, sehinggatrii(x) dano11'2(x.) Bsekarangbersamaan menulis. Sebuah toko-kausal yang konsistentidak memerlukanbersamaan menulisakanmemerintahkanglobal. sehinggaGambar. 6-10(b) Benar.

Gambar6.10. (a) pelanggarantokosantaikonsisten.(b) urutanyang benar dariperistiwadi tokokausalkonsisten.

Menerapkankonsistensikausalmembutuhkanmenjagatrukyangmycosestelah melihatyangMenulis. Inisecara efektifberarti bahwagrafikketergantunganyangoperasitergantung dimanaoperasi lainnyaharusdibangun dandipertahankan¬utama. Salah satucara untuk melakukan iniadalah dengan caracap waktuvektor. seperti yang kita bahasdalam bab sebelumnya. Kamikembali kepenggunaancap waktuvektoruntuk menangkapkausalitaskemudian dalambab ini.

6.2.4FIFOKonsistensi

Dalamkonsistensikausal, ituyang diizinkanbersamaan menulisdilihat dalam3urutanferentpada mesin yang berbeda, meskipunyangkausalterkaitharus dilihat dalamrangkaoleh semuamesin. Langkah berikutnya dalamconststencysantaiadalah untuk menjatuhkanpersyaratanyang terakhir. MelakukanmemberikankonsistensiFIFO, yangtunduk padakondisi:Menulisdilakukan olehproses tunggalyangdilihat olehsemua proseslain ditukang kudakenaikanmampu: merekadikeluarkan, tetapimenulis dariproses yang berbedadapat dilihatdalam urutan yang berbedaoleh prosesMeseta!.

FIFOkonsistensidisebutPRAMkonsistensi dalamkasussistemterdistribusimemori bersama dandijelaskan dalam(Lipson danSandberg. MS). PRAMsingkatanPip: RAMberlapis. karenatungaudengan prosestunggal dapatpipelined. yaitu,prosestidak harusmenungguwarunguntuk masing-masinglengkapsebelum memulaiyang berikutnya. FIFOkonsistensikontrasdengan konsistensikausalpada Gambar. 6-11. Urutanperistiwayang ditampilkan di sinidiperbolehkandengan tokoFIFOdata yang konsistentapi tidak dengansalah satu modelkuattelah kita pelajarisejauh ini.

KonsistensiFIFOmenarikkarena mudahuntuk diimplementasikan.Akibatnyadikatakanbahwa tidak adajaminantentangurutanproses yang berbedasecmenulis, kecuali bahwadua atau lebihmenulisdari satu sumberharus tibadalam urutan. Dimasukkan ke dalamistilah lain, dalam modelini semuamenulisdihasilkan olehbusurproses yang berbeda

bersamaan. Model inidapatdilaksanakan dengan hanyamenandai setiapoperasi menulisdengan(proses nomor urut) pasangan, dan melakukanmenulisper prosesdalam urutannomor urutmereka.

Mari kitasekarangmempertimbangkantigaprosesFig.6.7tapi kali inimenggunakankonsistensiFIFObukankonsistensisekuensial. DalamFIFOkonsistensi. proses yang berbedadapat melihatlaporandieksekusidalam urutan yang berbeda. Misalnya.6.12(a) menunjukkan bagaimanaPrmungkin melihatperistiwa. sedangkanGambar. 6.12(b) menunjukkan bagaimanaPzmungkin melihatmereka danGambar. 6-12(c) menunjukkanpandanganPxitu. Untuktokoberurutankonsisten.pandanganyang berbeda-Mu tidak akan diizinkan.

x = 1; print (y, z); y = 1; print(x, z); z = 1; print (x, y); Prints: 00      (a)

x = 1; y = 1; print(x, z); print ( y, z); z = 1; print (x, y); Prints: 10        (b)

y = 1; print (x, z); z = 1; print (x, y); x = 1; print (y, z); Prints:  01      (c)

Gambar 6-12. eksekusi pernyataanseperti yang terlihat olehtiga prosesdariara. 6.7. pernyataandalam huruf tebaladalah orang yangmenghasilkanoutput yang ditunjukkan.

Jika kita menggabungkan output dari tiga proses, kita mendapatkan hasil dari C01001. yang, seperti yang kita lihat sebelumnya, tidak mungkin dengan konsistensi sekuensial. Perbedaan utama antara konsistensi sekuensial dan konsistensi FIFO adalah bahwa dengan mantan, meskipun urutan eksekusi pernyataan adalah nondeterministie, setidaknya proses nil setuju apa itu. Dengan kedua, mereka perlu atau setuju. Differen: proses dapat melihat operasi dalam urutan yang berbeda.

Process P1	Process P2
x = 1; if (y == 0) kill (P2);	y = 1; if (x == 0) kill (P1);

Kadang-kadang konsistensi FIFO dapat menyebabkan hasil yang mungkin berlawanan. Pada contoh berikut ini, dijelaskan dalam (Goodman, 1989). mengasumsikan bahwa variabel integer x dan y yang diinisialisasi ke 0. Dalam Gambar. 6-13 satu naif mungkin berharap salah satu dari tiga kemungkinan hasil: P, terbunuh. P2 dibunuh, atau tidak dibunuh (jika dua tugas duluan). Dengan konsistensi FIFO, namun. kedua proses dapat dibunuh. Hasil ini dapat terjadi jika P, membaca RI (y) 0 sebelum melihat P W2 (01 dan P2 membaca WO RI sebelum melihat Pi W1 (01. Dengan menyimpan data secara berurutan konsisten, ada enam interleavings pernyataan mungkin. Dan tidak ada mereka menghasilkan kedua proses dibunuh.

6.2.5 Konsistensi Lemah

Meskipun konsistensi FIFO dapat memberikan kinerja yang lebih baik daripada model konsistensi kuat, masih perlu membatasi untuk banyak aplikasi karena mereka mengharuskan menulis berasal dalam suatu proses tunggal dilihat setiap tempat dalam rangka. Tidak semua aplikasi membutuhkan bahkan melihat semua menulis, apalagi melihat mereka dalam rangka. Pertimbangkan kasus suatu proses di dalam catatan menulis bagian yang kritis 10 database direplikasi. Meskipun proses lain tidak Sapp/064d sentuh 10 catatan sampai proses pertama telah meninggalkan critical section-nya, sistem database tidak memiliki cara untuk mengetahui kapan sebuah proses di bagian kritis dan jika tidak, tanah harus menyebarkan semua menulis ke semua salinan database.

Sebuah solusi yang lebih baik akan membiarkan dia selesai proses di bagian kritis dan kemudian memastikan bahwa hasil akhir akan dikirim di mana-mana, tidak terlalu khawatir apakah semua hasil antara juga telah disebarkan ke semua salinan dalam rangka. Atau bahkan sama sekali. Secara umum, hal ini dapat dilakukan dengan memperkenalkan apa yang disebut sebagai variabel syn chronization ¬. Sebuah S variabel sinkronisasi hanya memiliki operasi terkait satu menyinkronkan (S), yang mensinkronisasikan semua salinan lokal menyimpan data. Ingatlah bahwa proses P melakukan operasi hanya pada salinannya tersedia secara lokal dari toko. Ketika menyimpan data yang akan disinkronkan, semua lokal menulis dengan proses P yang disebarkan ke salinan lain, sedangkan menulis oleh proses lainnya dibawa ke copy P.
Menggunakan variabel sinkronisasi untuk sebagian menentukan konsistensi mengarah pada apa yang disebut konsistensi yang lemah (Dubois et al .. 1988). Model konsistensi yang lemah memiliki tiga sifat:

1.    Mengakses ke-sinkronisasi variabel yang terkait dengan penyimpanan data, yang secara berurutan konsisten

2.    Tidak ada operasi pada variabel sinkronisasi diperkenankan untuk terbentuk sampai sebelumnya semua menulis telah menyelesaikan di mana-mana.

3.    Tidak ada operasi membaca atau menulis data itmu yang diizinkan untuk terbentuk anal semua operasi sebelumnya untuk variabel sinkronisasi telah dilakukan.

Titik pertama mengatakan bahwa semua proses melihat semua operasi pada sinkronisasi variabel dalam urutan yang sama. Dengan kata lain, jika proses P, panggilan menyinkronkan (S1) pada saat yang sama bahwa P2 proses panggilan synehronize (S2). efeknya akan sama seperti jika salah eynchrectize (S1) didahului SynChrenize (S2), atau sebaliknya vetsa.

Titik kedua mengatakan sinkronisasi yang "flushes pipa." Ini memaksa semua menulis bahwa sedang berlangsung atau panially selesai atau diselesaikan di beberapa salinan lokal tetapi tidak yang lain untuk menyelesaikan di mana-mana. Ketika sinkronisasi dilakukan. 311 sebelumnya menulis dijamin akan dilakukan juga. Dengan melakukan sinkronisasi setelah memperbarui data bersama, proses dapat memaksa nilai-nilai baru keluar untuk semua salinan lokal lainnya dari toko.

Titik ketiga mengatakan bahwa ketika item data yang dipilih, baik untuk membaca atau menulis, semua sinkronisasi sebelumnya akan telah selesai. Dengan melakukan sinkronisasi sebelum membaca data bersama, proses dapat yakin untukmendapatkan nilai-nilai yang terbaru.

Berbeda dengan model sebelumnya konsistensi, konsistensi lemah memaksa con konsistensi pada sekelompok operasi. bukan pada individu membaca dan menulis. Model ini paling berguna ketika akses ke data bersama terisolasi jarang, dengan mengakses paling datang dalam kelompok (akses banyak dalam waktu singkat maka tidak ada untuk waktu yang lama.).Perbedaan penting lainnya dengan model konsistensi sebelumnya adalah bahwa kita sekarang membatasi hanya saat memegang konsistensi, daripada membatasi bentuk konsistensi. Pada kenyataannya, kita bisa mengatakan bahwa dengan konsistensi yang lemah,sekuensialkonsistensi diberlakukan antara kelompok operasi bukan antara operasi individu. Sinkronisasi variabel yang digunakan untuk membatasi kelompok-kelompok.

int a, b, c, d, e, x, y;                            /* variables */

int *p, *q;                                            /* pointers */

int f( int *p, int *q);                            /* function prototype */

a = x * x;                                             /* a stored in register */

b = y * y;                                             /* b as well */

c = a*a*a + b*b + a * b;                      /* used later */

d = a * a * c;                                       /* used later */

p = &a;                                                /* p gets address of a */

q = &b                                                 /* q gets address of b */

e = f(p, q)                                            /* function call */

Gambar6-14. Sebuahprovion(bagmen: di manaHornevarwletesnaydisimpan dalamregister.

Gagasan memilikimemoriyangsalahbukanlah hal baru.Banyakkompilermenipujuga.Sebagaicontoh, perhatikanfragmen programGambar.6-19, dengansemua variabeldiinisialisasi kenilai yang sesuai. Sebuah opsicompilerdapat memutuskan untukmenghitunga dan bdalam registerdanmenjaga nilai-nilaidi sana untuk sementara, tidakmemperbaruilokasimemori mereka. Hanya ketikaMefungsifdisebutcompilermemilikiuntuk menempatkannilai-nilaisaat inidaria dan bhackdalam memori. karena sayamungkin akan mencobauntuk mengaksesnya. Ini adalahoptimasicompilerkhas.

Memilikimemoribisa salahditerimadi sini karenacompiler tahuapa yang dilakukannyayaitu, karena perangkat lunaktidakBersikerasmemori yangmenjadiup.m.date). Jelas, jikaproses keduaadayang dapat membacamemori dalamuncon. carategang. skema initidak akan bekerja. Misalnya,jika selamatugas untukd, proses keduamembaca, b. dan, itu akan mendapatkannilai-nilaiyang tidak konsisten(nilai-nilai lama danb. tetapi nilaibaru e). Orang bisamembayangkan carakhusus untuk mencegahkekacauandengan memilikicompilerpertamamenulisflagbit khususmengatakanbahwa memoriadalah dari tanggal. Jikaproses laininginmengakses, itu akansibukmenunggu dibitflag. Dengan cara ini seseorangdapat hidupdengan kurang darikonsistensi yang sempurnaasalkansinkronisasidilakukandalam perangkat lunakdan semuapanikmematuhi aturan.

Sekarangmari kitamempertimbangkan situasiagak kurangterlalu mengada-ada. Dalam Gambar. 6.15(a) kita melihat bahwaprosesPimelakukan duamenuliske itemdata, dan kemudianmensinkronisasikan(ditandai dengan huruf S). JikaP2danPxbelumdisinkronkan, tidak adajaminanalediberikan tentangapa yang mereka lihat. sehinggaurutan kejadianberlaku.

Gambar6-15. jauhUrutanvalidacara, untuk konsistensi. (b) Sebuah urutanvaliduntuk konsistensilemah.Gambar. 6.15(b) berbeda.

BerikutP2telahdisinkronkan, yang berartibahwa salinanlokaldaridata storedibawaup to date.Ketika membacax, itu Harusmendapatkan nilaib. Mendapatkan. seperti yang ditunjukkanpada gambar. tidak diizinkandengan konsistensiyang lemah.

6.2.6Konsistensi Rilis

Konsistensiyang lemahmemilikimasalahbahwa ketikavanablesinkronisasidiakses, data storetidak tahuapakah hal inidilakukan karenaproses inibaikselesai menulisdatabersama ataujika tidakakanmembaca data. Akibatnya. harusmengambiltindakan yang diperlukandalam kedua kasus. yaitumak. ingyakinbahwasemua lokaldimulaimenulistelah selesai(misalnya, disebarkan ke semuaSalinanlainnya), sertamengumpulkansemuamenulis darisalinan lain. Jika tokobisamembedakan antaramemasukidaerah kritisdanmeninggalkan satu, implementasi yang lebihefisienmungkin mungkin.Untukmemberikan informasiini, dua jenisvariabelsinkronisasiAtauoperasi diperlukanbukan satu.

KonsistensiRelease (Gharachorloo Clal../990: menyediakanduajenis.OperasiMemperolehdigunakan untuk memberitahumenyimpan databahwadaerah kritisakan segeramasuk, sedangkanoperasirilismengatakan bahwadaerah kritisbaru sajakeluar. operasi inidapat diimplementasikan dalamsalah satu daridua cara(1)operasi biasapada variabelkhusus atau(2) operasi khusus. cara baik, programmerbertanggung jawab untukmemasukkankodeeksplisitdalam programmenyatakankapan harusmelakukan operasi. misalnya.dengan memanggilprosedurperpustakaansepertimemperoleh danmelepaskan ataupreceduresseperti_regionenter_ciriticaldanleave_critical_region.

Hal inijuga memungkinkan untuk menggunakanhambatanbukandaerah kritisdengan riliskonsistensi. Penghalangadalahmekanismesinkronisasiyang mencegahproses apapundari mulaifase Idari sebuah programsampai semuaprosesselesaifase. Ketika prosestiba diharrier, ia harus menunggu sampai semuaproses lainnyasampai ke sana juga. Ketikayang terakhirtiba, semuadata bersamadisinkronisasidan kemudiansemua prosesdilanjutkan.Berangkat daripenghalangdilakukanpadamemperoleh,dankedatangandilakukan padarilis.Selainoperasisinkronisasi,membaca dan menulisdata bersamajuga mungkin.Memperolehdan melepaskantidak harusberlaku untuksemua datadi tokoSebaliknya, mereka mungkinhanyamenjagadata bersamayang spesifik, di manahanya merekamelemparkanitem datadisimpankonsisten.DataBersamayang disimpankonsistendikatakandiadilindungi.
Sebuah tokodata yangoilersrilismenjaminkonsistensibahwa ketikaprocescyangtidakmemperolehsebuah, toko akanmemastikan bahwa semuasalinan lokalyang dilindungidaoyangdibawa up to dateagar sesuaidenganyang terpenciljika perlu. Ketika rilisdilakukan, data yang dilindungiyang telah diubahdisebarkankepadasalinanlokal lainnyastola. Melakukansebuahmengakuisisitidak menjamin bahwalc-kati membuat perubahanakan dikirim kesalinanlokal lainnyasegera.Demikian pula, melakukanrilistidak selalumengimporperubahan darisalinan lain.

Gambar. 6.16 menggambarkan urutan peristiwa berlaku untuk rilis konsistensi.

Proses P1 tidak memperoleh sebuah. mengubah item data bersama dua kali, dan kemudian melakukan sebuah rilis. Proses P2 arti sebuah mendapatkan dan membaca data barang x. Hal ini dijamin untuk mendapatkan nilai yang punya e pada saat rilis. yaitu b (kecuali mengakuisisi P2 melakukan befoic Pi '5 mengakuisisi). Memperoleh lentur telah dilakukan sebelum Pi melakukan rilis. Memperoleh akan ditunda sampai rilis telah terjadi. Karena P3 tidak melakukan memperoleh sebelum membaca data bersama, data store tidak memiliki kewajiban untuk memberikan nilai saat sering, sehingga mengembalikan diperbolehkan.

Untuk membuat belajar kembali konsistensi lebih jelas, mari kita jelaskan secara singkat kemungkinan implementasi berpikiran sederhana dalam konteks database direplikasi. Untuk melakukan akuisisi, proses mengirim pesan ke permintaan manajer sinkronisasi pusat. ing memperoleh pada kunci tertentu. Dengan tidak adanya kompetisi apapun. permintaan ini disetujui dan memperoleh selesai. Kemudian urutan sewenang-wenang membaca dan menulis ke data bersama dapat terjadi secara lokal. Tak satu pun dari yang disebarkan kesalinan lain dari database. Ketika rilis dilakukan. data yang dimodifikasi dikirim ke salinan lain yang menggunakannya. Setelah setiap salinan telah mengakui penerimaan data, manajer sinkronisasi informasi dari rilis. Dengan cara ini. sebuah Athi. jumlah gila membaca dan menulis pada data bersama makan dilakukan dengan jumlah yang tetap overhead. Mengakuisisi dan rilis Pada batuan yang berbeda terjadi secara independen satu sama lain.
Sedangkan algoritma terpusat dijelaskan di atas akan melakukan pekerjaan. itu adalah dengan tidak berarti satu-satunya pendekatan. Secara umum, menyimpan data terdistribusi adalah rilis konsisten jika mematuhi aturan berikut:

1.    Sebelum membaca atau menulis operasi pada data bersama pelforrned, semua sebelumnya mengakuisisi dilakukan oleh proses harus selesai dengan sukses.

2.    Sebelum rilis diperbolehkan ro dilakukan, semua sebelumnya membaca dan menulis dilakukan dengan proses tersebut harus telah selesai.

3.    Akses ke variabel sinkronisasi adalah FIFO konsisten (konsistensi sekuensial tidak diperlukan).

Jika semua kondisi ini makan bertemu dan proses memperoleh dan menggunakan melepaskan benar (yaitu, dalam memperoleh-release pasang), hasil eksekusi apapun akan tidak berbeda dari mereka telah dengan menyimpan data secara berurutan konsisten. Akibatnya, blok operasi pada data bersama yang dibuat oleh atom memperoleh dan melepaskan primitif untuk mencegah interleaving.
Sebuah implementasi yang berbeda dari rilis konsistensi adalah rilis konsistensi malas. (Keleher et al .. 1992). Dalam nom & rilis konsistensi. yang akan kita selanjutnya menelepon rilis konsistensi bersemangat untuk membedakannya dari varian malas, saat rilis dilakukan, proses melakukan rilis mendorong keluar semua data dimodifikasi untuk semua proses lain yang sudah memiliki salinan data dan dengan demikian berpotensi perlu itu. Tidak ada cara untuk mengetahui apakah mereka benar-benar akan membutuhkannya. jadi aman, mereka semua mendapatkan segala sesuatu yang telah berubah.

Meskipun mendorong semua data keluar dengan cara ini sangat mudah, umumnya inef6cient. Dalam rilis konsistensi malas, pada saat rilis, tidak ada yang dikirim di mana saja. Sebaliknya, ketika mengakuisisi dilakukan, proses mencoba untuk melakukan Memperoleh harus mendapatkan nilai-nilai yang terbaru dari data dari proses atau proses menahan mereka. Sebuah protokol tinzstamp dapat digunakan untuk menentukan item data harus benar-benar terbatas.Dalam banyak program, daerah kritis terletak di dalam lingkaran. Dengan rilis konsistensi bersemangat. pada setiap melewati loop rilis dilakukan, dan semua data yang dimodifikasi harus didorong ke semua proses memelihara salinan dari mereka. Algoritma ini limbah bandwidth dan memperkenalkan penundaan perlu. Dengan rilis konsistensi malas, di rilis tidak ada yang dilakukan. Pada Memperoleh berikutnya, proses menentukan bahwa ia sudah memiliki semua data yang dibutuhkan, sehingga tidak ada pesan yang dihasilkan di sini baik. Hasil akhirnya adalah bahwa dengan malas rilis konsistensi tidak ada lalu lintas jaringandihasilkan sama sekali sampai proses lain tidak memperoleh sebuah. Berulang pasang acquitc-release dilakukan dengan proses yang sama dengan tidak adanya kompetisi di luar bebas.

6.2.7 Konsistensi Entri

Konsistensi model lain yang telah dirancang untuk digunakan dengan bagian kritis adalah konsistensi masuk (Bershatt et al .. 1993). Seperti kedua varian rilis konsistensi, memerlukan programmer (atau kompilator) untuk menggunakan mendapatkan dan melepaskan pada awal dan akhir setiap bagian kritis. masing-masing. Namun, tidak seperti rilis konsistensi, konsistensi entri memerlukan masing-masing berbagi item data biasa menjadi asosiasi yang diasosiasikan dengan beberapa variabel sinkronisasi seperti kunci atau penghalang. Jika desited bahwa elemen array diakses secara independen secara paralel, elemen array kemudian berbeda harus dikaitkan dengan kunci yang berbeda. Ketika mengakuisisi dilakukan Pada variabel sinkronisasi, hanya data yang dijaga oleh variabel sinkronisasi dibuat konsistensi Masuk konsisten berbeda depan malas rilis konsistensi dalam bahwa yang terakhir tidak asosiasi item data bersama dengan kunci atau riers bar 'dan pada waktu memperoleh harus mengetahui secara empiris yang variabel yang dibutuhkan.
Bergaul daftar data tenda bersama dengan masing-masing variabel sinkronisasi mengurangi overhead yang terkait dengan mendapatkan dan melepaskan variabel sinkronisasi karena hanya beberapa item data bersama harus disinkronkan. Hal ini juga memungkinkan beberapa bagian penting yang melibatkan data bersama menguraikan untuk mengeksekusi secara bersamaan. meningkatkan jumlah paralelisme. Harga yang dibayarkan adalah overhead tambahan dan kompleksitas menghubungkan setiap item data bersama dengan sonic sinkronisasimampu.

Pemrograman dengan cara ini juga dapat lebih rumit dan rawan kesalahan.
Variabel sinkronisasi ale digunakan sebagai berikut. Setiap variabel sinkronisasi memiliki pemilik saat ini, yaitu, proses yang terakhir memperolehnya. Pemilik Mei masuk dan keluar bagian kritis berulang kali tanpa harus mengirim pesan apapun yang jaringan. Reses A saat ini tidak memiliki variabel sinkronisasi tapi ingin memperolehnya harus mengirim pesan ke pemilik saat ini meminta kepemilikan dan nilai saat ini dari data yang terkait dengan variabel sinkronisasi. ini juga memungkinkan beberapa proses untuk secara bersamaan memiliki variabel sinkronisasi dalam mode eksklusif, yang berarti bahwa mereka dapat membaca, tapi tidak menulis, data yang terkait.Secara formal, menyimpan data menunjukkan konsistensi masuk jika memenuhi semua kondisi berikut berlabuh dan Zekausas. 1991):

1.    memperoleh akses dari variabel sinkronisasi tidak diperbolehkan untuk melakukan sehubungan dengan proses sampai semua update ro data bersama dijaga telah dilakukan sehubungan dengan proses tersebut.

2.    Sebelum mode akses eksklusif untuk variabel sinkronisasi dengan
Proses diperbolehkan untuk pegorrn sehubungan dengan proses itu, tidak ada lainProses dapat memegang variabel sinkronisasi, bahkan dalam mode eksklusif.

3.    Setelah mode akses eksklusif untuk variabel sinkronisasi telah peiformed, dekat mode akses eksklusif setiap proses lain untuk variabel sinkronisasi mungkin tidak akan sampai prijormed Ini telah dilakukan dalam kaitannya membusuk / pemilik variabel Car.

Kondisi pertama mengatakan bahwa ketika proses tidak merupakan memperoleh, memperoleh tidak dapat menyelesaikan (kontrol kembali mis. ke pernyataan berikutnya) sampai semua data bersama dijaga telah dibesarkan tanggal Co. Dengan kata lain, pada memperoleh, semua perubahan remote untuk data dijaga harus ia membuat terlihat.

Kondisi kedua mengatakan bahwa sebelum memperbarui item data bersama, proses harus memasukkan wilayah penting dalam mock eksklusif untuk membuat yakin bahwa tidak ada proses lain yang hying untuk memperbaruinya pada waktu yang sama.

Kondisi ketiga mengatakan bahwa jika suatu proses ingin memasuki daerah kritis dalam mode eksklusif, pertama kali harus memeriksa dengan pemilik sinkronisasi variabel ¬ mampu menjaga wilayah penting untuk mengambil salinan terbaru dari data bersama dijaga.

Gambar. 6-17 menunjukkan contoh konsistensi entri. Alih-alih operasi pada seluruh data bersama, dalam contoh ini kita kaitkan kunci dengan setiap item data. Dalam hal ini tidak b1 sebuah mengakuisisi untuk x. mengubah a-sekali, setelah itu juga tidak memperoleh suatu untuk y. Proses P, apakah merupakan memperoleh untuk x tetapi tidak untuk y. sehingga akan membaca nilai untuk x. tetapi dapat membaca MI. untuk y. Karena proses PI pertama melakukan suatu memperoleh untuk y. akan membaca nilai y ketika dilepaskan oleh P1.

Salah satu masalah pemrograman dengan konsistensi entri data yang benar bergaul dengan variabel sinkronisasi. Salah satu pendekatan untuk masalah ini adalah penggunaan benda Bersama didistribusikan. Ia bekerja sebagai berikut. Setiap objek didistribusikan memiliki variabel sinkronisasi terkait. Variabel ini disediakan oleh sistem terdistribusi yang mendasari setiap kali objek terdistribusi yang dikawinkan, tetapi sebaliknya sama sekali tersembunyi dari klien.

Ketika klien memanggil metode objek terdistribusi, sistem yang mendasari pertama tidak memperoleh sebuah variabel yang terkait pada sinkronisasi objek. The lih. kaki adalah bahwa nilai terbaru negara objek, yang dapat direplikasi dan didistribusikan di beberapa mesin, dibawa ke salinan klien dari objek. Pada saat itu, doa yang dilakukan, sementara objek tetap terkunci untuk operasi bersamaan. Ketika doa selesai, maka dilanjutkan dengan operasi rilis implisit, yang juga membuka objek untuk operasi tertunda.

Efeknya adalah bahwa semua akses ke sebuah objek terbagi terdistribusi berurutan konsisten. Untungnya, klien tidak perlu khawatir tentang sinkronisasi
variabel, karena ini benar-benar ditangani oleh sistem terdistribusi yang mendasari. Pada kapur yang sama, setiap objek secara otomatis dilindungi secara simultan mengeksekusi invotations bersamaan.

Pendekatan ini telah diimplementasikan dalam bahasa pemrograman Oita (Bal et al, 1992;.. Bat et al, 1998), yang akan kita bahas secara rinci nanti dalam bab ini. Pendekatan serupa juga telah diikuti di CRL (Johnson et al .. 1995). di mana objek yang tampil dalam bentuk nonoverlapping daerah memori bersama didistribusikan. Setiap daerah memiliki variabel sinkronisasi terkait yang disediakan oleh sistem runtime yang mendasari. Sistem runtime mengurus sinkronisasi bila suatu daerah diakses.

2.8 Konsistensi Ringkasan Model

Meskipun lain (data-centric) model konsistensi telah diusulkan. yang utama yang dibahas di atas. Mereka berbeda dalam bagaimana membatasi mereka betapa kompleks implementasi mereka, kemudahan pemrograman, dan perfonnanee mereka. Konsistensi yang ketat adalah yang paling ketat, tetapi karena implementasinya dalam sistem terdistribusi pada dasarnya tidak mungkin, tidak pernah digunakan.
Linearizability adalah model konsistensi lemah berdasarkan jam disinkronisasi. Itu membuat penalaran tentang kebenaran program bersamaan lebih mudah. tetapi sebaliknya hampir tidak pernah digunakan untuk benar-benar membangun program.

Dari perspektif ini, model yang lebih baik adalah konsistensi sekuensial, yang telah terbukti layak, populer dengan programmer, dan memang banyak digunakan. Ini memiliki masalah kinerja yang buruk, namun. Cara untuk berkeliling hasil ini adalah untuk bersantai model konsistensi. Beberapa kemungkinan ditunjukkan pada Gambar. 6.18 (a). kira-kira dalam rangka penurunan juga keterbatasan.

Konsistensi kausal dan FIFO) konsistensi keduanya mewakili melemah, di mana tidak ada lagi yang disepakati secara global pada pandangan yang operasi muncul di mana urutan. Proses yang berbeda dapat melihat urutan yang berbeda dari operasi. Kedua model berbeda dalam hal mana urutan yang diperbolehkan dan yang saya tidak, tetapi dalam semua memudahkan terserah kepada programmer untuk menghindari melakukan hal-hal yang bekerja hanya jika data penggerusan yang berurutan konsisten.

Sebuah pendekatan yang berbeda adalah untuk memperkenalkan variabel sinkronisasi eksplisit. seperti halnya konsistensi lemah, rilis konsistensi, dan konsistensi entri. Ketiga dirangkum dalam Gambar. 6-18 (6). Ketika sebuah proses melakukan operasi pada item data bersama biasa, ada jaminan yang diberikan tentang kapan mereka akan terlihat oleh proses lainnya. Hanya ketika sinkronisasi eksplisit terjadi perubahan yang disebarkan. Tiga model berbeda dalam bagaimana sinkronisasi bekerja, tetapi dalam semua kasus proses Dapat melakukan beberapa membaca dan menulis di bagian kritis tanpa melibatkan setiap pengangkutan data. Ketika bagian kritis telah selesai. hasil akhir adalah baik disebarkan ke proses lain atau dibuat siap propgation harus setiap proses mengekspresikan kepentingan lain dalam data tersebut

Consistency	Description
Strict	Absolutewaktupemesanansemua halaksesbersama.
Linearizability	Semua prosesharus melihatsemua aksesbersamadalam urutan yang sama. Aksesyangselanjutnyamemerintahkanmenurut(uniknya) timestamp global
Sequential	Semua prosesmelihatsemua aksesbersamadalam urutan yang sama. Aksestidakmemerintahkandalam waktu
Causal	Semua prosesmelihataksesbersamakausalterkaitdalam urutan yang sama.
FIFO	Semua prosesmelihatmenulisdari satu sama laindalam urutanmereka digunakan. Menulis dariproses yang berbedamungkin agar tidak selaludilihat
	(a)
Consistency	Description
Weak	Data bersamadapatdiandalkan untuk menjadikonsistenhanya setelahsinkronisasidilakukan
Release	Berbagi datadibuat konsistenketika suatu wilayahkritiskeluar
Entry	Berbagi datayang berkaitan dengandaerah kritisdibuat konsistenketikadaerah kritisdimasukkan.
	(b)

Gambar 6.18. (A) Konsistensi rrackls nee menang synchronitsson esserabons. (B) model dengan operasi sinkronisasi.

Singkatnya, konsistensi lemah, rilis konsistensi, dan konsistensi entri membutuhkan pemrograman tambahan konstruksi itu. bila digunakan sebagai diarahkan, memungkinkan progtam. pria berpura-pura bahwa toko data berurutan konsisten, ketika, dalam kenyataannya, tidak. Pada prinsipnya. ketiga model menggunakan sinkronisasi eksplisit harus mampu menawarkan kinerja terbaik, tetapi ada kemungkinan bahwa aplikasi yang berbeda akan memberikan hasil yang cukup berbeda.

6.3 CLIENT-CENTRIC CONSISTENCY MODELS

            Modelkonsistensidijelaskan dalambagian sebelumnyabertujuanuntuk memberikansuatusystemwidekonsistenmelihat padasebuah tokodata.Sebuah asumsipenting adalah bahwaproses konkurendapatsecara bersamaanmemperbaruimenyimpan data, danbahwa itu adalahdiperlukan untuk memberikankonsistensidalam menghadapikonkurensitersebut. Misalnya, dalamkasusberbasis obyekkonsistensimasuk, menyimpan datamenjamin bahwaketika sebuahobjekdisebut, proses pemanggilandilengkapi dengansalinandari objekyang mencerminkansemua perubahanke objekyang telah dibuatsejauh ini,mungkin olehproses lainnya. Selama panggilan berlangsung, juga menjamin bahwatidak ada proses laindapatinterferethatadalah, akses eksklusifsalingdisediakanuntuk proses pemanggilan.

            Mampumenanganioperasi-bersamaan pada databersamadengan tetap menjagakonsistensisekuensialadalah dasarsistem terdistribusi. untukkinerja
alasan, konsistensisekuensialmungkin dapatdijaminhanya ketikaprosesmenggunakan mekanismesinkronisasiseperti transaksiataukunci.

            Padabagian ini, kita melihatpadakelas khususmenyimpan dataterdistribusi. Itumenyimpan datakita mempertimbangkandicirikan olehkurangnya pembaruansimultan, atauketika updatetersebutterjadi, merekadengan mudahdapatdiselesaikan. Sebagian besar melibatkanoperasimembaca data. Inimenyimpan datamenawarkan modelkonsistensisangat lemah, akhirnyadisebutkonsistensi. Dengan memperkenalkankhusus klien-sentris modelkonsistensi, ternyatabahwainkonsistensibanyakdapat disembunyikandengan cara yangrelatif murah.

6.3.1 Eventual Consistency

            Sampai sejauh manaprosesbenar-benar beroperasisecarabersamaan, dan untuk apakonsistensisejauhperludijamin, dapat bervariasi. Adabanyak contohdiyangconcurrencyhanya munculdalam bentukterbatas. Sebagai contoh, di banyak databasesistem, proses yang palinghampir tidak pernahmelakukan operasiupdate;mereka kebanyakanmembaca datadari database. Hanya satuproses, atausangat sedikitmelakukan operasiupdate.Pertanyaannyakemudian adalahseberapa cepatupdateharus dibuattersedia untukonlyreadingproses.

            Sebagai contoh lain, mempertimbangkan sistempenamaandi seluruh dunia sepertiDNS. ItuDNSruang namadipartisi menjadidomain, di manasetiap domainyangditugaskan untukpenamaanotoritas, yang bertindak sebagaipemilikdomain tersebut. Hanyaotoritasyang diperbolehkanuntuk memperbaruibagiannyadariruang nama. Akibatnya, konflikakibatdua operasiyangsama-sama inginmelakukan updatepada data yang sama(yaitu, writewritekonflik), tidak pernahterjadi.Situasi-satunya yang perluditangani adalah
baca-tulis konflik, di manasatu prosesyang inginmemperbaruiitem datasementara yang lainsecarabersamaanmencoba untuk membacaitem itu. Ternyata, seringuntuk menyebarkanupdatedalam modemalas, yang berarti bahwaprosespembacaanakan melihatupdatehanya setelahbeberapa waktutelah berlalu sejakupdateberlangsung.

            Namuncontoh lainadalahWorld Wide Web. Dalamhampirsemua kasus, Webhalamandiperbaruiolehotoritastunggal, sepertiwebmasteratau pemilikyang sebenarnyahalaman. Adabiasanyatidak menulis-menulis untuk menyelesaikankonflik. Di sisi laintangan, untuk meningkatkan efisiensi, danbrowserWeb proxyseringdikonfigurasi untukmenyimpanhalamandiambil dalamcachelokal dankembalihalaman tersebutataspermintaan berikutnya

            Sebuah aspek penting darikedua jeniscacheWebadalah bahwa merekadapat kembalioutof-saathalaman Web. Dengan kata lain, halamancacheyangdikembalikan kememintaklien adalahversi lamadibandingkandengan yangtersedia diWeb yang sebenarnyaserver.Ternyata, banyak pengguna menemukaninkonsistensiinidapat diterima(untuk tertentuderajat).

            Contoh-contoh inidapat dilihat sebagaikasus(besar-besaran) didistribusikan dandireplikasidatabase yangmentolerirtingkat yang relatif tinggiinkonsistensi. mereka memilikikesamaan bahwajika tidak adaupdateberlangsunguntuk waktu yang lama, semuareplikasecara bertahap akanmenjadikonsisten. Bentukkonsistensidisebutkonsistensiakhirnya.

            Datatokoyangpada akhirnyakonsistensehingga memilikipropertibahwa dalamadanyapembaruan, semuareplikamenyatuterhadapsalinan identiksatu sama lain. Konsistensiakhirnyadasarnyahanya membutuhkanbahwa pembaruandijaminuntuk menyebarkanuntuk semuareplika. Tulis-menulis konflikseringrelatif mudahuntuk memecahkanketikadengan asumsibahwa hanyasekelompok kecildapat melakukanprosesupdate. akhirnyakonsistensiOleh karena ituseringmurah untukmengimplementasikan

           

Parapengguna ponselmengaksesdatabasedengan menghubungkan kesalah satureplikadicaratransparan. Dengan kata lain, aplikasiyang berjalan padaportabelpenggunakomputertidak menyadaridi manareplikaitu sebenarnyaberoperasi. Asumsikanpenggunamelakukanoperasi updatebeberapadan kemudianterputuslagi. Kemudian, dia mengaksesdatabase lagi, mungkin setelahpindah kelokasi yangberbeda ataudengan menggunakanberbedamengakses perangkat. Pada saat itu, penggunadapatterhubung kereplikayang berbedadari sebelumnya, seperti ditunjukkan pada Gambar. 6-11. Namun, jikapembaruandilakukansebelumnyabelumdisebarkan, penggunaakan melihatperilakutidak konsisten. DiKhususnya, ia akanmengharapkan untuk melihatsemua perubahanyang dibuatsebelumnya, tetapi sebaliknya,tampak seolah-olahtidak ada sama sekalitelahterjadi

            Contoh inikhas untukmenyimpan data-akhirnya konsisten dandisebabkan olehfakta bahwapenggunaterkadangberoperasi padareplikayang berbeda. Masalahnyabisadiatasidengan memperkenalkanklien-sentris konsistensi. Pada intinya, klien-sentris konsistensimemberikan jaminanuntukklien tunggalmengenaikonsistensiakses untukmenyimpan dataoleh klienitu. Tidak adajaminanyangdiberikansehubunganbersamaanAksesolehklien yang berbeda.

            Klien-centric modelkonsistensiberasaldaribekerja padaBayou[lihat, untukTerrydkk. (1994) danTerryetaI., 1998)]. Bayouadalah sistem databasendikembangkanuntuk komputasi mobile, di manadiasumsikan bahwakonektivitasnjaringantidak dapat diandalkan dantunduk padaberbagaimasalah kinerja. Jaringan nirkabeldanjaringanyang mencakuparea yang luas, seperti Internet, termasuk dalam kategori ini.

            Bayoudasarnyamembedakanempat modelkonsistensiyang berbeda. untuk menjelaskanmodel ini, kami kembalimempertimbangkanmenyimpan datayangsecara fisikdidistribusikan dibeberapamesin. Ketika sebuah prosesmengaksesmenyimpan data, umumnyamenghubungkanke copy(atau terdekat) tersedia secara lokal, meskipun, pada prinsipnya, menyalin setiap akanmelakukanbaik-baik saja. Semuamembaca danmenulisoperasiyangdilakukan padabahwa salinanlokal. Updatepada akhirnyadisebarkankesalinanlainnya. Untukmenyederhanakan masalah, kita asumsikanbahwaDataitem memilikipemilikterkait, yang merupakansatu-satunya prosesyangdiizinkan untukmemodifikasiitem.Dengan cara ini, kita menghindaritulis-menulis konflik.

            Klien-centric modelkonsistensidijelaskandengan menggunakannotasiberikut.nBiarkanXi[t] menunjukkanversixitem datadiLsalinan lokal, pada waktu t. VersiXi(t] merupakan hasil dariserangkaian operasimenulisdiLiyang berlangsung sejakinisialisasi.  Vemenunjukkansetini sebagaiWS(xi [tD Jikaoperasi diWS. (XJtIJ) juga telahdilakukandiLjsalinan lokalpadat2lain waktu, kita menulisWS(xi (td ~[t2]). Jikamemesanoperasiatau waktuyangjelasdari konteks, indekswaktuakandihilangkan.