Chapter 17 examines various mechanisms for process synchronization and communication, as well as methods for dealing with the deadlock problem, in a distributed environment. In addition, since a distributed system may suffer from a variety of failures that are not encountered in a centralized system, we also discuss here the issue of failure in a distributed system. | Chapter 17 Distributed Coordination I Event Ordering I Mutual Exclusion I Atomicity I Concurrency Control I Deadlock Handling I Election Algorithms I Reaching Agreement Operating System Concepts Silberschatz, Galvin and Gagne 2002 Event Ordering I Happened-before relation (denoted by →). ✦ If A and B are events in the same process, and A was executed before B, then A → B. ✦ If A is the event of sending a message by one process and B is the event of receiving that message by another process, then A → B. ✦ If A → B and B → C then A → C. Operating System Concepts Silberschatz, Galvin and Gagne 2002 Relative Time for Three Concurrent Processes Operating System Concepts Silberschatz, Galvin and Gagne 2002 Implementation of → I Associate a timestamp with each system event. Require that for every pair of events A and B, if A → B, then the timestamp of A is less than the timestamp of B. I Within each process Pi a logical clock, LCi is associated. The logical clock can be implemented as a simple counter that is incremented between any two successive events executed within a process. I A process advances its logical clock when it receives a message whose timestamp is greater than the current value of its logical clock. I If the timestamps of two events A and B are the same, then the events are concurrent. We may use the process identity numbers to break ties and to create a total ordering. Operating System Concepts Silberschatz, Galvin and Gagne 2002 Distributed Mutual Exclusion (DME) I Assumptions ✦ The system consists of n processes; each process Pi resides at a different processor. ✦ Each process has a critical section that requires mutual exclusion. I Requirement ✦ If Pi is executing in its critical section, then no other process Pj is executing in its critical section. I We present two algorithms to ensure the mutual exclusion execution of processes in their critical sections. Operating System Concepts Silberschatz, .
