-You'll need to modify the ELF loader in @file{userprog/process.c} to
-do page table management according to your new design. As supplied,
-it reads all the process's pages from disk and initializes the page
-tables for them at the same time. For testing purposes, you'll
-probably want to leave the code that reads the pages from disk, but
-use your new page table management code to construct the page tables
-only as page faults occur for them.
-
-You should use the @func{palloc_get_page} function to get the page
-frames that you use for storing user virtual pages. Be sure to pass
-the @code{PAL_USER} flag to this function when you do so, because that
-allocates pages from a ``user pool'' separate from the ``kernel pool''
-that other calls to @func{palloc_get_page} make.
-
-There are many possible ways to implement virtual memory. The above
-is simply an outline of our suggested implementation.
-
-@node Problem 3-2 Paging To and From Disk
-@section Problem 3-2: Paging To and From Disk
-
-Implement paging to and from files and the swap disk. You may use the
-disk on interface @code{hd1:1} as the swap disk, using the disk
-interface prototyped in @code{devices/disk.h}. From the @file{vm/build}
-directory, use the command @code{pintos make-disk swap.dsk @var{n}} to
-create an @var{n} MB swap disk named @file{swap.dsk}. Afterward,
-@file{swap.dsk} will automatically be attached when you run
-@command{pintos}.
-
-You will need routines to move a page from memory to disk and from
-disk to memory, where ``disk'' is either a file or the swap disk. If
-you do everything correctly, your VM should still work when you
-implement your own file system for the next assignment.
-
-You will need a way to track pages which are used by a process but
-which are not in physical memory, to fully handle page faults. Pages
-that you write to swap should not be constrained to be in sequential
-order. You will also need a way to track all of the physical memory
-pages, to find an unused one when needed, or to evict a page
-when memory is needed but no empty pages are available. The data
-structures that you designed for problem 3-1 should do most of the work for
-you.
-
-You will need a page replacement algorithm. The hardware sets the
-accessed and dirty bits when it accesses memory. You can gain access
-to this information using the functions prototyped in
-@file{userprog/pagedir.h}. You should be able to take advantage of
-this information to implement some algorithm which attempts to achieve
-LRU-type behavior. We expect that your algorithm perform at least as
-well as a reasonable implementation of the second-chance (clock)
-algorithm. You will need to show in your test cases the value of your
-page replacement algorithm by demonstrating for some workload that it
-pages less frequently using your algorithm than using some inferior
-page replacement policy. The canonical example of a poor page
-replacement policy is random replacement.
-
-You must write your code so that we can choose a page replacement policy
-at compile time. By default, the LRU-like algorithm must be in effect,
-but we must be able to choose random replacement by inserting the line
-@code{#define RANDOM_REPLACEMENT 1} in @file{constants.h}.
-@xref{Conditional Compilation}, for details.
-
-Since you will already be paging from disk, you should implement a
-``lazy'' loading scheme for new processes. When a process is created,
-it will not run immediately. Therefore, it doesn't make sense to load
-all its code, data, and stack into memory when the process is created,
-since it might incur additional disk accesses to do so (if it gets
-paged out before it runs). When loading a new process, you should
-leave most pages on disk, and bring them in as demanded when the
-program begins running. Your VM system should also use the executable
-file itself as backing store for read-only segments, since these
-segments won't change.
-
-There are a few special cases. Look at the loop in
-@func{load_segment} in @file{userprog/process.c}. Each time
-around the loop, @code{read_bytes} represents the number of bytes to
-read from the executable file and @code{zero_bytes} represents the number
-of bytes to initialize to zero following the bytes read. The two
-always sum to @code{PGSIZE}. The page handling depends on these
-variables' values:
+You do not necessarily need to implement four completely distinct data
+structures: it may be convenient to wholly or partially merge related
+resources into a unified data structure.
+
+For each data structure, you need to determine what information each
+element should contain. You also need to decide on the data structure's
+scope, either local (per-process) or global (applying to the whole
+system), and how many instances are required within its scope.
+
+To simplify your design, you may store these data structures in
+non-pageable memory. That means that you can be sure that pointers
+among them will remain valid.
+
+Possible choices of data structures include arrays, lists, bitmaps, and
+hash tables. An array is often the simplest approach, but a sparsely
+populated array wastes memory. Lists are also simple, but traversing a
+long list to find a particular position wastes time. Both arrays and
+lists can be resized, but lists more efficiently support insertion and
+deletion in the middle.
+
+Pintos includes a bitmap data structure in @file{lib/kernel/bitmap.c}
+and @file{lib/kernel/bitmap.h}. A bitmap is an array of bits, each of
+which can be true or false. Bitmaps are typically used to track usage
+in a set of (identical) resources: if resource @var{n} is in use, then
+bit @var{n} of the bitmap is true. Pintos bitmaps are fixed in size,
+although you could extend their implementation to support resizing.
+
+Pintos also includes a hash table data structure (@pxref{Hash Table}).
+Pintos hash tables efficiently support insertions and deletions over a
+wide range of table sizes.
+
+Although more complex data structures may yield performance or other
+benefits, they may also needlessly complicate your implementation.
+Thus, we do not recommend implementing any advanced data structure
+(e.g.@: a balanced binary tree) as part of your design.
+
+@node Managing the Supplemental Page Table
+@subsection Managing the Supplemental Page Table
+
+The @dfn{supplemental page table} supplements the page table with
+additional data about each page. It is needed because of the
+limitations imposed by the page table's format. Such a data structure
+is often called a ``page table'' also; we add the word ``supplemental''
+to reduce confusion.
+
+The supplemental page table is used for at least two purposes. Most
+importantly, on a page fault, the kernel looks up the virtual page that
+faulted in the supplemental page table to find out what data should be
+there. Second, the kernel consults the supplemental page table when a
+process terminates, to decide what resources to free.
+
+You may organize the supplemental page table as you wish. There are at
+least two basic approaches to its organization: in terms of segments or
+in terms of pages. Optionally, you may use the page table itself as an
+index to track the members of the supplemental page table. You will
+have to modify the Pintos page table implementation in @file{pagedir.c}
+to do so. We recommend this approach for advanced students only.
+@xref{Page Table Entry Format}, for more information.
+
+The most important user of the supplemental page table is the page fault
+handler. In project 2, a page fault always indicated a bug in the
+kernel or a user program. In project 3, this is no longer true. Now, a
+page fault might only indicate that the page must be brought in from a
+file or swap. You will have to implement a more sophisticated page
+fault handler to handle these cases. Your page fault handler, which you
+should implement by modifying @func{page_fault} in
+@file{threads/exception.c}, needs to do roughly the following: