Best Fit Algorithm in Operating System
Best Fit Algorithm in Operating System
In the case of the best fit memory allocation scheme, the operating system searches for the empty memory block. When the operating system finds the memory block with minimum wastage of memory, it is allocated to the process this is known as Best Fit Algorithm in Operating System.
How does it work?
In Best fit memory allocation scheme, the operating system searches that can –
- Accommodate the process
- Also, leaves the minimum memory wastage
Example –
If you see the image below/right you will see that the process size is 40.
While blocks 1, 2 and 4 can accommodate the process. Block 2 is chosen as it leaves the lowest memory wastage
Advantage:
It is allocated to the process. This scheme is considered the best approach as it results in the most optimized memory allocation.
Also reduces internal fragmentation.
Disadvantage:
However, finding the best fit memory allocation may be time-consuming.
Code
The below code is in C you can check codes in other languages here –
- Read Also – Best Fit program in C
- Read Also – Best Fit program in C++
- Read Also – Best Fit program in JAVA
Methods discussed
We will look at two methods for the coding of the Best Fit algorithm.
- Method 1 – Multiple Processes allowed to share fragmented block space
- Method 2 – Only Single Process allowed to occupy any block space
Method 1 (Processes Allowed sharing BlockSpace)
Let us have a look at the code below –
// C Program for Worst Fit #include <stdio.h> void implimentBestFit(int blockSize[], int blocks, int processSize[], int processes) { // This will store the block id of the allocated block to a process int allocation[processes]; // initially assigning -1 to all allocation indexes // means nothing is allocated currently for(int i = 0; i < processes; i++){ allocation[i] = -1; } // pick each process and find suitable blocks // according to its size ad assign to it for (int i=0; i<processes; i++) { int indexPlaced = -1; for (int j=0; j<blocks; j++) { if (blockSize[j] >= processSize[i]) { // place it at the first block fit to accomodate process if (indexPlaced == -1) indexPlaced = j; // if any future block is better that is // any future block with smaller size encountered // that can accomodate the given process else if (blockSize[j] < blockSize[indexPlaced]) indexPlaced = j; } } // If we were successfully able to find block for the process if (indexPlaced != -1) { // allocate this block j to process p[i] allocation[i] = indexPlaced; // Reduce available memory for the block blockSize[indexPlaced] -= processSize[i]; } } printf("\nProcess No.\tProcess Size\tBlock no.\n"); for (int i = 0; i < processes; i++) { printf("%d \t\t\t %d \t\t\t", i+1, processSize[i]); if (allocation[i] != -1) printf("%d\n",allocation[i] + 1); else printf("Not Allocated\n"); } } // Driver code int main() { int blockSize[] = {50, 20, 100, 90}; int processSize[] = {10, 30, 60, 30}; int blocks = sizeof(blockSize)/sizeof(blockSize[0]); int processes = sizeof(processSize)/sizeof(processSize[0]); implimentBestFit(blockSize, blocks, processSize, processes); return 0 ; }
Output
Process No. Process Size Block no. 1 10 2 2 30 1 3 60 4 4 30 4
Method 2 (Processes not Allowed sharing BlockSpace)
Lets have a look at the code below –
#include <stdio.h> void implimentBestFit(int blockSize[], int blocks, int processSize[], int proccesses) { // This will store the block id of the allocated block to a process int allocation[proccesses]; int occupied[blocks]; // initially assigning -1 to all allocation indexes // means nothing is allocated currently for(int i = 0; i < proccesses; i++){ allocation[i] = -1; } for(int i = 0; i < blocks; i++){ occupied[i] = 0; } // pick each process and find suitable blocks // according to its size ad assign to it for (int i=0; i<proccesses; i++) { int indexPlaced = -1; for (int j=0; j<blocks; j++) { if (blockSize[j] >= processSize[i] && !occupied[j]) { // place it at the first block fit to accomodate process if (indexPlaced == -1) indexPlaced = j; // if any future block is larger than the current block where // process is placed, change the block and thus indexPlaced else if (blockSize[indexPlaced] < blockSize[j]) indexPlaced = j; } } // If we were successfully able to find block for the process if (indexPlaced != -1) { // allocate this block j to process p[i] allocation[i] = indexPlaced; // make the status of the block as occupied occupied[indexPlaced] = 1; // Reduce available memory for the block blockSize[indexPlaced] -= processSize[i]; } } printf("\nProcess No.\tProcess Size\tBlock no.\n"); for (int i = 0; i < proccesses; i++) { printf("%d \t\t\t %d \t\t\t", i+1, processSize[i]); if (allocation[i] != -1) printf("%d\n",allocation[i] + 1); else printf("Not Allocated\n"); } } // Driver code int main() { int blockSize[] = {5, 4, 3, 6, 7}; int processSize[] = {1, 3, 5, 3}; int blocks = sizeof(blockSize)/sizeof(blockSize[0]); int proccesses = sizeof(processSize)/sizeof(processSize[0]); implimentBestFit(blockSize, blocks, processSize, proccesses); return 0 ; }
Output
Lets have a look at the code below –Process No. Process Size Block no. 1 10 2 2 30 1 3 60 4 4 80 3
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment