SISTEM TERDISTRIBUSI NAME SERVICE & TIME & COORDINATION

NAME SERVICE

 Pengenalan Name Service

Dalam sistem terdistribusi, name service digunakan untuk menunjuk ke suatu sesumber yang beragam dan tersebar seperti komputer, layanan (services), file, remote object, use yang dapat memudahkan pengguna.

Contoh penamaan pada aplikasi sistem terdistribusi:

– URL untuk mengakses suatu halaman web.

– Alamat e-mail utk komunikasi antar pemakai.

Selain itu name service juga merupakan layanan penamaan yang berfungsi untuk menyimpan naming context, yakni kumpulan binding nama dengan objek, tugasnya untuk me-resolve nama. Kebutuhan akan penamaan juga memicu munculnya layanan penamaan (Naming Services) yang menyediakan mekanisme dan struktur penamaan objek itu sendiri. Contohnya DNS (Domain Name Service), X.500, COBRA, dan GNS.

 Name Resolution, Binding, Attributes

•  Name resolution: Nama ditranslasikan ke data ttg resource/object tsb.

•  Binding: Asosiasi antara nama & obyek. Dan biasanya nama diikat (bound) ke attributes dari suatu obyek.

•  Address: atribut kunci dari sebuah entitas dalam sistem terdistribusi

•  Attribute: nilai suatu object property.

Penguraian Naming Domains untuk mengakses resource dari URL

Didalam setiap name objek terdapat juga beberapa atribut yang merupakan properti suatu objek. Contoh :

✓  DNS : memetakan dari nama ke atribut alamat IP host

✓   X.500 : memetakan suatu nama seseorang ke beberapa atribut, seperti email, telepon, dsb.

✓       CORBA Naming Service yang memetakan nama remote objek ke remote object reference.

 Model Name Service and the Domain Name System

Suatu name service dapat menyimpan kumpulan satu atau lebih kontek penamaan yaitu sehimpunan keterkaitan antara nama dan atribut objek, seperti user, komputer, services dan remote object. Yang dibutuhkan dari suatu Name Services adalah :

– penamaan unik yang standard

– scalability

– consistency

– performance dan availability

– mudah menyesuaikan terhadap perubahan

– perlindungan kegagalan

Dalam rangka memenuhi kebutuhan tersebut, sebuah name server setidaknya dapat menerapkan mekanisme berikut :

o Partitioning

✓    Tidak ada satu name server yang dapat menyimpan seluruh nama dan atribut untuk seluruh jaringan.

✓  Data nama dipartisi berdasarkan domain.

o Replication

✓ Sebuah domain biasanya memiliki lebih dari satu name server

✓  Untuk meningkatkan availability dan performance o Caching

✓    Sebuah name server dapat melakukan mekanisme caching terhadap data nama dari name server lain

✓  Hal ini dilakukan untuk mencegah operasi permintaan sama berulang-ulang

 Name Space

Name Space adalah kumpulan nama sah yang dikenal oleh suatu layanan yang sesuai. Suatu nama dapat digambarkan dengan menggunakan generative grammar, seperti BNF (Backus-Naur Form).

Contoh BNF untuk email

Berikut adalah beberapa karakter dari name space :

•  memiliki struktur internal

✓ flat

✓ hirarki yang mempresentasikan posisi (contoh sistem berkas UNIX)

✓ hirarki yang mempresentasikan struktur organisasi (contoh Internet Domain)

•  Karena hirarki, memiliki potensi tak terbatas

•  Suatu name space dapat diatur secara terdistribusi (naming domain)

•  Suatu name space dapat berupa gabungan dari beberapa nama space lain. Contoh mount pada UNIX/Linux

Name Resolution

Nama resolution yaitu diberikan nama obyek , temukan obyek tersebut. Simpan semua nama di setiap name server. Partisi basis data penamaan (naming database) dapat dilakukan berdasarkan:

• Algoritma:

✓  Tergantung dari nilai sebuah fungsi hash.

✓  Tidak tergantung pada struktur dan lokasi obyek.

• Sintaks:

✓  Contoh: telaga.cs.ui.ac.id.

• Atribut.

✓ Proxy dapat menyimpan pointer migrasi suatu obyek.

Name servers and navigation

      Navigasi dan name servers di sini memiliki arti petunjuk pengaksesan nama data dari lebih dari satu name server untuk menyelesaikan suatu pemetaan nama (resolve a name). Yang didalamnya terdapat 3 metode,yaitu :

1.  Iterative Navigation

Agent tetap memegang kendali proses resolusi sebuah nama. Server mengembalikan status resolusi dan alamat server yang harus dihubungi selanjutnya.

Agent bekerja lebih keras dari cara pertama, dan perlu sedikit pintar.

Transitive Navigation hampir sama dengan resolusi rekursif. Return address dari agent diteruskan oleh server, sehingga jika informasi lokasi obyek ditemukan, informasi tersebut langsung diteruskan ke agent. Kelebihan : berkurangnya pengiriman pesan, server tidak perlu menyimpan status on going resolution. Kekurangan: pengirim tidak menerima ACK.  

2.  Non-recursive and Recursive server-controlled navigation

3.  Recursive Server Controlled

Rekursif adalah aktifitas berpindah dari server ke server, shg nama selalu di-resolve dalam konteks yang baru. Multiple servers transparan bagi name agent. Agent tidak sibuk. Servers harus menyimpan return address untuk setiap outgoing lookup, dan secara keseluruhan bekerja keras.

Domain Name System

Domain Name System merupakan sebuah name service sebagai standard penamaan pada Internet. Hal itu ditemukan oleh Mockapertis (1987) untuk menggantikan skema penamaan original, dimana semua hal dilakukan oleh satu central master file dan di download oleh FTP untuk semua computer yang membutuhkannya.

Database DNS diterapkan dengan sistem partitioning yang terbagi-bagi dalam suatu zone berdasar domainnya dan letak geografis. Top level organizational domain (biasa disebut generic domains) yang digunakan saat ini antara lain :

Com - organisasi komersial

Edu - institusi pendidikan

Gov - institusi pemerintahan

Mil - organisasi militer

Net - Network support center

Org - Organisasi tertentu yang tidak disebutkan disini Int - organisasi internasional

Us - United states

Uk - United kingdom

Id – Indonesian.

 

TIME & COORDINATION

 

.  Logical Clock & Syncronitation

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.

·         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.

·         Clock Skew And Clock Drift

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

·         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 clocknya dengan sinyal ini.

·         Sinkronasi Clock Fisik

Untuk mengetahui kapan sebuah peristiwa terjadi secara akurat pada proses system 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.

Koordinasi Terdistribusi

Dalam sistem terdistribusi berbasis koordinasi, fokusnya adalah pada bagaimana koordinasi antara proses berlangsung. Jika ada lebih dari satu proses yang siap running, maka Sistem Operasi akan menentukan salah satu proses untuk running lebih dulu. Aktivitas Koordinasi Terdistribusi :

1.          Pengurutan Event

·         Memori & clock tdk tunggal

·         Tidak mungkin menyatakan urutan dua kejadian

·         Hanya dpt ditentukan partial ordering (pengurutan sebagian) relasi Happened-Before (Hukum sebab-akibat : suatu pesan dapat diterima setelah pesan tersebut dikirim. Jika A dan B adalah event pada proses yg sama, dan A dieksekusi sebelum B, maka

A → B) 

2.          Mutual Exclusion

a.    Pendekatan Tersentralisasi (Centralized)

•  Salah satu proses dipilih sebagai koordinator utk mengatur entri ke CS

•  Menggunakan pesan request-reply-release untuk masuk ke CS

•  (+): menjamin mutex, dpt 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 yg gagal, mengganggu proses lain yg tidak akan masuk ke CS

c.    Pendekatan Token Passing

•  Menggunakan satu token yg beredar diantara proses

•  Hanya proses yg memiliki token saat itu yg dapat masuk ke CS

•  Syarat: adanya lingkaran lojik yg menghubungkan semua proses

•  (+): menjamin mutex, bebas starvation

•  (--): jika token gagal → perlu digenerate kembali, jika proses gagal → perlu dibentuk ring lojik baru.

3.          Atomisitas

Tiap situs memiliki koordinator transaksi yg berfungsi menjamin atomisitas eksekusi transaksi, dengan cara:

·         memulai eksekusi transaksi

·         memecah menjadi beberapa sub-transaksi dan mendistribusikannya pada situs-situs yg cocok utk dieksekusi

·           mengkoordinasikan terminasi transaksi (commit, atau abort)

·           Tiap situs menyimpan log untuk tujuan recovery

 

4.          Concurrency Control

Manajer transaksi berfungsi mengelola eksekusi transaksi yg mengakses data

·         Menyimpan log untuk tujuan recovery

·         Berpartisipasi dalam skema kontrol-konkurensi untuk mengkoordinasi eksekusi transaksi

5.          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 sistim

·        Sulit diterapkan: tidak praktis, boros resources

·        Mengizinkan sistim untuk masuk ke “state deadlock”

·        Gunakan algoritma deteksi (jika terjadi deadlock)

·        Skema recovery untuk mengembalikan ke “safe state”

6.       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:

1.  election message : digunakan untuk pemberitahuan akan adanya pemilihan

2.  answer message : merupakan jawaban dari election message

3.   coordinator message : digunakan untuk memberitahukan identitas dari proses pemilihan

Sebuah  proses  dimulai  dengan  pemilihan  ketika  telah  diperintahkan,  melewati

timeout, saat coordinator gagal. Ketika sebuah proses menerima pesan coordinator proses tersebut akan menset variabelnya menjadi elected. Jika sebuah proses menerima proses

election proses tersebut akan mengirim jawaban dan akan memulai proses terpilih tersebut, kecuali telah mulai sebelumnya.

·        Algoritma Ring

Tujuan dari algoritma ini adalah untuk memilih sebuah proses tunggal yang disebut koordinator, yang merupakan proses dengan identifier terbesar. Awalnya, setiap proses ditandai sebagai non-peserta dalam pemilihan. Setiap proses bisa mulai pemilihan. Hal hasil dengan menandai dirinya sebagai salah satu peserta, menempatkan para identifier dalam pemilihan pesan dan mengirimkannya kepada tetangga searah jarum jam. Ketika sebuah proses menerima pesan pemilihan, itu membandingkan pengenal dalam pesan dengan sendiri. Jika identifier yang tiba lebih besar, maka meneruskan pesan 10 tetangganya. Jika identifier yang tiba lebih kecil dan penerima bukan merupakan peserta maka pengganti pengenal sendiri dalam pesan dan ke depan itu, tetapi tidak meneruskan pesan jika sudah menjadi peserta. Pada pemilihan penerusan pesan dalam beberapa kasus, proses menandai dirinya sebagai peserta.

7.3.  Model sinkronisasi & Asinkronisasi

Sinkronisasi adalah proses pengaturan jalannya beberapa proses pada saat yang bersamaan. Secara garis besar mungkin sinkronisasi adalah menyamakan sesuatu secara 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.
Sistem   Asynchronous	-   seperti  object-oriented software   -		biasanya	Dibuat
dari modular 'benda  keras',  masing-masing		dengan  komunikasi  yang	terdefinisi	Dengan
baik antarmuka. Ini modul dapat	beroperasi	pada  kecepatan  variabel,  apakah		Karena

pengolahan data-dependent, skala tegangan dinamis , atau variasi proses . Modul kemudian dapat digabungkan bersama-sama untuk membentuk suatu sistem kerja yang benar, tanpa mengacu pada global sinyal clock . Biasanya, daya rendah diperoleh karena komponen diaktifkan hanya pada permintaan. Selain itu, beberapa gaya asynchronous telah terbukti untuk mengakomodasi antarmuka clock, dan dengan demikian mendukung desain campuran-waktu. Oleh karena itu, sistem asynchronous cocok dengan baik kebutuhan yang benar-by-konstruksi metodologi dalam perakitan sistem heterogen dan scalable skala besar.