The Core Problem: Two Views of Memory

Every process in a modern OS believes it has the entire memory to itself. A process might generate an instruction like "load the value at address 4096." But there are 50 other processes running simultaneously, and they all have their own address 4096. How does the system prevent chaos?

The answer is the fundamental separation between two completely different address spaces.

---

Logical Address Space vs. Physical Address Space

Logical Address (Virtual Address)

A logical address is generated by the CPU during the execution of a program. It is the address the program thinks it is accessing — relative to its own private address space, starting from 0.

• Also called a virtual address.
• Every process has its own independent logical address space, starting from address 0.
• The programmer and compiler always work in terms of logical addresses.
• Example: A program's instruction says "read from address 346." This 346 is a logical address.

Physical Address

A physical address is the actual location in the RAM hardware where the data is stored.

• There is exactly one physical address space, shared by all processes.
• The physical address space is managed entirely by the OS and hardware.
• Programs never directly see physical addresses during execution-time binding.

The Key Insight: The CPU generates logical addresses. The RAM only understands physical addresses. Something must translate between them. That something is the Memory Management Unit (MMU).

---

The Memory Management Unit (MMU)

The MMU is a hardware device (typically integrated into the CPU chip) that translates logical addresses to physical addresses at runtime, for every single memory access.

The simplest MMU: the Relocation Register

In the simplest scheme, the MMU uses a single register called the relocation register (also called the base register). The translation is just addition:

$\text{Physical Address} = \text{Logical Address} + \text{Relocation Register value}$

If a process is loaded at physical memory location 14,000, the relocation register is set to 14,000. Every logical address the process generates is offset by 14,000 to produce the correct physical address.

---

The Three Address Binding Times

Before a program can run, its instructions and data — which reference logical addresses — must somehow be connected to physical memory. This connection is called address binding, and it can happen at three different times:

1. Compile-Time Binding

• When: The compiler generates absolute physical memory addresses directly into the machine code.
• Requirement: The exact physical location where the program will be loaded must be known at compile time.
• Problem: If the program must be loaded at a different location, it must be recompiled.
• Modern use: Almost never used. Historical (e.g., MS-DOS .COM files).

2. Load-Time Binding

• When: The compiler generates relocatable code (addresses relative to 0). The loader translates them to absolute physical addresses when the program is loaded into memory.
• Requirement: The starting physical address must be known at load time.
• Problem: Once loaded, the process cannot be moved in memory without reloading it.
• Modern use: Rare in general-purpose OS; used in some embedded systems.

3. Execution-Time Binding (Runtime Binding)

• When: Addresses are kept as logical addresses throughout execution. The MMU hardware translates them to physical addresses on every memory access, at runtime.
• Requirement: Hardware support (MMU with base/limit registers or page tables).
• Benefit: A process can be moved in physical memory at any time — just update the MMU's registers. The process itself never knows.
• Modern use: Used by all modern operating systems (Linux, Windows, macOS).

---

Memory Protection: The Limit Register

With multiple processes in memory, the OS must ensure that no process can access another process's memory. Using only a base register is not enough — a process could generate a very large logical address and overflow into another process's space.

The solution is a second register: the limit register.

• The base register holds the starting physical address of the process.
• The limit register holds the size of the process's logical address space.

Every memory access is validated:

if (logical_address >= limit_register):
    → Trap to OS → "Addressing Error" → Process terminated
else:
    → physical_address = logical_address + base_register
    → Access RAM

This base + limit register pair is set by the OS at every context switch. When the OS switches from Process A to Process B, it loads Process B's base and limit values into the CPU registers. This ensures complete memory isolation between processes.

Contiguous Memory Allocation

In contiguous memory allocation, each process occupies a single, continuous block of physical memory. This is the simplest allocation strategy and forms the foundation for understanding why paging was invented.

---

Single-Partition Allocation

The earliest systems divided RAM into exactly two regions:

1. OS Region: A fixed area in low memory (or high memory) for the operating system kernel.
2. User Region: Everything else, allocated to a single user process at a time.

This model is trivially simple but wastes enormous amounts of memory — only one user process can run at a time.

---

Multiple-Partition Allocation

Modern batch systems keep multiple processes in memory simultaneously (multiprogramming). Memory is divided into partitions, each holding one process.

Fixed Partitioning:

• Memory is divided into a fixed number of partitions at system boot.
• Partitions can be equal size or unequal size.
• A process is loaded into any free partition large enough to hold it.

Variable Partitioning:

• No fixed divisions. The OS tracks which parts of memory are in use and which are free (holes).
• When a process arrives, the OS finds a hole large enough, allocates exactly what's needed, and the rest remains a hole.
• When a process terminates, its memory becomes a hole that may be merged with adjacent holes.

---

Fragmentation: The Core Problem

Fragmentation is wasted memory — memory that exists but cannot be used productively. It comes in two forms:

Internal Fragmentation

Occurs with fixed partitioning. If a 4KB partition holds a 3KB process, 1KB is wasted inside the partition. This wasted space cannot be given to any other process.

[  Process (3KB)  |  WASTED (1KB)  ]  ← 4KB partition

External Fragmentation

Occurs with variable partitioning. After many allocations and deallocations, free memory becomes fragmented into many small, non-contiguous holes. Even if the total free memory is sufficient, no single hole is large enough for a new process.

[ OS | Process A | [hole 2KB] | Process B | [hole 3KB] | Process C | [hole 2KB] ]
                                                                    ↑
              7KB total free, but a 6KB process CANNOT fit anywhere!

The 50% Rule (Knuth's observation): Given N allocated blocks, statistical analysis shows approximately N/2 blocks will be lost to external fragmentation. In other words, one-third of memory may be unusable due to external fragmentation over time.

---

The Three Hole-Selection Strategies

When a process needs memory and there are multiple free holes available, the OS must pick one. Three strategies exist:

1. First Fit

Allocate the first hole that is large enough (scanning from the beginning or from where the last search left off).

• ✅ Fastest — stops at the first suitable hole.
• Generally produces good results in practice.

2. Best Fit

Allocate the smallest hole that is large enough (must search the entire list).

• ❌ Slower — must scan all holes.
• Leaves the smallest possible leftover holes.
• In practice, these tiny leftover holes are often too small to be useful — can actually worsen external fragmentation over time.

3. Worst Fit

Allocate the largest available hole (must search the entire list).

• ❌ Slowest — must scan all holes.
• The idea: leave the largest possible leftover hole, which is more likely to be useful for future processes.
• Generally performs worst in practice for both speed and fragmentation.

Exam note: Both First Fit and Best Fit are better than Worst Fit in terms of speed and storage utilization. First Fit is generally preferred in practice.

PYQ Worked Example: First Fit vs Best Fit [2024 Q8b — 7 marks]

Problem: Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), how would the First-Fit and Best-Fit algorithms place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in order)? Which algorithm makes the most efficient use of memory?

Solution — First Fit:

First Fit result: 3 of 4 processes allocated. 426 KB process cannot fit.

Solution — Best Fit:

Best Fit result: All 4 processes allocated! Best Fit makes more efficient use of memory in this case because it leaves larger holes for future allocations by minimizing wasted space.

Compaction: Solving External Fragmentation

Compaction is the process of shuffling memory contents to consolidate all free space into one large contiguous block.

BEFORE compaction:                   AFTER compaction:
[ OS | A | hole | B | hole | C ]  →  [ OS | A | B | C | [big free hole] ]

• Cost: Requires moving large amounts of data in memory — very slow.
• Requirement: Execution-time binding must be used (so relocated processes' logical addresses still work after moving).
• Modern relevance: Compaction in RAM is largely replaced by paging (the topic of Section 2), which eliminates the need for contiguous physical allocation entirely.