UMBC CMSC421 UMBC | CSEE | CMSC421 | Fall 1999 (Section 0101)


Programming Project #3

CMSC 421, Section 0101 (Fall 1999)

Assigned: 16 November 1999
Design due: 23 November 1999 at 11 PM
Code due: 14 December 1999 at 11 PM


The goal for this project is to implement virtual memory using page tables. There are three parts to this assignment:


First, please make sure you have the latest version of dlxos.tgz and (if you're working off campus) dlxsim.tgz. The OS hasn't changed much from Project #2. However, we've provided some help for you if you weren't able to get user programs working - the OS has a working program loader, so you can still test your VM with a single program if you didn't get user traps to work.

Two-level page tables

Your first goal will be to implement two-level page tables for DLX. Currently, DLX uses only single-level page tables, but the "hardware" is capable of two-level tables. In order to activate two-level page tables, you'll need to modify the constants MEMORY_L1_PAGE_SIZE_BITS and MEMORY_L2_PAGE_SIZE_BITS. They're currently set to the same value (16), but you'll need to set them appropriately for your page tables, which should have 512 byte pages and map 64KB per level 2 page table. Your level 1 page tables should have 256 entries — enough to map 16MB of memory per process, which sholuld be plenty for a CPU with only 2MB of memory by default.

Level 1 page tables only have pointers to level 2 page tables in them. If the L2 page table for a particular entry doesn't exist, the PTE in the L1 page table should be 0. If it does exist, the PTE should just contain the address of the L2 table, which may start at any address divisible by 4 (except 0, of course).

Level 2 page tables have PTEs in them that point to real pages of memory. In addition to the page address itself, there are three special bits in each PTE: valid, dirty, and reference. The valid bit must be set by the operating system to indicate that the page in memory is valid. The dirty and reference bits are set by the "hardware" when an address in the page is modified and accessed (read or written), respectively. The bits are never reset by the "hardware", but they may be reset by the OS if desired. Definitions for the bits are in memory.h.

If a user process attempts to access an invalid page, a page fault trap is generated. This occurs if either the entry in the level 1 page table is 0, or if the entry in the level 2 page table is marked with an invalid bit. If the access is past the end of the level 1 page table, an illegal access trap is generated instead. You don't need to handle illegal accesses, but you do need to handle page faults (see below). After you've loaded the missing page and fixed up the page tables, you return from the trap the same way you returned from other traps.

In addition to implementing 2-level page tables, you'll need to modify MemoryTranslateUserToSystem() to be able to translate user addresses into system addresses. This currently works for the simple single level page tables already implemented, but you'll need to modify it to handle your 2-level page tables.

Note that all of this page table stuff needs to be freed up when a process exits, so you should keep track of which pages have been allocated to each process. The page table does this implicitly....

Sbrk trap

In this version of the operating system, processes can request more memory via the Sbrk() trap. This trap takes one argument: the number of bytes the process wants to allocate. The return value should be a pointer (in the user's address space) to the extra memory that was allocated.

Implementing Sbrk() will involve modifying the page tables for the process to make more pages valid, and any bookkeeping that might entail.

On-disk virtual memory

Since processes in DLXOS might use more memory than the system has available, you'll need to implement on-disk virtual memory. This means you'll need to be able to keep pages of memory on disk if there's no space for them in memory. To do this, you should use the FsOpen, FsRead, and FsWrite calls on a file called "vm" that you create. Sample usage for these calls (FsOpen & FsRead) is in process.c; FsWrite uses similar arguments to FsRead.

On a page fault, you'll need to choose a page to remove from memory and find the page on disk that you're going to replace it with. You may also need to write the page being replaced to disk if it's dirty. These tasks will involve keeping track of which parts of the disk are available and which parts are free. You'll also want to quickly be able to figure out where on the disk the page you're trying to bring in is located. The easiest way to do this is to somehow store the disk location in the PTE....


What to hand in

As with other projects, you'll need to hand in your design documentation and your code. Because your code may include both operating system code and user programs (such as the shell), please make sure your Makefile builds them separately.

Syllabus | Schedule | News & Notes | Grades | Feedback
Submit | Homework: 1 2 3 4 5 6 | Project: 1 2 3 4

Last updated 3 Dec 1999 by Ethan Miller (