11/18/21, 9:10 PM CSE 120: Principles of Computer Operating Systems
https://cseweb.ucsd.edu/classes/fa21/cse120-a/projects/project3.html 1/6
Project 3: Demand Paging
Fall 2021

Due: Tue, Dec 7 at 11:59pm
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 be implementing a
more sophisticated memory management system where physical pages are allocated on
demand and pages that cannot t in physical memory will be stored on disk.
Background
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 t 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:
1. 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.
2. Lazy Loading. To fulll the spirit of demand paging, processes should load no
pages when started, and depend on demand paging to provide even the rst
instruction they execute. When you are done, loadSections will not allocate
even a single page.
3. 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 les in the vm directory:
VMKernel.java — an extension of UserKernel
VMProcess.java — an extension of UserProcess
You will notice that these classes inherit from UserKernel and UserProcess . Try
to depend on the implementation of your base classes as much as possible. Note that,
with readVirtualMemory and writeVirtualMemory , very little code needs to
know the details of virtual addressing. For example, you should not have to change any
of the primary code which serviced the read syscall. That said, you should not change
11/18/21, 9:10 PM CSE 120: Principles of Computer Operating Systems
https://cseweb.ucsd.edu/classes/fa21/cse120-a/projects/project3.html 2/6
the base classes in any way that makes them dependent on project 3. It should still be
possible to run nachos from the proj2 subdirectory to run user-level programs.
You will compile and run the project in the proj3 directory. Unlike the rst 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 below.
Design Aspects
Central to this project are the following design aspects:
1. TranslationEntry bits. You will extend your kernel's handling of the page tables to
use three special bits in each TranslationEntry (TE):
Valid bit: Nachos 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 rst "clean" the page by writing its contents to disk. Once set, the dirty
bit remains set until the kernel clears it.
2. 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 le across all processes. This
le should last the lifetime of your kernel, and be properly deleted upon Nachos
termination. Be sure to choose a reasonably unique le name.
When designing the swap le, 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 (which will necessarily
occur with a global swap le upon program termination), try to ll them. As with
physical memory in project 2, a global free list works well. You can assume that the
swap le can grow arbitrarily, and that there should not be any read/write errors.
Assert if there are.
3. 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 of relevance 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.
11/18/21, 9:10 PM CSE 120: Principles of Computer Operating Systems
https://cseweb.ucsd.edu/classes/fa21/cse120-a/projects/project3.html 3/6
There are many approaches to solving this problem, but we suggest using a global
inverted page table (see the tips below).
4. 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 le or the swap le), you will need to "pin" the physical page while you
are using it. Consider the following actions:
1. Process A is executing the program at user-level and invokes the read
system call.
2. Process A enters the kernel, and is part way through writing to user
memory.
3. A timer interrupt triggers a context switch, entering process B.
4. Process B immediately generates numerous page faults, which in turn cause
pages to be evicted from other processes, including some used by process
A.
5. 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.
Tasks
1. (30%) Implement demand paging. In this rst 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 le, page replacement, page
pinning, an inverted page table, etc. Instead, you just need to make the following
changes:
1. 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
le. 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.
2. 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.
3. Add a method to prepare the requested page on demand. Note that faults on
dierent pages are handled in dierent ways. A fault on a code page should read
the corresponding code page from the COFF le, a fault on a data page should
11/18/21, 9:10 PM CSE 120: Principles of Computer Operating Systems
https://cseweb.ucsd.edu/classes/fa21/cse120-a/projects/project3.html 4/6
read the corresponding data page from the COFF le, and a fault on a stack
page or arguments page should zero-ll the frame.
For this step, for reference look at the COFF le loading code from
UserProcess.loadSections from project 2. If the process faults on page 0,
for example, then load the rst page of code from the executable le 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-ll it. It
is ne to loop through the sections of the COFF le until you nd the approprate
section and page to use (assuming it is in the COFF le).
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.
4. Update readVirtualMemory and writeVirtualMemory to handle invalid
pages and page faults. 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.
1. 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.
2. Extend your page fault exception handler to allocate a page frame on-the-y 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.
11/18/21, 9:10 PM CSE 120: Principles of Computer Operating Systems
https://cseweb.ucsd.edu/classes/fa21/cse120-a/projects/project3.html 5/6
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 ts into memory.
Now implement page replacement to free up a physical page frame to handle page
faults:
1. 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.
2. Evict the victim page. If the page is clean (i.e., not dirty), 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 le on
disk.
3. Read in the contents of the faulted page either from the executable le or from
swap (see below).
4. Implement the swap le for storing pages evicted from physical memory. You will
want to implement methods to create a swap le, 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 rst part of the project, the rst time a page is touched it needs to be
initialized (e.g., from the executable le 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 rst access (fault) on that page,
you will read that page in from the executable le. 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 le (the executable le 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 replacement working.
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 rst page fault is dierent than subsequent ones on a particular page. As
described above, on the rst fault on a page you need to read from the executable le,
11/18/21, 9:10 PM CSE 120: Principles of Computer Operating Systems
https://cseweb.ucsd.edu/classes/fa21/cse120-a/projects/project3.html 6/6
and on the second you may need to read from swap. Your implementation needs to be
able to handle this situation. In short:
Read-only COFF sections originate in the COFF le, and should never appear
in swap.
Read/write COFF sections originate in the COFF le, but may need to enter
swap if modied.
Other pages should be zero-initialized, and are never read from the COFF le.
Tips
Read Ryan Huang's tips for project 3.
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.
Occasionally check to make sure that you can still run project 2 from the proj2
subdirectory.
Testing
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
Begin testing with a running program that does not use exec . When you start
implementing swapping, you can control the number of pages (and thus,
indirectly, the necessity to swap) with the -m paramater to nachos :
% nachos -m 8 -x swap4.coff
or by modifying nachos.conf in the proj3 subdirectory. Your
implementation should not depend upon any particular number of physical pages,
but we will always test with at least four physical pages.
Implement a method to print memory state, and use it liberally when hunting for
errors. Lib.debug() and Lib.assertTrue() will also continue to be
helpful.
yiying@ucsd.edu

























































































































































































































































































































































































































































































































学霸联盟