L-4.5: Deadlock Avoidance Banker’s Algorithm with Example |With English Subtitles

Hello Friends, Welcome to GATE Smashers. The topic is Banker's Algorithm in Operating System. We also call Banker's Algorithm as Deadlock Avoidance Algorithm. The reason is that in Deadlock Avoidance we have to provide information to the Operating System beforehand which processes are coming, which processes will request for which resources, how many resources will they request, for how long will they do it, means I have to give information to the system beforehand so that the system performs accordingly and decides which process to perform and which process to not perform and make it wait. So Banker's algorithm, Deadlock Avoidance Many times it is being asked in theory whether it is a Deadlock Prevention or Deadlock Avoidance algorithm, Banker's is a Deadlock Avoidance algorithm. Other than this, it is also used for Deadlock Detection Detection means like we can detect in the system whether deadlock can occur in future or not, And question on this has been asked many times in GATE and all competitive exams where you are given a scenario, like number of processes like in this I have given you 5 processes, and all of these 5 are requesting some resources and some number, means how many like in this there are three resources A, B and C, different different kind of resources whether they are physical resources or logical resources like CPU, Memory, Cache, they are all what? Resources.

Like in this, there are three resources A, B and C. So five processes are requesting for these resources and along with that they are telling their needs that how much more we need. And on this basis we have to find out at the end, Banker's algorithm at the end shows whether deadlock occurs or not. So that's why we call it Deadlock Detection Algorithm So we check in this scenario whether deadlock can be detected or not, and why will it not occur? What is the reason of that? Like in this we have 5 processes P1, P2, P3, P4 and P5 and A, B and C are 3 resources.

These are of three resources types like A is you can say CPU, B is you can say Memory and C can be Printer. You can say any resources, it can be R1, R2, R3. A, B, C are 3 different types of resources, and we have in system 10 resources of A, 5 of B, 7 of C. Means we have 10 CPUs, 5 Memories and 7 Printers. Total we have how many resources in what number is given.

Other than that, what we are given here? Allocation. What is the meaning of allocation? Like which process has been already allocated how many resources by the system. Means no resource of A is allocated to P1 but 1 instance of B, we can call this instance like we have 10 instances of A, 5 instances of B and 7 instances of C or you can simply say that there are 10 CPUs, 5 Memories, 7 Printers. Whether you call it instance or number that is the same thing. So here what information is this giving? P1 process has 0 instance of A, means no CPU has been allocated yet. This is allocated, already allocated or not.

1 instance of B is allocated and C is 0. Similarly P2 is already allocated 2 instances of A, 0, 0. P3 is allocated 3, 0, 2. P4 has 2, 1, 1. P5 0, 0, 2 means 2 instances of C are allocated. So this is allocation, allocation tells how many resources system has already given to a particular process. Along with that what we are given? Maximum Need. Maximum Need means which process needs how many resources. This is the main point. This is why we call it a deadlock avoidance because we tell the system beforehand, P1 tells beforehand that I want 7 resources of A, 5 of B and 3 of C. If you give me these then I will be successfully executed and terminated Similarly P2 process also tells its demand of resources and P3 also tells its maximum demand or maximum needs of resources. Maximum need means like what is maximum need of P3? 9, 0, 2, means P3 says that give me 9 instances of A, I don't want any instance of B, and give me 2 instances of C. If you fulfil these needs then I will be successfully executed. So this is the way that, what is meaning of maximum need? How many maximum instances they want.

And P4, P5 all 5 have told their respective maximum needs. Now our main question starts, in question they can ask to show if there is a deadlock or not. If there is a deadlock then simply you can say that this is unsafe. We call it safe or unsafe. Safe means deadlock will not occur. And unsafe means deadlock will occur. So if deadlock occurs then your question, simple, finishes that there is a deadlock. Or if second can be that deadlock does not occur. If deadlock does not occur then its sequence comes which we call Safe Sequence. Safe Sequence means how do we sequence resources and processes so that deadlock doesn't occur. This when we solve this then we will see. Available. The third thing is Available, Available means how much is the total availability of resources we have.

Total we have 10, 5 and 7 But already system has allocated some resources means system has already allocated some because we are not starting from zero time, we are talking about at a particular point of time so at a particular point of time already some resources system has given to particular processes. and total we have these many. So what will be available? Total – Allocation. Means let's take the total of Allocation here A is 0, 2, 3, 2 means 2 + 3 = 5, +2 = 7. Already 7 resources of A are allocated. B, 1 + 1 = 2. And C, 2 + 1 + 2 = 5. So this what? 7, 2, 5 is what? 7 resources of A are already allocated, 2 resources of B, 5 resources of C are already allocated. And how many total A we have? 10. And how many are already allocated? 7, B, 2 and C, 5. So total we had 10 out of which we have already given 7, so how many remain? 3. 10-7 that is 3, 5-2 that is 3 and 7-5 that is 2. So this is our at present availability, means at present or we can call it Current, current availability is how much? 3, 3, 2.

And the next part is Remaining Need. What is the meaning of Remaining Need? Like we did here, allocation, means I have allocated some resources And system shows that processes have this much maximum need, this is their maximum need, And from maximum need if we subtract already allocated then what do we have left? Remaining Need. Means from maximum need we subtract allocation, so how much we have left? Remaining Need. Like many times we have questions in Maths when we were little at that time questions used to come like if I give a child 3 apples but he needs 10 apples so I will have to give him 7 more apples means if 3 apples I have already given, but the child says I want 10 apples, So I will provide him 7 more apples that's what we are saying here.

That I have already allocated some, maximum need it told me that I need this much, if you fulfil my need then I will be successfully executed. So I will calculate Remaining Need. How? By maximum – allocation. So P1, how much is maximum need? 7. But already how many are given? 0. Means nothing has been given yet. So means Remaining Need is still 7. B, 5 but here I have already given 1, so 5-1 that is 4. It needs 3 resources of C but how many are already given? Nothing is given yet, so 0. So means its need is still 3. Similarly if we talk about P2, P2 says I need 3 resources of A, already 2 resources are given so how many remaining? 1. For B, it needs 2, how many are given? 0, so 2.

Similarly 2 of C. So simply from Maximum Need if you subtract Allocation then we can find Remaining Need. So in the same way we find for P3, 9-3 that is 6, 0-0=0, 2-2=0. Just be little careful when you calculate then A from A, B from B, C from C. Otherwise many times here mistakes may happen in calculation, so be careful here. Similarly if we see P4, 4-2 that is 2, 2-1 that is 1, 2-1 that is 1. P5, for P5 it is 5-0=5, no resource is given yet, all 5 are needed, it needs all 3, already given 2 so only 1 resource is remaining. So this is the remaining need, remaining need you need to calculate carefully. So this is the remaining need of all the processes P1, P2, P3, P4 and P5.

So remaining need of all 5 is written here. Now availability, now what do we have at present available in the system, 3 resources of A, 3 resources of B, 2 resources of C. So now we have to check if according to my availability I can fulfil any of the remaining needs. How, let's say P1 needs 7 resources of A, so do I have 7 resources now? No, we have only 3 resources, needs 4 of B, how many do we have? 3, needs 3 of C, how many I have? 2. Means I can't fulfil the remaining needs of P1 because I have less availability.

So means P1 will not be in the sequence. So if here we check P2 next, but if let's say we cannot fulfil the need of all the processes, then we can simply say deadlock will occur in this. Like P2, what is the remaining need of P2? It needs 1 resource, we have 3, it needs 2 resources of B, we have 3, it needs 2 resources of C, we have 2, yes, so I can fulfil the remaining needs of P2. But let's say if here in case instead of 1 it was 4, then could I do? No. This here is a very important point because here what would be remaining need of P2? 4. And how many resources I have? 3. 2 of B, and I have 3, 2 here and I have 2, so you may think that I can give C because it needs 2 of C and I have 2, but guys you have to provide all 3 resources at the same time, otherwise you will make the system more complex.

Means the remaining need of all resources should match this, means either equal to or less than that. Means whatever the remaining need it should be either equal to or less than total available. If that happens then that is fine otherwise we will check next process. So here value was 1, so we will follow with 1, that is just for the explanation. P3, remaining of P3 is what? 6. But how many resources of A we have? 3. 0, we have 3, 0, we have 2 available. So you may think that yes, I can give B and C because it doesn't need B and C and we have freely available, But A, how many A? 6.

It is saying I need 6 CPUs, can we give 6 CPUs? No. You have only 3 CPUs. So means we cannot fulfil this. So you have to be little careful on this point. Now if we talk about P2 again, remaining need of P2 is what? 1, 2, 2 and we have 3, 3, 2 so easily we can fulfil the needs of P2. So if I talk about sequence, the first process whose need we fulfilled, that becomes P2.

So when we fulfilled the need of P2, it will be successfully executed because it says I need 1, 2, 2, 1 of A, 2 of B and 2 of C resources and I have 3, 3, 2 available which is more than its remaining need, so it will successfully take all resources and get terminated. When P2 is terminated then the resources already with P2, it will release. When P2 gets the remaining resources and it is successfully executed then those which it has already taken in allocation those will also be free, all resources get free, So means this was holding 2 resources, they are now free, so add it to available.

Means in available 2, 0, 0, we will add 2, 0, 0 in available because those which it was already holding will be released. So how many are total? 5, 3, 2. So those which it was already holding in advance in allocation those resources are also released. So now my availability is increased, availability becomes what? 5, 3, 2. And out of this our process P2 exits from here. Because we fulfilled its remaining need so it got successfully executed. Now let's say P3, can we fulfil the need of P3? P3 says I need 6 resources of A. Do I have 6? You have to check this, that was previous available now new available we have 5. But it is still less, we have only 5 available, it is demanding for 6. So you have to check all 3, if all 3 are equal to or less than this then you have to check otherwise no. Let's come to P4, P4 needs 2 resources of A but how many I have? 5.

So I can give. It needs 1 resource of B, I have 3 available, it says just give me 1 resource of C, I have 2 available, so yes, I can now fulfill the need of P4. So next process which will be successfully executed that is P4. So same if P4 is successfully executed, how it is executed? Its remaining need is less than my availability. Means the remaining need of any process should be less than or equal to current availability. You just have to check this, current availability should be greater than or equal to remaining need for all the processes, for all the resources. So if this formula is valid for for all the resources, then you can provide it. So yes, we fulfilled remaining need of P4 so P4 got successfully terminated. So when P4 is terminated then the resources it was already holding, which ones? P4 was holding 2 of A, 1 of B, and 1 of C.

So these will also be released because termination means what? whatever locks, resources, processes it was holding, whatever memory allocation, each and everything will be released. So we will again add them, so 2, 1, 1 we will add in this so it becomes 7, 4, 3. So my current availability becomes what? 7, 4, 3. Now let's check P5. Because we are going sequence wise, if you want to you can check P3 again that doesn't matter, you can check P1 again too that is also not a problem. But once we go in sequence we were checking P2 first then P3 did not come, checked P4, so now we come to P5. So P5 says I need 5 resources of A, how many I have? 7. I can easily give. I need 3 of B, I have 4.

P5 says I need only 1 resource of C, I have 3. So I can easily from my availability give it 5, 3, 1 and it will also be successfully executed. So means P5 is also successfully executed. So when P5 is successfully executed what comes next in my sequence? P5. So when P5 is executed then whatever resources it was holding, which ones? 0, 1, 2. So 0, 0, 2 we add to this so total becomes what? 7, 4, 5. So what is the total now? 7, 4, 5. So my current availability becomes what? 7, 4, 5. Now let's check again from P1. You can check P3 also nothing wrong. This sequence can be many count but deadlock should not occur, sequence can be many.

Like we again check P1, 7, I have available, 4, I have available, 3, I have available. So means what I have available is more than its remaining need. Now I will give P1 all resources it needs, whatever it needs, 7 out of 7 needed , given, 4 needed, given, 3 needed, given. So it will also be successfully executed. So next which one remains? P1. P1 is also successfully executed. So whatever resources P1 was holding I will take them back so 0, 1, 0 is added to this, so what does this become? 7, 5, 5. So this is my current availability. 7, 5, 5. So which process is remaining? Only P3. P3 says give me 6 resources of A, I have 7. It doesn't B and C, I still have available So I fulfilled the remaining need of P3 so who comes next in the sequence? P3.

P3 comes next in the sequence and whatever resources P3 had taken, because it is terminated, P3 also exits the system. So whatever resources it had taken which ones? 3, 0, 2. They are also released, so I will have added 3, 0, 2. So total becomes what? 10, 5, 7. So from here you can have an idea whether we are going right or not. So finally what is my total? 10, 5, 7. And how many I had? 10, 5, 7. So all the resources after allocating we terminated the processes, so whatever resources I had previously available, I have those many again total available and this Safe Sequence is created. We call this Safe Sequence. Why Safe Sequence? Because deadlock did not occur. So this safe sequence P2, P4, P5, P1, P3, first thing is it is not unique, here P3 could have also come before, that doesn't matter. But you can be asked a question where some sequence may be asked so you have to carefully design the sequence, and second you may be asked whether deadlock will occur or not.

So deadlock will occur only if I cannot fulfil the need of any of the 5. If I can fulfil even 1, then it will come first in the sequence. So this is what we call Deadlock Avoidance. Yes, in deadlock avoidance like we said that we have to feed the system beforehand that I want these many processes, I have these many resources, this is their demand, like we saw maximum need, So if say can this be implemented in real life? It can be, you can code in C programming, but how can you tell in real life which process is static, here we are talking about static need, it is static.

Means it tells beforehand that my need is 7, 5, 3. But in real life this never happens, processes never tell static need, their need is always dynamic. They can increase or decrease their need anytime during run time. So that's why this is not possible in real life. But to implement in real we have to create some base. That’s why this is a very important algorithm. Because it is asked many times in GATE and other competitive exams, so that's why you do this question carefully. And second we call it Deadlock Detection, we saw that we have to detect whether deadlock will occur or not. If it occurs then simple your question ends and second if it doesn't occur then which will be safe sequence? So that you will have to clearly find out here.

So if you liked this video please like it, share it and please subscribe my channel. Thank You..