Distributed Systems: Motivation, Time, Mutual ExclusionAnnouncementsTodayDistributed SystemsA Distributed SystemLoosely Coupled Distributed SystemsTightly Coupled Distributed-SystemsDistributed-Operating Systems (Cont.)Why Distributed Systems?Resource SharingOS Support for resource sharingDesign IssuesComputation SpeedupBreaking up the problemsDecomposition ExamplesDecomposition Examples (con’t)Linear SpeedupSuper-linear SpeedupOS Support for Parallel JobsOS Support for Parallel Jobs (con’t)ReliabilityRobustnessFailure DetectionFailure Detection (cont)ReconfigurationDistributed TimeWhat time is it?But what does time “mean”?Event OrderingLamport’s approachDrawing time-line pictures:Slide 32Slide 33Slide 34Slide 35Slide 36Happens before “relation”Logical clocksRules for managing logical clocksTime-line with LT annotationsSlide 41Total ordering?Partial OrderingTotal Ordering?Logical Timestamps w/ Process IDDistributed Mutual Exclusion (DME)Slide 47SolutionCDME: Centralized ApproachProblems of CDMEDDME: Fully Distributed ApproachDDME: Fully Distributed Approach (Cont.)Problems of DDMEToken PassingProblems of Token PassingCompare: Number of Messages?Compare : StarvationSummaryDistributed Systems: Motivation, Time, Mutual Exclusion2Announcements•Prelim II coming up next week:–In class, Thursday, November 20th, 10:10—11:25pm–203 Thurston–Closed book, no calculators/PDAs/…–Bring ID•Topics:–Everything after first prelim–Lectures 14-22, chapters 10-15 (8th ed)•Review Session Tuesday, November 18th, 6:30pm–7:30pm–Location: 315 Upson Hall3Today•Motivation•What is the time now?•Distributed Mutual Exclusion4Distributed SystemsDefinition:Loosely coupled processors interconnected by network•Distributed system is a piece of software that ensures:–Independent computers appear as a single coherent system•Lamport: “A distributed system is a system where I can’t get my work done because a computer has failed that I never heard of”-5A Distributed System-6Loosely Coupled Distributed Systems•Users are aware of multiplicity of machines. Access to resources of various machines is done explicitly by:–Remote logging into the appropriate remote machine.–Transferring data from remote machines to local machines, via the File Transfer Protocol (FTP) mechanism.-7Tightly Coupled Distributed-Systems•Users not aware of multiplicity of machines. Access to remote resources similar to access to local resources•Examples–Data Migration – transfer data by transferring entire file, or transferring only those portions of the file necessary for the immediate task.–Computation Migration – transfer the computation, rather than the data, across the system.-8Distributed-Operating Systems (Cont.)•Process Migration – execute an entire process, or parts of it, at different sites.–Load balancing – distribute processes across network to even the workload.–Computation speedup – subprocesses can run concurrently on different sites.–Hardware preference – process execution may require specialized processor.–Software preference – required software may be available at only a particular site.–Data access – run process remotely, rather than transfer all data locally.-9Why Distributed Systems?•Communication–Dealt with this when we talked about networks•Resource sharing•Computational speedup•Reliability-10Resource Sharing•Distributed Systems offer access to specialized resources of many systems–Example:•Some nodes may have special databases•Some nodes may have access to special hardware devices (e.g. tape drives, printers, etc.)•DS offers benefits of locating processing near data or sharing special devices-11OS Support for resource sharing•Resource Management?–Distributed OS can manage diverse resources of nodes in system–Make resources visible on all nodes •Like VM, can provide functional illusion but rarely hide the performance cost•Scheduling?–Distributed OS could schedule processes to run near the needed resources–If need to access data in a large database may be easier to ship code there and results back than to request data be shipped to code-12Design Issues• Transparency – the distributed system should appear as a conventional, centralized system to the user.•Fault tolerance – the distributed system should continue to function in the face of failure.•Scalability – as demands increase, the system should easily accept the addition of new resources to accommodate the increased demand.•Clusters vs Client/Server –Clusters: a collection of semi-autonomous machines that acts as a single system.-13Computation Speedup•Some tasks too large for even the fastest single computer–Real time weather/climate modeling, human genome project, fluid turbulence modeling, ocean circulation modeling, etc.–http://www.nersc.gov/research/GC/gcnersc.html•What to do?–Leave the problem unsolved?–Engineer a bigger/faster computer?–Harness resources of many smaller (commodity?) machines in a distributed system?-14Breaking up the problems•To harness computational speedup must first break up the big problem into many smaller problems•More art than science?–Sometimes break up by function•Pipeline?•Job queue?–Sometimes break up by data•Each node responsible for portion of data set?-15Decomposition Examples•Decrypting a message–Easily parallelizable, give each node a set of keys to try–Job queue – when tried all your keys go back for more?•Modeling ocean circulation–Give each node a portion of the ocean to model (N square ft region?)–Model flows within region locally–Communicate with nodes managing neighboring regions to model flows into other regions-16Decomposition Examples (con’t)•Barnes Hut – calculating effect of bodies in space on each other–Could divide space into NxN regions?–Some regions have many more bodies• Instead divide up so have roughly same number of bodies•Within a region, bodies have lots of effect on each other (close together)•Abstract other regions as a single body to minimize communication-17Linear Speedup•Linear speedup is often the goal. –Allocate N nodes to the job goes N times as fast•Once you’ve broken up the problem into N pieces, can you expect it to go N times as fast?–Are the pieces equal?–Is there a piece of the work that cannot be broken up (inherently sequential?)–Synchronization and communication overhead between