TAILIEUCHUNG - Operating System Concepts ppt (17)
Chapter 17 Distributed Coordination Event Ordering. Mutual Exclusion. Atomicity. Concurrency Control. Deadlock Handling. Election Algorithms. Reaching Agreement. Silberschatz, Galvin and Gagne 2002Event 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, Galvin and Gagne 2002Relative Time for Three Concurrent Processes. Silberschatz, Galvin and Gagne 2002Implementation 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, Galvin and Gagne 2002Distributed 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, Galvin and Gagne 2002DME: 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 decides which process can enter the. critical section next, and its sends that process a reply. message When the process receives a reply message from the. coordinator, it enters its critical section After exiting its critical section, the process sends a. release message to the coordinator and proceeds with its. execution This scheme requires three messages per critical-section. entry:. request. reply. release. Silberschatz, Galvin and Gagne 2002DME: Fully Distributed Approach When process Pi wants to enter its critical section, it. generates a new timestamp, TS, and sends the message. request (Pi, TS) to all other processes in the system When process Pj receives a request message, it may. reply immediately or it may defer sending a reply back When process Pi receives a reply message from all other. processes in the system, it can enter its critical section After exiting its critical section, the process sends reply. messages to all its deferred requests Silberschatz, Galvin and Gagne 2002DME: Fully Distributed Approach (Cont.). The decision whether process Pj replies immediately to a. request(Pi, TS) message or defers its reply is based on. three factors:. If Pj is in its critical section, then it defers its reply to Pi If Pj does not want to enter its critical section, then it sends a. reply immediately to Pi If Pj wants to enter its critical section but has not yet entered. it, then it compares its own request timestamp with the. timestamp TS If its own request timestamp is greater
đang nạp các trang xem trước
