Lab 7: Memory Management

01 Lab overview

Course	COMP 3150 / CMIS 3150 — Operating Systems
Unit	Unit 8 — Main Memory Management
Weight	1.25% of the final grade (1/12 of the 15% laboratory component)
Estimated duration	4–5 hours of hands-on work
Submission	One archive containing the C source files, the Makefile, the output logs, and a short lab report (see § 06)
Environment	Linux VM, `gcc`, `make`, `perf`, `valgrind`, `size`, `objdump`, `readelf`, optional `getconf` for page size

This lab contributes to U8.1 through U8.6, and to course learning outcomes CLO4 and CLO8.

02 Learning objectives

By the end of this laboratory you will be able to

Describe the memory hierarchy and explain why caches exist.
Measure cache behaviour and explain the difference between temporal and spatial locality.
Explain address binding at compile, load, and run time, and the role of the MMU and relocation registers.
Explain dynamic loading and dynamic linking, and observe their effect on a program's memory footprint.
Implement and compare first-fit, best-fit, and worst-fit contiguous allocation.
Quantify internal and external fragmentation and explain how compaction mitigates external fragmentation.
Implement a segmented memory manager with per-segment protection and demonstrate a segmentation fault caused by an out-of-bounds access.

03 Background

3.1 The memory hierarchy

Memory is organised in a hierarchy that trades capacity for latency: registers (a few hundred bytes, sub-nanosecond), L1 cache (tens of kilobytes, ~1 ns), L2 cache (hundreds of kilobytes, ~3 ns), L3 cache (tens of megabytes, ~10 ns), main memory (gigabytes, ~100 ns), and secondary storage (terabytes, milliseconds). The purpose of the hierarchy is to give the illusion of a large, fast memory at the cost of a small, fast one: programs are written as if all their data is in main memory, and the cache hierarchy transparently keeps the most-used data in the fastest level. This works because programs exhibit temporal locality (a location accessed once is likely to be accessed again soon) and spatial locality (a location near an accessed one is likely to be accessed soon).

3.2 Address binding

A program's instructions and data use addresses. The time at which those addresses are bound to physical addresses determines the flexibility of the memory manager:

Compile time. The compiler emits absolute addresses. The program must be loaded at a known address. This is what a raw binary does.
Load time. The compiler emits relocatable addresses, and the loader fixes them up when the program is loaded. The base address is fixed for the lifetime of the process.
Execution time. The compiler emits relocatable addresses, and the MMU translates them on every access. The process can be moved during execution, which is what makes paging and swapping possible.

Modern systems use execution-time binding. The MMU uses a base register (for contiguous allocation) or a page table (for paging) to translate a logical address to a physical one.

3.3 Contiguous allocation

In the simplest model, each process occupies a single contiguous block of physical memory. The memory manager maintains a list of free and allocated holes and satisfies each request by choosing a hole:

First-fit: the first hole large enough. Fast; tends to leave small holes near the start of memory.
Best-fit: the smallest hole large enough. Leaves the smallest leftover; tends to produce many tiny unusable holes.
Worst-fit: the largest hole. Leaves the largest leftover; tends to produce fewer but larger holes.

3.4 Fragmentation

Internal fragmentation is wasted space inside an allocated block: the block is larger than the request, and the difference is unusable. External fragmentation is wasted space between allocated blocks: there is enough total free memory to satisfy a request, but no single hole is large enough. External fragmentation is mitigated by compaction (moving all allocated blocks to one end of memory to consolidate the free space), which is possible only if address binding is done at execution time.

3.5 Segmentation

Segmentation is a memory-management scheme in which a program is divided into logical units — code, data, stack, and so on — each called a segment. A logical address is a pair ⟨segment number, offset⟩. The segment table maps each segment number to a base and a limit. The MMU checks that the offset is less than the limit; if not, it raises a trap. The scheme gives natural protection and supports sharing at the segment level.

04 Guided activities

Activity 4.1 — Cache behaviour and locality

Create the lab directory:

mkdir -p ~/comp3150/lab7 && cd ~/comp3150/lab7

Write locality.c that allocates a 64 MB array and visits it (a) row-major and (b) column-major. Use clock_gettime(CLOCK_MONOTONIC) to time both traversals.
Run the program and record the times. Explain the difference: both traversals touch the same number of elements, yet one is dramatically faster. Compute the effective bandwidth for each and compare to the theoretical main-memory bandwidth of the VM.
Use perf stat -e cache-references,cache-misses,L1-dcache-loads,L1-dcache-load-misses ./locality to measure the cache behaviour of both traversals. Report the miss rates.
Repeat with a 256 KB array (fits in L2) and a 4 KB array (fits in L1). How does the traversal order affect the time when the array fits entirely in cache? Explain.

Activity 4.2 — Address binding

Write a one-line C program that prints the address of a global variable, a static variable, and a local variable. Compile it twice — once without optimisation and once with -O2 — and record the addresses.
Use nm on the object file and on the final executable to inspect the symbol addresses. Compare the addresses in the object file (relocatable) to the addresses in the executable (absolute).
Run the program twice in a row. Observe the addresses. On a modern Linux system, ASLR (address-space layout randomisation) causes the addresses of the data segment, stack, and heap to differ between runs; the text segment may be at a fixed address if the binary is non-PIE. Disable ASLR with setarch $(uname -m) -R ./program and confirm the addresses become stable.
Use readelf -l ./program to inspect the program headers. Identify the text, data, and BSS segments and their virtual addresses.
Use size ./program to report the size of the text, data, and BSS sections. Explain the difference between a variable in the BSS (uninitialised, zero on load) and the same variable in the data section (initialised).

Activity 4.3 — Contiguous allocation algorithms

Write allocator.c that maintains a free list of holes (start address, size). It supports three algorithms, selectable by a command-line flag: --first, --best, --worst. Each request is a triple ⟨pid, size, action⟩ where action is allocate or release.
Feed the allocator a workload with alternating allocations and releases. Track and report: total allocated bytes, total free bytes, number of holes, largest hole, and external fragmentation (1 − largest_hole / total_free).
Run the same workload under all three algorithms and compare the resulting fragmentation curves. Which algorithm produces the fewest holes? Which produces the largest largest-hole? Which is fastest?
Extend the allocator to support compaction: on every release, move all allocated blocks to one end of memory and consolidate the free space. Measure the cost of compaction per release and the improvement in the largest hole.

Activity 4.4 — Internal fragmentation with fixed-size blocks

Modify allocator.c to allocate memory in fixed-size blocks (for example, 4 KB). Every request is rounded up to the next multiple of the block size.
Run a workload with request sizes drawn from a realistic distribution (for example, 80% of requests between 100 bytes and 2 KB, 20% between 2 KB and 20 KB). Measure the internal fragmentation: total bytes allocated minus total bytes requested, divided by total bytes allocated.
Vary the block size (256 B, 1 KB, 4 KB, 16 KB). Plot the internal fragmentation as a function of block size. Explain the trade-off: small blocks waste less per allocation but require more bookkeeping and produce more external fragmentation.

Activity 4.5 — Segmented memory manager

Write segment.c that implements a segment table with n entries. Each entry has a base, a limit, and a protection field (read, write, execute). The program accepts a logical address ⟨segment, offset⟩ and translates it to a physical address, checking the limit and the protection bits.
Demonstrate a successful translation, then a translation that violates the limit (raises a trap), then a translation that violates the protection bits (raises a different trap).
Extend the program to support segment sharing: two processes share a code segment but have private data and stack segments. Show that a write to the shared code segment is denied.
Draw the segment tables for both processes. Explain why segmentation gives natural protection and sharing without requiring the two processes to be related.

05 Exercises

Memory layout of a real program. Write a program that allocates memory from the heap, recurses a few frames deep, and declares both initialised and uninitialised globals. Use /proc/<pid>/maps to inspect the process's memory layout: text, data, BSS, heap, stack, and shared libraries. Produce a diagram with the actual addresses and sizes. Explain what each region contains.
Custom allocator. Implement my_malloc and my_free on top of a fixed-size arena using a free list with best-fit placement and coalescing of adjacent free blocks. Compare its performance and memory overhead with the system malloc on a synthetic workload. Explain when a custom allocator is worth writing.
Fragmentation simulator. Build a simulator that models memory as M bytes divided into fixed-size pages (say 1 MB of 4 KB pages). A workload issues allocation and free requests of variable sizes. Pages are allocated non-contiguously, so there is no external fragmentation, but internal fragmentation is the sum of the wasted portions of partially filled pages. Plot internal fragmentation against page size, and explain why paging is preferred to contiguous allocation in general-purpose systems.
Compaction cost. Measure the cost of compaction in the allocator from Activity 4.3 as a function of total allocated bytes. Use memcpy to move blocks. Estimate the throughput of compaction in bytes per second and explain why compaction is rarely performed in practice, even though it eliminates external fragmentation.
TLB behaviour with different page sizes. On a Linux system, the default page size is 4 KB. Huge pages (2 MB or 1 GB) are available via mmap with the MAP_HUGETLB flag. Write a program that allocates a large array and traverses it (a) with 4 KB pages and (b) with 2 MB huge pages. Use perf stat to measure the dTLB miss rate in each case. Explain the difference in terms of TLB coverage.
Segmentation vs. paging. Write a short essay (1–2 pages) comparing segmentation and paging as memory-management schemes. Cover the granularity of protection, the ability to share, the cost of the address translation, and the reason x86-64 uses paging with minimal segmentation support.

06 Deliverables

Submit a single archive named lab7-<lastname>-<studentnumber>.tar.gz containing:

locality.c — Activity 4.1.
binding.c — Activity 4.2 (the one-line program and a shell script that runs it under different configurations).
allocator.c — Activity 4.3 with all three algorithms and compaction support.
fixed_blocks.c — Activity 4.4.
segment.c — Activity 4.5.
my_malloc.c — Exercise 2.
The Makefile with one target per program and a clean target.
outputs.txt — the output logs of all programs with the commands that produced them.
perf/ — the perf stat output files for the cache and TLB experiments.
report.md (or report.pdf) — the lab report described below.

Lab report

The report should be 5–7 pages (excluding code) and contain:

Locality and cache. The timing and cache-miss data for the row-major and column-major traversals, and an explanation in terms of spatial and temporal locality.
Address binding. The addresses observed under different compilation options and with ASLR on and off, and the interpretation of readelf and size output.
Allocation algorithms. The fragmentation curves for first-fit, best-fit, and worst-fit on the same workload, with a discussion of which algorithm is best for which workload pattern and why.
Fragmentation. Quantitative results for internal fragmentation as a function of block size and for external fragmentation as a function of algorithm, including the compaction cost measurements.
Segmentation. The segment tables, the trap demonstrations, and a discussion of why segmentation provides protection more naturally than paging.
Reflection. A discussion of why general-purpose systems chose paging over contiguous allocation and segmentation, and how the hardware (MMU, TLB, page-table walker) implements the translation efficiently.

07 Grading rubric

Lab 7 grading rubric (100 points)
Criterion	Points	CLOs	Exemplary (90–100%)	Proficient (80–89%)	Developing (70–79%)
Locality and cache experiments	20	CLO4	Measurements are rigorous; the analysis explains the miss rates quantitatively.	Measurements are adequate; analysis mostly correct.	Measurements lack methodology or the analysis is superficial.
Address binding and layout	20	CLO4, CLO6	All three binding times are demonstrated; the memory layout is diagrammed accurately from `/proc/maps`.	Binding times demonstrated; layout mostly correct.	Binding or layout analysis incomplete.
Allocation algorithms	25	CLO4, CLO8	All three algorithms correct; fragmentation analysis is quantitative and comparative.	Algorithms correct; analysis adequate.	Algorithms have bugs or analysis is missing.
Fragmentation and compaction	20	CLO4	Internal and external fragmentation are measured separately; compaction cost is quantified.	Measurements present; analysis partially complete.	Measurements or analysis incomplete.
Segmentation	15	CLO4, CLO8	Segment table and protection checks are correct; trap demonstrations are clear.	Implementation correct; demonstrations brief.	Implementation incomplete or incorrect.

Late submission penalty: 10% per day, up to a maximum of three days, after which the lab is accepted only with documented extenuating circumstances.

08 Knowledge check

Check your understanding

Question 1

Why does the memory hierarchy work? Explain both kinds of locality and give an example of each.

Show answer

The hierarchy works because programs exhibit locality, which means that at any moment a program accesses only a small fraction of its address space, and that fraction changes slowly. Temporal locality: a location accessed recently is likely to be accessed again soon — a loop counter, a hot variable, an instruction inside a tight loop. Spatial locality: a location near one that was just accessed is likely to be accessed soon — the next element of an array, the next instruction in sequence, the fields of a struct. Because of locality, the cache hierarchy can keep the working set in the fast levels and satisfy most accesses without going to main memory.

Question 2

A 4 KB page table entry is 8 bytes. How large is a single-level page table for a 64-bit address space with a 4 KB page size? Why is this a problem?

Show answer

A 4 KB page size means 2¹² bytes per page, so the offset is 12 bits and the page number is 64 − 12 = 52 bits. The page table has 2⁵² entries. At 8 bytes each, that is 2⁵⁵ bytes = 32 PiB per process. This is impossibly large: it exceeds the address space of the machine itself and would consume enormous memory for every process, most of which is unused. This is the motivation for multi-level page tables, which allocate only the parts of the table that are actually used, and for inverted page tables, which store one entry per physical frame instead of one per virtual page.

Question 3

Explain the difference between internal and external fragmentation. Which is eliminated by paging, and which by compaction?

Show answer

Internal fragmentation is wasted space inside an allocated block: the block is larger than the request and the difference is unusable. External fragmentation is wasted space between allocated blocks: there is enough total free memory, but no single contiguous hole is large enough. Paging eliminates external fragmentation because any free frame can satisfy any page request — physical memory need not be contiguous. It does not eliminate internal fragmentation: the last page of a process is partly unused. Compaction eliminates external fragmentation by moving allocated blocks together, but it requires execution-time address binding (or a way to relocate a process) and it is expensive. Neither scheme eliminates internal fragmentation; that is the price of fixed-size allocation units.

Question 4

First-fit is generally faster than best-fit, yet best-fit often produces better memory utilisation. Explain the trade-off.

Show answer

First-fit scans the free list from the beginning and takes the first hole large enough. It can stop as soon as it finds a fit, so it is O(1) in the average case. Best-fit must scan the entire free list to find the smallest hole large enough, so it is O(n) in the number of holes. The utilisation difference is subtler than it first appears. Best-fit leaves the smallest leftover, which sounds good, but small leftovers are often too small to be useful and accumulate as unusable external fragmentation. First-fit, by contrast, tends to split large holes into medium-sized ones, which are more likely to be useful. Empirical studies show that first-fit and best-fit are usually comparable in utilisation, and first-fit is faster. Worst-fit is generally the worst of the three.

Question 5

Why does segmentation provide protection more naturally than paging?

Show answer

A segment is a logical unit — code, data, stack, a module — and different segments have naturally different access rights. The code segment is read-only and executable; the data segment is read-write but not executable; the stack is read-write. The segment table entry can therefore carry protection bits that apply to the whole segment, and the MMU can check them on every access without any additional bookkeeping. A page, by contrast, is a fixed-size physical unit with no inherent semantic meaning; the same page may contain both code and data, and the same logical object may span many pages. Protection therefore has to be applied per page, and the operating system must ensure that all pages of a given object receive the correct protection. The result is that segmentation gives coarser but more natural protection, while paging gives finer-grained but less semantically meaningful protection. Modern systems use paging with per-page permission bits, which is adequate for most purposes but requires the loader and the MMU to cooperate.

09 References

Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapters 9 and 10.
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 13–16.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3.
Denning, P. J. Virtual Memory. ACM Computing Surveys, 1970.
Knuth, D. E. The Art of Computer Programming, Volume 1, Section 2.5 (dynamic memory allocation).
Linux man-pages: man 2 mmap, man 2 brk, man 5 proc, man 1 perf, man 3 malloc.
Drepper, U. What Every Programmer Should Know About Memory. Red Hat, 2007.