Practical 14: Write a C program to simulate the following contiguous memory allocation techniques: First fit, Best fit, and Worst fit
2024, April 10
14. Memory Allocation Techniques
This section covers the theoretical concepts behind three primary memory allocation techniques used in operating systems: Worst Fit, Best Fit, and First Fit. Each technique utilizes a different strategy to manage free memory in a system and has its own advantages and disadvantages.
14.1. First Fit
First Fit allocates the first block that is big enough. This method scans memory from the beginning and allocates the first free block that fits the process. It is generally faster than Best and Worst Fit because it stops searching as soon as it finds a free block large enough.
Advantages:
- Simple and fast, especially if the free blocks are sorted by size.
- Less processing time since it allocates the first suitable block.
Disadvantages:
- May cause more fragmentation compared to Best Fit, as it can leave larger free blocks towards the end of the memory.
- Performance depends on the order of requests and releases, which can vary significantly.
14.1.1. Algorithm of First Fit
- Start Scan: Begin at the start of the list of memory blocks.
- Check Block Size: Examine each memory block in sequence to determine if it is free and large enough to accommodate the requested memory size.
- Allocate Memory:
- If a suitable block is found:
- Allocate the necessary memory from this block to the process.
- If the block is exactly the size needed, mark it as fully occupied.
- If the block is larger than needed, allocate the required amount at the beginning of the block and reduce the size of the block by the amount allocated.
- If no suitable block is found after checking all available blocks:
- Return a memory allocation error or attempt another memory management strategy, such as compaction or swapping.
- If a suitable block is found:
- Update Memory List: Adjust the list of memory blocks to reflect the allocated memory and any remaining free space.
- Process Request Complete: End the allocation process once the memory has been successfully assigned or an error has been returned.
14.1.2. Implementation of First Fit in C
#include <stdio.h>
#define max 25
void main()
{
int frag[max], b[max], f[max], i, j, nb, nf, temp;
static int bf[max], ff[max];
printf("\n\tMemory Management Scheme - First Fit");
printf("\nEnter the number of blocks:");
scanf("%d", &nb);
printf("Enter the number of files:");
scanf("%d", &nf);
printf("\nEnter the size of the blocks:-\n");
for (i = 1; i <= nb; i++)
{
printf("Block %d:", i);
scanf("%d", &b[i]);
}
printf("Enter the size of the files :-\n");
for (i = 1; i <= nf; i++)
{
printf("File %d:", i);
scanf("%d", &f[i]);
}
for (i = 1; i <= nf; i++)
{
for (j = 1; j <= nb; j++)
{
if (bf[j] != 1)
{
temp = b[j] - f[i];
if (temp >= 0)
{
ff[i] = j;
break;
}
}
}
frag[i] = temp;
bf[ff[i]] = 1;
}
printf("\nFile_no:\tFile_size :\tBlock_no:\tBlock_size:\tFragement");
for (i = 1; i <= nf; i++)
printf("\n%d\t\t%d\t\t%d\t\t%d\t\t%d", i, f[i], ff[i], b[ff[i]], frag[i]);
}14.2 Best Fit
Best Fit allocates the smallest free block that is adequate to accommodate the process's demands. By doing this, it attempts to minimize the size of the unallocated space which reduces the likelihood of unusable small free spaces after allocation.
Advantages:
- Optimizes space utilization by minimizing leftover space in memory blocks.
- Typically leaves smallest leftover blocks, which reduces the chances of fragmentation over time.
Disadvantages:
- Can increase fragmentation due to the accumulation of too small to use memory blocks over time.
- Searching for the smallest adequate block can increase allocation time, especially with larger memory size.
14.2.1. Algorithm of Best Fit
- Initialize Variables: Start with no block selected and set the size of the smallest suitable block found to be infinite (or a very large number).
- Scan Memory Blocks: Go through each block of memory:
- If the block is free and its size is greater than or equal to the requested size and smaller than the smallest found so far, update the smallest block variable to this block's size and record its location.
- Check for Suitable Block:
- If a suitable block has been found:
- Allocate the required amount of memory from this block.
- If the block size is exactly what is needed, mark it as fully occupied.
- If the block is larger than needed, allocate the necessary amount and reduce the size of the block by that amount, leaving the remainder as a smaller free block.
- If no suitable block is found (smallest block variable remains infinite):
- Return a memory allocation error or consider using other memory management techniques, such as compaction or using a different allocation strategy.
- If a suitable block has been found:
- Update Memory List: Modify the list of memory blocks to reflect the new allocation and any changes in block sizes.
- Complete Request: End the process once memory has been successfully allocated or an error message has been issued.
14.2.2. Implementation of Best Fit in C
#include <stdio.h>
#define max 25
void main()
{
int frag[max], b[max], f[max], i, j, nb, nf, temp, lowest = 10000;
static int bf[max], ff[max];
printf("\nEnter the number of blocks:");
scanf("%d", &nb);
printf("Enter the number of files:");
scanf("%d", &nf);
printf("\nEnter the size of the blocks:-\n");
for (i = 1; i <= nb; i++)
{
printf("Block %d:", i);
scanf("%d", &b[i]);
}
printf("Enter the size of the files :-\n");
for (i = 1; i <= nf; i++)
{
printf("File %d:", i);
scanf("%d", &f[i]);
}
for (i = 1; i <= nf; i++)
{
for (j = 1; j <= nb; j++)
{
if (bf[j] != 1)
{
temp = b[j] - f[i];
if (temp >= 0)
if (lowest > temp)
{
ff[i] = j;
lowest = temp;
}
}
}
frag[i] = lowest;
bf[ff[i]] = 1;
lowest = 10000;
}
printf("\nFile No\tFile Size \tBlock No\tBlock Size\tFragment");
for (i = 1; i <= nf && ff[i] != 0; i++)
printf("\n%d\t\t%d\t\t%d\t\t%d\t\t%d", i, f[i], ff[i], b[ff[i]], frag[i]);
}14.3 Worst Fit
The Worst Fit allocation method scans the list of free blocks and allocates the largest available block to the process. Its primary objective is to reduce the size of the largest free block. This approach is based on the assumption that a larger block will be more likely to accommodate future process requests, thereby minimizing the number of times a process cannot be allocated due to insufficient memory.
Advantages:
- Reduces the size of the largest free memory block less frequently than other techniques.
- Can be more efficient in systems with large variance in process sizes.
Disadvantages:
- Can lead to inefficient use of space due to potentially leaving too large gaps unusable for smaller processes.
- May increase the time to search for a suitable block as it needs to examine all free blocks.
14.3.1 Algorithm of Worst Fit
- Initialize Variables: Start with no block selected and set the size of the largest block found to zero.
- Scan Memory Blocks: Go through each block of memory:
- If the block is free and its size is larger than the current largest block that has been found and is capable of accommodating the requested size, update the largest block variable to this block's size and record its location.
- Allocate Memory:
- If a suitable block (largest block) has been found:
- Allocate the required amount of memory from this block.
- If the block is exactly the size needed, mark it as fully occupied.
- If the block is larger than needed, allocate the necessary amount from the beginning or end of the block and reduce the size of the block by the amount allocated, leaving the remainder as a free block.
- If no suitable block is found:
- Return a memory allocation error or consider using other memory management techniques, such as compaction or using a different allocation strategy.
- If a suitable block (largest block) has been found:
- Update Memory List: Modify the list of memory blocks to reflect the new allocation and any changes in block sizes.
- Complete Request: End the process once memory has been successfully allocated or an error message has been issued.
14.3.2 Implementation of Worst Fit in C
#include <stdio.h>
#define max 25
void main()
{
int frag[max], b[max], f[max], i, j, nb, nf, temp, highest = 0;
static int bf[max], ff[max];
printf("\n\tMemory Management Scheme - Worst Fit");
printf("\nEnter the number of blocks:");
scanf("%d", &nb);
printf("Enter the number of files:");
scanf("%d", &nf);
printf("\nEnter the size of the blocks:-\n");
for (i = 1; i <= nb; i++)
{
printf("Block %d:", i);
scanf("%d", &b[i]);
}
printf("Enter the size of the files :-\n");
for (i = 1; i <= nf; i++)
{
printf("File %d:", i);
scanf("%d", &f[i]);
}
for (i = 1; i <= nf; i++)
{
for (j = 1; j <= nb; j++)
{
if (bf[j] != 1) // if bf[j] is not allocated
{
temp = b[j] - f[i];
if (temp >= 0)
if (highest < temp)
{
ff[i] = j;
highest = temp;
}
}
}
frag[i] = highest;
bf[ff[i]] = 1;
highest = 0;
}
printf("\nFile_no:\tFile_size :\tBlock_no:\tBlock_size:\tFragement");
for (i = 1; i <= nf; i++)
printf("\n%d\t\t%d\t\t%d\t\t%d\t\t%d", i, f[i], ff[i], b[ff[i]], frag[i]);
}