Fixed Partitioning - Learning Module

Loading content...

0/240

Partition Assignment

The Matching Problem: Processes Meet Partitions

With our understanding of fixed partitioning mechanics and internal fragmentation in place, we now confront a central operational question:

When a process is ready to run, which partition should it receive?

This question seems simple in equal-size partitioning—any free partition works equally well. But even in that simple case, decisions about waiting processes introduce complexity. Which waiting process gets the next free partition? What if multiple partitions free simultaneously?

For unequal-size partitioning, the question becomes genuinely complex:

A 2 MB process could use a 2 MB, 4 MB, 8 MB, or 16 MB partition
Each choice has different fragmentation costs
The choice affects which future processes can run
System-wide efficiency depends on making good matches

Partition assignment encompasses all the policies and algorithms that govern how processes are matched to partitions. Getting this right is essential—poor assignment can waste memory even when better configurations exist.

Learning Objectives

By the end of this page, you will:

• Understand the full partition assignment decision space • Master assignment strategies for equal-size partitions • Implement first-fit, best-fit, and worst-fit for unequal partitions • Analyze single-queue vs. multiple-queue waiting management • Integrate partition assignment with process scheduling • Evaluate optimality and practical trade-offs

Assignment in Equal-Size Partitioning

In equal-size partitioning, all partitions are functionally identical. This simplifies assignment but doesn't eliminate the need for policy decisions.

The Simple Case: Process Arrives, Partition Free

When a process arrives and at least one partition is free:

Select any free partition (all are equivalent)
Allocate it to the process
Load and begin execution

Since all partitions have the same size, no allocation strategy offers advantage—first-fit, best-fit, worst-fit all behave identically.

equal_size_assign.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Assignment for equal-size partitions: trivially simple
int assign_partition_equal_size(int process_id, uint32_t size) {
    // Check if process can fit (same check for all partitions)
    if (size > PARTITION_SIZE) {
        return -1;  // Too large for any partition
    }
    
    // Find any free partition
    for (int i = 0; i < NUM_PARTITIONS; i++) {
        if (partition_table[i].state == PARTITION_FREE) {
            partition_table[i].state = PARTITION_OCCUPIED;
            partition_table[i].process_id = process_id;
            return i;
        }
    }
    
    return -1;  // No free partition
}

The Interesting Case: No Free Partition

When all partitions are occupied and a new process arrives, the system must manage waiting processes. This is where policy decisions become significant.

Option 1: FCFS (First-Come, First-Served) Queue

Maintain a single queue of waiting processes. When a partition frees, allocate it to the longest-waiting process (if it fits).

Pros: Fair, simple, predictable
Cons: Large processes may wait indefinitely while small ones arrive continuously

Option 2: Priority Queue

Order waiting processes by priority. Higher-priority processes get first access to freed partitions.

Pros: Important processes run sooner
Cons: Starvation risk for low-priority processes

Option 3: Size-Aware Queue

Order by process size, perhaps serving small processes first.

Pros: Maximizes throughput (more small jobs complete)
Cons: Large jobs may starve

Relation to Scheduling

Partition assignment waiting policies interact with CPU scheduling. A process without a partition cannot reach the ready queue. Thus, partition assignment acts as a memory admission filter before scheduling begins. Poor admission policies create unfairness that scheduling cannot fix.

Assignment in Unequal-Size Partitioning

With partitions of different sizes, assignment strategy significantly affects system efficiency. Let's analyze the three classical approaches in depth.

First-Fit Strategy

Algorithm: Scan partitions in order (typically by address). Allocate the first partition that is free AND large enough.

Characteristics:

Fast: Stops at first match, often after few comparisons
Biased: Tends to fill low-address partitions first
May waste large partitions on small processes

first_fit_detailed.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
// First-Fit with detailed logging and statistics
typedef struct {
                    int assignments;
                    int scans_total;
                    int wasted_bytes_total;
} FirstFitStats;
 
FirstFitStats ff_stats = {0, 0, 0};
 
int first_fit_assign(int process_id, uint32_t required_size) {
    int scans = 0;
    
    for (int i = 0; i < system_config.num_partitions; i++) {
        scans++;
        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;
            
            // Update statistics
            ff_stats.assignments++;
            ff_stats.scans_total += scans;
            ff_stats.wasted_bytes_total += p->wasted_space;
            
            log_debug("First-fit: pid=%d size=%u -> part=%d (size=%u, waste=%u, scans=%d)",
                      process_id, required_size, i, p->size, p->wasted_space, scans);
            
            return i;
        }
    }
    
    log_debug("First-fit: pid=%d size=%u -> NO PARTITION (scans=%d)",
              process_id, required_size, scans);
    return -1;
}
 
void report_first_fit_stats(void) {
    if (ff_stats.assignments > 0) {
        double avg_scans = (double)ff_stats.scans_total / ff_stats.assignments;
        double avg_waste = (double)ff_stats.wasted_bytes_total / ff_stats.assignments;
        
        printf("First-Fit Statistics:
");
        printf("  Assignments: %d
", ff_stats.assignments);
        printf("  Avg scans per assignment: %.2f
", avg_scans);
        printf("  Total wasted: %d bytes
", ff_stats.wasted_bytes_total);
        printf("  Avg waste per assignment: %.2f bytes
", avg_waste);
    }
}

Best-Fit Strategy

Algorithm: Scan ALL partitions. Choose the smallest partition that is free AND large enough.

Characteristics:

Slower: Must examine all partitions
Minimizes per-allocation waste
Preserves large partitions for large future requests
Can work poorly if small leftover fragments are unusable

best_fit_detailed.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
// Best-Fit with optimization for perfect matches
int best_fit_assign(int process_id, uint32_t required_size) {
    int best_index = -1;
    uint32_t best_size = UINT32_MAX;
    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;
            
            // Update best if this partition has less waste
            if (waste < best_waste) {
                best_index = i;
                best_size = p->size;
                best_waste = waste;
                
                // Optimization: perfect fit - stop searching
                if (waste == 0) {
                    log_debug("Best-fit: found perfect match (partition %d)", i);
                    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;
        
        log_debug("Best-fit: pid=%d size=%u -> part=%d (size=%u, waste=%u)",
                  process_id, required_size, best_index, best_size, best_waste);
        
        return best_index;
    }
    
    log_debug("Best-fit: pid=%d size=%u -> NO PARTITION", 
              process_id, required_size);
    return -1;
}

Worst-Fit Strategy

Algorithm: Scan ALL partitions. Choose the LARGEST partition that is free.

Rationale (for variable partitioning): Leave maximum leftover space, which might be usable for another process.

Problem in Fixed Partitioning: Leftover space is internal fragmentation—unusable by other processes. Worst-fit is generally not recommended for fixed partitioning.

worst_fit_detailed.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 (generally not recommended for fixed partitioning)
int worst_fit_assign(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) {
            
            worst_index = i;
            max_size = p->size;
        }
    }
    
    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;
        
        // Warning: this is often a poor choice
        log_warning("Worst-fit: pid=%d size=%u -> part=%d (size=%u, waste=%u) - consider using best-fit",
                    process_id, required_size, worst_index, max_size, p->wasted_space);
        
        return worst_index;
    }
    
    return -1;
}

Worst-Fit Caution

Worst-fit was designed for variable-size partitioning, where "leftover" space forms a new hole that might satisfy future requests. In fixed partitioning, there is no leftover—the internal fragmentation cannot be reclaimed. Using worst-fit in fixed partitioning typically maximizes waste, the opposite of its design intent.

Comparative Analysis: Which Strategy Wins?

Let's rigorously compare the allocation strategies using simulation and theoretical analysis.

Theoretical Comparison

Allocation Strategy Comparison for Fixed Partitioning
Criterion	First-Fit	Best-Fit	Worst-Fit
Time Complexity	O(n) average, O(1) best	O(n) always	O(n) always
Space Efficiency	Medium—may waste large partitions	High—minimizes per-allocation waste	Low—maximizes per-allocation waste
Implementation	Simplest	Slightly complex	Simple but counterproductive
Large Process Friendliness	Poor—may fill large partitions early	Excellent—preserves large partitions	Poor—fills largest first
Recommended for Fixed?	Yes, for speed	Yes, for efficiency	No

Simulation Study

Consider a system with 5 unequal partitions [2 MB, 4 MB, 4 MB, 8 MB, 16 MB] and a sequence of 5 processes [3 MB, 2 MB, 5 MB, 4 MB, 10 MB]:

First-Fit Sequence:

Process	Size	Scanned	Assigned	Waste
P1	3 MB	1-2	4 MB (#1)	1 MB
P2	2 MB	1	2 MB (#0)	0 MB
P3	5 MB	1-3	8 MB (#3)	3 MB
P4	4 MB	1-2	4 MB (#2)	0 MB
P5	10 MB	1-4	16 MB (#4)	6 MB

Total Waste: 10 MB Average Scans: 2.2

Best-Fit Sequence:

Process	Size	Scanned	Assigned	Waste
P1	3 MB	1-5	4 MB (#1)	1 MB
P2	2 MB	1-5	2 MB (#0)	0 MB
P3	5 MB	1-5	8 MB (#3)	3 MB
P4	4 MB	1-5	4 MB (#2)	0 MB
P5	10 MB	1-5	16 MB (#4)	6 MB

Total Waste: 10 MB Average Scans: 5.0

In this example, both strategies achieve the same waste (10 MB) because the partition sizes happen to match the process sizes well. The difference is in scan count: first-fit averaged 2.2 scans, best-fit always scanned all 5.

When Best-Fit Wins

Best-fit outperforms first-fit when:

Process order could fill large partitions first: If a 7 MB process arrives before a 15 MB process, first-fit might assign it to the 16 MB partition, leaving no room for the 15 MB process. Best-fit would assign 7 MB to the 8 MB partition.
Multiple size matches exist: When several partitions could fit, best-fit picks the tightest, maximizing options for future allocations.
Large processes are expected: Best-fit preserves large partitions for anticipated large processes.

Practical Recommendation

Use Best-Fit when:

Partition count is small (scan cost negligible)
Workload has significant size variation
Large processes are important to serve

Use First-Fit when:

Partition count is large (scan cost matters)
Workload is relatively uniform
Speed is prioritized over optimal allocation

In most fixed partitioning systems (typically 4-16 partitions), the scan cost difference is negligible, making Best-Fit generally preferred.

Queue Management: Handling Waiting Processes

When all suitable partitions are occupied, processes must wait. How we organize waiting significantly affects system fairness and efficiency.

Single Queue Approach

All processes waiting for any partition share one global queue.

single_queue_manager.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
// Single global queue implementation
typedef struct WaitingProcess {
    int process_id;
    uint32_t required_size;
    uint64_t arrival_time;
    int priority;
    struct WaitingProcess* next;
} WaitingProcess;
 
WaitingProcess* global_wait_queue = NULL;
 
// Add process to waiting queue (FCFS order)
void enqueue_waiting_process(int pid, uint32_t size, int priority) {
    WaitingProcess* wp = malloc(sizeof(WaitingProcess));
    wp->process_id = pid;
    wp->required_size = size;
    wp->arrival_time = get_current_time();
    wp->priority = priority;
    wp->next = NULL;
    
    if (!global_wait_queue) {
        global_wait_queue = wp;
    } else {
        WaitingProcess* tail = global_wait_queue;
        while (tail->next) tail = tail->next;
        tail->next = wp;
    }
    
    log_info("Process %d (size=%u) added to wait queue", pid, size);
}
 
// When partition i is freed, try to assign a waiting process
void on_partition_freed_single_queue(int partition_index) {
    uint32_t partition_size = system_config.partitions[partition_index].size;
    
    WaitingProcess* prev = NULL;
    WaitingProcess* curr = global_wait_queue;
    
    // Find first waiting process that fits this partition
    while (curr) {
        if (curr->required_size <= partition_size) {
            // Assign this waiting process to the freed partition
            allocate_specific_partition(partition_index, 
                                        curr->process_id,
                                        curr->required_size);
            
            // Remove from queue
            if (prev) prev->next = curr->next;
            else global_wait_queue = curr->next;
            
            uint64_t wait_time = get_current_time() - curr->arrival_time;
            log_info("Process %d assigned to partition %d after %llu ms wait",
                     curr->process_id, partition_index, wait_time);
            
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    }
    
    // No suitable waiting process; partition remains free
    log_debug("Partition %d freed, no suitable waiting process", partition_index);
}

Multiple Queues Approach

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

multiple_queues_manager.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
// Multiple queues: one per partition
WaitingProcess* partition_queues[MAX_PARTITIONS];
 
// Find the best partition queue for a given size
int find_queue_for_size(uint32_t required_size) {
    int best_partition = -1;
    uint32_t best_size = UINT32_MAX;
    
    // Find smallest partition that can fit the process
    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_partition = i;
        }
    }
    
    return best_partition;  // -1 if no partition can fit
}
 
// Add process to specific partition's queue
void enqueue_for_partition(int partition_index, int pid, uint32_t size) {
    WaitingProcess* wp = malloc(sizeof(WaitingProcess));
    wp->process_id = pid;
    wp->required_size = size;
    wp->arrival_time = get_current_time();
    wp->next = NULL;
    
    // Append to partition's queue
    if (!partition_queues[partition_index]) {
        partition_queues[partition_index] = wp;
    } else {
        WaitingProcess* tail = partition_queues[partition_index];
        while (tail->next) tail = tail->next;
        tail->next = wp;
    }
    
    log_info("Process %d queued for partition %d (size %u)",
             pid, partition_index, system_config.partitions[partition_index].size);
}
 
// When partition i is freed, serve its queue
void on_partition_freed_multi_queue(int partition_index) {
    if (partition_queues[partition_index]) {
        WaitingProcess* wp = partition_queues[partition_index];
        partition_queues[partition_index] = wp->next;
        
        allocate_specific_partition(partition_index,
                                    wp->process_id,
                                    wp->required_size);
        
        uint64_t wait_time = get_current_time() - wp->arrival_time;
        log_info("Process %d assigned to partition %d from dedicated queue after %llu ms",
                 wp->process_id, partition_index, wait_time);
        
        free(wp);
    } else {
        log_debug("Partition %d freed, queue empty", partition_index);
    }
}

Single Queue vs. Multiple Queues Comparison
Aspect	Single Queue	Multiple Queues
Implementation	Simple—one data structure	Complex—queue per partition
Partition utilization	Higher—any suitable process can use any suitable partition	Lower—processes bound to specific partitions
Internal fragmentation	Potentially higher—small process may take large partition	Lower—processes matched to appropriate sizes
Fairness	Global FCFS—first suitable process served	Per-partition FCFS—processes compete only within their class
Starvation risk	Possible—large process waits while small ones fill large partitions	Reduced—large processes have dedicated large-partition queues
Queue management overhead	O(queue length) scan per freed partition	O(1) dequeue from specific partition's queue

Integration with Process Scheduling

Partition assignment doesn't operate in isolation—it's part of the broader process management picture. Understanding its integration with scheduling is essential.

The Two-Stage Admission Model

Process admission involves two sequential stages:

Stage 1: Memory Admission (Partition Assignment)

Can the process fit in any partition?
If yes, allocate partition → proceed to Stage 2
If no, wait in memory queue or reject

Stage 2: CPU Admission (Scheduling)

Process is in a partition and ready to run
Enters the scheduler's ready queue
Competes for CPU time based on scheduling algorithm

two_stage_admission.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
// Two-stage admission: Memory first, then CPU
typedef enum {
    PROCESS_NEW,            // Just created
    PROCESS_WAITING_MEMORY, // Waiting for partition
    PROCESS_READY,          // Has partition, waiting for CPU
    PROCESS_RUNNING,        // Currently executing
    PROCESS_BLOCKED,        // Waiting for I/O
    PROCESS_TERMINATED      // Finished
} ProcessState;
 
// Submit a new process for execution
int submit_process(ProcessInfo* info) {
    int pid = create_process_structure(info);
    set_process_state(pid, PROCESS_NEW);
    
    // Stage 1: Try to allocate memory
    int partition = best_fit_assign(pid, info->memory_size);
    
    if (partition >= 0) {
        // Memory assigned - proceed to CPU scheduling
        set_process_state(pid, PROCESS_READY);
        load_process_into_partition(pid, partition);
        add_to_ready_queue(pid);
        
        log_info("Process %d admitted immediately (partition %d)", pid, partition);
    } else {
        // No memory available - wait
        set_process_state(pid, PROCESS_WAITING_MEMORY);
        enqueue_waiting_process(pid, info->memory_size, info->priority);
        
        log_info("Process %d waiting for memory", pid);
    }
    
    return pid;
}
 
// Called when a process terminates
void process_exit(int pid) {
    // Get process's partition
    int partition = get_process_partition(pid);
    
    // Mark partition free
    deallocate_partition(pid);
    set_process_state(pid, PROCESS_TERMINATED);
    
    // Try to assign freed partition to waiting process
    on_partition_freed_single_queue(partition);
    
    // Cleanup process structure
    destroy_process_structure(pid);
}

Priority Integration

When multiple processes wait for memory, should priorities influence assignment?

Option 1: FCFS Memory, Priority CPU

Memory allocation ignores priority—first come, first served
CPU scheduling respects priority
Simple but may delay high-priority processes for memory

Option 2: Priority-Aware Memory Allocation

High-priority processes jump memory queue
More complex but ensures important work runs sooner
Risk: low-priority starvation

Swapping Consideration

Systems with swapping add another dimension. When a high-priority process needs memory:

If partition free → allocate normally
If no partition free but lower-priority process occupies some → swap out the low-priority process, allocate to high-priority

Swapping enables priority-based preemption of memory, not just CPU. This significantly complicates partition management but improves responsiveness for important processes.

Optimality: Can We Do Better?

An important theoretical question: given a sequence of processes, what is the optimal partition assignment that minimizes total waste? And can we achieve it in practice?

The Offline Optimal

If we knew all process arrivals and departures in advance, we could compute an optimal assignment using integer programming or exhaustive search. This offline optimal serves as a benchmark.

Problem Formulation:

Given: Partition sizes S₁, S₂, ..., Sₙ
Given: Process sizes R₁, R₂, ..., Rₘ and arrival/departure times
Minimize: Total internal fragmentation over the workload

This is related to the bin packing problem and is NP-hard for large instances. However, for small partition counts, exhaustive search is feasible.

Online vs. Offline Analysis

Offline algorithms know the entire future—all process arrivals, sizes, and durations. They can make globally optimal decisions.

Online algorithms see only the present—current partitions, current processes, current requests. They must make decisions without knowing future requests.

All practical partition assignment algorithms are online. The question becomes: how close can online algorithms get to offline optimal?

Competitive Ratios for Bin Packing (Theoretical Reference)
Algorithm	Competitive Ratio	Interpretation
First-Fit	≤ 1.7 OPT	At most 70% worse than optimal
Best-Fit	≤ 1.7 OPT	At most 70% worse than optimal
First-Fit Decreasing	≤ 1.22 OPT	Much closer (requires sorting)
Online Lower Bound	≥ 1.54 OPT	No online algorithm can always beat this

Practical Implications

The competitive analysis shows that First-Fit and Best-Fit perform reasonably well—at most 70% more waste than optimal. For fixed partitioning:

Don't optimize endlessly—simple algorithms get most of the benefit
Focus on partition configuration—sizing partitions well often matters more than assignment algorithm
Monitor actual performance—theoretical bounds are worst-case; practice may be much better

Practical Near-Optimality

For most workloads, Best-Fit with well-configured partitions achieves near-optimal results:

1. Right-size partitions: Analyze workload and match partition sizes to common process sizes.

2. Use Best-Fit: Minimize per-allocation waste.

3. Balance partition counts: Ensure enough partitions of each needed size.

4. Monitor and adjust: Periodically review fragmentation statistics and reconfigure if needed.

The difference between theoretical optimal and practical Best-Fit is usually small enough to not justify more complex approaches.

Advanced Assignment Techniques

Beyond the basic algorithms, several advanced techniques can improve partition assignment in specific scenarios.

Technique 1: Next-Fit

Like First-Fit, but remembers where the last allocation occurred and starts searching from there, wrapping around.

Advantage: Distributes allocations more evenly across partitions Disadvantage: May skip perfectly suitable partitions at lower addresses

next_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
// Next-Fit: circular search from last allocation point
static int last_allocated_index = 0;
 
int next_fit_assign(int process_id, uint32_t required_size) {
    int n = system_config.num_partitions;
    
    // Search from last allocation point, wrapping around
    for (int count = 0; count < n; count++) {
        int i = (last_allocated_index + count) % n;
        PartitionDescriptor* p = &system_config.partitions[i];
        
        if (p->state == PARTITION_FREE && p->size >= required_size) {
            p->state = PARTITION_OCCUPIED;
            p->process_id = process_id;
            p->wasted_space = p->size - required_size;
            
            last_allocated_index = (i + 1) % n;  // Remember for next search
            
            log_debug("Next-fit: pid=%d -> partition %d", process_id, i);
            return i;
        }
    }
    
    return -1;  // No suitable partition
}

Technique 2: Sorted Partition Table

Maintain partition table sorted by size (ascending or descending). This can speed up Best-Fit (stop at first fit in ascending order) or enable efficient binary search.

Technique 3: Free List Optimization

Maintain a separate linked list of only free partitions. Reduces search time when most partitions are occupied.

free_list.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
// Free partition list for O(free_count) search instead of O(total)
typedef struct FreeNode {
    int partition_index;
    struct FreeNode* next;
} FreeNode;
 
FreeNode* free_list = NULL;
 
// Add partition to free list (call on deallocation)
void add_to_free_list(int partition_index) {
    FreeNode* node = malloc(sizeof(FreeNode));
    node->partition_index = partition_index;
    node->next = free_list;
    free_list = node;
}
 
// Remove partition from free list (call on allocation)
void remove_from_free_list(int partition_index) {
    FreeNode* prev = NULL;
    FreeNode* curr = free_list;
    
    while (curr) {
        if (curr->partition_index == partition_index) {
            if (prev) prev->next = curr->next;
            else free_list = curr->next;
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    }
}
 
// Best-fit using free list only
int best_fit_free_list(int process_id, uint32_t required_size) {
    int best_index = -1;
    uint32_t best_size = UINT32_MAX;
    
    for (FreeNode* node = free_list; node; node = node->next) {
        uint32_t psize = system_config.partitions[node->partition_index].size;
        if (psize >= required_size && psize < best_size) {
            best_size = psize;
            best_index = node->partition_index;
            if (psize == required_size) break;  // Perfect fit
        }
    }
    
    if (best_index >= 0) {
        allocate_specific_partition(best_index, process_id, required_size);
        remove_from_free_list(best_index);
        return best_index;
    }
    
    return -1;
}

Overhead vs. Benefit

Advanced techniques add implementation complexity. In fixed partitioning systems with few partitions (typically <16), linear scan is fast enough that optimization rarely provides meaningful benefit. These techniques become valuable in systems with many allocation units—which is one reason modern paging superseded fixed partitioning.

Summary: Partition Assignment

We have thoroughly examined the algorithms and policies that govern how processes are matched to partitions in fixed partitioning systems.

Core Concepts Mastered

•Equal-Size Assignment: Trivial—any free partition works equally well; complexity is in queue management.
•First-Fit: Fast (stops early), may waste large partitions on small processes.
•Best-Fit: Slower but minimizes per-allocation waste; preserves large partitions.
•Worst-Fit: Inappropriate for fixed partitioning—maximizes waste.
•Single Queue: Higher utilization but potential for waste and unfairness.
•Multiple Queues: Predictable per-size allocation but lower overall utilization.
•Scheduling Integration: Memory admission precedes CPU scheduling; two-stage model.
•Optimality: First-Fit/Best-Fit within 1.7× of optimal; focus on configuration over algorithm tuning.

What's Next

We've covered the mechanics, fragmentation, and assignment of fixed partitioning. The final page in this module addresses the crucial question: What are the fundamental limitations of this approach? Understanding these limitations explains why operating systems evolved toward more sophisticated memory management schemes.

Assignment Mastery Complete

You now understand the full spectrum of partition assignment strategies and can analyze their trade-offs. This knowledge enables you to configure fixed partitioning systems effectively and appreciate the algorithmic foundations that persist in modern memory allocators.

Partition Assignment

The Matching Problem: Processes Meet Partitions

With our understanding of fixed partitioning mechanics and internal fragmentation in place, we now confront a central operational question:

When a process is ready to run, which partition should it receive?

For unequal-size partitioning, the question becomes genuinely complex:

A 2 MB process could use a 2 MB, 4 MB, 8 MB, or 16 MB partition
Each choice has different fragmentation costs
The choice affects which future processes can run
System-wide efficiency depends on making good matches

Learning Objectives

By the end of this page, you will:

Assignment in Equal-Size Partitioning

In equal-size partitioning, all partitions are functionally identical. This simplifies assignment but doesn't eliminate the need for policy decisions.

The Simple Case: Process Arrives, Partition Free

When a process arrives and at least one partition is free:

Select any free partition (all are equivalent)
Allocate it to the process
Load and begin execution

Since all partitions have the same size, no allocation strategy offers advantage—first-fit, best-fit, worst-fit all behave identically.

equal_size_assign.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Assignment for equal-size partitions: trivially simple
int assign_partition_equal_size(int process_id, uint32_t size) {
    // Check if process can fit (same check for all partitions)
    if (size > PARTITION_SIZE) {
        return -1;  // Too large for any partition
    }
    
    // Find any free partition
    for (int i = 0; i < NUM_PARTITIONS; i++) {
        if (partition_table[i].state == PARTITION_FREE) {
            partition_table[i].state = PARTITION_OCCUPIED;
            partition_table[i].process_id = process_id;
            return i;
        }
    }
    
    return -1;  // No free partition
}

The Interesting Case: No Free Partition

When all partitions are occupied and a new process arrives, the system must manage waiting processes. This is where policy decisions become significant.

Option 1: FCFS (First-Come, First-Served) Queue

Maintain a single queue of waiting processes. When a partition frees, allocate it to the longest-waiting process (if it fits).

Pros: Fair, simple, predictable
Cons: Large processes may wait indefinitely while small ones arrive continuously

Option 2: Priority Queue

Order waiting processes by priority. Higher-priority processes get first access to freed partitions.

Pros: Important processes run sooner
Cons: Starvation risk for low-priority processes

Option 3: Size-Aware Queue

Order by process size, perhaps serving small processes first.

Pros: Maximizes throughput (more small jobs complete)
Cons: Large jobs may starve

Relation to Scheduling

Assignment in Unequal-Size Partitioning

With partitions of different sizes, assignment strategy significantly affects system efficiency. Let's analyze the three classical approaches in depth.

First-Fit Strategy

Algorithm: Scan partitions in order (typically by address). Allocate the first partition that is free AND large enough.

Characteristics:

Fast: Stops at first match, often after few comparisons
Biased: Tends to fill low-address partitions first
May waste large partitions on small processes

first_fit_detailed.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
// First-Fit with detailed logging and statistics
typedef struct {
                    int assignments;
                    int scans_total;
                    int wasted_bytes_total;
} FirstFitStats;
 
FirstFitStats ff_stats = {0, 0, 0};
 
int first_fit_assign(int process_id, uint32_t required_size) {
    int scans = 0;
    
    for (int i = 0; i < system_config.num_partitions; i++) {
        scans++;
        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;
            
            // Update statistics
            ff_stats.assignments++;
            ff_stats.scans_total += scans;
            ff_stats.wasted_bytes_total += p->wasted_space;
            
            log_debug("First-fit: pid=%d size=%u -> part=%d (size=%u, waste=%u, scans=%d)",
                      process_id, required_size, i, p->size, p->wasted_space, scans);
            
            return i;
        }
    }
    
    log_debug("First-fit: pid=%d size=%u -> NO PARTITION (scans=%d)",
              process_id, required_size, scans);
    return -1;
}
 
void report_first_fit_stats(void) {
    if (ff_stats.assignments > 0) {
        double avg_scans = (double)ff_stats.scans_total / ff_stats.assignments;
        double avg_waste = (double)ff_stats.wasted_bytes_total / ff_stats.assignments;
        
        printf("First-Fit Statistics:
");
        printf("  Assignments: %d
", ff_stats.assignments);
        printf("  Avg scans per assignment: %.2f
", avg_scans);
        printf("  Total wasted: %d bytes
", ff_stats.wasted_bytes_total);
        printf("  Avg waste per assignment: %.2f bytes
", avg_waste);
    }
}

Best-Fit Strategy

Algorithm: Scan ALL partitions. Choose the smallest partition that is free AND large enough.

Characteristics:

Slower: Must examine all partitions
Minimizes per-allocation waste
Preserves large partitions for large future requests
Can work poorly if small leftover fragments are unusable

best_fit_detailed.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
// Best-Fit with optimization for perfect matches
int best_fit_assign(int process_id, uint32_t required_size) {
    int best_index = -1;
    uint32_t best_size = UINT32_MAX;
    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;
            
            // Update best if this partition has less waste
            if (waste < best_waste) {
                best_index = i;
                best_size = p->size;
                best_waste = waste;
                
                // Optimization: perfect fit - stop searching
                if (waste == 0) {
                    log_debug("Best-fit: found perfect match (partition %d)", i);
                    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;
        
        log_debug("Best-fit: pid=%d size=%u -> part=%d (size=%u, waste=%u)",
                  process_id, required_size, best_index, best_size, best_waste);
        
        return best_index;
    }
    
    log_debug("Best-fit: pid=%d size=%u -> NO PARTITION", 
              process_id, required_size);
    return -1;
}

Worst-Fit Strategy

Algorithm: Scan ALL partitions. Choose the LARGEST partition that is free.

Rationale (for variable partitioning): Leave maximum leftover space, which might be usable for another process.

Problem in Fixed Partitioning: Leftover space is internal fragmentation—unusable by other processes. Worst-fit is generally not recommended for fixed partitioning.

worst_fit_detailed.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 (generally not recommended for fixed partitioning)
int worst_fit_assign(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) {
            
            worst_index = i;
            max_size = p->size;
        }
    }
    
    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;
        
        // Warning: this is often a poor choice
        log_warning("Worst-fit: pid=%d size=%u -> part=%d (size=%u, waste=%u) - consider using best-fit",
                    process_id, required_size, worst_index, max_size, p->wasted_space);
        
        return worst_index;
    }
    
    return -1;
}

Worst-Fit Caution

Comparative Analysis: Which Strategy Wins?

Let's rigorously compare the allocation strategies using simulation and theoretical analysis.

Theoretical Comparison

Allocation Strategy Comparison for Fixed Partitioning
Criterion	First-Fit	Best-Fit	Worst-Fit
Time Complexity	O(n) average, O(1) best	O(n) always	O(n) always
Space Efficiency	Medium—may waste large partitions	High—minimizes per-allocation waste	Low—maximizes per-allocation waste
Implementation	Simplest	Slightly complex	Simple but counterproductive
Large Process Friendliness	Poor—may fill large partitions early	Excellent—preserves large partitions	Poor—fills largest first
Recommended for Fixed?	Yes, for speed	Yes, for efficiency	No

Simulation Study

Consider a system with 5 unequal partitions [2 MB, 4 MB, 4 MB, 8 MB, 16 MB] and a sequence of 5 processes [3 MB, 2 MB, 5 MB, 4 MB, 10 MB]:

First-Fit Sequence:

Process	Size	Scanned	Assigned	Waste
P1	3 MB	1-2	4 MB (#1)	1 MB
P2	2 MB	1	2 MB (#0)	0 MB
P3	5 MB	1-3	8 MB (#3)	3 MB
P4	4 MB	1-2	4 MB (#2)	0 MB
P5	10 MB	1-4	16 MB (#4)	6 MB

Total Waste: 10 MB Average Scans: 2.2

Best-Fit Sequence:

Process	Size	Scanned	Assigned	Waste
P1	3 MB	1-5	4 MB (#1)	1 MB
P2	2 MB	1-5	2 MB (#0)	0 MB
P3	5 MB	1-5	8 MB (#3)	3 MB
P4	4 MB	1-5	4 MB (#2)	0 MB
P5	10 MB	1-5	16 MB (#4)	6 MB

Total Waste: 10 MB Average Scans: 5.0

When Best-Fit Wins

Best-fit outperforms first-fit when:

Process order could fill large partitions first: If a 7 MB process arrives before a 15 MB process, first-fit might assign it to the 16 MB partition, leaving no room for the 15 MB process. Best-fit would assign 7 MB to the 8 MB partition.
Multiple size matches exist: When several partitions could fit, best-fit picks the tightest, maximizing options for future allocations.
Large processes are expected: Best-fit preserves large partitions for anticipated large processes.

Practical Recommendation

Use Best-Fit when:

Partition count is small (scan cost negligible)
Workload has significant size variation
Large processes are important to serve

Use First-Fit when:

Partition count is large (scan cost matters)
Workload is relatively uniform
Speed is prioritized over optimal allocation

In most fixed partitioning systems (typically 4-16 partitions), the scan cost difference is negligible, making Best-Fit generally preferred.

Queue Management: Handling Waiting Processes

When all suitable partitions are occupied, processes must wait. How we organize waiting significantly affects system fairness and efficiency.

Single Queue Approach

All processes waiting for any partition share one global queue.

single_queue_manager.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
// Single global queue implementation
typedef struct WaitingProcess {
    int process_id;
    uint32_t required_size;
    uint64_t arrival_time;
    int priority;
    struct WaitingProcess* next;
} WaitingProcess;
 
WaitingProcess* global_wait_queue = NULL;
 
// Add process to waiting queue (FCFS order)
void enqueue_waiting_process(int pid, uint32_t size, int priority) {
    WaitingProcess* wp = malloc(sizeof(WaitingProcess));
    wp->process_id = pid;
    wp->required_size = size;
    wp->arrival_time = get_current_time();
    wp->priority = priority;
    wp->next = NULL;
    
    if (!global_wait_queue) {
        global_wait_queue = wp;
    } else {
        WaitingProcess* tail = global_wait_queue;
        while (tail->next) tail = tail->next;
        tail->next = wp;
    }
    
    log_info("Process %d (size=%u) added to wait queue", pid, size);
}
 
// When partition i is freed, try to assign a waiting process
void on_partition_freed_single_queue(int partition_index) {
    uint32_t partition_size = system_config.partitions[partition_index].size;
    
    WaitingProcess* prev = NULL;
    WaitingProcess* curr = global_wait_queue;
    
    // Find first waiting process that fits this partition
    while (curr) {
        if (curr->required_size <= partition_size) {
            // Assign this waiting process to the freed partition
            allocate_specific_partition(partition_index, 
                                        curr->process_id,
                                        curr->required_size);
            
            // Remove from queue
            if (prev) prev->next = curr->next;
            else global_wait_queue = curr->next;
            
            uint64_t wait_time = get_current_time() - curr->arrival_time;
            log_info("Process %d assigned to partition %d after %llu ms wait",
                     curr->process_id, partition_index, wait_time);
            
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    }
    
    // No suitable waiting process; partition remains free
    log_debug("Partition %d freed, no suitable waiting process", partition_index);
}

Multiple Queues Approach

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

multiple_queues_manager.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
// Multiple queues: one per partition
WaitingProcess* partition_queues[MAX_PARTITIONS];
 
// Find the best partition queue for a given size
int find_queue_for_size(uint32_t required_size) {
    int best_partition = -1;
    uint32_t best_size = UINT32_MAX;
    
    // Find smallest partition that can fit the process
    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_partition = i;
        }
    }
    
    return best_partition;  // -1 if no partition can fit
}
 
// Add process to specific partition's queue
void enqueue_for_partition(int partition_index, int pid, uint32_t size) {
    WaitingProcess* wp = malloc(sizeof(WaitingProcess));
    wp->process_id = pid;
    wp->required_size = size;
    wp->arrival_time = get_current_time();
    wp->next = NULL;
    
    // Append to partition's queue
    if (!partition_queues[partition_index]) {
        partition_queues[partition_index] = wp;
    } else {
        WaitingProcess* tail = partition_queues[partition_index];
        while (tail->next) tail = tail->next;
        tail->next = wp;
    }
    
    log_info("Process %d queued for partition %d (size %u)",
             pid, partition_index, system_config.partitions[partition_index].size);
}
 
// When partition i is freed, serve its queue
void on_partition_freed_multi_queue(int partition_index) {
    if (partition_queues[partition_index]) {
        WaitingProcess* wp = partition_queues[partition_index];
        partition_queues[partition_index] = wp->next;
        
        allocate_specific_partition(partition_index,
                                    wp->process_id,
                                    wp->required_size);
        
        uint64_t wait_time = get_current_time() - wp->arrival_time;
        log_info("Process %d assigned to partition %d from dedicated queue after %llu ms",
                 wp->process_id, partition_index, wait_time);
        
        free(wp);
    } else {
        log_debug("Partition %d freed, queue empty", partition_index);
    }
}

Single Queue vs. Multiple Queues Comparison
Aspect	Single Queue	Multiple Queues
Implementation	Simple—one data structure	Complex—queue per partition
Partition utilization	Higher—any suitable process can use any suitable partition	Lower—processes bound to specific partitions
Internal fragmentation	Potentially higher—small process may take large partition	Lower—processes matched to appropriate sizes
Fairness	Global FCFS—first suitable process served	Per-partition FCFS—processes compete only within their class
Starvation risk	Possible—large process waits while small ones fill large partitions	Reduced—large processes have dedicated large-partition queues
Queue management overhead	O(queue length) scan per freed partition	O(1) dequeue from specific partition's queue

Integration with Process Scheduling

Partition assignment doesn't operate in isolation—it's part of the broader process management picture. Understanding its integration with scheduling is essential.

The Two-Stage Admission Model

Process admission involves two sequential stages:

Stage 1: Memory Admission (Partition Assignment)

Can the process fit in any partition?
If yes, allocate partition → proceed to Stage 2
If no, wait in memory queue or reject

Stage 2: CPU Admission (Scheduling)

Process is in a partition and ready to run
Enters the scheduler's ready queue
Competes for CPU time based on scheduling algorithm

two_stage_admission.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
// Two-stage admission: Memory first, then CPU
typedef enum {
    PROCESS_NEW,            // Just created
    PROCESS_WAITING_MEMORY, // Waiting for partition
    PROCESS_READY,          // Has partition, waiting for CPU
    PROCESS_RUNNING,        // Currently executing
    PROCESS_BLOCKED,        // Waiting for I/O
    PROCESS_TERMINATED      // Finished
} ProcessState;
 
// Submit a new process for execution
int submit_process(ProcessInfo* info) {
    int pid = create_process_structure(info);
    set_process_state(pid, PROCESS_NEW);
    
    // Stage 1: Try to allocate memory
    int partition = best_fit_assign(pid, info->memory_size);
    
    if (partition >= 0) {
        // Memory assigned - proceed to CPU scheduling
        set_process_state(pid, PROCESS_READY);
        load_process_into_partition(pid, partition);
        add_to_ready_queue(pid);
        
        log_info("Process %d admitted immediately (partition %d)", pid, partition);
    } else {
        // No memory available - wait
        set_process_state(pid, PROCESS_WAITING_MEMORY);
        enqueue_waiting_process(pid, info->memory_size, info->priority);
        
        log_info("Process %d waiting for memory", pid);
    }
    
    return pid;
}
 
// Called when a process terminates
void process_exit(int pid) {
    // Get process's partition
    int partition = get_process_partition(pid);
    
    // Mark partition free
    deallocate_partition(pid);
    set_process_state(pid, PROCESS_TERMINATED);
    
    // Try to assign freed partition to waiting process
    on_partition_freed_single_queue(partition);
    
    // Cleanup process structure
    destroy_process_structure(pid);
}

Priority Integration

When multiple processes wait for memory, should priorities influence assignment?

Option 1: FCFS Memory, Priority CPU

Memory allocation ignores priority—first come, first served
CPU scheduling respects priority
Simple but may delay high-priority processes for memory

Option 2: Priority-Aware Memory Allocation

High-priority processes jump memory queue
More complex but ensures important work runs sooner
Risk: low-priority starvation

Swapping Consideration

Systems with swapping add another dimension. When a high-priority process needs memory:

If partition free → allocate normally
If no partition free but lower-priority process occupies some → swap out the low-priority process, allocate to high-priority

Swapping enables priority-based preemption of memory, not just CPU. This significantly complicates partition management but improves responsiveness for important processes.

Optimality: Can We Do Better?

An important theoretical question: given a sequence of processes, what is the optimal partition assignment that minimizes total waste? And can we achieve it in practice?

The Offline Optimal

If we knew all process arrivals and departures in advance, we could compute an optimal assignment using integer programming or exhaustive search. This offline optimal serves as a benchmark.

Problem Formulation:

Given: Partition sizes S₁, S₂, ..., Sₙ
Given: Process sizes R₁, R₂, ..., Rₘ and arrival/departure times
Minimize: Total internal fragmentation over the workload

This is related to the bin packing problem and is NP-hard for large instances. However, for small partition counts, exhaustive search is feasible.

Online vs. Offline Analysis

Offline algorithms know the entire future—all process arrivals, sizes, and durations. They can make globally optimal decisions.

Online algorithms see only the present—current partitions, current processes, current requests. They must make decisions without knowing future requests.

All practical partition assignment algorithms are online. The question becomes: how close can online algorithms get to offline optimal?

Competitive Ratios for Bin Packing (Theoretical Reference)
Algorithm	Competitive Ratio	Interpretation
First-Fit	≤ 1.7 OPT	At most 70% worse than optimal
Best-Fit	≤ 1.7 OPT	At most 70% worse than optimal
First-Fit Decreasing	≤ 1.22 OPT	Much closer (requires sorting)
Online Lower Bound	≥ 1.54 OPT	No online algorithm can always beat this

Practical Implications

The competitive analysis shows that First-Fit and Best-Fit perform reasonably well—at most 70% more waste than optimal. For fixed partitioning:

Don't optimize endlessly—simple algorithms get most of the benefit
Focus on partition configuration—sizing partitions well often matters more than assignment algorithm
Monitor actual performance—theoretical bounds are worst-case; practice may be much better

Practical Near-Optimality

For most workloads, Best-Fit with well-configured partitions achieves near-optimal results:

1. Right-size partitions: Analyze workload and match partition sizes to common process sizes.

2. Use Best-Fit: Minimize per-allocation waste.

3. Balance partition counts: Ensure enough partitions of each needed size.

4. Monitor and adjust: Periodically review fragmentation statistics and reconfigure if needed.

The difference between theoretical optimal and practical Best-Fit is usually small enough to not justify more complex approaches.

Advanced Assignment Techniques

Beyond the basic algorithms, several advanced techniques can improve partition assignment in specific scenarios.

Technique 1: Next-Fit

Like First-Fit, but remembers where the last allocation occurred and starts searching from there, wrapping around.

Advantage: Distributes allocations more evenly across partitions Disadvantage: May skip perfectly suitable partitions at lower addresses

next_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
// Next-Fit: circular search from last allocation point
static int last_allocated_index = 0;
 
int next_fit_assign(int process_id, uint32_t required_size) {
    int n = system_config.num_partitions;
    
    // Search from last allocation point, wrapping around
    for (int count = 0; count < n; count++) {
        int i = (last_allocated_index + count) % n;
        PartitionDescriptor* p = &system_config.partitions[i];
        
        if (p->state == PARTITION_FREE && p->size >= required_size) {
            p->state = PARTITION_OCCUPIED;
            p->process_id = process_id;
            p->wasted_space = p->size - required_size;
            
            last_allocated_index = (i + 1) % n;  // Remember for next search
            
            log_debug("Next-fit: pid=%d -> partition %d", process_id, i);
            return i;
        }
    }
    
    return -1;  // No suitable partition
}

Technique 2: Sorted Partition Table

Maintain partition table sorted by size (ascending or descending). This can speed up Best-Fit (stop at first fit in ascending order) or enable efficient binary search.

Technique 3: Free List Optimization

Maintain a separate linked list of only free partitions. Reduces search time when most partitions are occupied.

free_list.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
// Free partition list for O(free_count) search instead of O(total)
typedef struct FreeNode {
    int partition_index;
    struct FreeNode* next;
} FreeNode;
 
FreeNode* free_list = NULL;
 
// Add partition to free list (call on deallocation)
void add_to_free_list(int partition_index) {
    FreeNode* node = malloc(sizeof(FreeNode));
    node->partition_index = partition_index;
    node->next = free_list;
    free_list = node;
}
 
// Remove partition from free list (call on allocation)
void remove_from_free_list(int partition_index) {
    FreeNode* prev = NULL;
    FreeNode* curr = free_list;
    
    while (curr) {
        if (curr->partition_index == partition_index) {
            if (prev) prev->next = curr->next;
            else free_list = curr->next;
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    }
}
 
// Best-fit using free list only
int best_fit_free_list(int process_id, uint32_t required_size) {
    int best_index = -1;
    uint32_t best_size = UINT32_MAX;
    
    for (FreeNode* node = free_list; node; node = node->next) {
        uint32_t psize = system_config.partitions[node->partition_index].size;
        if (psize >= required_size && psize < best_size) {
            best_size = psize;
            best_index = node->partition_index;
            if (psize == required_size) break;  // Perfect fit
        }
    }
    
    if (best_index >= 0) {
        allocate_specific_partition(best_index, process_id, required_size);
        remove_from_free_list(best_index);
        return best_index;
    }
    
    return -1;
}

Overhead vs. Benefit

Summary: Partition Assignment

We have thoroughly examined the algorithms and policies that govern how processes are matched to partitions in fixed partitioning systems.

Core Concepts Mastered

•Equal-Size Assignment: Trivial—any free partition works equally well; complexity is in queue management.
•First-Fit: Fast (stops early), may waste large partitions on small processes.
•Best-Fit: Slower but minimizes per-allocation waste; preserves large partitions.
•Worst-Fit: Inappropriate for fixed partitioning—maximizes waste.
•Single Queue: Higher utilization but potential for waste and unfairness.
•Multiple Queues: Predictable per-size allocation but lower overall utilization.
•Scheduling Integration: Memory admission precedes CPU scheduling; two-stage model.
•Optimality: First-Fit/Best-Fit within 1.7× of optimal; focus on configuration over algorithm tuning.

What's Next

Assignment Mastery Complete