perkuliahan setelah uts pengantar teknologi sim...

SISTEM TERDISTRIBUSI (4KA)

MATERI 7

APA ITU TIME AND COORDINATION ?

2 Sistem Terdistribusi (4KA)

• Time And Coordination adalah mengkordinasikan

waktu dalam transfer data, agar tidak terjadi

ketimpangan pada proses transfer data

• Berguna untuk mengukur penundaan antara

komponen terdistribusi

• Menyinkronkan aliran data misalnya : suara dan

video

• Sebagai penanda keakuratan waktu untuk

mengidentifikasi atau mengotentikasi transaksi

bisnis dan serializability dalam database

terdistribusi dan keamanan protocol


Time

Time adalah sistem komputasi interaktif, dimana sistem

komputer menyediakan komunikasi on-line antara user

dengan sistem. User memberikan instruksi pada sistem

operasi atau program secara langsung dan menerima

respon segera

Coordination

Coordination adalah 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


CONTOH KASUS COORDINATION

• 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)


Clock (Jam)

Setiap komputer pasti memiliki clock fisik. Clock adalah alat

elektronik yang menghitung osilasi yang terjadi pada kristal pada

frekuensi tertentu, dan menyimpannya dalam counter register

Clock milik tiap-tiap komputer tidak selalu sama. Perbedaan

antara pembacaan dua clock komputer berbeda disebut Skew

Clock Drift Rate adalah perubahan perbedaan pembacaan

antara clock dan perfect reference clock (clock yang dijadikan

acuan)

Coordinated Universal Time (UTC) adalah standar

internasional untuk penjagaan waktu (timekeeping)

LOGICAL CLOCK & SYNCHRONISATION


Logical Clock

Logical clock adalah software counter yang bertambah

secara monoton dimana nilainya tidak perlu

menanggung hubungan tertentu ke suatu physical clock

Hampir seluruh komputer memiliki sebuah circuit untuk

menunjukkan waktu. Pada kenyataannya circuit tersebut

bukanlah penunjuk waktu (jam) yang sebenarnya. Kata

yang tepat untuk mendeskripsikan circuit tersebut

adalah timer. Timer pada suatu komputer pada

umumnya merupakan suatu crystal quartz yang

termekanisasi


Synchronization

Adalah proses pengaturan jalannya beberapa

proses pada saat yang bersamaan

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

SINKRONISASI CLOCK


• Sinkronisasi Clock adalah suatu masalah pada computer science

mengenai perbedaan waktu pada beberapa komputer atau sistem.

Semua komputer memiliki rangkaian pencatat waktu (clock). Selalu

ada sedikit perbedaan yang terjadi dan mengakibatkan perbedaan

waktu pula yang disebut clock skew

• Untuk mengatasi perbedaan waktu tersebut ada beberapa algoritma

yang telah dikembangkan untuk digunakan dalam sinkronisasi clock,

yaitu : Algoritma Lamport, Algoritma Christian, Algoritma Berkeley

• Algoritma untuk sinkronisasi dalam sistem terdistribusi memiliki

beberapa sifat : Informasi yang relevan tersebar di beberapa komputer,

Keputusan pembuatan proses hanya berdasarkan informasi local,

Peristiwa kegagalan dengan penyebab tunggal di dalam sistem harus

dihindarkan, tidak tersedianya clock atau sumber waktu global yang

akurat


Sikronisasi merupakan bagian penting untuk kerjasama dalam :

Pemakaian sumberdaya berbagi (Sharing resources), Pengurutan

kejadian, kesepakatan clock tersebar. Gambar dibawah

menggambarkan bahwa bila waktu pada output adalah 2144,

Kemudian source codenya dimodifikasi di komputer lain yang

clocknya lebih lambat, sehingga waktu source code adalah 2143

Karena source code memiliki waktu yang lebih lama daripada file

objeknya, maka make tidak akan melakukan rekompilasi

ALGORITMA LAMPORT


Menurut Lamport, sinkronisasi clock tidak harus dilakukan

dengan nilai mutlak clocknya, karena yang diperlukan

dalam sikronisasi proses-proses adalah urutan proses

tersebut. Jadi yang dipentingkan adalah konsistensi internal

clock, bukan apakah clock tersebut harus sama persis

dengan waktu real. Clock jenis ini biasanya disebut clock

logika

Syarat : Perlu pengurutan kejadian untuk sembarang

pasangan kejadian, tidak boleh ambigu, harus diketahui

keterdahuluan kejadian

Solusi : Penerapan algortima Lamport untuk pengurutan

kejadian. Penggunaan stempel waktu untuk proses

ALGORITMA CHRISTIAN


Suatu algoritma yang menganggap suatu mesin sebagai time server. Semua

mesin akan menanyakan waktu yang tertera pada time server tersebut.

Mesin tersebut (time server) kemudian merespon dengan waktu yang

sesingkat-singkatnya dengan mengirimkan pesan berisi waktu pada saat itu

(C UTC). Pada saat pengirim pesan menerima jawaban (reply) maka mesin

tersebut dapat menset waktu menjadi C UTC. Kelemahan : waktu tidak

boleh berjalan mundur, dibutuhkan waktu untuk mengirimkan balasan dari

time server

ALGORITMA BERKELEY


Algoritma Berkeley digunakan untuk mensinkronkan clock relatif

terhadap clock lainnya, dan bukan terhadap master clock tertentu.

Pada algoritma Berkeley, time server bersifat aktif. Time server akan

melakukan polling pada setiap mesin secara berkala dan menanyakan

waktu pada tiap mesin. Berdasarkan jawaban yang diberikan, time

server mengkomputasi dan memberikan perintah untuk mempercepat

atau memperlambat waktu

PROSES KOORDINASI PADA SISTEM TERDISTRIBUSI


Sistem tedistribusi memungkinkan kita untuk saling

mengkoordinasikan dan saling bekerja sama dalam

melakukan aktifitas secara lebih efisien dan lebih efektif.

Tujuan utama dari system terdistribusi dapat

direpresentasikan dengan : resource sharing, openness,

concurrency, scalability, fault-tolerance dan transparency

Proses koordinasinya :

• Dijalankan secara bersamaan (Execute Concurrently)

• Interaksi untuk bekerjasama dalam mencapai tujuan yang

sama

• Mengkoordinasikan aktifitas dan pertukaran informasi

yaitu pesan yang dikirim melalui jaringan komunikasi

AKTIVITAS KOORDINASI TERDISTRIBUSI


Pengurutan Event

Dalam manajemen koordinasi proses pada sistem tersentralisasi

memungkinkan untuk menentukan urutan kejadian, sebab hanya

terdapat satu memori dan clock. Sejumlah aplikasi sangat

menekankan urutan, misal : alokasi resource, resource dapat dipakai

setelah resource tersebut dipesan dan dijamin bebas. Manajemen

koordinasi antar proses pada sistem terdistribusi untuk menentukan

urutan kejadian tidak semudah seperti sistem tersentralisasi, karena

pada sistem terdistribusi parameter yang diperhatikan lebih komplek,

yaitu :

• Memori & clock tidak tunggal

• Tidak mungkin menyatakan urutan dua kejadian

• Hanya dapat ditentukan partial ordering (urutan bagian)

RELASI HAPPENED-BEFORE


• Relasi Happened-Before adalah suatu relasi yang

memperhatikan urutan kejadian, karena kejadian yang

satu dengan yang lain saling terkait. Pada Relasi

Happened-Before berlaku :

a. Proses-proses sekuensial, proses sekuensial adalah

semua kejadian dijalankan oleh satu pemroses

(Total Ordering)

b. Hukum sebab-akibat, hukum sebab-akibat adalah

suatu kejadian dimana pesan dapat diterima setelah

pesan tersebut dikirimkan

c. Simbol relasi happened-before : →


Sejumlah kejadian dapat dikelompokkan dalam relasi Happened-

Before sebagai berikut :

• Jika kejadian A & B berada dalam satu proses dan A dieksekusi

sebelum B, maka ditulis A → B

• Jika A adalah kejadian pengiriman pesan (sending) oleh sebuah

proses dan B adalah sebuah kejadian penerima pesan (receiving)

oleh proses lain, maka ditulis A → B (sending dilakukan sebelum

receiving)

• Jika A→B dan B→C, maka A→C Karena suatu event tidak dapat

terjadi sebelum dirinya sendiri terjadi, maka relasi happened-

before tidak bersifat refleksi (dipasangkan ke dirinya sendiri)

• Jika 2 event A & B tidak memenuhi Relasi → R (A tidak terjadi

sebelum B & B tidak terjadi sebelum A), maka kedua event

tersebut dieksekusi bersamaan (concurent). Dalam artian kondisi

kedua event tersebut tidak dapat saling mempengaruhi. (A→B :

ada kemungkinan A mempengaruhi B)

MUTUAL EXCLUSION


Mutual exclusion adalah jaminan hanya satu proses yang

mengakses sumber daya pada satu interval waktu tertentu.

Sumber daya yang tidak dapat dipakai bersama pada saat

bersamaan

Ada model pendekatan dalam mutual exclusion yaitu :

a. Pendekatan Tersentralisasi (Centralized)

• Salah satu proses dipilih sebagai koordinator untuk

mengatur entri ke CS

• Menggunakan pesan request-reply-release untuk masuk ke

CS

• (+) : Menjamin mutex, dapat menjamin fairness (no

starvation)

• (--) : Jika koordinator gagal → perlu dipilih kembali


b. Pendekatan Terdistribusi Penuh (Fully Distributed)

• Untuk masuk ke CS, proses mengirimkan pesan request (Pi,

TS) ke semua proses

• Pengiriman reply oleh Pi ke Pk :

• Jika Pi sedang berada di CS, reply ke Pk ditunda

• Jika Pi tidak akan masuk ke CS, reply langsung dikirim ke

Pk

• Jika Pi akan masuk ke CS dan TS(Pi) < TS(Pk) maka reply

ke Pk ditunda

• (+) : Menjamin mutex, bebas deadlock dan starvation

• (--) : Jumlah pesan minimum 2(n-1), proses harus tahu

identitas semua proses lain, tidak berfungsi jika ada proses

yang gagal, mengganggu proses lain yang tidak akan

masuk ke CS


c. Pendekatan Token Passing

• Menggunakan satu token yang beredar diantara

proses

• Hanya proses yang memiliki token saat itu yang

dapat masuk ke CS

• Syarat : Adanya lingkaran lojik yang

menghubungkan semua proses

• (+) : Menjamin mutex, bebas starvation

• (--) : Jika token gagal → perlu digenerate kembali,

jika proses gagal → perlu dibentuk ring lojik baru


ATOMISITAS

Tiap situs memiliki koordinator transaksi yang berfungsi menjamin atomisitas

eksekusi transaksi, dengan cara :

• Memulai eksekusi transaksi

• Memecah menjadi beberapa sub-transaksi dan mendistribusikannya pada situs-

situs yang cocok untuk dieksekusi

• Mengkoordinasikan terminasi transaksi (commit, atau abort)

• Tiap situs menyimpan log untuk tujuan recovery

PROTOKOL TWO-PHASE COMMIT (2PC)

Semua situs yang mengeksekusi transaksi T harus memiliki hasil akhir yang sama

(commit atau abort) Jika T adalah transaksi yg diinisiasi pada situs Si dengan

koordinator Ci, maka setelah transaksi selesai Ci memulai protokol 2PC :

• Fase 1 : Ci mengirimkan pesan ke semua situs yang mengeksekusi T untuk

mengetahui transaksi commit atau abort

• Fasea2a: Ci menentukan hasil akhir transaksi setelah menerima respon dari

semua situs; transaksi commit jika semua situs memberi respon commit


PROTOKOL TWO-PHASE COMMIT (2PC)

Penanganan Kegagalan pada 2PC

Kegagalan pada salah satu situs yang berpartisipasi

•Masalah : situs yang selesai melakukan recovery harus memeriksa log

untuk menentukan status transaksi

• Jika commit, situs melakukan redo (T)

• Jika abort, situs melakukan undo (T)

Kegagalan pada koordinator

•Masalah : situs yang berpartisipasi harus menentukan nasib T

• Jika salah satu situs berisi record maka coordinator akan mengikuti

hasilnya

• Jika ada situs yang belum berisi maka koordinator tidak dapat

memutuskan

Kegagalan pada jaringan

•Masalah : pesan yang dikirimkan tidak sampai

• Jika beberapa link terputus dapat dilakukan partisi jaringan

CONCURRENCY CONTROL


Manajer transaksi berfungsi mengelola eksekusi transaksi yang mengakses data.

Menyimpan log untuk tujuan recovery, berpartisipasi dalam skema kontrol-

konkurensi untuk mengkoordinasi eksekusi transaksi

Protokol Locking

Skema nonreplikas

Tiap situs memiliki satu manajer lock lokal untuk mengelola permintaan

lock/unlock data yang disimpan pada situs tersebut

(+) : sederhana

(--) : penanganan deadlock lebih rumit karena tidak ditangani oleh satu situs

Pendek atau Koordinator Tunggal

Ada manajer lock tunggal yang berada pada salah satu situs untuk menangani

permintaan lock/unlock data

• Read dapat dilakukan pada situs mana saja yang menyimpan data

• Write dilakukan pada semua replikasi


Protokol Mayoritas

Tiap situs memiliki lock manajer yang mengelola data

dan duplikat data yang disimpan pada situs tersebut

• Lock manajer menentukan lock yang dapat diberikan

• Transaksi terhadap data tidak dimulai sebelum kunci

dari mayoritas replika diperoleh

(+) : penanganan terdesentralisasi

(--) : penanganan deadlock perlu modifikasi, rumit

PENANGANAN DEADLOCK


Deadlock Prevention

Pencegahan : Faktor-faktor penyebab deadlock yang harus

dicegah untuk terjadi

4 faktor yang harus dipenuhi untuk terjadi deadlock :

• Mutual Exclusion : Pemakaian resources

• Hold and Wait : Cara menggunakan resources

• No preemption resource : Otoritas/hak

• Circular wait : Kondisi saling menunggu.

Jika salah satu bisa dicegah maka deadlock pasti tidak

terjadi


Deadlock Detection

Mencegah dan menghidari dari deadlock sulit dilakukan :

• Kurang efisien dan utilitas sistem

• Sulit diterapkan : tidak praktis, boros resources

• Mengizinkan sistim untuk masuk ke “state deadlock”

• Gunakan algoritma deteksi (jika terjadi deadlock)

Deteksi : Melihat apakah penjadwalan pemakaian

resource yang tersisa masih memungkinkan berada dalam

safe state (variasi “safe state”)

Skema recovery untuk mengembalikan ke “safe state”

ALGORITMA PEMILIHAN


Algoritma Bully

Adalah (Gracia-Moliana 1982) algoritma yang mengijinkan proses

mengalami crash pada saat terjadi pemilihan (election), meskipun

pengiriman pesan antar proses adalah reliable

Ada tiga tipe pada algoritma ini, yaitu :

• Election Message : Digunakan untuk pemberitahuan akan adanya

pemilihan

• Answer Message : Merupakan jawaban dari election message

• Coordinator Message : Digunakan untuk memberitahukan

identitas dari proses pemilihan

Algoritma Ring

Tujuan dari algoritma ini adalah untuk memilih sebuah proses tunggal yang

disebut koordinator, yang merupakan proses dengan identifier terbesar

PERBEDAAN MODEL SINKRONISASI DAN ASINKRONISASI


• Sinkron yaitu : sebelum seluruh proses transaksi update

dinyatakan selesai, data yang telah dimodifikasi

disinkronkan ke setiap duplikatnya; proses ini harus

menunggu hingga data di tempat penyimpanan duplikat

selesai ditulis sebelum dilakukan perubahan lainnya

sehingga menjadi lebih kompleks

• Asinkron yaitu : copy data diperbaharui secara periodik

berdasarkan data utama yang diperbaharui; proses

penulisan data selesai tanpa perlu menunggu penulisan

data di tempat penyimpanan duplikat selesai; proses ini

memang meningkatkan kinerja sistem namun risikonya,

inkonsistensi data bisa terjadi

TERIMA KASIH

perkuliahan setelah uts pengantar teknologi sim...

Documents