Memory Allocation with First-Fit and Best-Fit

Verified Sources

May 27, 2026

In contiguous memory allocation systems, the operating system selects a free partition or hole for each incoming process according to a placement rule such as first-fit or best-fit.2 These strategies influence fragmentation and overall memory efficiency.2

We are given memory blocks, in order:

Partition	Size
1	100 KB
2	500 KB
3	200 KB
4	300 KB
5	600 KB

Processes arrive in order:

Process	Size
P1	212 KB
P2	417 KB
P3	112 KB
P4	426 KB

Under first-fit, the allocator scans memory from the beginning and places each process into the first sufficiently large free block. Under best-fit, it scans all available blocks and chooses the smallest one that can still hold the process, aiming to reduce immediate leftover space.2

First-Fit Allocation in Operating Systems - Defines first-fit scanning behavior and discusses fragmentation effects. ↩ ↩² ↩³
First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩ ↩²
Memory Management in Operating System - Summarizes first-fit, best-fit, and fragmentation concepts in OS memory management. ↩ ↩²

First Fit, Best Fit, Next Fit, Worst Fit Memory Allocation

Key Interpretation

This problem is typically solved using variable-sized free blocks, where any leftover part of a block remains available for later allocation. That is why a $500$ KB block used for a $212$ KB process leaves a reusable $288$ KB hole.

First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩

First-Fit Allocation Walkthrough

1
Step 1
Scan from the first partition: $100$ is too small, $500$ is the first block large enough, so allocate P1 there. Remaining free space in that block becomes $500 - 212 = 288$ KB.

Footnotes

First-Fit Allocation in Operating Systems - Defines first-fit scanning behavior and discusses fragmentation effects. ↩
2
Step 2
Scan again from the beginning of memory among current free blocks: $100$ , $288$ , $200$ , and $300$ are too small; $600$ is the first block large enough, so allocate P2 to the $600$ KB block. Remaining free space becomes $600 - 417 = 183$ KB.

Footnotes

First-Fit Allocation in Operating Systems - Defines first-fit scanning behavior and discusses fragmentation effects. ↩
3
Step 3
Scan from the beginning: $100$ is too small, then $288$ is large enough, so allocate P3 there. Remaining free space becomes $288 - 112 = 176$ KB.

Footnotes

First-Fit Allocation in Operating Systems - Defines first-fit scanning behavior and discusses fragmentation effects. ↩
4
Step 4
Scan current free blocks: $100$ , $176$ , $200$ , $300$ , and $183$ are all too small. Therefore P4 cannot be allocated and must wait.2

Footnotes

First-Fit Allocation in Operating Systems - Defines first-fit scanning behavior and discusses fragmentation effects. ↩

Memory Management in Operating System - Summarizes first-fit, best-fit, and fragmentation concepts in OS memory management. ↩

The resulting first-fit state is:

Process	Allocation
P1 = 212 KB	placed in 500 KB block, leaving 288 KB
P2 = 417 KB	placed in 600 KB block, leaving 183 KB
P3 = 112 KB	placed in leftover 288 KB block, leaving 176 KB
P4 = 426 KB	not allocated

Final free blocks after first-fit:

Free block sizes
100 KB, 176 KB, 200 KB, 300 KB, 183 KB

Notice the important effect of external fragmentation: although total remaining free memory is $100 + 176 + 200 + 300 + 183 = 959$ KB, no single block is at least $426$ KB, so P4 still cannot be placed.2

\text{Largest free block after first-fit} = 300 \text{ KB} < 426 \text{ KB}

Thus, first-fit leaves enough total memory but not enough contiguous memory for the last process.2

Memory Management in Operating System - Summarizes first-fit, best-fit, and fragmentation concepts in OS memory management. ↩ ↩²
OPERATING SYSTEMS - Real Memory Management PDF - Explains placement algorithms and external fragmentation in contiguous allocation. ↩ ↩²

Best-Fit Allocation Walkthrough

1
Step 1
Among all free blocks large enough for $212$ KB, the candidates are $500$ , $300$ , and $600$ . The smallest adequate block is $300$ , so allocate P1 there.2 Remaining free space becomes $300 - 212 = 88$ KB.

Footnotes

First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩

Memory Management in Operating System - Summarizes first-fit, best-fit, and fragmentation concepts in OS memory management. ↩
2
Step 2
Current adequate blocks are $500$ and $600$ . The smallest adequate block is $500$ , so allocate P2 there. Remaining free space becomes $500 - 417 = 83$ KB.

Footnotes

First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩
3
Step 3
Current free blocks are $100$ , $83$ , $200$ , $88$ , and $600$ . The adequate blocks are $200$ and $600$ , so choose $200$ as the smallest adequate block.2 Remaining free space becomes $200 - 112 = 88$ KB.

Footnotes

First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩

Memory Management in Operating System - Summarizes first-fit, best-fit, and fragmentation concepts in OS memory management. ↩
4
Step 4
Current free blocks are $100$ , $83$ , $88$ , $88$ , and $600$ . Only $600$ is large enough, so allocate P4 there. Remaining free space becomes $600 - 426 = 174$ KB.

Footnotes

First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩

The resulting best-fit state is:

Process	Allocation
P1 = 212 KB	placed in 300 KB block, leaving 88 KB
P2 = 417 KB	placed in 500 KB block, leaving 83 KB
P3 = 112 KB	placed in 200 KB block, leaving 88 KB
P4 = 426 KB	placed in 600 KB block, leaving 174 KB

Final free blocks after best-fit:

Free block sizes
100 KB, 83 KB, 88 KB, 88 KB, 174 KB

All four processes are allocated successfully. This aligns with standard best-fit behavior: choosing the smallest adequate free block tends to preserve larger blocks for later large requests.2

First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩
Memory Management in Operating System - Summarizes first-fit, best-fit, and fragmentation concepts in OS memory management. ↩

Processes Successfully Allocated

Comparison of how many processes each algorithm places

A direct efficiency comparison can be made in two ways:

Number of processes allocated: best-fit allocates all $4$ processes, while first-fit allocates only $3$ .2
Memory utilization for this sequence: total requested memory is

212 + 417 + 112 + 426 = 1167 \text{ KB}

Under first-fit, allocated memory is

212 + 417 + 112 = 741 \text{ KB}

Under best-fit, allocated memory is

1167 \text{ KB}

So best-fit uses more of the available memory to satisfy actual process demand in this particular case.2

Metric	First-Fit	Best-Fit
Processes allocated	3	4
Requested memory satisfied	741 KB	1167 KB
Largest remaining free block	300 KB	174 KB
P4 allocated?	No	Yes

This example is a classic case where best-fit is more efficient because it avoids consuming large blocks too early.2

First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩ ↩² ↩³
OPERATING SYSTEMS - Real Memory Management PDF - Explains placement algorithms and external fragmentation in contiguous allocation. ↩ ↩²
Memory Management in Operating System - Summarizes first-fit, best-fit, and fragmentation concepts in OS memory management. ↩

Exam Strategy

For first-fit, always scan from the beginning and stop at the first usable block. For best-fit, compare all usable blocks before choosing. This prevents mistakes in allocation order.2

First-Fit Allocation in Operating Systems - Defines first-fit scanning behavior and discusses fragmentation effects. ↩
First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩

Common Mistake

Do not conclude that first-fit is better just because it may search less. In this problem, search speed is not the question; allocation efficiency is. Best-fit is more efficient here because it places all four processes.3

First-Fit Allocation in Operating Systems - Defines first-fit scanning behavior and discusses fragmentation effects. ↩
First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩
Memory Management in Operating System - Summarizes first-fit, best-fit, and fragmentation concepts in OS memory management. ↩

Process	Placement
$212$ KB	$500$ KB block
$417$ KB	$600$ KB block
$112$ KB	leftover $288$ KB block from the $500$ KB allocation
$426$ KB	not allocated

Remaining free blocks: $100$ , $176$ , $200$ , $300$ , $183$ KB.

Concept Checks and Clarifications

Allocation Sequence Across the Two Algorithms

P1 = 212 KB

Step 1

First-fit selects $500$ KB; best-fit selects $300$ KB.2"

First-Fit Allocation in Operating Systems - Defines first-fit scanning behavior and discusses fragmentation effects. ↩
First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩

P2 = 417 KB

Step 2

First-fit selects $600$ KB; best-fit selects $500$ KB.2"

First-Fit Allocation in Operating Systems - Defines first-fit scanning behavior and discusses fragmentation effects. ↩
First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩

P3 = 112 KB

Step 3

First-fit uses leftover $288$ KB; best-fit uses $200$ KB.2"

First-Fit Allocation in Operating Systems - Defines first-fit scanning behavior and discusses fragmentation effects. ↩
First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩

P4 = 426 KB

Step 4

First-fit fails because no contiguous free block is large enough; best-fit still has $600$ KB available and succeeds.2"

First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩
OPERATING SYSTEMS - Real Memory Management PDF - Explains placement algorithms and external fragmentation in contiguous allocation. ↩

Final Conclusion

For the partitions $100$ , $500$ , $200$ , $300$ , and $600$ KB and the processes $212$ , $417$ , $112$ , and $426$ KB, the placements are:

First-fit:
$212 \rightarrow 500$ ,
$417 \rightarrow 600$ ,
$112 \rightarrow 288$ leftover,
$426 \rightarrow$ not allocated.2
Best-fit:
$212 \rightarrow 300$ ,
$417 \rightarrow 500$ ,
$112 \rightarrow 200$ ,
$426 \rightarrow 600$ .2

Therefore, best-fit makes the most efficient use of memory in this case because it allocates all four processes, whereas first-fit allocates only three.2

First-Fit Allocation in Operating Systems - Defines first-fit scanning behavior and discusses fragmentation effects. ↩
OPERATING SYSTEMS - Real Memory Management PDF - Explains placement algorithms and external fragmentation in contiguous allocation. ↩ ↩² ↩³
First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩ ↩²

Knowledge Check

Question 1 of 4

Q1Single choice

In first-fit, where is the $212$ KB process placed?

In the $500$ KB partition

In the $300$ KB partition

In the $200$ KB partition

In the $100$ KB partition

Explore Related Topics

Virtual Memory, Its Implementation, and the Role of the TLB

Virtual memory abstracts physical RAM by giving each process a large contiguous logical address space, implemented with paging, page tables, and a Translation Lookaside Buffer (TLB) that caches recent translations.

Provides protection, simplifies programming, enables demand paging and sharing of code/pages.
Virtual address = (VPN, offset); physical address = (PFN, offset) with VPN → PFN via TLB or page‑table walk.
Effective access time: $EAT = \alpha (m+\epsilon) + (1-\alpha)(2m+\epsilon)$ , so high TLB hit rate $\alpha$ is critical.
Multi‑level page tables reduce memory use for sparse address spaces.
TLB reach = (entries) × (page size); exceeding it causes TLB thrashing and performance loss.

Systems Programming: Processes, Memory, Concurrency, and Operating-System Interfaces

SSTF Disk Scheduling Worked Example: Total Head Movement for the Given Request Queue

The example applies the Shortest Seek Time First (SSTF) disk‑scheduling algorithm to a pending request queue, starting from head position 143, and computes the total cylinder movement.

Service order by minimum distance:  $143 \rightarrow 130 \rightarrow 86 \rightarrow 913 \rightarrow 948 \rightarrow 1022 \rightarrow 1470 \rightarrow 1509 \rightarrow 1750 \rightarrow 1774$
Stepwise moves:  $13, 44, 827, 35, 74, 448, 39, 241, 24$  cylinders, giving total movement $1745$ cylinders
The previous request at  $125$ only hints at recent direction; SSTF selects the nearest pending request regardless of it
SSTF typically lowers seek time versus FIFO but can starve distant requests, and a straightforward simulation runs in $O(n^2)$ time.

Browse all research articles

Memory Allocation with First-Fit and Best-Fit

Footnotes

First Fit, Best Fit, Next Fit, Worst Fit Memory Allocation

Key Interpretation

Footnotes

First-Fit Allocation Walkthrough

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

Best-Fit Allocation Walkthrough

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

Processes Successfully Allocated

Footnotes

Exam Strategy

Footnotes

Common Mistake

Footnotes

Concept Checks and Clarifications

Allocation Sequence Across the Two Algorithms

P1 = 212 KB

Footnotes

P2 = 417 KB

Footnotes

P3 = 112 KB

Footnotes

P4 = 426 KB

Footnotes

Final Conclusion

Footnotes

Knowledge Check

Explore Related Topics