Simulate memory allocation methods: (i) Best Fit, (ii) Worst Fit and (iii)
Next Fit
Simulate page replacement algorithms: FIFO, LRU
memory allocation methods
Bestfit
#include <stdio.h> // Header file for input/output functions
// Structure to represent a memory hole
struct hole {
int id; // Hole number
int size; // Size of the hole
};
// Structure to represent a process
struct process {
int id; // Process number
int size; // Size required by process
};
int main() {
int nh, np; // nh = number of holes, np = number of processes
// Input number of holes
printf("Enter number of holes: ");
scanf("%d", &nh);
struct hole h[nh]; // Array to store holes
// Input hole sizes
for (int i = 0; i < nh; i++) {
h[i].id = i + 1; // Assign hole number
printf("Enter size of hole %d: ", i + 1);
scanf("%d", &h[i].size); // Read hole size
}
// Input number of processes
printf("\nEnter number of processes: ");
scanf("%d", &np);
struct process p[np]; // Array to store processes
// Input process sizes
for (int i = 0; i < np; i++) {
p[i].id = i + 1; // Assign process number
printf("Enter size of process %d: ", i + 1);
scanf("%d", &p[i].size); // Read process size
}
int allocation[np]; // Stores which hole is allocated to each process
// Initialize all processes as not allocated (-1)
for (int i = 0; i < np; i++) {
allocation[i] = -1;
}
// 🔷 BEST FIT ALGORITHM STARTS HERE
for (int i = 0; i < np; i++) { // Loop through each process
int bestIndex = -1; // To store index of best hole
for (int j = 0; j < nh; j++) { // Check all holes
// Check if hole can fit the process
if (h[j].size >= p[i].size) {
// Select smallest suitable hole
if (bestIndex == -1 || h[j].size < h[bestIndex].size) {
bestIndex = j; // Update best hole index
}
}
}
// If a suitable hole is found
if (bestIndex != -1) {
allocation[i] = bestIndex; // Allocate hole to process
h[bestIndex].size -= p[i].size; // Reduce hole size
}
}
// Display output
printf("\nProcess No\tProcess Size\tHole No\n");
for (int i = 0; i < np; i++) {
if (allocation[i] != -1) {
// If allocated, print hole number
printf("%d\t\t%d\t\t%d\n",
p[i].id, p[i].size, allocation[i] + 1);
} else {
// If not allocated
printf("%d\t\t%d\t\tNot Allocated\n",
p[i].id, p[i].size);
}
}
return 0; // End of program
}
Output:
Enter number of holes: 4
Enter size of hole 1: 200
Enter size of hole 2: 100
Enter size of hole 3:
150
Enter size of hole 4: 250
Enter number of processes: 4
Enter size of process 1: 400
Enter size of process 2: 100
Enter size of process 3: 120
Enter size of process 4: 200
Process No Process Size Hole No
1 400 Not Allocated
2 100 2
3 120 3
4 200 1
WorstFit
#include <stdio.h> // Header file for input/output functions
// Structure to represent a memory hole
struct hole {
int id; // Hole number
int size; // Size of the hole
};
// Structure to represent a process
struct process {
int id; // Process number
int size; // Size required by process
};
int main() {
int nh, np; // nh = number of holes, np = number of processes
// Input number of holes
printf("Enter number of holes: ");
scanf("%d", &nh);
struct hole h[nh]; // Array to store holes
// Input hole sizes
for (int i = 0; i < nh; i++) {
h[i].id = i + 1; // Assign hole number
printf("Enter size of hole %d: ", i + 1);
scanf("%d", &h[i].size); // Read hole size
}
// Input number of processes
printf("\nEnter number of processes: ");
scanf("%d", &np);
struct process p[np]; // Array to store processes
// Input process sizes
for (int i = 0; i < np; i++) {
p[i].id = i + 1; // Assign process number
printf("Enter size of process %d: ", i + 1);
scanf("%d", &p[i].size); // Read process size
}
int allocation[np]; // Stores which hole is allocated
// Initialize all processes as not allocated (-1)
for (int i = 0; i < np; i++) {
allocation[i] = -1;
}
// 🔷 WORST FIT ALGORITHM STARTS HERE
for (int i = 0; i < np; i++) { // Loop through each process
int worstIndex = -1; // To store index of largest hole
for (int j = 0; j < nh; j++) { // Check all holes
// Check if hole can fit the process
if (h[j].size >= p[i].size) {
// Select largest suitable hole
if (worstIndex == -1 || h[j].size > h[worstIndex].size) {
worstIndex = j; // Update worst hole index
}
}
}
// If a suitable hole is found
if (worstIndex != -1) {
allocation[i] = worstIndex; // Allocate hole
h[worstIndex].size -= p[i].size; // Reduce hole size
}
}
// Display output
printf("\nProcess No\tProcess Size\tHole No\n");
for (int i = 0; i < np; i++) {
if (allocation[i] != -1) {
// If allocated
printf("%d\t\t%d\t\t%d\n",
p[i].id, p[i].size, allocation[i] + 1);
} else {
// If not allocated
printf("%d\t\t%d\t\tNot Allocated\n",
p[i].id, p[i].size);
}
}
return 0; // End of program
}
Output
Enter number of holes: 3
Enter size of hole 1: 200
Enter size of hole 2: 130
Enter size of hole 3: 300
Enter number of processes: 3
Enter size of process 1: 150
Enter size of process 2: 100
Enter size of process 3: 120
Process No Process Size Hole No
1 150 3
2 100 1
3 120 3
FIFO Page Replacement
#include <stdio.h> // For printf, scanf
int main()
{
int i, j, n, a[50], frame[10], n0, k;
int avail, count = 0;
// Input number of pages
printf("\nEnter number of pages: ");
scanf("%d", &n);
// Input page reference string
printf("Enter page numbers:\n");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
// Input number of frames
printf("\nEnter number of frames: ");
scanf("%d", &n0);
// Initialize frames to -1 (empty)
for (i = 0; i < n0; i++)
frame[i] = -1;
j = 0; // Pointer for FIFO replacement
printf("\nOutput");
printf("\nRef String\tFrames\n");
// Traverse all pages
for (i = 0; i < n; i++)
{
printf("%d\t\t", a[i]);
avail = 0;
// Check if page already exists (HIT)
for (k = 0; k < n0; k++)
{
if (frame[k] == a[i])
{
avail = 1; // Page found
break;
}
}
// If page not found → PAGE FAULT
if (avail == 0)
{
frame[j] = a[i]; // Replace page using FIFO
j = (j + 1) % n0; // Move pointer circularly
count++; // Increase page fault count
// Print frame contents
for (k = 0; k < n0; k++)
printf("%d\t", frame[k]);
}
printf("\n");
}
// Print total page faults
printf("\nTotal Page Faults = %d\n", count);
return 0;
}
Output
Enter number of pages: 12
Enter page numbers:
1
2
3
4
1
2
5
1
2
3
4
5
Enter number of frames: 3
Output
Ref String Frames
1 1 -1 -1
2 1 2 -1
3 1 2 3
4 4 2 3
1 4 1 3
2 4 1 2
5 5 1 2
1
2
3 5 3 2
4 5 3 4
5
Total Page Faults = 9
LRU
#include <stdio.h>
int main()
{
int p[50], frame[10]; // p = reference string, frame = memory frames
int n, f; // n = number of pages, f = number of frames
int i, j, k, count = 0;
int found, least, pos;
// Input number of pages
printf("Enter number of pages: ");
scanf("%d", &n);
// Input reference string
printf("Enter the reference string:\n");
for(i = 0; i < n; i++)
scanf("%d", &p[i]);
// Input number of frames
printf("Enter number of frames: ");
scanf("%d", &f);
// Initialize frames as empty
for(i = 0; i < f; i++)
frame[i] = -1;
printf("\nRef String\tFrames\n");
// Traverse each page
for(i = 0; i < n; i++)
{
printf("%d\t\t", p[i]);
found = 0;
// Check if page already in frame (HIT)
for(j = 0; j < f; j++)
{
if(frame[j] == p[i])
{
found = 1;
break;
}
}
// If page NOT found → PAGE FAULT
if(found == 0)
{
count++; // Increase page fault
// Check for empty frame first
for(j = 0; j < f; j++)
{
if(frame[j] == -1)
{
frame[j] = p[i];
break;
}
}
// If no empty frame → apply LRU
if(j == f)
{
int min = i, index;
// Find least recently used page
for(j = 0; j < f; j++)
{
for(k = i - 1; k >= 0; k--)
{
if(frame[j] == p[k])
{
if(k < min)
{
min = k;
index = j;
}
break;
}
}
}
// Replace LRU page
frame[index] = p[i];
}
// Print frames after allocation
for(j = 0; j < f; j++)
printf("%d\t", frame[j]);
}
printf("\n");
}
printf("\nTotal Page Faults = %d\n", count);
return 0;
}
Output :
Enter number of pages: 8
Enter the reference string:
31216513
Enter number of frames: 3
Ref String Frames
3 3 -1 -1
1 3 1 -1
2 3 1 2
1
6 6 1 2
5 6 1 5
1
3 3 1 5
Total Page Faults = 6