Chapter 6 Synchronization (PDF)

CHAPTER 6- SYNCHRONIZATION Measuring the time: UTC (Universal Coordinated Time Zaman, 17. yüzyılda mekanik saatler kullanarak astronomik metotlarla ölçülüyordu. Güneşin öğlenleri en üst noktaya çıkışından yararlanılıyordu. Güneşin iki gün arka arkaya en üst noktaya çıktığı anlar arasında geçen zam...

CHAPTER 6- SYNCHRONIZATION Measuring the time: UTC (Universal Coordinated Time Zaman, 17. yüzyılda mekanik saatler kullanarak astronomik metotlarla ölçülüyordu. Güneşin öğlenleri en üst noktaya çıkışından yararlanılıyordu. Güneşin iki gün arka arkaya en üst noktaya çıktığı anlar arasında geçen zamana bir güneş günü deniyordu. Bir güneş günü 24 saat içerdiğinden ve her saat 3600 sn. ye karşı geldiğinden bir güneş saniyesi de bir güneş gününün 1/86.400’ü oluyordu. 1940larda çeşitli nedenlerle dünyanın dönüş süresinin her gün eşit olmadığı tespit edildi. Bunun üzerine bir güneş saniyesinin hesaplanmasında 2 güneş günü yerine daha çok sayıda güneş gününün ortalaması kullanıldı ve elde edilen değere ortalama güneş saniyesi dendi. 1948’de atomic saatin bulunması ile zaman ölçümü astronominin değil, fiziğin konusu oldu. Zaman cesium 133 atomunun salınımlarının sayısı ile ölçülmeye başlandı. Dünyada birçok laboratuvara cesium 133 atomu verildi. Bu labaratuvarlar periyodik olarak bu atomun salınım sayılarını Paris’teki bir büroya göndermeye başladılar. Bu büro bu değerlerin ortalamasını alarak International Atomic Time (TAI) ismiyle zamanı ölçmeye başladılar. Ancak 86400 TAI saniyesi astronominin hesapladığı ortalama güneş gününden 3 milisaniye daha kısa idi. Bu fark yıllar içinde birikim yaparak çeşitli istenmeyen durumlara yol açabilirdi. Paris’teki büro TAI ve güneş günü arasındaki zaman 800 msn’yeye çıkınca artık saniyeler ekleyerek düzeltme yaptılar. Bu ölçüm sistemine Universal Coordinated Time (UTC) dendi. Günümüzde dünyanın çeşitli yerlerindeki 40 kısa dalga radyo istasyonu her UTC saniyesinin başında kısa bir pulse yayınlamaktadır. Bu istasyonların hassasiyeti +- 1 milisndir. Ancak atmosferik nedenlerden dolayı fark +-10 milisn’yeye çıkabilmektedir. Bunun yanısıra birçok uydu da UTC zamanı sağlamada kullanılmaktadır. Uyduların UTC ölçüm hassasiyeti 0,5 milisnye olmaktadır. Hatta birden fazla uydunun kullanımı ile hassasiyet 50 nanosn.’ye düşebilmektedir.  Clock Syncronization An example clock synchronization algorithm: Berkeley algorithm Time daemon tüm makinalardan o amki clock değerini ister. 3 makinanın clok değerlerinini ortalamasını alır ve tüm makinalara düzeltme değerini gönderir. (Network Time Protocol- NTP) İnternette zaman NTP ya da Network Time Protocol ile ölçülmektedir. Ana servisçiler UTC radio pulse’ı kaynağına doğrudan bağlıdır. İkincil servisçiler Ana servisçilere senkronize olurlar. Primary servers are connected directly to a time source such as a radio clock receiving UTC; Secondary servers are synchronized, ultimately, with primary servers. Bu servisçiler katmanlı bir mimari ile birbirine başlıdır. 1. Katmanda ana servisçiler vardır. 2. Katmandaki servisçiler 1. Katmandaki servisçilere senkronize olurlar. 3. Katmandakiler de 2. Katmandakilere senkronize olurlar. En alttaki servisçiler (yapraklar) kullanıcı makinasında bulunurlar. Alt katmanlara inildikçe hassasiyet düşer. NTP protokolü gidiş/geliş gecikmelerini dikkate alan matematiksel bir işlem ile düzeltme yapar. The servers are connected in a logical hierarchy called a synchronization subnet whose levels are called strata. Primary servers occupy stratum 1: they are at the root. Stratum 2 servers are secondary servers that are synchronized directly with the primary servers; stratum 3 servers are synchronized with stratum 2 servers, and so on. The lowest-level (leaf) servers execute in users’ workstations. The clocks belonging to servers with high stratum numbers are liable to be less accurate than those with low stratum numbers, because errors are introduced at each level of synchronization. NTP also takes into account the total message round-trip delays to the root in assessing the quality of timekeeping data held by a particular server. https://support.microsoft.com/en-gb/help/262680/list-of-the-simple- network-time-protocol-sntp-time-servers-available  LOGICAL CLOCKS Çoğu durumda gerçek dünya saatine senknonize olmak gerekmeyebilir. Düğümlerin kararlaştırdıkları bir zamana senkronize olması yeterlidir. Lamport’s logical clocks: 1. a ve b bir süreçteki 2 olaysa , a b’den once ortaya cıkmıssa ab doğrudur 2. a bir sürecin mesaj gönderimi, b başka bir sürecin mesaj alımı ise ab ‘dir. Bir mesaj gönderilmeden alınamaz. Dağıtık sistemlerde tüm saatler aynı zamanı göstermeyebilir. Senkronizasyon mesaj alım ve gönderimi ile sağlanır. Bir mesaj gönderilmeden alınmaz. Dağıtık sistemde mesaj tabanlı iletişim oldugu için mantıksal senkronizasyon sağlanmış olur.  TOTALLY ORDERED MULTICAST Bir bankanın veritabanının İstanbul ve Ankara olmak üzere 2 şehirde kopyası olsun. Ali’nin bu bankada 1000 TLsi olsun. Veritabanının iki kopyasında da Ali’nin parası 1000 TL görülür. Ali Ankara’dan 100 TL eklesin, İstanbul’daki bir banka memuru da aynı anda faizi %1 arttırsın. Mesafeden dolayı iki işlem iki kopya üzerinde farklı sırada gerçekleştirilir. Ankara’da, önce Ali’nin işlemi yapılır, sonra yeni faiz oranı ile hesaplama yapılır. İstanbul’da da önce yeni faiz oranı ile hesaplama yapılır, sonra Ali’nin işlemi yapılır. Ankara’daki kopyaya göre Ali’nin 1111 TL’si olur, İstanbul’daki kopyaya göre Ali’nin 1110 TLsi olur. Bu hatanın olmaması için 2 işlemin 2 yerde aynı sırada yapılması gerekir. Bunu sağlayan çözüm Totally Ordered Multicast olarak bilinir. Bu yaklaşımda güncelleme isteğini gönderen paketlere bir timestamp eklenir. Bu şekilde mesajlar çoğayayım (multicast) ile tüm kopyalara gönderilir. Mesajlar tüm kopyalarda timestamplere göre küçükten büyüğe sıralı bir kuyruğa konur. Bu şekilde tüm kopyalardaki kuyruklar aynı olur. Tüm güncellemeler aynı sırada gerçekleşir ve tutarsızlık problemi ortadan kalkar. Solution:  MUTUAL EXCLUSION For concurrent access to unsharable resources. Belli bir anda sadece bir kullanıcı/süreç tarafından kullanılan kaynaklara paylaşılamayan kaynaklar denir. Mutual Exclusion böyle bir kaynağa aynı anda çok kullanıcı/süreçten istek gelirse erişimi düzenler. Belli bir anda sadece bir kullanıcı/sürecin kaynağa erişmesini ve kaynağı kullanmasını sağlar. Değişik Mutual Exclusion yaklaşımları bulunmaktadır. 1. Centralized Approach / Merkezi yaklaşım Her kaynak için bir koordinatör süreç bulunur. Süreçler bir kaynağı kullanmak istedikleri zaman bu koordinatörden izin almak durumundadırlar. Yukarıdaki şekilde P1 koordinatörden kaynağı istedi. O anda kaynak kullanımda olmadığı için koordinatör OK mesajı ile kaynağı P1e verir. Kaynak P1 tarafından kullanılırken P2 den de istek geldi. P1 hala kaynağı kullandığı için koordinatör P2ye OK mesajı göndermez, P2’den gelen mesajı kaynağın kuyruğuna ekler. P1 kaynakla işini bitirdiğinde bu durumu Release mesajı ile koordinatöre bildirir. Koordinatör P2’ye OK mesajı gönderir ve P2 artık kaynağa erişim yapabilir. Problem: The coordinator is the single point of failure Bu yaklaşımın problem koordinatör sürecin bozulması/çökmesi durumunda sistemin de çökmesidir.  2. Distributed Approach/Dağıtık yaklaşım Dağıtık yaklaşımda kaynağı kullanmak isteyen süreçler sistemdeki tüm süreçlere istek gönderir. Bu süreçler istek mesajlarına bir timestamp eklerler. Bu şekilde her bir süreç diğer tüm süreçlerin kaynağını kullanmak istemesinden haberdardır. Şekilde 0 ve 2 numaralı süreçler kaynağı kullanmak istediklerinde kendileri de dahil tüm süreçlere istek mesajı gönderiyor. Tüm süreçler kendilerine gelen istek mesajlarındaki timestamplere bakıyorlar. Timestampi en küçük olan süreç kaynağı kullanma hakkı kazanır. Şekilde b şıkkında 0 numaralı süreç kendi isteğinin en küçük timestampe sahip olduğunu görür. Diğer süreçler de bunu görürler. P1 2 sürece de OK mesajı gönderir. P2 de P0’a OK mesajı göndererek P0’ın kaynağı kullanmasına izin verir. P0 tüm süreçlerden OK mesajı aldığında kaynağı kullanma iznini almış olur. Kaynakla işi bitince P2ye kaynak kullanma izni verir. P1 zaten önceden P2ye bir OK mesajı göndermişti. P2de böylece tüm süreçlerden izin almış olur ve kaynağa erişim yapar. Problems: 1. Crash of any process leads to excessive waiting 2. A lot of messaging Bu yaklaşımın problemleri mesaj yükünün çok olması ve herhangi bir sürecin çökmesi durumunda çok yüksek beklemelerin ortaya çıkmasıdır. 3. Token Ring Approach Bu yaklaşımda süreçler mantıksal bir halka ile birbirine bağlanırlar. Sistemde her kaynak için sürekli dolaşan bir jeton vardır. Bir kaynağı kullanmak isteyen süreç bu kaynağın jetonu kendine geldiğinde onu alır ve kaynağa erişim yapar. Diğer süreçlerden de kaynağı kullanmak isteyen varsa jeton kendisine gelmediği için kullanamaz. Kaynağı alan süreç işi bitince jetonu halkaya bırakır. Diğer süreçlerden jeton kendisine ilk gelen kaynağa erişim hakkı kazanır. Problem: Process crash Problem: Herhangi bir sürecin çökmesi sistemi de çökertir. 4. A Decentralized Algorithm Request permission from majority of processes Problem: If there are many requests for the same resource no process can get permission from majority of processes. Kaynak isteyen bir süreç tüm süreçlerin yarısından bir fazlasından onay alırsa kaynağa erişim hakkı kazanır. Problem: Kaynak için aynı anda birden fazla süreç istekte bulunursa süreçlerin hiçbiri süreçlerin yarısından bir fazlasından onay almayabilir.  ELECTION ALGORITHMS/Seçim Algoritmaları For selecting a new coordinator if a coordinator crashes Koordinatör içeren dağıtık yazılımlarda koordinatörün çökmesi durumunda yeni bir koordinatör belirlenmelidir. 1. Bully Algorithm Koordinatör 7 nolu süreçti ve çöktü. Bunun farkına ilk varan süreç 4 numaralı süreç oldu. Bu süreç numarası kendi numarasından büyük tüm süreçlere Seçim mesajı gönderir. Bu süreçler (5 ve 6) kontrolü ele alır ve 4 numaralı sürece OK mesajı göndererek durmasını bildirir. 5 ve 6 nolu süreçler numarası kendilerinden büyük olan süreçlere Seçim mesajı gönderirler. 6 nolu süreç 5 nolu sürece OK mesajı göndererek durmasını bildirir, kontrolü ele alır ve tüm süreçlere koordinatör olduğunu ilan eder. 2. Ring Algorithm Tüm süreçler mantıksal bir halkaya dizilmişlerdir. 6 numaralı süreç koordinatör olan 7 nolu sürecin çöktüğünü fark edince halkaya kendi numarasını içeren bir seçim mesajı koyar. Bu mesaj halka üzerinde dolaşır. Mesajı alan süreçler kendi numaralarını bu mesaja yazar. Mesaj tüm süreçler arasında dolaşır. Mesaj 6 nolu sürece gelince bu süreç mesajdaki süreç numaralarına bakar ve o an aktif en büyük numaraya sahip süreci koordinatör olarak seçer. Aynı anda birden fazla süreç koordinatörün çöktüğünü belirlerse her biri seçim sürecini başlatabilir. Örnekte 3 nolu süreçte koordinatörün çöktüğünü belirlemiştir. Oda 6 nolu süreç gibi halkaya seçim mesajı koyar. Bu mesaj kendisine tekrar geldiğinde mesajdaki süreç numaralarının en büyüğünü yeni koordinatör olarak belirler. Örnekte 3 nolu süreç de 6 nolu sürecin koordinatör olması gerektiğini anlamıştır. Koordinatörü belirleyen süreçler tüm süreçlere yeni koordinatör numarasını bildirirler.