Session 4.2 – Contiguous Memory Allocation
Understanding memory partitioning, allocation algorithms, and fragmentation management
Learning Objectives
By the end of this session, you will be able to:
- Understand the concept of contiguous memory allocation
- Explain different partition allocation strategies
- Compare and analyze memory allocation algorithms (First Fit, Best Fit, Worst Fit)
- Identify and understand internal and external fragmentation
- Describe compaction techniques and their trade-offs
Introduction to Contiguous Memory Allocation
Contiguous memory allocation is one of the simplest memory management schemes where each process is allocated a single contiguous section of memory. This approach was commonly used in early computer systems and is still relevant for understanding modern memory management concepts.
Advantages
- Simple to implement
- Fast allocation and deallocation
- Minimal memory overhead
- Good cache performance
Disadvantages
- Memory fragmentation
- Inefficient memory utilization
- Limited process size flexibility
- Difficulty in growing process memory
Memory Partition Strategies
Fixed Partitioning
Memory is divided into fixed-size partitions during system initialization. Each partition can hold exactly one process.
Fixed Partitioning Example
(150K)
(200K)
(100K)
(250K)
Dynamic Partitioning
Partitions are created dynamically based on the exact memory requirements of processes. This approach is more flexible but requires sophisticated allocation algorithms.
Dynamic Partitioning Example
(120K)
(180K)
(200K)
(150K)
Memory Allocation Algorithms
First Fit Algorithm
Strategy: Allocate the first free partition that is large enough to accommodate the process.
First Fit Algorithm: 1. Start from the beginning of memory 2. Find the first free block ≥ process size 3. Allocate the process to this block 4. If remainder > 0, create a new free block 5. Update free block list Time Complexity: O(n) where n is number of free blocks Advantage: Fast allocation Disadvantage: May not utilize memory optimally
Best Fit Algorithm
Strategy: Allocate the smallest free partition that is large enough to accommodate the process.
Best Fit Algorithm: 1. Search entire free block list 2. Find the smallest block ≥ process size 3. Allocate the process to this block 4. If remainder > 0, create a new free block 5. Update free block list Time Complexity: O(n) where n is number of free blocks Advantage: Minimizes wasted space Disadvantage: Slower allocation, creates small fragments
Worst Fit Algorithm
Strategy: Allocate the largest free partition to the process.
Worst Fit Algorithm: 1. Search entire free block list 2. Find the largest free block 3. Allocate the process to this block 4. If remainder > 0, create a new free block 5. Update free block list Time Complexity: O(n) where n is number of free blocks Advantage: Creates larger remaining fragments Disadvantage: Wastes memory, slower allocation
Algorithm Comparison Example
Consider memory with free blocks of sizes: 100K, 500K, 200K, 300K, 600K
Process requests: 212K, 417K, 112K, 426K
| Algorithm | 212K Process | 417K Process | 112K Process | 426K Process | Success Rate |
|---|---|---|---|---|---|
| First Fit | 500K block (288K left) | 600K block (183K left) | 288K block (176K left) | Failed | 75% |
| Best Fit | 300K block (88K left) | 500K block (83K left) | 200K block (88K left) | 600K block (174K left) | 100% |
| Worst Fit | 600K block (388K left) | 500K block (83K left) | 388K block (276K left) | Failed | 75% |
Memory Fragmentation
Internal Fragmentation
Definition: Wasted space within allocated memory partitions.
- Cause: Fixed partition sizes don't match exact process requirements
- Example: Process needs 120K but gets 150K partition
- Waste: 30K internal fragmentation
- Solution: Dynamic partitioning
External Fragmentation
Definition: Free memory exists but is scattered in small, unusable chunks.
- Cause: Process allocation and deallocation creates scattered free spaces
- Example: Total free memory = 400K but largest block = 150K
- Problem: Cannot allocate 200K process
- Solution: Compaction or non-contiguous allocation
Fragmentation Visualization
Before Fragmentation
After Process B Terminates
External Fragmentation: 650K total free, but max contiguous = 350K
50-Percent Rule
Memory Compaction
Compaction is a solution to external fragmentation that involves moving all allocated partitions to one end of memory, creating one large free block.
Compaction Algorithm
Memory Compaction Process: 1. Identify all allocated partitions 2. Calculate total free memory 3. Move all processes to beginning of memory 4. Update process addresses and pointers 5. Create single large free block at end 6. Update memory management tables Requirements: - Dynamic relocation capability - Process suspension during compaction - Address translation updates
Compaction Example
Before Compaction
After Compaction
Single large free block created!
Compaction Benefits
- Eliminates external fragmentation
- Creates large contiguous free space
- Improves memory utilization
- Allows larger processes to be allocated
Compaction Drawbacks
- High CPU overhead
- System downtime during compaction
- Complex address translation updates
- May not be feasible in real-time systems
Practical Examples
Memory Allocation Simulation
Scenario:
Memory size: 1000K, Initial free blocks: [100K, 300K, 200K, 400K]
Process requests arrive in order: P1(150K), P2(80K), P3(250K), P4(120K)
| Step | Process | First Fit | Best Fit | Worst Fit | Remaining Blocks |
|---|---|---|---|---|---|
| 0 | Initial | Free blocks: [100K, 300K, 200K, 400K] | 1000K total free | ||
| 1 | P1 (150K) | Uses 300K block | Uses 200K block | Uses 400K block | FF: [100K, 150K, 200K, 400K] BF: [100K, 300K, 50K, 400K] WF: [100K, 300K, 200K, 250K] |
| 2 | P2 (80K) | Uses 100K block | Uses 100K block | Uses 300K block | FF: [20K, 150K, 200K, 400K] BF: [20K, 300K, 50K, 400K] WF: [100K, 220K, 200K, 250K] |
C Code Example: First Fit Implementation
#include <stdio.h>
#include <stdlib.h>
typedef struct block {
int size;
int allocated;
struct block* next;
} Block;
Block* first_fit(Block* head, int process_size) {
Block* current = head;
while (current != NULL) {
if (!current->allocated && current->size >= process_size) {
// Found suitable block
if (current->size > process_size) {
// Split the block
Block* new_block = malloc(sizeof(Block));
new_block->size = current->size - process_size;
new_block->allocated = 0;
new_block->next = current->next;
current->size = process_size;
current->next = new_block;
}
current->allocated = 1;
return current;
}
current = current->next;
}
return NULL; // No suitable block found
}Session Summary
Key Concepts
- Contiguous Allocation: Each process gets a single memory segment
- Fixed vs Dynamic: Partitioning strategies comparison
- Allocation Algorithms: First Fit, Best Fit, Worst Fit
- Fragmentation: Internal and external memory waste
- Compaction: Solution to external fragmentation
Performance Insights
- First Fit: Fastest but may waste space
- Best Fit: Memory efficient but slower
- Worst Fit: Creates large fragments but wastes memory
- Compaction: Effective but expensive
- 50% Rule: Up to 1/3 memory may be fragmented
Next Session Preview
Session 4.3 will cover Non-Contiguous Memory Allocation including paging concepts, page tables, and Translation Lookaside Buffers (TLB). We'll see how these techniques address the limitations of contiguous allocation.