Lecture notes for CSC 2/456, 3 April 2000ff Network Operating Systems ========================= users aware of multiple machines (telnet, ftp) data/computation migration <== user responsible Distributed Operating Systems ============================= access to remote resources same as local data/computation migration under the control of the OS Data Migration ============== a. whole files (like automated ftp), eg. AFS first version b. on-demand (like demand-paging), eg. NFS, SMB, AFS newer versions tradeoffs between two methods Computation Migration ===================== a. RPC b. messages (more concurrency) Process Migration ================= natural extension from computation migration. reasons: * load balancing * computation speedup * h/w preference * s/w preference * data access either automated (transparent) or user specifies how the process should migrate Remote Services (RPC) ===================== message-based communication (UDP ?): send message to server (talk about ports), block, and wait for reply. kernels involved... message has a function id and arguments, reply has return value Semantics --------- RPCs can fail or be duplicated due to network errors. easier for OS to ensure that executed at leas once, than exactly once <== to solve use timestamps & history two ways of addressing functions: * fixed port number * "matchmaker" (show an RPC call using both methods on board) Threads ------- how can we use threads to build a server? * one thread to handle network (send/recv module) * server threads to handle requests (either thread pool with reuse, or create a new thread per request and then kill it) Light-weight RPC ---------------- we can do better if both ends on the same machine. use a-stack, and register to indicate function id. have the kernel map the a-stack to both processes (avoid copying). a-stack uses for return value too. Robustness ========== Failure Detection ----------------- ``i'm alive'' and ``are you alive?'' messages / timeout insufficient information to decide: 1) the message is lost 2) the link is down 3) the host is down give example of what one can do... point out there is no standard mechanism for handling this ==> theoretically we can never be sure Reconfiguration --------------- site/link failure information must be broadcasted if a server fails we need an election protocol what happens if it was a false alarm and now we have to servers running? (eg. locking server) Recovery -------- we need a graceful integration of a node in the rest of the system Design Issues ============= Transparency ------------ two extremes (network os vs. fully transparent) examples: small scale: NFS large scale: AFS (CMU), Athena (MIT), NSFv.4 (?) Fault Tolerance --------------- communicatin faults, machines failures, disk crashes should be tolerated. system should continue to work after a number of failures. very hard problem. most systems provide limited fault tolerance. Scalability ----------- performance should not degrade significantly (sublinear) when you add more nodes in the system. many systems have bottlenecks (pottential b/necks are centralized servers.) principle: service demand from any component should be constant, independent of the number of nodes ==> total symmetry !!! this is (usually) impossible. solution: clustering ------------------------------------------------------------------------ Event Ordering ============== I) Happened Before ------------------ a) A --> B, A executed before B, in same process b) A --> B, A send msg x, B recv msg x c) A --> B and B --> C, then A --> C (show & explain fig 18.1, pp 565) II) Implementation ------------------ a) global clock | b) perfectly sync clocks |==> impossible !!! ==> timestamps: virtual clock, eg. per process counter LC_i(A) < LC_j(B) ==> A --> B Mutual Exclusion ================ I) Centralized -------------- we have a server (request/reply/release). the caller is blocked waiting for reply. server is fair (eg. FIFO) ==> NO STARVATION 3 messages per critical section entry and exit II) Fully Distributed --------------------- P_j send request(P_j, TS_j) to all and wait for all to answer a) P_i in critical section ==> no reply b) P_i doesn't want to enter critical section ==> immediate reply c) P_i wants to enter critical section ==> compare timestamps Pros: a) mutual exclusion obtained b) no deadlock c) no starvation (timestamps == FIFO) d) number of messages is 2*(N-1) which is proven to be minimum Cons: a) the processes need to know all the others. when a process enters the group it has to receive the names of all the others, and all the others have to be notified about the new one. b) if one fails ==> the scheme collapses. solution: constant monitoring of all processes. c) processes not in critical section must pause to answer requests from others who wish to enter the critical section. III) Token Passing ------------------ * processes in a logical ring * pass the token around. when in critical section keep it. * if ring unidirectional then no starvation * number of message varies from 1 --> oo failures: a) token lost: election to generate new token b) node fails: establish new logical ring Concurrency Control =================== Timestamping ------------ a) centralized: one site generates timestamps b) distributed: ts is vector, order is significant! Deadlock Handling ================= I) Deadlock Prevention ---------------------- resource ordering & banker algorithm work here too (centralized) we can do better: assign priorities to processes. if P_i > P_j then P_i wait for P_j, else P_i rollback. The wait-for graph has no cycles. PROBLEM: starvation SOLUTION: use timestamps * wait-die : TS(P_i) < TS(P_j) ==> P_i wait else P_i rollback. * wound-wait: TS(P_i) > TS(P_j) ==> P_i wait else P_j rollback. THIS WORKS IFF THE TIMESTAMP OF THE ROLLED-BACK DOES NOT CHANGE PROBLEMS: the older you are the more you wait (wait-die). also you may have many rollbacks before you acquire the resource. II) Deadlock Detection ---------------------- Construct a wait-for graph. A cycle means deadlock. Local wait-for graphs local cycle ==> deadlock ( but <=/= ) no-deadlock <==> union of all locals acyclic. (a) Centralized deadlock-detection coordinator (distinction between real and constructed graph.) 3 points in time to build the graph: 1) an edge insert/delete in local graph 2) periodically after a number of changes on a local graph 3) when the coordinator invokes the cycle-detection algorithm problem with 1 & 2: unnecessary rollbacks due to (a) false cycles, (b) solve if we use timestamps with the 3rd option (see book.) (b) Fully Distributed local graphs extended with a P_ex node. * P_i --> P_ex if P_i waits for remote resource * P_ex --> P_i if some remote process(es) wait for P_i Election Algorithms =================== assume unique priority for each active process the coordinator is *always* the process with the highest priority two algorithms, both use N^2 messages: The Bully Algorithm ------------------- if coordinator times out (after T) send a message. if all timeout (after T) you're the one!!! if you get a reply, wait for T' for a new coordinator if you timeout again (after T') restart the algorithm whenever a process recovers from a failure it restarts the algorithm as soon as it joins the cluster The Ring Algorithm ------------------ unidirectional, logical ring. active list: list with all priorities of all active processes when the algorithm ends. 1) P_i detects coordinator failure. new empty a-list. send "elect(i)" and add "i" to list. 2) if P_i receives "elect(j)" (a) if this the first "elect" message, create new list with "i,j" and send "elect(i)", "elect(j)" (b) if i != j, add j to list, forward "elect(j)" (c) if i == j, a-list has all active nodes. the coordinator is the one with the highest priority number. ============================ Atomicity and 2-phase commit Locking protocols Agreement and "Byzantine" faults