this project. You should also write programs to test the new features
introduced in this project.
+You will continue to handle Pintos disks and file systems the same way
+you did in the previous assignment (@pxref{Using the File System}).
+
Your submission should define @code{THREAD_JOIN_IMPLEMENTED} in
@file{constants.h} (@pxref{Conditional Compilation}).
been modified, the page must be first saved to disk before the needed
page can be brought in. Many virtual memory systems avoid this extra
overhead by writing modified pages to disk in advance, so that later
-page faults can be completed more quickly.
+page faults can be completed more quickly (but you do not have to
+implement this optimization).
@node Memory Mapped Files
@section Memory Mapped Files
Memory mapped files are typically implemented using system calls. One
system call maps the file to a particular part of the address space.
-For example, one might map the file @file{foo}, which is 1000 bytes
+For example, one might conceptually map the file @file{foo}, which is
+1000 bytes
long, starting at address 5000. Assuming that nothing else is already
at virtual addresses 5000@dots{}6000, any memory accesses to these
locations will access the corresponding bytes of @file{foo}.
A consequence of memory mapped files is that address spaces are
sparsely populated with lots of segments, one for each memory mapped
file (plus one each for code, data, and stack). You will implement
-memory mapped files for problem 3 of this assignment, but you should
-design your solutions to problems 1 and 2 to account for this.
+memory mapped files in problem 3-3. You should
+design your solutions to problems 3-1 and 3-2 to anticipate this.
@node Stack
@section Stack
segment).
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.
-You must devise a heuristic that attempts to distinguish stack
-accesses from other accesses. Document and explain the heuristic in
-your design documentation.
+time, so we must allocate pages as necessary. You should only allocate
+additional pages if they ``appear'' to be stack accesses. You must
+devise a heuristic that attempts to distinguish stack accesses from
+other accesses. Document and explain the heuristic in your
+design documentation.
The first stack page need not be loaded lazily. You can initialize it
with the command line at load time, with 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.
+Stack facts:
+
+@itemize
+@item
+The user program's current stack pointer is in the @struct{intr_frame}'s
+@code{esp} member.
+
+@item
+Only buggy user programs write to memory within the stack but below the
+stack pointer. This is because more advanced OSes may interrupt a
+process at any time to deliver a ``signal'' and this uses the stack.
+
+@item
+The 80@var{x}86 @code{push} instruction may cause a page fault 4 bytes
+below the stack pointer, because it checks access permissions before it
+adjusts the stack pointer. (Otherwise, the instruction would not be
+restartable in a straightforward fashion.)
+
+@item
+Similarly, the 80@var{x}86 @code{pusha} instruction, which pushes all 32
+bytes of the 8 general-purpose registers at once, may cause a page fault
+32 bytes below the stack pointer.
+
+@item
+Most OSes impose some sort of limit on the stack size. Sometimes it is
+user-adjustable.
+@end itemize
+
@node Problem 3-1 Page Table Management
@section Problem 3-1: Page Table Management
physical page frames. Consider using a hash table (@pxref{Hash
Table}).
-@item
-Some way of translating from physical page frames back to virtual page
-frames, so that when you evict a physical page from its frame, you can
-invalidate its translation(s).
+It is possible to do this translation without adding a new data
+structure, by modifying the code in @file{userprog/pagedir.c}. However,
+if you do that you'll need to carefully study and understand section 3.7
+in @bibref{IA32-v3}, and in practice it is probably easier to add a new
+data structure.
@item
Some way of finding a page on disk if it is not in memory. You won't
need this data structure until problem 3-2, but planning ahead is a
good idea.
+
+You can generalize the virtual-to-physical page table, so that it allows
+you to locate a page wherever it is in physical memory or on disk, or
+you can make this a separate table.
+
+@item
+Some way of translating from physical page frames back to virtual page
+frames, so that when you evict a physical page from its frame, you can
+invalidate its translation(s).
@end itemize
The page fault handler, @func{page_fault} in
@item
Locate the page backing the virtual
address that faulted. It might be in the file system, in swap,
-already be in physical memory and just not set up in the page table,
or it might be an invalid virtual address.
+If you implement sharing, it might even
+already be in physical memory and just not set up in the page table,
If the virtual address is invalid, that is, if there's nothing
assigned to go there, or if the virtual address is above
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}.
+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
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
@example
length = ROUND_UP (length, PGSIZE);
@end example
+(The @code{ROUND_UP} macro is defined in @file{<round.h>}.)
The remainder of this description assumes that this has been done.
If @var{length} is less than @var{fd}'s length, you should only map
-the first part of the file. If @var{length} is greater than
-@var{fd}'s length, when the file's length is also rounded up to the
-nearest multiple of the page size, the call should fail. Ideally it
-would extend the file, but our file system does not yet support
-growing files.
+the first @var{length} bytes of the file. If @var{length} is greater
+than @var{fd}'s length, when the file's length is also rounded up to a
+page multiple, the call should fail. Ideally it would extend the
+file, but our file system does not yet support growing files.
-If @var{length} is greater than @var{fd}'s unrounded length, then some
+If @var{length} is greater than @var{fd}'s (unrounded) length, then some
bytes in the final mapped page ``stick out'' beyond the end of the
-file. These bytes are set to zero when the page is faulted in from
-disk. They are discarded when the page is written back to disk.
+file. Set these bytes to zero when the page is faulted in from
+disk, and discard them when the page is written back to disk.
-Your VM system should be able to use the @code{mmap}'d file itself as
-backing store for the mapped segment. That is, if a page mapped by
+Your VM system should use the @code{mmap}'d file itself as
+backing store for the mapped segment. That is, to evict a page mapped by
@code{mmap} must be evicted, write it to the file it was mapped from.
(In fact, you may choose to implement executable mappings as a special
case of file mappings.)
@end itemize
As with @code{mmap}, @var{length} is treated as if it were rounded up
-to the nearest multiple of the page size
+to the nearest multiple of the page size.
It is valid to unmap only some of the pages that were mapped in a
previous system call.
projects / pintos-anon / blobdiff