Exploring Operating Systems
Day 43: Memory Fragmentation
Table of Contents
- Introduction to Memory Fragmentation
- Types of Memory Fragmentation
- Memory Defragmentation Algorithms
- Memory Compaction Techniques
- Memory Pool Management
- Advanced Memory Allocation Strategies
- Fragmentation Prevention
- Monitoring and Analysis Tools
- Performance Optimization
- Conclusion
1. Introduction to Memory Fragmentation
Memory fragmentation occurs when memory is divided into small, non-contiguous blocks, making it difficult to allocate larger blocks of memory even if the total free memory is sufficient. Fragmentation can significantly degrade system performance and lead to inefficient memory utilization.
Key Concepts in Memory Fragmentation
- Internal Fragmentation: Wasted space within allocated memory blocks due to rounding up to the nearest block size.
- External Fragmentation: Wasted space between allocated memory blocks, making it difficult to allocate large contiguous blocks.
- Memory Compaction: The process of reorganizing memory to reduce fragmentation by moving allocated blocks closer together.
- Allocation Strategies: Techniques to minimize fragmentation during memory allocation.
2. Types of Memory Fragmentation
Memory fragmentation can be categorized into internal and external fragmentation. Below is an implementation of a memory manager that analyzes fragmentation:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct MemoryBlock {
size_t size;
bool is_allocated;
void *start_address;
struct MemoryBlock *next;
struct MemoryBlock *prev;
} MemoryBlock;
typedef struct {
MemoryBlock *head;
size_t total_size;
size_t used_size;
size_t internal_fragmentation;
size_t external_fragmentation;
} MemoryManager;
void analyze_fragmentation(MemoryManager *manager) {
MemoryBlock *current = manager->head;
size_t total_internal = 0;
size_t total_external = 0;
size_t largest_free_block = 0;
while (current != NULL) {
if (current->is_allocated) {
// Calculate internal fragmentation
size_t block_internal = current->size -
get_actual_data_size(current);
total_internal += block_internal;
} else {
// Track external fragmentation
total_external += current->size;
if (current->size > largest_free_block) {
largest_free_block = current->size;
}
}
current = current->next;
}
manager->internal_fragmentation = total_internal;
manager->external_fragmentation = total_external - largest_free_block;
}
3. Memory Defragmentation Algorithms
Defragmentation involves reorganizing memory to reduce fragmentation. Below is an implementation of a defragmentation algorithm:
typedef struct {
void *old_address;
void *new_address;
size_t size;
} RelocationEntry;
typedef struct {
RelocationEntry *entries;
size_t count;
size_t capacity;
} RelocationTable;
bool defragment_memory(MemoryManager *manager) {
RelocationTable relocation_table = {
.entries = malloc(1000 * sizeof(RelocationEntry)),
.count = 0,
.capacity = 1000
};
// Phase 1: Analyze and plan relocations
MemoryBlock *current = manager->head;
void *next_free_address = manager->head->start_address;
while (current != NULL) {
if (current->is_allocated) {
if (current->start_address != next_free_address) {
// Need to relocate this block
RelocationEntry entry = {
.old_address = current->start_address,
.new_address = next_free_address,
.size = current->size
};
relocation_table.entries[relocation_table.count++] = entry;
}
next_free_address += current->size;
}
current = current->next;
}
// Phase 2: Perform relocations
for (size_t i = 0; i < relocation_table.count; i++) {
RelocationEntry *entry = &relocation_table.entries[i];
memmove(entry->new_address, entry->old_address, entry->size);
update_pointers(manager, entry);
}
// Phase 3: Update memory block list
coalesce_free_blocks(manager);
free(relocation_table.entries);
return true;
}
4. Memory Compaction Techniques
Memory compaction involves moving allocated memory blocks to reduce fragmentation. Below is an implementation of memory compaction:
typedef struct {
void **pointers;
size_t count;
} PointerRegistry;
bool compact_memory(MemoryManager *manager, PointerRegistry *registry) {
// Phase 1: Mark all blocks
mark_live_blocks(manager);
// Phase 2: Calculate new addresses
void *compact_address = manager->head->start_address;
MemoryBlock *current = manager->head;
while (current != NULL) {
if (current->is_allocated) {
current->new_address = compact_address;
compact_address += current->size;
}
current = current->next;
}
// Phase 3: Update pointers
for (size_t i = 0; i < registry->count; i++) {
void *old_ptr = *registry->pointers[i];
MemoryBlock *block = find_block_for_address(manager, old_ptr);
if (block != NULL) {
size_t offset = (char*)old_ptr - (char*)block->start_address;
*registry->pointers[i] = (char*)block->new_address + offset;
}
}
// Phase 4: Move memory
current = manager->head;
while (current != NULL) {
if (current->is_allocated &&
current->start_address != current->new_address) {
memmove(current->new_address,
current->start_address,
current->size);
current->start_address = current->new_address;
}
current = current->next;
}
return true;
}
5. Memory Pool Management
Memory pools allocate fixed-size blocks of memory, reducing fragmentation. Below is an implementation of a memory pool:
typedef struct {
void *pool_start;
size_t block_size;
size_t num_blocks;
uint8_t *block_status; // 0 = free, 1 = allocated
void **free_blocks;
size_t free_count;
} MemoryPool;
MemoryPool* create_memory_pool(size_t block_size, size_t num_blocks) {
MemoryPool *pool = malloc(sizeof(MemoryPool));
pool->block_size = block_size;
pool->num_blocks = num_blocks;
pool->pool_start = aligned_alloc(sizeof(void*),
block_size * num_blocks);
pool->block_status = calloc(num_blocks, sizeof(uint8_t));
pool->free_blocks = malloc(num_blocks * sizeof(void*));
pool->free_count = num_blocks;
// Initialize free block list
for (size_t i = 0; i < num_blocks; i++) {
pool->free_blocks[i] = (char*)pool->pool_start +
(i * block_size);
}
return pool;
}
void* pool_allocate(MemoryPool *pool) {
if (pool->free_count == 0) return NULL;
void *block = pool->free_blocks[--pool->free_count];
size_t block_index = ((char*)block - (char*)pool->pool_start) /
pool->block_size;
pool->block_status[block_index] = 1;
return block;
}
6. Advanced Memory Allocation Strategies
The buddy system is an advanced memory allocation strategy that reduces fragmentation by splitting and merging memory blocks.
Buddy System Implementation
Below is an implementation of the buddy system:
typedef struct {
void *memory;
size_t total_size;
size_t min_block_size;
size_t max_order;
struct list_head *free_lists;
} BuddyAllocator;
BuddyAllocator* create_buddy_allocator(size_t total_size,
size_t min_block_size) {
BuddyAllocator *allocator = malloc(sizeof(BuddyAllocator));
allocator->total_size = total_size;
allocator->min_block_size = min_block_size;
allocator->max_order = log2(total_size / min_block_size);
allocator->memory = aligned_alloc(min_block_size, total_size);
// Initialize free lists
allocator->free_lists = malloc(sizeof(struct list_head) *
(allocator->max_order + 1));
for (size_t i = 0; i <= allocator->max_order; i++) {
INIT_LIST_HEAD(&allocator->free_lists[i]);
}
// Add initial block to highest order free list
add_to_free_list(allocator, allocator->memory, allocator->max_order);
return allocator;
}
void* buddy_allocate(BuddyAllocator *allocator, size_t size) {
size_t order = calculate_order(size, allocator->min_block_size);
// Find suitable block
for (size_t i = order; i <= allocator->max_order; i++) {
if (!list_empty(&allocator->free_lists[i])) {
void *block = remove_from_free_list(allocator, i);
// Split block if necessary
while (i > order) {
i--;
void *buddy = (char*)block + (1 << i);
add_to_free_list(allocator, buddy, i);
}
return block;
}
}
return NULL;
}
7. Fragmentation Prevention
Fragmentation prevention involves strategies to minimize fragmentation during memory allocation.
8. Monitoring and Analysis Tools
Monitoring tools help analyze memory usage and fragmentation. Below is an implementation of memory monitoring:
typedef struct {
size_t total_allocations;
size_t total_deallocations;
size_t peak_memory_usage;
size_t current_memory_usage;
double fragmentation_ratio;
size_t largest_contiguous_free;
} MemoryStats;
void collect_memory_stats(MemoryManager *manager, MemoryStats *stats) {
MemoryBlock *current = manager->head;
size_t total_free = 0;
size_t largest_free = 0;
size_t current_free = 0;
while (current != NULL) {
if (current->is_allocated) {
current_free = 0;
} else {
current_free += current->size;
total_free += current->size;
if (current_free > largest_free) {
largest_free = current_free;
}
}
current = current->next;
}
stats->largest_contiguous_free = largest_free;
stats->fragmentation_ratio = 1.0 -
((double)largest_free / total_free);
}
9. Performance Optimization
Key performance considerations for memory fragmentation management include:
- Allocation Time Complexity: O(1) for pool allocation, O(log n) for buddy system.
- Memory Overhead: Additional structures for tracking fragmentation.
- Compaction Cost: O(n) for full compaction.
- Cache Performance: Impact of memory layout on cache efficiency.
10. Conclusion
Memory fragmentation management is crucial for system performance and reliability. Understanding and implementing proper fragmentation prevention and management techniques can significantly improve system efficiency and resource utilization.