1.
AIM
To implement and compare First-Fit, Best-Fit, and Worst-Fit memory allocation strategies
using contiguous memory allocation in C programming.
2. THEORY
In Contiguous Memory Allocation, each process is allocated memory in a single
contiguous block.
1. First-Fit:
Allocates the first memory block that is large enough.
Faster but may cause fragmentation.
2. Best-Fit:
Allocates the smallest available block that fits the process.
Minimizes leftover space but may increase search time.
3. Worst-Fit:
Allocates the largest available block.
Leaves larger remaining blocks, which may be useful for future processes.
3. ALGORITHM
First-Fit Allocation
Input:
- blockSize[1...n] = sizes of n memory blocks
- processSize[1...m] = sizes of m processes
1. Initialize allocation[] to -1 for all processes.
2. For each process:
a. Search each block from beginning:
- If block size ≥ process size:
→ Allocate block
→ Reduce block size
→ Break loop
3. Display allocation result.
For each process i from 1 to m:
a. For each block j from 1 to n:
i. If blockSize[j] >= processSize[i]:
- Allocate process i to block j
- blockSize[j] = blockSize[j] - processSize[i]
- allocation[i] = j
- Break the inner loop (go to next process)
Best-Fit Allocation
1. Initialize allocation[] to -1 for all processes.
2. For each process:
a. Find the block with minimum size ≥ process size.
b. If found:
→ Allocate block
→ Reduce block size
3. Display allocation result.
Input:
- blockSize[1...n] = sizes of n memory blocks
- processSize[1...m] = sizes of m processes
1. Initialize allocation[1...m] = -1
2. For each process i from 1 to m:
a. Set bestIdx = -1
b. For each block j from 1 to n:
i. If blockSize[j] >= processSize[i]:
- If bestIdx == -1 OR blockSize[j] < blockSize[bestIdx]:
-> bestIdx = j
c. If bestIdx != -1:
- Allocate process i to block bestIdx
- blockSize[bestIdx] = blockSize[bestIdx] - processSize[i]
- allocation[i] = bestIdx
3. Display the allocation result
Worst-Fit Allocation
1. Initialize allocation[] to -1 for all processes.
2. For each process:
a. Find the block with maximum size ≥ process size.
b. If found:
→ Allocate block
→ Reduce block size
3. Display allocation result.
Input:
- blockSize[1...n] = sizes of n memory blocks
- processSize[1...m] = sizes of m processes
1. Initialize allocation[1...m] = -1
2. For each process i from 1 to m:
a. Set worstIdx = -1
b. For each block j from 1 to n:
i. If blockSize[j] >= processSize[i]:
- If worstIdx == -1 OR blockSize[j] > blockSize[worstIdx]:
-> worstIdx = j
c. If worstIdx != -1:
- Allocate process i to block worstIdx
- blockSize[worstIdx] = blockSize[worstIdx] - processSize[i]
- allocation[i] = worstIdx
3. Display the allocation result
Implementation :
#include <stdio.h>
#define MAX 100
void firstFit(int blockSize[], int blocks, int processSize[], int processes) {
int allocation[MAX];
for (int i = 0; i < processes; i++)
allocation[i] = -1;
for (int i = 0; i < processes; i++) {
for (int j = 0; j < blocks; j++) {
if (blockSize[j] >= processSize[i]) {
allocation[i] = j;
blockSize[j] -= processSize[i];
break;
}
}
}
printf("\nFirst-Fit Allocation:\n");
printf("Process No.\tProcess Size\tBlock No.\n");
for (int i = 0; i < processes; i++) {
printf("%d\t\t%d\t\t", i + 1, processSize[i]);
if (allocation[i] != -1)
printf("%d\n", allocation[i] + 1);
else
printf("Not Allocated\n");
}
}
void bestFit(int blockSize[], int blocks, int processSize[], int processes) {
int allocation[MAX];
for (int i = 0; i < processes; i++)
allocation[i] = -1;
for (int i = 0; i < processes; i++) {
int bestIdx = -1;
for (int j = 0; j < blocks; j++) {
if (blockSize[j] >= processSize[i]) {
if (bestIdx == -1 || blockSize[j] < blockSize[bestIdx])
bestIdx = j;
}
}
if (bestIdx != -1) {
allocation[i] = bestIdx;
blockSize[bestIdx] -= processSize[i];
}
}
printf("\nBest-Fit Allocation:\n");
printf("Process No.\tProcess Size\tBlock No.\n");
for (int i = 0; i < processes; i++) {
printf("%d\t\t%d\t\t", i + 1, processSize[i]);
if (allocation[i] != -1)
printf("%d\n", allocation[i] + 1);
else
printf("Not Allocated\n");
}
}
void worstFit(int blockSize[], int blocks, int processSize[], int processes) {
int allocation[MAX];
for (int i = 0; i < processes; i++)
allocation[i] = -1;
for (int i = 0; i < processes; i++) {
int worstIdx = -1;
for (int j = 0; j < blocks; j++) {
if (blockSize[j] >= processSize[i]) {
if (worstIdx == -1 || blockSize[j] > blockSize[worstIdx])
worstIdx = j;
}
}
if (worstIdx != -1) {
allocation[i] = worstIdx;
blockSize[worstIdx] -= processSize[i];
}
}
printf("\nWorst-Fit Allocation:\n");
printf("Process No.\tProcess Size\tBlock No.\n");
for (int i = 0; i < processes; i++) {
printf("%d\t\t%d\t\t", i + 1, processSize[i]);
if (allocation[i] != -1)
printf("%d\n", allocation[i] + 1);
else
printf("Not Allocated\n");
}
}
int main() {
int blockSize[MAX], processSize[MAX];
int blocks, processes;
printf("Enter number of memory blocks: ");
scanf("%d", &blocks);
printf("Enter size of each block:\n");
for (int i = 0; i < blocks; i++) {
printf("Block %d: ", i + 1);
scanf("%d", &blockSize[i]);
}
printf("Enter number of processes: ");
scanf("%d", &processes);
printf("Enter size of each process:\n");
for (int i = 0; i < processes; i++) {
printf("Process %d: ", i + 1);
scanf("%d", &processSize[i]);
}
int blockCopy1[MAX], blockCopy2[MAX], blockCopy3[MAX];
for (int i = 0; i < blocks; i++) {
blockCopy1[i] = blockCopy2[i] = blockCopy3[i] = blockSize[i];
}
firstFit(blockCopy1, blocks, processSize, processes);
bestFit(blockCopy2, blocks, processSize, processes);
worstFit(blockCopy3, blocks, processSize, processes);
return 0;
}
