TAILIEUCHUNG - Operating System Concepts (18)

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 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 and Galvin 1999 DME: 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 and Galvin 1999 DME: 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

• Sáng kiến kinh nghiệm
• Operating system concepts
• Lecture Operating system concepts
• Operating system
• Operating system services
• Operating system structures
• Operating system design
• Operating system structure
• Hệ điều hành
• Lecture Operating system principles
• Computer system
• Modern operating systems
• Evolution of operating systems
• Multiprocessor operating systems
• Operating systems
• Lecture Operating systems
• Structure of operating systems
• Distributed operating systems
• Memory management
• Computer system organization
• Operating system concept
• File systems
• Operating systems design
• Operating systems capabilities
• Network operating system
• Operating System Debugging
• Operating System Generation
• Types of System Calls
• Bài giảng Hệ điều hành
• Lecture Advanced Operating Systems
• Advanced Operating Systems
• Bài giảng Hệ điều hành nâng cao
• Server operating systems
• PC operating systems
• Main frame operating systems
• Real time operating systems
• History of operating systems
• The operating system zoo
• Computer hardware review
• System calls
• Computer system structures
• Operations on processes
• Thread libraries
• CPU scheduling
• Process synchronization
• Handling deadlocks
• Virtual memory
• File system interface
• File system implementation
• Application I O interface
• Mass storage systems