Partition Management Techniques

Definition

Partition Management is allocating and managing memory partitions in contiguous memory allocation schemes. Techniques differ in how they divide memory and manage free/allocated space. Critical for efficient memory utilization.

Fixed Partitioning

Concept

Divide memory into predetermined, fixed-size partitions before runtime:

Memory Layout (predetermined):
┌──────────────┐ 0
│    OS        │ (60KB)
├──────────────┤ 60KB
│ Partition 1  │ (64KB)
├──────────────┤ 124KB
│ Partition 2  │ (128KB)
├──────────────┤ 252KB
│ Partition 3  │ (256KB)
├──────────────┤ 508KB
│ Partition 4  │ (512KB)
├──────────────┤ 1020KB
│              │
└──────────────┘ 1024KB (total RAM)

Allocation

OS maintains queue of processes per partition:

Partition 1 (64KB) Queue:
┌─────┐
│Proc │─→ Proc B ─→ (waiting)
│  A  │   (waiting)
└─────┘

Partition 2 (128KB) Queue:
┌─────┐
│Proc │─→ (waiting)
│  C  │
└─────┘

Process waits for partition of sufficient size:

Process D needs 100KB
- Partition 1 (64KB): Too small
- Partition 2 (128KB): Fits! Allocate
- Partition 3 (256KB): Fits but larger, save for bigger

Use best-fit: Partition 2

Advantages

1. Simple Implementation

  • Fixed number of partitions
  • Simple allocation logic

2. No External Fragmentation

  • Each partition independent
  • No holes between partitions

3. Low Overhead

  • Just track which partition in use

Disadvantages

1. Internal Fragmentation

Process smaller than partition wastes space:

Partition 2: 128KB
Process: 50KB allocated
Wasted: 78KB!

Fragmentation = 78/128 = 61% waste!

2. Inflexible

Partition sizes cannot change:

Many 100KB processes, none 256KB:
Partition 4 (256KB) sits mostly empty
Can't give extra space to Partition 1
Stuck until reboot

3. Underutilized

16GB RAM divided into 4 partitions:
4GB, 4GB, 4GB, 4GB
Only run 2 programs each needing 3GB:
Using: 6GB / 16GB = 37.5%
Rest wasted!

When Used

  • Batch processing systems (1960s-1970s)
  • Embedded systems with known workload
  • Real-time systems with fixed number of processes

Example: IBM System/360 (1960s)

Common configuration:
OS: 32KB
Partition A: 64KB
Partition B: 128KB
Partition C: 256KB
Partition D: 512KB
Total: 992KB

Could support 4 simultaneous processes
(compared to 1 without partitions)

Dynamic Partitioning

Concept

Allocate partitions dynamically as processes request memory:

Initial State:
┌──────────────┐
│    OS        │ (60KB)
├──────────────┤
│ Free Space   │ (964KB)
└──────────────┘

Process A requests 100KB:
┌──────────────┐
│    OS        │ (60KB)
├──────────────┤
│ Process A    │ (100KB exactly!)
├──────────────┤
│ Free Space   │ (864KB)
└──────────────┘

Process B requests 150KB:
┌──────────────┐
│    OS        │
├──────────────┤
│ Process A    │
├──────────────┤
│ Process B    │ (150KB exactly!)
├──────────────┤
│ Free Space   │ (714KB)
└──────────────┘

Process A exits:
┌──────────────┐
│    OS        │
├──────────────┤
│ Free Space   │ (100KB)
├──────────────┤
│ Process B    │
├──────────────┤
│ Free Space   │ (714KB)
└──────────────┘

Allocation Strategies

1. First Fit

Allocate first block large enough:

Free blocks: [100KB, 50KB, 200KB, 150KB]
Process needs: 120KB

Scan left to right:
100KB: Too small
50KB: Too small
200KB: Fits! Allocate here

Result: [100KB, 50KB, 80KB_free, 150KB]

Characteristics:

  • ✓ Fast (stop at first fit)
  • ❌ Might leave small fragments

2. Best Fit

Allocate smallest block that fits:

Free blocks: [100KB, 50KB, 200KB, 150KB]
Process needs: 120KB

Check all:
100KB: Too small
50KB: Too small
200KB: Fits, waste = 80KB
150KB: Fits, waste = 30KB

Best fit: 150KB (waste only 30KB)

Result: [100KB, 50KB, 200KB, 120KB, 30KB_free]

Characteristics:

  • ✓ Minimizes waste per allocation
  • ❌ Slower (check all blocks)
  • ❌ Creates many tiny fragments

3. Worst Fit

Allocate largest block:

Free blocks: [100KB, 50KB, 200KB, 150KB]
Process needs: 120KB

Use largest: 200KB
Rationale: Leave bigger block for larger process

Result: [100KB, 50KB, 80KB_free, 150KB]

Characteristics:

  • ❌ Worst performance (leaves most fragmentation)
  • Rarely used

4. Next Fit

Continue from last allocation:

Last allocation ended at position P
Find next free block after P (wrapping around)

Variant: Spread allocations more evenly

Characteristics:

  • ✓ Fair allocation
  • ✓ Similar to First Fit
  • ✓ Slightly better fragmentation

Comparison

StrategySpeedFragmentationUsage
First Fit▓▓▓▓▓▓▓▓Most common
Best Fit▓▓▓▓Minimize waste
Worst Fit▓▓▓▓▓Rarely used
Next Fit▓▓▓▓▓▓Fair distribution

Addressing External Fragmentation

Problem: External Fragmentation

After many allocations/deallocations:

Free blocks: [50KB, 75KB, 30KB, 100KB, 20KB]
Total free: 275KB

Process needs: 150KB
Can't allocate! (no single block ≥ 150KB)

Solution: Compaction

Compaction

Move processes to eliminate holes:

Before:
┌─────────────┐
│ Process A   │ (100KB)
├─────────────┤
│ Hole 1      │ (50KB)
├─────────────┤
│ Process B   │ (75KB)
├─────────────┤
│ Hole 2      │ (30KB)
├─────────────┤
│ Process C   │ (100KB)
├─────────────┤
│ Hole 3      │ (100KB)
└─────────────┘

After compaction:
┌─────────────┐
│ Process A   │ (100KB)
├─────────────┤
│ Process B   │ (75KB)
├─────────────┤
│ Process C   │ (100KB)
├─────────────┤
│ Free Space  │ (180KB - continuous!)
└─────────────┘

Steps:

  1. Suspend all processes
  2. Move Process A to address 0
  3. Move Process B directly after A
  4. Move Process C directly after B
  5. Free space at end (continuous)
  6. Resume processes
  7. Update base registers for relocated processes

Cost:

Moving 500MB × CPU speed (few ns per byte)
= thousands of nanoseconds
But suspend all processes!
= Lost CPU time = milliseconds to seconds
Expensive operation!

When to Compact:

  • ✓ When allocation fails but total free space sufficient
  • ✓ When fragmentation ratio exceeds threshold (e.g., >40%)
  • ❌ Not continuously (too expensive)
  • ❌ Not during interactive use (visible pause)

Practical Example

Scenario: University Lab Computer

RAM: 2GB
OS: 256MB
Free: 1744MB initially

Day 1 Morning

Process 1 (300MB): Allocate
Process 2 (400MB): Allocate
Process 3 (250MB): Allocate
Free: 794MB
Memory: [OS (256) | P1 (300) | P2 (400) | P3 (250) | Free (794)]

Day 1 Afternoon

Process 1 exits (freed 300MB)
Free blocks: [300MB, 794MB]
Total free: 1094MB
Process 4 needs 500MB:
  Option 1: Use 300MB block? No, too small
  Option 2: Use 794MB block? Yes, use here
  Option 3: Compact? Expensive, but only 1094MB > 500MB requirement

Use option 2 (don't compact yet):
Memory: [OS (256) | Free (300) | P2 (400) | P3 (250) | P4 (500) | Free (294)]

Fragmentation Problem

Many small processes start and stop
After hours: Free blocks [50, 75, 30, 100, 20, 45, 60]MB (280MB total)
Process needs 150MB
Can't fit! (largest block = 100MB)

Trigger compaction:
Memory: [OS (256) | P2 (400) | P3 (250) | P5 (200) | Free (894)]

Success!

Modern Systems

Modern systems use virtual memory with paging instead:

  • ✓ No external fragmentation
  • ✓ No compaction needed
  • ✓ More flexible
  • ✓ Process can be larger than RAM

Dynamic partitioning used in:

  • Legacy systems
  • Some embedded systems
  • Memory allocation within processes (malloc)

Summary

Fixed partitioning is simple but inflexible with high internal fragmentation. Dynamic partitioning is flexible but causes external fragmentation. First-fit is fastest, best-fit minimizes waste, worst-fit rarely used. Compaction solves fragmentation but is expensive (stops all processes). Compaction only practical for batch systems with few allocations. Modern systems use virtual memory with paging to avoid fragmentation entirely. Understanding partition management important for appreciating evolution to modern memory schemes.