CS514: Intermediate Course in Operating SystemsTopics for this lectureMany systems need real-timeSlide 4Real time in real systemsClock Synchronization and Synchronous SystemsClock SynchronizationClock synchronization protocolsPrecision and AccuracyThought question... and the answerHow clock synchronization used to workThinks known about clock sync.Better way to express thisGlobal Positioning SystemClock synchronization with GPSBasic ideaA-posteriori method, adjustment stageUsing real-timeReal-time broadcast protocolsA real-time broadcastA real-time distributed shared memoryPeriodic process group: MarzulloThe CASD protocolsBasic idea of the CASD protocolsCASD pictureIdea of CASDThe problems with CASDCASD in a more typical run... leading developers to employ more aggressive parameter settingsCASD with over-aggressive paramter settings starts to “malfunction”CASD “mile high”How to repair CASD in this case?Why worry?Slide 35Using CASD in real environmentsSlide 37Slide 38Issues?Similar to MARSMany more issues….FAA experience?Totem approachTradeoffs between consistency, timeA puzzleSlide 46What does real-time mean?Some real-time issuesReal-time todayCS514: Intermediate Course in Operating SystemsProfessor Ken BirmanBen Atkin: TALecture 23: Nov. 14Topics for this lecture•Adding clocks to distributed systems–Also, to non-distributed one–We won’t look at real-time operating systems and scheduling, but this was an active area until recently–Recent machines are so fast that importance of topic is now reduced…•Using time in broadcast protocols•Comparison of CASD with gossipMany systems need real-time•Air traffic control talks about “when” planes will be at various locations•Doctors talk about how patients responded after drug was given, or change therapy after some amount of time•Process control software runs factor floors by coordinating what machine tools do, and whenMany systems need real-time•Video and multi-media systems need isochronous communication protocols that coordinate video, voice, and other data sources•Telecommunications systems must guarantee real-time response despite failures, for example when switching telephone callsReal time in real systems•These real systems combine the need for logical consistency and coordination (for control) with the need for physical coordination and timely behavior•Issue becomes one of integrating real-time tools and support with logical tools and support such as we have already considered•Not real-time or logical time, but want both for different aspects of a single application!Clock Synchronization and Synchronous Systems•Up to now, we restricted attention to logical notions of time: “a happens before b”•Today look at adding real clocks to such a system•Two views of real-time:–Supporting clocks that programs can consult as needed–Making direct use of real-time inside protocolsClock Synchronization•Topic was extremely active during early 1980’s•Best known algorithms include the one in OSF/1 UNIX (based on one by Marzullo at Xerox), the “optimally accurate” algorithm of Srikanth and Toueg, and the “probabilistic” algorithm of Cristian•Introduction of Global Positioning System is eliminating the need for this form of synchronizationClock synchronization protocols•Would like to think of network as having a single “clock” that all processes can consult•But need to implement this using many “local” clocks that can:–Initially be set incorrectly–Drift over the course of time•Clock synchronization tries to keep clocks close to true real-time and minimize their tendency to driftPrecision and Accuracy•Accuracy measures local clocks relative to an external source of accurate real-time. Accurate clocks are close to real-time•Precision measures local clocks relative to each other. Precise clocks are close to each other•Skew is the numerical limit on the maximum dis-tance that correct clocks can drift apart. E.g. could say the “maximum skew is 1sec” for some systemThought question•Suppose that you were an air-traffic controller•Assume that clock synchronization is by a protocol that runs on your local area network. Each control center runs its own clock sync.•Would you prefer an algorithm that optimizes for the best possible accuracy, or for the best possible precision?... and the answer•Air traffic controller basically says to planes “during time t0 to t1 fly from a to b”•Planes presumably have accurate clocks.... so ATC needs accurate clocks, too.•Precision is like internal consistency. Accuracy is like external consistency (dynamic uniformity)How clock synchronization used to work•Periodically, all processors would run a clock sync protocol, for example by broadcasting the reading from their clocks•Each receives a set of values from the others (sets may differ due to faults!)•Algorithm would pick a synchronized value from the set; analysis used to prove properties of clocksThinks known about clock sync.•Accuracy of clock synchronization is limited by end-to-end latencies for messages passing through the network•Example: you tell me that it is 10:00am, exactly. •I am unsure how long the message took to pass through the network, hence I conclude that the time is in the range [10:00, 10:00+]Better way to express this•Suppose that I know something about the mean message propagation latency•The quality of clock synchronization is at best proportional to the possible variation in latency relative to this mean•A-posteriori method of Verissimo and Rodriguez uses this to obtain optimal precision (but is less accurate than the algorithm of Srikanth, Toueg)Global Positioning System•Satellite system launched by military in early 1990’s, became public and inexpensive•Can think of satellites as broadcasting the time•Small radio receiver picks up signals from three satellites and triangulates to determine position•Same computation also yields extremely accurate clock (accurate to a few milliseconds)Clock synchronization with GPS•Put two GPS receivers (or more) on a network•Periodically, receivers broadcast the “true time”•Other machines only need to adjust their clocks to overcome propagation delays for clock sync messages through the network!•Well matched to the a-posteriori clock synchronization approachBasic idea•GPS receiver broadcasts “the time is now 10:00” on a broadcast network
View Full Document
Unlocking...