tailieunhanh - Lecture Operating system concepts - Module 18

After studying this chapter, you should be able to: Discuss basic concepts related to concurrency, such as race conditions, OS concerns, and mutual exclusion requirements; understand hardware approaches to supporting mutual exclusion; define and explain semaphores; define and explain monitors. | Module 18: Distributed Coordination Event Ordering Mutual Exclusion Atomicity Concurrency Control Deadlock Handling Election Algorithms Reaching Agreement Operating System Concepts 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. Operating System Concepts 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 | Module 18: Distributed Coordination Event Ordering Mutual Exclusion Atomicity Concurrency Control Deadlock Handling Election Algorithms Reaching Agreement Operating System Concepts 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. Operating System Concepts 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. Operating System Concepts 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. Operating System Concepts 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