Green University of Bangladesh
Department of Computer Science and Engineering (CSE)
Faculty of Sciences and Engineering (FSE)
Semester: (Fall, Year:2024), B.Sc. in CSE (Day)
Lab Report NO 04
Course Title: Operating System Lab
Course Code: CSE 310 Section: 222 D5
Lab Experiment Name: Implementation of first fit contiguous memory allocation
algorithm
Student Details
Name ID
Majedul Islam Shakib 222902025
Lab Date : 19-11-2024
Submission Date : 26-11-2024
Course Teacher’s Name : Jarin Tasnim Tonvi
Lab Report Status
Marks: ………………………………… Signature:.....................
Comments:.............................................. Date:..............................
1
1. TITLE OF THE LAB REPORT EXPERIMENT
Implement first fit contiguous memory allocation algorithm
2. OBJECTIVES / AIM
• Gathering knowledge about memory management concepts.
• To implement the first-fit contiguous memory allocation technique.
• To understand the basics of memory allocation.
• To analyze and calculate internal fragmentation and external fragmentation.
• To identify unallocated files and unutilized memory blocks.
• To optimize memory usage by allocating suitable blocks for files.
3. ALGORITHM
• Read input number_of_blocks.
• Take an array block[] based on the number_of_blocks.
• For each block (from 1 to number_of_blocks), read the fixed block size into block[].
• Read input number_of_files.
• Take an array file[] based on the number_of_files.
• For each file (from 1 to number_of_files), read the file size into file[].
• Initialize arrays block_flag[] to 0 and frag[] to -1.
• For each file i (from 1 to number_of_files) do:
For each block j (from 1 to number_of_blocks) do:
If block_flag[j] == 0 AND block[j] >= file[i]:
Assign the block to the file.
Computes frag[i] = block[j] - file[i].
Mark the block as allocated: block_flag[j] = 1.
Break the inner loop (stop searching for more blocks for this file).
If no block is allocated for file i:
Print that the file could not be allocated.
• For each block j (from 1 to number_of_blocks) do:
If block_flag[j] == 0:
Add the size of the unallocated block to external_frag.
• Print results:
File number, file size, block number, block size, internal fragmentation (for allocated files).
External fragmentation (total size of unallocated blocks).
• End.
4. IMPLEMENTATION IN C
#include <stdio.h>
int main() {
2
int nb, b[10], nf, f[10], bf[10] = {0}, frag[10] = {0}, ef = 0;
int alloc[10] = {-1};
printf("Enter number of blocks: ");
scanf("%d", &nb);
for (int i = 0; i < nb; i++) {
printf("Enter size of block %d: ", i + 1);
scanf("%d", &b[i]);
}
printf("Enter number of files: ");
scanf("%d", &nf);
for (int i = 0; i < nf; i++) {
printf("Enter size of file %d: ", i + 1);
scanf("%d", &f[i]);
}
for (int i = 0; i < nf; i++) {
for (int j = 0; j < nb; j++) {
if (bf[j] == 0 && b[j] >= f[i]) {
frag[i] = b[j] - f[i];
alloc[i] = j;
bf[j] = 1;
break;
}
}
if (alloc[i] == -1) {
printf("\nFile %d of size %d could not be allocated", i + 1, f[i]);
}
}
for (int j = 0; j < nb; j++) {
if (bf[j] == 0) {
ef += b[j];
}
}
printf("\n\nFile_no \t File_size \t Block_no \t Block_size \t
Internal_Fragmentation");
for (int i = 0; i < nf; i++) {
if (alloc[i] != -1) {
int block_no = alloc[i];
printf("\n%d \t\t %d \t\t %d \t\t %d \t\t %d",
i + 1, f[i], block_no + 1, b[block_no], frag[i]);
} else {
printf("\n%d \t\t %d \t\t Not Allocated", i + 1, f[i]);
}
}
printf("\n\nTotal External Fragmentation: %d\n", ef);
return 0;
}
3
5. INPUT / OUTPUT
Output: Here is output for internal fragmentation and external fragmentation.
Figure: Output of First-Fit Algorithm
7. ANALYSIS AND DISCUSSION
This algorithm demonstrates the First-Fit Contiguous Memory Allocation technique, where files are
allocated to the first available memory block that is large enough to accommodate them. The algorithm
systematically iterates through the list of memory blocks and assigns them to files, while tracking internal
fragmentation (unused space within allocated blocks) and external fragmentation (unused space in
unallocated blocks). This algorithm provides a clear understanding of fixed partition memory allocation and
the challenges of fragmentation. While it highlights the simplicity and practicality of the first-fit approach,
it also demonstrates its inefficiencies, particularly with memory wastage.
