Topic 7.3 · Memory Management & Allocation

Free Space Management, Allocation Algorithms & Compaction

3 min read1 question to test yourself

1Definition

Free Space Management is the system mechanism used by an operating system to track unallocated memory blocks (free holes) using data structures such as linked lists. Allocation Algorithms—including First Fit, Next Fit, Best Fit, and Worst Fit—determine which free hole is assigned to an incoming process. Compaction (Defragmentation) is a relocation technique that shuffles memory partitions to merge scattered free holes into one large contiguous block.

2Simple Explanation

When memory contains scattered empty holes, and a new process arrives, the OS must choose which hole to assign.

  • First Fit: Scans the free list from the beginning and picks the very first hole big enough. (Fastest!).
  • Next Fit: Starts scanning from where the last allocation occurred.
  • Best Fit: Scans the entire list and picks the smallest hole big enough. (Leaves tiny useless micro-holes).
  • Worst Fit: Scans the entire list and picks the largest hole available. (Leaves big remaining holes).
  • Compaction: When free space is fragmented into tiny gaps, the OS pauses execution and slides all active processes to the top of RAM, combining all free gaps at the bottom.

3Real-Life Example / Analogy

Packing Suitcases:

  • First Fit: Throwing clothes into the first open pocket in your bag that fits.
  • Best Fit: Searching every pocket in your bag to find the tightest matching pocket.
  • Compaction: Pushing all packed clothes tightly to the left side of a closet so you have one large open space on the right for a big suitcase.

4Diagram / Visual Representation

AFTER COMPACTION

BEFORE COMPACTION

P1 · 2 MB

Free hole · 2 MB

P2 · 3 MB

Free hole · 3 MB

P3 · 1 MB

Free hole · 1 MB

Compaction

P1 · 2 MB

P2 · 3 MB

P3 · 1 MB

One contiguous free hole · 6 MB

5Working / How It Works

  • Allocation Algorithms Execution:
    • First Fit: Search linked list from head -> Select first node where Hole Size≥Process Size\text{Hole Size} \ge \text{Process Size} -> Allocate -> Terminate search. Time complexity O(N)O(N) worst case, very fast average case.
    • Best Fit: Search entire linked list -> Find hole minimizing (Hole Size−Process Size)≥0(\text{Hole Size} - \text{Process Size}) \ge 0 -> Allocate. Time complexity O(N)O(N).
    • Worst Fit: Search entire linked list -> Find hole maximizing Hole Size\text{Hole Size} -> Allocate. Time complexity O(N)O(N).

6Types / Components / Characteristics

  • Allocation Algorithms Comparison:
Algorithm Search Strategy Speed / Time Complexity Primary Advantage Primary Disadvantage
First Fit First hole big enough Fastest High search speed Leaves small holes at start of list
Next Fit Starts search from last allocation Fast Uniform memory distribution May skip suitable holes at start
Best Fit Smallest hole big enough Slow (Scans full list) Minimizes leftover space in partition Creates severe external micro-fragmentation
Worst Fit Largest hole big enough Slow (Scans full list) Leftover space remains large enough for jobs Quickly exhausts large memory holes

7Solved Examples / Problems

Problem: Given memory holes of sizes 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB in order, place processes of sizes 212 KB, 417 KB, 112 KB, and 426 KB using First Fit. Solution:

  1. Process 212 KB:
    • Check 100 KB (Too small) -> Check 500 KB (Fits!).
    • Allocated to 500 KB hole. Remaining hole = 500−212=288 KB500 - 212 = \mathbf{288 \text{ KB}}.
    • Holes list: [100KB, 288KB, 200KB, 300KB, 600KB].
  2. Process 417 KB:
    • Check 100 KB, 288 KB, 200 KB, 300 KB (Too small) -> Check 600 KB (Fits!).
    • Allocated to 600 KB hole. Remaining hole = 600−417=183 KB600 - 417 = \mathbf{183 \text{ KB}}.
    • Holes list: [100KB, 288KB, 200KB, 300KB, 183KB].
  3. Process 112 KB:
    • Check 100 KB (Too small) -> Check 288 KB (Fits!).
    • Allocated to 288 KB hole. Remaining hole = 288−112=176 KB288 - 112 = \mathbf{176 \text{ KB}}.
  4. Process 426 KB:
    • Check all holes: 100KB, 176KB, 200KB, 300KB, 183KB. No single hole ≥426\ge 426 KB!
    • Process 426 KB must WAIT due to External Fragmentation.

8Advantages, Disadvantages & Applications

  • Compaction Advantages: Merges scattered free memory blocks to allow large processes to run.
  • Compaction Disadvantages: Extremely high CPU and bus overhead; requires dynamic execution relocation registers.

9Important Points to Remember

  • First Fit is generally the fastest and most efficient allocation algorithm in practice.
  • Best Fit produces tiny useless free memory micro-holes.

10Test Your Understanding

  1. MCQ: Which memory allocation algorithm searches the entire list of free holes to allocate the smallest block big enough for a process?
    • A) First Fit
    • B) Next Fit
    • C) Best Fit
    • D) Worst Fit
    Show answer
    C.
  2. Conceptual Question: Explain how Compaction resolves external fragmentation and state its primary operational drawback.
  3. Application Question: Trace process allocations for given hole sizes using Best Fit and Worst Fit algorithms.

Finished this topic?

0 of 27 topics read in Operating Systems

Handwritten notes for the exam

Unit-wise SPPU notes and PYQs for this subject.

Helpful? Share it with your class

Free for everyone, no login needed.

Share topic