In the last post I discussed about contiguous memory allocation. We also discussed 2 types of partitioning in contiguous memory allocation. In both the partitioning techniques we can use the 3 algorithms that I am going to discuss now. Today we will be discussing about First, Worst, Best Fit Algorithm 1- operating system tutorial ,We will be solving a problem by variable size partitioning so that you can understand the 3 algorithms easily. So, let's start, shall we?
First, Worst, Best Fit Algorithm in Variable Size Partitioning
I hope you know what variable size partitioning means. In variable size partitioning, partitions are not made and process are allocated to the memory.
In the picture above the shaded region indicate the occupied region of the memory and non-shaded region indicates the unoccupied region of memory.
You might be confused that in variable sized partitioning we don't have any partitions but here we have partitions. So, try to understand that it is not the present scenario because many processes came before these and many process left so this is the current scenario of the memory.
Now, we have 4 processes in order with their space requirements P1=300, P2=25, P3=125, P4=50. We will allocate these processes to the memory in the above picture using first , worst and best fit.
First fit
It says that you shall start searching from the start index and you shall use the first partition that is capable of accomodating the process. But remember that you will allocate only the required space to the process and if some space is left then it can be reused because it is variable sized partitioning.
So, we start with P1 process with size 300.
We start from the beginning and P1 cannot be accomodated in 150 sized block so move forward.
P1 can be accomodated in the 350 sized block so 300 will be allocated and remaining 50 will be left as it is.
Now let's take P2 with size 25.
We start from the beginning and 25 can be accomodated in 150 sized block. So, 25 will be allocated and remaining 125 will be left as it is.
Now let's take P3 with size 125.
We start from the beginning and we found a 125 empty space. So, we allocated it to P3.
Now we take P4 with size 50.
We start from beginning and we found a 50 empty space. So, we allocate it to P4.
Best fit
It will search for all the empty spaces present in the memory first and then it allocate the process to the space which has less size if it can accomodate it.
First P1 comes in the memory.
It has size 300 so it can be accomodated in the 2nd space only. Now, remaining space is 50.
Next P2 comes in the memory.
Now P2 has size 25 and it can accomodated in both the space of 150 or 50. But according to best fit we will have to select 50 because it has less size. Now remaining spaces are 150 and 25.
Next P3 comes in memory.
P3 has size 125 and it will be allocated to space of 150 so P3 will be accomodated in space of 150. Now, remaining space are 25 and 25.
P4 will come in the memory.
P4 has size 50 but it cannot be allocated because we have 2 spaces of 25 each but they are not continuous.
Worst fit
It will search for all the empty spaces present in the memory first and then it allocate the process to the space which has largest size if it can accomodate it.
First P1 comes in memory.
P1 has size of 300 so it can only be allocated to 350 sized space. So, remaining space is 50 now.
Next P2 comes in memory.
P2 has a size of 25. According to worst fit we will have to select largest space possible which is 150. So 25 will be allocated to P2 and remaining 125 will be left.
Next P3 comes in memory.
P3 has a size of 125 so it will be allocated to larger space available which is of size 125.
next P4 comes in memory.
P4 has a size of 50 so it will be allocated to 50 sized empty space.
Conclusion
In First, Worst, Best Fit Algorithm 1- operating system tutorial for variable partitioning it is seen that Worst Fit actually performs best because the left over space will be of large size and generally larger size can accomodate more processes. but in Best Fit the left over space will be of small size so less processes can be accomodated into it.