Algoritma sinkronisasi waktu banyak digunakan.
Misalnya, dalam sistem Unix, perintah Make hanya digunakan untuk mengkompilasi file kode yang baru diubah. Perintah Make menggunakan jam klien yang sedang berjalan untuk menentukan file mana yang telah dimodifikasi. Namun, jika kode ditempatkan di server file dan waktu host menjalankan perintah make berbeda dari waktu di server file, perintah make mungkin tidak berfungsi dengan benar.
Misalnya, saat bermain Dota, beberapa klien memerlukan jam yang disinkronkan agar gambar setiap orang tetap konsisten. , Misalnya, waktu server sinkronisasi komputer PC dapat mencapai akurasi sinkronisasi yang sangat tinggi.
Algoritma sinkronisasi waktu
Algoritma sinkronisasi waktu memiliki solusi berikut:
Algoritma Cristian
Latar belakang penerapan algoritma Algoritma Cristian terutama ketika proses P seperti server S yang meminta waktu:
1. P mengirimkan paket permintaan ke S untuk meminta waktu.
2. Setelah S menerima paket permintaan P, ia menambahkan waktu S saat ini ke paket tersebut dan kemudian mengirimkannya kembali.
3. Setelah P menerima paket data, waktu saat ini disetel ke T+RTT/2.
RTT mewakili Round Trip Time, yaitu waktu dari pengiriman P hingga penerimaan paket data. Algoritme ini mengasumsikan bahwa pengiriman dan penerimaan paket memerlukan jumlah waktu yang sama di jaringan. Dan juga diasumsikan bahwa waktu S dapat diabaikan saat memproses permintaan. Berdasarkan asumsi di atas, algoritma dapat diperbaiki sebagai berikut:
Kirim beberapa paket permintaan dari P ke S, lalu ambil RTT terkecil sebagai RTT dibagi dua dan tambahkan ke waktu yang termasuk dalam paket ini.
Analisis akurasi algoritma: Asumsikan min adalah waktu terpendek dari S ke P, dan T adalah waktu yang termasuk dalam RTT yang ditentukan di atas. Kemudian, rentang waktu pengaturan P harus [T+min, T+RTT-min]. Dengan cara ini, rentang penyimpangan waktu berada dalam RTT-2 menit. Keakuratan algoritma yang ditingkatkan harus RTT/2 menit.
algoritma algoritma Berkeley
Lingkungan penggunaan algoritma Berkeley berbeda dengan algoritma Cristian. Algoritma Cristian digunakan ketika klien meminta waktu yang tepat dari server. Algoritma Berkeley adalah algoritma untuk sinkronisasi jam antara beberapa klien. Algoritma spesifiknya adalah sebagai berikut:
1. Pertama pilih node dari ring sebagai Master melalui Perubahan dan Algoritma Robert.
2. Seorang Master menggunakan algoritma Cristian untuk meminta waktu setiap node.
3. Master mengevaluasi penyimpangan waktu setiap node dengan mencatat rata-rata RTT dan menghilangkan RTT dengan penyimpangan yang besar.
4. Master mengirimkan penyimpangan waktu setiap node ke setiap node, sehingga node dapat mengoreksi dirinya sendiri.
Setelah klien menerima waktu, secara umum, klien tidak akan menyesuaikan kembali waktu saat ini. Karena ini akan menyebabkan beberapa kesalahan yang tidak dapat dijelaskan pada program. Karena dalam banyak algoritma, asumsi dasar adalah bahwa waktu tidak akan disesuaikan kembali. Misalnya, buat perintah.
Ada solusinya: biarkan jam berjalan lebih lambat. Luangkan waktu untuk menyesuaikan diri dengan waktu yang tepat.
Selain itu algoritma Change dan Algoritma Robert perlu dibahas. Algoritma ini sama dengan algoritma sinkronisasi waktu dan dibutuhkan ketika bermain Dota. Ketika dota diinisialisasi, jam setiap pemain perlu disinkronkan. Setelah offline, algoritma tertentu harus digunakan untuk mencari host baru:
Perubahan dan Algoritma Robert
Algoritma Perubahan dan Algoritma Robert mengasumsikan bahwa setiap Proses memiliki UID dan dapat terdapat saluran komunikasi tanpa arah dalam jaringan berbentuk Cincin. Algoritmanya adalah sebagai berikut:
1. Pertama, setiap node dalam ring mengidentifikasi dirinya sebagai non-peserta.
2. Ketika suatu proses menemukan bahwa host sedang offline, pertama-tama ia mengidentifikasi dirinya sebagai peserta, dan kemudian mengirimkan paket pilihan host yang berisi UID-nya sendiri ke tetangganya.
3. Ketika paket data mencapai tetangganya, pertama-tama ia membandingkannya dengan UID miliknya. Jika UID miliknya lebih besar dari UID ini, ia mengidentifikasi dirinya sebagai peserta, mengubah UID dalam paket data, dan juga mengirimkannya ke paket data tersebut. arah jarum jam.
4. Ketika suatu proses menerima paket data dan menemukan bahwa UID dalam paket data sama dengan UID miliknya, maka proses tersebut memulai tahap kedua dari algoritma:
5. Proses ini mengidentifikasi dirinya sebagai non-peserta dan mengirimkan informasi tentang host yang dipilih ke tetangga, termasuk informasi UID.
6. Siklus ini berlanjut hingga proses kembali ke Proses yang dipilih sebagai host. Seluruh proses berakhir.
Ini adalah algoritma untuk memilih host dalam sistem terdistribusi. Tentu saja, dalam keadaan tertentu, Anda dapat mengubah kondisi pemilihan, seperti memilih salah satu dengan kecepatan jaringan tercepat atau CPU tercepat sebagai host. Pada saat yang sama, algoritme ini juga dapat menghindari situasi di mana beberapa proses menemukan bahwa host sedang offline pada saat yang sama, dan beberapa proses mencari host pada saat yang bersamaan.
Pseudocode dari algoritma ini dapat digambarkan sebagai berikut:
Mulai : M:= saya:
Kirim <i> ke tetangga;
Setelah menerima pesan <j>;
Jika M<j maka M:=j;
Kirim <j> ke tetangga;
Elseif M=j maka pemimpin;
Akhir;
Untuk analisis kompleksitas terperinci, model matematika, dan tabel statistik dari algoritma ini, silakan merujuk ke makalah ini:
http://www.vs.inf.ethz.ch/publ/papers/MsgCplxElecAlgo.pdf
Artikel ini hanya menganalisis beberapa algoritma sinkronisasi waktu dalam Sistem Terpusat, dan tidak menganalisis algoritma Sinkronisasi siaran Protokol Waktu Jaringan dan Referensi dalam sistem terdistribusi. Saya akan belajar NTP ketika saya punya waktu di masa depan.