We have discussed that First, Worst, Best Fit algorithm in variable partitioning in the last lecture. Today, we will be discussing First, Worst, Best Fit algorithm in fixed sized partitioning (First, Worst, Best Fit Algorithm 2 - operating system tutorial). So, let's start, shall we?
We will be solving a problem of fixed sized partitioning so that you can understand first, worst, best fit algorithm. Remember that in variable sized partitioning the space left in the memory can be reused but that's not the case in fixed sized partitioning. Fixed sized partitioning means that the size of partition is fixed and it cannot be changed . If the size of the process is less than size of partition then the remaining space is wasted but you cannot reuse it.
The processes we have to allocate are P1=357, P2=210, P3=468, P4=491.
We will be considering the above memory present in the picture.
First Fit
In first fit we start searching from the beginning for an empty partition and to the first empty partition we allocate the process to it.
1. Initially, P1 comes to the memory.
We start searching for an empty partition from the starting. Partition of size 400 is capable to store P1 so we allocate P1 to partition of size 400. Remaining 43 units are wasted in the partition causing internal fragmentation.
2. Then P2 comes to the memory.
We start searching for an empty partition from the starting. Partition of size 600 is capable to store P2 so we allocate P2 to partition of size 600. Remaining 390 units are wasted in the partition causing internal fragmentation.
3. Then P3 comes to the memory.
We start searching for an empty partition from the starting. Partition of size 500 is capable to store P3 so we allocate P3 to partition of size 500. Remaining 32 units are wasted in the partition causing internal fragmentation.
4. Then P3 comes to the memory.
We start searching for an empty partition from the starting. But there are no partitions which are left so we cannot allocate this process in the memory leading to external fragmentation.
Correction - In the picture above the white box does not means it is externally fragmented area.
Best Fit
It first searches the entire memory and then selects the smallest partition which can satisfy the request of process.
1. Initially, P1 comes to the memory.
We start searching for an empty partition from the starting which can be allocated to P1. We have partitions of size 400, 600, 500. We will have to select the smallest sized partition which is 400. So, 357 units are allocated to P1. 43 units are wasted which causes internal fragmentation.
2. Now, P2 comes to the memory.
We start searching for an empty partition from the starting which can be allocated to P2. We have partitions of size 600, 500, 300, 250. We will have to select the smallest sized partition which is 250. So, 210 units are allocated to P1. 40 units are wasted which causes internal fragmentation.
2. Now, P3 comes to the memory.
We start searching for an empty partition from the starting which can be allocated to P3. We have partitions of size 600, 500. We will have to select the smallest sized partition which is 500. So, 468 units are allocated to P1. 32 units are wasted which causes internal fragmentation.
2. Now, P4 comes to the memory.
We start searching for an empty partition from the starting which can be allocated to P4. We have partitions of size 600. We will have to select the smallest sized partition which is 600 only. So, 491 units are allocated to P1. 109 units are wasted which causes internal fragmentation.
In this case there is no external fragmentation.
Here notice that best fit algorithm actually performs best because it selects the partition with the smallest size thus least space is wasted.
Correction - In the picture above the white box does not means it is externally fragmented area.
Worst Fit
It first searches the entire memory and then selects the largest partition which can satisfy the request of process.
1. First P1 comes in the memory.
We will select the largest possible partition. So we select the partition of size 600 and allocate P1 to it. Remaining 243 units are wasted.
2. Then P2 comes in the memory.
We will select the largest possible partition. So we select the partition of size 500 and allocate P2 to it. Remaining 290 units are wasted.
3. Then P3 comes in the memory.
Notice that no partition can allocate P3.
4. Then P4 comes in the memory.
Notice that no partition can allocate P4.
Notice that internal fragmented area is very large in worst fit. That's why worst fit actually performs worst in fixed sized partitioning.
Conclusion
(First, Worst, Best Fit Algorithm 2 - operating system tutorial) In fixed sized partition the Best fit actually performs best because it selects the smallest partition from memory so internally fragmented area is also minimal. However, Worst fot actually performs worst because it selects the largest partition from memory so internally fragmented area is maximum.
(First, Worst, Best Fit Algorithm 2 - operating system tutorial) In fixed sized partition the Best fit actually performs best because it selects the smallest partition from memory so internally fragmented area is also minimal. However, Worst fot actually performs worst because it selects the largest partition from memory so internally fragmented area is maximum.