no new code to get acquainted with for this assignment. The @file{vm}
directory contains only the @file{Makefile}s. The only change from
@file{userprog} is that this new @file{Makefile} turns on the setting
-@option{-DVM}, which you will need for this assignment. All code you
-write will either be newly generated files (e.g.@: if you choose to
-implement your paging code in their own source files), or will be
-modifications to pre-existing code (e.g.@: you will change the
-behavior of @file{addrspace.c} significantly).
+@option{-DVM}. All code you write will either be newly generated
+files (e.g.@: if you choose to implement your paging code in their own
+source files), or will be modifications to pre-existing code (e.g.@:
+you will change the behavior of @file{process.c} significantly).
You will be building this assignment on the last one. It will benefit
you to get your project 2 in good working order before this assignment
so those bugs don't keep haunting you.
+All the test programs from the previous project should also work with
+this project. You should also write programs to test the new features
+introduced in this project.
+
+Your submission should define @code{THREAD_JOIN_IMPLEMENTED} in
+@file{constants.h} (@pxref{Conditional Compilation}).
+
@menu
* VM Design::
* Page Faults::
* Virtual Memory FAQ::
@end menu
-@node VM Design, Page Faults, Project 3--Virtual Memory, Project 3--Virtual Memory
+@node VM Design
@section A Word about Design
It is important for you to note that in addition to getting virtual
memory working, this assignment is also meant to be an open-ended
design problem. We will expect you to come up with a design that
-makes sense. You will have the freedom to choose how to do software
-translation on TLB misses, how to represent the swap partition, how to
-implement paging, etc. In each case, we will expect you to provide a
-defensible justification in your design documentation as to why your
-choices are reasonable. You should evaluate your design on all the
-available criteria: speed of handling a page fault, space overhead in
-memory, minimizing the number of page faults, simplicity, etc.
+makes sense. You will have the freedom to choose how to handle page
+faults, how to organize the swap disk, how to implement paging, etc.
+In each case, we will expect you to provide a defensible justification
+in your design documentation as to why your choices are reasonable.
+You should evaluate your design on all the available criteria: speed
+of handling a page fault, space overhead in memory, minimizing the
+number of page faults, simplicity, etc.
In keeping with this, you will find that we are going to say as little
as possible about how to do things. Instead we will focus on what end
functionality we require your OS to support.
-@node Page Faults, Disk as Backing Store, VM Design, Project 3--Virtual Memory
+@node Page Faults
@section Page Faults
For the last assignment, whenever a context switch occurred, the new
/ /
@end example
+Header @file{threads/mmu.h} has useful functions for various
+operations on virtual addresses. You should look over the header
+yourself, but its most important functions include these:
+
+@table @code
+@item pd_no(@var{va})
+Returns the page directory index in virtual address @var{va}.
-FIXME need to explain virtual and physical memory layout - probably
-back in userprog project
+@item pt_no(@var{va})
+Returns the page table index in virtual address @var{va}.
-FIXME need to mention that there are many possible implementations and
-that the above is just an outline
+@item pg_ofs(@var{va})
+Returns the page offset in virtual address @var{va}.
+
+@item pg_round_down(@var{va})
+Returns @var{va} rounded down to the nearest page boundary, that is,
+@var{va} but with its page offset set to 0.
+
+@item pg_round_up(@var{va})
+Returns @var{va} rounded up to the nearest page boundary.
+@end table
-@node Disk as Backing Store, Memory Mapped Files, Page Faults, Project 3--Virtual Memory
+@node Disk as Backing Store
@section Disk as Backing Store
In VM systems, since memory is less plentiful than disk, you will
overhead by writing modified pages to disk in advance, so that later
page faults can be completed more quickly.
-@node Memory Mapped Files, Stack, Disk as Backing Store, Project 3--Virtual Memory
+@node Memory Mapped Files
@section Memory Mapped Files
The traditional way to access the file system is via @code{read} and
memory mapped files for problem 3 of this assignment, but you should
design your solutions to problems 1 and 2 to account for this.
-@node Stack, Problem 3-1 Page Table Management, Memory Mapped Files, Project 3--Virtual Memory
+@node Stack
@section Stack
In project 2, the stack was a single page at the top of the user
unless those pages are unavailable because they are in use by another
segment, in which case some sort of fault should occur.
-@node Problem 3-1 Page Table Management, Problem 3-2 Paging To and From Disk, Stack, Project 3--Virtual Memory
+@node Problem 3-1 Page Table Management
@section Problem 3-1: Page Table Management
Implement page directory and page table management to support virtual
virtual address to the physical page found in step 2.
@end enumerate
-You'll need to modify the ELF loader in @file{userprog/addrspace.c} to
+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
use your new page table management code to construct the page tables
only as page faults occur for them.
-@node Problem 3-2 Paging To and From Disk, Problem 3-3 Memory Mapped Files, Problem 3-1 Page Table Management, Project 3--Virtual Memory
+There are many possible ways to implement virtual memory. The above
+is simply an outline of our suggested implementation. You may choose
+any implementation you like, as long as it accomplishes the goal.
+
+@node Problem 3-2 Paging To and From Disk
@section Problem 3-2: Paging To and From Disk
-Implement 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.
You will need routines to move a page from memory to disk and from
-disk to memory. You may use the Pintos file system for swap space, or
-you may use the disk on interface @code{hd1:1}, which is otherwise
-unused. A swap disk can theoretically be faster than using the file
-system, because it avoid file system overhead and because the swap
-disk and file system disk will be on separate hard disk controllers.
-You will definitely need to be able to retrieve pages from files in
-any case, so to avoid special cases it may be easier to use a file for
-swap. You will still be using the basic file system provided with
-Pintos. If you do everything correctly, your VM should still work
-when you implement your own file system for the next assignment.
+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 store on disk should not be constrained to be in sequential
-order, and consequently your swap file (or swap disk) should not
-require unused empty space. You will also need a way to track all of
-the physical memory pages, in order 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 in part 1 should do
-most of the work for you.
+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, in order 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 in part 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. Therefore, you
segments won't change.
There are a few special cases. Look at the loop in
-@code{load_segment()} in @file{userprog/addrspace.c}. Each time
+@code{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
@item
If neither @code{read_bytes} nor @code{zero_bytes} equals
@code{PGSIZE}, then part of the page is to be read from disk and the
-remainder zeroed. This is a special case, which you should handle by
+remainder zeroed. This is a special case. You may handle it by
reading the partial page from disk at executable load time and zeroing
-the rest of the page. It is the only case in which loading should not
-be ``lazy''; even real OSes such as Linux do not load partial pages
-lazily.
+the rest of the page. This is the only case in which we will allow
+you to load a page in a non-``lazy'' fashion. Many real OSes such as
+Linux do not load partial pages lazily.
@end itemize
-FIXME mention that you can test with these special cases eliminated
+Incidentally, if you have trouble handling the third case above, you
+can eliminate it temporarily by linking the test programs with a
+special ``linker script.'' Read @file{tests/userprog/Makefile} for
+details. We will not test your submission with this special linker
+script, so the code you turn in must properly handle all cases.
You may optionally implement sharing: when multiple processes are
created that use the same executable file, share read-only pages among
structures in part 1, sharing of read-only pages should not make this
part significantly harder.
-@node Problem 3-3 Memory Mapped Files, Virtual Memory FAQ, Problem 3-2 Paging To and From Disk, Project 3--Virtual Memory
+@node Problem 3-3 Memory Mapped Files
@section Problem 3-3: Memory Mapped Files
Implement memory mapped files.
the file. (In fact, you may choose to implement executable mappings
as a special case of file mappings.)
-@node Virtual Memory FAQ, , Problem 3-3 Memory Mapped Files, Project 3--Virtual Memory
+@node Virtual Memory FAQ
@section FAQ
@enumerate 1
Yes.
@item
-@b{How do I use the hash table provided in @file{lib/hash.c}?}
+@b{How do I use the hash table provided in @file{lib/kernel/hash.c}?}
-FIXME
+First, you need to embed a @code{hash_elem} object as a member of the
+object that the hash table will contain. Each @code{hash_elem} allows
+the object to a member of at most one hash table at a given time. All
+the hash table functions that deal with hash table items actually use
+the address of a @code{hash_elem}. You can convert a pointer to a
+@code{hash_elem} member into a pointer to the structure in which
+member is embedded using the @code{hash_entry} macro.
-There are two things you need to use this hashtable:
+Second, you need to decide on a key type. The key should be something
+that is unique for each object, because a given hash table may not
+contain two objects with equal keys. Then you need to write two
+functions. The first is a @dfn{hash function} that converts a key
+into an integer. Some sample hash functions that you can use or just
+examine are given in @file{lib/kernel/hash.c}. The second function
+needed is a @dfn{comparison function} that compares a pair and returns
+true if the first is less than the second. These two functions have
+to be compatible with the prototypes for @code{hash_hash_func} and
+@code{hash_less_func} in @file{lib/kernel/hash.h}.
-1. You need to decide on a key type. The key should be something
-that is unique for each object as inserting two objects with
-the same key will cause the second to overwrite the first.
-(The keys are compared with ==, so you should stick to
-integers and pointers unless you know how to do operator
-overloading.) You also need to write a hash function that
-converts key values to integers, which you will pass into the
-hash table constructor.
+Here's a quick example. Suppose you want to put @code{struct thread}s
+in a hash table. First, add a @code{hash_elem} to the thread
+structure by adding a line to its definition:
-2. Your key needs to be a field of your object type, and you
-will need to supply a 'get' function that given an object
-returns the key.
+@example
+hash_elem h_elem; /* Hash table element. */
+@end example
-Here's a quick example of how to construct a hash table. In
-this table the keys are Thread pointers and the objects are
-integers (you will be using different key/value pairs I'm
-sure). In addition, this hash function is pretty puny. You
-should probably use a better one.
+We'll choose the @code{tid} member in @code{struct thread} as the key,
+and write a hash function and a comparison function:
@example
-FIXME
+/* Returns a hash for E. */
+unsigned
+thread_hash (const hash_elem *e, void *aux UNUSED)
+@{
+ struct thread *t = hash_entry (e, struct thread, h_elem);
+ return hash_int (t->tid);
+@}
+
+/* Returns true if A's tid is less than B's tid. */
+bool
+thread_less (const hash_elem *a_, const hash_elem *b_, void *aux UNUSED)
+@{
+ struct thread *a = hash_entry (a_, struct thread, h_elem);
+ struct thread *b = hash_entry (b_, struct thread, h_elem);
+ return a->tid < b->tid;
+@}
@end example
-and to construct the hash table:
+Then we can create a hash table like this:
-HashTable<Thread *, HashObject *> *htable;
+@example
+struct hash threads;
+
+hash_init (&threads, thread_hash, thread_less, NULL);
+@end example
-htable = new HashTable<Thread *, HashObject *>(ExtractKeyFromHashObject,
- MyKeyToHashValue);
+Finally, if @code{@var{t}} is a pointer to a @code{struct thread},
+then we can insert it into the hash table with:
+
+@example
+hash_insert (&threads, &@var{t}->h_elem);
+@end example
If you have any other questions about hash tables, the CS109
and CS161 textbooks have good chapters on them, or you can come
You are welcome to modify it. It is not used by any of the code we
provided, so modifying it won't affect any code but yours. Do
-whatever it takes to make it work like you want it to.
-
-@item
-@b{Is the data segment page-aligned?}
-
-No.
+whatever it takes to make it work the way you want.
@item
@b{What controls the layout of user programs?}
@item Page Table Management FAQs
@enumerate 1
@item
-@b{How do we manage allocation of pages used for page tables?}
-
-You can use any reasonable algorithm to do so. However, you should
-make sure that memory used for page tables doesn't grow so much that
-it encroaches deeply on the memory used for data pages.
+@b{Do page tables need to created lazily?}
-Here is one reasonable algorithm. At OS boot time, reserve some fixed
-number of pages for page tables. Then, each time a new page table
-page is needed, select one of these pages in ``round robin'' fashion.
-If the page in use, clean up any pointers to it. Then use it for the
-new page table page.
+No. You can create the page tables at load time (or @code{mmap}
+time). Real OSes often manage their page tables lazily, but it's just
+an unneeded complication for our purposes.
@item
@b{Our code handles the PageFault exceptions. However, the number of
@enumerate 1
@item
-@b{Can we assume (and enforce) that the user's stack will
-never increase beyond one page?}
+@b{Does the virtual memory system need to support growth of the stack
+segment?}
+
+Yes. If a page fault appears just below the last stack segment page,
+you must add a new page to the bottom of the stack. It is impossible
+to predict how large the stack will grow at compile time, so we must
+allocate pages as necessary. You should only allocate additional pages
+if they ``appear'' to be stack accesses.
+
+@item
+@b{Does the first stack page need to be loaded lazily?}
-No. This value was useful for project 2, but for this assignment, you
-need to implement an extensible stack segment.
+No, you can initialize the first stack page with the command line at
+load time. There's no need to wait for it to be faulted in. Even if
+you did wait, the very first instruction in the user program is likely
+to be one that faults in the page.
@item
@b{Does the virtual memory system need to support growth of the data
previous years, but adds little additional complexity to a
well-designed system.
-@item
-@b{Does the virtual memory system need to support growth of the stack
-segment?}
-
-Yes. If a page fault appears just below the last stack segment page,
-you must add a new page to the bottom of the stack. It is impossible
-to predict how large the stack will grow at compile time, so we must
-allocate pages as necessary. You should only allocate additional pages
-if they ``appear'' to be stack accesses.
-
@item
@b{But what do you mean by ``appear'' to be stack accesses? How big can a
stack growth be? Under what circumstances do we grow the stack?}
projects / pintos-anon / blobdiff