DAFTAR ISI
Puji syukur penulis
panjatkan kehadirat Allah SWT atas segala
limpahan Rahmat, Inayah, Taufik dan Hinayahnya sehingga penulis dapat
menyelesaikan Tugas Sistem Terdistribusi ini dalam bentuk maupun isinya yang
sangat sederhana. Semoga Tugas Sistem Terdistribusi ini dapat dipergunakan
sebagai salah satu acuan, petunjuk maupun pedoman bagi pembaca dalam
administrasi pendidikan dalam profesi keguruan.
Harapan penulis semoga Tugas Sistem Terdistribusi ini membantu
menambah pengetahuan dan pengalaman bagi para pembaca, sehingga penulis dapat
memperbaiki bentuk maupun isi Tugas ini sehingga kedepannya dapat lebih baik.
Tugas Sistem Terdistribusi ini penulis akui masih banyak kekurangan karena
pengalaman yang penulis miliki sangat kurang. Oleh kerena itu penulis harapkan
kepada para pembaca untuk memberikan masukan-masukan yang bersifat membangun
untuk kesempurnaan Tugas ini.
Penulis
MtgDua.3-april-2013
Dampak dan
pengaruh dari perkembangan teknologi saat ini semakin meningkat diberbagai
perusahaan, organisasi maupun masyarakat. Kemajuan teknologi begitu cepat
sehingga dapat memperbaharui sistem kerja yang masih manual menjadi terkomputerisasi.
Suatu sistem yang dapat membantu mengerjakan segala bentuk kegiatan organisasi
misalnya melakukan input, pemrosesan data dan output data sehingga didapatkan
hasil yang tepat dan akurat.
Distribusi fungsi : komputer memiliki kemampuan fungsi yang
berbeda-beda:
• client/server
• Host/terminal
• Data gathering / data processing
Distribusi beban/keseimbangan : pemberian tugas ke prosesor
secukupnya sehingga unjuk kerja seluruh sistem teroptimasi.
Sifat terdistribusi mencegah terjadinya application domain.
• cash register dan sistem persediaan untuk supermarket
• Komputer pendukung collaborative work
Replikasi
kekuatan pemrosesan : independent processors bekerja untuk pekerjaan yang sama
• Sistem terdistribusi terdiri dari kumpulan mikrokomputer yang
memiliki kekuatan pemrosesan yang tidak dapat dicapai oleh super computer 10000
CPU, masing-masing berjalan pada 50 MIPS, mencapai 500000 MIPS, Maka satu
perintah dijalankan dalam waktu 0.002 nsec.
Pemisahan fisik : sistem yang menggantungkan pada fakta bahwa komputer secara
fisik terpisah (mencapai kehandalan).
Ekonomis : kumpulan mikroprosesor menawarkan harga/unjuk kerja yang lebih baik
dari pada mainframe.
sebagai dasar dalam sistem terdistribusi
: berupa sekumpulan proses untuk mengkoordinasikan tindakan atau menyetujui
satu atau beberapa nilai. Contohnya pada kasus mesin seperti pesawat ruang
angkasa. Hal itu perlu dilakukan, komputer mengendalikannya agar setuju pada
kondisi tertentu seperti apakah misi dari pesawat luar angkasa dilanjutkan atau
telah selesai.,Komputer tersebut harus mengkoordinasikan tindakannya secara
tepat untuk berbagi.
Coordination adalah apakah system
terdistribusi asinkron atau sinkron. Algoritma –algoritma yang digunakan juga
harus mempertimbangkan kegagalan yang terjadi, dan bagaimana caranya untuk
berhubungan satu sama lain ketika sedang mendesaian algoritma. Selanjutnya di
makalah ini juga akan dijelaskan mengenai masalah dalam mendistribusikan mutual
exclusion, election, multicastcommunication, dan mengenai masalah dalam
persetujuan(agreement).
Hal yang penting dalam Coordination and
Agreement adalah apakah sistem terdistribusi asinkron atau sinkron. Algoritma
–algoritma yang digunakan juga harus mempertimbangkan kegagalan yang terjadi,
dan bagaimana caranya untuk berhubungan satu sama lain ketika sedang mendesaian
algoritma. Selanjutnya di makalah ini juga akan dijelaskan mengenai masalah
dalam mendistribusikan mutual exclusion, election, multicast communication, dan
mengenai masalah dalam persetujuan(agreement)
Sinkronisasi dan Asinkronisasi. Opsi ini
menunjukkan bagaimana proses input dan output ke filesystem dilakukan.
sinkornisasi berarti dilakukan secara sinkronisasi. Contohnya digunakan pada
floopy, artinya ketika anda menyalin sebuah file ke floopy, perubahan secara
fisik langsung ditulis ke floppy saat anda memberikan perintah copy Jika anda
menggunakan opsi async, input dan output dilakukan secara asinkronisasi. Dengan
contoh diatas, opsi ini membuat proses penyalinan ke floopy mungkin dilakukan
jauh setelah perintah copy anda berikan. Hal ini tidaklah buruk, bahkan
terkadang menjadi pilihan, dikarenakan misalnya jika anda memindahkan floopy
tanpa melakukan unmounting terlebih dahulu, file-file yang disalin mungkin
secara fisik belum masuk ke dalam floopy tersebut.
Pada
suatu sistem multithreading, sinkronisasi adalah suatu proses pengendalian
akses dari sumber daya terbagi pakai (shared resource) oleh banyak thread
sedemikian sehingga hanya satu thread yang dapat mengakses sumber daya tertentu
pada satu waktu.
Dalam
aplikasi multithreaded yang tidak tersinkronisasi, sangat mungkin terjadi
adanya satu thread memodifikasi suatu obyek yang dipakai bersama pada saat
thread lain sedangkan dalam proses menggunakan atau mengupdate nilai obyek
tersebut. Sinkronisasi mencegah jenis kerusakan data demikian, jika tidak
disinkronkan maka dapat mengakibatkan pembacaan yang buruk dan error yang
signifikan. Secara umum bagian kritis (critical sections) dari kode biasanya
ditandai dengan kata kunci synchronized.
koordinasi sistem berbasis, fokusnya adalah
pada bagaimana koordinasi antara proses berlangsung.Cabri dkk. (2000)
memberikan taksonomi model koordinasi untuk agen mobile yangdapat applled sama
untuk jenis lain dari sistem terdistribusi. Beradaptasi terminologiuntuk sistem
terdistribusi pada umumnya, kami membuat perbedaan antara model bersama
dua dimensi yang berbeda, temporal dan referensial.
Sistem
terdidtribusi adalah suatu kesatuan dari elemen-elemen yang saling berinteraksi
secara sistematis dan teratur untuk mendistribusikan data, informasi, obyek dan
layanan dari dan kepada pengguna yang terkait didalamnya. Infrastruktur utama
sistem terdistribusi adalah jaringan, hardware software dan pengguna yang
terkait di dalamnya. 1 Dalam sistem terdistribusi terdapat pembagian pekerjaan
antara elemen yang satu dengan elemen yang lain Sarana komunikasi antar elemen
dijembatani dengan jaringan. Tata cara komunikasi antar elemen diatur dengan
sebuah perjanjian sehingga terjadi komunikasi yang dapat dipahami antara masing
masing elemen yang terlibat.
Time adalah pengembangan dari sistem
multiprogram.Beberapa job yang berada pada memory utama dieksekusi oleh CPU
secara bergantian.CPU hanya bisa menjalankan program yang berada pada memory
utama. Perpindahanantar job terjadi sangat sering sehingga user dapat
berinteraksi dengan setiap programpada saat dijalankan. Suatu job akan
dipindahkan dari memori ke disk dan sebaliknya.
Time juga disebut dengan sistem komputasi
interaktif, dimanasistem komputer menyediakan komunikasi on-line antara user
dengan sistem. Usermemberikan instruksi pada sistem operasi atau program secara
langsung dan menerimarespon segera. Perangkat input berupa keyboard dan perangkat
output berupa displayscreen, seperti cathode-ray tube (CRT) atau monitor. Bila
sistem operasi selesaimengeksekusi satu perintah, makan sistem akan mencari
pernyataan berikutnya dariuser melalui keyboard. Sistem menyediakan editor
interaktif untuk menulis programdan sistem debug untuk membantu melakukan
debugging program.
Sekumpulan algoritma yang tujuannya
bermacam-macam namun men-share tujuannya, sebagai dasar dalam sistem
terdistribusi : berupa sekumpulan proses untuk mengkoordinasikan tindakan atau
menyetujui satu atau beberapa nilai. Contohnya pada kasus mesin seperti pesawat
ruang angkasa. Hal itu perlu dilakukan, komputer mengendalikannya agar setuju
pada kondisi tertentu seperti apakah misi dari pesawat luar angkasa dilanjutkan
atau telah selesai.
Komputer tersebut harus
mengkoordinasikan tindakannya secara tepat untuk berbagi hal yang penting dalam
Coordination and Agreement adalah apakah system terdistribusi asinkron atau
sinkron. Algoritma –algoritma yang digunakan juga harus mempertimbangkan
kegagalan yang terjadi, dan bagaimana caranya untuk berhubungan satu sama lain
ketika sedang mendesaian algoritma. Selanjutnya di makalah ini juga akan
dijelaskan mengenai masalah dalam mendistribusikan mutual exclusion, election,
multicast communication, dan mengenai masalah dalam persetujuan(agreement).
6.1 Logical Clock & Synchronisation
A. Sinkronisasi
Clock
Alasan penting sinkronisasi waktu di system tersebar:
·
Waktu dapat
merupakan kuntitas yang perlu diukur secara akurat untuk mengetahui saat
terjadinya suatu kejadian
·
Banyak
algoritma yang bergantung pada sinkronisasi clock seperti pengelolaan
konsistensi data tersebar, perkiraan otentikasi, dsb.
Lamport (1978) menunjukkan sinkronisasi clock memungkinkan, yaitu:
·
Sinkronisasi clock
tak perlu absolute
·
Penjaminan
urutan (order) kejadian-kejadian yang benar
o
Logical Clock
Kita dapat membuat mekanisme
pewaktuan sederhana yaitu pengurutan kejadian-kejadianm berdasarkan pada
nilai-nilai clock yang mengikat yang dijamin konsisten dengan keterdahuluan sebab.
o
Algoritma
Lamport
Relasi happens-before (a,b), “a terjadi sebelum b” berarti semua
proses sepakat bahwa kejadianmpertama yaitu a terjadi kemudian setelah itu
kejadian b terjadi.
happens-before merupakan relasi transitif sehingga: jika a,b dan b,c
maka a,c
o
Physical Clocks
Physical Clocks yang paling akurat adalah menggunaakan atomic
ascilator dengan akurasi
10-13 detik. Keluaran clock atomic digunakan sebagai standart waktu
nyata.
UTC (Coordinated Universal Time) berdasarkan waktu atom, kadang
disesuaikan dengan waktu astronomi.
B. Model
dasar physical clock
·
Tiap mesin
diasumsikan mempunyai timer yang memberi interupsi H kali per detik. Ketika
·
timer selesai
interupsi, interrupt handler menaikkan counter (C) yang menyimpan jumlah tick
·
(interupsi)
·
Ketika UTS
menunjukkan nilai t, maka nilai clock di mesin p adalah C (t) p
. Untuk kondisi
·
sempurnaC t
t p ( ) = untuk semua p dan t, berarti dC/dt=1.
·
Timer nyata
computer tidak diinterrupsi tepat H kali. Secara teori, bila H=60, clock
·
membangkitkan
216.000 tick per jam.
·
Hubungan antara
waktu clock dan UTS ketika tick jam pada tingkat yang berbeda
o
Algoritma
Cristian
Time
server mensinkronkan waktunya dengan UTC dan memberi waktu menurut clock-nya ke
computer-komputer
lain bila di minta. Memperoleh waktu sekarang dari waktu server
o
Algoritma
Berkeley
Time
server mengirimi (polling) mesin secara periodic meminta waktu saat itu
di mesin yang dikirimi. Berdasarkan jawaban, timer server estimasi waktu local
berdasarkan observasi waktu untuk pengiriman pesan, menghitung waktu rata-rata
dan memberi perintah ke mesin lain untuk memajukan dan mengundurkan clock
supaya mendapat su atu reduksi spesifik.
Banyak ahli mendefinisikan pemahaman tentang
koordinasi dengan memberi pendapat yang berbeda-beda tetapi mempunyai tujuan
yang sama, yakni bahwa koordinasi adalah asas umum dalam semua organisasi atau
dapat dikatakan koordinasi adalah asas pokok organisasi.
Mooney
dalam Sutarto (1998: 141) mengemukakan bahwa pengertian koordinasi adalah “The
orderly arrangement of group effort, to provide unity of action in the pursuit
of common purpose.”
Dengan demikian Mooney memandang bahwa
koordinasi merupakan suatu pengaturan usaha sekelompok orang secara teratur
untuk menciptakan kesatuan tindakan dalam mengusahakan tercapainya suatu
tujuan. Pengaturan usaha kelompok atau organisasi memang diperlukan, mengingat
organisasi terdiri atas sejumlah unit kerja yang berlainan fungsi namun diikat
oleh satu kesatuan tujuan tertentu.
Selaras dengan pendapat di atas Benn dalam
Sutarto (1998 : 141) mengatakan bahwa ”Coordination: A Continuous, harmonious
action toward the objectives, attained through leadership, organization, and
administration; The arrangement of group efforts in a continuous and orderly
manner so as to provide unification of action in the pursuit of a common goal.”
Dari
pendapat di atas diperoleh suatu konsep pemahaman bahwa koordinasi suatu
kelangsungan, keharmonisan mencapai tujuan, yang dapat dicapai melalui
kepemimpinan, organisasi dan administrasi; dan koordinasi juga dipandang
sebagai suatu penyusunan usaha-usaha kelompok di dalam suatu kelangsungan dan
keteraturan sikap sehingga menciptakan kesatuan tindakan dalam mengusahakan
tercapainya tujuan bersama. Dalam pendapat ini, faktor kepemimpinan, organisasi
dan administrasi tampaknya dijadikan faktor-faktor yang memerlukan keharmonisan
dan keteraturan yang dikondisikan melalui kegiatan koordinasi.
6.2.1 Algoritma Koordinasi
Ikhtisar
• Koordinasi di dalam sistem terdistribusi
–
mengapa
[yang] diperlukan, sumber permasalahan
• Pengeluaran timbal balik
–
ring-based
– multicast & waktu logis [ Ricart Dan
Agrawala]
• Pemilihan Pemimpin
–
ring-based
[ Chang&Roberts]
–
secara acak [ Itai&Rodeh]
– pohon identifikasi [ FIREWIRE
IEEE 1394]
Algoritma Koordinasi adalah pokok
membagi-bagikan sistem:
•
karena sumber daya yang terbagi: [yang] bersamaan memperbaharui– arsip di
(dalam) suatu database ( [record/
catatan] mengunci)
–
file (
kunci file di (dalam) file server tak berkewarganegaraan)
–
suatu
buletin bersama yang diberitahu
• untuk
bermufakat melakukan tindakan: apakah untuk
–
commit/abort
transaksi database
–
bermufakat
untukmelakukan suatu pengenalan dari suatu kelompok sensor
• untuk
dengan dinamis re-assign peran guru
–
memilih
server waktu utama setelah roboh/hancur
–
memilih koordinator setelah bentuk/ wujud jaringan kembali
Kenapa
sulit?
• Solusi Centralised tidak sesuai
–
komunikasi
bottleneck
• Master-Slave yang ditetapkan memperbaiki
Pengaturan yang tidak sesuai
–
proses
kehancuran
• Macam-Macam topologi jaringan
–
[cincin/arena],
pohon, sewenang-wenang dan permasalahan yang saling berhubungan
• Jika mungkin, kegagalan harus dimaklumi
–
kegagalan
mata rantai
–
proses kehancuran
• Ketidakmungkinan akan menghasilkan
– kegagalan di dalam kehadiran, esp model yang
tak serempak
Permasalahan Koordinasi Melihat[ Membunuh
beramai-ramai 1996] untuk lebih detil.
• Pengeluaran timbal balik
–
format
yang didistribusikan dari bagian permasalahan yang kritis
–
harus
menggunakan pesan yang telah lewat
• Pemilihan Pemimpin
–
setelah
roboh/hancur kegagalan telah terjadi
–
setelah
bentuk/wujud jaringan kembali
• Konsensus ( juga disebut Persetujuan): yaitu
ceramah kuliah berikutnya
–
serupa
untuk mengkoordinir serangan
–
beberapa
berdasarkan pada multicast komunikasi
–
varian yang tergantung pada jenis kegagalan, jaringan, dll
Asumsi Kegagalan mengasumsikan mata rantai
yang dapat dipercaya, tetapi prosesnya mungkin mengalami kehancuran.
• [Jasa;Layanan] Pendeteksian Kegagalan
–
menyediakan
query jika suatu proses telah gagal
–
bagaimana?
• proses mengirimkan ‘ P di sini’ merupakan
pesan T per tiap-tiap detik
•
jawaban dari arsip detektor kegagalan
– tak dapat dipercaya, terutama di dalam
sistem yang tak serempak
• Pengamatan atas kegagalan:
–
Yang
dicurigai: tidak ada komunikasi terbaru, tetapi bisa melambat
–
Yang tak
dicurigai: tetapi tidak ada jaminan bahwa sejak itu belum digagalkan
– Yang digagalkan: hancurnya telah ditentukan
Pengeluaran timbal balik yang dibagi-bagikan
• Masalah:
–
N proses
yang tidak sama, karena kesederhanaan tidak mempunyai kegagalan
–
penyerahan pesan yang dijamin ( mata rantai yang dapat dipercaya)
– untuk melaksanakan bagian kritis ( CS), yang
masing-masing proses tersebut adalah:
• masuk()
• resourceAccess()
• keluar()
•
Kebutuhan ( MC1) Paling banyak ada satu proses dalam CS yang dilakukan pada
waktu yang sama.
(MC2) Permintaan untuk masuk dan keluar harus
secepatnya dilakukan.
(MC3- Opsional, lebih kuat) Permintaan untuk
masuk dilakukan menurut pesanan yang mempunyai hubungan sebab akibat.
Pemusatan dalam pengeluaran yang berhubungan
timbal balik Pemusatan dalam pelayanan?
• Server tunggal mengimplementasi tanda khayal
–
hanya proses memegang tanda itu yang dapat dilakukan CS
–
server
menerima permintaan untuk tanda
–
akses
akan mengabulkan jawaban jika CS
cuma-cuma; atau dengan cara meminta queued
–
ketika
suatu proses melepaskan tanda, permintaan paling tua dari antrian akan
dikabulkan
•
meskipun demikian...
– tidak menghormati order yang memiliki
hubungan sebab akibat dari permintaan (MC3) mengapa?
• tetapi
– server adalah pencapaian dari bottleneck!
– apa akibatnya jika server tersebut hancur?
Algoritma Ring-based prosesnya disusun didalam
suatu cincin logis, yang membiarkan mereka melewati tanda.
• Tidak ada server bottleneck, tidak ada guru Proses:
– secara terus menerus tanda
lewat di sekitar [cincin/arena], dalam satu arah
–
jika
tidak memerlukan akses untuk CS, lewat ke atas tetangga
–
cara
lainnya, nantikan tanda dan pertahankannya selagi dalam CS
– untuk pergi, memberikan . pada tetangga
• Bagaimana [itu] bekerja
–
penggunaan
lebar jalur jaringan berlanjut
–
menunda
untuk masuk tergantung pada ukuran [cincin/arena]
–
order yang memiliki hubungan sebab akibat dari permintaan yang tidak
sesuai
( MC3) - mengapa?
Ricart&Agrawala Algoritma
• Multicast yang didasarkan pada Komunikasi
– proses inter-connected N yang
tidak terjadi bersamaan, dengan masing-masingnya
• identitas yang unik
• waktu Lamport’S yang logis
– proses multicast untuk meminta masuk:
• timestamped dengan waktu Lamport’S dan
proses identitas
– memasuki untuk dikabulkan
• ketika semua proses yang lain menjawab
• permintaan bersama memecahkan dengan
timestamp
• Bagaimana [itu] bekerja
– membuat baik [properti/milik] yang lebih
kuat ( MC3)
– jika perangkat keras mendukung
untuk multicast, hanya satu pesan yang masuk
Ricart&Agrawala Algoritma Pada status
initialisasi:= YANG DILEPASKAN; Untuk memasuki status bagian yang kritis:= YANG
DIINGINKAN; Multicast meminta kepada semua proses; proses permintaan yang
ditunda T:= request’s timestamp; Menunggu sampai ( jumlah jawaban yang
diterima= ( N– 1)); status:= YANG DIPEGANG; Sesudah menerima suatu permintaan
< Ti, Pi (22:7)> pada pj ( i ?? j)
jika(tate = HELD) atau ((state = WANTED) dan
((T, pj) < (Ti, pi))
then queue request from pi without replying;
else reply immediately to pi; end if To exit the critical section state :=
RELEASED; reply to any queued requests;
kemudian
menunngu permintaan dari pi (22:7) tanpa menjawab; seketika jawaban itu akan
muncul ke pi (22:7); berakhir; jika status bagian yang kritis keluar:= YANG
DILEPASKAN; menjawab setiap permintaan
queued;
Multicast pengeluaran timbal balik p1, p2
meminta akses [yang] secara bersamaan, p3 tidak dapat melakukan pengaksesan.
p2 tidak menjawab ke p1 karena mempunyai
timestamp yang rendah Ringkasan Pengeluaran timbal balik
• Penampilan
– satu sudah cukup untuk masuk
–
pemakaian
lebar jalur jaringan yang tinggi
–
penundaan klien tergantung pada frekwensi akses dan ukuran jaringan
• Toleransi
pada Kesalahan
–
pada
umumnya mengasumsikan mata rantai yang dapat dipercaya
–
Beberapa, dapat beradaptasi untuk berhadapan dengan kehancuran
• Lain solusi
– cukup
untuk memperoleh persetujuan dari overlap subsets tertentu dari proses yang memilih di-set ( Maekawa Algoritma)
6.2.3 Algoritma
Pemilihan Pemimpin
• Masalah
– Proses N, boleh atau tidak boleh mempunyai
id yang unik ( UIDS)
–
untuk
kemudahan mengasumsikan tidak ada apapun yang hancur
–
harus
memilih koordinator guru unik selama proses
–
pemilihan
dilakukan setelah kegagalan telah terjadi
–
satu
atau lebih proses dapat melakukan pemilihan yang secara bersamaan
•
Kebutuhan ( LE1) Tiap-Tiap proses mengetahui P, identitas pemimpin, di mana P
adalah orang yang tak punya proses id yang unik ( pada umumnya maksimum) atau
yang tak tergambarkan.
( LE2) Semua proses mengambil bagian dan
secepatnya menemukan identitas pemimpin ( tidak bisa tak tergambarkan).
Chang&Roberts Pemilihan Pemimpin algoritma
di dalam arena: model tidak bersamaan, yang dikenal sebagai UIDS.
Chang&Roberts algoritma
• Asumsi
– cincin
arena yang searah, tak serempak, masing-masing proses mempunyai UID
• Pemilihan
–
pada
awalnya masing-masing proses bukanlah
peserta
–
menentukan
pemimpin ( pesan pemilihan):
• pemrakarsa menjadi peserta dan melewati
kepunyaan UID kepada tetangga
•
ketika tidak peserta menerima pesan
pemilihan, teruskan dengan maksimum pada kepunyaan dan UID yang diterima dan
menjadi peserta
• peserta tidak meneruskan pesan pemilihan itu
–
mengumumkan pemenang ( pesan yang dipilih):
• ketika
peserta menerima pesan pemilihan dengan kepunyaan UID, menjadi pemimpin
dan bukan peserta, dan lanjutkan UID dalam
pesan yang dipilih
• cara
lainnya, arsip leader’s UID, menjadi
bukan peserta dan lanjutkan itu
Chang&Roberts algoritma
• Bagaimana [itu] bekerja
–
jika
UIDS, kemudian identitas dari pemimpin yang unik
–
dua
pertukaran di sekitar [cincin/arena]: pemilihan, mengumumkan pemenang
–
jika
satu proses memulai pemilihan
• dalam
kasus yang terburuk 3 round-trips akan diperlukan- jelaskan?
•
tetapi– tidak memaklumi kegagalan (memerlukan detektor kegagalan yang dapat
dipercaya)
• lihat algoritma yang terbaik ( synchronous
model)
•
bekerja jika lebih dari satu proses [yang] secara bersamaan memulai pemilihan–
apa akibatnya jika tidak (ada) UIDS?
• persetujuan pada suatu jaringan
re-configurable, ‘ hot-pluggable’
Itai&Rodeh Algoritma
• Asumsi
–
Proses
N, cicin arena tidak searah, synchronous
–
proses
tidak mempunyai UIDs
• Pemilihan
– setiap proses memilih ID secara acak dari
set { 1,..K}
–
proses
melewati semua IDs di sekitar [cincin/arena]
–
setelah
satu putaran, jika di sana ada suatu ID yang unik kemudian pilihlah ID unik
yang maksimum
–
cara
lainnya, mengulangi
• Pertanyaan
– bagaimana cara mengakhiri putarannya?
Itai&Rodeh Algoritma
• Bagaimana cara mengetahui algoritma
berakhir?
–
dari
kemungkinan: jika kamu melemparkan suatu koin dengan adil kemudian setelah
beberapa kepala- kamu harus mendapatkan ekor
• Berapa banyak putaran yang dikerjakan?
–
kemungkinan
yang paling besar dari ID yang unik, yang lebih cepat algo
– waktu yang diharapkan: N=4, K=16,
mengharapkan 1.01 putaran
• Mengapa
menggunakan randomisasi?
–
perusak/interuptor
simetri
–
solusi
cepat
• tetapi hanya probabilistic ( dengan
kemungkinan 1) jaminan untuk berhenti FIREWIRE IEEE 1394 pohon mengidentifikasi
• Asumsi
–
tak
satu [cincin/arena] pun : jaringan
acyclic
–
hot-pluggable,
maka tidak (ada) UIDS selama pohon mengidentifikasi
–
harus
memilih suatu koordinator ( untuk bertindak sebagai bus manajer) setelah
masing-masing keputusan ditambahkan/ diubah
• Bagaimana caranya bekerja?
–
jaringan
acyclic- hampir suatu pohon
–
mulai
dengan daun-daun: mengirimkan ‘ jadilah orangtua ku’ pesan ke tetangga
–
tangkai pohon yang menerima N-1 Permintaan ( N adalah banyaknya tetangga), mengirimkan ‘ jadilah orangtua ku’ kepada tangkai pohon yang sisanya
• Pertanyaan: akankah itu menentukan akarnya?
Akar Gagasan Permasalahan
• Masalah
– dua
tangkai pohon boleh secara bersamaan mengirimkan pesan ‘ jadilah orangtua ku’
Untuk satu sama lain!
• Solusi
–
masing-masing
penantang menghempaskan suatu koin, kemudian memilih memilih penundaan yang
pendek/singkat atau lama
–
setelah
penundaan, jika itu telah menerima ‘ jadilah orangtua ku’ itu menjadi akar
–
cara lainnya, mengirimkan kembali ‘ jadilah orangtua ku’
– jika permasalahan timbul kembali, proses
mengulangi
Ringkasan
• Algoritma yang didistribusikan
–
lebih
peka untuk terjadi kehancuran
–
pesan
yang berdasarkan pada yang disampaikan
• memakai lebar jalur jaringan
• Randomisasi
–
bermanfaat
sebagai perusak/interuptor simetri
–
menghasilkan
algoritma lebih cepat dan lebih sederhana
–
tetapi penghentian probabilistic terjamin
Sinkronisasi adalah Adalah satu kunci kerja
dari komunikasi data. Transmiter mengirimkan pesan 1 bit pada satu saat melalui
medium ke receiver. Receiver harus menandai awal dan akhir blok dari bit, juga
harus diketahui durasi untuk masing-masing bit sehingga dapat sample lajur dari
timing untuk membaca masing-masing bit (merupakan tugas dari timming).
Contoh : jika ada perbedaan misalkan 1 % (clock
receiver 1% lebih lambat atau lebih cepat daripada clock transmitter), maka
pada pensamplingan pertama akan meleset dari tengah bit dan setelah jumlah
waktu tertentu, akan mengalami error.
Sinkronisasi di bagi menjadi 2, yaitu :
1. Asynchronous
Untuk mencegah problem timming dengan tidak mengirim aliran bit panjang yang
tidak putus putusnya. Bit-bit dikirim per-karakter pada setiap waktu yang mana
masing-masing karakter mempunyai panjang 5-8 bit. Timing atau synchronisasi
harus dipertahankan antara tiap karakter; receiver mempunyai kesempatan untuk
men-synchron-kan awal dari tiap karakter baru.
- Idle (biasanya =‟1‟) jika tidak ada karakter yang
ditransmisikan dan start bit = “0”, sedangkan jumlah karakter yang
ditransmisikan antara 5-8 bit.
- Bit paritas digunakan untuk mendeteksi error, diatur
oleh pengirim agar jumlah total „1‟ termasuk bit paritas adalah genap, dan
stop bit = „1‟, yang panjangnya 1; 1,5; 2 kali durasi bit pada umumnya
- Komunikasi asinkron adalah sederhana dan murah, tetapi
memerlukan overhead dari 2 ke 3 bit per karakter, prosentasi overhead
dapat dikurangi dengan mengirimkan blok-blok bit besar antara bit start
dan bit stop
2. Synchronous
/ timing
Lebih efisien, karena blok-blok
karakter / bit-bit ditransmisikan tanpa kode start dan stop, tetapi tiap blok
blok dimulai dengan suatu pola preamble bit dan diakhiri dengan pola postamble
bit. Pola-pola ini adalah kontrol informasi.Waktu kedatangan dan keberangkatan
untuk masing-masing bit dapat diramalkan. Frame adalah data plus kontrol
informasi. Format framenya tergantung dari metode transmisi, yaitu:
1. Transmisi
orientasi karakter
- Blok-blok data dikerjakan sebagai barisan karakter
(biasanya 8 bit karakter), frame dimulai dengan 1 atau lebih karakter
sinkronisasi. Karakter sinkronisasi biasanya disebut dengan “SYN” yang
merupakan bit pattern unik sinyal yang diterima penerima permulaan dari
blok.
- Penerima kemudian merubah blok-blok data yang datang
oleh karakter SYN dan menerima data sampai karakter postamble (informasi
yang terletak pada bagian belakang blok data yang dikirimkan) terlihat dan
begitu seterusnya
2. Transmisi bit.
- Blok-blok data dikerjakan sebagai barisan bit-bit, tidak ada
data maupun informasi kontrol diperlukan untuk menginter-prestasikan dalam
satuan karakter 8 bit
- Untuk blok-blok data yang cukup besar, transmisi sinkronisasi
jauh lebih efisien daripada asinkron. Transmisi asinkron memerlukan
overhead 20 % atau lebih.
- Bila menggunakan transmisi sinkron biasanya lebih kecil dari
1000 bit, yang mengandung 48 bit kontrol informasi (termasuk flag), maka
untuk pesan 1000 bit, overheadnya adalah 48 / 1048 X 100% = 4.6%
Urutan pengerjaan sinkronisasi yaitu :
- Sinkronisasi bit: Ditandai awal & akhir untuk
masing-masing bit
- Sinkronisasi karakter / kata: Ditandai awal dan akhir untuk
masing-masing karakter / satuan kecil lainnya dari data
- Sinkronisasi blok / pesan :Ditandai awal dan akhir dari satuan
besar data. Dan untuk pesan yang besar, dibagi-bagi menjadi beberapa blok
kemudian baru dikirimkan pengurutan blok-blok yang telah dibagi tersebut
adalah tugas dari timming. Sedangkan pengaturan level sinyal adalah tugas
dari sintax dan untuk melihat arti dari pesan adalah tugas dari semantik.
o
Sinkronisasi yang terjadi pada CPU yaitu:
Merupakan salah satu cara komputer
mengkoordinir kegiatannya dg peralatan input dan ouput yg dihubungkan
kepadanya. Pada program-controlled Input dan Ouput:
Prosesor terus-menerus memeriksa status flag setiap peralatan Input dan Ouput
untuk mencapai sinkronisasi antara prosesor dan Input dan Ouput device.
o
Interrup
Digunakan untuk meningkatkan kinerja processor
dalam penanganan peralatan Input dan Ouput yang dimilikinya. CPU tidak harus
selalu mengecek status peralatan Input dan Ouput. Bila terdapat peralatan Input
dan Ouput yang meminta pelayanan, maka peralatan tersebut akan mengirim sinyal
interrupt kepada CPU. Sinyal interrupt ini disebut juga sebagai Interrupt
Request .Sinyal interrupt dikirim melalui jalur kontrol bus yang disebut
interrupt request line. Processor akan merespon interrupt yang diterima dengan
menghentikan proses yang sedang berjalan dan mengecek status peralatan Input
dan Ouput untuk mencari peralatan yang meminta interrupt. Selanjutnya processor
akan menjalankan suatu program untuk merespon interrupt yang diterimanya.
Program ini disebut sebagai interrupt-service routine (ISR). Berikut contoh processor
dalam menjalankan ISR untuk merespon interrupt pencetakan ke printer.
Opsi ini menunjukkan bagaimana proses input dan
output ke filesystem dilakukan. sinkornisasi berarti dilakukan secara
sinkronisasi. Contohnya digunakan pada floopy, artinya ketika anda menyalin
sebuah file ke floopy, perubahan secara fisik langsung ditulis ke floppy saat
anda memberikan perintah copy
Jika anda menggunakan opsi async, input dan
output dilakukan secara asinkronisasi. Dengan contoh diatas, opsi ini membuat
proses penyalinan ke floopy mungkin dilakukan jauh setelah perintah copy anda
berikan. Hal ini tidaklah buruk, bahkan terkadang menjadi pilihan, dikarenakan
misalnya jika anda memindahkan floopy tanpa melakukan unmounting terlebih
dahulu, file-file yang disalin mungkin secara fisik belum masuk ke dalam floopy
tersebut.
§ http://ebookbrowse.com/rancang-bangun-sistem-pengukuran-terdistribusi-berbasis-jaringan-multidrop-rs-485-daftar-pustaka-pdf-d325997191
§ Ferdian
Pramudya P (32582) ,Agung kaharesa W (32649) ,Jurusan Teknik Elektro FT UGM,
Yogyakarta
§ http://fachrurozhi-inf-usk.
/2012/02/sinkronisasi-dan-asinkronisasi.html
