This homework assignment is about managing memory in constrained systems! You are going to be programming the memory management layer of an operating system: contiguous allocation strategies and paging with address translation!
Over-dough-se Pizza is expanding to three new franchise locations, each running on a different vintage machine. Your memory management code must work across all of them ā from 256 bytes on an 8-bit "Relic" to 4 GB on a 32-bit system. The sections below give you direct and indirect help with organizing your thoughts about generics, collections, traits, and the data structures you will need to implement allocation and page tables in Rust.
In "The Rust Language Book" read:
Optionally for help with the homework:
(The optional chapters cover trait objects and advanced generics that may help you understand how the page table trait and machine configurations work under the hood)
While it's not one of your required materials, the Rust by Example docs are associated with the Rust Language Book and are a great resource for understanding the concepts in the book in a more direct programmatic way. You should go through all of it but for now, Read section 14: Generics and Section 19: Std Library Types (particularly HashMap and Vec, which back the two page table implementations).
Read Chapter 4: Memory Management (Page 93-148) from our course textbook. It provides a thorough overview of contiguous allocation, fragmentation, paging, and address translation ā all of which are directly implemented in this assignment.
Operating Systems and Middleware: Supporting Controlled Interaction
This programming assignment is about implementing memory management strategies (contiguous allocation and paging) in Rust!
Your repository will contain the following files:
CMSI-3510-HW4/
āāā .gitignore
āāā hot_and_not_ready_yet/
ā āāā Cargo.toml
ā āāā Cargo.lock
ā āāā src/
ā āāā allocator.rs
ā āāā array_page_table.rs
ā āāā best_fit.rs
ā āāā component.rs
ā āāā counter.rs
ā āāā first_fit.rs
ā āāā lib.rs
ā āāā machine.rs
ā āāā main.rs
ā āāā mmu.rs
ā āāā naive_page_table.rs
ā āāā page_table.rs
ā āāā profiler.rs
ā āāā visualization.rs
āāā README.md
Need a refresher on how to interact with the HW for this course? Watch the helper video posted to Zoom via the link below!
You can find the GitHub Classroom assignment link and the Brightspace turn in link using the buttons at the top of this section.
In this optional section you'll go further with the memory-management ideas from HW4 by building a real allocator, a real garbage collector, or a real virtual-memory simulator from scratch. Memory management is one of the richest sub-fields of systems programming with a thriving "build your own" tutorial scene ā this optional plugs you straight into it.
Pick one of the project ideas below (or pitch your own!), follow its starter article to get oriented, and then build it out in your own empty repo.
Bump (arena) allocator. The simplest non-trivial allocator: hand out memory by incrementing a pointer, free everything at once. A great way to internalize what #[global_allocator] actually plugs into.
Slab / fixed-size pool allocator. Allocate fixed-size objects from a pre-carved pool. The same idea backs Linux's kmem_cache_alloc. Compare its fragmentation behavior to your bump allocator and to first-fit/best-fit from HW4.
Mark-and-sweep garbage collector. Build a tiny GC for a toy interpreter (or for a stand-alone object graph). The classic "build your own GC" project ā short, deep, and a great interview talking point.
Virtual memory simulator with page replacement. Extend HW4's page-table abstraction with a finite frame pool and implement at least two page-replacement algorithms (e.g., FIFO, LRU, Clock, Aging). Run the same access trace through each and compare hit rates.
Memory profiler / leak detector. Wrap the system allocator with a #[global_allocator] shim that records every allocation and deallocation, then dump a report on program exit showing leaks and the largest live allocations.
Bring your own. Anything where the central question is "how do we hand out, track, or reclaim memory?" works. Pitch it in your README.
Whichever idea you pick, your repo must include:
Vec).cargo test. At least one of those tests should exercise an interesting edge case (out-of-memory, fragmentation, double-free detection, page eviction under pressure, etc.).README.md explaining what you built, which starter article you used, and a brief write-up of the design tradeoffs you made.I have made an empty Github assignment for you to pull and create your Rust project from scratch (This is out of convenience so that I can use Github classroom to collate all your projects rather than go through being added to all the repos). Feel free to architect your project as you choose.
Since the repository is private, feel free after you are done to copy it over into a public repository to show off on your Github!
Earning points in this optional is not as rigid since you may pick your own project. With that said, to earn full points you must:
README.md that names your starter article, describes what you built, and includes a short write-up of the design tradeoffs (why this allocator/algorithm, what it's good and bad at).cargo test, at least one of which exercises an interesting edge case.Below is the button that links to the Github Optional Assignment repository. The Brightspace submission link is at the top of this section.