Contiguous Memory Allocation in OS

Memory Management

Memory management is a critical function of operating systems that:

• Manages primary memory (RAM)
• Tracks memory usage
• Allocates/deallocates memory space for processes
• Optimizes memory utilization

Key Objectives

1. Efficient memory allocation/deallocation
2. Process isolation (prevent unauthorized access)
3. Memory protection and sharing
4. Minimize fragmentation
5. Support memory hierarchy (cache, RAM, disk)

Types of Memory Management

1. Manual vs Automatic

   • Manual: Programmer-controlled (e.g., C’s malloc/free)
   • Automatic: Garbage-collected (e.g., Java, Python)

2. Static vs Dynamic

   • Static: Fixed-size allocation (compile-time)
   • Dynamic: Variable-size allocation (run-time)

3. Contiguous vs Non-contiguous

   • Contiguous: Process stored in consecutive memory blocks
   • Non-contiguous: Process divided into separate blocks

   (Non-contiguous will be covered later)

Contiguous Memory Allocation

Definition

Entire process loaded into:

• Single continuous block of memory
• Requires all memory addresses to be sequential
• Simpler implementation but suffers from fragmentation

Types of Contiguous Allocation

1. Fixed Partitioning (Static Partitioning)

• How It Works

  • Memory divided into fixed-size partitions at boot time
  • Partition sizes can be:
    • Equal-sized: Simple but inefficient
    • Unequal-sized: Better for varied process sizes

• Example

  System with fixed partitions:

  Partition	Size
  P1	100KB
  P2	200KB
  P3	300KB

  Process Requirements:

  • Process A: 80KB → Allocated to P1 (20KB internal fragmentation)
  • Process B: 250KB → Needs P3 (50KB internal fragmentation)
  • Process C: 150KB → Cannot fit (even though total free space exists)

• Characteristics

  • Pros:
    • Simple implementation
    • Fast allocation (O(1) lookup)
  • Cons:
    • Internal fragmentation
    • Limits process size to partition size
    • Poor memory utilization

2. Dynamic Partitioning (Variable Partitioning)

• How It Works

  • Creates partitions at runtime matching exact process size
  • Maintains free memory list using:
    • Bitmaps
    • Linked lists
  • Requires allocation algorithms for hole selection

• Allocation Algorithms

  Algorithm	Strategy	Pros/Cons
  First-Fit	Allocate first sufficient hole	Fast but creates fragments
  Best-Fit	Allocate smallest sufficient hole	Reduces waste but slow
  Worst-Fit	Allocate largest hole	Leaves large fragments

• Detailed Examples

  ==== First-Fit Example ==== Free Memory Blocks: [200KB, 500KB, 300KB] Process Request: 450KB

  1. Check 200KB → Too small
  2. Check 500KB → Allocate 450KB
  3. Remaining: 50KB fragment

  Result: Fast allocation with 50KB leftover

  ==== Best-Fit Example ==== Free Memory Blocks: [150KB, 400KB, 600KB] Process Request: 350KB

  1. Find smallest sufficient block:
     • 400KB (400-350=50KB fragment)
  2. Allocate to 400KB block

  Result: Leaves smallest possible fragment

  ==== Worst-Fit Example ==== Free Memory Blocks: [250KB, 700KB, 300KB] Process Request: 400KB

  1. Find largest block: 700KB
  2. Allocate 400KB → Leaves 300KB

  Result: Better for future large requests

• Fragmentation Issues

  Type	Cause	Solution
  Internal	Fixed partition > process size	Use dynamic partitioning
  External	Free memory gaps between alloc	Compaction, paging

• Compaction Example

  Before Compaction: [Process1][Free][Process2][Free][Process3]

  After Compaction: [Process1][Process2][Process3][Free Block]

• Characteristics

  • Pros:
    • No internal fragmentation
    • Better memory utilization
  • Cons:
    • External fragmentation
    • Allocation overhead
    • Compaction requires CPU time

Real-World Implementations

1. Fixed Partitioning: Early IBM OS/360
2. Dynamic Partitioning: Classic UNIX systems

Comparison Table

Mathematical Analysis

External Fragmentation Calculation: Total Free Memory = 500KB Largest Contiguous Block = 200KB Fragmentation Ratio = (500-200)/500 = 60%

Historical Context

• First used in batch processing systems
• Evolved to support time-sharing systems
• Basis for modern memory management techniques