Before We Begin CSE 120 Principles of Operating Systems Read Chapters 15 17 on Distributed Systems topics Lecture 13 Distributed Systems December 2 2003 Prof Joe Pasquale Department of Computer Science and Engineering University of California San Diego 2003 by Joseph Pasquale 2 1 What is a Distributed System Advantages Computers connected by a network that can cooperate Degree of integration may be loose Speed more resources parallelism less contention Reliability resource redundancy fault tolerance messages between inter machine processes Scalability incremental growth can start cheap email ftp Or it may be medium network operating system remotely execute cmds cross mount file systems Or it may be tight distributed operating system Economy of scale amortizing cost of shared resources Geographic distribution communication reliability process migration distributed file system 3 4 Disadvantages Which is Better Global state uncertainty Single fast server with no shared memory single queue no shared clock Multiple slower servers Simultaneous decisions may conflict with separate queues mutually conflicting decision problem Multiple slower servers Distributed algorithms are complex with single queue all interactions via messages no shared memory distributed debugging is difficult 2 2 2 2 2 2 Little s Law N W 5 Performance Load Balancing 6 Reliability File Replication Load average number of runnable processes Maintain multiple copies of files on separate nodes Keep load balanced across all nodes When file requested obtain from node having copy primary and backup When process created consider where to run all nodes are equal node where it was submitted node that is least loaded Improves availability and maybe even performance random selection Problem updates If load becomes unbalanced migrate processes when a file is written how are copies updated may be more trouble than worth 7 8 The Client Server Model Client Client Peer to Peer Peer to peer is typically dynamic client server Server a node may act as a client or server other peer to peer relationships are possible Short lived process that makes requests Example peer to peer file sharing User side of application Client A requests file from server B Server Exports well defined requests response interface Long lived process that waits for requests Upon receiving request carries it out may spawn Server B provides file to client A Client C can request file from A or B say A A formerly a client now acts as server 9 10 Distributed File Systems Event Ordering What is order of events given no shared clock memory File service file system interface for remote clients Happened before relation File server machine s that provides file service A B events of same process and A before B A B storage devices connected to file server A is a send event B is a receive event A B Issues If A B and B C then A C Naming location transparency and independence Caching client caches server caches consistency State stateful vs stateless file service Implementation Timestamp all events based on local clock Upon receiving a message advance local clock Replication number of replicas updating 11 Resolve ties by ordering machines 12 Mutual Exclusion Atomic Transactions Centralized approach Program unit that must be executed atomically single process acts as coordinator server executed to completion or not at all request reply to allow entrance release Distributed transactions Distributed approach process sends a request with TS to all processes waits until it receives all replies ok to enter enter critical section may get requests defers upon exiting responds to release to all deferred TS used to order simultaneous requests transactions broken into multiple sub transactions sub transactions executed on different machines To make distributed transaction atomic have all sub transactions execute run two phase commit protocol 13 14 Two Phase Commit Protocol Stable Storage Phase 1 Uses multiple storage devs independent failure modes Coordinator logs prepare T sends to all sites Each logical block has 2 or more physical blocks At each site upon receiving prepare T To write write first block if successful write second either log no T reply or log ready T reply Write is successful only if all succeed Phase 2 C waits to receive all responses or times out If all responses are ready T commit else abort Log decision and send decision to all sites Recovery If no detectable errors and blocks same all is ok If detectable error in one block copy good to bad If no errors but blocks different copy 2nd to 1st Log to stable storage 15 16 Leader Election Byzantine Generals Problem Many distributed algs rely on a leader e g coordinator Need to determine whether leader exists if not elect Bully algorithm elects leader L Divisions of Byzantine army surround enemy camp generals must agree whether to attack at dawn all must agree if only some attack defeat Generals can only communicate via messengers Every process is numbered priority P1 P2 Pi sends request to L no reply tries to elect itself Pi sends election msg to all Pj j i wait for replies No replies Pi becomes L sends msgs to Pj j i If some Pj replies then Pi waits for election msg If no election msg Pi restarts election algorithm 17 Messengers may get captured unreliable comm Generals may be traitors faulty processors Can t create reliable comm from unreliable parts Can overcome faulty procs if n 3m 1 m of n faulty 18
View Full Document
Unlocking...