Ho-Ramamoorthy Path Pushing Algorithm

Ho-Ramamoorthy path pushing algorithm There are two kinds of protocols, one is one-phase algorithm, another is two-phase algorithm, right? So, let’s see the algorithm and the various steps first, and I will tell you which steps are covered in one-phase algorithm and what additional steps are covered in two-phase algorithm, right? So, the first step, whether in two-phase or one-phase, is: Step 1: Each local site has a status table, right? So, each local site has a status table that includes whatever resources the site already has and the processes happening on that local site. So, you know, every site has some local processes, isn’t it? So, those processes, and also the local site, have their own resources too, okay? This status table indicates what resources are locked by the processes and which processes are waiting for whichever resources, right? So, this is what actually the status table does. The status table includes: • • The locked resources The resources being waited for And there will always be a global controller, which takes responsibility for constructing the wait-for graph and detecting deadlocks, okay? There will be one among the local sites that will be nominated as a global controller site, whose responsibility is to construct the wait-for graph and detect deadlocks. So, the global controller, as a whole responsible site, will request the status table, which is maintained by every individual site. It will send a request message for the status table to all the other sites. On receiving this status table request message, every site will respond, isn’t it? By responding, they send their own status table to the global controller. On receiving the status table, the controller will construct a wait-for graph (WFG). Once the wait-for graph is constructed, the controller will check whether any cycles exist, right? • • If so, the deadlock is detected, right? Otherwise, if there is no cycle, then there is no deadlock. Now, coming to the third step, which is not happening in the one-phase algorithm, right? It happens only in the two-phase algorithm, okay? Once the first wait-for graph is constructed and a cycle is found, the global controller detects a deadlock, but it is not yet confirmed. So, it requests again later, after some time, for the status table to confirm the deadlock. On receiving the status table again, the controller will construct one more wait-for graph, but this time only for common requests, right? If there are any local requests, they will not be included in the wait-for graph. Local request means, for example, if there is a resource that is locked by a local resource itself (Site 1) and requested by a process of Site 2, the local cycle exists. If a cycle exists, then confirm a deadlock. So, this is what is known as the Chandy-Misra-Haas algorithm. The first two steps consist of the one-phase algorithm, and all the remaining steps make up the complete algorithm. Right, as usual, I said, let’s have Site One and another Site Two under Control Site. Site One has its own status table, okay? So, this is the status table for Site One, which includes the resources already locked and the resources the process is waiting for, right? So, let’s say Site One has three processes: P1, P2, and P3. • • • P1 has already locked resource R1 and is waiting for resource R4. P2 has already locked R2 and is waiting for R3. P3 has already locked R3 and is waiting for R4. Look at this: • • • R1 is the resource of P1, a local resource. R2 is the local resource of P2. R3 is local for P3, okay? Now, coming to Site Two, the status table (ST) of Site Two is here. Site Two has two processes: P4 and P5. • P4 is holding resource R4, which is locked by itself, and is waiting for R5, • P5 is waiting for R5 and then waiting for R1, right? right? So, this is the initial state. Now, as per our algorithm, the Control Site sends a request message for the status table to both the local sites. On receiving this request, both Site One and Site Two will respond with their status tables, okay? Now, what happens? On receiving the status tables of Site One and Site Two, this is what happens in one-phase construction (one-phase algorithm). Our graph is constructed: There are five processes: P1, P2, P3, P4, and P5. Now, look at this: • • • • • P1 is requesting R4, which P4 holds. P2 is locking R2 but requesting R3, which is the resource of P3. P2 is requesting R3, and P3 is requesting R4, okay? P4 is requesting R5. P5 is requesting R1, which is locked by P1, right? So, this is the wait-for graph. This is the first graph, okay? Now, look at this graph—there is a cycle, right? So, now what happens? The Control Site detects a deadlock, right? So, deadlock detected, right? Next step: One-phase algorithm will not stop with this step. It has one more step, which is the second phase, where again one more request will be sent. So, in the two-phase algorithm, the Control Site again requests for the status table (ST), right? So, this is Request 2 for ST, and it is also requesting this site, okay? So, this is Request 2 for ST, okay? This time, the sites respond again. So, ST2 will be sent here. Also, ST2 will be sent again. On receiving the new status tables (STs), what happens here? Right, so the sites, as per the status table, have local resources. • • R1 is waiting for R4. R3 is waiting for R4, right? So, there is a common waiting. The common request: • R4 is waiting for R5, but R5 is waiting for R1. So, there is an inter-site waiting request, right? Now: • • • • P1 (Process 1) is waiting for R4, which is already held by P4. P3 (Process 3) is waiting for R4 (which is a common request). P4 (Process 4) is waiting for R5, which is already held by P5. P5 (Process 5) is waiting for R1, right? So, this is the case, okay? Now, because there is again a deadlock, a deadlock is detected. So, the deadlock detector finds a cycle, and again, the deadlock is confirmed. Now, the deadlock is confirmed, okay? So, that is how the second phase works. Now, you might have one more doubt. Since P3 and P4 are waiting for a local resource, why is this considered a deadlock? Because R5 is available locally.