Contiguous Memory Allocation Fundamentals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

STRUCTURE FixedPartitionTable:
    partitions: ARRAY[1..MAX_PARTITIONS] OF PartitionEntry
    num_partitions: INTEGER
    
STRUCTURE PartitionEntry:
    base: ADDRESS           // Starting address
    size: SIZE              // Partition size in bytes
    allocated: BOOLEAN      // Is partition in use?
    process_id: PID         // Process using this partition (if allocated)
 
// Strategy 1: Best-Fit Assignment (minimize waste)
FUNCTION AssignBestFit(process: Process, table: FixedPartitionTable) -> INTEGER:
    best_partition := -1
    min_waste := INFINITY
    
    FOR i := 1 TO table.num_partitions:
        IF NOT table.partitions[i].allocated THEN
            IF table.partitions[i].size >= process.memory_size THEN
                waste := table.partitions[i].size - process.memory_size
                IF waste < min_waste THEN
                    best_partition := i
                    min_waste := waste
                END IF
            END IF
        END IF
    END FOR
    
    IF best_partition = -1 THEN
        RETURN ERROR_NO_PARTITION  // No suitable partition
    END IF
    
    // Assign process to partition
    table.partitions[best_partition].allocated := TRUE
    table.partitions[best_partition].process_id := process.pid
    
    // Load process into partition
    LoadProcess(process, table.partitions[best_partition].base)
    
    RETURN best_partition
END FUNCTION
 
// Strategy 2: First-Fit Assignment (faster search)
FUNCTION AssignFirstFit(process: Process, table: FixedPartitionTable) -> INTEGER:
    FOR i := 1 TO table.num_partitions:
        IF NOT table.partitions[i].allocated THEN
            IF table.partitions[i].size >= process.memory_size THEN
                table.partitions[i].allocated := TRUE
                table.partitions[i].process_id := process.pid
                LoadProcess(process, table.partitions[i].base)
                RETURN i
            END IF
        END IF
    END FOR
    
    RETURN ERROR_NO_PARTITION
END FUNCTION
 
// Release partition when process terminates
PROCEDURE ReleasePartition(partition_index: INTEGER, table: FixedPartitionTable):
    IF table.partitions[partition_index].allocated THEN
        // Clean up process
        UnloadProcess(table.partitions[partition_index].process_id)
        
        // Mark partition as free
        table.partitions[partition_index].allocated := FALSE
        table.partitions[partition_index].process_id := NULL_PID
        
        // Partition is now available for next process
    END IF
END PROCEDURE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

STRUCTURE HoleNode:
    base: ADDRESS       // Starting address of hole
    size: SIZE          // Size of hole in bytes
    next: POINTER TO HoleNode
    prev: POINTER TO HoleNode
 
STRUCTURE VariablePartitionManager:
    hole_list_head: POINTER TO HoleNode
    process_table: MAP<PID, ProcessMemoryDescriptor>
    
STRUCTURE ProcessMemoryDescriptor:
    base: ADDRESS
    size: SIZE
    
// Allocate memory for a new process
FUNCTION AllocateMemory(manager: VariablePartitionManager, 
                        process: Process) -> ADDRESS:
    // Find suitable hole using allocation strategy
    // (First-Fit, Best-Fit, Worst-Fit, Next-Fit)
    hole := FindSuitableHole(manager.hole_list_head, process.memory_size)
    
    IF hole = NULL THEN
        // Try compaction
        Compact(manager)
        hole := FindSuitableHole(manager.hole_list_head, process.memory_size)
        IF hole = NULL THEN
            RETURN ERROR_OUT_OF_MEMORY
        END IF
    END IF
    
    allocated_base := hole.base
    
    // Allocate from beginning of hole
    IF hole.size = process.memory_size THEN
        // Exact fit: remove entire hole from list
        RemoveFromList(manager.hole_list_head, hole)
        FreeHoleNode(hole)
    ELSE
        // Partial fit: shrink the hole
        hole.base := hole.base + process.memory_size
        hole.size := hole.size - process.memory_size
    END IF
    
    // Record allocation
    manager.process_table[process.pid] := {
        base: allocated_base,
        size: process.memory_size
    }
    
    RETURN allocated_base
END FUNCTION
 
// Release memory when process terminates
PROCEDURE FreeMemory(manager: VariablePartitionManager, pid: PID):
    IF pid NOT IN manager.process_table THEN
        RETURN  // Process already freed or never allocated
    END IF
    
    descriptor := manager.process_table[pid]
    
    // Create new hole for freed memory
    new_hole := AllocateHoleNode()
    new_hole.base := descriptor.base
    new_hole.size := descriptor.size
    
    // Insert hole into list and merge with adjacent holes
    InsertAndMergeHole(manager.hole_list_head, new_hole)
    
    // Remove from process table
    DELETE manager.process_table[pid]
END PROCEDURE
 
// Merge adjacent holes to combat fragmentation
PROCEDURE InsertAndMergeHole(list_head: POINTER TO HoleNode, 
                             new_hole: POINTER TO HoleNode):
    // Insert in address-sorted order
    InsertByAddress(list_head, new_hole)
    
    // Check for merge with previous hole
    IF new_hole.prev != NULL THEN
        IF new_hole.prev.base + new_hole.prev.size = new_hole.base THEN
            // Previous hole is adjacent: merge
            new_hole.prev.size := new_hole.prev.size + new_hole.size
            RemoveFromList(list_head, new_hole)
            FreeHoleNode(new_hole)
            new_hole := new_hole.prev  // Continue checking with merged hole
        END IF
    END IF
    
    // Check for merge with next hole
    IF new_hole.next != NULL THEN
        IF new_hole.base + new_hole.size = new_hole.next.base THEN
            // Next hole is adjacent: merge
            new_hole.size := new_hole.size + new_hole.next.size
            old_next := new_hole.next
            RemoveFromList(list_head, old_next)
            FreeHoleNode(old_next)
        END IF
    END IF
END PROCEDURE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

// First Fit: Find the first hole large enough
FUNCTION FirstFit(hole_list: POINTER TO HoleNode, size: SIZE) -> POINTER TO HoleNode:
    current := hole_list
    WHILE current != NULL:
        IF current.size >= size THEN
            RETURN current  // Found suitable hole
        END IF
        current := current.next
    END WHILE
    RETURN NULL  // No suitable hole found
END FUNCTION
 
// Best Fit: Find the smallest hole that's large enough
FUNCTION BestFit(hole_list: POINTER TO HoleNode, size: SIZE) -> POINTER TO HoleNode:
    best_hole := NULL
    current := hole_list
    
    WHILE current != NULL:
        IF current.size >= size THEN
            IF best_hole = NULL OR current.size < best_hole.size THEN
                best_hole := current
            END IF
        END IF
        current := current.next
    END WHILE
    
    RETURN best_hole
END FUNCTION
 
// Worst Fit: Find the largest hole
FUNCTION WorstFit(hole_list: POINTER TO HoleNode, size: SIZE) -> POINTER TO HoleNode:
    worst_hole := NULL
    current := hole_list
    
    WHILE current != NULL:
        IF current.size >= size THEN
            IF worst_hole = NULL OR current.size > worst_hole.size THEN
                worst_hole := current
            END IF
        END IF
        current := current.next
    END WHILE
    
    RETURN worst_hole
END FUNCTION
 
// Next Fit: Start searching from last allocation position
GLOBAL last_allocated: POINTER TO HoleNode := NULL
 
FUNCTION NextFit(hole_list: POINTER TO HoleNode, size: SIZE) -> POINTER TO HoleNode:
    // Start from last position, or beginning if no prior allocation
    start := last_allocated
    IF start = NULL THEN start := hole_list END IF
    
    // Search from last position to end
    current := start
    WHILE current != NULL:
        IF current.size >= size THEN
            last_allocated := current
            RETURN current
        END IF
        current := current.next
    END WHILE
    
    // Wrap around: search from beginning to last position
    current := hole_list
    WHILE current != start:
        IF current.size >= size THEN
            last_allocated := current
            RETURN current
        END IF
        current := current.next
    END WHILE
    
    RETURN NULL  // Complete circle, no suitable hole
END FUNCTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

STRUCTURE ProcessControlBlock:
    pid: PID
    state: ProcessState
    registers: RegisterSet
    base_register: ADDRESS      // Process's memory base
    limit_register: SIZE        // Process's memory size
    // ... other fields
 
// Context switch includes protection register update
PROCEDURE ContextSwitch(old_process: PCB, new_process: PCB):
    IF old_process != NULL THEN
        // Save current process state including protection registers
        old_process.registers := CPU.Registers
        old_process.base_register := CPU.BaseRegister
        old_process.limit_register := CPU.LimitRegister
    END IF
    
    // Load new process state
    CPU.Registers := new_process.registers
    
    // CRITICAL: Update protection registers
    // This defines which memory new_process can access
    CPU.BaseRegister := new_process.base_register
    CPU.LimitRegister := new_process.limit_register
    
    // Now when new_process runs, hardware enforces its boundaries
END PROCEDURE
 
// Hardware memory access check (performed on EVERY memory access)
HARDWARE_FUNCTION MemoryAccessCheck(logical_address: ADDRESS) -> ADDRESS:
    mode := CPU.Mode
    
    IF mode = SUPERVISOR THEN
        // OS mode: no translation, no restrictions
        RETURN logical_address
    END IF
    
    // User mode: check against base/limit
    IF logical_address >= CPU.LimitRegister THEN
        RaiseException(SEGMENTATION_FAULT)
        HALT  // Never reaches here
    END IF
    
    // Translate: add base to get physical address
    physical_address := CPU.BaseRegister + logical_address
    
    RETURN physical_address
END HARDWARE_FUNCTION