sinkronisasi clock

22
SISTEM TERDISTRIBUSI Naming And Synchronization [] SURYA DARMA [1102698] ERAHAYANI RITONGA [1102696] PENI MALA SARI PENDIDIKAN TEKNIK INFORMATIKA

Upload: jujuk-kurniawan

Post on 12-Apr-2016

244 views

Category:

Documents


31 download

DESCRIPTION

Komputer

TRANSCRIPT

Page 1: Sinkronisasi Clock

SISTEM TERDISTRIBUSI

Naming And Synchronization

[] SURYA DARMA

[1102698] ERAHAYANI RITONGA

[1102696] PENI MALA SARI

PENDIDIKAN TEKNIK INFORMATIKA

UNIVERSITAS NEGERI PADANG

2014

Page 2: Sinkronisasi Clock

SYNCHRONIZATION

A. Clock Synchronization

Sistem tersistribusi sebenarnya adalah proses-proses yang berkolaborasi atau

bekerjasama.. Sikronisasi sendiri diperlukan baik di sistem tunggal atau sistem terdistribusi

dengan alasan yang sama.

bagian penting dalam Sikronisasi :

Berbagi Pemakaian sumberdaya (Sharing resources)

Pengurutan kejadian

Kesepakatan clock terdistribusi

Algoritma untuk sinkronisasi dalam sistem terdistribusi memiliki beberapa sifat:

Informasi yang relevan terdistribusi di beberapa komputer

Keputusan pembuatan proses hanya berdasarkan informasi local

kegagalan Event dengan penyebab tunggal di dalam sistem harus dihindarkan

Tidak tersedianya clock atau sumber waktu global yang akurat.

1. Physical Clocks

Pada beberapa sistem, waktu clock aktual menjadi penting, contohnya real-time sistem.

Untuk sistem ini diperlukan Physical Clocks eksternal. Karena alasan efisiensi dan

redundansi, penggunaan Physical Clocks jamak biasanya mengakibatkan muncul nya dua

masalah :

Bagaimana mensinkronkan eksternal clock tersebut dengan clock sebenarnya

Bagaimana mensinkronkan antar clock yang ada.

2. Algoritma Sinkronisasi Clock

Frekuensi detik clock logika tergantung dari nilai yang dimuat ke counter. Nilai ini yang

menentukan resolusi clock. Interval waktu yang lebih kecil dari resolusi tidak dapat

dibedakan. Laju pergeseran clock adalah perubahan offset antara clock dengan nominal

referensi ideal per unit waktu yang diukur di referensi. Clock hardware hanya berupa nilai di

dalam register, seperti nilai 32 bit, yang kelak di roll-over. Penanganan dilakukan dengan

Page 3: Sinkronisasi Clock

mengubah konstanta yang ditambahkan untuk memperoleh clock software yang biasanya

berkisar di orde mikrodetik atau milidetik dari tanggal yang disepakati.

Algoritma Cristian

Bila sebuah mesin memiliki penerima WWV sehingga dapat berfungsi sebagai time server.

Secara periodik, setiap mesin mengirim pesan ke time server menanyakan waktu terkini,

Cutc. Ada 2 masalah dalam algo ini,. Masalah majornya adalah waktu penanya tidak boleh

dimundurkan dan untuk mengatasinya adalah dengan memperlambat clock tick.

Masalah minor adalah waktu tunda dari balasan server,yang besarnya variatif tergantung

beban jaringan. Diatasi dengan menghitung interval waktu pengiriman dan penerimaan pesan

To sd T1 dan waktu penangan interupsi I, sehingga bisa dihitung lama propagasi pesan dalam

satu arah(T1-T0-I)/2. Nilai ini dijadikan koreksi terhadap nilai waktu yang diperoleh.

Algoritma Berkeley

Algoritma Berkeley digunakan untuk mensinkronkan clock relatif terhadap clock lainnya,

dan bukan terhadap master clock tertentu. Daemon di server time melakukan polling ke

semua client, yang akan dijawab oleh setiap clock. Kemudian time daemon akan mengirim

penyesuaiannya.

Forward dapat dilakukan dengan meloncat

Backward perlu perlambatan yang bertahap

Page 4: Sinkronisasi Clock

Algoritma Rata-rata

Berbeda dengan metode sebelumnya yang terpusat, maka metode ini mensinkronkan clock

dengan cara desentralisasi. Cara kerjanya dengan membagi waktu ke dalam interval

resinkronisasi yang lebarnya tetap. Interval ke I dimulai pada T0 + iR dan berjalan sampai

T0+(I+1)R, dimana T0 adalah kesepakatan lalu dan R adalah parameter sistem. Pada setiap

awal interval, setiap mesin mengumumkan waktu terkininya. pengumuman ini tidak akan

terjadi bersamaan. Setelah semua pengumuman diterima, waktu yang baru dapat dihitung

dengan algoritma yang ada. Algoritma paling sederhana adalah merata-ratakan nilai yang

diperoleh dari semua mesin.

Sumber Clock Eksternal Jamak

Algoritma ini menjadi dasar untuk protokol NTP (Network Time Protocol). Digunakan

dalam sistem yang disinkronkan dengan sangat akurat.

Waktu diperoleh dari beberapa sumber UTC

Koreksi dari waktu rambat diperhitungkan

Gunakan media overlap sebagai perkiraan terbaik

Standar waktu yang diterima bersumber pada satu set jam atom-jam atom. Bila perambatan

sinyal radio tidak dipengaruhi oleh kondisi atmosfir, maka pemancaran sinyal waktu dan

penerimaan sinyal tersebut dengan akurat dapat terjadi. Keakurasian terbaik yang dapat

Page 5: Sinkronisasi Clock

dicapai melalui satelit GEOS atau GPS berkisar 1.1 milidetik. Untuk aplikasi tertentu,

didefinisikan kebenaran (correctness) sebagai dalam toleransi ∆ misal dalam 5 milidetik

UTC. Definisi lain yang kadang-kadang digunakan adalah t` > t => C(t`) > C(t).

3. Penggunaan Clock Sinkronisasi ( Use Of Synchronized Clocks)

Pelaksanaan sinkronisasi clock dalam skala luas terjadi baru-baru ini saja, yang salah satu

teknologi enabling-nya adalah internet. Yang dapat mensinkronkan jutaan clock dalam orde

milidetik dengan UTC. Berbagai algoritma baru yang menggunakan clock sinkron mulai

bermunculan, berikut ini contohnya :

At-Most-Once Message Delivery

Setiap pesan membawa pengenal koneksi dan time stamp. Untuk setiap koneksi, server

menyimpan time stamp terbaru ke dalam tabel. Bila ada pesan masuk dengan timestamp yang

lebih lama daripada time stamp yang disimpan, maka pesan tersebut akan ditolak dan

dianggap sebagai duplikat. Server menyimpan variabel global yang memungkinkannya untuk

menghapus timestamp lama.

Konsistensi Cache Berbasis Clock

Bila dua komputer memodifikasi file secara bersamaan, berpotensi menyebabkan

inkonsistensi. Ide dasarnya bila client menginginkan sebuah file, lease akan diberikan

untukmenentukan berapa lama copy tersebut valid. Bila lease sudah hampir habis

berlakunya, cache dari copy tersebut tidak akan digunaka dan client dapat meminta untuk

memperbaharuinya.

B. Logical Clocks

Jika dua proses tidak berinteraksi, tidak perlu bahwa jam mereka akan disinkronkan karena

kurangnya sinkronisasi tidak akan diamati dengan demikian tidak dapat menimbulkan masalah.

Selain itu, dia menunjukkan bahwa apa yang biasanya penting bukanlah semua proses setuju

pada apa waktu itu, melainkan bahwa mereka setuju pada urutan di mana event terjadi.

1. Lamport Timestamps

Page 6: Sinkronisasi Clock

Lamport mendefinisikan hubungan , Ekspresi a → b dibaca "a terjadi sebelum b" dan berarti

bahwa semua proses setuju bahwa event pertama terjadi, maka setelah itu, event b terjadi.

1) Jika a dan b merupakan suatu event dalam proses yang sama, dan terjadi sebelum b, maka

→ b benar.

2) Jika pesan yang dikirim oleh salah satu proses, dan b adalah dari pesan yang diterima

oleh proses lain, maka a → b juga benar pesan tidak dapat diterima sebelum dikirim, atau

bahkan pada saat yang sama waktu pengiriman, karena dibutuhkan terbatas, jumlah nol

waktu untuk tiba.

Terjadi sebelumnya merupakan relasi transitif, jadi jika a→ b dan b → c, maka → c. Jika dua

event, x dan y, terjadi dalam proses yang berbeda yang tidak bertukar pesan (bahkan secara

tidak langsung melalui pihak ketiga), maka x → y tidak benar, tetapi juga tidak ada y → x.

Event ini dikatakan bersamaan, yang berarti thet ada van dikatakan (atau perlu dikatakan)

tentang kapan event itu terjadi pertama.

2. Cap vektor

Lamport timnestamp menyebabkan situasi ua kejadian dalam sistem terdistribusi secara total

dipesan dengan properti yang jika event event yang terjadi sebelum event b, maka juga akan

diposisikan dalam memesan sebelum b, yaitu C (a) < C (b). Namun dengan Lamport cap,

tidak ada yang dapat dikatakan tentang hubungan antara dua kejadian a dan b hanya dengan

membandingkan waktu, nilai C (a) dan C (b), masing-masing. Dengan kata lain, jika C (a)

<C (b), maka hal ini tidak selalu berarti bahwa terjadi sebelumnya b.

Salah satu contoh yang paling populer seperti sistem pesan elektronik adalah layanan papan

buletin internet , jaringan berita. Pengguna bergabung dengan kelompok diskusi tertentu.

Postingan dalam kelompok tersebut.

Sebuah vektor timestamp VT (a) ditugaskan untuk sebuah event memiliki properti bahwa

jika VT (a) <VT (b) untuk beberapa event b, maka event yang diketahui kausal prcede event

b. waktu perangko vektor dibangun dengan membiarkan setiap proses pi mempertahankan

vektor vi dengan dua sifat berikut:

1) Vi[i] adalah jumlah event yang telah terjadi sejauh ini di pi.

2) Jika Vi[j] = k maka pik nowns bahwa k event telah terjadi di pj.

Page 7: Sinkronisasi Clock

Properti pertama dikelola oleh incrementing Vi [i] pada terjadinya setiap event baru yang

happenes pada proses Pi properti kedua dipertahankan dengan membonceng vektor bersama

dengan pesan yang dikirim. Secara khusus, ketika Pi mengirim pesan m, ia akan

mengirimkan sepanjang arus vektor sebagai vt timestamp.

Dalam sebuah penerima informasi tentang jumlah kejadian yang telah terjadi di Pi. Lebih

penting, namun adalah bahwa penerima diberitahu berapa banyak Avants pada proses lainnya

telah terjadi sebelum Pi mengirim pesan m. dengan kata lain, cap vt m memberitahu

penerima berapa banyak event di prosesses lain telah mendahului m, dan di mana m dapat

kausal tergantung. Ketika proses pi menerima m, yang menyesuaikan vektor sendiri dengan

menetapkan setiap entri Vj [k], untuk max {Vj [k], vt [k]}. Vektor sekarang mencerminkan

jumlah pesan yang Pj harus menerima untuk memiliki setidaknya terlihat menjadi pesan yang

sama yang mendahului pengiriman m. Hereaafter, entri Vj [t] bertambah dengan 1 mewakili

hal menerima pesan berikutnya.

Secara khusus, pesan r disampaikan hanya jika kondisi berikut ini mte:

1) Vt (r) [j] = Vk [j] +1

2)   Vt (r) [i] ≤ Vk [i] untuk semua i ≠ j

Kondisi pertama menyatakan bahwa r adalah pesan berikutnya yang Pk mengharapkan dari

proses Pj. Yang kedua menyatakan bahwa kondisi Pk belum melihat adanya pesan yang tidak

terlihat oleh Pj ketika ia mengirimkan pesan r. Secara khusus, ini berarti bahwa Pk telah

melihat pesan.

C. Global StateKetika jumlah node dalam sebuah sistem terdistribusi berkembang, menjadi semakin sulit

bagi setiap node untuk melacak orang lain. Pengetahuan tersebut dpenting untuk

melaksanakan algoritma terdistribusi seperti routing, multicasting, data penempatan, mencari,

dan sebagainya.

Dalam jaringan overlay geometrik setiap node diberi posisi di 111 ruang dimensi geometris ,

sehingga jarak antara dua node dalam ruang mencerminkan kinerja dunia nyata metrik. Yang

paling sederhana, dan paling diterapkan Sebagai contoh, adalah di mana jarak sesuai dengan

internode latency. Dengan kata lain. diberikan dua node P dan Q, maka jarak d (P, Q)

Page 8: Sinkronisasi Clock

mencerminkan berapa lama waktu yang dieprlukan pesan ke perjalanan dari P ke Q dan

sebaliknya.

Ada banyak aplikasi jaringan overlay geometris. Pertimbangkan situasi di mana sebuah situs

web di server 0 telah direplikasi ke beberapa server S} "". Sk di Internet. Ketika sebuah klien

meminta halaman C dari 0, yang kedua mungkin memutuskan untuk mengarahkan

permintaan itu ke server terdekat dengan C, yaitu, salah satu yang akan memberikan waktu

respon yang terbaik. Jika lokasi geometrik C dikenal, serta orang-orang dari setiap server

replika, 0 kemudian dapat hanya memilih server S, yang d (C, SJ adalah minimal. Perhatikan

bahwa seperti pilihan hanya membutuhkan pemrosesan lokal di O. Dengan kata lain, ada,

misalnya, tidak perlu sampel semua latency antara C dan masing-masing server replika.

Sebagai contoh terakhir, mempertimbangkan posisi berbasis routing (Araujo dan Rodrigues,

2005, dan Stojmenovic, 2002). Dalam skema tersebut, pesan diteruskan tujuan

menggunakan informasi posisi saja. Sebagai contoh, sebuah algoritma routing yang

membiarkan setiap node meneruskan pesan ke tetangga yang paling dekat dengan tujuan.

Meskipun dengan mudah dapat menunjukkan bahwa algoritma tertentu tidak perlu

bertemu,menggambarkan bahwa informasi lokal hanya digunakan untuk mengambil

keputusan. Ada tidak perlu untuk menyebarkan informasi tersebut kepada link atau semua

node dalam jaringan, seperti kasus dengan algoritma routing konvensional.

Secara teoritis, posisi node di ruang m-dimensi geometris membutuhkan

m tindakan jarak +1 ke node dengan posisi yang dikenal. Hal ini dapat dengan mudah dilihat

dengan mempertimbangkan kasus m = 2, seperti ditunjukkan pada Gambar. 6-18. Dengan

asumsi bahwa P simpul ingin menghitung posisinya sendiri, kontak tiga node lain dengan

posisi yang dikenal dan mengukur jarak ke masing-masing.

D. PEMILIHAN ALGORITMA

Algoritma didistribusikan memerlukan satu proses untuk bertindak sebagai koordinator,

inisiator, atau melakukan beberapa peran khusus. Secara umum, tidak peduli Proses ini

mengambil tanggung jawab khusus, tapi salah satu dari mereka harus melakukannya. dalam hal

Page 9: Sinkronisasi Clock

ini bagian ini kita akan melihat algoritma untuk memilih seorang koordinator (menggunakan ini

sebagai generik nama untuk proses khusus).

Jika semua proses persis sama, tanpa membedakan karakteristik,

tidak ada cara untuk memilih salah satu dari mereka untuk menjadi istimewa. Akibatnya, kita

akan mengasumsikan bahwa setiap proses memiliki nomor yang unik, misalnya, alamat jaringan

nya (untuk kesederhanaan, kita akan mengasumsikan satu proses per mesin).

Ada banyak algoritma dan variasi, yang penting yang dibahas dalam buku-buku teks

dengan Lynch (l996) dan Tel (2000), masing-masing.

1. The Bully Algorithm

Sebagai contoh pertama, mempertimbangkan algoritma pengganggu yang dibuat oleh Garcia-

Molina (1982). Bila sebuah proses mendapatkan coordinator tidak lagi menanggapi request

yang dikirim, maka proses pemilihan akan diinisiasi. Proses P mengadakan pemilihan

sebagai berikut:

1) P mengirim pesan ELECTION ke semua proses dengan nomor proses yang lebih besar.

2) Bila tidak ada tanggapan, proses P memenangkan pemilihan dan menjadi koordinator.

3) Namun bila salah satu proses dengan nomor yang lebih tinggi menjawab, proses

tesebutlah yang akan mengambil alih proses pemilihan. Pekerjaan prosess P sendiri

selesai.

2. Sebuah Algoritma Cincin

Proses diperintah secara fisik atau logis, sehingga setiap proses tahu siapa penggantinya.

Ketika setiap proses pemberitahuan bahwa koordinator tidak berfungsi, itu membangun suatu

PEMILU pesan yang berisi nomor proses sendiri dan mengirimkan pesan ke penggantinya.

Jika penggantinya sedang down, pengirim melompat ke penerus dan pergi ke anggota

berikutnya di sepanjang cincin. Pada setiap langkah di sepanjang jalan, pengirim

menambahkan nomor proses sendiri untuk daftar di pesan secara efektif membuat dirinya

calon yang akan terpilih sebagai koordinator.

Akhirnya, pesan akan kembali ke proses yang memulai semuanya. proses

mengakui event ini ketika menerima pesan masuk yang berisi nya

sendiri proses nomor. Pada saat itu, jenis pesan diubah menjadi KOORDINATOR

dan beredar sekali lagi, kali ini untuk menginformasikan orang lain yang koordinator adalah

Page 10: Sinkronisasi Clock

(anggota daftar dengan jumlah tertinggi) dan siapa para anggota cincin baru. Ketika pesan ini

sudah beredar sekali, itu akan dihapus dan semua kembali bekerja

E. Mutual Exclusion

Dasar dari sistem terdistribusi adalah konkurensi dan kolaborasi

diantara beberapa proses. Dalam banyak kasus, hal ini juga berarti bahwa proses akan

membutuhkan untuk secara bersamaan mengakses sumber daya yang sama. Untuk mencegah

akses yang bersamaan yang dapat merusak sumber daya, atau membuatnya tidak konsisten,

solusi yang diperlukan untuk memberikan saling eksklusif akses oleh proses.

1. Sebuah Algoritma Terpusat

Cara yang paling mudah untuk mencapai bersama. pengecualian dalam sistem terdistribusi

untuk mensimulasikan bagaimana hal itu dilakukan dalam suatu sistem satu-prosesor. Salah

satu proses terpilih sebagai koordinator. Setiap kali suatu proses ingin mengakses sumber

daya , ia akan mengirimkan pesan permintaan kepada koordinator menyatakan ingin

mengakses dan meminta izin. Jika tidak ada proses lain yang sedang mengakses sumber daya

itu, koordinator mengirimkan kembali balasan pemberian izin.

Koordinator mengambil item pertama dari antrian permintaan yang ditangguhkan dan

mengirimkan proses bahwa memberikan pesan. Jika proses masih diblokir (yaitu, ini adalah

pesan pertama untuk itu), itu unblocks dan mengakses sumber daya. Jika pesan eksplisit telah

dikirim menyangkal izin, proses harus jajak pendapat untuk lalu lintas masuk atau blok nanti.

Either way, ketika melihat hibah, dapat pergi ke depan juga.

koordinator hanya memungkinkan satu proses pada suatu waktu untuk sumber daya. Hal ini

juga adil, karena permintaan yang diberikan dalam urutan di mana mereka diterima. Proses

Tidak pernah menunggu selamanya.

2. Algoritma Terdistribusi

Algoritma Ricart dan Agrawala mensyaratkan bahwa harus ada pemesanan total dari semua

event dalam sistem. Artinya, untuk setiap sepasang event, seperti pesan, itu harus jelas mana

yang benar-benar terjadi pertama kali. Algoritma Lamport yang disajikan dalam Sec. 6.2.1

adalah salah satu cara untuk mencapai pemesanan ini dan dapat digunakan untuk

memberikan cap waktu untuk saling pengecualian didistribusikan.

Page 11: Sinkronisasi Clock

Algoritma ini bekerja sebagai berikut. Ketika sebuah proses ingin mengakses sumber daya

bersama, itu membangun sebuah pesan yang berisi nama sumber daya, nomor proses nya,

dan arus (logis) waktu. Ini kemudian mengirimkan pesan ke semua proses lainnya,

konseptual termasuk dirinya sendiri. Pengiriman pesan diasumsikan handal, yaitu, tidak ada

pesan yang hilang.

Ketika sebuah proses menerima pesan permintaan dari proses lain, tindakan itu mengambil

tergantung pada negara sendiri sehubungan dengan sumber daya yang disebutkan dalam

pesan.

Tiga kasus yang berbeda harus dibedakan secara jelas:

1) Jika penerima tidak mengakses sumber daya dan tidak ingin mengakses

itu, ia akan mengirimkan kembali pesan OK ke pengirim.

2) Jika penerima telah memiliki akses ke sumber daya, dan tidak

menjawab. Sebaliknya, itu antrian permintaan.

3) Jika penerima ingin mengakses sumber daya juga tapi belum

melakukannya, itu membandingkan timestamp dari pesan yang masuk dengan saya. salah

satu yang terkandung dalam pesan yang telah dikirim orang. yang terendah satu menang.

Jika pesan yang masuk memiliki timestamp yang lebih rendah, penerima mengirimkan

kembali pesan OK. Jika pesan sendiri memiliki lebih rendah timestamp, antrian penerima

permintaan yang masuk dan mengirimkan apa-apa.

Setelah mengirimkan permintaan meminta izin, proses duduk kembali dan menunggu sampai

orang lain telah diberi izin. Segera setelah semua izin diperoleh , dan selesai, ia akan

mengirimkan pesan OK untuk semua proses pada perusahaan antrian dan menghapus mereka

semua dari antrian.

Proses 0 mengirimkan semua permintaan dengan timestamp 8, sementara pada saat yang

sama, Proses 2 mengirimkan semua permintaan dengan timestamp 12. Proses 1 tidak tertarik

di sumber daya, sehingga mengirimkan OK untuk kedua pengirim. Proses 0 dan 2 baik

melihat konflik dan membandingkan cap waktu. Proses 2 melihat bahwa ia telah kehilangan,

sehingga memberikan izin ke 0 dengan mengirimkan OK. Proses 0 sekarang antrian

permintaan dari 2 untuk nanti pengolahan dan mengakses sumber daya, seperti yang

ditunjukkan pada Gambar. 6-15 (b). Ketika selesai, menghilangkan permintaan dari 2 dari

antrian dan mengirim pesan OK untuk memproses 2, yang memungkinkan kedua untuk pergi

Page 12: Sinkronisasi Clock

ke depan, seperti yang ditunjukkan pada Gambar. 6-15 (c). Algoritma ini bekerja karena

dalam kasus konflik, timestamp terendah menang dan semua orang setuju pada Urutan cap

waktu

Perhatikan bahwa situasi pada Gambar. 6-15 akan menjadi dasarnya berbeda jika Proses 2

telah mengirimkan pesannya di awal waktu sehingga proses sudah 0 dan diberikan izin

sebelum membuat permintaan sendiri. Dalam hal ini, akan memiliki 2 menyadari bahwa itu

sendiri sudah akses ke sumber daya pada saat permintaan, dan antri bukannya mengirimkan

balasan.

Seperti dengan algoritma terpusat dibahas di atas, saling pengecualian adalah dijamin tanpa

kebuntuan atau kelaparan. Jumlah pesan yang dibutuhkan per entri sekarang 2 (n - 1), di

mana jumlah proses dalam sistem adalah n. Terbaik dari semua, tidak ada single point of

failure ada.

Sayangnya, titik tunggal kegagalan telah digantikan oleh poin n kegagalan. Jika proses

apapun crash, maka akan gagal untuk menanggapi permintaan. Keheningan ini akan diartikan

(salah) sebagai penolakan izin, sehingga memblokir semua berikutnya upaya oleh semua

proses untuk memasukkan semua daerah kritis. Karena probabilitas dari satu proses n gagal

setidaknya n kali lebih besar sebagai koordinator tunggal gagal, kami telah berhasil

mengganti algoritma miskin dengan yang lebih dari n kali buruk dan membutuhkan lalu

lintas jaringan yang jauh lebih banyak.

Algoritma dapat ditambal oleh trik yang sama yang kita diusulkan sebelumnya. Ketika

permintaan datang, penerima selalu mengirimkan balasan, baik pemberian atau menyangkal

izin. Setiap kali baik permintaan atau balasan hilang, waktu pengirim keluar dan terus

mencoba sampai baik balasan datang kembali atau pengirim menyimpulkan bahwa tujuan

sudah mati. Setelah permintaan ditolak, pengirim harus memblokir menunggu untuk pesan

OK berikutnya.

Masalah lain dengan algoritma ini adalah bahwa baik komunikasi multicast primitif harus

digunakan. atau proses masing-masing harus menjaga daftar anggota grup sendiri, termasuk

proses memasuki kelompok, meninggalkan kelompok, dan menabrak. Metode ini bekerja

terbaik dengan kelompok-kelompok kecil dari proses yang tidak pernah berubah mereka

kelompok keanggotaan.

Page 13: Sinkronisasi Clock

Akhirnya, ingat bahwa salah satu masalah dengan algoritma terpusat adalah bahwa sehingga

menangani semua permintaan dapat menyebabkan kemacetan. Dalam algoritma terdistribusi,

semua proses yang terlibat dalam semua keputusan yang menyangkut mengakses sumber

daya bersama. Jika satu proses tidak dapat menangani beban, tidak mungkin bahwa memaksa

semua orang untuk melakukan hal yang sama secara paralel akan banyak membantu.

Berbagai perbaikan kecil yang mungkin untuk algoritma ini. Misalnya, mendapatkan izin

dari setiap orang benar-benar berlebihan. Semua yang diperlukan adalah suatu metode untuk

mencegah dua proses mengakses sumber daya pada saat yang sama. Algoritma dapat

dimodifikasi untuk memberikan izin ketika telah dikumpulkan izin dari sederhana sebagian

besar proses lainnya, bukan dari mereka semua. Tentu saja, dalam variasi ini, setelah proses

telah memberikan izin untuk satu proses, tidak bisa memberikan izin yang sama untuk proses

lain sampai yang pertama selesai.

Namun demikian, algoritma ini lebih lambat, lebih rumit, lebih mahal,

dan kurang kuat bahwa yang terpusat aslinya. Mengapa repot-repot belajar di bawah kondisi

ini? Untuk satu hal, itu menunjukkan bahwa algoritma didistribusikan setidaknya mungkin,

sesuatu yang tidak jelas ketika kita mulai. Juga, dengan menunjukkan kekurangan, kita dapat

merangsang teori masa depan untuk mencoba untuk menghasilkan algoritma yang benar-

benar berguna. Akhirnya, seperti makan bayam dan belajar Latin SMA, beberapa hal yang

dikatakan baik untuk Anda dalam beberapa cara abstrak

3. Algoritma Token Ring

Algoritma Token ring menggunakan sebuah jaringan bus dengan proses yang tidak

berurutan. Melaui perangkat lunak, logika ring disusun dengan setiap proses yang ditetapkan

posisinya dalam ring.

Posisi ring dapat ditentukan dengan menggunakan urutan nomor alamat jaringan atau dengan

cara lain, namun yang terpenting adalah setiap proses harus tahu siapa proses sesudahnya.

Pada saat ring diinialisasi, proses 0 diberi token yang nantinya di sirkulasi dalam jaringan.

Token ini berpindah dari proses K ke proses K+1 dengan pesan point-to-point. Ketika

proses memperoleh token dari tetangganya, proses memeriksa apakah proses situ sedang

berusaha memasuki critical region.

Jika ingin masuk, proses memasuki critical region, mengerjakan semua yang diperlukan

dan meninggalkan critical region.

Page 14: Sinkronisasi Clock

Setelah keluar, proses melewatkan token ke ring. Proses tidak mengijinkan memasuki

critical region yang kedua kalinya dengan token yang sama.

Jika proses yang mempunyai token tetapi tidak ingin memasuki critical region, proses segera

melewatkan token. Konsekuensinya, jika tak ada proses yang ingin masuk critical region,

token berputar dengan kecepatan tinggi mengelilingi ring.

Kelebihan dan kekurangan dari algoritma token ring

Algoritma ini menjamin hanya satu proses masuk critical region, karena hanya satu

proses yang dapat mempunyai token

Startvation tidak terjadi karena adanya pengurutan proses

Kekurangan

Jika token hilang, token harus dibangitkan lagi, dan mendeteksi token hilang adalah sulit,

karena interval waktu kemunculan token tidak dibatasi.

Proses yang crash akan menimbulkan kesulitan.

Perbandingan tiga algoritma

Algoritma terpusat merupakan algoritma yang efisien dan lebih mudah dari ketiga algoritma

tersebut. Hanya ada tiga proses yang dibutuhkan untuk keluar masuk daerah kritis adalah

reguest, grant, release. Pada algoritma terdistribusi lebih sensitive pada kejadian crash

Page 15: Sinkronisasi Clock

DAFTAR PUSTAKA

second edition

Andrew s. Tanenbaum dan Maarten Van Steen. distributed systemsprinciples and paradigms.

second edition

http://prezi.com/c8eqtkvgmdub/sistem-terdistribusi/

synchronization

http://esetblog.blogspot.com/2014/01/pertemuan-v-sistem-terdistribusi.html