rangkuman sister 3b

Time and Global State

TIME AND GLOBAL STATE Arif Herusetyo W – 33003

Ircham Ardani – 33125

Tulus Hamdani - 33507

Jurusan Teknik Elektro FT UGM,

Yogyakarta

1. PENDAHULUAN

Bab ini membahas tentang konsep dan algoritma pemrograman yang berhubungan

dengan monitoring sistem terdistribusi dan pewaktuan eksekusi yang terjadi. Waktu adalah hal

yang penting dalam sistem terdistribusi karena beberapa hal. Pertama, waktu adalah satuan

akurasi. Untuk mengetahui kapan suatu peristiwa terjadi, dibutuhkan sinkronisasi clock pada

sistem dan di luar sistem. Sebagai contoh, transaksi e-commerce terjadi di komputer pengguna

dan komputer bank. Kejadian tersebut haruslah dicatat waktunya secara akurat untuk keperluan

audit. Kedua, algoritma mengenai sinkronisasi clock memiliki beberapa masalah, antara lain

mempertahankan konsistensi data yang didistribusikan, otentikasi request yang dikirim ke server,

dan menghapus proses yang terduplikasi.

Jika dianalogikan, seperti teori relativitas milik Einstein. Suatu kejadian yang diamati

oleh pengamat yang satu bisa saja berbeda dengan pengamat lainnya dalam hal interval (jeda)

waktu. Dalam sistem terdistribusi, masalahnya adalah mencatat waktu terjadinya suatu kejadian

pada node yang berbeda-beda secara akurat sehingga dapat diketahui mana yang hanya terjadi

dan mana yang terjadi secara serempak.

2. PEMBAHASAN

2.1 Clock, Kejadian, dan Process State

2.1.1 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. Sistem operasi membaca clock fisik tersebut dan menerjemahkannya ke software clock.

Software clock tidak selalu akurat sehingga pewaktuan hardware dan software memiliki

perbedaan walaupun sangat kecil. Namun, software clock tetap menjadi acuan pencatatan waktu

setiap kejadian proses. Kejadian yang terjadi setelah suatu kejadian akan tercatat di waktu yang

berbeda apabila resolusi clock (periode update software clock) lebih kecil daripada interval

waktu antar kejadian.


2.1.2 Clock Skew dan Clock Drift

Gambar 1 Skew antar clock komputer dalam sistem terdistribusi

Clock milik tiap-tiap komputer tidak selalu sama. Perbedaan antara pembacaan dua clock

komputer berbeda disebut skew. Sedangkan perbedaan clock rate disebut clock drift. Pada clock

fisik, osilasi, frekuensi, dan temperatur mempengaruhi perbedaan clock tiap komputer.

Perbedaannya mungkin sangat kecil, tetapi akumulasi perbedaan tersebut dapat mencapai tahap

yang bisa diamati dengan mata telanjang walaupun sudah disamakan nilainya. Clock drift rate

adalah perubahan perbedaan pembacaan antara clock dan perfect reference clock (clock yang

dijadikan acuan).

2.1.3 Waktu Universal Terkoordinasi (Coordinated Universal Time)

Clock komputer dapat disinkronkan dengan clock luar yang akurasinya tinggi. Clock yang

akurasinya paling tinggi menggunakan osilator atom. Keluaran clock ini digunakan sebagai

standar waktu international. Coordinated Universal Time (UTC) adalah standar internasional

untuk penjagaan waktu (timekeeping). Sinyal UTC disiarkan dari stasiun radio dan satelit ke

seluruh dunia. Komputer dengan penerima sinyal di seluruh dunia dapat mensinkronkan clock-

nya dengan sinyal ini.

2.2 Sinkronasi Clock Fisik

Untuk mengetahui kapan sebuah peristiwa terjadi secara akurat pada proses sistem

terdistribusi, diperlukan sinkronisasi dengan sumber waktu dari luar, yang disebut sinkronisasi

eksternal (external synchronization). Dan jika satu clock tersinkronisasi dengan clock yang lain

dengan derajat akurasi yang diketahui, maka kita bisa mengukur interval terjadinya dua peristiwa

pada komputer yang berbeda, walaupun tidak tersinkronisasi ke sumber waktu dari luar. Hal ini

disebut sinkronisasi internal (internal synchronization).

Beberapa gagasan pengkoreksian (correctness) untuk clock sudah pernah diajukan.

Hardware clock H selalu dikoreksi apabila drift-nya sudah mencapai angka tertentu (ρ > 0). Jadi,

galat (error) perhitungan interval antara waktu sebenarnya t dan t’ (t > t’) adalah:

(1 - ρ)(t' - t) ≤ H(t') - H(t) ≤ (1 + ρ)(t' -t)

Clock yang tidak menerima pengkoreksian apapun dinyatakan faulty. Clock dinyatakan

crash failure ketika berhenti berdetik sama sekali. Kegagalan clock lainnya adalah arbitrary

failure. Contoh arbitrary failure adalah ‘Y2K bug’ yang terjadi pada pergantian tahun 1999 ke

2000. Setelah 31 Desember 1999 dilanjutkan ke 1 Januari 1900.

Catatan: clock tidak harus akurat untuk menjadi benar.

Network


2.2.1 Sinkronisasi pada Sistem Sinkron

Pada sistem sinkron, sebuah proses mengirim waktu t dari clock lokalnya ke proses

lainnya dalam pesan m. Proses seharusnya menerima dan mencocokkannya dengan clock

lokalnya sendiri dengan t + Ttrans, di mana Ttrans adalah waktu transmisi. Sayangnya Ttrans

bervariasi dan sulit diketahui. Namun, waktu minimal transmisi min tetap dapat diperkirakan

apabila jaringan lancar dan tidak ada proses lain yang berjalan bersamaan.

Sistem terdistribusi yang banyak digunakan adalah asinkron. Delay pesan tidak terbatas

atau tergantung masing-masing clock komputer. Pada sistem asinkron, Ttrans = min + x, di mana x

≥ 0. Nilai x tidak diketahui, tetapi dapat diukur.

2.2.2 Metode Cristian untuk Sinkronisasi Clock

Gambar 2 Sinkronisasi clock dengan server

Cristian menyarankan untuk menggunakan server yang menerima sinyal UTC untuk

mensiknronisasikan komputer secara eksternal. Sebuah proses p meminta waktu dalam pesan m

kepada server S, kemudian menerima nilai waktu t dalam pesan mt. Proses p merekam total

waktu yang dibutuhkan Tround untuk mengirim permintaan dan menerima balasan. Dengan begini,

waktu yang akurat dapat diperhitungkan.

Permasalahannya adalah server yang menyimpan waktu hanya satu, yang apabila gagal

maka untuk sementara waktu sinkronisasi tidak dapat dilakukan. Cristian menyarankan untuk

menggunakan beberapa server yang sudah tersinkronasi. Jadi, klien meminta ke semua server

dan hanya menggunakan balasan yang pertama kali diterima.

2.2.3 Algoritma Berkeley

Gusella dan Zatti mengembangkan algoritma untuk sinkronisasi internal. Mereka

megembangkan algoritma ini pada komputer berbasis Barkeley UNIX. Pada lagoritma ini,

sebuah komputer ditunjuk sebagai coordinator yang disebut master. Komputer ini kemudian

memilih komputer-komputer untuk dimintai sinkronisasi, yang disebut slave, dengan master

secara periodik. Slave-slave membalas dengan nilai clock miliknya. Master menghitung clock-

nya sendiri dengan memperhitungkan waktu perjalanan data dan rata-rata dari nilai clock yang

didapat.

Algoritma ini tidak akan membaca clock yang faulty. Clock yang hanya berbeda sedikit,

dengan jumlah tertentu, dengan clock lainnya yang dipilih untuk dirata-rata. Hal ini disebut fault

tolerant average. Sehingga, ketika ada satu clock yang gagal atau rusak, tidak mempengaruhi

clock Master.


2.2.3 Protokol Waktu Jaringan (Network Time Protocol)

Metode Cristian dan algoritma Berkeley pada dasarnya digunakan untuk komunikasi

intranet. Protokol Waktu Jaringan (NTP) mendefinisikan arsitektur untuk pelayanan waktu dan

protocol untuk distribusi informasi waktu lewat internet.

Tujuan dan fitur NTP, antara lain:

To provide a service enabling clients across the Internet to be synchronized accurately to

UTC: NTP menyediakan layanan agar klien di internet dapat bersinkronisasi dengan

UTC.

To provide a reliable service that can survive lengthy losses of connectivity: NTP

menyediakan layanan yang bisa bertahan di jaringan mengalami loss karena jarak.

To enable clients to resynchronize sufficiently frequently to offset the rates of drift found

in most computers: NTP memungkinkan klien untuk sinkronisasi ulang secara berkala.

To provide protection against interference with the time service, whether malicious or

accidental: NTP menyediakan perlindungan terhadap interferensi dari layanan waktu,

baik galat maupun ketidaksengajaan.

Gambar 3 Contoh sinkronisasi subnet di NTP

Layanan NTP tersebar pada banyak server di internet. Server utama tersambung langsung

ke sumber waktu, seperti penerima sinyal radio UTC. Server sekunder disinkronisasi dengan

server primer. Server-servernya tersambung dalam hierarkikal logika yang disebut

synchronization subnet seperti Gambar 3. Semakin atas levelnya akan semakin akurat clock-nya.

Galat terjadi setiap melewati satu level.

Server-server NTP bersinkronasi satu sama lain dengan tiga cara, antara lain multicast,

procedure-call, dan symmetric.


1. Multicast

Multicast ditujukan untuk LAN berkecepatan tinggi. Satu atau lebih server secara

periodik menyebar waktu clock ke server di komputer lain yang tersambung di LAN.

Mode ini akurasinya rendah tetapi cocok untuk berbagai kepentingan.

2. Procedure-call

Procedure-call hamper sama dengan algoritma Cristian. Server menerima request dari

komputer lain dan membalasnya dengan pembacaan clock saat pengiriman. Mode ini

cocok ketika keakurasian tinggi dibutuhkan atau ketika multicast tidak dappat dilakukan.

3. Symmetric

Mode symmetric ditujukan untuk server yang mensuplai waktu dalam LAN atau pada

level tertinggi dari sebuah synchronization subnet.

Gambar 4. Message Exchange between a pair NTP peers

Pada mode procedure-call dan symmetric mode, memroses pertukaran bagian-bagian

pesan. Tiap pesan memiliki catatan waktu dari peristiwa yang baru saja terjadi, yaitu waktu local

ketika pesan tersebut dikirimkan. Seperti pada Gambar 4, pesan m menyimpan catatan waktu

setiap akan ditransmisikan, yaitu Ti-3 dan Ti-1, dan ketika diterima, yaitu Ti-2 dan Ti. Kemudian

NTP menghitung jeda waktu antara dua clock komputer.

2.3 Logical Time and logical Clock

Dari sudut pandang dari setiap single proses, event-event diurutkan berdasakan waktu seperti

pada local clock. Tetapi, seperti yang dikatakan oleh Lamport [1978], kita tidak dapat melakukan

singkronisasi clock secara sempurna pada sebuah sistem terdistribusi. Kita tidak dapat secara

umum menggunakan physical time untuk menentukan urutan dari suatu event yang terjadi.

Secara umum, kita dapat menggunkan sebuah skema yang mirip dengan physical, tapi pada

sistem terdistribusi digunakan untuk mengurutkan event-event yang terjadi pada proses yang

berbeda. Pengurutan ini berdasarkan pada dua hal yang simple dan intuitif :

o Jika dua event terjadi bersamaam pada satu process yang sama pi (i = 1,2, … ,N), kemudian

event-event tersebut terjadi sesuai dengan urutan pi yang kita sebuatkan diatas.


o Kapan saja sebuah message dikirim diantara proses-proses, event dari pengiriman message

terjadi sebelum event dari penerimaan message

Lamport menyebutkan partial ordering diperoleh dengan men-generalalisasikan kedua

hubungan ini, relasi happened-before. Istilah ini biasa juga disebut causal ordering atau potential

causal ordering.

Kita dapat mendefinisikan relasi happened-before, dinotasikan dengan →, seperti berikut :

HB1 : Jika Ǝ process pi : e → ie’, maka e → e’.

HB2 : untuk setiap message m, send(m) → receive(m)

- Dimana send(m) adalah event dari pengiriman message dan receive(m) adalah event

dari penerimaan message

HB3 : Jika e, e’ dan e” adalah event dimana e → e’ dan e’→e” maka e → e”

Relasi → diilustrasikan pada gambar 10.5. Pada ketiga proses tersebut, dapat dikombinasikan

menjadi a → f. Antar a dan e tidak ada relasi, maka ditulis a║ e

Gambar 5. Event yang terjadi pada tiga proses

2.3.1 Logical Clocks

Lamport menemukan sebuah mekanisme yang simple untuk mengurutkan happened-before

secara numeris. Mekanisme ini disebut logical clock. Lamport logical clock adalah software

counter yang bertambah secara monoton dimana nilainya tidak perlu menanggung hubungan

tertentu ke suatu physical clock. Setiap proses pi tetap berada pada logical clock masing-masing.

Timestamp dari suatu event e pada pi disini dinotasikan dengan Li(e) dan L(e).

Untuk notasi dalam suatu prose adalah sebagai berikut :

LC 1 : Li bertambah sebelum setiap event muncul pada proses pi

Li := Li + 1

LC 2 : (a) Ketika sebuah proses pi mengirim sebuah message m, nilai L juga ditempelkan

pada nilai m

t = Li

(b) pada saat menerima pesan (m,t), sebuah proses pj menghitung Lj := max(Lj ,t) dan

lalu mengalplikasikan LC1 sebelum melakukan timestamp untuk event

receive(m).


Gambar 6. Lamport timestamp untuk event pada gambar 5

2.3.2 Totally ordered logical clocks

Beberapa pasang event yang berbeda, yang dihasilkan oleh proses yang berbeda, telah diidentikfikasi

dengan Lamport timestamp secara numeris. Namun, kita dapat menciptakan sebuah urutan total peristiwa

- yaitu, satu untuk yang semua pasangan dari event yang berbeda terjadi. Jika e adalah sebuah peristiwa

yang terjadi di pi dengan local timestamp Ti dan e' adalah sebuah event yang terjadi di pj dengan local

timestamp Tj, kita mendefinisikan global logic timestamp untuk event ini menjadi (Ti, i) dan (Tj, j). Dan

kita define (Ti, i) <(Tj, j) jika hanya jika salah Ti <Tj atau Ti = Tj dan i <j terpenuhi. Urutan ini tidak

memiliki arti fisik umum (karena pengidentifikasi proses yang tidak beraturan), tetapi kadang-kadang

berguna. Lamport menggunakannya, misalnya, untuk mengurutkan proses masuknya ke bagian kritis.

2.3.3 Vector clocks

Mattern [1989] dan Fidge [1991] mendevelop vector clocks untuk mengatasi kekurangan pada

Lamport clocks : fakta bahwa dari L(e) < L(e’) kita tidak dapat menyimpulkan bahwa e → e’ . Vektor

clock untuk sebuah sistem dari N proses adalah sebuah array dari N integer. Setiap proses berada

pada vektor clock Vi masing-masing. Aturan adalah sebagai berikut :

VC1 : Inisialisasi Vi [j] = 0 for i,j = 1,2,… , N

VC2 : sesaat sebelum pi men-timestamp sebuah event, diset Vi[i] := Vi[i] + 1

VC3 : pi memasukan nilai t = Vi pada setiap message yang diirim

VC4 : Ketika pi menarima sebuah timestamp t pada sebuah sebuah message, pi di set

Vi[j] := max(Vi[j], t[j]) , for j = 1,2,…,N.


Gambar 7 Vektor timestamp untuk event pada gambar 5

2.4 Global States

Pada akhir dari sesi ini kita akan memeriksa masalah dari menentukan benar tidaknya sebuah

property dari sebuah sistem terdistribusi seperti yang dieksekusi. Kita mulai dari melihat contoh kondisi

dibawah ini

Gambar 10.8 Detecting global properties

Distributed garbage collection : sebuah objek akan dianggap sampah bila tidak ada yang mereferensi

ke objek ini pada sistem terdistribusi. Memori yang dipakai dapat di kosongkan kembali ketika objek ini

telah dianggap sampah.

Distributed deadlock detection : sebuah distributed deadlock terjadi ketika setiap dari kumpulan

proses saling menunggu proses yang lain untuk mengirim message.Jadi sistem tidak pernah ada

kemajuan.

p2p1

message

garbage object

objectreference

a. Garbage collection

p2p1 wait-for

wait-forb. Deadlock

p2p1

activatepassive passivec. Termination


Distributed termination detection : masalah disini adalah untuk mendeteksi bahwa sebuah algoritma

terdistribusi telah diputus. Detecting termination adalah masalah yang terdengar mudah untuk

diselesaikan : kelihatannya pada saat pertama saja yang perlu ditest apakah sudah diputus. Untuk melihat

bahwa tidak demikian, bayangkan sebuah algoritma terdistribusi di eksekusi oleh dua proses yang

berbeda, p1 dan p2 . Saat p1 dan p2 ada yang dalam kondisi aktif atau pasif tidak muncul masalah. Namun

ketika dua-duanya dalam kondisi pasif – suatu proses yang pasif tidak terlibat dengan aktivitas apapun,

tetapi hanya bersiap untuk merespon nilai yang diminta oleh proses yang lain (gambar 10.8c).

Distributed termination dan deadlock memang mirip, tapi pada dasarnya adalah masalah

yang berbeda. Deadlock mungkin efeknya hanya pada bagian dari proses dalam suatu sistem,

sedangkan pada distributed termination, semua proses harus dihentikan. Kedua, process

passivity tidak sama dengan proses menunggu pada deadlock : suatu proses deadlock berupaya

untuk melakukan tindakan lebih lanjut, dimana proses lain menunggu,sementara proses pasif

tidak terlibat dalam aktivitas apapun.

Distributed debugging : Sistem terdistribusi sangat kompleks untuk didebug [Bonnaire et all.

1995], dan ketelitian dan hati-hati sangat diperlukan dalam menentukan apa yang terjadi saat

eksekusi. Contohnya, Smith menulis applikasi dimana setiap proses pi berisi sebuah variable xi (i

= 1,2,…,N). Variable berubah sejalan dengan jalannya program, tapi variabel-variabel tersebut

selalu diharuskan dalam selisih δ satu sama lain. Sayangnya, ada bug dalam program dan

dicurigai nilainya berada dalam |xi – xj| > δ untuk beberapa i dan j. Masalahnya adalah bahwa relasi

ini harus dievaluasi untuk nilai-nilai dari variabel-variabel yang terjadi pada saat yang sama.

2.4.1 Global states and consistent cuts

Dimungkinkan bagi kita untuk mengamati suksesi dari tiap individual proses. Tapi akan

lebih susah ketika akan membuat global state dari sistem. Kita dapat mengkatarestikan eksekusi

dari setiap proses dari historynya :

History(pi) = hi = < ei0 , ei

1, ei

2,…>

Dengan cara yang sama, kita dapat membuat untuk setiap finite prefix dari history proses :

hik = < ei

0 , ei

1, … ,ei

k>

Gambar 8. Cuts

m1 m2

p1

p2Physical

time

e10

Consistent cutInconsistent cut

e11

e12

e13

e20 e 2

1 e 22


Secara prinsip kita dapat merekam apa yang terjadi pada eksekusi ϑ. Setiap proses dapat

merekam event yang terjadi disana dan suksesi dari state. Kita notasikan dengan sik

untuk state

dari proses pi sesaat sebelum event ke-k. Jadi si0digunakan sebagai inisialisasi awal.

Kita juga dapat membentuk global history dari ϑ sebagai union dari history proses individual:

H = h0 ∪ h1 ∪ … ∪ hN-1

Sebuah cut dari eksekusi suatu sistem adalah subset dari global histori adalah union dari

prefix histori proses :

C = h1C1

∪ h2C1 ∪ … ∪ ℎc

Cn

Sebuah cut C konsisten jika berisi juga seluruh event yang terjadi sebelum event tersebut :

Untuk semua event e ∈ C, f → e => f ∈C

Sebuah global state yang konsisten adalah satu yang sesuai dengan cut yang konsisten :

S0 → S1 → S2 →…

2.4.2 Global states predicates, stability, safety and liveness

Global state predicate adalah fungsi yang memetakan dari set dari global state dari proses

pada system ϑ untuk {true, false}.Salah satu karakteristik dari predicate yang terasosiasi dengan

state dari objek yang dianggap sampah, sedang deadlock atau sistem yang di terminate adalah

stabil. Sekali saja sistem memasukan state dengan predicate true akan mengembalikan nilai true

juga untuk semua state yang masih reachable.

Disini kita juga memperhatikan dua poin yang relevan dengan global state predicate : safety

and liveness. Misalkan ada sebuah property α yang merupakan sebuah predicate dari global

system state. Contohnya, α adalah sebuah property dari objek yang deadlock. Biarkan S0

menjadi stage original dari system. Safety sehubungan dengan α adalah pernyataan bahwa α

mengevaluasi menjadi false untuk semua state S dicapai dari S0. Sebaliknya, biarkan β menjadi properti

yang diinginkan dari global state system - sebagai contoh, properti dari mencapai terminasi. Liveness

sehubungan dengan β adalah properti itu, untuk setiap linearisasi L dimulai di state bagian S0, β

mengevaluasi menjadi true berlaku untuk beberapa state SL yang dapat dijangkau dari S0

2.4.3 Algoritma Snapshot

Algoritma Snapshot adalah algoritma yang sering digunakan pada sistem terdistribusi untuk

menyimpan global state yang konsisten dari sebuah sistem yang bekerja secara asinkron.

Algoritma ini dikembangkan tahun 1985 oleh Leslie Lamport dan K. Mani Chandy. Tujuan

utama dari algoritma ini adalah menyimpan dan kemudian merepresentasikan sebuah set proses

dan state dari saluran media transmisi untuk masing-masing dari set proses tersebut, sedemikian

sehingga walaupun kombinasi dari proses dan media transmisi yang sama tidak pernah terulang

kembali, global state yang tersimpan tetap konsisten.


Algoritma ini bekerja dengan beberapa asumsi, antara lain:

o Tidak ada error yang terjadi pada proses maupun media transmisi.

o Media transmisi bekerja secara unidirectional, dan bekerja dengan sistem queue, yaitu FIFO

(First In First Out).

o Proses-proses ang berhubungan dan media transmisinya terkoneksi dengan jelas, maksudnya

disini ada saluran jelas yang menghubungkan kedua proses.

o Masing-masing proses dapat memulai proses pencatatan global state kapan saja.

o Proses dapat bekerja dengan normal, walaupun algoritma snapshot sedang digunakan dan

bekerja.

Cara kerja Algoritma Snapshot dapat direpresentasikan dengan langkah-langkah berikut:

a) Salah satu proses yang akan memulai proses penyimpanan global state, dalam hal ini

disebut observer process, melakukan 2 hal berikut:

1) Menyimpan state local yang dimiliki.

2) Mengirim snapshot request ke proses-proses yang lain yang termasuk dalam sistem

komunikasi suatu sistem terdistribusi.

b) Proses-proses lain pada sistem komunikasi tersebut yang menerima message request

snapshot tadi, kemudian merespon request tersebut dengan melakukan 2 hal, yaitu:

1) Mengirimkan state yang terakhir disimpan oleh proses tersebut ke proses yang

mengirimkan snapshot request, state terakhir ini biasanya disebut snapshot token.

2) Setelah mengirimkan state yang terakhir disimpan, proses kemudian mengirimkan

suatu record, simpanan data, yang merupakan special marker message, yang

berfungsi untuk membantu pemrosesan algoritma snapshot di proses yang

mengirimkan permintaan.

c) Ketika suatu proses menerima suatu pesan snapshot token yang tidak mengandung

special marker message, proses tersebut mengirimkan snapshot token yang telah diterima

ke observer process. Jadi setiap ada snapshot token, yang diterima tanpa adanya special

marker message, pada algoritma snapshot selalu diasumsikan message tersebut

merupakan bagian dari respon proses lain ke proses pengamat yang mengirimkan

permintaan snapshot.

d) Akhirnya, setelah semua proses selesai mengirimkan message dan semua snapshot token

telah diterima oleh proses pengamat, proses pengamat menggabungkan semua informasi

yang terkandung dalam semua snapshot token yang telah diterima untuk disimpan

sebagai global state dari sistem terdistribusi tersebut.


Gambar 9. Diagram Alur Kerja Snapshot Algorithm

Keuntungan utama penggunaan algoritma snapshot, antara lain:

a) Sangat efisien dalam mendeteksi hasil eksekusi dari berbagai proses dalam sebuah sistem

terdistribusi.

b) Seluruh state dari masing-masing proses dalam sistem terdistribusi tersimpan secara

terstruktur dan tersentralisasi, sehingga seorang administrator dari sistem terdistribusi

tersebut dapat melakukan pengecekan dengan mudah dan cepat.

c) Relatif lebih hemat sumber daya, karena masing-masing proses hanya melakukan

penyimpanan state pada saat yang dibutuhkan dan setelah selesai sumber daya langsung

dilepaskan.

2.4.4 Debug Terdistribusi

Tujuan utama dari proses pengumpulan, penyimpanan dan strukturisasi global state yang

telah dibahas sebelumnya adalah untuk memudahkan seorang programmer atau administrator

dari suatu sistem terdistribusi untuk melakukan pengawasan dan perubahan-perubahan yang

mungkin diperlukan untuk meningkatkan performa dari sistem terdistribusi itu sendiri. Proses

pengawasan dan melakukan perubahan-perubahan yang dirasa perlu ini dalam sistem terdistribus

biasa disebut distributed debugging, debug terdistribusi, melakukan proses pencarian dan

perbaikan berbagai bug dari sistem secara terdistribusi dengan mengamati berbagai kondisi yang

telah terkumpul pada global state.

Jadi, pada intinya, debug terdistribusi merupakan rangkaian dari 3 proses, yaitu:

a) Pengumpulan state-state dari masing-masing proses penyusun dari sistem terrdistribusi

ke dalam sebuah sistem pengamatan, yang biasanya disebut observer process.

b) Merestrukturisasi state-state tersebut menjadi sebuah basis data global state yang

konsisten dan mudah dimengerti.

c) Mengevaluasi nilai-nilai pada basis data global state ada menjadi suatu sistem penilaian

apakah suatu proses telah bekerja sesuai prosedur, pada istilah sistem terdistribusi sering


disebut “definitely true”, atau masih ada kekurangan-kekurangan yang harus diperbaiki,

untuk optimalisasi kerja suatu sistem terdistribusi, “possibly true”.

2.4.5 Pengumpulan State-State

Pengumpulan state-state dalam proses debug terdistribusi biasanya memanfaatkan sebuah

proses yang berperan sebagai pengamat yang bekerja di luar sistem terdistribusi yang diamati.

Salah satu contoh proses pengamatan dan pengumpulan state-state dapat diilustrasikan

sebagai berikut.

Gambar10. Contoh Kasus Pengumpulan State

Setiap ada perubahan nilai variabel dari proses p1 atau p2, proses yang bersangkutan

mengirim pesan update state ke proses yang mengamati kinerja sistem. Jadi setiap ada perubahan

sedikit saja, global state tersimpan di proses pengamat langsung terupdate.

Untuk memisahkan proses mana yang global state-nya sudah konsisten mana yang belum,

digunakan sebuah tipe data queue, yang berguna untuk menyimpan data sesuai urutan

pengiriman state.

Jadi, akhirnya didapatkan sebuah metode unutk mengumpulkan state-state yang diperlukan

untuk penentuan keputusan debugging.

2.4.6 Evaluasi “Possibly True”

Possibly True adalah kondisi dimana secara logis dan syntax program telah bekerja dengan

benar, tetapi ada hal lain yang menyebabkan ada kemungkinan program salah. Hal-hal lain

tersebut misalnya saja adalah delay pada sistem mekanis, human-error dari operator dan

sebagainya.

Contoh sederhana dari kasus yang merupakan contoh kondisi Possibly True adalah sebuah

program dirancang untuk membuka dan menutup 10 pintu secara bersamaan. Karena salah satu

pintu tidak diberi pelumas yang cukup, pintu tersebut belum menutup ketika 9 pintu lain telah

tertutup. Jadi dari sisi software, semuanya telah bekerja dengan benar, namun pada eksekusi

dunia nyatanya, eksekusi tidak berjalan semestinya.


Untuk membedakan kondisi seperti ini, diperlukan sistem monitoring yang berada diluar

sistem dan bekerja dengan data-data analog. Data analog digunakan karena untuk mengamati

eksekusi yang sesuai aslinya diperlukan simulasi mata manusia. Jadi, misalnya saja untuk kasus

10 pintu diatas, yang dimonitor adalah kerapatan kusen pintu dengan pintu yang diamati dengan

cara pengamatan berbasis kamera, bukan sinyal-sinyal elektronis yang bertujuan menggerakkan

pintu yang ada.

Peran global state dalam evaluasi kondisi Possibly True adalah sebagai sistem monitor data-

data analog tadi. Jadi dengan algoritma yang telah ditentukan, kemungkinan besar algoritma

snapshot, sistem monitoring mengumpulkan state-state dari pengamat data dan kemudian

berdasarkan kondisi tersebut menentukan tindakan yang paling baik untuk merespon data yang

ada.

2.4.7 Evaluasi “Definitely True”

Perbedaan evaluasi untuk “Definitely True” dengan “Possibly True”, adalah pada evaluasi

“Definitely True”, evaluasi dilakukan secara linear, berurutan dari proses awal lanjut ke proses

turunannya, dan seterusnya hingga proses terakhir.

Gambar 11. Evaluasi Definitely True

Pada ilustrasi diatas, tampak bahwa pada level 3 dari evaluasi ada 2 jenis kondisi linear yang

mungkin, yaitu satu true dan false. Dua kondisi ini merupakan representasi dari state yang

dikumpulkan oleh sistem monitoring. Pada level 4, ada 2 kondisi yaitu sebuah kondisi false dan

sebuah kondisi yang tidak diperhatikan karena hanya bisa dicapai jika kondisi level 3 bernilai

true. Jadi untuk algoritma evaluasi seperti gambar diatas, evaluasi akan selesai jika kondisi pada

level 5 bernilai true. Jika tidak, harus lanjut ke level-level selanjutnya.

Untuk evaluasi kondisi seperti diatas, tampak bahwa algoritma sangat boros sumber daya

karena harus ada pengecekan dimana sebuah kondisi akhir bernilai true, dan tidak ada alternatif

untuk kondisi tersebut.


2.4.8 Evaluasi “Possibly True” dan “Definitely True” pada sistem singkron

Perbedaan utama sistem sinkron adalah adanya internal clock yang mengontrol seluruh kerja

sistem terdistribusi yang diamati global state-nya. Efek dari internal clock disini adalah

pengiriman state dan berbagai pesan apapun disistem teratur dan memiliki jangka waktu yang

telah ditentukan sebelumnya. Jadi, akan ada penghematan sumber daya, karena pengecekan

kondisi dan pengirimannnya hanya dilakukan pada saat-saat tertentu dengan jumlah bit data yang

lebih sedikit karena komunikasinya berbasis sinkron.

Selain perbedaan diatas, prinsip kerja berbagai algoritma mengenai Time and Global States,

bekerja sama persis dengan komunikasi yang berbasis asinkron.

3. KESIMPULAN

Makalah ini membahas mengenai pentingnya penyimpanan kondisi pada suatu waktu tertentu

pada sebuah sistem terdistribusi. Events, Local and Global Histories, Cuts, Local and Global

States, Runs, Consistent States, Linearization, and Reachabity adalah beberapa konsep

pengelolaan time and global states pada sistem terdistribusi yang dibahas di makalah ini.

Kemudian setelah itu dibahas juga mengenai beberapa algoritma yang dapat memfasilitasi

proses penyimpanan kondisi tersebut bergantung pada kondisi komunikasi yang dimiliki oleh

masing-masing sistem terdistribusi.

rangkuman sister 3b

Documents