Nachos Project 3: Virtual Memory
Informal Design Document Due: Never
Project 2 Autograder Rerun: May 30 at 14:00 PDT (See webboard for details!)
Early Submit Checkpoints: June 1 and 3 and 4, at 21:00 PDT
Project Code Due: Thursday, June 5, at 23:59 PDT
Announcement: If you are out of free pages
and you try to exec(), you may just return -1. However, for 5% extra
credit, you may sleep it and wake it up when there is a free page
available for it.
The third phase of Nachos is to investigate the interaction between the TLB,
the virtual memory system, and the file system. We don't provide any new
virtual memory code for this assignment. You will continue to use the stub
file system and your per process page tables. For this phase, you should run make and nachos
in the proj3 directory.
To help you to organize your code better, we provide you with a new package,
nachos.vm, with two new classes, VMKernel and
VMProcess. VMKernel extends UserKernel, and
VMProcess extends UserProcess.
VMKernel and VMProcess are the only classes you
should have to modify for this project phase.
This phase of the project involves open-ended design problems. We
will expect you to come up with a design that would make sense in a
real system. For example, you will have some freedom to choose how to
do software address translation on TLB misses, how to represent the
swap partition, how to implement paging, etc. There is no single
The first design aspect to consider is the software-managed translation
lookaside buffer (TLB). Page tables were used in phase 2 to simplify
memory allocation and to isolate failures from one address space
from affecting other programs. For this phase, the processor knows
nothing about page tables. Instead, the processor only deals
with a software-managed cache of page table entries, called the TLB.
Given a memory address (an instruction to fetch, or data to load or
store), the processor first looks in the TLB to determine if the mapping
of the virtual page to a physical page is already known. If the
translation is in the TLB, the processor uses it directly. If the
translation is not in the TLB (a "TLB miss"), the processor causes
a trap to the OS kernel. Then it is the kernel's responsibility to load
the mapping into the TLB.
In other words, the Nachos MIPS simulator does not have
direct access to your page tables; it only knows about the TLB.
It is your job to write the code that manages a TLB miss. It is important to note that a TLB miss may not necessarily result in a page fault.
The second design aspect of this project is paging, which
allows physical memory pages to be transferred to and from disk to
provide the illusion of an (almost) unlimited physical memory. A TLB
miss may require a page to be brought in from disk to satisfy the
translation. That is, when a TLB miss fault occurs, the process should
check its own page table. If the page is not in memory, it should
read the page in from disk, set the page table entry to point to
the new page, install the page table entry, and resume the execution of
the user program. Of course, the process must first find space
in memory for the incoming page, potentially writing some other
page back to disk, if it has been modified. Note that this is a local page replacement policy.
For this assignment, each process will have 4
physical pages (i.e. at most 4 entries in your page table are valid),
which are taken from your free list. We do this so one process doesn't
take up all the physical memory. To implement this you may need a data
structure to keep track of which of your pages are actually in
Performance of this mechanism depends greatly on the policy used to
decide which pages are kept in memory and which are stored on disk.
On a page fault, the kernel must decide which page to replace; ideally,
it will throw out a page that will not be referenced for a long time,
keeping in memory those pages may be referenced soon. Another
consideration is that if the replaced page has been modified, the page
must first be saved to disk before the needed page can be brought in.
(Of course, if the page has not been modified, it is not necessary to
write it back to disk.)
To help you implement demand paging, each TranslationEntry contains
three status bits: valid, used, and dirty. If
the valid bit is set, the virtual page is in memory and the
translation can be used directly by the processor. If the valid bit is
clear, or if the page translation is not found in the page table, then
the processor traps to the OS to perform the translation. You will
need to set the used bit in the TLB entry whenever a page is
referenced and sets the the dirty bit whenever the page is
modified. Also, keep in mind that you will be using a local page
replacement algorithm. That is, processes can only evict their own pages.
(33%) Implement software-management of the TLB,
with per-process page tables similar to what you did in Project 2.
Since VMProcess extends UserProcess, you
should not have to duplicate much code from UserProcess;
that is, only override what's necessary and call methods in the
superclass for everything else.
The way to handle TLB misses is to add code to
VMProcess.handleException which deals with the
The virtual address causing the TLB miss is obtained by
- Some methods you will need to use are: Machine.processor().getTLBSize()
(obtains the size of the processor's TLB), Machine.processor().readTLBEntry()
(reads a TLB entry), and Machine.processor().writeTLBEntry()
(writes a TLB entry). Note that TLB entries are of type TranslationEntry,
the same class used for page table entries in project phase 2.
When you run Nachos from the proj3 directory, the processor
no longer deals with page tables (as it did in phase 2); instead, the
processor traps to the OS on a TLB miss.
- You will need to make sure that TLB state is set up properly on
a context switch. Most systems simply invalidate all the TLB entries on
a context switch, causing entries to be reloaded as the pages are referenced.
- Your TLB replacement policy can be random, if you wish. The only
requirement is that your policy makes use of all TLB entries (that is,
don't simply use a single TLB entry or something weird like that).
- Only invalidate TLB entries when it is necessary to do so
(e.g. on context switches).
- Don't forget to set used and dirty bits where necessary in
readVirtualMemory and writeVirtualMemory.
(34%) Implement demand paging of virtual memory. For this, you will
need routines to move a page from disk to memory and from memory to disk.
You should use the Nachos stub file system as backing store; this will make
Part 3 (see below) a lot easier.
- You will need
to maintain a separate data structure for locating pages in swap.
- The Nachos TLB sets the dirty and used bits, which
you can use to implement the clock algorithm for page replacement.
- Your page-replacement policy should not write any pages to the
swap file which have not been modified (i.e. for which the dirty bit
is not set). Thus, you will be required to keep pages around in swap even
if they have been moved to physical memory.
- We recommend that you use a single global swap file shared by
all processes. You may use any format you wish for this file, but
it should be rather simple as long as you keep track of where different
virtual pages are stored in the file. You may assume that it's safe to
grow the swap file to an arbitrary size; that is, you don't need to be
concerned about running out of disk space for this file. (If a read or write
operation on the swap file returns fewer bytes than requested, this is
a fatal error.) To conserve disk space, you should reuse unallocated
swap file space; a simple list of free swap file pages is sufficient for this.
- The swap file should be closed and deleted when
VMKernel.terminate() is called. Don't forget to flush pages from the swap file when a process exits or is killed.
- If a process experiences an I/O error when accessing the swap
file, you should kill the process.
Note that it is possible to experience indefinite thrashing when the
system has only a single physical page of memory if a process
attempts to perform a load/store operation (convince
yourself why!). Your implementation need not deal with this case.
(33%) Implement lazy loading of the code and data
pages from user programs. That is, rather than reading all of the code
and data from a user program at startup time, set up page table
entries so that when page faults occur, the pages from the executable
will be read into memory on demand.
- You must ensure that changes to the memory image of the executable
are not written back to the executable file. Code pages are always
read-only, so there is no danger that the user process can modify them during
execution. However, the data pages from the executable (representing
global variables and the like) may be modified by the process.
Ensure that these changes are not written back to the executable file.
- In addition to lazy-loading pages from the executable file,
you should allocate stack pages on demand as well. So, you should
not allocate the full set of stack pages to the process when it
is initialized; rather, when a page fault occurs on a stack page, you
should allocate a new stack page at that time.
- As with project phase 2, the maximum number of stack pages
needed by a process is 8.