Goals

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

• Implement two-level page tables, replacing the primitive page tables currently provided in process.c and memory.c. Memory should be allocated when a process is created and deallocated when a process ends.
• Allow programs to request more memory via a trap. This trap should take a single argument — the amount of memory desired — and return a pointer to the additional memory. The amount of memory may be more than a single page, so the allocated memory should be contiguous. It's probably easiest to do this by simply adding more pages at the end of the current memory space for the process. The trap should be called Sbrk (you can read the Unix man page for sbrk to see why).
• Allow individual pages to reside on "disk" rather than in "memory". To do this, you'll need to use the file system calls provided in the simulator (FsRead, FsWrite, etc.). Store your pages in a file called "vm", which should have enough space for 20 MB of memory. Keep in mind that you'll have to keep track of which areas on the disk are in use and which are free in addition to remembering which areas belong to which in-memory pages.

Specifications

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....

Hints

• You might want to build a bitmap that shows you which disk blocks are available. In such a structure, you have one bit per block, with a 0 indicating the space is available and a 1 indicating that it's in use. For a 20MB virtual memory, you'll need 40K bits, or just 5KB. A similar bitmap is used to keep track of which in-memory pages are available — check out the code.
• You'll need to implement a page replacement algorithm. The clock-based algorithms are typically easy to implement and perform quite well. FIFO is another easy-to-implement choice.
• Don't forget that you'll need to dynamically allocate space for page tables as well as for the memory space for a process. Allocate the minimum space for page tables that you need, and grow the tables as necessary.
• Use simple processes that allocate lots of memory to test your code. Make use of Putchar() to show progress in various processes.
• System processes can't benefit from this memory stuff; you'll have to use user processes to test it out.
• Use debugging statements to track where your code is going.

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.