Memory Partition Allocation with First-Fit, Best-Fit, and Worst-Fit

Verified Sources

Sep 14, 2026

We have 5 fixed memory partitions (in order) of sizes: 100 KB, 500 KB, 200 KB, 300 KB, 600 KB. Processes arrive (in order) with sizes: 212 KB, 417 KB, 112 KB, 426 KB.

We apply three contiguous memory allocation heuristics: First-Fit , Best-Fit , and Worst-Fit.

Assumption (standard for such problems): after a process is placed, the partition is reduced/left as a remaining “hole” (external fragmentation), and subsequent allocations consider the remaining free space as available.

First Fit vs Best Fit vs Worst Fit (Memory Allocation) - Explanation

Apply First-Fit, Best-Fit, Worst-Fit (process order preserved)

1
Step 1
Free partition sizes in order: [100, 500, 200, 300, 600] KB.
2
Step 2
First partition that fits is 500 KB (since 100 < 212). Place into 500 → remaining hole becomes 500−212=288 KB.
3
Step 3
Scan partitions in order using current remaining free sizes: remaining holes include 288, 200, 300, 600 (and 100 is still 100). First that fits 417 KB is 600 KB → remaining becomes 600−417=183 KB.
4
Step 4
Scan again: first free hole ≥112 is 288 KB → remaining becomes 288−112=176 KB.
5
Step 5
Free holes now are: 100, 176, 200, 300, 183 (in their original order positions). None is ≥426 KB, so it cannot be placed.

First-Fit final placement result

Let each placement be recorded as (process → chosen partition → remaining hole).

212 KB → 500 KB → 288 KB hole
417 KB → 600 KB → 183 KB hole
112 KB → 288 KB → 176 KB hole
426 KB → cannot be allocated (no hole ≥ 426 KB)

So, under First-Fit, 3 of 4 processes are placed; total free-space usage is limited by the remaining hole sizes.

Best-Fit placement (smallest hole that fits)

1
Step 1
Among holes ≥212: 500, 200 (no), 300, 600 → candidates are 500, 300, 600. Smallest that fits is 300 KB → remaining becomes 300−212=88 KB.
2
Step 2
Remaining holes: 100, (500), 200, 88, 600. Holes ≥417: 500 and 600. Smallest is 500 → remaining becomes 500−417=83 KB.
3
Step 3
Now holes include: 100, 83, 200, 88, 600(remaining? actually 600 is untouched because 417 went into 500). Wait: in this model 600 is still 600. Holes ≥112: 200 and 600 (also 88 and 83 are too small, and 100 is too small). Smallest that fits is 200 → remaining becomes 200−112=88 KB.
4
Step 4
Current free holes are 100, 83, 88, 88, 600. Only 600 fits ≥426 → allocate into 600 → remaining becomes 600−426=174 KB.

Best-Fit final placement result

212 KB → 300 KB → 88 KB hole
417 KB → 500 KB → 83 KB hole
112 KB → 200 KB → 88 KB hole
426 KB → 600 KB → 174 KB hole

All 4 of 4 processes are placed successfully.

Worst-Fit placement (largest hole that fits)

1
Step 1
Largest hole ≥212 is 600 → remaining becomes 600−212=388 KB.
2
Step 2
Now the largest hole ≥417 is 500 KB? (sizes are 100, 500, 200, 300, 388). Candidates ≥417: only 500 (since 388 < 417). Place 417 into 500 → remaining becomes 500−417=83 KB.
3
Step 3
Now holes: 100, 83, 200, 300, 388. Largest hole ≥112 is 388 → remaining becomes 388−112=276 KB.
4
Step 4
Now holes: 100, 83, 200, 300, 276. None is ≥426 KB → cannot place.

Worst-Fit final placement result

212 KB → 600 KB → 388 KB hole
417 KB → 500 KB → 83 KB hole
112 KB → 388 KB → 276 KB hole
426 KB → cannot be allocated (max free hole is 300 KB)

So Worst-Fit also places 3 of 4 processes.

Process Placement Outcome by Algorithm

Number of processes successfully allocated out of 4

Which algorithm makes the most efficient use of memory?

A common criterion in these exercises is maximizing number of processes placed (and equivalently, minimizing the likelihood the later large process cannot be satisfied). Under that criterion:

First-Fit: places 212, 417, 112; fails to place 426 (only 3/4 placed).
Worst-Fit: places 212, 417, 112; fails to place 426 (only 3/4 placed).
Best-Fit: places 212, 417, 112, 426 (4/4 placed).

Therefore, Best-Fit makes the most efficient use of memory because it successfully allocates all requested processes, avoiding the situation where the final large process cannot fit.

Key takeaways and subtle points

Pro Tip

When doing these by hand, track remaining hole sizes after each placement in order (especially for First-Fit). For Best-Fit/Worst-Fit, always pick the smallest/largest qualifying hole among the currently free holes.

Common mistake to avoid

Do not choose a partition based only on the original sizes once processes start modifying (splitting) the partitions. Decisions for later processes depend on the updated free-hole sizes.

Quick self-check

1 / 4

Question · Term

First-Fit rule?

Click to reveal

Answer · Definition

Allocate to the first (lowest-index) free partition that is large enough for the process.

Knowledge Check

Question 1 of 4

Q1Single choice

Under First-Fit, which partition is used for the 212 KB process?

300 KB

500 KB

600 KB

None (cannot be placed)

Explore Related Topics

Memory Allocation with First-Fit and Best-Fit

Quick Sort Algorithm and Its Best-, Worst-, and Average-Case Time Complexities

Fixed Partition vs Variable Partition in Operating Systems, and the Need for Compaction

Fixed and variable partitioning are contiguous memory allocation schemes that differ in when partitions are created and the type of fragmentation they produce, prompting the use of compaction.

Fixed partitioning: static predefined partitions, simple implementation, limited multiprogramming, suffers internal fragmentation (e.g., a $20\text{ KB}$ process in a $32\text{ KB}$ partition).
Variable partitioning: dynamic partitions sized to each process, higher memory utilization, but creates external fragmentation requiring placement algorithms.
Compaction moves processes to coalesce free holes, turning scattered space such as $10\text{ KB}+12\text{ KB}+18\text{ KB}=40\text{ KB}$ into a single $40\text{ KB}$ block for a $30\text{ KB}$ request.
Compaction is expensive because it involves process relocation and address updates.

Browse all research articles