tailieunhanh - Lecture Operating system concepts (Fifth edition): Module 18 - Avi Silberschatz, Peter Galvin

Module 18 - Distributed coordination. Chapter 18 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. | Lecture Operating system concepts Fifth edition Module 18 - Avi Silberschatz Peter Galvin Module 18 Distributed Coordination Event Ordering Mutual Exclusion Atomicity Concurrency Control Deadlock Handling Election Algorithms Reaching Agreement Silberschatz and Galvin 1999 Event Ordering 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. Silberschatz and Galvin 1999 Implementation of 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. 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. A process advances its logical clock when it receives a message whose timestamp is greater than the current value of its logical clock. 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. Silberschatz and Galvin 1999 Distributed Mutual Exclusion DME 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. Requirement If Pi is executing in its critical section then no other process Pj is executing in its critical section. We present two algorithms to ensure the mutual exclusion execution of processes in their critical sections. Silberschatz and Galvin 1999 DME Centralized Approach One of the processes in the system is chosen to coordinate the entry to the critical section. A process that wants to enter its critical section sends a request message to the coordinator. The coordinator