PERTEMUAN VI (SISTEM TERDISTRIBUSI)

BAB IV
NAMING

4.2.3 Home-Based Approaches

            Alternatif teknik lain yang tidak mengalami permasalahan ketika entitas bergerak dalam jaringan skala besar adalah pendekatan home-based, yaitu sebuah teknik resolving sedemikian sehingga sebuah entitas bergerak memiliki entitas agen dengan sebuah alamat tetap yang menjadi 'alamat rumah' . Ketika entitas tersebut bergerak ke lokasi lain entitas tersebut akan mendapatkan alamat baru yang kemudian didaftarkan entitas agen yang berada di 'alamat rumah'. Ketika sebuah pesan dikirimkan untuk entitas bergerak tersebut tujuan dari pesan adalah 'alamat rumah'. Entitas agen di alamat rumah akan menyampaikan pesan tersebut ke lokasi baru dari entitas bergerak berdasarkan alamat baru yang didaftarkan entitas tersebut. Entitas agen juga akan memberitahu pengirim pesan alamat baru dari entitas bergerak tersebut sehingga komunikasi berikutnya terjadi antara pengirim dengan entitas bergerak di lokasi barunya.

Penggunaan penyiaran dan forwarding pointer membebankan masalah skalabilitas. Penyiaran atau multicasting sulit untuk menerapkan secara efisien dalam skala besar jaringan sedangkan rantai panjang pointer forwarding memperkenalkan masalah kinerja dan rentan terhadap link yang rusak.

Pendekatan yang populer untuk mendukung entitas mobile di jaringan skala besar adalah untuk memperkenalkan lokasi rumah yang melacak lokasi saat suatu entitas. Teknik khusus dapat diterapkan untuk melindungi terhadap kegagalan jaringan atau proses. Dalam prakteknya, lokasi rumah sering dipilih untuk menjadi tempat di mana sebuah entitas diciptakan.

Pendekatan berbasis rumah digunakan sebagai mekanisme jatuh-kembali untuk layanan lokasi didasarkan pada pointer forwarding, seperti yang dibahas di atas. Contoh lain di mana pendekatan rumahan diikuti, adalah mobile IP (perkins, 1997). Setiap mobile host menggunakan alamat IP tetap. Semua komunikasi ke alamat IP yang awalnya diarahkan ke host mobile, AOS agen rumah. Ini agen rumah terletak di jaringan lokal-daerah sesuai dengan alamat jaringan yang terkandung dalam mobile host, AOS alamat IP. Setiap kali mobile host pindah ke jaringan lain, ia meminta alamat sementara yang dapat digunakan untuk komunikasi. Ini perawatan-alamat yang terdaftar di agen rumah.

Ketika agen rumah menerima paket untuk mobile host, itu mendongak tuan rumah, AOS lokasi saat ini. Jika tuan rumah itu adalah pada jaringan lokal saat ini, paket hanya diteruskan. Jika tidak, maka terowongan ke host, AOS lokasi saat ini, yang dibungkus sebagai data dalam paket IP dan dikirim ke alamat perawatan-. Pada saat yang sama, pengirim paket yang diinformasikan dari tuan rumah, AOS lokasi saat ini. Prinsip ini ditunjukkan pada Gbr.4-20. Perhatikan bahwa alamat IP secara efektif digunakan sebagai pengidentifikasi untuk mobile host. Gbr.4-20 juga menggambarkan kelemahan dari rumahan pendekatan dalam jaringan skala besar. Untuk berkomunikasi dengan entitas mobile, klien pertama harus menghubungi rumah, yang mungkin berada di lokasi yang sama sekali berbeda dari entitas itu sendiri. Hasilnya adalah peningkatan latency komunikasi.

Sebuah solusi diterapkan pada telepon selular adalah dengan menggunakan skema dua-berjenjang (Mohan dan Jain, 1994). Saat membuat sambungan ke badan ponsel, klien pertama memeriksa registri lokal untuk melihat apakah entitas mobile avalaible lokal. Jika tidak, entitas, AOS lokasi rumah yang dihubungi untuk menemukan lokasi saat ini. Di bawah ini, kita membahas perpanjangan dengan skema ini yang berkembang di seluruh lapisan hirarkis beberapa.

Gambar 4-20. prinsip mobile IP.

Kekurangan teknik ini adalah penggunaan lokasi rumah yang tetap sehingga rumah ini harus dipastikan selalu tersedia. Jika entitas bergerak hendak pindah untuk jangka waktu lama atau menetap di lokasi lain maka ada baiknya lokasi rumah juga ikut berpindah. Solusi masalah ini adalah dengan mendaftarkan lokasi rumah pada sebuah layanan penerjemahan alamat (naming service) jika lokasi rumah dapat berpindah sehingga lokasi rumah dapat ditemukan oleh entitas yang memerlukannya melalui naming service tersebut.

Sebuah solusi untuk masalah ini adalah untuk mendaftarkan rumah pada layanan penamaan tradisional dan membiarkan klien pertama mencari lokasi rumah. Karena lokasi rumah dapat diasumsikan relatif stabil, lokasi yang dapat secara efektif cache setelah telah mendongak.

4.2.4 Pendekatan hirarkis

            Pada teknik ini jaringan dibagi-bagi menjadi beberapa bagian yang dikenal sebagai domain. Domain-domain ini berada di dalam sebuah domain yang berada di tingkat paling atas yang meliputi seluruh jaringan (top-level domain). Sebuah domain yang berada di bawah/dalam sebuah domain lain dikenal sebagai sub-domain. Domain yang berada pada posisi paling bawah dan tidak memiliki sub-domain lagi dikenal sebagai leaf-domain.

Setiap domain D memiliki simpul direktori, dir(D), yang menyimpan informasi lokasi setiap entitas dalam domain tersebut. Akibatnya terbentuk sebuah pohon direktori dengan simpul paling atas disebut simpul direktori akar (root directroy node) yang mengetahui semua entitas.

Dua-tier rumahan pendekatan entitas lokasi dapat digeneralisasi untuk beberapa lapisan. Pada bagian ini, pertama-tama kita membahas pendekatan umum untuk skema lokasi hirarkis, setelah beberapa optimasi disajikan. Pendekatan kami sajikan didasarkan pada layanan lokasi Globe yang mewakili banyak layanan lokasi hirarkis diusulkan untuk apa yang disebut Sistem Komunikasi Pribadi (Pitoura dan Samaras, 2001; Wang, 1993).

Mekanisme umum

Dalam skema hirarkis, jaringan dibagi menjadi koleksi domain, sangat mirip dengan organisasi hirarkis DNS. Ada top-level domain tunggal yang meliputi seluruh jaringan. Setiap domain dapat dibagi menjadi beberapa, subdomain kecil. Sebuah domain tingkat terendah, disebut domain daun, biasanya berkaitan dengan jaringan area lokal dalam jaringan komputer atau sebuah sel dalam jaringan telepon selular.

Juga analog ke DNS dan sistem penamaan hirarkis, masing-masing D domain memiliki direktori terkait simpul dir (D) yang melacak entitas dalam domain tersebut. Hal ini menyebabkan pohon node direktori. Simpul direktori dari domain top-level, yang disebut root (direktori) node, tahu tentang semua entitas. Ini organisasi umum dari domain inot jaringan dan node direktori diilustrasikan dalam Gbr.4-21.

Gambar 4-21. Hirarkis organisasi layanan lokasi ke dalam domain, masing-masing memiliki simpul direktori terkait

Untuk melacak lokasi sebuah entitas dalam sebuah domain setiap entitas dalam domain terdaftar di dalam simpul direktori domain tersebut. Catatan lokasi (location record) sebuah entitas E pada simpul direktori N dari domain D berisi alamat entitas tersebut di dalam domain D. Sebaliknya, simpul direktori N' dari domain D' yang menjadi domain induk dari domain D hanya akan menyimpan catatan lokasi E berupa penunjuk (pointer) ke simpul direktori N dan demikian juga induk dari N' hanya menyimpan penunjuk ke simpul direktori N'. Pada akhirnya simpul direktori root berisi penunjuk ke simpul direktori dari semua sub-domain di bawahnya.

Sebuah entitas dapat memiliki beberapa alamat sebagai contoh: jika entitas tersebut direplikasi. Jika sebuah entitas memiliki alamat di leaf-domain D1 dan D2 maka simpul direktori dari domain induk dari domain D1 dan D2 menyimpan dua penunjuk untuk setiap sub-domain.

Gambar 4-22. Contoh dari menyimpan informasi dari sebuah entitas yang memiliki dua alamat dalam domain daun yang berbeda.

Mari kita mempertimbangkan bagaimana suatu operasi pencarian berlangsung sedemikian layanan lokasi hirarkis. Seperti yang ditunjukkan pada Gambar. 4-23, klien yang ingin mencari suatu entitas E, isu permintaan lookup ke node direktori dari domain D daun di mana klien berada. Jika node direktori tidak menyimpan catatan lokasi untuk entitas, maka entitas saat ini tidak terletak di D. Akibatnya, ke depan permintaan untuk node induknya. Perhatikan bahwa node orangtua merupakan domain lebih besar dari anaknya. Jika orangtua juga tidak memiliki catatan lokasi untuk E, permintaan pencarian diteruskan ke tingkat berikutnya yang lebih tinggi, dan sebagainya.

Jika sebuah entitas E1 ingin mengetahui alamat entitas E2 maka pertama kali ia akan mencari catatan lokasi entitas tujuan tersebut di simpul direktori domain tempat ia berada. Jika pada simpul direktori ini tidak terdapat catatan lokasi entitas E2 berarti entitas E2 tidak berada pada domain yang sama dengan entitas E1. Permintaan entitas E1 akan diteruskan ke simpul direktori dari simpul direktori dari induk domain tempatnya berada dan seterusnya ke simpul direktori induk dari induk domainnya hingga menemukan catatan lokasi untuk E2. Pada kasus terburuk pencarian akan berlanjut hingga simpul direktori domain akar. Jika pada salah satu domain ditemukan catatan lokasi untuk E2 maka permintaan pencarian akan diteruskan ke sub domain yang ditunjuk oleh catatan lokasi untuk E2 tersebut seterusnya hingga ditemukan alamat dari E2.

Gambar 4-23. mencari lokasi di layanan lokasi hirarki terorganisir.

Setelah permintaan mencapai M direktori simpul yang menyimpan catatan lokasi untuk E entitas, kita tahu bahwa E adalah suatu tempat di dom domain (M) diwakili oleh simpul M. di Gbr.4-23, M ditampilkan untuk menyimpan lokasi record yang mengandung pointer ke salah satu subdomainnya. Permintaan lookup kemudian diteruskan ke node direktori itu subdomain, yang pada gilirannya ke depan itu lebih bawah pohon, hingga permintaan akhirnya mencapai simpul daun. Catatan lokasi disimpan dalam simpul daun akan berisi alamat E dalam domain daun. Alamat ini kemudian dapat dikembalikan ke klien yang awalnya meminta lookup berlangsung.

Sebuah pengamatan penting sehubungan dengan layanan lokasi hirarkis, adalah bahwa operasi pencarian mengeksploitasi lokalitas. Pada prinsipnya, entitas yang dicari dalam cincin bertahap meningkatkan berpusat di sekitar klien meminta. Daerah pencarian diperluas setiap kali permintaan pencarian diteruskan ke node yang lebih tinggi-level direktori berikutnya. Dalam kasus terburuk, pencarian continoues hingga permintaan mencapai simpul akar. Karena akar memiliki catatan lokasi untuk setiap entitas, permintaan yang kemudian dapat hanya diteruskan sepanjang jalan ke bawah dari pointer ke salah satu node daun.

Operasi update mengeksploitasi lokalitas dalam cara yang sama, seperti yang ditunjukkan pada Gambar. 4-24. Pertimbangkan E entitas yang telah menciptakan replika dalam daun domain D yang dibutuhkan untuk memasukkan alamatnya. Penyisipan ini dimulai pada daun simpul dir (D) dari D, yang segera meneruskan permintaan insert ke induknya. Orang tua akan meneruskan permintaan insert juga, sampai mencapai M direktori simpul yang sudah menyimpan catatan lokasi untuk E.        

Node M kemudian akan menyimpan pointer dalam catatan lokasi untuk E, mengacu pada node anak dari mana permintaan insert itu diteruskan. Pada saat itu, simpul anak menciptakan rekor lokasi untuk E, yang mengandung pointer ke simpul yang lebih rendah-tingkat berikutnya dari mana permintaan datang. Ini terus menerus proses sampai kita mencapai simpul daun dari mana insert dimulai. Simpul daun, akhirnya, menciptakan rekor dengan alamat entitas dalam domain daun terkait.

Gambar 4-24. (a) Permintaan insert diteruskan ke node pertama yang tahu tentang E entitas
(b) Sebuah rantai forwarding pointer ke node daun dibuat.

Memasukkan alamat seperti yang baru saja dijelaskan, mengarah ke menginstal rantai pointer secara top-down dimulai dari node direktori tingkat terendah yang memiliki catatan lokasi untuk entitas E. Alternatif adalah untuk membuat data lokasi sebelum melewati permintaan insert ke simpul orangtua. Dengan kata lain, rantai pointer dibangun dari bawah ke atas. Keuntungan yang kedua adalah bahwa alamat menjadi avalaible untuk pencarian sesegera mungkin. Akibatnya, jika node induk untuk sementara tidak terjangkau, alamat masih bisa mendongak dalam domain diwakili oleh node saat ini.

Sebuah operasi menghapus analog dengan operasi insert. Ketika sebuah alamat untuk E entitas dalam daun domain D perlu dihapus, direktori simpul dir (D) diminta untuk menghapus alamat yang dari rekor lokasi untuk E. Jika yang merekam lokasi menjadi kosong, yang tidak berisi alamat lain untuk E di D, catatan dapat dihapus. Dalam hal ini, node induk dir (D) ingin menghapus pointer untuk dir (D). Jika catatan lokasi untuk E pada orangtua kini juga menjadi kosong, catatan yang harus dihapus juga dan simpul yang lebih tinggi-level direktori selanjutnya harus diberitahu. Sekali lagi, ini terus menerus proses sampai pointer dihapus dari catatan lokasi yang tetap tidak kosong sesudahnya atau sampai akar tercapai.

4.3.1 Obyek dengan cara kerangka terkait yang dilakukan oleh Server.

Dalam apa yang berikut, kita asumsikan bahwa sebuah objek hanya dapat diakses jika ada remote untuk itu. Sebuah objek yang ada referensi terpencil ada harus dihapus sistem. Di sisi lain, memiliki referensi remote ke obyek tidak berarti bahwa objek akan pernah diakses. Untuk berbagai alasan, adalah mungkin bahwa ada dua benda, masing-masing menyimpan direferensikan ke yang lain, tetapi sebaliknya tidak direferensikan sama sekali. Situasi ini dengan mudah digeneralisasikan ke siklus obyek hanya merujuk satu sama lain. Objek tersebut juga harus dideteksi dan dihapus.

Secara umum, model ini dapat diwakili oleh grafik di mana setiap node mewakili obyek. Keunggulan dari M node ke node N mewakili fakta bahwa objek M berisi referensi ke obyek N. ada bagian dibedakan dari benda-benda yang disebut set root, yang tidak perlu dirujuk sendiri. Sebuah objek di set akar biasanya merupakan layanan sistem yang luas, pengguna dan sebagainya. Gambar. 4.28 menunjukkan contoh seperti grafik direferensikan. Semua node putih yang mewakili benda-benda yang tidak langsung atau tidak langsung direferensikan oleh benda Di set root. Benda tersebut harus dihapus.

Gambar 4-28 An example of a graph representing objects containing references to each other

Dalam sistem prosesor tunggal, mendeteksi dan menghapus objek unreferenced relatif sederhana dibandingkan dengan situasi dalam sistem terdistribusi (untuk ikhtisar dari pengumpulan sampah dalam sistem uniprocessor, lihat Wilsons, 1994). Karena objek didistribusikan di beberapa mesin, pengumpulan sampah didistribusikan memerlukan jaringan komunikasi. Ternyata, komunikasi ini secara signifikan menentukan efisiensi dan skalabilitas dari solusi. Selain itu, komunikasi sebagai mesin juga suatu proses yang tunduk pada kegagalan, yang membuat masalah lebih buruk.

 Bagian ini, kami mempertimbangkan sejumlah baik-tahu solusi untuk pengumpulan sampah didistribusikan. Dalam kebanyakan kasus, solusi ini hanya sebagian memecahkan masalah. Pendekatan kami berikut pada mengambil dalam (plainfosse dan Shapiro, 1995), yang memberikan gambaran lebih lanjut dari pengumpulan sampah terdistribusi. Informasi lebih lanjut juga dapat ditemukan dalam (Abdullahi dan rinwood, 1998).

4.3.2 Referensi Menghitung

Sebuah metode yang populer di sistem prosesor tunggal untuk memeriksa apakah sebuah objek dapat dihapus adalah hanya menghitung referensi ke obyek itu. Setiap kali referensi ke sebuah objek dibuat, sebuah referensi counter untuk objek tersebut. Sebuah meja referensi untuk objek yang bertambah. Selanjutnya, pada saat referensi dihapus, counter referensi decremented. Segera setelah counter mencapai nol, objek dapat dihapus.

Sederhana Referensi Menghitung Referensi sederhana menghitung dalam sistem terdistribusi menyebabkan sejumlah masalah, yang sebagian disebabkan oleh kenyataan bahwa komunikasi tidak dapat diandalkan. Tanpa kehilangan umum, kita dapat mengasumsikan bahwa objek menyimpan kontra referensi sendiri dalam kerangka terkait sebagai dipelihara oleh server objek yang bertanggung jawab untuk objek. Situasi ini ditunjukkan pada gambar. 4-29.

Ketika P proses menciptakan referensi ke obyek O terpencil, menginstal p proxy untuk O dalam ruang alamat nya, seperti yang juga ditampilkan dalam Gbr.4-29. Untuk increment counter referensi, proxy mengirim pesan m ke kerangka obyek, dan mengharapkan untuk kembali pengakuan. Namun, jika pengakuan hilang, proxy akan mengirim ulang m. Jika tidak ada langkah khusus yang diambil untuk mendeteksi pesan duplikat, kerangka palsu mungkin kenaikan referensi yang kontra lagi.

Dalam prakteknya, mendeteksi pesan duplikat relatif mudah. Demikian juga, s masalah juga bisa disebabkan ketika referensi remote untuk dihapus. Dalam hal ini, proxy akan mengirim pesan untuk penurunan konter referensi. Jika pengakuan hilang lagi, maka transmisi pesan yang dapat menyebabkan penurunan yang lain, yang salah meja. Akibatnya, dalam menghitung referensi didistribusikan, adalah penting untuk mendeteksi pesan duplikat dan kemudian membuang mereka saat mereka masuk.

Masalah lain yang perlu diselesaikan terjadi ketika menyalin referensi remote ke proses lain. Jika P1 proses melewati referensi untuk proses P2, objek, atau lebih tepatnya, tulangnya, akan menyadari bahwa sebuah referensi baru telah dibuat. Akibatnya, jika proses P1 memutuskan untuk menghapus referensi sendiri, counter referensi mungkin drop ke nol dan O dapat dihapus sebelum P2 pernah kontak itu. Masalah ini diilustrasikan pada Gambar. 4-30 (a).

Referensi Menghitung Sebuah solusi adalah membiarkan P1 menginformasikan kerangka benda itu akan melewati sebuah referensi untuk memproses P2. Selain itu, proses ini tidak pernah diperbolehkan untuk menghapus referensi sebelum kerangka memiliki pengakuan bahwa ia tahu tentang keberadaan referensi yang. Solusi ini ditunjukkan pada Gambar. 4-30 (b). pengakuan mengirim melalui O ke P2 mengkonfirmasikan ke P2 bahwa O telah terdaftar referensi, nantinya akan memungkinkan P2 untuk menghapus referensi untuk O. Selama P2 tidak yakin bahwa O tahu tentang referensi, P2 tidak diperbolehkan untuk meminta O untuk lakukan dengan decrement counter referensi.

Perhatikan bahwa, selain komunikasi yang handal, melewati referensi sekarang membutuhkan tiga pesan. Jelas, ini dapat dengan mudah menyebabkan masalah kinerja dalam skala besar sistem terdistribusi.

Lanjutan Referensi Menghitung

Sederhana sistem terdistribusi referensi menghitung memaksakan kondisi lomba antara incrementing dan decrementing counter referensi sebagai hanya dijelaskan. Kondisi balapan tersebut dapat dihindari jika operasi pengurangan hanya dapat terjadi. Solusi ini diadopsi dalam referensi menghitung tertimbang, di mana setiap objek sebagai berat, tetap total. Ketika objek dibuat, berat total toko dalam kerangka terkait (yang kita sebut sebagai s), bersama dengan berat badan parsial, yang diinisialisasi dengan berat total, seperti yang ditunjukkan pada Gambar. 4-31 (a).

Ketika referensi remote baru (p, s) dibuat, setengah dari berat parsial disimpan dalam kerangka objek ditugaskan untuk p proxy baru, seperti ditunjukkan pada Gambar. 4-31 (b). Setengah yang tersisa adalah kerangka s. Ketika referensi remote diduplikasi,

Misalnya, ketika melewati itu dari P1 proses P2, setengah dari berat sebagian proxy di P1 ditugaskan ke proxy disalin untuk P2, sementara separuh lainnya tetap di proxy di P1, seperti ditunjukkan pada Gambar. 4-31 (c).

Ketika referensi hancur, pesan penurunan dikirim ke kerangka obyek, yang kemudian mengurangi berat parsial referensi dihapus dari berat total. Begitu berat total mencapai nol, tidak ada referensi lebih jauh ada, sehingga objek bisa dihapus secara aman. Perhatikan bahwa, juga dalam kasus ini, pesan yang dianggap tidak akan hilang atau memberikan lebih dari sekali.

Masalah utama dengan referensi menghitung tertimbang adalah bahwa hanya sejumlah referensi dapat dibuat. Begitu berat sebagian kerangka obyek, serta orang-orang dari referensi terpencil, turun menjadi nol, tidak ada referensi lebih dapat diciptakan atau digandakan. Solusi untuk masalah ini adalah dengan menggunakan berat o, proxy sendiri telah mencapai 1, seperti ditunjukkan pada Gambar. 4-32. Dalam hal ini, P1 menciptakan 'kerangka dalam ruang alamatnya dengan berat total yang tepat, dan berat parsial ditetapkan sama dengan berat total. Ini sangat sejalan dengan kerangka s dibuat dalam ruang alamat di mana objek berada. Proxy kemudian dikirim ke P2, dengan setengah dari berat parsial 'kerangka s ditugaskan untuk itu. Sisi lain berat disimpan di 's untuk distribusi ke proxy lain.

            Perhatikan bahwa jika berat total 's kerangka diatur 1, pendekatan ini adalah sama dengan menciptakan pointer forwarding dari P2 proses P1. Jika pada gilirannya, P2 ingin menyampaikan referensi, ia akan harus membuat yang lain pointer forwarding. Masalah yang paling serius dengan menggunakan pointer forwarding adalah bahwa rantai panjang serius menurunkan kinerja. Juga, rantai lebih rentan terhadap kegagalan.

Sebuah alternatif untuk menggunakan tipuan disediakan oleh penghitungan Generation referensi. Sekali lagi, menganggap bahwa setiap referensi remote dibangun sebagai pasangan (proxy, kerangka), di mana (saja) kerangka s terletak di ruang alamat yang sama sebagai obyek. Setiap proxy menyimpan counter untuk jumlah kali ini telah disalin, n samping sejumlah generasi. Ketika sebuah referensi baru (p, s) dibuat, jumlah generasi p proxy yang sesuai diatur ke nol. Karena tidak ada salinan tersebut belum dibuat dari p, counter salinannya juga diatur ke nol.

Menyalin referensi remote (p, s) untuk proses lain dilakukan dengan cara biasa dengan mengirimkan copy p 'p. Dalam hal ini, konter salinan P bertambah, sementara itu dari 'p diatur ke nol. Namun, karena p 'disalin dari P, dikatakan milik generasi berikutnya, yang untuk alasan jumlah generasi p' diatur satu lebih tinggi dari dari p, seperti yang ditunjukkan pada Gambar. 4-33.

            Kerangka mempertahankan G meja, di mana G [i] menunjukkan jumlah salinan yang beredar untuk generasi i. jika p proxy dihapus, hapus pesan dikirim ke kerangka yang berisi nomor generasi proxy, katakanlah, k, dan jumlah salinan yang telah dibuat dari p, katakanlah n. kerangka menyesuaikan G dengan terlebih dahulu decrementing G [k] oleh satu, menunjukkan bahwa referensi milik generasi k-th telah dihapus. Kedua, kenaikan itu G [k +1] dengan n, untuk mendaftarkan bahwa referensi dihapus telah menciptakan saudara n, atau, dengan kata lain, itu, itu telah disalin ke n generasi referensi. (Perhatikan bahwa kerangka pertama mungkin perlu membuat entri G [k +1] sebagai generasi k +1 adalah belum diketahui untuk itu.) Segera setelah setiap entri G [i] adalah nol, diketahui bahwa objek tidak lagi direferensikan sehingga dapat dihapus.

Generasi referensi menghitung masih membutuhkan komunikasi yang handal, tetapi dapat menangani duplikasi referensi tanpa perlu menghubungi kerangka ketika membuat salinan.

4.3.3 Referensi Daftar

Sebuah pendekatan yang berbeda untuk mengelola referensi, adalah untuk membiarkan kerangka melacak proxy yang memiliki referensi untuk itu. Dengan kata lain, alih-alih menghitung referensi, kerangka memelihara daftar eksplisit semua proxy yang menunjukkan hal itu. Seperti daftar referensi tidak berpengaruh ketika proxy yang sudah terdaftar. Demikian juga, menghapus proxy dari daftar di mana hal itu tidak terjadi, juga tidak memiliki efek. Menambahkan atau menghapus proxy kembali operasi sehingga idempoten.
            Operasi idempoten dicirikan oleh kenyataan bahwa mereka dapat diulang tanpa mempengaruhi hasil akhir. Secara khusus, saat membuat referensi baru ke obyek, proses pembuatan berulang kali dapat mengirim pesan ke kerangka objek, meminta untuk menambahkan proxy ke dalam daftar referensi. Ini seperti berhenti mengirim pesan secepat pengiriman telah diakui. Demikian pula, menghapus referensi dapat dilaporkan oleh (mungkin berulang-ulang) mengirimkan pesan meminta kerangka untuk menghapus proxy dari daftar. Kenaikan dan penurunan operasi jelas tidak idempotent.

Akibatnya, daftar referensi tidak memerlukan komunikasi dapat diandalkan, juga tidak perlu bahwa pesan duplikat dapat dideteksi dan dibuang. (Namun, perlu bahwa penyisipan atau penghapusan referensi diakui.) Ini merupakan keuntungan penting selama referensi menghitung.

Daftar referensi yang digunakan di Jawa RMI, berdasarkan metode yang diuraikan dalam (Birrell et al .. 1993). Dalam metode ini, ketika P proses menciptakan referensi remote ke obyek, ia mengirimkan identifikasi terhadap kerangka obyek, yang menambahkan P ke daftar referensi. Ketika pengakuan dikembalikan, proses menciptakan proxy untuk objek dalam ruang alamat sendiri.

Melewati referensi ke proses lain, yaitu, mengirimkan salinan proxy, ditangani sama. Setiap kali P1 proses mengirimkan salinan proxy untuk objek O untuk memproses P2, P2 permintaan pertama kerangka objek untuk menambahkan P2 ke daftar referensi. Ketika itu telah dilakukan, P2 proses menginstal proxy dalam ruang alamat nya.

            Masalah dapat terjadi ketika P1 proses menghilangkan proksi sendiri sebelum P2 telah meminta untuk dimasukkan dalam daftar referensi objek. Dalam hal ini, jika menghapus meminta P1 kirim ke kerangka objek ditangani sebelum permintaan insert dari P2, daftar referensi dapat menjadi kosong sehingga kerangka palsu menyimpulkan dapat membiarkan objek dihapus. Ini kondisi lomba benar-benar analog dengan satu dengan referensi menghitung, seperti ditunjukkan pada Gambar. 4-30 (a), dan dapat diselesaikan dengan cara yang sama.

            Keuntungan penting lainnya dari daftar referensi, adalah bahwa lebih mudah untuk menjaga daftar referensi yang konsisten dalam menghadapi kegagalan proses. Kerangka objek secara teratur memeriksa apakah setiap proses yang terdaftar masih berdiri dan berjalan dengan mengirimkan pesan ping, meminta apakah masih hidup dan memegang referensi ke objek. Proses ini diharapkan untuk segera menanggapi pesan ini. Jika tidak ada respon yang diterima, bahkan mungkin setelah beberapa upaya telah dilakukan, kerangka menghilangkan proses dari daftar.

            Kelemahan utama dari daftar referensi, adalah bahwa hal itu mungkin skala buruk jika kerangka itu perlu untuk melacak banyak referensi. Salah satu solusi untuk menjaga daftar bawah, adalah untuk membiarkan janji kerangka itu akan mendaftarkan referensi hanya untuk waktu yang terbatas. Jika proxy belum memperpanjang pendaftaran tersebut pada kerangka sebelum waktu itu berakhir, referensi hanya dijatuhkan dari daftar. Pendekatan ini juga disebut sebagai penanganan keluar sewa. Kami kembali ke sewa di Chap.6.

4.3.4 Mengidentifikasi Unreachable Entitas

            Seperti juga ditunjukkan pada Gambar. 4-28, koleksi entitas dalam sistem terdistribusi dapat terdiri dari entitas yang menyimpan referensi satu sama lain, namun tidak satupun dari entitas dapat dicapai dari suatu entitas di set akar, dan dengan demikian, mereka juga harus dihapus. Sayangnya, teknik pengumpulan sampah dijelaskan di atas gagal untuk menemukan entitas.
            Apa yang dibutuhkan adalah sebuah metode dimana semua entitas dalam sistem terdistribusi yang ditelusuri. Secara umum, hal ini dilakukan dengan memeriksa mana entitas dapat dicapai dari set akar dan kemudian menghapus semua orang lain. Metode tersebut umumnya disebut menelusuri berbasis pengumpulan sampah. Berbeda dengan referensi didistribusikan dibahas sejauh ini, menelusuri berbasis pengumpulan sampah memiliki masalah skalabilitas yang melekat, karena kebutuhan untuk melacak semua entitas dalam sistem terdistribusi.

Naif Tracing dalam Sistem Terdistribusi

            Untuk memahami didistribusikan menelusuri berbasis pengumpulan sampah, akan sangat membantu untuk mempertimbangkan bagaimana menelusuri dalam kerja sistem uniprocessor. Pendekatan yang paling sederhana untuk uniprocessor tracing, diikuti oleh mark-dan-menyapu kolektor. Kolektor tersebut membedakan dua fase.

            Selama fase mark, entitas yang ditelusuri oleh rantai berikut referensi yang berasal dari entitas di set root. Setiap entitas yang dapat dicapai dengan cara ini ditandai, misalnya dengan merekam entitas dalam tabel terpisah. Fase menyapu terdiri dari mendalam memeriksa memori untuk menemukan entitas yang belum ditandai. Entitas tersebut dianggap sampah yang akan dihapus.

            Cara lain untuk melihat tanda-dan-menyapu kolektor adalah untuk menerapkan warna tiga-menandai untuk entitas. Awalnya, setiap entitas yang perlu diperiksa adalah berwarna white.by akhir fase mark, semua entitas yang telah berwarna hitam yang dicapai dari akar, sementara mereka yang tidak terjangkau masih putih. Warna abu-abu digunakan untuk melacak kemajuan yang sedang dibuat dalam fase mark. Entitas ditandai abu-abu ketika ditemukan dapat dicapai tetapi referensi yang disimpan oleh entitas yang perlu belum diperiksa. Ketika semua referensi yang telah ditandai abu-abu, entitas adalah berwarna hitam.

            Sebuah versi didistribusikan mark-menyapu dan-yang diimplementasikan dalam sistem Emerals, dijelaskan dalam (Jul et al, 1998.). Di Emerald, seorang kolektor sampah lokal dimulai pada rocess masing-masing, dengan semua kolektor berjalan secara paralel. Kolektor warna proxy, kerangka, dan benda-benda yang sebenarnya. Awalnya, semuanya ditandai putih. Ketika sebuah benda yang berada di ruang alamat dari proses P dicapai dari akar yang juga di P, objek tersebut ditandai abu-abu. Ketika menandai suatu objek abu-abu, semua proxy yang terkandung dalam objek tha ditandai abu-abu juga. Menandai sarana abu-abu proxy yang catatan kolektor lokal sampah yang remote object direferensikan masih perlu diperiksa oleh pengumpul sampah terkait lokalnya.

            Ketika proxy ditandai abu-abu, pesan dikirim ke kerangka proxy terkait untuk menandainya abu diri juga. Obyek terkait dengan kerangka ditandai abu-abu secepat kerangka menjadi abu-abu. Dengan rekursi, ini berarti bahwa semua proxy dalam objek yang ditandai abu-abu juga. Pada saat itu, kerangka dan objek yang terkait ditandai hitam, dan pesan yang dikirim kembali ke semua proxy yang terkait. Perhatikan bahwa walaupun dalam pendekatan ini, kerangka yang tahu proxy yang terhubung, hal ini tidak berarti bahwa proxy dianggap dicapai dari kerangka tersebut. Logikanya, sepasang (proxy, kerangka) adalah referensi searah ketat dari proxy untuk kerangka.

            Ketika proxy menerima pesan bahwa kerangka terkait adalah nowblack, proxy ditandai hitam juga. Dengan kata lain, pengumpul sampah setempat sekarang tahu bahwa objek remote direferensikan dengan cara proxy telah dicatat sebagai terjangkau.

            Ketika semua kolektor lokal telah selesai fase jejak mereka, mereka dapat secara terpisah mengumpulkan semua benda putih seperti sampah. Sebuah fase mark berakhir ketika semua benda, kerangka, dan proxy sudah ditandai baik putih atau hitam. Menghapus objek putih juga berarti menghapus kerangka terkait serta semua proxy yang terkandung dalam objek tersebut.

            The drawbacck utama dari algoritma mark-dan-menyapu adalah bahwa ia memerlukan grafik reachability tetap sama selama kedua fase kedua. Dengan kata lain, pelaksanaan program yang proses awalnya diciptakan harus dihentikan sementara dan eksekusi diaktifkan untuk mengumpulkan sampah. Dalam didistribusikan mark-dan-menyapu berarti, ini bahwa semua proses dalam sistem yang pertama perlu disinkronkan, maka masing-masing dari mereka beralih ke mengumpulkan sampah, setelah itu mereka semua bisa melanjutkan pekerjaan asli mereka.

            Skenario ini, juga disebut "stop-the-dunia" sinkronisasi, sering tidak dapat diterima untuk kolektor sampah didistribusikan. Perbaikan dapat dilakukan dengan pengumpul sampah tambahan, yang memungkinkan eksekusi program yang akan disisipkan dengan pengumpulan sampah. Sayangnya, kolektor tersebut tidak skala baik dalam sistem terdistribusi. Karena mereka berjalan bersamaan dengan program yang memodifikasi grafik reachability, benda sering selalu ditandai abu-abu, yang mengarah ke penyebaran tanda abu-abu untuk proses remote. Hasilnya adalah pesan lalu lintas tinggi, kinerja sistem mungkin merendahkan keseluruhan.

Menelusuri di Grup

            Untuk menjelaskan masalah scability melekat banyak tracing berbasis pengumpul sampah, Lang et al. Merancang metode yang proses (yang containthe objek) dalam sebuah sistem terdistribusi besar yang hirarki terorganisir dalam kelompok-kelompok (Lang et al., 1992). Pengumpulan sampah terjadi di dalam kelompok melalui kombinasi mark-menyapu dan-dan referensi menghitung. Mari kita berkonsentrasi pada algoritma dasar untuk mengumpulkan sampah dalam kelompok proses. Grup A hanyalah sebuah kumpulan proses. Satu-satunya alasan mengapa kelompok yang digunakan adalah untuk scability. Ide dasarnya adalah pertama untuk mengumpulkan sampah semua dalam kelompok, termasuk siklus referensi yang terletak seluruhnya di dalam grup. Langkah berikutnya adalah untuk mempertimbangkan kelompok yang lebih besar yang meliputi sejumlah sub kelompok, tetapi yang masing-masing hanya dibersihkan oleh garbage collector.

            Untuk mengakomodasi penelusuran dalam kelompok, diasumsikan bahwa referensi remote lagi diimplementasikan sebagai ("proxy, kerangka) pasang. Untuk setiap objek, hanya ada satu kerangka di ruang alamat di mana objek berada, namun beberapa proxy untuk objek yang dapat berkomunikasi dengan kerangka itu. Kerangka mempertahankan counter referensi seperti yang dijelaskan dalam Sec.4.3.2, yang menghitung jumlah proxy terkait. Sebuah proses dapat memiliki paling banyak satu proxy untuk setiap objek terdistribusi.

            Setelah sekelompok proses telah dibentuk, algoritma dasar untuk mengumpulkan sampah dalam suatu kelompok terdiri dari lima langkah berikut, yang dibahas secara rinci di bawah ini:

1. Awal menandai, di mana kerangka hanya ditandai.

2. Intraprocess propagasi tanda dari kerangka ke proxy.

3. Interprocess propagasi tanda dari proxy untuk kerangka.

4. Stabilisasi dengan pengulangan dari dua langkah sebelumnya.

5. Sampah reklamasi.

Sebelum kita mulai menjelaskan masing-masing langkah dalam beberapa detail, adalah penting untuk memahami apa yang menandai entitas singkatan. Algoritma pada dasarnya berhubungan dengan menandai proxy saja dan kerangka. Penting untuk dicatat bahwa baik proxy atau kerangka yang bisa milik set akar. Sebuah kerangka dapat ditandai tidak lembut atau keras sedangkan proxy dapat ditandai eithe, lembut, atau keras. Ketika kerangka ditandai keras, ini berarti bahwa baik dicapai dari proxy dalam proses di luar kelompok, atau dicapai dari objek akar dalam kelompok. Sebuah kerangka yang ditandai lembut, dianggap dapat dicapai hanya dari proxy dalam kelompok. Penandaan kerangka diperbolehkan untuk mengubah hanya dari lembut ke keras.

            Sebuah proxy yang ditandai keras, dapat dicapai dari suatu objek di set root. Ketika ditandai lembut, proxy dapat dicapai dari suatu kerangka yang telah ditandai lembut serta. Proxy tersebut berpotensi berbaring di siklus yang tidak dapat diraih dari suatu objek di set root. Sebuah proxy yang ditandai tidak ada yang tidak dapat dijangkau dari kerangka, atau obyek di set root. Proxy Hanya yang sudah ditandai tidak dapat diubah keras. Seperti yang akan terlihat, begitu proxy telah ditandai lembut, tetap seperti itu.

            Langkah pertama terdiri dari penandaan hanya kerangka. Sebuah kerangka ditandai baik lembut atau keras, tergantung pada apakah ot dapat dicapai dari proxy luar kelompok. Reachability ini dapat dengan mudah diperiksa dengan memeriksa meja referensi kerangka itu. Nilai counter ini menunjukkan berapa banyak proxy dalam proses-proses lain menyebutnya. Beberapa dari proses ini dalam kelompok, sementara yang lain berada di luar kelompok. Jika ada proxy dalam proses di luar kelompok, kerangka harus ditandai keras. Dengan hanya menghitung berapa banyak proxy yang berhubungan dengan kebohongan kerangka dalam kelompok dan mengurangkan angka tersebut dari meja referensi, dapat diputuskan jika ada proxy juga terkait di luar kelompok. Hal ini mengarah pada algoritma berikut:

1. Untuk setiap proksi dalam kelompok, lakukan dengan decrement counter referensi kerangka terkait, hanya jika kerangka yang juga dalam kelompok.

2. Kerangka dalam kelompok yang kontra referensi kini turun menjadi nol ditandai lembut. Jika tidak, itu dapat dicapai dari proxy luar kelompok, dan ditandai keras.

Ini langkah pertama diilustrasikan pada Gambar. 4-34 (a), di mana semua kecuali satu kerangka telah ditandai lembut. Kerangka-satunya yang ditandai keras, dipandang dicapai dari proxy luar kelompok.

Langkah kedua terdiri dari membiarkan setiap proses menjalankan garbage collector lokal sendiri. Bagaimana kolektor yang bekerja independen dari pengumpulan sampah global. Satu-satunya persyaratan adalah bahwa seorang kolektor sampah lokal menyebarkan tanda dari kerangka ke proxy dalam proses sedang berjalan. Lebih khusus, anggaplah bahwa dalam proses tunggal proxy dicapai dari kerangka. (Perhatikan bahwa proxy dan kerangka milik objek yang berbeda). Hasil propagasi lokal tanda adalah bahwa proxy akan ditandai setidaknya sekeras kerangka. Apalagi jika proxy dapat dicapai dari suatu objek di set akar, maka akan ditandai keras.

Propagasi lokal dalam proses P dapat dilakukan sebagai berikut. Awalnya, semua proxy di P ditandai tidak ada. Para kolektor lokal mulai menelusuri mulai penelusuran dari set yang terdiri dari kerangka yang sebelumnya telah ditandai keras, serta dari benda-benda di set root. Tanda Hard disebarkan ke semua objek (yaitu, objek lokal dan proxy) yang dicapai dari set ini. Sebuah jejak kedua dilakukan dari kerangka yang telah ditandai lembut. Jika proxy yang kini mencapai yang ditandai tidak ada, tandanya berubah menjadi lembut. Jika proxy ditandai keras, tetap ditandai seperti. Akibatnya, setelah propagasi lokal, masing-masing proxy di proses akan ditandai baik tidak ada, lembut, atau keras. Gambar. 4-34 (a).

            Langkah ketiga terdiri dari menyebarkan tanda dari proxy untuk kerangka mereka terkait. Dengan kata lain, tanda yang disebarkan antara proses yang berbeda. Secara khusus, jika proxy telah ditandai keras, pesan harus dikirim ke kerangka yang terkait untuk menandai sulit juga, jika tidak sudah ditandai seperti. Sebuah pesan akan dikirim hanya jika kerangka terletak di dalam kelompok. Tanda lembut tidak harus disebarkan: fase menandai awal sudah ditetapkan bahwa setiap kerangka dalam kelompok ditandai baik lembut atau keras.

            Hasil Langkah keempat dari propagasi global marka keras pada langkah sebelumnya. Sebuah kerangka dalam, katakanlah, P proses sekarang mungkin memiliki tandanya berubah dari lembut ke keras. Perubahan ini berasal dari fakta bahwa kerangka ternyata dicapai dari obyek yang terkandung dalam set akar dari proses remote. Akibatnya, ini tanda keras pertama perlu disebarkan ke proxy lokal di P, dan kemudian, secara global disebarkan kepada proses tetangga. Dengan kata lain, langkah 2 dan 3 harus diulang asalkan tanda dapat baik secara lokal atau global disebarkan. Segera setelah stabilisasi telah tercapai, yaitu, tidak ada perubahan yang lebih berkenaan dengan menandai terjadi proses dalam kelompok, hasil algoritma dengan langkah berikutnya. Dalam contoh kita, efek mengulangi langkah 2 dan 3 mengarah ke final menandai seperti ditunjukkan pada Gambar. 4-34 (c).

            Langkah kelima dan terakhir terdiri dari menghilangkan benda terjangkau, termasuk proxy terjangkau, serta mereka proxy dan tengkorak yang sudah ditandai lembut. Penting untuk dicatat bahwa yang terakhir tidak dapat diraih dari luar kelompok, mereka juga tidak dapat dicapai dari objek dalam satu set root. Dengan kata lain, soft-ditandai proxy dan kerangka hanya mengacu pada satu sama lain, dan dengan demikian harus dihapus.

            Sampah reklamasi dapat dilakukan sebagai efek samping dari propagasi lokal. Alih-alih eksplisit menghapus entitas dalam langkah terakhir, kerangka ditandai lembut diubah untuk merujuk nihil. Akibatnya, dapat direklamasi kemudian ketika pengumpulan sampah lokal dijalankan lagi. Selain itu, jika objek yang terkait dengan kerangka yang sekarang menjadi terjangkau, maka akan direklamasi juga. Jika proxy lokal disebut dengan objek yang juga tidak lagi terjangkau, mereka akan ditandai dan tetap tidak ditandai seperti itu. Oleh karena itu aman untuk membiarkan pengumpul sampah lokal merebut kembali proxy none-ditandai, setelah mengirim pesan ke penurunan kerangka proxy terkait di salah satu proses remote.

            Dengan hirarki mengorganisir ke dalam kelompok, solusi yang lebih scalable untuk pengumpulan sampah terdistribusi dapat dicapai. Ide dasarnya adalah untuk membiarkan tingkat rendah kelompok mengumpulkan sampah, dan meninggalkan analisis referensi antarkelompok kepada kelompok yang lebih tinggi-tingkat berikutnya. Dengan membiarkan rendah tingkat kelompok mengurangi jumlah objek yang perlu ditelusuri, lebih tinggi tingkat kelompok dasarnya beroperasi pada jumlah yang sama sebagai obyek masing-masing jika subkelompok, tetapi yang tersebar di jaringan yang lebih besar. Kami menghilangkan detail, yang dapat ditemukan dalam (Lang et al, 1992.).

Daftar Pustaka

Andrew S. Tanenbaum & Maarten Van Steen. 2002. Distributed Systems Principles And Paradigms. New Jersey 07458: Prentice Hall.

http://mytopfiles.com/documents/file/2006-Book-distributed-systems-principles-and paradigms-2nd-editi/644041.htm

repository.politekniktelkom.ac.id