L-4.5: Deadlock Avoidance Banker's Algorithm with Example |With English Subtitles
L-4.5: Deadlock Avoidance Banker's Algorithm with Example |With English Subtitles
👉Subscribe to our new channel: / @varunainashots
Banker’s algorithm is a deadlock avoidance algorithm. It is used in banking systems to determine whether a loan can be granted or not.
►Operating System (Complete Playlist):
• Operating System (Complete Playlist)
Other subject-wise playlist Links:
--------------------------------------------------------------------------------------------------------------------------------------
►Design and Analysis of algorithms (DAA):
• Design and Analysis of algorithms (DAA)
►Database Management System:
• DBMS (Database Management system) Com…
► Theory of Computation
• TOC(Theory of Computation)
►Artificial Intelligence:
• Artificial Intelligence (Complete Pla…
►Computer Networks (Complete Playlist):
• Computer Networks (Complete Playlist)
►Computer Architecture (Complete Playlist):
• Computer Organization and Architectur…
►Structured Query Language (SQL):
• Structured Query Language (SQL)
►Discrete Mathematics:
• Discrete Mathematics
►Compiler Design:
• Compiler Design (Complete Playlist)
►Number System:
• Number system
►Cloud Computing \u0026 BIG Data:
• Cloud Computing \u0026 BIG Data
►Software Engineering:
• Software Engineering
►Data Structure:
• Data Structure
►Graph Theory:
• Graph Theory
►Programming in C:
• C Programming
►Digital Logic:
• Digital Logic(Complete Playlist)
---------------------------------------------------------------------------------------------------------------------------------------
Our social media Links:
► Subscribe to us on YouTube: / gatesmashers
►Subscribe to our new channel: / @varunainashots
► Like our page on Facebook: https://www.facebook.com/gatesmashers
► Follow us on Instagram: https://www.instagram.com/gate.smashers
► Follow us on Instagram: https://www.instagram.com/varunainashots
► Follow us on Telegram: https://t.me/gatesmashersofficial
--------------------------------------------------------------------------------------------------------------------------------------
►For Any Query, Email us at: [email protected]
►Be a Member \u0026 Give your Support on the below link: / @gatesmashers
#Deadlocks#OperatingSystem#GATE#UGCNET
Content
0.5 -> Hello Friends, Welcome to GATE Smashers. The topic is Banker's Algorithm in Operating System.
6 -> We also call Banker's Algorithm as Deadlock Avoidance Algorithm. The reason is that
10.6 -> in Deadlock Avoidance we have to provide information to the Operating System beforehand
15 -> which processes are coming, which processes will request for which resources,
20 -> how many resources will they request, for how long will they do it, means
24 -> I have to give information to the system beforehand so that the system performs accordingly
30 -> and decides which process to perform and which process to not perform and make it wait.
36 -> So Banker's algorithm,
43 -> Deadlock Avoidance
48 -> Many times it is being asked in theory whether it is a Deadlock Prevention or Deadlock Avoidance algorithm,
55 -> Banker's is a Deadlock Avoidance algorithm.
57 -> Other than this, it is also used for Deadlock Detection
67 -> Detection means like we can detect in the system whether deadlock can occur in future or not,
74 -> And question on this has been asked many times in GATE and all competitive exams
79 -> where you are given a scenario, like number of processes like in this I have given you 5 processes,
85.6 -> and all of these 5 are requesting some resources and some number, means how many
93 -> like in this there are three resources A, B and C, different different kind of resources
99 -> whether they are physical resources or logical resources like CPU, Memory, Cache,
105 -> they are all what? Resources. Like in this, there are three resources A, B and C.
112 -> So five processes are requesting for these resources and
118 -> along with that they are telling their needs that how much more we need.
123 -> And on this basis we have to find out at the end,
127 -> Banker's algorithm at the end shows whether deadlock occurs or not.
133 -> So that's why we call it Deadlock Detection Algorithm
137 -> So we check in this scenario whether deadlock can be detected or not,
143 -> and why will it not occur? What is the reason of that?
146 -> Like in this we have 5 processes P1, P2, P3, P4 and P5 and A, B and C are 3 resources.
156 -> These are of three resources types like A is you can say CPU,
162 -> B is you can say Memory and C can be Printer.
169 -> You can say any resources, it can be R1, R2, R3. A, B, C are 3 different types of resources,
176 -> and we have in system 10 resources of A, 5 of B, 7 of C.
182 -> Means we have 10 CPUs, 5 Memories and 7 Printers.
188 -> Total we have how many resources in what number is given.
193 -> Other than that, what we are given here? Allocation. What is the meaning of allocation?
200 -> Like which process has been already allocated how many resources by the system.
205 -> Means no resource of A is allocated to P1 but 1 instance of B, we can call this instance like
214 -> we have 10 instances of A, 5 instances of B and 7 instances of C or you can simply say that
223 -> there are 10 CPUs, 5 Memories, 7 Printers.
227 -> Whether you call it instance or number that is the same thing.
231 -> So here what information is this giving? P1 process has 0 instance of A,
238 -> means no CPU has been allocated yet.
243 -> This is allocated, already allocated or not.
247 -> 1 instance of B is allocated and C is 0.
252 -> Similarly P2 is already allocated 2 instances of A, 0, 0.
257 -> P3 is allocated 3, 0, 2. P4 has 2, 1, 1. P5 0, 0, 2 means 2 instances of C are allocated.
266 -> So this is allocation, allocation tells how many resources system has already given to a particular process.
273 -> Along with that what we are given? Maximum Need. Maximum Need means which process needs how many resources.
283 -> This is the main point. This is why we call it a deadlock avoidance
288 -> because we tell the system beforehand, P1 tells beforehand that I want 7 resources of A,
295 -> 5 of B and 3 of C. If you give me these then I will be successfully executed and terminated
305 -> Similarly P2 process also tells its demand of resources
312 -> and P3 also tells its maximum demand or maximum needs of resources.
316 -> Maximum need means like what is maximum need of P3? 9, 0, 2, means
322 -> P3 says that give me 9 instances of A, I don't want any instance of B,
328 -> and give me 2 instances of C. If you fulfil these needs then I will be successfully executed.
335 -> So this is the way that, what is meaning of maximum need? How many maximum instances they want.
341 -> And P4, P5 all 5 have told their respective maximum needs.
347 -> Now our main question starts, in question they can ask to show if there is a deadlock or not.
354 -> If there is a deadlock then simply you can say that this is unsafe.
358 -> We call it safe or unsafe.
364 -> Safe means deadlock will not occur. And unsafe means deadlock will occur.
371 -> So if deadlock occurs then your question, simple, finishes that there is a deadlock.
377 -> Or if second can be that deadlock does not occur.
380 -> If deadlock does not occur then its sequence comes which we call Safe Sequence.
387 -> Safe Sequence means how do we sequence resources and processes so that deadlock doesn't occur.
397 -> This when we solve this then we will see.
400 -> Available. The third thing is Available, Available means
404 -> how much is the total availability of resources we have.
407 -> Total we have 10, 5 and 7
411 -> But already system has allocated some resources
415 -> means system has already allocated some because we are not starting from zero time,
421 -> we are talking about at a particular point of time
423.4 -> so at a particular point of time already some resources system has given to particular processes.
430 -> and total we have these many. So what will be available? Total - Allocation.
436 -> Means let's take the total of Allocation here
440 -> A is 0, 2, 3, 2 means 2 + 3 = 5, +2 = 7.
447 -> Already 7 resources of A are allocated. B, 1 + 1 = 2.
455 -> And C, 2 + 1 + 2 = 5.
460 -> So this what? 7, 2, 5 is what? 7 resources of A are already allocated,
466 -> 2 resources of B, 5 resources of C are already allocated.
471 -> And how many total A we have? 10. And how many are already allocated? 7, B, 2 and C, 5.
482 -> So total we had 10 out of which we have already given 7, so how many remain? 3.
489 -> 10-7 that is 3, 5-2 that is 3 and 7-5 that is 2.
499 -> So this is our at present availability, means at present or we can call it Current,
507 -> current availability is how much? 3, 3, 2.
511 -> And the next part is Remaining Need. What is the meaning of Remaining Need?
516 -> Like we did here, allocation, means I have allocated some resources
522 -> And system shows that processes have this much maximum need, this is their maximum need,
528 -> And from maximum need if we subtract already allocated then what do we have left? Remaining Need.
535 -> Means from maximum need we subtract allocation, so how much we have left? Remaining Need.
546 -> Like many times we have questions in Maths when we were little at that time questions used to come
551 -> like if I give a child 3 apples but he needs 10 apples so I will have to give him 7 more apples
561 -> means if 3 apples I have already given, but the child says I want 10 apples,
566 -> So I will provide him 7 more apples that's what we are saying here.
571 -> That I have already allocated some, maximum need it told me that I need this much,
576 -> if you fulfil my need then I will be successfully executed.
580 -> So I will calculate Remaining Need. How? By maximum - allocation.
585 -> So P1, how much is maximum need? 7. But already how many are given? 0.
592 -> Means nothing has been given yet. So means Remaining Need is still 7.
597 -> B, 5 but here I have already given 1, so 5-1 that is 4.
605 -> It needs 3 resources of C but how many are already given? Nothing is given yet, so 0.
611 -> So means its need is still 3.
614 -> Similarly if we talk about P2, P2 says I need 3 resources of A,
618 -> already 2 resources are given so how many remaining? 1.
623 -> For B, it needs 2, how many are given? 0, so 2. Similarly 2 of C.
630 -> So simply from Maximum Need if you subtract Allocation then we can find Remaining Need.
638 -> So in the same way we find for P3, 9-3 that is 6, 0-0=0, 2-2=0.
647 -> Just be little careful when you calculate then A from A, B from B, C from C.
653 -> Otherwise many times here mistakes may happen in calculation, so be careful here.
658 -> Similarly if we see P4, 4-2 that is 2, 2-1 that is 1, 2-1 that is 1.
669 -> P5, for P5 it is 5-0=5, no resource is given yet, all 5 are needed,
677 -> it needs all 3, already given 2 so only 1 resource is remaining.
682 -> So this is the remaining need, remaining need you need to calculate carefully.
692 -> So this is the remaining need of all the processes P1, P2, P3, P4 and P5.
701 -> So remaining need of all 5 is written here.
707 -> Now availability, now what do we have at present available in the system,
713 -> 3 resources of A, 3 resources of B, 2 resources of C.
716 -> So now we have to check if according to my availability I can fulfil any of the remaining needs.
724 -> How, let's say P1 needs 7 resources of A, so do I have 7 resources now? No, we have only 3 resources,
734 -> needs 4 of B, how many do we have? 3, needs 3 of C, how many I have? 2.
739 -> Means I can't fulfil the remaining needs of P1 because I have less availability.
746 -> So means P1 will not be in the sequence.
751 -> So if here we check P2 next, but if let's say we cannot fulfil the need of all the processes,
760 -> then we can simply say deadlock will occur in this.
764 -> Like P2, what is the remaining need of P2? It needs 1 resource, we have 3,
771 -> it needs 2 resources of B, we have 3, it needs 2 resources of C, we have 2,
778 -> yes, so I can fulfil the remaining needs of P2.
782 -> But let's say if here in case instead of 1 it was 4, then could I do? No.
792 -> This here is a very important point because here what would be remaining need of P2? 4.
798 -> And how many resources I have? 3. 2 of B, and I have 3, 2 here and I have 2,
804 -> so you may think that I can give C because it needs 2 of C and I have 2,
810 -> but guys you have to provide all 3 resources at the same time,
814 -> otherwise you will make the system more complex.
816.6 -> Means the remaining need of all resources should match this, means either equal to or less than that.
826 -> Means whatever the remaining need it should be either equal to or less than total available.
832.7 -> If that happens then that is fine otherwise we will check next process.
837 -> So here value was 1, so we will follow with 1, that is just for the explanation.
846 -> 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.
855 -> 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,
861 -> But A, how many A? 6. It is saying I need 6 CPUs, can we give 6 CPUs? No. You have only 3 CPUs.
870 -> So means we cannot fulfil this. So you have to be little careful on this point.
875 -> Now if we talk about P2 again, remaining need of P2 is what? 1, 2, 2
880 -> and we have 3, 3, 2 so easily we can fulfil the needs of P2.
886 -> So if I talk about sequence, the first process whose need we fulfilled, that becomes P2.
895 -> So when we fulfilled the need of P2, it will be successfully executed because
901 -> 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
909 -> which is more than its remaining need, so it will successfully take all resources and get terminated.
916 -> When P2 is terminated then the resources already with P2, it will release.
924 -> When P2 gets the remaining resources and it is successfully executed then
931 -> those which it has already taken in allocation those will also be free, all resources get free,
937 -> So means this was holding 2 resources, they are now free, so add it to available.
945 -> Means in available 2, 0, 0, we will add 2, 0, 0 in available
951 -> because those which it was already holding will be released.
957 -> So how many are total? 5, 3, 2.
961 -> So those which it was already holding in advance in allocation those resources are also released.
968 -> So now my availability is increased, availability becomes what? 5, 3, 2.
972 -> And out of this our process P2 exits from here.
979 -> Because we fulfilled its remaining need so it got successfully executed.
986 -> Now let's say P3, can we fulfil the need of P3? P3 says I need 6 resources of A. Do I have 6?
994 -> You have to check this, that was previous available now new available we have 5.
998 -> But it is still less, we have only 5 available, it is demanding for 6. So you have to check all 3,
1005 -> if all 3 are equal to or less than this then you have to check otherwise no.
1009 -> Let's come to P4, P4 needs 2 resources of A but how many I have? 5. So I can give.
1017 -> It needs 1 resource of B, I have 3 available, it says just give me 1 resource of C, I have 2 available,
1025 -> so yes, I can now fulfill the need of P4.
1025 -> So next process which will be successfully executed that is P4.
1037 -> So same if P4 is successfully executed, how it is executed? Its remaining need is less than my availability.
1048 -> Means the remaining need of any process should be less than or equal to current availability.
1065 -> You just have to check this, current availability should be greater than or equal to remaining need
1071 -> for all the processes, for all the resources. So if this formula is valid for for all the resources,
1076 -> then you can provide it.
1079 -> So yes, we fulfilled remaining need of P4 so P4 got successfully terminated.
1086 -> So when P4 is terminated then the resources it was already holding, which ones? P4 was holding
1093 -> 2 of A, 1 of B, and 1 of C. So these will also be released because termination means what?
1099 -> whatever locks, resources, processes it was holding, whatever memory allocation, each and everything will be released.
1106 -> So we will again add them, so 2, 1, 1 we will add in this so it becomes 7, 4, 3.
1117 -> So my current availability becomes what? 7, 4, 3.
1120 -> Now let's check P5. Because we are going sequence wise, if you want to you can check P3 again
1128 -> that doesn't matter, you can check P1 again too that is also not a problem.
1133 -> But once we go in sequence we were checking P2 first then P3 did not come, checked P4, so now we come to P5.
1140 -> So P5 says I need 5 resources of A, how many I have? 7. I can easily give.
1146 -> I need 3 of B, I have 4. P5 says I need only 1 resource of C, I have 3.
1154 -> So I can easily from my availability give it 5, 3, 1 and it will also be successfully executed.
1163 -> So means P5 is also successfully executed.
1167 -> So when P5 is successfully executed what comes next in my sequence? P5.
1172 -> So when P5 is executed then whatever resources it was holding, which ones? 0, 1, 2.
1177 -> So 0, 0, 2 we add to this so total becomes what? 7, 4, 5.
1183 -> So what is the total now? 7, 4, 5. So my current availability becomes what? 7, 4, 5.
1188 -> Now let's check again from P1. You can check P3 also nothing wrong.
1196 -> This sequence can be many count but deadlock should not occur, sequence can be many.
1203 -> Like we again check P1, 7, I have available, 4, I have available, 3, I have available.
1212 -> So means what I have available is more than its remaining need.
1217 -> Now I will give P1 all resources it needs, whatever it needs,
1223 -> 7 out of 7 needed , given, 4 needed, given, 3 needed, given. So it will also be successfully executed.
1230 -> So next which one remains? P1. P1 is also successfully executed. So whatever resources P1 was holding
1236 -> I will take them back so 0, 1, 0 is added to this, so what does this become? 7, 5, 5.
1247 -> So this is my current availability. 7, 5, 5.
1252 -> 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
1261 -> So I fulfilled the remaining need of P3 so who comes next in the sequence? P3.
1268 -> P3 comes next in the sequence and whatever resources P3 had taken, because it is terminated, P3 also exits the system.
1276 -> So whatever resources it had taken which ones? 3, 0, 2. They are also released, so I will have added 3, 0, 2.
1283 -> So total becomes what? 10, 5, 7. So from here you can have an idea whether we are going right or not.
1292 -> So finally what is my total? 10, 5, 7. And how many I had? 10, 5, 7. So all the resources
1302 -> after allocating we terminated the processes, so whatever resources I had previously available,
1308 -> I have those many again total available and this Safe Sequence is created. We call this Safe Sequence.
1315 -> Why Safe Sequence? Because deadlock did not occur.
1319 -> So this safe sequence P2, P4, P5, P1, P3, first thing is it is not unique,
1326 -> here P3 could have also come before, that doesn't matter.
1330 -> But you can be asked a question where some sequence may be asked
1335 -> so you have to carefully design the sequence,
1338 -> and second you may be asked whether deadlock will occur or not.
1341 -> So deadlock will occur only if I cannot fulfil the need of any of the 5.
1348 -> If I can fulfil even 1, then it will come first in the sequence.
1353 -> So this is what we call Deadlock Avoidance.
1357 -> Yes, in deadlock avoidance like we said that we have to feed the system beforehand that
1363 -> I want these many processes, I have these many resources, this is their demand, like we saw maximum need,
1370 -> So if say can this be implemented in real life? It can be, you can code in C programming, but
1378 -> how can you tell in real life which process is static, here we are talking about static need, it is static.
1386 -> Means it tells beforehand that my need is 7, 5, 3. But in real life this never happens,
1392 -> processes never tell static need, their need is always dynamic.
1397 -> They can increase or decrease their need anytime during run time. So that's why this is not possible in real life.
1403 -> But to implement in real we have to create some base. That’s why this is a very important algorithm.
1411 -> Because it is asked many times in GATE and other competitive exams, so that's why you do this question carefully.
1420 -> And second we call it Deadlock Detection, we saw that we have to detect whether deadlock will occur or not.
1427 -> If it occurs then simple your question ends and second if it doesn't occur then which will be safe sequence?
1433 -> So that you will have to clearly find out here.
1436 -> So if you liked this video please like it, share it and please subscribe my channel. Thank You.
Source: https://www.youtube.com/watch?v=7gMLNiEz3nw