COMP 3150Operating Systems

Module 3 · Unit 8 of 2

Main Memory Management

How the operating system gives each process a place in physical memory. The memory hierarchy, when addresses are bound, how programs are loaded, the classical contiguous-allocation schemes, the fragmentation problems they create, and the segmentation abstraction that follows.

Start Lesson 8.1 See all lessons
6 lessons Lab 7 · Memory management CLO4 ≈ 1.5 weeks at recommended pace
The memory hierarchy and the fragmentation problem On the left, a stacked hierarchy from registers down to disk, showing typical access latencies. On the right, a physical memory layout illustrating external fragmentation — allocated and free holes scattered through memory. MEMORY HIERARCHY Registers ~1 cycle L1 cache ~4 cycles L2 cache ~12 cycles L3 cache ~40 cycles Main memory ~200 cycles SSD ~50k cycles Magnetic disk ~10M cycles Smaller · faster · more expensive ↓ Larger · slower · cheaper EXTERNAL FRAGMENTATION Process A · 32 KB free · 8 KB Process B · 48 KB free · 4 KB Process C · 44 KB free · 12 KB Process D · 36 KB free · 8 KB + 4 KB + 16 KB total 28 KB, but not contiguous Enough total free memory for a 24 KB process, but no single contiguous hole large enough.

Module 3 · Unit 8

Main Memory Management

The physical side of the memory abstraction. This unit establishes the hierarchy, examines when addresses are bound to memory locations, and surveys the classical schemes for placing processes in physical memory — along with the fragmentation they inevitably produce.

01 Unit learning outcomes

Upon completion of this unit you will be able to

  • U8.1 — Describe the memory hierarchy and its performance characteristics.
  • U8.2 — Explain address binding and the timing of address resolution.
  • U8.3 — Apply dynamic loading and linking.
  • U8.4 — Analyse contiguous allocation strategies.
  • U8.5 — Evaluate fragmentation and its mitigations.
  • U8.6 — Apply segmentation as an abstraction.

This unit addresses course learning outcome CLO4 — explain memory and virtual-memory management techniques.

02 Lessons in this unit

The unit moves from hardware characteristics to software abstractions. Lessons 8.1–8.3 establish the foundation; Lessons 8.4–8.6 examine the classical allocation schemes and the abstraction — segmentation — that motivated the virtual-memory design in Unit 9.

Lesson 8.1

Memory Hierarchy

Registers through disk: latency, capacity, cost, and the locality that makes the hierarchy work.

 Lesson 8.2

Address Binding

Compile time, load time, and execution time binding — and why only the last supports relocation.

 Lesson 8.3

Dynamic Loading

Loading routines on demand, dynamic linking, shared libraries, and the trade-offs they impose.

 Lesson 8.4

Contiguous Allocation

Fixed and variable partitions, placement strategies (first fit, best fit, worst fit), and their costs.

 Lesson 8.5

Fragmentation

Internal and external fragmentation, compaction, paging as a fix, and how to quantify the waste.

 Lesson 8.6

Segmentation

The programmer-visible model: segments, base and limit registers, and the transition to paging.

03 What you will learn, lesson by lesson

8.1 Memory Hierarchy

  • Describe hierarchy levels.
  • Explain locality of reference.
  • Analyse access-time differences.
  • Evaluate cache organisation.
  • Relate hierarchy to OS design.

8.2 Address Binding

  • Distinguish logical and physical addresses.
  • Explain compile-time binding.
  • Explain load-time binding.
  • Explain execution-time binding.
  • Analyse relocatability.

8.3 Dynamic Loading

  • Define dynamic loading.
  • Explain dynamic linking.
  • Describe shared libraries.
  • Analyse memory savings.
  • Evaluate runtime costs.

8.4 Contiguous Allocation

  • Describe fixed partitioning.
  • Describe variable partitioning.
  • Apply first fit.
  • Apply best fit and worst fit.
  • Compare placement costs.

8.5 Fragmentation

  • Define internal fragmentation.
  • Define external fragmentation.
  • Analyse the 50% rule.
  • Apply compaction.
  • Evaluate paging as a fix.

8.6 Segmentation

  • Define segments.
  • Explain segment tables.
  • Apply base and limit registers.
  • Analyse segment addressing.
  • Compare segmentation and paging.

04 Worked example

A first-fit allocation trace to make the placement policies concrete.

Placing processes in a fragmented memory

Suppose free memory is divided into holes of the following sizes, in address order:

Hole 1: 100 KB
Hole 2: 500 KB
Hole 3: 200 KB
Hole 4: 300 KB
Hole 5: 600 KB

A sequence of requests arrives: 212 KB, 417 KB, 112 KB, 426 KB.

First fit — allocate the first hole large enough:

  1. 212 KB → Hole 2 (500 KB). Remaining: 288 KB.
  2. 417 KB → Hole 5 (600 KB). Remaining: 183 KB.
  3. 112 KB → Hole 2 (288 KB). Remaining: 176 KB.
  4. 426 KB → no hole large enough. Blocked.

Best fit — allocate the smallest hole large enough:

  1. 212 KB → Hole 4 (300 KB). Remaining: 88 KB.
  2. 417 KB → Hole 5 (600 KB). Remaining: 183 KB.
  3. 112 KB → Hole 3 (200 KB). Remaining: 88 KB.
  4. 426 KB → no hole large enough. Blocked.

Worst fit — allocate the largest hole:

  1. 212 KB → Hole 5 (600 KB). Remaining: 388 KB.
  2. 417 KB → Hole 2 (500 KB). Remaining: 83 KB.
  3. 112 KB → Hole 5 (388 KB). Remaining: 276 KB.
  4. 426 KB → Blocked (largest hole is 276 KB).

All three policies fail in this trace, because no policy can overcome the fundamental limit: the total free memory (1700 KB minus what is allocated) is enough, but the free space is scattered. This is external fragmentation, and paging — the subject of Unit 9 — is the standard fix.

05 Required reading

  • Operating System Concepts — Chapter 9, Sections 9.1–9.4 (Main Memory). This is the primary reference for the classical material.
  • OSTEP — Chapter 12, Dialogue on Memory Virtualization, and Chapter 13, The Abstraction: Address Spaces. OSTEP's framing of the address-space abstraction is a useful complement to the classical text.
  • Intel Software Developer's Manual, Volume 3A, Chapter 3 (Protected Mode Memory Management), for the segmentation details on x86.

Read for the framing, not the implementation

The classical material is written for an era of contiguous allocation that few modern systems use directly. Read it for the framing — how the address-space problem is posed, and what trade-offs each scheme makes — rather than as a description of what your Linux machine does today.

06 Unit discussion

Discussion prompt

The classical allocation schemes — first fit, best fit, worst fit — were designed for a world where processes occupied contiguous physical memory. Modern systems use paging and virtual memory instead, and do not place processes into physical memory contiguously at all.

Yet the placement-policy problem reappears at higher levels of the stack: page-frame allocation, slab allocation in the kernel, heap allocators in the C library, and even job scheduling in container orchestrators. Pick one such modern context and argue whether the classical policies still offer useful guidance, or whether the problem has changed fundamentally.

Post your response to the Unit 8 discussion forum and reply to at least two classmates. Supports CLO4 and CLO7.

07 Laboratory connection

Lab 7 — Memory Management is completed at the end of this unit. It asks you to implement the classical placement policies, measure fragmentation on a synthetic workload, and compare their effectiveness.

Lab 7 coverage
Lesson Lab 7 exercise
8.1 Memory HierarchyMeasure access latencies with lmbench or cachebench
8.2 Address BindingInspect a running process's memory map with /proc/PID/maps
8.3 Dynamic LoadingCompare a statically linked and dynamically linked binary with ldd
8.4 Contiguous AllocationImplement first fit, best fit, worst fit in a simulator
8.5 FragmentationMeasure fragmentation as a function of allocation pattern
8.6 SegmentationObserve segment registers on x86-64 (in 32-bit mode)

08 Knowledge check & quiz

Quick check before you begin

Question 1

Why is the memory hierarchy necessary? What physical constraint makes a single-level memory impractical?

Show answer
Fast memory is expensive. SRAM — the technology behind caches — is several times more expensive per bit than DRAM, and DRAM is much more expensive than disk. A machine with a large, single-level memory built from the fastest technology would be prohibitively expensive. The hierarchy exploits locality of reference: most accesses hit a small working set that fits in the fast levels, so the average access time is close to the fast-level latency while the capacity is close to the slow-level capacity.

Question 2

Distinguish logical from physical addresses, and explain why the distinction matters.

Show answer
A logical address (also called virtual) is the address a program uses — the one generated by the CPU when executing the program's instructions. A physical address is the actual address on the memory bus. The distinction matters because it allows the operating system to move processes around in physical memory without the programs knowing, to give each process an isolated address space, and to use virtual-memory techniques. Without this separation, relocation would require rewriting a program's addresses every time it moved.

Question 3

A system has 128 MB of free memory, but only 48 MB in any single contiguous block. A program needs 64 MB. What is the problem and what is the classical fix?

Show answer
This is external fragmentation: the total free memory is sufficient, but no single hole is large enough. The classical fix is compaction — moving processes in memory so that all free space becomes contiguous. Compaction requires execution-time address binding so that the processes can be relocated. The modern fix, which avoids compaction entirely, is paging: allocate the program's memory in fixed-size chunks that need not be contiguous.

After completing all six lessons, take the Unit 8 quiz in the LMS. It covers the hierarchy, address binding, dynamic loading, allocation policies, fragmentation, and segmentation.

👤