-@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.}
+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: