Various allocation methods in Contiguous Memory Management. So basically we are using 4 algorithms how we are allocating the memory to the processes. Means in our memory as many processes are already present and as many available holes we have, how we allocate processes in those holes. So basically there are 4 algorithms, First Fit, Next Fit, Best Fit, and Worst Fit. So let's examine this according to this diagram, this is showing a process has already occupied this memory area. This is what, already there is a process let's say process10, there is one process11, a process12, process13, process14, process15. So these processes are already there in the memory and this is representing the holes, these are the holes, means leftover space. So how we can manage this leftover space? We will be using these algorithms. So let's start with the first, First Fit algorithm. According to the First Fit algorithm, allocate the first hole or partition, we can say partition also but majority we use it to manage the holes. So allocate the first hole that is big enough means let's say there is a process P1, and process size is 15K. Process size is 15KB. So if process of 15K is coming, so according to the First Fit what it will check? It will simply check the first location that is big enough which can hold the 15K. Means it will start from this, so this is already occupied, occupied, occupied, this is the empty space. So this is one hole, what is the size of this hole? 25K. So 25K can easily accommodate the 15K, so according to the First Fit, it will simply stop searching, which search? Hole searching it will stop, and simply allocate P1 to this partition or we can say hole. Means where will it accommodate P1? In this space. First such hole where I can fit that process, that we'll call the First Fit. It is easiest. Because here my searching time is also very less, I'm not searching the entire list, when I get the first hole, I will accommodate the process there. According to the Next Fit, Next Fit is modified version of the First Fit. So in Next Fit also we are doing same, same as first fit but start searching always from the last allocated hole. Means the last allocated hole given to some process we will keep a pointer on that. Let's say that according to first fit I put P1 here, so I allocated P1 here. Now here a pointer, I will keep a pointer at this area. That pointer will help with what? Next time if a process comes, let's say process comes P2, one more process comes P2 and size of P2 is let's say 18K. Size of P2 is 18K, so from where it will start searching? It will not start searching from the beginning. It will start searching from the last value or last space where the process was allocated. Means last where it was? On this hole, so it will start searching from here and whatever the next, let's say 40K is enough, in 40K we can easily put 18K, so this area will be taken by P2. So advantage of Next Fit is that we need not search from the beginning again and again, whatever last hole I gave to some process from that hole next we will start for the empty hole means we will start searching for the next empty hole so that I can accommodate next process in that. So here according to Next Fit I will again not start from zero to search, where will I start from? From this hole. Because this hole I had already given in First Fit so I will next start form 40K. In 40K I can easily accommodate process of 18K so I will put P2 here. This is the concept of the Next Fit. Third one is Best Fit, what is the concept of Best Fit? From the name it is clear, it will search the entire list and it will try to search that hole which will lead to minimum internal fragmentation. The main thing is that let's say my process is Let's start this again, if process size is 15K. Size of process is 15K. Then 15K process according to the First Fit I can put in this. According to the Next Fit also I can put in this. But according to Best Fit, although according to Best Fit also in this already 15K can be accommodated in this. But it will search the entire list, let's say 40K, it can be accommodated in 40K also but the leftover space is very huge. So remaining portion should be minimum, it will try to search for that hole. So at last where will it come? In 20K. 20K can accommodate P1? Yes, 20K can accommodate P1 easily. And what is the leftover space? If I allocate P1 here, so if P1 is allocated then how much is my leftover space? 5K. Because remaining area is taken by what? P1. P1 takes the remaining area, so leftover space is what? 5K. So it will search the entire list, it will search all holes and choose that hole in which if I put that process then remaining memory, remaining portion will be least. This is the concept of the Best Fit. So that my internal fragmentation should be minimum in that case. According to the Worst Fit, what we do in Worst Fit, we simply select the largest hole. Means in this also we will search the entire list, but which process we will put in it? Or in which hole we will put the process? Where my leftover space is maximum. Means this is exact opposite of Best Fit, it is reverse of Best Fit, so if size of P1 is 15K then I can put it here also, here also, here also, different places. But according to the Worst Fit where will I put P1? In this hole. Because when P1 is put here, P1 is accommodated here. So how much is remaining portion? Rest of the portion is 85K, which is leading to the maximum memory leftover. So means according to the Worst Fit where we put any process? Where my left space, after putting that process my hole size is very big. Now if these are compared then First Fit is easiest method, very simple. It is very simple to implement and very fast. The advantage is it is very fast. Because it is directly searching for the first hole that is big enough to hold my process. It has nothing to do whether leftover space is high or low, if a process can be accommodated by a hole then the first hole found it will allocate that process in it. So here my advantage is simple, it is fast but what is the disadvantage here? It is possible that disadvantage may be that the remaining portion, the remaining hole, let's say if I accommodate P1 here then the remaining portion, it will create holes, big holes it can create. Means remaining you see if I put 15K here, means if I accommodate P1 here, then how much remaining space I have? Further hole of 10K remains. Now in this 10K hole if some process of 10K comes then I can accommodate in this, but if processes of large size are coming then I cannot accommodate in this. So this is the advantage of the First Fit. Next Fit is same according to the First Fit. But one more advantage is First Fit will always start searching from zero, as soon as first slot is found, first hole is found, it will put the process in that. But in Next Fit we did little faster, how we made fast? As soon as we put P1 here, we put a pointer here, now next time when we search for some hole then we will start searching from this point, we will not start again form zero. So in Next Fit also same, when one more process comes, let's say if one more process of 15K comes then which is the next hole found? This hole. What is the size? 40K. And what is the size my process? 15K. So I can easily put the 15K in this. Third one is Best Fit. In Best Fit what advantage I get here is that in this internal fragmentation will be very less. Means the portion that will be left laterwards will be a very small portion. But in a way this can be disadvantage also. Let's say that a process comes, size of process is if size of process is 35K. Then according to the Best Fit I will put in this slot, I can put in this also because 100K can also accommodate, but Best Fit says that after putting a process in the hole remaining space should be the least. So according to that rule I will simply put this let's say the process is P2, this P2 process in this. So what is the remaining portion left? Only 5K. So many times what this Best Fit does it creates such small, tiny holes that in it I may not be able to further accommodate a process. because in such small holes it is possible that my process may not accommodate. Process sizes are little larger and there are tiny holes. In those tiny holes I cannot put the process but if we see from normal point of view then we are basically searching for such a hole in which my internal fragmentation is lowest. And there is one more big disadvantage in Best Fit, the point is it will search the entire list. It will search the entire list then it will know in which hole to put that process so that the leftover portion should be least. To know this it will have to compare everywhere. P2 size is 35K, hole size is 40K, so leftover portion is 5K. Next 100K, P2 size is 35K, hole size is 100K, leftover portion will be near about 65K which is huge. So it will search for entire holes, and then it will decide in which hole I have to put the process so that leftover portion is least. Means here in Best Fit in advantages we can say that the internal fragmentation internal fragmentation will be less or we can say that the remaining holes will be left in very small portions, but if we see its disadvantages then disadvantage is very slow, this is very slow. Because it will search for the entire list. Worst Fit is also same. In Worst Fit what are we searching for? For such a hole in which my remaining portion is very high. Means if a process comes, let's say size of process is 15K or let's say size of process is 20K. So 20K process where we will accommodate according to the Worst Fit? We will simply accommodate here so that, we put this 20K here, we put this process here, how much is the remaining portion I have? 80K. So means in Worst Fit an advantage is that although it is searching for that hole which is big enough and which is leaving the maximum leftover space. So here maximum leftover space is 80K. But this space is so enough that if one more process comes or two, three more processes come, here I can accommodate those also. So means here I don't have so small portions left of 1-2 bytes, of 1-2 kilobytes in which I don't put the process. Where was this problem coming? In Best Fit. But in Worst Fit one more 80K hole is left, now in this 80K hole let's say process P2 comes, P2 size is 10K. Or let's say size of P2 is let's take 10K. So according to 10K if I use Worst Fit then again I will put this 10K in this 80K hole, so that again my leftover portion will again be biggest that is 70K. So means there are chances of putting more processes in it. But in Best Fit when you put a process then remaining portion, remaining memory is so less that in that remaining hole chances of putting further processes are very less. But in Worst Fit chances are still there because remaining portion is still enough that you can accommodate another two, three processes. But here also what is the problem? Slow. Why is it slow? Obviously, it will also search for the entire list, after searching for the entire list, then it will decide in which hole to put the process so that remaining memory or remaining space is highest, remaining space is maximum. In Best Fit remaining space should be minimum, and in Worst Fit remaining space after putting the process, remaining space in that hole should be maximum. So Best Fit and Worst Fit are what? Exact opposite. So on this many times question comes in GATE, like if you are given a diagram that here how many processes are already occupied and some holes are there, then according to First Fit, Next Fit, Best Fit or Worst Fit how can I accommodate processes in hole. So if we see in real life then we can say that First Fit is the most convenient method because if we simply talk according to time, then among these four, or basically among these three, because this Next Fit is a modified version of this. So we can overall compare First Fit, Best Fit and Worst Fit because this is the modified version of First Fit. So this is the most convenient method because here time taken is least. But if you normally get a question then in the question, any scenario may be there. Maybe there Worst Fit works best, maybe First Fit works best, so you don't need to cram this but how these algorithms are actually working, that is the important thing. So if you like the video then please like it, share it and please subscribe my channel, thank you.