Project 5: Virtual Memory


Overview

In this fifth project, you will add memory management and support for virtual memory to the kernel.

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:

Specifically, it will be your job to modify memory.h and memory.c.

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.

We also provide six test programs (process[1-4].c and th[1-2].c) that automatically test your memory manager when built. See Testing for instructions on how to use these tests.

Finding Your Way Around this Project

The code for this project is a bit different from the other projects so far (e.g., PCB structure is different.) Don't Panic! You will need to look at kernel.[ch] and tlb.h to find useful data structures and functions. The test processes and kernel show you how your memory manager will be used.

There are many constants in 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.

The start code is available on the lab machines at /u/318/code/project5/p5_start_code.tar.gz


Steps

  1. Review project specs and download the start code.
  2. Write your design review (due Monday Dec 5, 2016)
  3. Complete memory.h, and memory.c
  4. Compile and build the disk image.
  5. Test Run the Bochs emulator and play with the small shell program.
  6. Complete the general project requirements
  7. Submit

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? Make use of the provided functions init_ptab_entry(), insert_ptab_dir(), and set_ptab_entry_flags() when setting page table entries, page directory entries, and page entry flags.

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 page tables to make. Each kernel page table should contain PAGE_N_ENTRIES (1024) entries, until the page base address of a page reaches MAX_PHYSICAL_MEMORY.

Notice that our initial values for the constants given in memory.h can all fit in one table. It's OK to map more than required (for example, you can map the whole page table).

Implement init_memory() to initially map your physical memory pages to run the kernel threads.

User process's virtual address space:

Implement setup_page_table() to load the code and data of a user process into its virtual address space. You will need to allocate its pages and load the process. The page directory of a task is determined by pcb->page_directory. This needs to be set when you're setting up the page tables.

There are two more things that you will need to set up the address space and that will help you with keeping track of page mappings:


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 (e.g. FIFO).

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.

Note: You will probably want to clear the page at this point. Doing 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() in scsi.h: implement page_swap_out(). You also must page in from disk in page_swap_in().

Check out the PCB fields swap_loc and swap_size. They will be very helpful here.

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: This is a good place to make sure that you are flushing the TLB appropriately.

You will find the functions in scsi.h helpful for this part of the assignment.


Page Fault Handler

You will need to 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:

page_fault_handler() may be interrupted, which means there might be two concurrent page_fault_handler() calls. You will want to use some synchronization primitives to handle this.


Testing

Unlike project3, which could be broken down into several phases for testing, you will need to understand and implement project 5 in its entirety before you can test your work.

This will be frustrating, but Don't Panic! The test processes that are part of the start code and are built into the disk image upon compilation should demonstrate where your problems lie.

To test your project 5, simply make your code, and run with Bochs. Note: Don't waste time trying to test your work on a real machine using a USB drive.


Design Review

As always, please take a look at
what we expect from you in general.

This project will have, like the others, a design review worth 5 points. You will be asked about the following things:

Also, you should read through the whole project description before showing up to design review. Students missed points last time for questions with answers directly on the project description.

Each group must schedule a 10-minute design review slot. The review will take place on Monday, December 5th.

Some tips:

To sign up for a design review, use our signup page.


Hints and FAQs

HINTS FROM 2013: (use as you wish)

Checklist

Here is a checklist to help you complete this project. Implement the functions roughly in this order:

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 the Not Recently Used Page Replacement Algorithm. If a page is not modified, you should not write it back.


Program Submission

Don't forget to complete the general requirements for each project! In particular, you need to submit a README file, which concisely describes your design and implementation, and what parts work and what parts you didn't get to work. You don't have to repeat anything you presented in the design review.

Submit via Dropbox; only one person per group should submit. When submitting the assignment, please turn in the files specified in the Dropbox, along with your readme (less than 500 words in text format).