-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 Segment Table
+@subsection Managing the Segment Table
+
+The @dfn{segment table} supplements the page table with additional data
+about each page. It is required because of the limitations imposed by
+the page table's format. Such a supplementary data structure is often
+called a ``page table'' also; we call it a segment table to avoid
+confusion.
+
+The segment 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 segment table to find out what data should be there. Second, the
+kernel consults the segment table when a process terminates, to decide
+what resources to free.
+
+You may organize the segment 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 as part of your
+segment table design. 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 segment 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: