Practical- 14
Title : Write a program that simulates different memory partitioning methods and allocation strategies (firstfit,best-fit, next- fit, worst-fit).
—----------------------------------------------------------------------------------------------------------------------------
In memory management, the objective is to allocate memory to processes efficiently and to minimize fragmentation. Different strategies are employed to decide how to allocate memory blocks to processes. Here’s a look at each strategy:
1. First-Fit Allocation
Description: Allocates the first available block of memory that is large enough for the process.
Pros: Simple and fast allocation.
Cons: Can lead to fragmentation and inefficient memory use.
2. Best-Fit Allocation
Description: Allocates the smallest available block of memory that fits the process, minimizing wasted space.
Pros: Reduces wasted memory within allocated blocks.
Cons: Can be slower due to scanning all blocks and may create small fragments.
3. Next-Fit Allocation
Description: Allocates memory starting from the last allocated block, wrapping around if needed.
Pros: Avoids re-scanning from the start, potentially faster than First-Fit.
Cons: Can still lead to fragmentation and uneven allocation.
4. Worst-Fit Allocation
Description: Allocates the largest available block of memory to the process, leaving the remainder as free memory.
Pros: Keeps larger chunks of memory available for future processes.
Cons: Can cause fragmentation and inefficient use of large blocks.
Algorithms :
1. First-Fit Allocation Algorithm
Objective: Allocate the first block of memory that fits the process.
Algorithm:
Initialize:
Memory blocks and their sizes.
Process requests and their sizes.
Set a flag for allocation status.
For Each Process Request:
Scan memory blocks from the beginning.
If a block is found that is large enough and is free:
Allocate the block to the process.
Mark the block as used.
Break the scan and move to the next process request.
If no suitable block is found:
Mark the process as not allocated.
Output:
Display the allocation status for each process.
2. Best-Fit Allocation Algorithm
Objective: Allocate the smallest block that is large enough to fit the process.
Algorithm:
Initialize:
Memory blocks and their sizes.
Process requests and their sizes.
Set a flag for allocation status.
For Each Process Request:
Scan all memory blocks.
Track the smallest block that is large enough and free.
Allocate this block to the process if found.
If no suitable block is found:
Mark the process as not allocated.
Output:
Display the allocation status for each process.
3. Next-Fit Allocation Algorithm
Objective: Allocate memory starting from the last allocated block, wrapping around if necessary.
Algorithm:
Initialize:
Memory blocks and their sizes.
Process requests and their sizes.
Set the index of the last allocated block to the start.
For Each Process Request:
Start searching from the index of the last allocation.
If a block is found that is large enough and is free:
Allocate the block to the process.
Update the index to the next block.
Break the scan and move to the next process request.
If no suitable block is found in the current pass:
Wrap around and continue the search from the beginning.
Output:
Display the allocation status for each process.
4. Worst-Fit Allocation Algorithm
Objective: Allocate the largest available block of memory to the process.
Algorithm:
Initialize:
Memory blocks and their sizes.
Process requests and their sizes.
Set a flag for allocation status.
For Each Process Request:
Scan all memory blocks.
Track the largest block that is large enough and is free.
Allocate this block to the process if found.
If no suitable block is found:
Mark the process as not allocated.
Output:
Display the allocation status for each process.
Code:
#include <stdio.h>
#include <stdbool.h>
#define MEMORY_SIZE 100
// Function prototypes
void firstFit(int memory[], int blockSize[], int processSize[], int m, int n);
void bestFit(int memory[], int blockSize[], int processSize[], int m, int n);
void nextFit(int memory[], int blockSize[], int processSize[], int m, int n);
void worstFit(int memory[], int blockSize[], int processSize[], int m, int n);
int main() {
int memory[MEMORY_SIZE] = {0}; // Memory blocks initialized to 0 (free)
int blockSize[] = {10, 20, 30, 40, 50}; // Sizes of memory blocks
int processSize[] = {12, 25, 10, 30, 44}; // Sizes of processes
int m = sizeof(blockSize) / sizeof(blockSize[0]);
int n = sizeof(processSize) / sizeof(processSize[0]);
printf("First Fit Allocation:\n");
firstFit(memory, blockSize, processSize, m, n);
printf("\nBest Fit Allocation:\n");
bestFit(memory, blockSize, processSize, m, n);
printf("\nNext Fit Allocation:\n");
nextFit(memory, blockSize, processSize, m, n);
printf("\nWorst Fit Allocation:\n");
worstFit(memory, blockSize, processSize, m, n);
return 0;
}
void printMemory(int memory[], int size) {
printf("Memory: ");
for (int i = 0; i < size; i++) {
printf("%d ", memory[i]);
}
printf("\n");
}
void firstFit(int memory[], int blockSize[], int processSize[], int m, int n) {
printf("Process No.\tProcess Size\tBlock Size\n");
for (int i = 0; i < n; i++) {
int allocated = 0;
for (int j = 0; j < m; j++) {
if (blockSize[j] >= processSize[i] && memory[j] == 0) {
memory[j] = processSize[i];
printf("%d\t\t%d\t\t%d\n", i + 1, processSize[i], blockSize[j]);
allocated = 1;
break;
}
}
if (!allocated) {
printf("%d\t\t%d\t\tNot Allocated\n", i + 1, processSize[i]);
}
}
printMemory(memory, m);
}
void bestFit(int memory[], int blockSize[], int processSize[], int m, int n) {
printf("Process No.\tProcess Size\tBlock Size\n");
for (int i = 0; i < n; i++) {
int bestIdx = -1;
for (int j = 0; j < m; j++) {
if (blockSize[j] >= processSize[i] && memory[j] == 0) {
if (bestIdx == -1 || blockSize[j] < blockSize[bestIdx]) {
bestIdx = j;
}
}
}
if (bestIdx != -1) {
memory[bestIdx] = processSize[i];
printf("%d\t\t%d\t\t%d\n", i + 1, processSize[i], blockSize[bestIdx]);
} else {
printf("%d\t\t%d\t\tNot Allocated\n", i + 1, processSize[i]);
}
}
printMemory(memory, m);
}
void nextFit(int memory[], int blockSize[], int processSize[], int m, int n) {
static int lastIndex = 0;
printf("Process No.\tProcess Size\tBlock Size\n");
for (int i = 0; i < n; i++) {
int allocated = 0;
for (int j = lastIndex; j < m; j++) {
if (blockSize[j] >= processSize[i] && memory[j] == 0) {
memory[j] = processSize[i];
lastIndex = (j + 1) % m; // Circular index
printf("%d\t\t%d\t\t%d\n", i + 1, processSize[i], blockSize[j]);
allocated = 1;
break;
}
}
if (!allocated) {
for (int j = 0; j < lastIndex; j++) {
if (blockSize[j] >= processSize[i] && memory[j] == 0) {
memory[j] = processSize[i];
lastIndex = (j + 1) % m; // Circular index
printf("%d\t\t%d\t\t%d\n", i + 1, processSize[i], blockSize[j]);
allocated = 1;
break;
}
}
}
if (!allocated) {
printf("%d\t\t%d\t\tNot Allocated\n", i + 1, processSize[i]);
}
}
printMemory(memory, m);
}
void worstFit(int memory[], int blockSize[], int processSize[], int m, int n) {
printf("Process No.\tProcess Size\tBlock Size\n");
for (int i = 0; i < n; i++) {
int worstIdx = -1;
for (int j = 0; j < m; j++) {
if (blockSize[j] >= processSize[i] && memory[j] == 0) {
if (worstIdx == -1 || blockSize[j] > blockSize[worstIdx]) {
worstIdx = j;
}
}
}
if (worstIdx != -1) {
memory[worstIdx] = processSize[i];
printf("%d\t\t%d\t\t%d\n", i + 1, processSize[i], blockSize[worstIdx]);
} else {
printf("%d\t\t%d\t\tNot Allocated\n", i + 1, processSize[i]);
}
}
printMemory(memory, m);
}
No comments:
Post a Comment