Coordination of Processes in Distributed Systems
- If there is more than one process ready to run, the operating system will determine one process to run first. • Therefore good scheduling is needed in process management. • Fairness – Ensuring that each process gets the same and fair turn • Efficiency – Using CPU time as optimal as possible • Respontime – Speeding up response time with users interactively • Turn around time – Minimizing waiting time from the start of the process until the process finishes running • Through out – Maximizing the number of jobs that can be processed unity of time • In coordination between processes in a distributed system the system can deadlock • A deadlock system is a condition where 2 or more processes cannot continue their execution • Causes of deadlock include: – Mutual Exclusion – Hold & Wait – No Preemption – Circular Wait • Mutual Exclusion – If a process has used a resource, then no other process can use that resource • Hold & Wait – When a process is accessing a resource, the process can ask permission to access another resource • No Preemption – If a process requests permission to access the resource, sement the resource can be canceled • Circular Wait – If process P0 is accessing resource R1 and requests permission to access resource R2 while at the same time P1 is accessing resource R0 and requests permission to access R1 • Coordination management between processes in different distributed systems in a centralized system • Some parameters that need to be considered include: – Not a single memory & clock – It is not possible to declare a sequence of two events – Only partial ordering can be determined (Happened-Before part relation): • Happened-before relation is a relation that pays attention to the sequence of events, because the events that are related to each other • In the happened-before relation apply: – sequential processes Legal causation – The symbol of the happened-before relation is the arrow symbol “→” • If the A & B event is in a process and A is executed before B, then it is written A → B • If A is an event of sending by a process and B is an event receiving the message (receiving) by another process, then written A → B (sending is done before receiving) • If A → B and B → C, then A → C • Because an event cannot occur before itself occurs , then the happened-before relation is not reflective (attached to itself) • If 2 A & B events do not fulfill the relation → R, then both events are executed concurrently • The concurrency & happened-before is explained using a space-time diagram • The horizontal direction represents space (the process is different) • The vertical direction represents time • Vertical lines indicate the processor (uppercase) and small circles show events (lowercase) • Wave lines indicate the sender of the message / path • For events concurrent there is no path between the two Examples: • A number of events associated with happenedbefore: p1 → q2, r0 → q4, q3 → r1, p1 → q4 • A number of concurrent events from the system are q0 and p2, r0 and q3, r3 and p3, q3 and p3 • Event p on processor P, q on Q, and r on R • To determine event A to occur before event B requires a general clock or a perfect synchronizer clock set • In coordinating management of processes on a distributed system these two things are not possible done • So we need a special definition of the relation happened before without using clock physics • For management of coordination between processes in a distributed system known the concept of Timestamp • Timestamp for an event is a logical clock value for the event • Where each system event is associated with a timestamp, then defined Global Ordering Requirements (GOR) • For each pair of events A & B applies, if A → B then the timestamp A ˂ timestamp B • First define in each Pi process a logical clock (LCi) • Where LCi can be implemented as a simple couter incremented between 2 events executed sequentially in a process • LCi can show event numbers uniquely, so that if an event occurs before event B in the Pi process, then LCi ( A) ˂ LCi (B) • For example there are 2 processes P1 and P2 that are communicating: – P1 sends a message to P2 and LCi event A ＝ 200 – P2 receives a message and Lci event B ＝ 192 – Assumes the P2 process is slower than the P1 process • In the example they can confuse GOR, because if A → B, then LCi (A) ˂ LCi (B) • Therefore the solution needed is the process of advancing the LCi if receiving a message with a timestamp is greater than the recipient LCi • How: if the Pi process receives a message (event B) with a timestamp ＝ t and LCi (B) ˂ ＝ t, then the process must raise the clock, which is equal to: LCi (B) ＝ t + 1 • Is a condition where the resource (resource ) cannot be shared with users • Mutual exclusion can occur because of : – No two processes are at the same time in a critical section – There are no processes that run outside the critical section that can inhibit other processes – There is no process that can not enter into the critical section – The condition is overcome by using several types of algorithms in Mutual Exclusion • Centralized Distributed Approach (CDA) • Fully Distributed Approach (FDA) • Token Parsing Approach (TPA)