In this post, we implement the Best Fit Memory Allocation Algorithm in C++. Unlike First Fit which takes the first block large enough for a job, Best Fit searches through all free blocks and selects the one whose size is closest to the job’s size — the tightest possible fit. The goal is to minimize wasted space inside allocated blocks (internal fragmentation) and preserve large blocks for future large jobs.
What is Best Fit Memory Allocation?
Best Fit works by sorting memory blocks in ascending order of size before allocation. By scanning the sorted list and taking the first block that fits, we automatically pick the smallest block that still accommodates the job. This is the defining characteristic of Best Fit: among all free blocks that are large enough, it selects the one with the smallest size, leaving the rest of the available space in larger blocks undisturbed for future use.
- Sort all memory blocks in ascending order of size.
- For each job, scan the sorted blocks and allocate the first free block whose size ≥ job size. Because blocks are sorted by ascending size, the first fitting block is automatically the smallest one that fits — i.e., the best fit.
- After all allocations are done, re-sort blocks by their original block number so the output table is readable.
Compared to First Fit, Best Fit produces less internal fragmentation per allocation because it picks the tightest available block. However, it tends to leave behind many tiny leftover fragments that are too small to be reused — a form of external fragmentation. It is also slower than First Fit because it must consider all blocks before allocating.
C++ Code Implementation
// ============================================================
// Best Fit Memory Allocation Algorithm in C++
// Allocates the SMALLEST block that is large enough for each job
// Minimizes per-allocation internal fragmentation
// ============================================================
#include <iostream>
using namespace std;
// Represents a single memory block (partition) in main memory
struct MemoryBlock {
int blockNo; // Original block number (used to restore display order after sorting)
int blockSize; // Total size of this memory block
int isOccupied; // 0 = free, 1 = allocated to a job
int jobNo; // Job number currently in this block (0 = empty)
};
// Represents a job (process) that needs memory
struct Job {
int jobNo; // Job number (1-based)
int jobSize; // Memory required by this job
int isAllocated; // 0 = not yet placed, 1 = successfully allocated
};
int main() {
// -------------------------------------------------------
// Step 1: Read memory block information
// -------------------------------------------------------
cout << "\n Enter No of Blocks in memory: ";
int blockCount;
cin >> blockCount;
MemoryBlock memBlocks[99];
MemoryBlock tempBlock; // Temporary variable used during sorting
for (int blockIdx = 0; blockIdx < blockCount; blockIdx++) {
cout << "\n Enter Size of Block " << blockIdx + 1 << ": ";
cin >> memBlocks[blockIdx].blockSize;
memBlocks[blockIdx].blockNo = blockIdx + 1;
memBlocks[blockIdx].isOccupied = 0; // All blocks start free
memBlocks[blockIdx].jobNo = 0; // No job assigned yet
}
// -------------------------------------------------------
// Step 2: Read job information
// -------------------------------------------------------
int jobCount;
cout << "\n Enter No of Jobs: ";
cin >> jobCount;
Job jobs[99];
for (int jobIdx = 0; jobIdx < jobCount; jobIdx++) {
cout << "\n Enter size of Job " << jobIdx + 1 << ": ";
cin >> jobs[jobIdx].jobSize;
jobs[jobIdx].jobNo = jobIdx + 1;
jobs[jobIdx].isAllocated = 0; // Not allocated yet
}
// Display entered job data
cout << "\n JobNo\tJobSize";
for (int jobIdx = 0; jobIdx < jobCount; jobIdx++) {
cout << "\n " << jobs[jobIdx].jobNo << "\t" << jobs[jobIdx].jobSize;
}
// -------------------------------------------------------
// Step 3: Sort memory blocks by size ASCENDING (Best Fit preparation)
// KEY INSIGHT: After sorting, the first block that fits a given job
// IS the smallest fitting block — which is exactly "best fit".
// We sort entire structs (not just sizes) so blockNo travels with
// the block data and the re-sort in Step 5 works correctly.
// -------------------------------------------------------
for (int outer = 0; outer < blockCount - 1; outer++) {
for (int inner = outer + 1; inner < blockCount; inner++) {
if (memBlocks[outer].blockSize > memBlocks[inner].blockSize) {
// Swap entire MemoryBlock records to keep all fields consistent
tempBlock = memBlocks[outer];
memBlocks[outer] = memBlocks[inner];
memBlocks[inner] = tempBlock;
}
}
}
// After sorting: memBlocks[0] has the smallest block, memBlocks[last] the largest
// -------------------------------------------------------
// Step 4: Best Fit Allocation
// For each job, scan the size-sorted block list and allocate
// the FIRST free block that fits (= the smallest fitting block
// because of the ascending sort in Step 3)
// -------------------------------------------------------
for (int jobIdx = 0; jobIdx < jobCount; jobIdx++) {
for (int blockIdx = 0; blockIdx < blockCount; blockIdx++) {
if (memBlocks[blockIdx].isOccupied == 0
&& memBlocks[blockIdx].blockSize >= jobs[jobIdx].jobSize
&& jobs[jobIdx].isAllocated != 1) {
memBlocks[blockIdx].jobNo = jobs[jobIdx].jobNo;
memBlocks[blockIdx].isOccupied = 1;
jobs[jobIdx].isAllocated = 1;
break; // Stop after the first (= best/smallest) fitting block in sorted order
}
}
}
// -------------------------------------------------------
// Step 5: Re-sort blocks by original block number for display
// We want output to show Block1, Block2, Block3... in order,
// not in the ascending-size order used during allocation.
// -------------------------------------------------------
for (int outer = 0; outer < blockCount - 1; outer++) {
for (int inner = outer + 1; inner < blockCount; inner++) {
if (memBlocks[outer].blockNo > memBlocks[inner].blockNo) {
tempBlock = memBlocks[outer];
memBlocks[outer] = memBlocks[inner];
memBlocks[inner] = tempBlock;
}
}
}
// -------------------------------------------------------
// Step 6: Display allocation results
// -------------------------------------------------------
cout << "\n\n BlockNo\tBlockSize\tJobNo\tJobSize\tStatus\tInternal Frag";
for (int blockIdx = 0; blockIdx < blockCount; blockIdx++) {
cout << "\n " << memBlocks[blockIdx].blockNo
<< "\t\t" << memBlocks[blockIdx].blockSize;
if (memBlocks[blockIdx].jobNo != 0) {
int allocatedJobIdx = memBlocks[blockIdx].jobNo - 1;
int internalFrag = memBlocks[blockIdx].blockSize - jobs[allocatedJobIdx].jobSize;
cout << "\t" << memBlocks[blockIdx].jobNo
<< "\t" << jobs[allocatedJobIdx].jobSize
<< "\t" << memBlocks[blockIdx].isOccupied
<< "\t" << internalFrag;
} else {
cout << "\t0\t0\t" << memBlocks[blockIdx].isOccupied << "\t0";
}
}
// Report unallocated jobs
cout << "\n";
for (int jobIdx = 0; jobIdx < jobCount; jobIdx++) {
if (jobs[jobIdx].isAllocated == 0) {
cout << "\n Job " << jobs[jobIdx].jobNo
<< " (size " << jobs[jobIdx].jobSize
<< ") could NOT be allocated — no suitable block found.";
}
}
cout << endl;
return 0;
}
Explanation of the Code
- Why sort before allocating? — The “best fit” block for a given job is the smallest block whose size ≥ job size. By sorting blocks in ascending order of
blockSize, the first block in the sorted list that satisfiesblockSize >= jobSizeis automatically the smallest fitting one. This converts a potentially expensive “find minimum” search into a simple first-fit scan on a sorted array. Without this sort, the same code would be First Fit. - Preserving
blockNoduring sorting — The sort swaps entireMemoryBlockstructs (not just sizes). This meansblockNotravels with the block data. After the re-sort byblockNoin Step 5, each block is mapped back to its original position for display. - Two-phase sort — Sort ascending by size (for allocation), then ascending by
blockNo(for display). This keeps allocation logic clean and output readable. - Allocation loop — Identical structure to First Fit, but operating on the size-sorted array. The
breakstops at the first (smallest) fitting block. The sort is what transforms First Fit into Best Fit. - Internal fragmentation — Computed as
blockSize - jobSizeper allocated block. Best Fit minimizes this per allocation but produces more tiny leftovers overall.
Sample Output
Enter No of Blocks in memory: 4
Enter Size of Block 1: 30
Enter Size of Block 2: 15
Enter Size of Block 3: 50
Enter Size of Block 4: 20
Enter No of Jobs: 4
Enter size of Job 1: 10
Enter size of Job 2: 20
Enter size of Job 3: 30
Enter size of Job 4: 10
JobNo JobSize
1 10
2 20
3 30
4 10
BlockNo BlockSize JobNo JobSize Status Internal Frag
1 30 3 30 1 0
2 15 1 10 1 5
3 50 4 10 1 40
4 20 2 20 1 0
(All 4 jobs allocated successfully)Step-by-Step Explanation of Input/Output
Blocks sorted ascending by size: Block2(15) → Block4(20) → Block1(30) → Block3(50). Jobs are allocated in this sorted order:
- Job 1 (size 10): Sorted list: B2(15), B4(20), B1(30), B3(50). First fit in sorted order = Block2 (size 15 ≥ 10, and the smallest). Internal frag = 15 − 10 = 5.
- Job 2 (size 20): Block2 occupied. Next: Block4 (size 20 ≥ 20) → exact fit! Internal frag = 20 − 20 = 0.
- Job 3 (size 30): Blocks 2, 4 occupied. Next: Block1 (size 30 ≥ 30) → exact fit! Internal frag = 30 − 30 = 0.
- Job 4 (size 10): Blocks 1, 2, 4 occupied. Only Block3 (size 50) remains. Internal frag = 50 − 10 = 40.
- Total internal fragmentation = 5 + 0 + 0 + 40 = 45. All 4 jobs allocated successfully.
Compare with First Fit on the same input: First Fit gets total frag = 55 and fails to place Job 3 entirely. Best Fit wins on both internal fragmentation and allocation success rate for this dataset.
Best Fit vs. First Fit — Comparison
| Criterion | First Fit | Best Fit |
|---|---|---|
| Speed | Faster — stops at first fit | Slower — scans all blocks (via sort) |
| Internal Fragmentation | Higher per allocation | Lower per allocation |
| Large Block Preservation | Poor — uses big blocks for small jobs | Better — picks smallest fitting block |
| External Fragmentation | Lower areas become cluttered | Many tiny unusable gaps left over |
| Allocation Success Rate | May fail even when total free memory is enough | Higher — finds tighter fits |
See Also
Bottom line is…
Best Fit reduces internal fragmentation by tightly fitting each job into the smallest available block. It preserves large blocks for future large jobs and generally achieves a higher allocation success rate than First Fit. The trade-off is speed (a sort pass is needed) and the tendency to produce many tiny leftover fragments that cannot be used — a form of external fragmentation. Neither First Fit nor Best Fit eliminates external fragmentation entirely; only compaction (moving jobs in memory) or non-contiguous allocation strategies like paging achieve that.