Session 4.5 – Swapping and Relocation

Introduction to Swapping and Relocation

Swapping and relocation are fundamental techniques in memory management that allow operating systems to efficiently utilize limited physical memory and support multiprogramming by moving processes between main memory and secondary storage.

Swapping Concepts

Swapping involves moving entire processes or parts of processes between main memory and secondary storage to optimize memory utilization and system performance.

Swapping Mechanisms and Policies

Different swapping mechanisms and policies determine when, what, and how to swap processes or memory segments.

Swap Decision Algorithm:
if (free_memory < threshold) {
    select_victim();
    if (victim.priority < current.priority) {
        swap_out(victim);
    }
}

Victim Selection:
for each process p {
    score = priority_weight * p.priority +
            size_weight * p.memory_size +
            idle_weight * p.idle_time;
    if (score > best_score) {
        victim = p;
    }
}

Total Swap Time:
T_swap = T_context_save + 
         T_disk_access + 
         T_transfer + 
         T_context_restore

Example (100MB process):
T_swap = 1ms + 10ms + 200ms + 1ms = 212ms

Dynamic Relocation

Dynamic relocation allows programs to be loaded and executed from different memory locations without modification, enabling flexible memory management and supporting swapping operations.

Program Code:
LOAD R1, 100    ; Load from address 100
ADD  R1, R2     ; Add registers
STORE 200, R1   ; Store to address 200

Logical Addresses: 100, 200
Physical Addresses: 100, 200

Same Program Code:
LOAD R1, 100    ; Load from address 100
ADD  R1, R2     ; Add registers  
STORE 200, R1   ; Store to address 200

Logical Addresses: 100, 200
Physical Addresses: 5100, 5200

Base and Limit Registers

Base and limit registers provide a simple but effective mechanism for dynamic relocation and memory protection in single-user or simple multiprogramming systems.

MMU Components:
┌─────────────────────┐    ┌─────────────────────┐
│   Base Register     │    │   Limit Register    │
│      (Relocation)   │    │     (Protection)    │
│                     │    │                     │
│      14000          │    │       2000          │
└─────────────────────┘    └─────────────────────┘
           │                           │
           ▼                           ▼
┌─────────────────────────────────────────────────┐
│           Memory Management Unit (MMU)          │
│                                                 │
│  Physical_Addr = Logical_Addr + Base           │
│  if (Logical_Addr >= Limit) → Protection_Fault │
└─────────────────────────────────────────────────┘

Base Register Usage:
Process A: Base = 0     (0-4K)
Process B: Base = 4000  (4K-8K) 
Process C: Base = 8000  (8K-12K)

Context Switch:
OLD_BASE = save_base_register();
load_base_register(NEW_BASE);

Protection Check:
if (logical_address >= limit_register) {
    generate_protection_fault();
    return;
}
physical_address = logical_address + base_register;
access_memory(physical_address);

Logical: 800
Check: 800 < 2000 ✓
Base: 14000
Physical: 800 + 14000 
        = 14800 ✓

Access Granted

Logical: 2500  
Check: 2500 < 2000 ✗
Limit Exceeded!

Protection Fault
Generated

Address Binding

Address binding is the process of mapping program addresses to actual memory locations. Different binding strategies offer various trade-offs between flexibility and performance.

Characteristics:
• Fixed load address
• No relocation possible
• Must recompile to move
• Simple implementation

Example:
Program always loads 
at address 1000

Characteristics:
• Address set at load time
• Cannot move during execution
• Relocatable object code
• Loader performs binding

Example:
Loader places program
at first available space

Characteristics:
• Dynamic address translation
• Can move during execution
• Hardware support required
• Maximum flexibility

Example:
Base register updated
during context switches

Performance Analysis

Understanding the performance implications of swapping and relocation is crucial for system design and optimization.

Swap Out Time:
T_out = T_context_save + T_write_to_disk

Swap In Time:  
T_in = T_read_from_disk + T_context_restore

Total Swap Time:
T_total = T_out + T_in

Example (50MB process, 100MB/s disk):
T_write = T_read = 50MB / 100MB/s = 0.5s
T_context = 1ms (typical)
T_total = 1ms + 500ms + 500ms + 1ms ≈ 1s

System Utilization:
Without swapping: 100% CPU utilization possible
With swapping: Reduced due to swap overhead

Effective CPU Utilization:
U_eff = U_cpu × (1 - swap_fraction × swap_time)

Example:
If 10% of time spent swapping:
U_eff = 100% × (1 - 0.1 × 1.0) = 90%

Memory Usage Regions:

Region 1: Sufficient Memory (0-80% usage)
├─ No swapping needed
├─ Optimal performance
└─ CPU utilization: 95-100%

Region 2: Memory Pressure (80-95% usage)  
├─ Occasional swapping
├─ Some performance degradation
└─ CPU utilization: 70-90%

Region 3: Heavy Swapping (95-100% usage)
├─ Frequent swapping  
├─ Significant slowdown
└─ CPU utilization: 30-60%

Region 4: Thrashing (>100% demand)
├─ Continuous swapping
├─ System nearly unusable
└─ CPU utilization: 5-20%

Practical Examples

System Analysis:

Total Memory Demand: 10 × 800MB = 8GB
Available Memory: 4GB  
Memory Shortage: 8GB - 4GB = 4GB

Swapping Requirements:
Processes in Memory: 4GB ÷ 800MB = 5 processes
Processes on Disk: 10 - 5 = 5 processes

Swap Operation Times:
Process Size: 800MB
Transfer Rate: 100MB/s
Swap Out Time: 800MB ÷ 100MB/s = 8 seconds
Swap In Time: 800MB ÷ 100MB/s = 8 seconds  
Context Switch: 2ms (negligible)

Total Context Switch Time:
If process needs to be swapped in: 8 seconds
If process already in memory: 2ms

Performance Impact:
Average swap frequency: 2 swaps per minute
Time spent swapping: 2 × 8s = 16s per minute
System overhead: 16/60 = 26.7%
Effective performance: 100% - 26.7% = 73.3%

Program Instructions:
100: LOAD  R1, 500    ; Load variable
104: ADD   R1, R2     ; Add numbers  
108: STORE 600, R1    ; Store result
112: HALT

Address Translation:
Logical 500 → Physical 2500 ✓
Logical 600 → Physical 2600 ✓
All accesses within limit (1000) ✓

Same Program Instructions:
100: LOAD  R1, 500    ; Load variable
104: ADD   R1, R2     ; Add numbers
108: STORE 600, R1    ; Store result  
112: HALT

New Address Translation:
Logical 500 → Physical 5500 ✓
Logical 600 → Physical 5600 ✓
Program runs without modification!

Invalid Access Attempt:
Instruction tries to access logical address 1200
Check: 1200 < 1000 (limit) → FALSE
Result: PROTECTION FAULT generated
Action: OS terminates process or handles exception

Hardware Implementation:
if (logical_address >= limit_register) {
    generate_interrupt(PROTECTION_VIOLATION);
    return ERROR;
}
physical_address = logical_address + base_register;
return access_memory(physical_address);

Session Summary