-@node Page Table Structure
-@subsubsection Page Table Structure
-
-On the 80@var{x}86, the page table format is fixed by hardware. We
-have provided code for managing page tables for you to use in
-@file{userprog/pagedir.c}. The functions in there provide an
-abstract interface to all the page table functionality that you should need
-to complete the project. However, you may still find it worthwhile to
-understand a little about the hardware page table format, so we'll go
-into a little of detail about that in this section.
-
-The top-level paging data structure is a page called the ``page
-directory'' (PD) arranged as an array of 1,024 32-bit page directory
-entries (PDEs), each of which represents 4 MB of virtual memory. Each
-PDE may point to the physical address of another page called a
-``page table'' (PT) arranged, similarly, as an array of 1,024
-32-bit page table entries (PTEs), each of which translates a single 4
-kB virtual page to a physical page.
-
-Translation of a virtual address into a physical address follows
-the three-step process illustrated in the diagram
-below:@footnote{Actually, virtual to physical translation on the
-80@var{x}86 architecture occurs via an intermediate ``linear
-address,'' but Pintos (and most other 80@var{x}86 OSes) set up the CPU
-so that linear and virtual addresses are one and the same. Thus, you
-can effectively ignore this CPU feature.}
+In Pintos, a @dfn{page table} is a data structure that the CPU uses to
+translate a virtual address to a physical address, that is, from a page
+to a frame. The page table format is dictated by the 80@var{x}86
+architecture. Pintos provides page table management code in
+@file{pagedir.c} (@pxref{Page Table}).
+
+The diagram below illustrates the relationship between pages and frames.
+The virtual address, on the left, consists of a page number and an
+offset. The page table translates the page number into a frame number,
+which is combined with the unmodified offset to obtain the physical
+address, on the right.
+
+@example
+@group
+ +----------+
+ .--------------->|Page Table|-----------.
+ / +----------+ |
+ 0 | 12 11 0 0 V 12 11 0
+ +---------+----+ +---------+----+
+ |Page Nr | Ofs| |Frame Nr | Ofs|
+ +---------+----+ +---------+----+
+ Virt Addr | Phys Addr ^
+ \_______________________________________/
+@end group
+@end example
+
+@node Swap Slots
+@subsubsection Swap Slots
+
+A @dfn{swap slot} is a contiguous, page-size region of disk space on the
+swap disk. Although hardware limitations dictating the placement of
+slots are looser than for pages and frames, swap slots should be
+page-aligned because there is no downside in doing so.
+
+@node Resource Management Overview
+@subsection Resource Management Overview
+
+You will need to design the following data structures:
+
+@table @asis
+@item Segment table
+
+Enables page fault handling by supplementing the page table.
+@xref{Managing the Segment Table}.
+
+@item Frame table
+
+Allows efficient implementation of eviction policy.
+@xref{Managing the Frame Table}.
+
+@item Swap table
+
+Tracks usage of swap slots.
+@xref{Managing the Swap Table}.
+
+@item Table of file mappings
+
+Processes may map files into their virtual memory space. You need a
+table to track which files are mapped into which pages.
+@end table
+
+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: