←Back to Subject
Notes
Notes
Study material and explanations
Diagrams
Diagrams
Visualize concepts easily
Mnemonics
Mnemonics
Tricks to remember faster
One Night Prep
One Night Prep
Short and focused revision
Revision
Revision
Quick summary and key points
Important Questions
Important Questions
Practice most relevant questions
Notes

Contiguous & Non-Contiguous Allocation, Fragmentation (Internal & External) & Compaction

Study material and explanations for Unit 4

Contiguous & Non-Contiguous Allocation, Fragmentation & Compaction

1. Contiguous vs Non-Contiguous Memory Allocation

When a process needs to be loaded into Main Memory (RAM), the Operating System can allocate memory to it using two fundamental approaches:

Figure 4.4: Contiguous Memory Allocation vs Non-Contiguous Memory Allocation
1. Contiguous Memory Allocation
  • Each process is contained in a single continuous (adjacent) block of RAM addresses
  • Simple & fast address translation using Base + Limit registers
  • Types: Fixed Partitioning (MFT) & Variable/Dynamic Partitioning (MVT)
  • Drawback: Suffers from Internal & External Fragmentation
2. Non-Contiguous Memory Allocation
  • A single process is divided into blocks and placed in scattered, non-adjacent locations in RAM
  • Uses a Page Table or Segment Table to keep track of blocks
  • Types: Paging and Segmentation
  • Benefit: Eliminates External Fragmentation (in Paging)!

2. Contiguous Memory Allocation Techniques

In Contiguous Memory Allocation, every process must occupy a single unbroken block of contiguous physical memory. It is implemented in two ways:

A. Fixed-Size Partitioning (MFT — Multiprogramming with a Fixed Number of Tasks)

  • Main Memory (RAM) is divided at system boot time into several fixed-size partitions (blocks) (e.g., four partitions of 100 KB each).
  • Each partition can hold exactly one process.
  • Problem: If a small 30 KB process is placed inside a 100 KB fixed partition, the remaining 70 KB inside that partition is wasted and cannot be given to any other process! This wasted space is called Internal Fragmentation.

B. Variable / Dynamic Partitioning (MVT — Multiprogramming with a Variable Number of Tasks)

  • Initially, all user RAM is treated as one large block of free memory called a Hole.
  • When a process arrives (e.g., needing 75 KB), the OS carves out a partition of exact size 75 KB for it.
  • As processes enter and leave RAM over time, memory becomes a checkerboard of allocated blocks and scattered small free Holes of varying sizes (20 KB, 15 KB, 40 KB), leading to External Fragmentation.

3. Dynamic Storage Allocation Algorithms (First Fit, Best Fit, Worst Fit)

When a new process of size N arrives and there are several free Holes (empty blocks) scattered across RAM, how does the OS choose which hole to allocate? Using one of 3 Dynamic Allocation Strategies (a very popular numerical & theory question in DAVV exams!):

  1. First Fit:
    • Scans the list of free holes from the beginning and allocates the FIRST hole that is big enough (≥ N).
    • Pros: Fastest algorithm because it searches as little as possible.
  2. Best Fit:
    • Searches the entire list of free holes and allocates the SMALLEST hole that is big enough (≥ N), so that the leftover wasted hole is as tiny as possible.
    • Cons: Slower (must scan entire list unless sorted) and leaves behind tiny, unusable leftover slivers (1 KB, 2 KB) across RAM!
  3. Worst Fit:
    • Searches the entire list and allocates the LARGEST available hole, so that the leftover fragment after allocation is still large enough to hold another process later.
    • Cons: Slower and breaks up large holes quickly.

Solved Example: First Fit vs Best Fit vs Worst Fit

Suppose RAM has 4 Free Holes in order: 100 KB, 500 KB, 200 KB, and 300 KB. Where will a new process of size 212 KB be placed?

  • First Fit: Scans from left: 100 KB (too small) → 500 KB (First hole ≥ 212 KB! Allocated here, leaving 288 KB).
  • Best Fit: Checks all holes ≥ 212 KB (500 KB and 300 KB). Smallest fit is 300 KB! (Allocated in 300 KB, leaving 88 KB).
  • Worst Fit: Checks all holes ≥ 212 KB. Largest hole is 500 KB! (Allocated in 500 KB).

4. Fragmentation: Internal vs External Fragmentation

Fragmentation refers to memory space in RAM that is wasted and cannot be used efficiently to allocate processes. There are two types of fragmentation:

Figure 4.5: Internal Fragmentation vs External Fragmentation
1. Internal Fragmentation (Waste INSIDE Block)
  • Occurs when memory is divided into Fixed-Size blocks (Fixed Partitioning / Paging)
  • A process of 18 KB is given a 20 KB block → 2 KB wasted INSIDE the block!
  • Belongs to the allocated partition, so no other process can use it
2. External Fragmentation (Waste OUTSIDE Blocks)
  • Occurs in Variable-Size Contiguous Allocation & Segmentation
  • Total free RAM is 100 KB, but split into scattered holes (`30 KB + 40 KB + 30 KB`), so a 60 KB process cannot fit!
  • Solved using Compaction or Paging

Comparison Table: Internal Fragmentation vs External Fragmentation

This table is a guaranteed 5-mark question in DAVV BCA exams!

Basis Internal Fragmentation External Fragmentation
1. Definition Wasted memory INSIDE an allocated memory block when the block is slightly larger than the process requested. Wasted memory OUTSIDE allocated blocks when enough total free RAM exists, but it is not contiguous (scattered in small holes).
2. Cause Caused by Fixed-Size memory allocation (Fixed Partitioning and Paging). Caused by Variable-Size contiguous allocation as processes are loaded and removed repeatedly.
3. Who Owns the Waste? The wasted space is assigned to a specific partition/process. The wasted holes are free, belonging to no process, yet too small individually.
4. Solution / Remedy Use Variable-sized partitions or smaller page sizes. Use Compaction (shuffling RAM) or Non-Contiguous Paging!

5. Compaction (Defragmentation of RAM)

What is Compaction?

Compaction is a technique used by the Operating System to solve External Fragmentation!

  • How It Works: The OS shifts (shuffles) all currently allocated processes toward one end of Main Memory (RAM) so that all the scattered small free holes combine together at the other end to form one single large contiguous block of free memory!
Figure 4.6: How Compaction Eliminates External Fragmentation
Before Compaction[P1] [Free 30K] [P2] [Free 40K] [P3] [Free 30K]
→ Shift Processes Together →
After Compaction[P1] [P2] [P3] [One Big Free Block: 100 KB!]
  • Now a 60 KB or 100 KB process can easily fit into the combined 100 KB block!

Important Requirement & Drawback of Compaction:

  1. Requires Dynamic (Execution-Time) Address Binding: Because Compaction physically moves running processes to new addresses in RAM, it is ONLY possible if address binding is done dynamically at Execution Time using relocation registers! (If addresses were bound statically at Compile or Load time, Compaction cannot be done).
  2. High CPU Overhead: Moving megabytes of processes in RAM takes CPU time, so an alternative solution is to allow non-contiguous allocation (Paging).

💡 Exam Preparation Tips for DAVV BCA

  • Always draw Figure 4.6 (Before Compaction vs After Compaction) and the Internal vs External Fragmentation table—these two visuals make your Unit 4 answer crystal clear!
  • Remember that Compaction only works when Execution-Time (Dynamic) Address Binding is used.