Project 5: Virtual Memory
Project Due 11:59pm 12/2
Design Reviews on 11/26
TA in charge of this project: |
Aaron Blankstein (ablankst@cs.princeton.edu) |
Lab TAs in charge of this project: |
Michael Franklin |
| Ilias Glechaskiel |
Overview
Your previous kernels used a single global memory layout, where
the kernel and all processes shared access to the same memory,
and granted kernel permissions to all user processes.
Now, you will extend the provided kernel
with a demand-paged virtual memory manager and restrict user processes to
user mode privileges (ring 3) instead of kernel mode privileges (ring 0).
You will implement:
- virtual address spaces for user processes
- page fault handler
- page allocation
- paging to and from disk
As a result, each process will get its own address space and will not
be allowed to use certain instructions that could be used to interfere
with the rest of the system. Assuming the kernel and kernel threads
have no bugs/vulnerabilities, this will prevent buggy or malicious
processes from corrupting the kernel and other processes. Furthermore,
paging memory will allow programs to use more data than is available in RAM.
Aaron Blankstein is the TA in charge.
Important Dates
Design review: Monday 11/26
Project Due: Sunday 12/2 at 11:59pm
Finding Your Way Around this Project
The big stuff of this project is going to be in memory.c
and memory.h. The code for this project is a bit different
from the other projects so far (e.g., PCB structure is different.)
Don't Panic! It'll make sense to you if you look at it and
you won't actually need to mess with much of the code outside
of memory.[ch]
There are a bunch of constants hanging around these files that
you'll want to use:
$ grep "PROCESS_STACK" *.h
$ grep "PROCESS_START" Makefile
$ grep "PAGE" *.h
Note: this start code ships with its own bochs VGAROM and ROM. You
may have to edit the provided bochsrc to get it to point to the
right places... but it should be okay!
Design Review
This project will have, like the others, a design review worth 5 points. I'll ask
about the following things:
- Page table + Page Faults (2 points)
Explain how virtual addresses are translated to physical addresses on i386.
When are page faults triggered? How are you going to figure out what address a fault occurred on?
- Page Map (1 point)
You're going to need a data structure to track information about pages.
What information should you track?
- Calling Relationships (2 point)
For the functions page_alloc,
page_swap_in, page_swap_out, and
page_fault_handler, please describe the caller-callee
relationship graph.
Also,
you should read through the whole project description before
showing up to design review. Students missed points last time
around for questions with answers directly on the project description.
Page Table Setup
You must set up a two-level page table to map virtual to physical addresses,
as described in class and in your course textbook, for each
process. The i386 architecture uses a two-level table structure: one page
of memory is set aside as a directory that has 1024 entries pointing to the
actual page tables. Each of these page tables also has 1024 entries
describing pages of virtual memory.
You need to understand this
structure well.
That last statement needs to be reiterated. You will need to
understand what page table entries must look like. How are flags
set? How do you map a virtual address to a particular entry? How
do you store the physical page address for the entry?
The page directory of a task is determined
by
pcb->page_directory. You should set
that.
Kernel threads all share the same kernel address space and screen memory, so they can use
the same page table. Use
N_KERNEL_PTS (the number of kernel page
tables in the kernel page directory) to determine how many kernel
pages tables to make.
Each kernel page table should contain 1024 entries until
MAX_PHYSICAL_MEMORY has been mapped.
Notice that our initial values for you can all fit in one table. It's OK to map more than required (for example,
you can map the whole page table).
User process's virtual address space:
-
Map kernel and screen to their physical addresses ( virtual =
physical )
-
Map addresses for the process' code and data segments to its
own pages. Look at PROCESS_START and
PROCESS_STACK for an idea
of where in virtual memory everything resides. You should allocate
N_PROCESS_STACK_PAGES pages for a process stack.
- Kernel memory: inaccessible
- Screen memory: read-write
- Other memory: read-write
Implement
init_memory to initially map your
physical memory pages to run the kernel threads.
Implement
setup_page_table to load the code and data of
a user process into its virtual address space. However, you do not
need to load the process or allocate its pages right away. Instead,
prepare its virtual address space and mark all of the pages as
invalid. When the process is run and first accesses
its pages, a page fault will be generated and your handler will
automatically take care of allocating and loading the needed page.
Page Fault Handler
Write a page fault handler in
page_fault_handler to handle the case where
a process tries to access a page that is not currently in RAM.
The handler should:
- Allocate a page of physical memory.
-
Load the contents of the page from the appropriate swap
location on the USB disk. (How are you going to figure out the
swap location?)
-
Update the page table of the process.
page_fault_handler may be interrupted, which means
there might be two concurrent
page_fault_handler calls. Use the necessary
synchronization primitives to protect your data structures.
Page Allocator
Write a physical page frame allocator,
page_alloc, to prepare a free page of physical memory. If
there are free pages available, the job is simple: pick one.
Otherwise, you must choose one to page out to disk, using the policy implemented in
page_replacement_policy, and then reset
the page to be used again. For this assignment, any simple
replacement policy is acceptable.
Some pages may be so important or frequently used (or it might just
be more convenient for you) that they should never be paged out. For
example, you should never evict page tables. Such pages are
pinned.
Implement a mechanism for pinning pages so that they are never evicted by your
page allocator.
We can artificially limit the amount of physical RAM available to your OS by
setting
PAGEABLE_PAGES to some lower
number (try the 20s) in
memory.h. This way, the total
available physical memory is smaller than the total memory needed to run
all the processes, requiring the system to use your paging implementation.
This is a helpful value to change for testing.
You are probably going to want to clean the page at this
point. Doing it later will be hard!
Paging to/from Disk
If there are no more free physical pages for your page allocator to
allocate, you must choose a page to evict, writing it to disk
using
scsi_write:
implement
page_swap_out. You
also must page in from disk in
swap_in.
Check out the pcb variables
swap_loc and
swap_size. They will be
very helpful
You may assume that processes do not use a heap for dynamic
memory allocation: a process does not change size. In this case,
the user memory space of a process contains an interval
of
pcb->swap_size sectors starting from
PROCESS_START, plus the memory for user stack.
Note that you will need to flush the TLB (
tlb.h) appropriately for this project.
You will find the functions in
usb.h helpful for this part of the assignment.
Checklist
You'll have to do the following things for this project:
-
page_alloc()
- init_memory() to set up
the kernel pages and any other data structures your memory.c
code will be using.
- setup_page_table() to
set up the page table for a new task. For kernel threads, they
should use the pages
from init_memory(). For processes,
each process needs a different set of pages.
- page_fault_handler() and
page_swap_in()
With all of the above implemented, increase PAGEABLE_PAGES and
you should be able to run the test
-
Implement swapping pages out
with page_swap_out()
and page_replacement_policy().
Extra Credit
For 1 point of extra credit, implement a FIFO with Second Chance paging
policy. To test this, you can modify the loaded the processes,
threads, etc. If you're particularly clever, you can
test it by adjusting some of the constants in the memory.h and
then running process 3 and 4.
For 1 more point of extra credit, implement working set
tracking. Your paging policy should attempt to evict pages outside
of the current process' working set before pages within the
working set.
Submission
If you did not do extra credit, submit only:
- memory.h
- memory.c
- readme.txt
The readme should contain a very brief description of the state of your project (e.g. 'We think everything works.').
Submit via
dropbox; only
one person per group should submit (seriously guys.)
If you did the extra credit, include a extra credit readme file
(extra-readme.txt) describing how exactly you implemented extra
credit and how you tested it. Also include any files you changed, and any files
you added for testing.