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
5Working / How It Works
- Allocation Algorithms Execution:
- First Fit: Search linked list from head -> Select first node where -> Allocate -> Terminate search. Time complexity worst case, very fast average case.
- Best Fit: Search entire linked list -> Find hole minimizing -> Allocate. Time complexity .
- Worst Fit: Search entire linked list -> Find hole maximizing -> Allocate. Time complexity .
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:
- Process 212 KB:
- Check 100 KB (Too small) -> Check 500 KB (Fits!).
- Allocated to 500 KB hole. Remaining hole = .
- Holes list:
[100KB, 288KB, 200KB, 300KB, 600KB].
- 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 = .
- Holes list:
[100KB, 288KB, 200KB, 300KB, 183KB].
- Process 112 KB:
- Check 100 KB (Too small) -> Check 288 KB (Fits!).
- Allocated to 288 KB hole. Remaining hole = .
- Process 426 KB:
- Check all holes: 100KB, 176KB, 200KB, 300KB, 183KB. No single hole 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
- 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. - Conceptual Question: Explain how Compaction resolves external fragmentation and state its primary operational drawback.
- Application Question: Trace process allocations for given hole sizes using Best Fit and Worst Fit algorithms.
