Contiguous Allocation Management

Contiguous Allocation

Contiguous allocation means giving a process one contiguous block of memory. The scheme is simple and intuitive, but it is prone to memory fragmentation.

Single Contiguous Allocation

Basic Idea

Single contiguous allocation is the simplest memory allocation scheme: the whole memory space is handed to a single process.

Memory Layout

Characteristic Analysis

Advantages:

• Simple to implement, with little management overhead
• Simple address translation: a base register is all that is needed
• Suitable for single-program systems

Disadvantages:

• Low memory utilization
• No support for multiprogramming
• The program size is limited by the size of memory

Implementation Example

// Memory management for single contiguous allocation
typedef struct {
    int base;          // program base address
    int limit;         // program length
    int total_memory;  // total size of memory
} SingleContiguousMemory;

void init_memory(SingleContiguousMemory *mem, int total) {
    mem->total_memory = total;
    mem->base = 0;
    mem->limit = 0;
}

int load_program(SingleContiguousMemory *mem, int program_size) {
    if (program_size > mem->total_memory) {
        return -1;  // program too large to load
    }

    mem->base = 0;
    mem->limit = program_size;
    return 0;
}

int address_translation(int logical_addr, SingleContiguousMemory *mem) {
    if (logical_addr >= mem->limit) {
        return -1;  // address out of bounds
    }
    return mem->base + logical_addr;
}

Fixed Partition Allocation

Basic Idea

The memory space is divided into a number of fixed-size partitions, and each partition is assigned to one process.

Partition Table Structure

typedef struct {
    int start_addr;    // start address of the partition
    int size;          // size of the partition
    int status;        // partition status: 0-free, 1-allocated
    int process_id;    // id of the process occupying it
} Partition;

#define MAX_PARTITIONS 10
Partition partition_table[MAX_PARTITIONS];
int partition_count;

Partition Allocation Algorithms

1. First Fit

int first_fit_allocate(int process_size, int process_id) {
    for (int i = 0; i < partition_count; i++) {
        if (partition_table[i].status == 0 &&
            partition_table[i].size >= process_size) {
            partition_table[i].status = 1;
            partition_table[i].process_id = process_id;
            return partition_table[i].start_addr;
        }
    }
    return -1;  // no suitable partition
}

2. Best Fit

int best_fit_allocate(int process_size, int process_id) {
    int best_index = -1;
    int min_fragment = INT_MAX;

    for (int i = 0; i < partition_count; i++) {
        if (partition_table[i].status == 0 &&
            partition_table[i].size >= process_size) {
            int fragment = partition_table[i].size - process_size;
            if (fragment < min_fragment) {
                min_fragment = fragment;
                best_index = i;
            }
        }
    }

    if (best_index != -1) {
        partition_table[best_index].status = 1;
        partition_table[best_index].process_id = process_id;
        return partition_table[best_index].start_addr;
    }
    return -1;
}

3. Worst Fit

int worst_fit_allocate(int process_size, int process_id) {
    int worst_index = -1;
    int max_fragment = -1;

    for (int i = 0; i < partition_count; i++) {
        if (partition_table[i].status == 0 &&
            partition_table[i].size >= process_size) {
            int fragment = partition_table[i].size - process_size;
            if (fragment > max_fragment) {
                max_fragment = fragment;
                worst_index = i;
            }
        }
    }

    if (worst_index != -1) {
        partition_table[worst_index].status = 1;
        partition_table[worst_index].process_id = process_id;
        return partition_table[worst_index].start_addr;
    }
    return -1;
}

Algorithm Comparison

Variable Partition Allocation

Basic Idea

The memory space is divided dynamically according to the actual needs of the processes, which avoids the internal fragmentation caused by fixed partitions.

Free Partition Table

typedef struct {
    int start_addr;    // start address
    int size;          // size of the partition
    int next;          // index of the next free partition
} FreePartition;

#define MAX_FREE_PARTITIONS 100
FreePartition free_table[MAX_FREE_PARTITIONS];
int free_count;
int free_head;  // head of the free partition list

Allocation Algorithm Implementations

1. First Fit

int first_fit_allocate_variable(int process_size, int process_id) {
    int current = free_head;
    int prev = -1;

    while (current != -1) {
        if (free_table[current].size >= process_size) {
            // Found a suitable partition
            int allocated_addr = free_table[current].start_addr;

            if (free_table[current].size == process_size) {
                // Exact match, remove this free partition
                if (prev == -1) {
                    free_head = free_table[current].next;
                } else {
                    free_table[prev].next = free_table[current].next;
                }
            } else {
                // Split the partition
                free_table[current].start_addr += process_size;
                free_table[current].size -= process_size;
            }

            return allocated_addr;
        }

        prev = current;
        current = free_table[current].next;
    }

    return -1;  // no suitable partition
}

2. Best Fit

int best_fit_allocate_variable(int process_size, int process_id) {
    int current = free_head;
    int best_index = -1;
    int min_fragment = INT_MAX;

    while (current != -1) {
        if (free_table[current].size >= process_size) {
            int fragment = free_table[current].size - process_size;
            if (fragment < min_fragment) {
                min_fragment = fragment;
                best_index = current;
            }
        }
        current = free_table[current].next;
    }

    if (best_index != -1) {
        int allocated_addr = free_table[best_index].start_addr;

        if (free_table[best_index].size == process_size) {
            // Remove this free partition
            remove_free_partition(best_index);
        } else {
            // Split the partition
            free_table[best_index].start_addr += process_size;
            free_table[best_index].size -= process_size;
        }

        return allocated_addr;
    }

    return -1;
}

3. Next Fit

int next_fit_allocate(int process_size, int process_id) {
    static int last_allocated = 0;  // position of the last allocation
    int start = last_allocated;
    int current = start;

    do {
        if (free_table[current].size >= process_size) {
            // Found a suitable partition
            int allocated_addr = free_table[current].start_addr;
            last_allocated = current;

            if (free_table[current].size == process_size) {
                remove_free_partition(current);
            } else {
                free_table[current].start_addr += process_size;
                free_table[current].size -= process_size;
            }

            return allocated_addr;
        }

        current = free_table[current].next;
        if (current == -1) current = free_head;
    } while (current != start);

    return -1;
}

Memory Reclamation

void free_memory(int start_addr, int size) {
    // Find the insertion position
    int current = free_head;
    int prev = -1;

    while (current != -1 && free_table[current].start_addr < start_addr) {
        prev = current;
        current = free_table[current].next;
    }

    // Create a new free partition
    int new_index = get_free_slot();
    free_table[new_index].start_addr = start_addr;
    free_table[new_index].size = size;

    // Insert it into the list
    if (prev == -1) {
        free_table[new_index].next = free_head;
        free_head = new_index;
    } else {
        free_table[new_index].next = free_table[prev].next;
        free_table[prev].next = new_index;
    }

    // Merge the adjacent free partitions
    merge_adjacent_partitions();
}

void merge_adjacent_partitions() {
    int current = free_head;

    while (current != -1 && free_table[current].next != -1) {
        int next = free_table[current].next;

        if (free_table[current].start_addr + free_table[current].size ==
            free_table[next].start_addr) {
            // Merge the adjacent partitions
            free_table[current].size += free_table[next].size;
            free_table[current].next = free_table[next].next;
            free_table[next].size = 0;  // marked as invalid
        } else {
            current = free_table[current].next;
        }
    }
}

The Fragmentation Problem

Types of Fragmentation

1. Internal Fragmentation

• The part of an allocated memory block that the process never uses
• Common in fixed partition allocation
• Cannot be used by any other process

2. External Fragmentation

• Small free areas in memory that cannot be assigned to any process
• Common in variable partition allocation
• Can be dealt with by compaction

Compaction

void memory_compaction() {
    // Move all processes towards the low end of memory
    int new_addr = 0;

    for (int i = 0; i < process_count; i++) {
        if (process_table[i].status == 1) {
            int old_addr = process_table[i].start_addr;
            int size = process_table[i].size;

            // Move the process
            memmove((void*)new_addr, (void*)old_addr, size);

            // Update the process address
            process_table[i].start_addr = new_addr;
            new_addr += size;
        }
    }

    // Rebuild the free partition table
    rebuild_free_table(new_addr);
}

The Buddy System

Basic Idea

Memory is divided into blocks whose sizes are powers of two, 2^k. On allocation the closest 2^k block is found, which keeps fragmentation under control.

Implementation Example

#define MAX_ORDER 10
#define PAGE_SIZE 4096

typedef struct {
    int order;         // size level of the block
    int start_addr;    // start address
    int status;        // status: 0-free, 1-allocated
} BuddyBlock;

BuddyBlock buddy_table[1 << MAX_ORDER];
int free_lists[MAX_ORDER + 1];  // free list of each size level

void init_buddy_system() {
    // Initialize the buddy system
    int total_pages = (1 << MAX_ORDER);

    for (int i = 0; i < total_pages; i++) {
        buddy_table[i].order = 0;
        buddy_table[i].start_addr = i * PAGE_SIZE;
        buddy_table[i].status = 0;
    }

    // Initialize the free lists
    for (int i = 0; i <= MAX_ORDER; i++) {
        free_lists[i] = -1;
    }

    // Put the largest block on the free list
    free_lists[MAX_ORDER] = 0;
}

int buddy_allocate(int size) {
    int order = get_order(size);

    // Look for a free block of a suitable size
    for (int i = order; i <= MAX_ORDER; i++) {
        if (free_lists[i] != -1) {
            return split_and_allocate(i, order);
        }
    }

    return -1;  // not enough free space
}

int get_order(int size) {
    int order = 0;
    int page_count = (size + PAGE_SIZE - 1) / PAGE_SIZE;

    while ((1 << order) < page_count) {
        order++;
    }

    return order;
}

int split_and_allocate(int large_order, int target_order) {
    if (large_order == target_order) {
        // Allocate directly
        int block_index = free_lists[large_order];
        free_lists[large_order] = buddy_table[block_index].next;
        buddy_table[block_index].status = 1;
        return buddy_table[block_index].start_addr;
    }

    // Split the block
    int block_index = free_lists[large_order];
    free_lists[large_order] = buddy_table[block_index].next;

    // Create the two buddy blocks
    int buddy_index = block_index + (1 << (large_order - 1));

    buddy_table[block_index].order = large_order - 1;
    buddy_table[buddy_index].order = large_order - 1;
    buddy_table[block_index].status = 0;
    buddy_table[buddy_index].status = 0;

    // Put the buddy block on the free list
    buddy_table[buddy_index].next = free_lists[large_order - 1];
    free_lists[large_order - 1] = buddy_index;

    // Allocate recursively
    return split_and_allocate(large_order - 1, target_order);
}

Practical Applications

The Buddy System in Linux

The Linux kernel uses the buddy system to manage physical page frames:

// The buddy system in the Linux kernel
struct zone {
    struct free_area free_area[MAX_ORDER];
    // ...
};

struct free_area {
    struct list_head free_list[MIGRATE_TYPES];
    unsigned long *map;
    unsigned long count;
};

Memory Management in Windows

Windows uses paging, but it still keeps the idea of contiguous allocation:

// Windows memory allocation
LPVOID VirtualAlloc(
    LPVOID lpAddress,
    SIZE_T dwSize,
    DWORD flAllocationType,
    DWORD flProtect
);

Summary

Contiguous allocation is the foundation of memory management. Each scheme, from the simplicity of single contiguous allocation to the complexity of the buddy system, suits its own scenario, and choosing the right allocation algorithm is essential for memory utilization and overall performance. Modern operating systems usually combine several allocation schemes so that different applications get what they need.

---

Glossary