Operating SystemsFixed Partitioning

Fixed Partitioning: Static Memory Division

LevelIntermediate

Duration60 mins

TopicFixed Partitioning

1 / 5

Equal-Size Partitions

The Challenge of Sharing Main Memory

In the earliest days of computing, the operating system faced a fundamental challenge that would shape decades of research: how do you allow multiple programs to reside in main memory simultaneously?

Before multi-programming, computers operated in a simple batch mode—load one program, execute it to completion, load the next. This approach left the CPU idle during I/O operations, wasting precious computational resources. The solution was obvious: keep multiple programs in memory so the CPU could switch between them. But this solution immediately raised a critical question that would define memory management forever:

How do you divide a single, finite physical memory among multiple processes that have no knowledge of each other's existence?

Fixed partitioning with equal-size partitions represents humanity's first systematic answer to this question. While primitive by modern standards, understanding this scheme is essential—it establishes the vocabulary, trade-offs, and design patterns that permeate all subsequent memory management innovations.

Learning Objectives

By the end of this page, you will:

• Understand the fundamental concept of equal-size fixed partitioning • Trace the historical context and design rationale behind this approach • Analyze the memory allocation and process loading mechanics • Implement partition management data structures • Evaluate the scheme's behavior under various workloads • Recognize the inherent trade-offs that motivate more advanced techniques

The Core Concept: Uniform Division of Memory

Equal-size fixed partitioning is a memory management scheme where the operating system divides the total available physical memory into a fixed number of partitions, all of identical size. This division occurs at system boot time (or during OS initialization) and remains constant throughout the system's operation—no partition can be created, destroyed, resized, or merged during runtime.

The Defining Characteristics

Let's formalize the properties that define this scheme:

1. Static Division The memory is divided once, typically at system startup. If the system has 64 MB of user memory and we create 8 partitions, each partition is exactly 8 MB. This division persists until the system is reconfigured and rebooted.

2. Uniform Size Every partition has identical dimensions. If partition P₁ is 8 MB, then P₂, P₃, ..., Pₙ are all exactly 8 MB. There are no exceptions, no special cases.

3. Exclusive Allocation Each partition can hold at most one process at any given time. A partition is either:

Free: Available for allocation to a new process
Occupied: Contains exactly one process (no sharing)

4. Fixed Boundaries Partition boundaries are immutable. A process allocated to a partition cannot "spill over" into adjacent partitions, regardless of its actual memory requirements.

The Simplicity Principle

The appeal of equal-size partitions lies in its radical simplicity. The OS doesn't need complex algorithms to decide partition sizes, doesn't need to track variable-length memory regions, and doesn't need to coalesce adjacent free areas. Every allocation decision reduces to: "Is there a free partition?" This simplicity translated directly to faster implementation, fewer bugs, and predictable behavior in an era when computing resources were precious and software development was expensive.

Mathematical Formalization

Given:

M = Total physical memory available for user processes
n = Number of equal-size partitions
S = Size of each partition

The fundamental relationship is:

S = M ÷ n

Or equivalently:

M = n × S

This relationship constrains system design. A system administrator configuring the partition scheme must choose either n or S, and the other is determined. For example:

64 MB memory with 8 partitions → 8 MB per partition
64 MB memory with 4 MB partitions → 16 partitions

The degree of multi-programming (maximum concurrent processes) equals n—you can never have more processes in memory than you have partitions, regardless of how small those processes might be.

Example: 64 MB Memory with Various Partition Configurations
Number of Partitions (n)	Partition Size (S)	Max Processes	Best For
4	16 MB	4	Few large processes
8	8 MB	8	Balanced workload
16	4 MB	16	Many small processes
32	2 MB	32	High concurrency, small tasks
64	1 MB	64	Maximum concurrency

Historical Context: Why Equal-Size Partitions?

To appreciate fixed partitioning, we must understand the technological context of the late 1950s and 1960s when these schemes emerged. The constraints of that era profoundly shaped the design decisions that may seem arbitrary or suboptimal from a modern perspective.

The Era's Constraints

1. Limited Hardware Support Early computers lacked the Memory Management Units (MMUs) that modern systems take for granted. There was no hardware-assisted address translation, protection mechanisms, or page table support. Any memory management had to be implemented almost entirely in software, with minimal hardware assistance.

2. Scarce Memory Main memory was extraordinarily expensive. A system might have only 32 KB to 256 KB of total memory. Every byte mattered, and the overhead of memory management data structures was a genuine concern.

3. Simple Protection Needs The primary protection mechanism was typically a pair of base and limit registers:

Base register: Starting physical address of the partition
Limit register: Size of the partition

With equal-size partitions, the limit register could be hardwired to a single value, simplifying the hardware.

4. Predictable Workloads Batch processing systems of that era ran standardized jobs with relatively predictable memory requirements. Variability existed, but not at the scale seen in modern interactive systems.

5. Minimal Runtime Overhead With CPU cycles precious, any memory management scheme needed minimal runtime overhead. Equal-size partitions require almost no computation—partition lookup is O(1), and there's no fragmentation management.

The IBM System/360 Connection

IBM's System/360 (1964), one of the most influential computer architectures in history, used variations of fixed partitioning in its early operating systems (DOS/360, OS/MFT). Understanding equal-size partitions provides insight into the design philosophy that shaped commercial computing for decades.

The Design Philosophy

Equal-size fixed partitioning embodies a particular philosophy that trades flexibility for simplicity:

One-Time Configuration Cost The system administrator pays the "cost" of analyzing workload characteristics once, at configuration time. They study the typical processes that will run, estimate memory requirements, and choose an appropriate partition size. This upfront investment eliminates runtime decision-making.

Uniform Treatment By treating all partitions identically, the system avoids a class of bugs and edge cases. There's no "special" partition that behaves differently, no complex priority logic, no size-dependent algorithms.

Predictable Performance Context switching between processes requires loading new base/limit register values. With equal-size partitions, this operation has constant, predictable timing. System administrators could reason about worst-case performance.

Failure Isolation A misbehaving process can only corrupt its own partition. With hardware-enforced boundaries (base/limit registers), processes cannot access memory outside their assigned region, providing primitive but effective isolation.

Memory Layout and System Architecture

Understanding the physical memory layout is crucial for grasping how equal-size partitioning integrates with the broader system architecture.

Physical Memory Organization

Physical memory in a fixed-partition system is typically organized as follows:

+---------------------------+ 0x00000000 (Address 0)
|   Interrupt Vectors       |  
|   (Reserved by Hardware)  |  
+---------------------------+
|                           |
|   Operating System        |  
|   (Kernel Code + Data)    |  
|                           |  
+---------------------------+ OS_END
|                           |
|   Partition 0             | Size = S
|   [Process A or FREE]     |
|                           |
+---------------------------+ OS_END + S
|                           |
|   Partition 1             | Size = S
|   [Process B or FREE]     |
|                           |
+---------------------------+ OS_END + 2S
|                           |
|   Partition 2             | Size = S
|   [Process C or FREE]     |
|                           |
+---------------------------+ OS_END + 3S
|          ...              |
+---------------------------+ OS_END + (n-1)S
|                           |
|   Partition n-1           | Size = S
|   [Process N or FREE]     |
|                           |
+---------------------------+ MEMORY_TOP

Address Calculation

The starting address of partition i is:

Partition_Start(i) = OS_END + (i × S)

Where OS_END is the first address after the operating system's reserved memory region. This formula enables O(1) address calculation for any partition—no searching, no pointer chasing.

Base and Limit Register Integration

The hardware protection mechanism works as follows:

When a process is dispatched (given the CPU):

The OS loads the base register with the starting address of the process's partition
The OS loads the limit register with the partition size S
Every memory access by the process is checked by hardware:
- Compute: physical_address = base + logical_address
- Check: logical_address < limit
- If check fails: Generate protection fault (trap to OS)

For equal-size partitions:

The limit register always holds the same value S
Only the base register changes during context switches
Hardware can potentially optimize for this uniformity

Partition Addressing Modes

Processes generate logical addresses (also called virtual addresses in this context) relative to address 0. The hardware automatically translates these to physical addresses:

Logical Address: 0x00001000 (4 KB into process memory)
Base Register:   0x00100000 (Partition 3 starts here)
Physical Address: 0x00101000 (Base + Logical)

This translation is transparent to the process—it believes it has memory starting at address 0, regardless of which partition it actually occupies.

Example: 4 Equal Partitions in 32 MB User Memory
Partition #	Base Address	Limit	Physical Range	Current State
0	0x00800000 (8 MB)	8 MB	8 MB - 16 MB	Process A (PID 101)
1	0x01000000 (16 MB)	8 MB	16 MB - 24 MB	FREE
2	0x01800000 (24 MB)	8 MB	24 MB - 32 MB	Process B (PID 203)
3	0x02000000 (32 MB)	8 MB	32 MB - 40 MB	Process C (PID 157)

Implementation: Data Structures and Algorithms

Implementing equal-size fixed partitioning requires minimal but carefully designed data structures. The simplicity is a primary advantage of this scheme.

Core Data Structures

The OS maintains a Partition Table that tracks the state of each partition:

partition_table.c
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
// System configuration constants (set at boot time)
#define NUM_PARTITIONS    8
#define PARTITION_SIZE    (8 * 1024 * 1024)  // 8 MB each
#define USER_MEM_START    0x00800000         // After OS kernel
 
// Partition states
typedef enum {
    PARTITION_FREE,      // Available for allocation
    PARTITION_OCCUPIED   // Contains an active process
} PartitionState;
 
// Partition descriptor
typedef struct {
    PartitionState state;           // Current state
    int            process_id;      // PID of occupying process (-1 if free)
    uint32_t       base_address;    // Starting physical address
    uint32_t       size;            // Partition size (always PARTITION_SIZE)
    uint64_t       allocation_time; // Timestamp for debugging/statistics
} PartitionDescriptor;
 
// The global partition table
PartitionDescriptor partition_table[NUM_PARTITIONS];
 
// Initialize partition table at boot time
void init_partition_table(void) {
    for (int i = 0; i < NUM_PARTITIONS; i++) {
        partition_table[i].state = PARTITION_FREE;
        partition_table[i].process_id = -1;
        partition_table[i].base_address = USER_MEM_START + (i * PARTITION_SIZE);
        partition_table[i].size = PARTITION_SIZE;
        partition_table[i].allocation_time = 0;
    }
}

Allocation Algorithm

The allocation algorithm for equal-size partitions is remarkably simple. When a process requests memory, the OS simply finds any free partition:

allocate_partition.c
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
// Allocate a partition to a process
// Returns partition index on success, -1 on failure
int allocate_partition(int process_id, uint32_t required_size) {
    // Critical check: Process must fit in a partition
    if (required_size > PARTITION_SIZE) {
        // Process too large for any partition
        log_error("Process %d requires %u bytes, max partition size is %u",
                  process_id, required_size, PARTITION_SIZE);
        return -1;  // Allocation failure
    }
    
    // Search for any free partition (linear scan)
    for (int i = 0; i < NUM_PARTITIONS; i++) {
        if (partition_table[i].state == PARTITION_FREE) {
            // Found a free partition - allocate it
            partition_table[i].state = PARTITION_OCCUPIED;
            partition_table[i].process_id = process_id;
            partition_table[i].allocation_time = get_current_time();
            
            // Update process control block with memory info
            set_process_memory(process_id, 
                               partition_table[i].base_address,
                               PARTITION_SIZE);
            
            log_info("Allocated partition %d to process %d (base: 0x%08X)",
                     i, process_id, partition_table[i].base_address);
            
            return i;  // Success - return partition index
        }
    }
    
    // No free partition available
    log_warning("No free partition for process %d - system at capacity", 
                process_id);
    return -1;  // Allocation failure - must wait or swap
}

Time Complexity Analysis

Allocation: O(n) in worst case, where n is the number of partitions. We scan until finding a free partition.

Deallocation: O(1) if we know the partition index; O(n) if we search by process ID.

Memory Access: O(1) address translation via hardware base register.

In practice, with a small number of partitions (typically 4-16), this linear scan is negligible.

Deallocation Algorithm

When a process terminates, its partition must be released:

deallocate_partition.c
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
// Deallocate a partition when a process terminates
void deallocate_partition(int process_id) {
    for (int i = 0; i < NUM_PARTITIONS; i++) {
        if (partition_table[i].process_id == process_id) {
            // Found the process's partition
            
            // Security: Zero out memory to prevent data leakage
            // (Critical in multi-user systems)
            memset((void*)partition_table[i].base_address, 0, PARTITION_SIZE);
            
            // Mark partition as free
            partition_table[i].state = PARTITION_FREE;
            partition_table[i].process_id = -1;
            partition_table[i].allocation_time = 0;
            
            log_info("Deallocated partition %d (formerly process %d)", 
                     i, process_id);
            
            // Wake up any processes waiting for memory
            signal_memory_available();
            
            return;
        }
    }
    
    // Process not found - programming error or double-free
    log_error("Attempted to deallocate partition for unknown process %d", 
              process_id);
}

Process Loading and Execution Lifecycle

Understanding how a process is loaded into a partition and begins execution reveals the practical mechanics of this memory management scheme.

The Loading Sequence

When a user submits a job (program) for execution, the following sequence occurs:

Process Loading Steps

•Job Submission: User submits executable file with memory requirements
•Size Check: OS verifies process size ≤ PARTITION_SIZE; rejects if too large
•Partition Search: OS scans partition table for PARTITION_FREE entry
•Wait or Proceed: If no free partition, job enters wait queue; otherwise continue
•Memory Allocation: Mark partition as PARTITION_OCCUPIED, record PID
•Image Loading: Copy executable code and data from disk to partition memory
•Relocation: Adjust addresses in loaded code (if not position-independent)
•PCB Setup: Create Process Control Block with base address, register state
•Ready Queue: Add process to scheduler's ready queue
•Dispatch: When scheduled, load base/limit registers and transfer control

Relocation: A Critical Detail

Programs are typically compiled with addresses starting at 0. When loaded into a partition starting at a different address, there are two approaches:

1. Static Relocation (Load-Time) The loader adjusts all memory references in the program before execution begins. This is a one-time cost at load time.

2. Dynamic Relocation (Run-Time) The base register performs address adjustment on every memory access. All logical addresses are added to the base register to produce physical addresses.

Equal-size partitioning typically uses dynamic relocation (base-register translation), which offers a crucial advantage: a process can be swapped out to disk and later reloaded into a different partition without any address adjustment. The base register simply gets loaded with the new partition's starting address.

load_process.c
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
// Complete process loading sequence
int load_process(const char* executable_path, int priority) {
    // Step 1: Read executable header to determine size
    ExecutableHeader header;
    if (read_executable_header(executable_path, &header) < 0) {
        return -1;  // Invalid executable
    }
    
    uint32_t process_size = header.code_size + header.data_size 
                          + header.bss_size + header.stack_size;
    
    // Step 2: Size check
    if (process_size > PARTITION_SIZE) {
        log_error("Process requires %u bytes, max is %u", 
                  process_size, PARTITION_SIZE);
        return -1;  // Too large
    }
    
    // Step 3: Create process control block
    int pid = create_pcb(executable_path, priority);
    
    // Step 4: Allocate partition
    int partition = allocate_partition(pid, process_size);
    if (partition < 0) {
        // No free partition - add to waiting queue
        add_to_memory_wait_queue(pid, process_size);
        log_info("Process %d waiting for memory", pid);
        return pid;  // Process created but not loaded
    }
    
    uint32_t base = partition_table[partition].base_address;
    
    // Step 5: Load executable sections into partition
    load_code_section(executable_path, base);
    load_data_section(executable_path, base + header.code_size);
    zero_bss_section(base + header.code_size + header.data_size, 
                     header.bss_size);
    // Stack grows from top of partition
    uint32_t stack_top = base + PARTITION_SIZE;
    
    // Step 6: Initialize PCB with memory layout
    PCB* pcb = get_pcb(pid);
    pcb->base_address = base;
    pcb->limit = PARTITION_SIZE;
    pcb->program_counter = base;  // Entry point
    pcb->stack_pointer = stack_top;
    pcb->state = PROCESS_READY;
    
    // Step 7: Add to ready queue
    add_to_ready_queue(pid);
    
    log_info("Process %d loaded into partition %d at 0x%08X", 
             pid, partition, base);
    
    return pid;
}

Workload Analysis and System Behavior

The effectiveness of equal-size partitioning depends critically on the workload characteristics. Let's analyze how the system behaves under different scenarios.

Scenario 1: Homogeneous Workload

Conditions: All processes require approximately the same memory (close to partition size)

Example: A system with 8 MB partitions running processes that each need 6-8 MB.

Analysis:

Memory utilization is high (75-100% per partition)
Minimal wasted space
All partitions equally suitable for any process
System operates at designed efficiency

This is the ideal case for equal-size partitioning—it was designed precisely for such workloads.

Scenario 2: Heterogeneous Workload

Conditions: Process sizes vary significantly

Example: 8 MB partitions with processes requiring 1 MB to 20 MB.

Small Processes (< 8 MB)

•Can be loaded into any partition
•Significant space wasted per partition
•A 1 MB process wastes 7 MB (87.5%)
•High internal fragmentation

Large Processes (> 8 MB)

•Cannot be loaded at all
•Must be rejected or redesigned
•No amount of free memory helps
•System cannot serve these workloads

Scenario 3: Memory Pressure

Conditions: More processes want to run than there are partitions

Analysis: With n partitions, at most n processes can be memory-resident. Additional processes must:

Wait in a queue until a partition becomes free
Be swapped to disk (if swapping is implemented)
Be rejected with a "system busy" error

Unlike variable-size schemes, no amount of memory reorganization can help. If all 8 partitions are occupied by processes using 1 MB each (7 MB wasted each), a 9th 1 MB process cannot run—even though 56 MB of memory is effectively unused.

This rigid limitation motivates the development of more sophisticated memory management techniques.

Memory Utilization Analysis: 64 MB User Memory, 8 × 8 MB Partitions
Process Distribution	Actual Memory Used	Partition Memory Allocated	Utilization %	Assessment
8 × 8 MB processes	64 MB	64 MB	100%	Optimal
8 × 6 MB processes	48 MB	64 MB	75%	Good
8 × 4 MB processes	32 MB	64 MB	50%	Poor
8 × 1 MB processes	8 MB	64 MB	12.5%	Wasteful
4 × 8 MB + blocked	32 MB	32 MB	50%	Blocked by limit

The Fundamental Trade-Off

Equal-size partitioning forces a painful choice:

Large partitions: Good for big processes but waste memory on small ones, limit multi-programming degree.

Small partitions: Good for small processes but cannot run large ones, even with abundant free memory.

There is no partition size that works well for all workloads—this limitation is inherent to the equal-size approach.

Advantages and Suitable Use Cases

Despite its limitations, equal-size partitioning offers genuine advantages that made it practical for its era and relevant for understanding modern systems.

Key Advantages

Strengths of Equal-Size Partitioning

•Extreme Simplicity — Implementation requires minimal code, minimal data structures, minimal ongoing maintenance. The entire partition manager might be under 200 lines of code.
•Predictable Allocation — Allocation either succeeds in O(n) time or fails immediately. There's no pathological case where allocation takes unexpectedly long.
•No External Fragmentation — Unlike variable partitioning, there's no fragmented free space. Each partition is either fully available or fully occupied.
•Instant Deallocation — Freeing a partition is O(1). Mark it free and signal waiters. No merging, no compaction, no bookkeeping.
•Uniform Hardware Support — The limit register never changes. Hardware can optimize for this uniformity.
•Easy Swapping — Any process can be swapped to disk and reloaded into any partition. No relocation needed.
•Simple Protection — Identical protection bounds for all processes simplifies security analysis.

Suitable Use Cases

1. Embedded Systems with Fixed Tasks A control system running exactly 4 monitoring tasks of similar size can use 4 equal partitions efficiently. The fixed workload matches the fixed allocation.

2. Batch Processing with Standardized Jobs Historical mainframes ran standardized COBOL batch jobs with predictable memory requirements. System administrators could size partitions to match typical job profiles.

3. Educational Systems The simplicity makes equal-size partitioning ideal for teaching memory management fundamentals. Students can implement a complete working system.

4. Very Small Partition Counts With only 2-4 partitions (common in early systems), the overhead of more sophisticated schemes wasn't justified. Equal-size worked "well enough."

5. Real-Time Systems with Known Bounds Systems where maximum memory per task is strictly bounded can use equal-size partitions sized to that bound, gaining predictability.

Modern Echoes

While not used directly in modern general-purpose OS, the equal-size philosophy appears in:

• Fixed-size slab allocators for kernel objects • Page-based allocation (fixed 4KB pages) • Memory pools in embedded systems • Container resource limits (fixed memory quotas)

The principle—simplify by fixing sizes—remains powerful.

Summary: Equal-Size Fixed Partitioning

We have conducted a thorough examination of equal-size fixed partitioning, the simplest approach to multi-programming memory management.

Key Takeaways

Core Concepts Mastered

•Static Division: Memory divided at boot into n partitions of identical size S; division fixed for system lifetime.
•Exclusive Allocation: Each partition holds exactly one process or remains empty; no sharing, no splitting.
•Base/Limit Protection: Hardware registers enforce partition boundaries; all partitions use same limit value.
•Algorithm Simplicity: O(n) allocation via linear scan; O(1) deallocation by state change.
•Internal Fragmentation: Space inside partitions wasted when process smaller than partition size.
•Degree of Multiprogramming: Maximum concurrent processes equals number of partitions n.
•Size Constraint: Processes larger than S cannot run, regardless of total free memory.
•Historical Context: Designed for 1960s constraints; simple hardware, predictable batch workloads.

What's Next

The equal-size constraint creates a fundamental tension: partition size that works for one workload fails for another. The next page examines unequal-size partitioning, which relaxes the uniformity constraint to better accommodate diverse process sizes. This seemingly small change introduces significant new complexity in allocation strategy.

Conceptual Foundation Established

You now understand the fundamental principles, implementation, and trade-offs of equal-size fixed partitioning. This knowledge forms the foundation for analyzing all subsequent memory management schemes—each one addresses specific limitations we've identified here.

1 / 5

Loading learning content...

Operating SystemsFixed Partitioning

Fixed Partitioning: Static Memory Division

LevelIntermediate

Duration60 mins

TopicFixed Partitioning

1 / 5

Equal-Size Partitions

The Challenge of Sharing Main Memory

How do you divide a single, finite physical memory among multiple processes that have no knowledge of each other's existence?

Learning Objectives

By the end of this page, you will:

The Core Concept: Uniform Division of Memory

The Defining Characteristics

Let's formalize the properties that define this scheme:

2. Uniform Size Every partition has identical dimensions. If partition P₁ is 8 MB, then P₂, P₃, ..., Pₙ are all exactly 8 MB. There are no exceptions, no special cases.

3. Exclusive Allocation Each partition can hold at most one process at any given time. A partition is either:

Free: Available for allocation to a new process
Occupied: Contains exactly one process (no sharing)

4. Fixed Boundaries Partition boundaries are immutable. A process allocated to a partition cannot "spill over" into adjacent partitions, regardless of its actual memory requirements.

The Simplicity Principle

Mathematical Formalization

Given:

M = Total physical memory available for user processes
n = Number of equal-size partitions
S = Size of each partition

The fundamental relationship is:

S = M ÷ n

Or equivalently:

M = n × S

This relationship constrains system design. A system administrator configuring the partition scheme must choose either n or S, and the other is determined. For example:

64 MB memory with 8 partitions → 8 MB per partition
64 MB memory with 4 MB partitions → 16 partitions

The degree of multi-programming (maximum concurrent processes) equals n—you can never have more processes in memory than you have partitions, regardless of how small those processes might be.

Example: 64 MB Memory with Various Partition Configurations
Number of Partitions (n)	Partition Size (S)	Max Processes	Best For
4	16 MB	4	Few large processes
8	8 MB	8	Balanced workload
16	4 MB	16	Many small processes
32	2 MB	32	High concurrency, small tasks
64	1 MB	64	Maximum concurrency

Historical Context: Why Equal-Size Partitions?

The Era's Constraints

3. Simple Protection Needs The primary protection mechanism was typically a pair of base and limit registers:

Base register: Starting physical address of the partition
Limit register: Size of the partition

With equal-size partitions, the limit register could be hardwired to a single value, simplifying the hardware.

The IBM System/360 Connection

The Design Philosophy

Equal-size fixed partitioning embodies a particular philosophy that trades flexibility for simplicity:

Memory Layout and System Architecture

Understanding the physical memory layout is crucial for grasping how equal-size partitioning integrates with the broader system architecture.

Physical Memory Organization

Physical memory in a fixed-partition system is typically organized as follows:

+---------------------------+ 0x00000000 (Address 0)
|   Interrupt Vectors       |  
|   (Reserved by Hardware)  |  
+---------------------------+
|                           |
|   Operating System        |  
|   (Kernel Code + Data)    |  
|                           |  
+---------------------------+ OS_END
|                           |
|   Partition 0             | Size = S
|   [Process A or FREE]     |
|                           |
+---------------------------+ OS_END + S
|                           |
|   Partition 1             | Size = S
|   [Process B or FREE]     |
|                           |
+---------------------------+ OS_END + 2S
|                           |
|   Partition 2             | Size = S
|   [Process C or FREE]     |
|                           |
+---------------------------+ OS_END + 3S
|          ...              |
+---------------------------+ OS_END + (n-1)S
|                           |
|   Partition n-1           | Size = S
|   [Process N or FREE]     |
|                           |
+---------------------------+ MEMORY_TOP

Address Calculation

The starting address of partition i is:

Partition_Start(i) = OS_END + (i × S)

Where OS_END is the first address after the operating system's reserved memory region. This formula enables O(1) address calculation for any partition—no searching, no pointer chasing.

Base and Limit Register Integration

The hardware protection mechanism works as follows:

When a process is dispatched (given the CPU):

The OS loads the base register with the starting address of the process's partition
The OS loads the limit register with the partition size S
Every memory access by the process is checked by hardware:
- Compute: physical_address = base + logical_address
- Check: logical_address < limit
- If check fails: Generate protection fault (trap to OS)

For equal-size partitions:

The limit register always holds the same value S
Only the base register changes during context switches
Hardware can potentially optimize for this uniformity

Partition Addressing Modes

Processes generate logical addresses (also called virtual addresses in this context) relative to address 0. The hardware automatically translates these to physical addresses:

Logical Address: 0x00001000 (4 KB into process memory)
Base Register:   0x00100000 (Partition 3 starts here)
Physical Address: 0x00101000 (Base + Logical)

This translation is transparent to the process—it believes it has memory starting at address 0, regardless of which partition it actually occupies.

Example: 4 Equal Partitions in 32 MB User Memory
Partition #	Base Address	Limit	Physical Range	Current State
0	0x00800000 (8 MB)	8 MB	8 MB - 16 MB	Process A (PID 101)
1	0x01000000 (16 MB)	8 MB	16 MB - 24 MB	FREE
2	0x01800000 (24 MB)	8 MB	24 MB - 32 MB	Process B (PID 203)
3	0x02000000 (32 MB)	8 MB	32 MB - 40 MB	Process C (PID 157)

Implementation: Data Structures and Algorithms

Implementing equal-size fixed partitioning requires minimal but carefully designed data structures. The simplicity is a primary advantage of this scheme.

Core Data Structures

The OS maintains a Partition Table that tracks the state of each partition:

partition_table.c
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
// System configuration constants (set at boot time)
#define NUM_PARTITIONS    8
#define PARTITION_SIZE    (8 * 1024 * 1024)  // 8 MB each
#define USER_MEM_START    0x00800000         // After OS kernel
 
// Partition states
typedef enum {
    PARTITION_FREE,      // Available for allocation
    PARTITION_OCCUPIED   // Contains an active process
} PartitionState;
 
// Partition descriptor
typedef struct {
    PartitionState state;           // Current state
    int            process_id;      // PID of occupying process (-1 if free)
    uint32_t       base_address;    // Starting physical address
    uint32_t       size;            // Partition size (always PARTITION_SIZE)
    uint64_t       allocation_time; // Timestamp for debugging/statistics
} PartitionDescriptor;
 
// The global partition table
PartitionDescriptor partition_table[NUM_PARTITIONS];
 
// Initialize partition table at boot time
void init_partition_table(void) {
    for (int i = 0; i < NUM_PARTITIONS; i++) {
        partition_table[i].state = PARTITION_FREE;
        partition_table[i].process_id = -1;
        partition_table[i].base_address = USER_MEM_START + (i * PARTITION_SIZE);
        partition_table[i].size = PARTITION_SIZE;
        partition_table[i].allocation_time = 0;
    }
}

Allocation Algorithm

The allocation algorithm for equal-size partitions is remarkably simple. When a process requests memory, the OS simply finds any free partition:

allocate_partition.c
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
// Allocate a partition to a process
// Returns partition index on success, -1 on failure
int allocate_partition(int process_id, uint32_t required_size) {
    // Critical check: Process must fit in a partition
    if (required_size > PARTITION_SIZE) {
        // Process too large for any partition
        log_error("Process %d requires %u bytes, max partition size is %u",
                  process_id, required_size, PARTITION_SIZE);
        return -1;  // Allocation failure
    }
    
    // Search for any free partition (linear scan)
    for (int i = 0; i < NUM_PARTITIONS; i++) {
        if (partition_table[i].state == PARTITION_FREE) {
            // Found a free partition - allocate it
            partition_table[i].state = PARTITION_OCCUPIED;
            partition_table[i].process_id = process_id;
            partition_table[i].allocation_time = get_current_time();
            
            // Update process control block with memory info
            set_process_memory(process_id, 
                               partition_table[i].base_address,
                               PARTITION_SIZE);
            
            log_info("Allocated partition %d to process %d (base: 0x%08X)",
                     i, process_id, partition_table[i].base_address);
            
            return i;  // Success - return partition index
        }
    }
    
    // No free partition available
    log_warning("No free partition for process %d - system at capacity", 
                process_id);
    return -1;  // Allocation failure - must wait or swap
}

Time Complexity Analysis

Allocation: O(n) in worst case, where n is the number of partitions. We scan until finding a free partition.

Deallocation: O(1) if we know the partition index; O(n) if we search by process ID.

Memory Access: O(1) address translation via hardware base register.

In practice, with a small number of partitions (typically 4-16), this linear scan is negligible.

Deallocation Algorithm

When a process terminates, its partition must be released:

deallocate_partition.c
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
// Deallocate a partition when a process terminates
void deallocate_partition(int process_id) {
    for (int i = 0; i < NUM_PARTITIONS; i++) {
        if (partition_table[i].process_id == process_id) {
            // Found the process's partition
            
            // Security: Zero out memory to prevent data leakage
            // (Critical in multi-user systems)
            memset((void*)partition_table[i].base_address, 0, PARTITION_SIZE);
            
            // Mark partition as free
            partition_table[i].state = PARTITION_FREE;
            partition_table[i].process_id = -1;
            partition_table[i].allocation_time = 0;
            
            log_info("Deallocated partition %d (formerly process %d)", 
                     i, process_id);
            
            // Wake up any processes waiting for memory
            signal_memory_available();
            
            return;
        }
    }
    
    // Process not found - programming error or double-free
    log_error("Attempted to deallocate partition for unknown process %d", 
              process_id);
}

Process Loading and Execution Lifecycle

Understanding how a process is loaded into a partition and begins execution reveals the practical mechanics of this memory management scheme.

The Loading Sequence

When a user submits a job (program) for execution, the following sequence occurs:

Process Loading Steps

•Job Submission: User submits executable file with memory requirements
•Size Check: OS verifies process size ≤ PARTITION_SIZE; rejects if too large
•Partition Search: OS scans partition table for PARTITION_FREE entry
•Wait or Proceed: If no free partition, job enters wait queue; otherwise continue
•Memory Allocation: Mark partition as PARTITION_OCCUPIED, record PID
•Image Loading: Copy executable code and data from disk to partition memory
•Relocation: Adjust addresses in loaded code (if not position-independent)
•PCB Setup: Create Process Control Block with base address, register state
•Ready Queue: Add process to scheduler's ready queue
•Dispatch: When scheduled, load base/limit registers and transfer control

Relocation: A Critical Detail

Programs are typically compiled with addresses starting at 0. When loaded into a partition starting at a different address, there are two approaches:

1. Static Relocation (Load-Time) The loader adjusts all memory references in the program before execution begins. This is a one-time cost at load time.

2. Dynamic Relocation (Run-Time) The base register performs address adjustment on every memory access. All logical addresses are added to the base register to produce physical addresses.

load_process.c
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
// Complete process loading sequence
int load_process(const char* executable_path, int priority) {
    // Step 1: Read executable header to determine size
    ExecutableHeader header;
    if (read_executable_header(executable_path, &header) < 0) {
        return -1;  // Invalid executable
    }
    
    uint32_t process_size = header.code_size + header.data_size 
                          + header.bss_size + header.stack_size;
    
    // Step 2: Size check
    if (process_size > PARTITION_SIZE) {
        log_error("Process requires %u bytes, max is %u", 
                  process_size, PARTITION_SIZE);
        return -1;  // Too large
    }
    
    // Step 3: Create process control block
    int pid = create_pcb(executable_path, priority);
    
    // Step 4: Allocate partition
    int partition = allocate_partition(pid, process_size);
    if (partition < 0) {
        // No free partition - add to waiting queue
        add_to_memory_wait_queue(pid, process_size);
        log_info("Process %d waiting for memory", pid);
        return pid;  // Process created but not loaded
    }
    
    uint32_t base = partition_table[partition].base_address;
    
    // Step 5: Load executable sections into partition
    load_code_section(executable_path, base);
    load_data_section(executable_path, base + header.code_size);
    zero_bss_section(base + header.code_size + header.data_size, 
                     header.bss_size);
    // Stack grows from top of partition
    uint32_t stack_top = base + PARTITION_SIZE;
    
    // Step 6: Initialize PCB with memory layout
    PCB* pcb = get_pcb(pid);
    pcb->base_address = base;
    pcb->limit = PARTITION_SIZE;
    pcb->program_counter = base;  // Entry point
    pcb->stack_pointer = stack_top;
    pcb->state = PROCESS_READY;
    
    // Step 7: Add to ready queue
    add_to_ready_queue(pid);
    
    log_info("Process %d loaded into partition %d at 0x%08X", 
             pid, partition, base);
    
    return pid;
}

Workload Analysis and System Behavior

The effectiveness of equal-size partitioning depends critically on the workload characteristics. Let's analyze how the system behaves under different scenarios.

Scenario 1: Homogeneous Workload

Conditions: All processes require approximately the same memory (close to partition size)

Example: A system with 8 MB partitions running processes that each need 6-8 MB.

Analysis:

Memory utilization is high (75-100% per partition)
Minimal wasted space
All partitions equally suitable for any process
System operates at designed efficiency

This is the ideal case for equal-size partitioning—it was designed precisely for such workloads.

Scenario 2: Heterogeneous Workload

Conditions: Process sizes vary significantly

Example: 8 MB partitions with processes requiring 1 MB to 20 MB.

Small Processes (< 8 MB)

•Can be loaded into any partition
•Significant space wasted per partition
•A 1 MB process wastes 7 MB (87.5%)
•High internal fragmentation

Large Processes (> 8 MB)

•Cannot be loaded at all
•Must be rejected or redesigned
•No amount of free memory helps
•System cannot serve these workloads

Scenario 3: Memory Pressure

Conditions: More processes want to run than there are partitions

Analysis: With n partitions, at most n processes can be memory-resident. Additional processes must:

Wait in a queue until a partition becomes free
Be swapped to disk (if swapping is implemented)
Be rejected with a "system busy" error

This rigid limitation motivates the development of more sophisticated memory management techniques.

Memory Utilization Analysis: 64 MB User Memory, 8 × 8 MB Partitions
Process Distribution	Actual Memory Used	Partition Memory Allocated	Utilization %	Assessment
8 × 8 MB processes	64 MB	64 MB	100%	Optimal
8 × 6 MB processes	48 MB	64 MB	75%	Good
8 × 4 MB processes	32 MB	64 MB	50%	Poor
8 × 1 MB processes	8 MB	64 MB	12.5%	Wasteful
4 × 8 MB + blocked	32 MB	32 MB	50%	Blocked by limit

The Fundamental Trade-Off

Equal-size partitioning forces a painful choice:

Large partitions: Good for big processes but waste memory on small ones, limit multi-programming degree.

Small partitions: Good for small processes but cannot run large ones, even with abundant free memory.

There is no partition size that works well for all workloads—this limitation is inherent to the equal-size approach.

Advantages and Suitable Use Cases

Despite its limitations, equal-size partitioning offers genuine advantages that made it practical for its era and relevant for understanding modern systems.

Key Advantages

Strengths of Equal-Size Partitioning

•Extreme Simplicity — Implementation requires minimal code, minimal data structures, minimal ongoing maintenance. The entire partition manager might be under 200 lines of code.
•Predictable Allocation — Allocation either succeeds in O(n) time or fails immediately. There's no pathological case where allocation takes unexpectedly long.
•No External Fragmentation — Unlike variable partitioning, there's no fragmented free space. Each partition is either fully available or fully occupied.
•Instant Deallocation — Freeing a partition is O(1). Mark it free and signal waiters. No merging, no compaction, no bookkeeping.
•Uniform Hardware Support — The limit register never changes. Hardware can optimize for this uniformity.
•Easy Swapping — Any process can be swapped to disk and reloaded into any partition. No relocation needed.
•Simple Protection — Identical protection bounds for all processes simplifies security analysis.

Suitable Use Cases

1. Embedded Systems with Fixed Tasks A control system running exactly 4 monitoring tasks of similar size can use 4 equal partitions efficiently. The fixed workload matches the fixed allocation.

3. Educational Systems The simplicity makes equal-size partitioning ideal for teaching memory management fundamentals. Students can implement a complete working system.

4. Very Small Partition Counts With only 2-4 partitions (common in early systems), the overhead of more sophisticated schemes wasn't justified. Equal-size worked "well enough."

5. Real-Time Systems with Known Bounds Systems where maximum memory per task is strictly bounded can use equal-size partitions sized to that bound, gaining predictability.

Modern Echoes

While not used directly in modern general-purpose OS, the equal-size philosophy appears in:

• Fixed-size slab allocators for kernel objects • Page-based allocation (fixed 4KB pages) • Memory pools in embedded systems • Container resource limits (fixed memory quotas)

The principle—simplify by fixing sizes—remains powerful.

Summary: Equal-Size Fixed Partitioning

We have conducted a thorough examination of equal-size fixed partitioning, the simplest approach to multi-programming memory management.

Key Takeaways

Core Concepts Mastered

•Static Division: Memory divided at boot into n partitions of identical size S; division fixed for system lifetime.
•Exclusive Allocation: Each partition holds exactly one process or remains empty; no sharing, no splitting.
•Base/Limit Protection: Hardware registers enforce partition boundaries; all partitions use same limit value.
•Algorithm Simplicity: O(n) allocation via linear scan; O(1) deallocation by state change.
•Internal Fragmentation: Space inside partitions wasted when process smaller than partition size.
•Degree of Multiprogramming: Maximum concurrent processes equals number of partitions n.
•Size Constraint: Processes larger than S cannot run, regardless of total free memory.
•Historical Context: Designed for 1960s constraints; simple hardware, predictable batch workloads.

What's Next

Conceptual Foundation Established

1 / 5