Lab 9
Q1. Write a Program to implement best, worst, first fit memory allocation and
also calculate internal and external fragmentation
Sols.
Code:
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
struct Block {
int size; // size of memory block
bool allocated; // flag to check if block is allocated
};
struct Process {
int size; // size of the process
int allocatedBlock; // index of allocated block
};
// Function to print memory blocks and processes in vertical direction
void printMemoryAndProcesses(const vector<Block>& blocks, const vector<Process>&
processes) {
cout << "--- Memory Blocks ---\n";
for (int i = 0; i < [Link](); i++) {
cout << "Block " << i + 1 << ": " << blocks[i].size << " units\n";
}
cout << "\n--- Processes ---\n";
for (int i = 0; i < [Link](); i++) {
cout << "Process " << i + 1 << ": " << processes[i].size << " units\n";
}
cout << endl;
}
// Function to calculate internal and external fragmentation
void calculateFragmentation(const vector<Block>& blocks, const vector<Process>&
processes) {
int internalFragmentation = 0;
int externalFragmentation = 0;
// Calculate internal fragmentation
for (int i = 0; i < [Link](); i++) {
if (blocks[i].allocated) {
// Internal fragmentation: Block size - Process size
for (int j = 0; j < [Link](); j++) {
if (processes[j].allocatedBlock == i) {
internalFragmentation += blocks[i].size - processes[j].size;
break;
}
}
} else {
Lab 9
// External fragmentation: sum of free blocks
externalFragmentation += blocks[i].size;
}
}
cout << "Internal Fragmentation: " << internalFragmentation << " units\n";
cout << "External Fragmentation: " << externalFragmentation << " units\n\n";
}
// Function to implement First Fit algorithm
void firstFit(vector<Block>& blocks, vector<Process>& processes) {
bool allocated[[Link]()] = {false};
for (int i = 0; i < [Link](); i++) {
for (int j = 0; j < [Link](); j++) {
if (!blocks[j].allocated && blocks[j].size >= processes[i].size) {
blocks[j].allocated = true;
processes[i].allocatedBlock = j;
allocated[i] = true;
cout << "Process " << i + 1 << " allocated to Block " << j + 1 << " (First Fit)\n";
break;
}
}
}
// Print processes that couldn't be allocated memory
for (int i = 0; i < [Link](); i++) {
if (!allocated[i]) {
cout << "Process " << i + 1 << " couldn't be allocated memory (First Fit)\n";
}
}
calculateFragmentation(blocks, processes);
}
// Function to implement Best Fit algorithm
void bestFit(vector<Block>& blocks, vector<Process>& processes) {
bool allocated[[Link]()] = {false};
for (int i = 0; i < [Link](); i++) {
int bestIdx = -1;
int minSize = INT_MAX;
for (int j = 0; j < [Link](); j++) {
if (!blocks[j].allocated && blocks[j].size >= processes[i].size && blocks[j].size -
processes[i].size < minSize) {
minSize = blocks[j].size - processes[i].size;
bestIdx = j;
}
}
if (bestIdx != -1) {
blocks[bestIdx].allocated = true;
processes[i].allocatedBlock = bestIdx;
allocated[i] = true;
cout << "Process " << i + 1 << " allocated to Block " << bestIdx + 1 << " (Best Fit)\n";
}
Lab 9
}
// Print processes that couldn't be allocated memory
for (int i = 0; i < [Link](); i++) {
if (!allocated[i]) {
cout << "Process " << i + 1 << " couldn't be allocated memory (Best Fit)\n";
}
}
calculateFragmentation(blocks, processes);
}
// Function to implement Worst Fit algorithm
void worstFit(vector<Block>& blocks, vector<Process>& processes) {
bool allocated[[Link]()] = {false};
for (int i = 0; i < [Link](); i++) {
int worstIdx = -1;
int maxSize = -1;
for (int j = 0; j < [Link](); j++) {
if (!blocks[j].allocated && blocks[j].size >= processes[i].size && blocks[j].size -
processes[i].size > maxSize) {
maxSize = blocks[j].size - processes[i].size;
worstIdx = j;
}
}
if (worstIdx != -1) {
blocks[worstIdx].allocated = true;
processes[i].allocatedBlock = worstIdx;
allocated[i] = true;
cout << "Process " << i + 1 << " allocated to Block " << worstIdx + 1 << " (Worst
Fit)\n";
}
}
// Print processes that couldn't be allocated memory
for (int i = 0; i < [Link](); i++) {
if (!allocated[i]) {
cout << "Process " << i + 1 << " couldn't be allocated memory (Worst Fit)\n";
}
}
calculateFragmentation(blocks, processes);
}
// Function to implement Next Fit algorithm
void nextFit(vector<Block>& blocks, vector<Process>& processes) {
bool allocated[[Link]()] = {false};
int lastIdx = 0; // Start searching from the first block
for (int i = 0; i < [Link](); i++) {
bool allocatedFlag = false;
for (int j = lastIdx; j < [Link](); j++) {
if (!blocks[j].allocated && blocks[j].size >= processes[i].size) {
blocks[j].allocated = true;
processes[i].allocatedBlock = j;
lastIdx = j; // Update the search starting point
Lab 9
allocated[i] = true;
cout << "Process " << i + 1 << " allocated to Block " << j + 1 << " (Next Fit)\n";
allocatedFlag = true;
break;
}
}
if (!allocatedFlag) {
for (int j = 0; j < lastIdx; j++) {
if (!blocks[j].allocated && blocks[j].size >= processes[i].size) {
blocks[j].allocated = true;
processes[i].allocatedBlock = j;
lastIdx = j;
allocated[i] = true;
cout << "Process " << i + 1 << " allocated to Block " << j + 1 << " (Next Fit)\n";
break;
}
}
}
}
// Print processes that couldn't be allocated memory
for (int i = 0; i < [Link](); i++) {
if (!allocated[i]) {
cout << "Process " << i + 1 << " couldn't be allocated memory (Next Fit)\n";
}
}
calculateFragmentation(blocks, processes);
}
int main() {
// Memory blocks sizes
vector<Block> blocks = {
{100, false},
{500, false},
{200, false},
{300, false},
{600, false}
};
// Process sizes
vector<Process> processes = {
{212, -1},
{417, -1},
{112, -1},
{426, -1}
};
// Display memory blocks and processes
printMemoryAndProcesses(blocks, processes);
// Call the allocation methods
cout << "\n--- First Fit Allocation ---\n";
firstFit(blocks, processes);
Lab 9
// Reset allocation status for other algorithms
for (auto& block : blocks) [Link] = false;
for (auto& process : processes) [Link] = -1;
cout << "\n--- Best Fit Allocation ---\n";
bestFit(blocks, processes);
// Reset allocation status for other algorithms
for (auto& block : blocks) [Link] = false;
for (auto& process : processes) [Link] = -1;
cout << "\n--- Worst Fit Allocation ---\n";
worstFit(blocks, processes);
// Reset allocation status for other algorithms
for (auto& block : blocks) [Link] = false;
for (auto& process : processes) [Link] = -1;
cout << "\n--- Next Fit Allocation ---\n";
nextFit(blocks, processes);
return 0;
}
Output: