北大 分布式系统synchronization.ppt

Synchronization ./~course/cs501/2012 Hongfei Yan School of EECS, Peking University 4/18/2012 Contents 01: Introduction 02: Architectures 03: Processes 04: Communication 05: Naming 06: Synchronization 07: Consistency & Replication 08: Fault Tolerance 09: Security 10: Distributed Object-Based Systems 11: Distributed File Systems 12: Distributed Web-Based Systems 13: Distributed Coordination-Based Systems 2 /N Outline Clock Synchronization (++) Logical Clocks (++) Mutual Exclusion Global Positioning of nodes Election Algorithms Clock Synchronization ? Physical Clocks ? Global Positioning System (++) ? Clock Synchronization Algorithms (++) Why is it important ? ? Need to measure accurately ? ., auditing in merce ? Algorithms depending on ? ., consistency, ? make ? Correctness of distributed systems frequently hinges upon the satisfaction of global system invariants . ? ., Absence of deadlocks ? Write access to a distributed database never granted to more than one process ? the sum of all account debits and ATM payments in an electronic cash system is zero ? Objects are only subject to garbage collection when no further reference to them exists ., UNIX make program ? When each machine has its own clock, an event that occurred after another event may nevertheless be assigned an earlier time. 时间简史?人类生活有紧密联系的太阳的运动是比较均匀?地球自传是一天,公转是一年?天文计量,自从 17 世纪机械钟表发明. GMT (Greenwich Mean Time) ?太阳到达天空中它出现的最高点时称为中天?两次连续的太阳中天之间的时间称为一个太阳日?每天有 24 小时,每小时有 3600 秒, 1/86400 个太阳日是太阳秒?物理计量, 20 世纪 40 年代?1秒是铯 133 原子作 9,192,631,770 次跃迁所用的时间? BIH (Bureau International de l ’ Heure) 将这些值平均起来产生国际原子时间,简称为 TAI (International Atomic Time) ? TAI 和太阳秒计时之间的差增加到 800 毫秒时使用一次闰秒,修正后的时间系统称作统一协调时间,简称 UTC (Universal Coordinated Time) Physical Clocks ? A high-frequency oscillator, counter, and holding register ? Counter decrements on each oscillation, generates a “ tick ” and is reset from the holding register when it goes to 0. ? On work, cl