Project 3: Demand Paging
Due: Friday, December 2 at 11:59pm (No time for extensions)
In project 2, each process had a page table that was initialized
with physical pages and their contents when the process was created.
In project 3, you will implement a more sophisticated memory
management system where physical pages are allocated on demand and
pages that cannot fit in physical memory will be stored on
You will implement and debug virtual memory in two steps. First,
you will implement demand paging using page faults to dynamically
initialize process virtual pages on demand, rather than initializing
page frames for each process in advance at exec time as you
did in project 2. Next, you will implement page replacement,
enabling your kernel to evict a virtual page from memory to free up
a physical page frame to satisfy a page fault. Demand paging and
page replacement together allow your kernel to "overbook" memory by
executing more processes than would fit in machine memory at any one
time, using page faults to multiplex the available physical page
frames among the larger number of process virtual pages. When
implemented correctly, virtual memory is undetectable to user
programs unless they monitor their own performance.
You project will implement the following functionality:
- Demand Paging. Pages will be in physical memory only as
needed. When no physical pages are free, it is necessary to free
pages, possibly evicting pages to swap.
- Lazy Loading. To fulfill the spirit of demand paging,
processes should load no pages when started, and depend on demand
paging to provide even the first instruction they execute. When
you are done, loadSections will not allocate even a
- Page Pinning. At times it will be necessary to "pin" a
page in memory, making it temporarily impossible to evict.
The changes you make to Nachos will be in these two files in
the vm directory:
- VMKernel.java — an extension of UserKernel
- VMProcess.java — an extension of UserProcess
These classes inherit from UserKernel
and UserProcess. While the VM versions of these classes
will be able to depend upon functionality in the base classes, the
focus in this project will be on demand-paged virtual memory. As a
result, you will be implementing new versions of key methods in
VMProcess such as loadSections, readVirtualMemory, and
You will compile and run the project in the proj3
directory. Unlike the first two projects, you will not need to
learn any new Nachos modules and will continue to use functionality
that you became familiar with in project 2. Before starting your
implementation, also see the Tips section
Central to this project are the following design aspects:
- TranslationEntry bits. You will extend your kernel's
handling of the page tables to use three special bits in each
- Valid bit: You will set or clear the valid bit in each TE to
tell the CPU which virtual pages are resident in memory (a valid
translation) and which are not resident (an invalid translation).
If a user process references an address for which the TE is marked
invalid, then the CPU raises a page fault exception and transfers
control to the Nachos exception handler.
- Used bit: The CPU sets the used bit (aka reference bit) in the
TE to pass information to Nachos about page access patterns. If a
virtual page is referenced by a process, the machine sets the
corresponding TE reference bit to inform the kernel that the page
is active. Once set, the reference bit remains set until the
kernel clears it.
- Dirty bit: The CPU sets the dirty bit in the TE whenever a
process executes a store (write) to the corresponding virtual
page. This step informs the kernel that the page is dirty; if the
kernel evicts the page from memory, then it must first "clean" the
page by writing its contents to disk. Once set, the dirty bit
remains set until the kernel clears it.
- Swap File. To manage swapped out pages on disk, use
the StubFileSystem (via ThreadedKernel.fileSystem)
as in project 2. There are many design choices, but we suggest
using a single, global swap file across all processes. This file
should last the lifetime of your kernel.
Be sure to choose a reasonably unique file name that will not
conflict with other files in the test directory.
When designing the swap file, keep in mind that the units of
swap are pages. Thus you should try to conserve disk space using
the same techniques applied in virtual memory: if you end up
having gaps in your swap space (due to processes terminating), try
to fill them. As with physical memory in project 2, a global free
list works well. You can assume that the swap file can grow
arbitrarily, and that there should not be any read/write errors.
Assert if there are.
- Global Memory Accounting.
In addition to tracking free pages (which may be managed as in
project 2), there are now two additional pieces of memory
information relevant to all processes: which pages are pinned, and
which process owns which pages. The former is necessary to prevent
the eviction of certain "sensitive" pages. The latter is necessary
to managing eviction of pages.
There are also multiple approaches to solving this problem, but we
suggest using a global inverted page table (see
the tips below).
- Page Pinning. When your code is using a physical page for
system calls (e.g., in readVirtualMemory
or writeVirtualMemory) or I/O (e.g., reading from
the COFF file or the swap file), you will need to "pin" the
physical page while you are using it. Consider the following
- Process A is executing the program at user-level and invokes
the read system call.
- Process A enters the kernel, and is part way through writing to
- A timer interrupt triggers a context switch, entering process B.
- Process B immediately generates numerous page faults, which in
turn cause pages to be evicted from other processes, including some
used by process A.
- Eventually, process A is scheduled to run again, and continues
handling the read syscall as before.
In this example, the page to which A is writing should be pinned
in memory so that it is not chosen for page eviction. Otherwise, if
process B evicted the page, then when process A was rescheduled it
would accidentally write over the page B loaded. Just use another
data structure to keep track of which pages are pinned.
1. (30%) Implement demand paging. In this first part, you will
continue to preallocate a physical page frame for each virtual page
of each newly created process at exec time, just as in
project 2. And as before, for now continue to return an error from
the exec system call if there are not enough free page
frames to hold the process' new address space. You will not yet
need to implement the swap file, page replacement, page pinning, an
inverted page table, etc. Instead, you just need to make the
- In VMProcess.loadSections, initialize all of the
TranslationEntries as invalid. This will cause the machine
to trigger a page fault exception when the process accesses a
page. Also do not initialize the page by, e.g., loading from
the COFF file. Instead, you will do this on demand when
the process causes a page fault. As a
result, loadSections will continue to allocate physical
page frames in the page table for each virtual page, but delay
loading the frames with content until they are actually referenced
by the process. Note that handling a page fault does not have
a return value.
- Handle page fault exceptions
in VMProcess.handleException. When the process
references an invalid page, the machine will raise a page fault
exception (if a page is marked valid, no fault is
generated). Modify your exception handler to catch this exception
and handle it by preparing the requested page on demand.
- Add a method to prepare the requested page on demand. Note
that faults on different pages are handled in different ways. A
fault on a code page should read the corresponding code page from
the COFF file, a fault on a data page should read the
corresponding data page from the
COFF file, and a fault on a stack page or arguments page
should zero-fill the page.
For this step, for reference look at the COFF file
loading code from UserProcess.loadSections from project
2. If the process faults on page 0, for example, then load the
first page of code from the executable file into it. More
generally, when you handle a page fault you will use the value
of the faulting address to determine how to initialize that
page: if the faulting address is in the code segment, then you
will be loading a code page; if the address is in the data
segment, then load the appropriate data page; if it is any other
page, zero-fill it. It is fine to loop through the sections of
the COFF file until you find the approprate section and
page to use (assuming it is in the COFF file).
Once you have paged in the faulted page, mark the
TranslationEntry as valid. Then let the machine restart
execution of the user program at the faulting instruction: return
from the exception, but do not increment the PC (as is done when
handling a system call) so that the machine will re-execute the
faulting instruction. If you set up the page (by initializing it)
and page table (by setting the valid bit) correctly, then the
instruction will execute correctly and the process will continue
on its way, none the wiser.
- Once you have basic functionality working with test programs
that do not use files or the console (e.g., matmult,
swap4 and swap5), then implement
and VMProcess.writeVirtualMemory methods to handle
invalid pages and page faults, starting with your implementations
from project 2. Both methods directly access physical memory to
read/write data between user-level virtual address spaces and the
Nachos kernel. These methods will now need to check to see if the
virtual page is valid. If it is valid, it can use the physical
page as before. If the page is not valid, then it will need to
fault the page in as with any other page fault.
Testing: As long as there is enough physical memory to fully
load a program, then you should be able to use test programs from
project 2 to test this part of project 3. See the tips in
the Testing section below for how you can
control (increase or decrease) the number of physical pages
(e.g., write10 is going to need more than the default of 16
pages). If you give Nachos enough physical pages, you can even run
the swap4 and swap5 tests (and these tests do not
use any system calls other than exit).
2. (70%) Now implement demand paged virtual memory with page
replacement. In this second part, not only do you delay
initializing pages, but now you delay the allocation of physical
page frames until a process actually references a virtual page that
is not already loaded in memory.
- In part one for VMProcess.loadSections, you
allocated physical pages for each virtual page, but you marked
them as invalid so that they would be initialized on a page
fault. Now change VMProcess.loadSections so that it
does not even allocate a physical page. Instead, merely mark
all the TranslationEntries as invalid.
- Extend your page fault exception handler to allocate a page
frame on-the-fly when a page fault occurs. In part one, you
just initialized the contents of the virtual page when a page
fault occurred. In this part, now allocate a physical page
for the virtual page and use your code from part 1 above to
initialize it, mark the TranslationEntry as valid, and return
from the exception.
You can get the above two changes working without having page
replacement implemented for the case where you run a single
program that does not consume all of physical memory. Before
moving on, be sure that the two changes above work for a single
program that fits into memory.
Now implement page replacement to free up a physical page
frame to handle page faults:
- Extend your page fault exception handler to evict pages
once physical memory becomes full. First, you will need to
select a victim page to evict from memory.
Your page eviction strategy should be the clock algorithm.
Then mark the TranslationEntry
for that page as invalid.
- Evict the victim page. If the page is clean (i.e., not
dirty) and the contents of that page are on disk (e.g.,
already in the swap file, code in the COFF file,
etc.) then the page can be used immediately; you can always
recover the contents of the page from disk. If the page is
dirty, though, the kernel must save the page contents in the
swap file on disk.
- Read in the contents of the faulted page either from the
executable file or from swap (see below).
- Implement the swap file for storing pages evicted from
physical memory. You will want to implement methods to create
a swap file, write pages from memory to swap (for page out),
read from swap to memory (for page in), etc.
As you implement the above operations, keep the following
points in mind:
- As in the first part of the project, the first time a page
is touched it needs to be initialized (e.g., from the
executable file for code and data). If this page is
subsequently evicted to swap, it will be read from there on
further page faults. To be concrete, consider a page used for
data. On the first access (fault) on that page, you will read
that page in from the executable file. Assume the process
dirties the page. When this page gets evicted, you should
write it to the swap. If the process faults on the page
again, you should read the page in from the swap, not from the
executable file (the executable file contains the initial
version of the page, the swap contains the most recent version
of the page).
- When running multiple processes, the page replacement
algorithm may select a victim page to evict from another
process. As a result, you will need to update the
TranslationEntry in the page table for that process,
not the faulting one.
- readVirtualMemory and writeVirtualMemory
will need to pin memory. It is possible that a process needs
a page, but not only are all pages in use (meaning an eviction
must occur), but all pages are pinned (meaning an eviction
must not occur now ). Handle this situation using
synchronization. If process A needs to evict a page, but all
pages are pinned, block A. When another process unpins a
page, it can unblock A. In terms of prioritizing, implement
this functionality towards the end after you have general page
Finally, you should only do as many page reads and writes as
necessary to execute the program, and as dictated by the page
replacement algorithm. You will soon discover that the first page
fault can be different than subsequent ones on a particular page:
- Read-only COFF sections originate in
the COFF file, and should never appear in swap.
- Read/write COFF sections originate in
the COFF file, but will need to be saved to swap if
- Other pages should be zero-initialized, and are never read
from the COFF file. If these pages are chosen for
eviction, they will need to be saved to swap and subsequent
faults on those pages will read them from swap.
- Tips from Ryan Huang
- There are many potential race conditions in this project
because multiple processes are accessing shared data structures.
We suggest using a coarse-grained lock to protect the data
structures. This will only be necessary once you start working
with multiple processes, and do not worry about it until after you
have page replacement working with a single process whose virtual
address space exceeds physical memory.
- Here are a couple of example test programs you can use to get
started on testing your implementation:
- swap4.c: Initialize and read a large array
- swap5.c: Initialize, read, and modify a large array
- Note: When starting on part 1, by default Nachos will
not have enough physical memory to run large programs like write10
and swap4/5. When testing part 1 with these programs, you will
need to explicitly have Nachos allocate more physical memory using
the -m paramater to nachos. The following gives
Nachos plenty of physical memory:
% nachos -m 64 -x swap4.coff
In contrast, when you start implementing swapping in part 2
you will want to explicitly control and reduce the number of
pages (and thus, indirectly, the necessity to swap), such as:
% nachos -m 8 -x swap4.coff
You can also modify nachos.conf in the proj3
subdirectory to control the default amount of physical memory.
Note that your implementation should not depend upon any
particular number of physical pages, but we will always test with
at least four physical pages. When testing with multiple processes,
we will test with at least twice the number of physical pages
as processes (e.g., eight pages with four processes).
- Implement a method to print the state of the inverted page
table (which processes are using which physical pages) and process
page tables (which pages are in physical memory, which pages are
in swap), and use it liberally when debugging.
Lib.debug() will also
continue to be helpful.
As with the previous projects, during the project period you can
also use Gradescope to run a snapshot of your code on the sample
tests that we have given. For reference, see the
post describing how to use Gradescope to compile and run the
sample tests. Important: As with the previous projects,
before the deadline you must submit your code to Gradescope at least
once to initialize the grading system for your project.
As a final step, create a file named README in the proj3
directory. The README file should list the members of your group
and provide a short description of what code you wrote, how well it
worked, how you tested your code, and how each group member
contributed to the project. The goal is to make it easier for us to
understand what you did as we grade your project in case there is a
problem with your code, not to burden you with a lot more work. Do
not agonize over wording. It does not have to be poetic, but it
should be informative.
We will use a snapshot of your Nachos implementation in your
github repository as it exists at the deadline, and grade that
version. (Even if you have made changes to your repo after the
deadline, that's ok, we will use a snapshot of your code at the
Important: Before the deadline, you must submit
your code to Gradescope at least once. See the instructions in
the Testing section above.
Troubleshooting Account Issues
If you encounter problems with your account (command not found,
disk quota exceeded, class file has wrong version,
etc.), see these troubleshooting
You can discuss concepts with students in other groups, but do not
cheat when implementing your project. Cheating includes copying
code from someone else's implementation, or copying code from an
implementation found on the Internet. See the
main project page for more
We will manually check and also run code plagiarism tools on
submissions and multiple Internet distributions.