Fixed Partitioning - Learning Module

Loading content...

0/227

Unequal-Size Partitions

Beyond Uniformity: Recognizing Process Diversity

The equal-size partitioning scheme we examined previously embodies a powerful simplicity, but that simplicity comes at a cost. When system administrators observed real workloads, they noticed a persistent problem:

Real processes don't come in uniform sizes.

A typical computing environment might run:

Small utility programs requiring 512 KB
Medium-sized application programs requiring 2-4 MB
Large scientific computations requiring 16 MB or more
Batch processing jobs with requirements spanning the entire spectrum

With equal-size partitions, system administrators faced an impossible choice. Size partitions for large programs, and small programs waste enormous memory. Size partitions for small programs, and large programs cannot run at all.

Unequal-size partitioning emerged as the natural evolution: instead of dividing memory into identical slices, why not create partitions of different sizes to match the diversity of process requirements?

This seemingly simple idea introduces layers of complexity that illuminate fundamental computer science trade-offs. Let's explore them systematically.

Learning Objectives

By the end of this page, you will:

• Understand the design rationale for unequal-size partitions • Analyze the complexity increase compared to equal-size schemes • Master multiple allocation strategies for partition assignment • Evaluate trade-offs in partition size selection • Implement partition tables with heterogeneous sizes • Recognize historical systems that employed this approach

The Core Concept: Heterogeneous Division

Unequal-size fixed partitioning divides physical memory into a fixed number of partitions at system initialization, but unlike the equal-size variant, each partition may have a different, administrator-defined size.

Defining Characteristics

Let's formalize the properties that distinguish this scheme:

1. Static Division, Variable Sizes The memory is divided once at system startup into n partitions. However, partition sizes S₁, S₂, ..., Sₙ can differ from each other. Once established, these sizes remain constant during system operation.

2. Size Constraint The sum of all partition sizes must equal the available user memory:

S₁ + S₂ + S₃ + ... + Sₙ = M (total user memory)

3. Exclusive Allocation (Preserved) Each partition still holds at most one process. A partition is either free or occupied by exactly one process.

4. Fixed Boundaries (Preserved) Partition boundaries remain immutable. Partitions cannot be split, merged, or resized during operation.

Example: 64 MB Memory with Unequal Partitions
Partition #	Size	Base Address	Target Workload
0	2 MB	0x00800000	Small utilities
1	2 MB	0x00A00000	Small utilities
2	4 MB	0x00C00000	Small applications
3	4 MB	0x01000000	Small applications
4	8 MB	0x01400000	Medium applications
5	8 MB	0x01C00000	Medium applications
6	16 MB	0x02400000	Large programs
7	20 MB	0x03400000	Very large programs
—	64 MB Total	—	—

The Design Philosophy Shift

Unequal-size partitioning represents a fundamental shift in design philosophy:

Equal-Size Philosophy: "Treat all workloads identically."

One-size-fits-all approach
Maximum simplicity
Accepts mismatch for many workloads

Unequal-Size Philosophy: "Match infrastructure to workload characteristics."

Tailored approach based on workload analysis
Increased complexity
Better fit for diverse workloads

This shift requires the system administrator to possess knowledge about expected workload distributions—a form of capacity planning that would become increasingly important as systems grew more complex.

Workload Profiling

Effective unequal-size partitioning requires analyzing historical workloads:

• What sizes do processes typically require? • What's the distribution (many small, few large)? • What are the peak concurrent process counts per size category? • How does the mix vary by time of day or processing cycle?

This analysis drives partition configuration. Poor analysis leads to poor partition fit; excellent analysis leads to efficient memory utilization.

Implementation: Enhanced Data Structures

Unequal-size partitioning requires more sophisticated data structures than its equal-size counterpart, since we can no longer compute partition addresses from a uniform size.

Enhanced Partition Table

unequal_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
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
// Partition configuration (set at boot via configuration file)
#define MAX_PARTITIONS    16
 
// Partition states
typedef enum {
    PARTITION_FREE,
    PARTITION_OCCUPIED
} PartitionState;
 
// Partition descriptor with variable size
typedef struct {
    PartitionState state;
    int            process_id;      // PID (-1 if free)
    uint32_t       base_address;    // Starting physical address
    uint32_t       size;            // Size in bytes (varies per partition)
    uint32_t       wasted_space;    // Tracking internal fragmentation
    uint64_t       allocation_time;
} PartitionDescriptor;
 
// System configuration
typedef struct {
    int num_partitions;
    uint32_t total_memory;
    PartitionDescriptor partitions[MAX_PARTITIONS];
} PartitionConfig;
 
PartitionConfig system_config;
 
// Initialize from configuration file
int init_partition_config(const char* config_file) {
    FILE* f = fopen(config_file, "r");
    if (!f) return -1;
    
    uint32_t current_address = USER_MEM_START;
    system_config.num_partitions = 0;
    system_config.total_memory = 0;
    
    // Read partition sizes from config
    // Format: one size (in bytes) per line
    uint32_t size;
    while (fscanf(f, "%u", &size) == 1 && 
           system_config.num_partitions < MAX_PARTITIONS) {
        
        int i = system_config.num_partitions;
        system_config.partitions[i].state = PARTITION_FREE;
        system_config.partitions[i].process_id = -1;
        system_config.partitions[i].base_address = current_address;
        system_config.partitions[i].size = size;
        system_config.partitions[i].wasted_space = 0;
        system_config.partitions[i].allocation_time = 0;
        
        current_address += size;
        system_config.total_memory += size;
        system_config.num_partitions++;
    }
    
    fclose(f);
    
    log_info("Configured %d partitions, total %u MB",
             system_config.num_partitions,
             system_config.total_memory / (1024 * 1024));
    
    return 0;
}

Key Differences from Equal-Size

Notice the critical differences in this implementation:

1. Variable Size Field Each partition now stores its own size. We can no longer compute size from a global constant.

2. Pre-computed Base Addresses Base addresses must be stored explicitly. With equal sizes, we computed: base = START + (i × SIZE). With variable sizes, we must accumulate: base[i] = base[i-1] + size[i-1].

3. Wasted Space Tracking We track internal fragmentation per partition: wasted = partition.size - process.actual_size. This enables monitoring and optimization.

4. Configuration Complexity The initialization requires external configuration rather than simple arithmetic. This adds a failure mode (misconfiguration) but enables flexibility.

Configuration File Example

A typical partition configuration file might contain:

# partition_config.txt
# Sizes in bytes
2097152    # 2 MB - small utilities
2097152    # 2 MB - small utilities
4194304    # 4 MB - small apps
4194304    # 4 MB - small apps
8388608    # 8 MB - medium apps
8388608    # 8 MB - medium apps
16777216   # 16 MB - large programs
20971520   # 20 MB - very large programs

Changing this configuration requires a system reboot—the partitions are truly fixed at runtime.

Allocation Strategies: Choosing the Right Partition

With unequal-size partitions, a new question emerges that didn't exist before:

When multiple free partitions can accommodate a process, which partition should we choose?

This question defines the field of partition allocation strategies. Each strategy optimizes for different goals and produces different trade-offs.

Strategy 1: First Fit

Allocate the first partition (in address order) that is free and large enough.

first_fit.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// First Fit: Allocate first partition large enough
int allocate_first_fit(int process_id, uint32_t required_size) {
    for (int i = 0; i < system_config.num_partitions; i++) {
        PartitionDescriptor* p = &system_config.partitions[i];
        
        if (p->state == PARTITION_FREE && p->size >= required_size) {
            // Found suitable partition
            p->state = PARTITION_OCCUPIED;
            p->process_id = process_id;
            p->wasted_space = p->size - required_size;
            p->allocation_time = get_current_time();
            
            log_info("First-fit: Process %d (%u bytes) -> Partition %d (%u bytes), waste: %u",
                     process_id, required_size, i, p->size, p->wasted_space);
            
            return i;
        }
    }
    return -1;  // No suitable partition found
}

First Fit Characteristics

•Speed: Fast—stops at first suitable partition. O(n) worst case, but often O(1) or O(k) for small k.
•Memory: May waste space if first suitable partition is much larger than needed.
•Bias: Tends to allocate from lower-addressed memory, potentially leaving larger partitions free longer.
•Simple: Easy to implement and debug.

Strategy 2: Best Fit

Allocate the smallest partition that is free and large enough. This minimizes wasted space per allocation.

best_fit.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
// Best Fit: Allocate smallest partition large enough
int allocate_best_fit(int process_id, uint32_t required_size) {
    int best_index = -1;
    uint32_t best_waste = UINT32_MAX;
    
    for (int i = 0; i < system_config.num_partitions; i++) {
        PartitionDescriptor* p = &system_config.partitions[i];
        
        if (p->state == PARTITION_FREE && p->size >= required_size) {
            uint32_t waste = p->size - required_size;
            
            if (waste < best_waste) {
                best_waste = waste;
                best_index = i;
                
                // Optimization: perfect fit found
                if (waste == 0) break;
            }
        }
    }
    
    if (best_index >= 0) {
        PartitionDescriptor* p = &system_config.partitions[best_index];
        p->state = PARTITION_OCCUPIED;
        p->process_id = process_id;
        p->wasted_space = best_waste;
        p->allocation_time = get_current_time();
        
        log_info("Best-fit: Process %d (%u bytes) -> Partition %d (%u bytes), waste: %u",
                 process_id, required_size, best_index, p->size, best_waste);
        
        return best_index;
    }
    
    return -1;  // No suitable partition found
}

Best Fit Characteristics

•Speed: Slower—must scan all partitions to find optimal. Always O(n).
•Memory: Minimizes waste per allocation. Preserves larger partitions for larger processes.
•Bias: Tends to use small partitions first, leaving large partitions available.
•Complex: Requires tracking minimum across all partitions.

Strategy 3: Worst Fit

Allocate the largest free partition. The rationale: the leftover space (internal fragmentation) might be large enough to be "useful" in some conceptual sense.

worst_fit.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
// Worst Fit: Allocate largest partition available
int allocate_worst_fit(int process_id, uint32_t required_size) {
    int worst_index = -1;
    uint32_t max_size = 0;
    
    for (int i = 0; i < system_config.num_partitions; i++) {
        PartitionDescriptor* p = &system_config.partitions[i];
        
        if (p->state == PARTITION_FREE && 
            p->size >= required_size && 
            p->size > max_size) {
            
            max_size = p->size;
            worst_index = i;
        }
    }
    
    if (worst_index >= 0) {
        PartitionDescriptor* p = &system_config.partitions[worst_index];
        p->state = PARTITION_OCCUPIED;
        p->process_id = process_id;
        p->wasted_space = p->size - required_size;
        p->allocation_time = get_current_time();
        
        log_info("Worst-fit: Process %d (%u bytes) -> Partition %d (%u bytes), waste: %u",
                 process_id, required_size, worst_index, p->size, p->wasted_space);
        
        return worst_index;
    }
    
    return -1;  // No suitable partition found
}

Note on Worst Fit

Worst fit was designed for variable-size partitioning (where leftover space creates new holes), not fixed partitioning. In fixed partitioning, the "leftover space" is internal fragmentation that cannot be used by other processes. Worst fit in fixed partitioning typically performs poorly—it wastes large partitions on small processes that could have used small partitions.

Queue-Based Allocation: One Queue vs. Multiple Queues

When all suitable partitions are occupied, arriving processes must wait. The organization of waiting processes creates another design dimension.

Single Queue Design

All waiting processes share one global queue. When a partition becomes free, we scan the queue for a process that can use it.

single_queue.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
// Single global queue for waiting processes
typedef struct QueueNode {
    int process_id;
    uint32_t required_size;
    uint64_t arrival_time;
    struct QueueNode* next;
} QueueNode;
 
QueueNode* wait_queue_head = NULL;
QueueNode* wait_queue_tail = NULL;
 
// Add process to waiting queue
void enqueue_waiting(int process_id, uint32_t required_size) {
    QueueNode* node = malloc(sizeof(QueueNode));
    node->process_id = process_id;
    node->required_size = required_size;
    node->arrival_time = get_current_time();
    node->next = NULL;
    
    if (!wait_queue_tail) {
        wait_queue_head = wait_queue_tail = node;
    } else {
        wait_queue_tail->next = node;
        wait_queue_tail = node;
    }
}
 
// When partition i becomes free, try to allocate from queue
void on_partition_freed(int partition_index) {
    uint32_t partition_size = system_config.partitions[partition_index].size;
    
    QueueNode* prev = NULL;
    QueueNode* curr = wait_queue_head;
    
    while (curr) {
        if (curr->required_size <= partition_size) {
            // Found a process that fits
            allocate_specific_partition(partition_index, 
                                        curr->process_id, 
                                        curr->required_size);
            
            // Remove from queue
            if (prev) prev->next = curr->next;
            else wait_queue_head = curr->next;
            if (!curr->next) wait_queue_tail = prev;
            
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    }
    
    // No suitable process found; partition remains free
}

Single Queue Advantages

•Any suitable process can use any suitable partition
•Better overall memory utilization
•A freed partition finds the longest-waiting suitable process
•No small process blocked while large partition sits empty

Single Queue Disadvantages

•Small process may occupy large partition (high waste)
•Queue scan on every deallocation: O(queue length)
•Implementation more complex
•Less predictable allocation patterns

Multiple Queues Design

Each partition (or partition size class) maintains its own dedicated queue. Processes are assigned to the queue for the smallest partition that can accommodate them.

multiple_queues.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
// Multiple queues: one per partition
QueueNode* partition_queues[MAX_PARTITIONS];
 
// Associate process with specific partition queue
void enqueue_for_partition(int partition_index, int process_id) {
    QueueNode* node = malloc(sizeof(QueueNode));
    node->process_id = process_id;
    node->arrival_time = get_current_time();
    node->next = NULL;
    
    // Append to partition's queue
    if (!partition_queues[partition_index]) {
        partition_queues[partition_index] = node;
    } else {
        QueueNode* tail = partition_queues[partition_index];
        while (tail->next) tail = tail->next;
        tail->next = node;
    }
}
 
// Find best partition queue for a process
int find_best_queue(uint32_t required_size) {
    int best = -1;
    uint32_t best_size = UINT32_MAX;
    
    for (int i = 0; i < system_config.num_partitions; i++) {
        uint32_t psize = system_config.partitions[i].size;
        if (psize >= required_size && psize < best_size) {
            best_size = psize;
            best = i;
        }
    }
    return best;  // -1 if no partition can fit
}
 
// When partition i frees: serve its queue
void on_partition_freed_multi_queue(int partition_index) {
    if (partition_queues[partition_index]) {
        QueueNode* node = partition_queues[partition_index];
        partition_queues[partition_index] = node->next;
        
        allocate_specific_partition(partition_index, 
                                    node->process_id,
                                    /* size tracked elsewhere */);
        free(node);
    }
    // If queue empty, partition remains free
}

Multiple Queue Trade-off

Advantage: Processes always get their assigned partition size—predictable allocation, minimal waste.

Disadvantage: A small process waits in the small-partition queue even while large partitions sit empty. Utilization can suffer when workload doesn't match partition distribution.

This mirrors a classic systems trade-off: optimization versus fairness. Multiple queues optimize per-size-class but may be "unfair" from a global utilization perspective.

Comparative Analysis: Equal vs. Unequal Partitions

Let's systematically compare the two fixed partitioning schemes across multiple dimensions.

Fixed Partitioning: Equal-Size vs. Unequal-Size Comparison
Dimension	Equal-Size	Unequal-Size
Implementation complexity	Very simple	Moderate
Configuration effort	Choose one size	Design size distribution
Memory utilization (homogeneous workload)	High if well-matched	Can match closely
Memory utilization (heterogeneous workload)	Poor—one size forces waste	Better—multiple sizes available
Maximum process size	Fixed at S	Varies up to largest partition
Allocation time	O(n) simple scan	O(n) with strategy logic
Deallocation time	O(1)	O(1)
Internal fragmentation	Uniform waste pattern	Variable, often lower average
External fragmentation	None	None
Partition count flexibility	Easy to adjust	Requires careful planning

Worked Example: Workload Comparison

Consider a workload of 8 processes with the following memory requirements:

2 processes need 1 MB each
2 processes need 2 MB each
2 processes need 4 MB each
1 process needs 8 MB
1 process needs 16 MB

Equal-Size Approach (8 × 8 MB = 64 MB)

Process	Size	Partition	Waste
P1	1 MB	8 MB	7 MB
P2	1 MB	8 MB	7 MB
P3	2 MB	8 MB	6 MB
P4	2 MB	8 MB	6 MB
P5	4 MB	8 MB	4 MB
P6	4 MB	8 MB	4 MB
P7	8 MB	8 MB	0 MB
P8	16 MB	Cannot fit!	—

Total Used: 38 MB (excluding P8) Total Allocated: 56 MB Total Waste: 34 MB (47%) Rejected: 1 process

Unequal-Size Approach (2×1, 2×2, 2×4, 1×8, 1×16 = 38 MB)

Process	Size	Partition
P1	1 MB	1 MB
P2	1 MB	1 MB
P3	2 MB	2 MB
P4	2 MB	2 MB
P5	4 MB	4 MB
P6	4 MB	4 MB
P7	8 MB	8 MB
P8	16 MB	16 MB

Total Used: 38 MB Total Allocated: 38 MB Total Waste: 0 MB (0%) Rejected: 0 processes

The Power of Matching

When partition sizes match process sizes perfectly, unequal-size partitioning achieves optimal utilization. The challenge is that real workloads vary, and perfect matching is rarely possible. The administrator must make educated guesses about future workloads, and these guesses are fixed until reboot.

Historical Systems: OS/MFT and Its Legacy

The most historically significant implementation of unequal-size fixed partitioning was IBM's OS/MFT (Operating System with a fixed number of Tasks), part of the OS/360 family introduced in 1966.

OS/MFT Architecture

OS/MFT divided memory into a fixed set of regions (IBM's term for partitions). Key characteristics:

1. Operator-Configured Regions System operators defined region sizes at system generation (SYSGEN) or via configuration statements. A typical configuration might include:

3 small regions for utility programs
2 medium regions for application programs
1 large region for major batch jobs

2. Job-to-Region Assignment Jobs specified their region requirements in Job Control Language (JCL). The system matched jobs to appropriately-sized free regions.

//MYJOB JOB (...)
//STEP1 EXEC PGM=PROCESS,REGION=256K

3. Multiple Queues OS/MFT typically used multiple input queues, each associated with specific region sizes. Jobs waited in their designated queue until a matching region became available.

The MFT to MVT Transition

OS/MFT's limitations led IBM to develop OS/MVT (Multiprogramming with a Variable number of Tasks), which used variable-size partitioning. The evolution from MFT to MVT mirrors our curriculum progression from fixed to variable partitioning. MVT's added flexibility came with increased complexity—a trade-off that defines memory management history.

Design Lessons from OS/MFT

Studying OS/MFT reveals enduring principles:

1. Configuration is a Form of Programming Partition configuration required understanding workload characteristics. Poor configuration led to poor system performance, regardless of OS code quality.

2. Trade-offs Are Fundamental More regions meant more concurrency but smaller maximum job size. Fewer regions meant larger jobs could run but with less concurrency.

3. Static Decisions Have Long-Term Consequences Once configured, the system operated with those partitions until reconfiguration. This incentivized careful upfront analysis.

4. Real-World Pressure Drives Innovation OS/MFT's limitations in production environments drove the demand for more flexible schemes, leading to MVT and eventually paging.

Design Trade-offs: Choosing Partition Sizes

Designing an optimal partition configuration is a constrained optimization problem. Let's analyze the key trade-offs.

The Fundamental Tensions

Key Design Tensions

•Many Small Partitions: High concurrency for small jobs, but large jobs cannot run. Good when workload is dominated by small processes.
•Few Large Partitions: Large jobs can run, but small jobs waste space and concurrency is limited. Good when workload includes large computations.
•Mixed Sizes: Balance between large and small, but getting the mix right requires accurate workload prediction. Configuration becomes critical.
•Partition Count: More partitions = more data structure overhead + more scheduling complexity. Fewer partitions = simpler but less flexible.

Heuristics for Configuration

Experienced system administrators developed rules of thumb:

1. Analyze Historical Logs Study process sizes from past workloads. Build a histogram of memory requirements.

2. Match Distribution Configure partitions to match the frequency distribution. If 60% of jobs need ≤2 MB, allocate 60% of memory to small partitions.

3. Ensure Large-Job Capacity Always include at least one partition large enough for the largest expected job. Running important large jobs is often critical.

4. Leave Margin Don't size partitions exactly to current maximums. Leave 10-20% margin for growth.

5. Monitor and Adjust Track utilization over time. If certain partitions are always empty while their queues are full, reconfigure.

Example Configuration Analysis
Process Size Range	% of Workload	Suggested Partition Allocation
0-1 MB	40%	4 partitions × 1 MB
1-4 MB	35%	3 partitions × 4 MB
4-8 MB	15%	2 partitions × 8 MB
8-16 MB	8%	1 partition × 16 MB
16 MB	2%	1 partition × 32 MB

The Static Configuration Problem

No static configuration optimally serves a dynamic workload. Workloads change—by time of day, season, project phase, or business evolution. Fixed partitioning forces administrators to choose a single compromise configuration that serves the average case but may perform poorly during workload peaks or shifts. This fundamental limitation drove the development of dynamic partitioning schemes.

Summary: Unequal-Size Fixed Partitioning

We have thoroughly examined unequal-size fixed partitioning, understanding how relaxing the uniformity constraint enables better workload matching at the cost of increased complexity.

Core Concepts Mastered

•Heterogeneous Division: Memory divided into partitions of administrator-chosen sizes; sum equals total user memory.
•Design Philosophy: Tailored approach matching infrastructure to expected workload characteristics.
•Allocation Strategies: First-fit (fast), best-fit (minimal waste), worst-fit (generally poor for fixed partitioning).
•Queue Organization: Single queue (better utilization) vs. multiple queues (predictable, per-size allocation).
•Historical Context: OS/MFT pioneered this approach; its limitations drove evolution to variable partitioning.
•Configuration Complexity: Requires workload analysis; static configuration cannot optimally serve dynamic workloads.
•Trade-off Spectrum: Many small partitions (high concurrency) vs. few large partitions (large job support).

What's Next

Both equal-size and unequal-size fixed partitioning suffer from a common problem: internal fragmentation—wasted space inside allocated partitions. The next page examines this phenomenon in detail, providing quantitative analysis and understanding its impact on system efficiency.

Design Understanding Complete

You now understand both variants of fixed partitioning and can analyze their trade-offs. This knowledge prepares you to appreciate why internal fragmentation is such a significant concern, and why operating systems eventually moved to more dynamic memory management schemes.