Best Fit Algorithm Program In C
Best Fit Algorithm Program in C
Memory allocation is one of the important tasks of the operating system. As the different processes need the CPU processing time, they also need a certain amount of memory. This memory is allocated to different processes according to their demand.
What is memory allocation
Memory allocation is one of the important tasks of the operating system. As the different processes need the CPU processing time, they also need a certain amount of memory. This memory is allocated to different processes according to their demand.
The three most common types of memory allocation schemes are
What is Best Fit
In the case of the best fit memory allocation scheme for process p1, the operating system searches for –
- The empty memory block that can accommodate process P1
- The memory wastage is minimum after allocating the process p1 out of all blocks.
This scheme is considered the best approach as it results in the most optimised memory allocation. However, finding the best fit memory allocation may be time-consuming.
- Read Also – Best Fit program in C++
Methods discussed
We will look at two methods for the coding of the Best Fit algorithm.
- Method 1 – Only Single Process allowed to occupy any block space
- Method 2 – Multiple Processes allowed to share fragmented block space
Method 1 (Processes not Allowed sharing BlockSpace)
Let us 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 smalller than the current block where // process is placed, change the block and thus indexPlaced // this reduces the wastage thus best fit 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; // make the status of the block as occupied occupied[indexPlaced] = 1; } } 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[] = {100, 50, 30, 120, 35}; int processSize[] = {40, 10, 30, 60}; int blocks = sizeof(blockSize)/sizeof(blockSize[0]); int proccesses = sizeof(processSize)/sizeof(processSize[0]); implimentBestFit(blockSize, blocks, processSize, proccesses); return 0 ; }
Output
Process No. Process Size Block no. 1 10 2 2 30 1 3 60 4 4 30 4
Method 2 (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
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
Read More
- Memory Management Introduction
- Partition Allocation Method
- Buddy- System Allocator
- Paging
- Types of Paging
- Fragmentation
- Mapping Virtual address to Physical Address.
- Virtual Memory
- Demand Paging
- Implementation of Demand paging and page fault
- Segmentation
- Page Replacement Algorithms
- Thrashing
- Belady’s Anomaly
- Static vs Dynamic Loading
- Static vs Dynamic Linking
- Swapping
- Translational Look Aside Buffer
- Process Address Space
- Difference between Segmentation and Paging
Login/Signup to comment