Discussion 8: Measuring Fragmentation

01 Overview

Course	COMP 3150 / CMIS 3150 — Operating Systems
Unit	Unit 8 — Main Memory Management
Weight	Part of the 5% participation grade (each discussion is worth approximately 0.4% of the final grade)
Opens	Monday of Week 8
Initial post due	Thursday of Week 8, 23:59
Peer replies due	Sunday of Week 8, 23:59
Format	One initial post (500–700 words, including a table or a plot of measured results) and at least two substantive peer replies (150–250 words each)
CLOs assessed	CLO4, CLO6, CLO8

02 Learning outcomes addressed

By participating in this discussion you will

Describe the memory hierarchy and explain the role of caches and locality (U8.1).
Explain address binding at compile, load, and run time (U8.2).
Implement and evaluate the contiguous allocation strategies — first-fit, best-fit, and worst-fit (U8.4).
Quantify internal and external fragmentation and explain how compaction mitigates external fragmentation (U8.5).
Evaluate the trade-offs of segmentation as an alternative to contiguous allocation (U8.6).

This discussion assesses CLO4 (explain memory-management techniques), CLO6 (apply Linux systems programming and tools), and CLO8 (design and implement OS-related components).

03 Discussion prompt

Your task

Choose a memory-allocation scenario. You have two options:
- Simulate it. Use the allocator you built in Lab 7 or write a new one. Generate a workload with a realistic distribution of allocation and free requests — for example, 80% of requests between 100 bytes and 2 KB and 20% between 2 KB and 20 KB, with a lifetime distribution that produces churn. Run at least 100,000 operations.
- Measure it. Choose a real workload whose memory behaviour you can observe. Examples: a compiler building a large project, a database running a query, a Python interpreter executing a script. Use /proc/<pid>/smaps, valgrind --tool=massif, or heaptrack to record the allocation pattern, then re-run it against your allocator's statistics.
Run the workload under two strategies. Choose two of:
- Contiguous first-fit.
- Contiguous best-fit.
- Contiguous worst-fit.
- Fixed-size block allocator with a configurable block size.
- Segregated free-list allocator with size classes (as used by real allocators such as jemalloc and tcmalloc).
Measure the fragmentation. For each strategy, report:
- Internal fragmentation: the total bytes allocated minus the total bytes requested, divided by the total bytes allocated.
- External fragmentation: the number and size distribution of free holes, and the ratio of the largest free hole to the total free memory. (A large ratio means the free space is contiguous; a small ratio means it is scattered.)
- Maximum simultaneous allocation: the highest total bytes held at any instant, which gives the minimum memory the workload could have used with a perfect allocator.
Interpret the results. Which strategy produced less internal fragmentation? Which produced less external fragmentation? Which would you choose for this workload, and why? Your answer should connect the numbers to the properties of the strategies:
- First-fit tends to leave medium-sized holes near the start of memory.
- Best-fit leaves the smallest leftover at each allocation, which sounds good but tends to produce many tiny unusable holes.
- Worst-fit leaves the largest leftover, but fragments large holes quickly.
- Fixed-size blocks eliminate external fragmentation but produce internal fragmentation proportional to the block size.
- Segregated free lists are used by real allocators because they trade a small amount of internal fragmentation for much lower external fragmentation and much lower lookup cost.
Discuss compaction. External fragmentation can be eliminated by compaction — moving all allocated blocks to one end of memory and consolidating the free space. Explain why compaction is rarely used in modern general-purpose systems, even though it eliminates the problem. Address the cost of moving live data and the conditions under which compaction is feasible (execution-time address binding, a quiescent point where no thread is accessing the memory being moved).

Your post should be 500–700 words. Include the measurement table. State the workload, the strategies, and the parameters (number of operations, request-size distribution) so that the experiment can be reproduced.

04 Suggested experiments and tools

4.1 Simulated workload

The simplest approach is to write a small simulator that maintains a list of free and allocated blocks and processes a synthetic sequence of allocate and free operations. Use the allocator from Lab 7 as a starting point. Record the state after every operation, and compute the fragmentation metrics periodically (for example, every 1,000 operations).

4.2 Real workload measurement

If you prefer to measure a real workload, use one of the following tools to capture the allocation pattern:

valgrind --tool=massif — records the heap profile over time. The output can be visualised with ms_print.
heaptrack — a heap profiler that records every allocation and free, with backtraces. It produces a trace that can be analysed with the heaptrack_gui tool or with a script.
perf record -e syscalls:sys_enter_mmap — traces mmap calls (used for large allocations in glibc).

Once you have the allocation trace, you can replay it against your allocator and measure the fragmentation it would produce. This is more work than the simulated approach but gives you a real workload to reason about.

4.3 Metrics to report

For each strategy and workload, report the following in a table:

Total operations (allocate + free).
Peak bytes held — the maximum simultaneous allocation.
Internal fragmentation — bytes allocated minus bytes requested, over bytes allocated (as a percentage).
External fragmentation — largest free hole over total free memory (a ratio between 0 and 1).
Number of holes — the count of free blocks at the end of the run.
Mean allocation cost — the average number of free-list entries examined per request (a proxy for the lookup cost of the strategy).

4.4 Interpretation

When you interpret the results, remember the following:

Internal and external fragmentation are not independent. Fixed-size blocks eliminate external fragmentation but produce internal fragmentation. Contiguous allocators do the reverse.
The best strategy depends on the workload's request-size distribution and lifetime distribution. A workload with a small number of size classes is well served by segregated free lists; a workload with a wide range of sizes and long-lived allocations may do better with a careful contiguous allocator.
The metric that matters in practice is often not the theoretical fragmentation but the actual peak memory usage and the latency of allocation. A strategy that produces slightly more fragmentation but allocates much faster is often the right choice.

05 Grading rubric

The discussion is marked out of 100 points. The criteria and their weights are given below.

Discussion 8 grading rubric — weights
Criterion	Weight
Post quality (experiment, metrics, interpretation)	40%
Peer response quality	30%
Engagement and timeliness	20%
Netiquette and clarity	10%

5.1 Post quality (40 points)

Level	Descriptor
Exemplary (90–100%)	A clear workload and a reproducible experiment. Both strategies are run with the same workload. The fragmentation metrics are computed correctly and presented in a table. The interpretation connects the numbers to the properties of the strategies, and it addresses the trade-off between internal and external fragmentation. Compaction is discussed with an understanding of its cost. Sources are cited.
Proficient (80–89%)	A clear workload. Both strategies are run. The metrics are computed correctly and presented. The interpretation is sound but does not fully connect the numbers to the strategies' properties. Compaction is mentioned but not analysed.
Developing (70–79%)	A workload is described but the experiment is incomplete (only one strategy is run, or the metrics are missing). The interpretation is superficial. Compaction is not discussed.
Beginning (60–69%)	The experiment is not run, or the results are not reported. The post is a theoretical description of fragmentation without measurement.
Not demonstrated (<60%)	The post is missing, off-topic, or a restatement of the prompt without any measurement.

5.2 Peer response quality (30 points)

The descriptors are the same as for Discussion 3. An exemplary reply might:

Suggest a workload that would reverse the classmate's conclusion (for example, a workload with a very different size distribution).
Compare the classmate's results with their own and explain the difference in terms of the workloads.
Propose a third strategy (for example, a segregated free list) and predict how it would fare on the classmate's workload.

5.3 Engagement and timeliness (20 points)

The descriptors are the same as for Discussion 1.

5.4 Netiquette and clarity (10 points)

The descriptors are the same as for Discussion 1.

06 Resources

Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapters 9–10 (Main Memory and Virtual Memory).
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 13–16 (Address Spaces, Memory API, Address Translation, Segmentation).
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3 (Memory Management).
Knuth, D. E. The Art of Computer Programming, Volume 1, Section 2.5 (Dynamic Storage Allocation).
Wilson, P. R., Johnstone, M. S., Neely, M., & Boles, D. Dynamic Storage Allocation: A Survey and Critical Review. International Workshop on Memory Management, 1995.
Evans, J. A Scalable Concurrent Memory Allocator for Large-Scale Multicore Systems. PhD thesis, University of Massachusetts Amherst, 2006 (the design of jemalloc).
Linux man-pages: man 3 malloc, man 5 proc (/proc/<pid>/smaps), man 1 valgrind (Massif section).
Heaptrack documentation: github.com/KDE/heaptrack.