Hello Friends! Welcome to GATE SMASHERS! The topic is Banker's Algorithm in Operating System We also call it as Deadlock Avoidance Algorithm As we have to provide information to the Operating System beforehand about the upcoming processes, their request of resources, their count and their delay So that the Operating System decides on which process sequence should be executed or awaited We call Banker's algorithm as Deadlock Avoidance algorithm Many a times it is being asked in the theory if Banker's algorithm is for Deadlock Prevention or Avoidance Banker's algorithm is for Deadlock Avoidance Other than this, Banker's Algorithm is also used for Deadlock Detection Detection means it helps us to find if there is any possibility of deadlock occurrence between processes in the future And this is asked in all competitive exams where you will be given a scenario In which processes are given like here we have 5 processes that are requesting some resources And resources are, like here we have three namely A, B and C which may be physical similar to CPU, Memory and Cache And these five processes are requesting for these resources of their individual needs And on this basis, applying the Banker's algorithm, we have have to find out whether deadlock occurs or not So that's why we call it Deadlock Detection Algorithm So we have to check in this scenario whether deadlock occurs or not, if no then we have to find why not? Now here we have processes P1, P2, P3, P4 and P5 with resources A, B and C These resources are of three types like let's pose A is CPU, B is Memory and C is Printer The name can be any (say R1, R2 and R3) and we assume here A = 10, B = 5 and C = 7, in the sense 10 CPUs, 5 Memories and 7 Printers So the number of resources are already given Other than that, we are given Allocation which means the given amount of resource is allocated to respective process Means no unit amount of A is allocated to P1 but B is allocated 1 instance of P1 like we call here the unit amount as instance Now we have 10 instances of A or CPU, 5 instances of B or Memory and 7 instances of C or Printer Now all are considered same if I call it number or instance. Here P1 is not allocated of any instance as of now. B is allocated 1 instance and C is not allocated any instance Likewise P2 is allocated 2 0 0. P3 is allocated 3 0 2. P4 is allocated 2 1 1. P5 is allocated 0 0 2. So this is allocation which tells how many resources are allocated to each process with which we are going to see Max Need that allocates max. resources to processes Now this is the main point why we call Banker's problem a deadlock avoidance one because the process tells the system how much resources it needs at most If P1 is given 7 5 3 it will be executed and terminated Similarly P2 and P3 convey their maximum needs Maximum need is when P3 conveys its need of A being 9, B being 0 and C being 2 which means if these are allocated to P2 it will be successfully executed and terminated So maximum need is allocation of maximum requirement of resources to processes And P4 and P5 also have reported their respective maximum needs of resources But now the main question starts (ie) if a deadlock exists or not. If yes then if it is safe or unsafe If it is safe then no deadlock. If unsafe then deadlock exists. So when deadlock occurs then question is simple that there exists deadlock, if not it is safe If no deadlock then we call it Safe Sequence which means we sequentially arrange processes with resources If we solve this problem we will get to know Now next comes Available which means The total availability of resources Here we have 10, 5 and 7 resources But resources are allocated already as because we are starting the reading at a particular point of time and not from 0. Then processes are allocated the required resources where total are this much So Available = Total - Allocation Now let's total the Allocation values Calculating A = 0 + 2 + 3 + 2 + 0 = total 7 Already 7 resources of A are allocated. Now B = 1 + 1 = 2 resources of B as well And C = 2 + 1 + 2 = 5 resources So this is A B C = 7 2 5 resource allocation And total A = 10 but allocated A = 7 Allocated B = 2 and C = 5 Already we allocated 7 out of 10 of A and the remaining will be 3 A = 10 - 7 = 3 and B = 5 - 2 = 3 and C = 7 - 5 = 2 Now we have this much available that we call 'Current' in which we have 3 3 2 And next part is Remaining Need in the sense we have allocated some resources to processes out of Max Need then the remaining amount or instance is called Remaining Need So Remaining Need = Max Need - Allocation We would have come across a question in Maths during childhood which goes a child is given 3 apples but he needs 10 apples so more 7 apples are to be given. So that's what is exactly explained here That I have already allocated some here beyond which the processes have told that this is their maximum need. After that we calculate Remaining Need Now Remaining Need of A = 7 - 0 = 7
Remaining Need of B = 5 - 1 = 4
Remaining Need of C = 3 - 0 = 3 for P1 Now Remaining Need of A = 3 - 2 = 1
Remaining Need of B = 2 - 0 = 2
Remaining Need of C = 2 - 0 = 2 for P2 Which means Remaining Need = Max Need - Allocation Now Remaining Need of A = 9 - 3 = 6
Remaining Need of B = 0 - 0 = 0
Remaining Need of C = 2 - 2 = 0 for P3 But be careful and make sure while calculating you are subtracting only the corresponding A, B and C values because silly mistakes may happen at times Now Remaining Need of A = 4 - 2 = 2
Remaining Need of B = 2 - 1 = 1
Remaining Need of C = 2 - 1 = 1 for P4 Now Remaining Need of A = 5 - 0 = 5
Remaining Need of B = 3 - 0 = 3
Remaining Need of C = 3 - 2 = 1 for P5 So this is the remaining need which we need to calculate carefully The remaining needs of processes P1, P2, P3, P4 and P5 are written here Now comes Availability which has A = 3, B = 3 and C = 2 in total Which means if I can fulfill any of the remaining needs with my available instances Now let's take P1 where A has 3 out of 7 needs, B has 3 out of 4 needs and C has 2 out of 3 needs that implies I can't fulfill the remaining needs of P1 as I have low amounts and so P1 will not be in the sequence anymore Now before we check P2 if any of these resources have shortage of resources that means we have more chances of deadlock occurrence Now let's take P2 where A has only 1 need where we have 3, B has 2 needs but we have 3 and C has 2 needs and we have 2 that implies I can fulfill the remaining needs of P2 Now let's pose we have A = 4 instead of 1 so we need to be careful as at a time all resources have to be filled with the available amounts equally or the system would become complex which means the remaining need should be less or equal to available, else we go to next process Now in P3 if A needs 6 but we have 3, B needs 0 and we have 3, C needs 0 and we have 2, we might think that B and C can be filled but A? No way so you have to be careful on such statures Now if we come back to P2 we need 1 2 2 and we have 3 3 2 available which means we will be able to fulfill the needs Now in terms of sequence the first process to enter in with all needs fulfilled is P2 As we have fulfilled the needs of P2 it will be successfully executed because the remaining needs were less compared to available resources so it gets terminated after execution If P2 is terminated then the allocated resources of P2 will automatically be released and let free So if set free it will be immediately added on to the Available amount of resources like A B C were 3 3 2 now it becomes 5 3 2 Now that the Available resource instances has been increased the P2 process after execution and termination will be removed from the sequence So let's see P3 now can the Available resource instances A=5, B=3, C=2 fulfill the resources of A=6, B=0, C=0 in P3? Not possible as we have less Available at A, so we have check all (ie) A, B and C Now let's take P4 where A has only 2 need where we have 5, B has 1 need but we have 3 and C has 1 need and we have 2 that implies I can fulfill the remaining needs of P4 and next process to get into the sequence is P4 P4 has been executed as the Remaining Needs were less than Available resources so we have to apply the formula "Remaining Need <= Current Availability" for all resources not for any individual resource alone And we have fulfilled the needs of P4 so it got terminated successfully So after P4 is terminated then its allocated resources A=2, B=1, C=1 will be let free as termination marks all resources a process carried to be released So if resources of P4 are released then A B C = 5 3 2 becomes A B C = 7 4 3 at present Now let's check P5. As we are actually going by an order we are checking so but if need be the case we can check P1 and P3 also but as of now we are following an order in which P5 is considered here Now in P5 where A has 5 needs where we have 7, B has 3 needs but we have 4 and C has 1 needs and we have 3 that implies I can fulfill the remaining needs of P5 and easily execute and terminate it And the next in my sequence of executed processes comes P5 So if resources of P5 are released then A B C = 7 4 3 becomes A B C = 7 4 5 at present Now let's check back from P1 We can check P3 as well nothing wrong. Sequence can extend to any count but no deadlock should occur in between which should be ensured Now in P1 where A has 7 needs where we have 7, B has 4 needs but we have 4 and C has 3 needs and we have 5 that implies I can fulfill the remaining needs of P1 and easily execute and terminate it And the next in my sequence of executed processes comes P1. So if resources of P1 are released then A B C = 7 4 5 becomes A B C = 7 5 5 at present Now the last is P3 where A has 6 needs where we have 7, B and C have 0 need but we have 5 each that implies I can fulfill the remaining needs of P3 and easily execute and terminate it adding to the sequence So if resources of P3 are released then A B C = 7 4 5 becomes A B C = 10 5 7 at present which sums up to the total number of resources that we had at the beginning where we created a Safe Sequence of Processes simultaneously Why is it a Safe Sequence? Because deadlock has not occurred anywhere So the sequence P2, P4, P5, P1, P3 is not unique as the values could have swapped but it is being asked in the exams with a given sequences that where deadlock does not occur and if at least one process doesn't create deadlock it gets into the sequence instantly So this is what we call Deadlock Avoidance And in deadlock avoidance as discussed earlier that we should feed and allocate the resources to respective processes beforehand like in Maximum Need So if we consider real life scenarios in this algorithm then it is not possible as the needs are dynamic in nature, not static like here the needs are already allocated which we can work the code in C programming So in real life we have to create some base setup to implement due to which it is an important algorithm Because it is asked many times in GATE and other competitive exams so practise this algorithm to perfection And second we call it Deadlock Detection algorithm as we find out if deadlock occurs or not. If yes then answer ends there and of no we have to find the safe sequence and write down the result of the same And if you liked this video please like it, share it and subscribe to my channel. Thank You!
