Memory Management

Introduction

Memory management is the OS's job of giving each process the memory it needs, protecting processes from each other, and making efficient use of limited RAM.

Address Binding

A program's addresses are bound to physical memory at one of three times:

• Compile time — produce absolute addresses; inflexible.
• Load time — linker/loader relocates.
• Execution time — done by hardware (MMU) at every memory reference; supports modern virtual memory.

Logical vs Physical Address

Programs see logical (virtual) addresses; the CPU translates them to physical addresses through the Memory Management Unit (MMU). The mapping gives protection and flexibility.

Contiguous Allocation

Each process occupies one contiguous block of memory. Two schemes:

• Single partition — only OS + one user.
• Multiple partitions — fixed or variable sizes for multiple processes.

Allocation strategies for variable partitions:

• First-fit — first hole big enough.
• Best-fit — smallest hole big enough.
• Worst-fit — largest hole.

Fragmentation

External fragmentation — total free memory is enough but in small scattered holes; process cannot fit. Fix with compaction.
Internal fragmentation — space wasted inside an allocated partition because it is slightly larger than needed.

Swapping

To fit more processes than RAM allows, the OS can swap a process to disk (backing store) and bring it back later. Swapping improves utilization at the cost of I/O time.

Paging

Paging eliminates external fragmentation by dividing physical memory into fixed-size frames and logical memory into the same-size pages. A page table maps page numbers to frame numbers.

physical address = frame * page_size + offset

Modern systems use 4 KB pages. Each process has its own page table, giving memory protection.

Translation Lookaside Buffer (TLB)

Accessing the page table on every memory reference is slow. The TLB is a small fast cache of recent translations inside the MMU. A TLB hit is fast; a miss triggers a page-table walk.

Multilevel Page Tables

A 32-bit address with 4 KB pages needs a 1 M-entry page table per process — large. Multilevel page tables split the address into two or more indices, so only parts of the table that are actually used need to be allocated.

Inverted Page Tables

One entry per frame instead of per page, so size grows with physical memory not virtual address space. Lookup uses hashing. Used on some 64-bit architectures.

Segmentation

Segmentation divides a program into variable-sized logical units (code, data, stack, heap). Each segment has a base and limit. Addresses are <segment, offset>. Segmentation matches the programmer's view but reintroduces external fragmentation.

Segmented Paging

Combine: segments are divided into pages, pages are mapped to frames. x86 used this for decades. Best of both worlds.

Protection and Sharing

Page-table entries carry protection bits: read, write, execute, user/kernel. Shared read-only pages (e.g., the C library) save memory across processes.

Summary

Memory management has evolved from simple contiguous allocation to sophisticated paging with multilevel tables, TLBs, and shared segments. The next chapter adds virtual memory — the illusion of more memory than the machine has.

Important Questions

1. Differentiate logical and physical address.
2. Explain first-fit, best-fit, and worst-fit allocation.
3. Differentiate internal and external fragmentation.
4. What is paging? How does it remove external fragmentation?
5. Explain the role of the TLB.
6. Why are multilevel page tables needed?
7. Compare paging and segmentation.
8. How is memory protection enforced with paging?