Project 5: Virtual Memory
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).
Your VMM 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. Furthurmore,
paging memory will allow programs to use more data than is available in RAM.
CJ Bell is the TA in charge.
Getting Started
Download the starter code.
Refer to previous projects for information on building and testing your
project.
We have already provided a
-
user and kernel protection mechanism (you just need to set the right
bits)
- USB driver
Project Files
Miscellaneous
common.h |
Common constants, macros, and type definitions |
createimage.c |
Tool to create a bootable operating system image on a USB disk |
Makefile |
A makefile for you to compile with the right options. |
util.c util.h |
Library of useful support routines |
Bootloader
bootblock.s |
Code for the bootblock of a bootable disk |
cantboot.s |
Code for the bootblock of a non-bootable disk |
Kernel
entry.S |
Code for entry point of interrupts |
interrupt.c interrupt.h |
Interrupt handlers |
kernel.c kernel.h |
Kernel code |
keyboard.c keyboard.h |
Keyboard handling code |
mbox.c mbox.h |
The implementation of the mailbox mechanism |
memory.c memory.h |
Physical memory page allocator, page table handling, and virtual memory mapping |
scheduler.c scheduler.h |
Scheduler code |
sleep.c sleep.h |
Contains function to allow processes to sleep for some milleseconds |
thread.c thread.h |
Synchronization primitives |
time.c time.h |
Time calibration |
usb.c usb.h |
Code to access the USB disk |
usbV86.S |
Code for the USB disk driver |
Threads
th.h |
Header file of th1.c and th2.c |
th1.c |
Code of the loader thread and the clock thread |
th2.c |
Code of two kernel threads to test synchronization primitives |
Processes
shell.c |
A primitive shell that uses the keyboard input |
syslib.c syslib.h |
System calls |
process1.c |
The first user process |
process2.c |
The second user process |
process3.c |
One of the processes to test the mailboxes |
process4.c |
The other process used to test the mailboxes |
Page Table Setup
You must setup a two-level page table to map virtual to physical addresses,
as described in class (REF) and in your course textbook (REF), 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.
Kernel threads all share the same kernel address space, so they can use
the same page table.
User process' virtual address space:
-
Map kernel and video memory to their physical addresses (virtual =
physical)
-
Map addresses above the kernel and video memory to different physical
addresses for each process: to the pages allocated to the process.
- Kernel memory: read-only
- Video memory: read-write
- Other memory: read-write
Implement
init_memory to initially map your
physical memory pages to run the kernel threads and
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 first run and on each first-access
of 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 backing store on the USB disk
-
Update the process' page table
Page Allocator
Write a physical page frame allocator,
allocate_page, 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, implemented in
page_replacement_policy, and then reset
the page to be used again.
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 they are never evicted by your
page allocator.
We artificially limit the amount of physical RAM available to your OS by
setting
PAGEABLE_PAGES in
memory.h to
29. 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 pagaing implementation.
This is a helpful value to change for testing.
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 a backing
store on disk: implement
swap_out. You
also must page in from disk in
swap_in.
You may simplify the mapping between virtual addresses and disk addresses
(the backing store) on the USB disk by mapping addresses in a process to
the process' location in the image file on disk. In other words, when a page
is paged-out of physical memory, write it back to the USB disk in the same
location it was loaded from.
Mind the boundary cases.
For this, you may assume that processes do not use a heap for dynamic
memory allocation: a process does not change size. Note that with this
approach, you will have to
cat the image to disk
each time you run the OS in order to reset the state of the programs.
Using this approach doesn't allow you to page out a process' stack because
it does not exist in the image. You may pin stack segments, so they are
never evicted, when you initialize each process' address space.
A better approach will earn you extra credit.
Checklist
Note: this is not intended to be a thorough list; just a quick
reference.
Functions to implement in
memory.h:
We only provide definitions for the functions above that other parts of the
kernel use.
Grading
The writeup should include:
-
A statement regarding the correctness of your project. Are there any
parts that you have not completed, that do not follow the specification,
or otherwise don't work? In what way? If a shortcoming you discuss
cascades into a disproportionate number of failures against test cases,
we may restore some credit. State if you believe your implementation to
be correct in all ways.
-
An overview of your design, modulo aspects that we discussed in the
design review.
Your writeup does not need to cover how to build and run your code; we
expect those details to remain the same.
We don't have strict rules concerning style; strive for clear code with
meaningful comments.
Extra Credit
FIFO Replacement Policy
For
0.5 points, implement the FIFO replacement policy described
in class. For an additional
0.5 points, implement the FIFO
with a second-chance replacement policy.
Paging
For
1 point, implement a backing store that doesn't overwrite
programs in the disk image, pages out stack pages instead of pinning
them, and finally, only writes back a page if it has been modified.
This extra credit will be due a few days after the main project