Programming Project #3
Memory Management

Assigned: November 4th
Due: Thursday, November 20th at 11:59 PM

Please make sure you've read the general project information page, including information on handing in your project.

Ground rules

The basic rules and project information are the same for this assignment as for Project #2. If you're working in a group, please remember that the student whose handin directory isn't being used should submit a single file called partner containing the name and CATS account of both project members into her directory. The grade received by each project partner will be the same.

As with other projects, the following suggestions apply:

Goals

The goal for this project is to implement virtual memory for DLXOS by adding the following functionality to DLXOS:

Most of your changes will be in memory.c and memory.h, though you'll probably have to make minor changes to other files such as traps.c and process.c.

If you can't get paging to and from a virtual memory file working, you can still get an 89 on the assignment, but you'll need to get paging to work if you want an A on this project. We suggest using CVS or RCS to track working versions of your code.

Specifications

What's there now?

DLXOS uses the TLB to translate virtual addresses to physical addresses. If a translation is not in the TLB, a TLBFAULT exception is generated by the user process and handled in traps.c. The handler calls MemoryTlbFault() to place the correct entry into the TLB.

Additionally, the routine MemoryTranslateUserToSystem() is used to translate virtual addresses into physical addresses. This routine is used in many places, so it's important to keep it working. Currently, it uses the (simple) one-level page tables in the PCB to do this mapping; you'll have to modify the routine to deal with your page tables. NOTE: do not make PCBs much larger than they are currently. Increasing PCB size by 64 bytes is OK; increasing it by 3 KB is not, and will cause your OS to crash.

Flexible page tables

Currently, processes are given a fixed-size page table with 16 pages. This is clearly not a good solution. You need to give each process a 32 MB address space. To do this, you'll need more flexible page tables that don't waste a bunch of space if (as usual) the address space is sparsely used. You will also need to make sure that the page table only contains as much space as is required by the process. You can use ProcessGetCodeInfo() to find out how big the code and data section are for a user program, and use this information to create a page table that has only as much space as was requested.

Don't forget to change the address that the user process stack starts at by modifying this line of code in process.c. It should point to an address just below 32 MB (32 * 1024 * 1024 - 32). The original line of code looks like this: 

curUserStack = (pcb->npages * MEMORY_PAGE_SIZE) - 32;;

You should dynamically allocate stack space as needed; when a reference is made to a memory address closer than 8 KB to the bottom of the stack, allocate more space for the stack (see below for information on how to do this).

Memory allocation trap

Processes may need to allocate more space. To do this, they'll use the Allocate() trap, which you have to write. The Allocate() trap should increase the amount of memory accessible to the process by increasing the valid portion of the address space for the process. Note that this might not mean actually allocating new pages to the process until it actually accesses them. The Allocate() trap works in much the same way as the Unix system call sbrk(). It takes one argument, the amount of memory to allocate, and returns a pointer to the memory region in the user's address space that contains the allocated space. For example,
addr = Allocate(1000);
would allocate 1000 bytes in the user process's data space, and return a pointer to the start of that space.

To do this, you'll probably want to keep track of the current maximum accessible heap address, and add to it as more space is requested. You should do the same for the stack, which is at the top of the process's address space.

Paging to and from disk

You need to allow for the system to allocate more pages than it has physical memory. This can be done by reading and writing a file called "vm"; you can use FsOpen(), FsRead(), etc. to access this file. All you need to do is write out a page that you no longer want in memory, and read it back in when necessary. You should use the reference and dirty bits from the TLB to decide whether you actually need to rewrite a page that's already in the VM file.

The VM file should be capable of holding 32 MB. Obviously, this is larger than your disk quota will allow, but at 1 bit per page, it's only 32 thousand bits, or 4 KB. You can use a single bit to indicate whether a particular page in the VM file is free. You can use your page table structure to keep track of which pages are where in the file. See the memory allocation routines for hints on how to manage a bitmap of free pages.

Design hints

Page tables

You can use any structure you want for your page table(s), so long as you don't waste space when a process uses very little space. You can use either inverted page tables (per process or global) or two-level page tables, or any other data structure you want. If you'd like to use small chunks of (constant-sized) memory, see the code in chunk.c for hints on how to manage a lot of small chunks of memory in the kernel.

You'll need to be able to create page tables, destroy them (reclaiming any used resources such as memory), and make them larger. You might want to keep track of the top of the heap and bottom of the stack for each process in its PCB. However, there is not enough space to actually build the page table in the PCB; you must not use more space for the page tables in the PCB than is currently used (24 integers). Instead, use dynamic allocation to build the page tables.

Keep in mind that ProcessTranslateUserToSystem() is used throughout the operating system, so make sure it works with your page tables.

Allocating memory

To keep things simple, only assign physical pages to processes when you actually need them. Allocation need only consist of modifying the page table so that the process is capable of accessing more memory; it need not actually allocate the memory. You could go one step further and write a process's initial memory to the VM file and allow it to use TLB faults to bring memory in from disk.

If you follow this method, the only place you'll need to reallocate physical pages is in MemoryTlbFault() because you can't have a page fault without first having a TLB fault. You should use MemoryAllocatePage() to allocate unused physical pages, and might want to keep a few around for the operating system's use. Similarly, MemoryFreePage() should be used when a physical page is no longer needed by a process.

You should use the trap number 0x450 for the Allocate trap.

Accesses to unallocated memory

For each process, you should keep track of the top of the heap and bottom of the stack, killing off the process if an access is made to an address above the top of the heap. Accesses just below the top of the stack (remember, the stack grows downward) are almost certainly due to the stack growing downward; if you get a TLB fault for an unallocated address within 8 KB of the current top of the stack, allocate more space for it in the page table.

All of this can be done in MemoryTlbFault(), which will always be called when a desired virtual address isn't in the TLB. If the page also isn't in physical memory, you may have to write out an existing physical page, bring in the desired page, and update the page table(s).

Managing the VM file

You can access the VM file, which you should call vm, using the FsOpen(), FsSeek(), FsRead(), and FsWrite() calls. These function identically to the open(), lseek(), read() and write() Unix system calls. If you want to write a page of memory to the VM file at a particular offset, you should make an FsSeek() call to the desired location, followed by an FsWrite() of the page in question. The same applies for reads; use FsSeek() followed by FsRead(). Keep in mind that FsRead() and FsWrite() read and write raw data—no formatting is done, and you don't want to use formatting in any case. A call like FsRead(fd, pageStart, pageLength) will write pageLength bytes starting at pageStart to the file described by fd (fd is returned from FsOpen).

You may want to experiment with FsRead() and FsWrite() to understand how they work.

Design hints

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 and test programs), please make sure your Makefile builds them separately (the Makefile provided with this assignment already does this). You may also want to hand in any test code and test documentation you used in completing this assignment.

Code from Project #2

You'll probably find it useful to have a user shell to test your program. You can modify your code from Project #2 if you like, or you can get a fresh copy of dlxos.tgz from /afs/cats/courses/cmps111-elm/dlx/ (no changes have been made to the code since Project #2). The "clean" version of dlxos.tgz has working code for Project #2, and has a working shell (called shell.exe). You can run it with the following command line:

dlxsim -x os.exe -a -u shell.exe

If you do use our solution for Project #2, please hand in proj2.s as well as shell.exe and any other user programs you write to test your code.

Extra credit

IMPORTANT: get the basic stuff working before you attempt the extra credit. No extra credit will be given to projects that don't implement the basic functionality. Minor bugs are OK, but you can't get extra credit unless your shell works well under "normal" conditions. Also, you can only get extra credit if your project is turned in on time; no extra credit will be given to late projects.

Last updated 12 Nov 2003 by Ethan L. Miller (elm@ucsc.edu)