馃攳
L-5.5: First Fit, Next Fit, Best Fit, Worst fit Memory Allocation | Memory Management | OS - YouTube
Channel: Gate Smashers
[0]
Various allocation methods in Contiguous Memory Management. So basically we are using 4 algorithms
[7]
how we are allocating the memory to the processes. Means in our memory
[13]
as many processes are already present and as many available holes we have,
[19]
how we allocate processes in those holes. So basically there are 4 algorithms,
[25]
First Fit, Next Fit, Best Fit, and Worst Fit.
[29]
So let's examine this according to this diagram,
[32]
this is showing a process has already occupied this memory area. This is what,
[40]
already there is a process let's say process10, there is one process11, a process12,
[48]
process13, process14, process15. So these processes are already there in the memory and
[58]
this is representing the holes, these are the holes, means leftover space.
[64]
So how we can manage this leftover space? We will be using these algorithms.
[69]
So let's start with the first, First Fit algorithm.
[72]
According to the First Fit algorithm, allocate the first hole or partition,
[78]
we can say partition also but majority we use it to manage the holes.
[83]
So allocate the first hole that is big enough means let's say there is a process P1,
[91]
and process size is 15K.
[96]
Process size is 15KB.
[99]
So if process of 15K is coming, so according to the First Fit what it will check?
[105]
It will simply check the first location that is big enough which can hold the 15K.
[113]
Means it will start from this, so this is already occupied, occupied, occupied,
[119]
this is the empty space. So this is one hole, what is the size of this hole? 25K.
[124]
So 25K can easily accommodate the 15K, so according to the First Fit,
[129]
it will simply stop searching, which search? Hole searching it will stop,
[136]
and simply allocate P1 to this partition or we can say hole.
[142]
Means where will it accommodate P1? In this space. First such hole
[146]
where I can fit that process, that we'll call the First Fit. It is easiest.
[153]
Because here my searching time is also very less, I'm not searching the entire list,
[159]
when I get the first hole, I will accommodate the process there.
[164]
According to the Next Fit, Next Fit is modified version of the First Fit.
[170]
So in Next Fit also we are doing same, same as first fit but start searching
[174]
always from the last allocated hole. Means the last allocated hole given to some process
[181]
we will keep a pointer on that. Let's say that according to first fit I put P1 here,
[188]
so I allocated P1 here. Now here a pointer, I will keep a pointer at this area.
[196]
That pointer will help with what? Next time if a process comes,
[200]
let's say process comes P2, one more process comes P2 and size of P2 is let's say 18K.
[209]
Size of P2 is 18K, so from where it will start searching?
[214]
It will not start searching from the beginning.
[217]
It will start searching from the last value or last space where the process was allocated.
[224]
Means last where it was? On this hole, so it will start searching from here
[229]
and whatever the next, let's say 40K is enough, in 40K we can easily put 18K,
[235]
so this area will be taken by P2. So advantage of Next Fit is that
[240]
we need not search from the beginning again and again,
[244]
whatever last hole I gave to some process from that hole next we will start
[251]
for the empty hole means we will start searching for the next empty hole so that
[255]
I can accommodate next process in that.
[259]
So here according to Next Fit I will again not start from zero to search,
[266]
where will I start from? From this hole. Because this hole I had already given in First Fit
[271]
so I will next start form 40K. In 40K I can easily accommodate process of 18K
[278]
so I will put P2 here. This is the concept of the Next Fit.
[284]
Third one is Best Fit, what is the concept of Best Fit? From the name it is clear,
[288]
it will search the entire list and it will try to search that hole which will lead to
[296]
minimum internal fragmentation. The main thing is that let's say my process is
[303]
Let's start this again, if process size is 15K.
[308]
Size of process is 15K.
[311]
Then 15K process according to the First Fit I can put in this.
[317]
According to the Next Fit also I can put in this. But according to Best Fit,
[322]
although according to Best Fit also in this already 15K can be accommodated in this.
[327]
But it will search the entire list, let's say 40K, it can be accommodated in 40K also
[333]
but the leftover space is very huge. So remaining portion should be minimum,
[339]
it will try to search for that hole. So at last where will it come? In 20K.
[345]
20K can accommodate P1? Yes, 20K can accommodate P1 easily. And what is the leftover space?
[352]
If I allocate P1 here, so if P1 is allocated then how much is my leftover space? 5K.
[363]
Because remaining area is taken by what? P1. P1 takes the remaining area,
[369]
so leftover space is what? 5K.
[372]
So it will search the entire list, it will search all holes and choose that hole
[379]
in which if I put that process then remaining memory, remaining portion will be least.
[386]
This is the concept of the Best Fit. So that my internal fragmentation should be minimum in that case.
[393]
According to the Worst Fit, what we do in Worst Fit, we simply select the largest hole.
[400]
Means in this also we will search the entire list, but which process we will put in it?
[405]
Or in which hole we will put the process? Where my leftover space is maximum.
[411]
Means this is exact opposite of Best Fit, it is reverse of Best Fit, so if size of P1 is 15K
[418]
then I can put it here also, here also, here also, different places.
[421]
But according to the Worst Fit where will I put P1? In this hole.
[426]
Because when P1 is put here, P1 is accommodated here. So how much is remaining portion?
[433]
Rest of the portion is 85K, which is leading to the maximum memory leftover.
[439]
So means according to the Worst Fit where we put any process? Where my left space,
[447]
after putting that process my hole size is very big. Now if these are compared
[453]
then First Fit is easiest method, very simple. It is very simple to implement and very fast.
[462]
The advantage is it is very fast. Because it is directly searching for the first hole
[470]
that is big enough to hold my process. It has nothing to do whether leftover space is
[477]
high or low, if a process can be accommodated by a hole then the first hole found
[484]
it will allocate that process in it.
[487]
So here my advantage is simple, it is fast but what is the disadvantage here?
[493]
It is possible that disadvantage may be that the remaining portion, the remaining hole,
[499]
let's say if I accommodate P1 here then the remaining portion, it will create holes,
[506]
big holes it can create. Means remaining you see if I put 15K here,
[511]
means if I accommodate P1 here, then how much remaining space I have?
[515]
Further hole of 10K remains.
[518]
Now in this 10K hole if some process of 10K comes then I can accommodate in this,
[524]
but if processes of large size are coming then I cannot accommodate in this.
[530]
So this is the advantage of the First Fit. Next Fit is same according to the First Fit.
[537]
But one more advantage is First Fit will always start searching from zero,
[543]
as soon as first slot is found, first hole is found, it will put the process in that.
[548]
But in Next Fit we did little faster, how we made fast? As soon as we put P1 here,
[555]
we put a pointer here, now next time when we search for some hole then
[560]
we will start searching from this point, we will not start again form zero.
[566]
So in Next Fit also same, when one more process comes,
[570]
let's say if one more process of 15K comes then which is the next hole found? This hole.
[575]
What is the size? 40K. And what is the size my process? 15K.
[579]
So I can easily put the 15K in this.
[584]
Third one is Best Fit. In Best Fit what advantage I get here is that
[589]
in this internal fragmentation will be very less. Means the portion that will be left laterwards
[595]
will be a very small portion. But in a way this can be disadvantage also.
[600]
Let's say that a process comes, size of process is
[606]
if size of process is 35K.
[611]
Then according to the Best Fit I will put in this slot, I can put in this also
[617]
because 100K can also accommodate, but Best Fit says that after putting a process in the hole
[623]
remaining space should be the least. So according to that rule I will simply put this
[630]
let's say the process is P2, this P2 process in this.
[634]
So what is the remaining portion left? Only 5K. So many times what this Best Fit does
[640]
it creates such small, tiny holes that in it I may not be able to further accommodate a process.
[648]
because in such small holes it is possible that my process may not accommodate.
[652]
Process sizes are little larger and there are tiny holes. In those tiny holes
[658]
I cannot put the process but if we see from normal point of view then
[662]
we are basically searching for such a hole in which my internal fragmentation is lowest.
[669]
And there is one more big disadvantage in Best Fit, the point is it will search the entire list.
[676]
It will search the entire list then it will know in which hole to put that process
[684]
so that the leftover portion should be least. To know this it will have to compare everywhere.
[691]
P2 size is 35K, hole size is 40K, so leftover portion is 5K. Next 100K,
[698]
P2 size is 35K, hole size is 100K, leftover portion will be near about 65K which is huge.
[705]
So it will search for entire holes, and then it will decide in which hole
[710]
I have to put the process so that leftover portion is least. Means here in Best Fit
[717]
in advantages we can say that the internal fragmentation
[724]
internal fragmentation will be less
[730]
or we can say that the remaining holes will be left in very small portions,
[736]
but if we see its disadvantages then disadvantage is very slow, this is very slow.
[743]
Because it will search for the entire list. Worst Fit is also same.
[748]
In Worst Fit what are we searching for? For such a hole in which
[752]
my remaining portion is very high. Means if a process comes,
[758]
let's say size of process is 15K or let's say size of process is 20K.
[766]
So 20K process where we will accommodate according to the Worst Fit?
[772]
We will simply accommodate here so that, we put this 20K here, we put this process here,
[781]
how much is the remaining portion I have? 80K. So means in Worst Fit an advantage is
[789]
that although it is searching for that hole which is big enough and which is leaving the
[795]
maximum leftover space. So here maximum leftover space is 80K. But this space is so enough
[803]
that if one more process comes or two, three more processes come,
[807]
here I can accommodate those also. So means here I don't have so small portions left
[814]
of 1-2 bytes, of 1-2 kilobytes in which I don't put the process.
[819]
Where was this problem coming? In Best Fit. But in Worst Fit one more 80K hole is left,
[825]
now in this 80K hole let's say process P2 comes, P2 size is 10K.
[833]
Or let's say size of P2 is let's take 10K.
[837]
So according to 10K if I use Worst Fit then again I will put this 10K in this 80K hole,
[845]
so that again my leftover portion will again be biggest that is 70K.
[851]
So means there are chances of putting more processes in it.
[855]
But in Best Fit when you put a process then remaining portion, remaining memory is so less
[863]
that in that remaining hole chances of putting further processes are very less.
[869]
But in Worst Fit chances are still there because remaining portion is still enough
[874]
that you can accommodate another two, three processes. But here also what is the problem?
[880]
Slow. Why is it slow? Obviously, it will also search for the entire list,
[886]
after searching for the entire list, then it will decide in which hole to put the process
[893]
so that remaining memory or remaining space is highest, remaining space is maximum.
[900]
In Best Fit remaining space should be minimum, and in Worst Fit remaining space
[904]
after putting the process, remaining space in that hole should be maximum.
[909]
So Best Fit and Worst Fit are what? Exact opposite. So on this many times
[914]
question comes in GATE, like if you are given a diagram that
[918]
here how many processes are already occupied and some holes are there, then
[923]
according to First Fit, Next Fit, Best Fit or Worst Fit how can I accommodate processes in hole.
[931]
So if we see in real life then we can say that First Fit is the most convenient method
[937]
because if we simply talk according to time, then among these four, or
[941]
basically among these three, because this Next Fit is a modified version of this.
[945]
So we can overall compare First Fit, Best Fit and Worst Fit because
[950]
this is the modified version of First Fit. So this is the most convenient method
[956]
because here time taken is least. But if you normally get a question
[962]
then in the question, any scenario may be there. Maybe there Worst Fit works best,
[966]
maybe First Fit works best, so you don't need to cram this but
[971]
how these algorithms are actually working, that is the important thing.
[975]
So if you like the video then please like it, share it and please subscribe my channel, thank you.
Most Recent Videos:
You can go back to the homepage right here: Homepage