COS 318 : Operating system Fall 2006, Princeton University Project 5: Virtual Memory

Important Dates

Introductory Precept: Tue 11/21, 3:00-4:00pm; Wed 11/22, 3:00-4:00pm
Design Review: Mon 11/27, 6:00-9:00pm
Second Precept: Wed 11/29, 8:30-9:30pm
Project Due: Tue 12/05, 11:59pm

To signup for the design review, please use online signup here.

Previous projects have used memory as a flat layout; this project will require you to implement a simple virtual memory mechanism in your operating system. Processes will now execute in separate virtual address spaces that are protected from each other. No process may access or modify data in another process' address space. The kernel will also be protected from processes in a similar manner. Additionally we now make a distinction between regular instructions and 'protected' instructions (i.e. certain instructions are enabled only in certain privelege levels). The x86 architecture has four privelege levels that can be used to enforce different levels of responsibility in the system. We will use only two of these levels, the kernel and the kernel threads will run in kernel mode (privilege level 0) and the processes will run in user mode (privilege level 3).

Your task in this project is to implement a simple, demand-paged virtual memory system with the USB disk. In order to accomplish this, you will need to do the following :

• Set up a two-level page table per process, the page table will also map (with proper protection) the entire address space of the kernel. Thus, all kernel threads share the same page table.
• A page fault handler for the faulting virtual page to allocate a physical page frame and fetch the virtual page from the USB disk.
• A physical page frame allocation scheme to allocate the physical page frame. When it runs out of physical page frames, it will trigger a random page replacement policy to evict a physical page frame to the USB disk.

You should use the code we sent to you "5_pre.tar.gz" as a starting point for your project. We have provided you with two main components to help you with the virtual memory implementation:

• The user and kernel protection mechanism.
• A USB disk driver that allow you to write to and read from a sector synchronously (see usb.h for more details).

There are now 39 files. Don't be daunted by the large number of files since you are already familiar with many of them, and the only files that need to be changed are memory.c and memory.h.

• Makefile : A makefile for you to compile with the right options.
• bootblock.s: Code for the bootblock of a bootable disk.
• cantboot.s: Code for the bootblock of a non-bootable disk.
• entry.S: Code for entry point of interrupts.
  
• common.h: Common constants, macros, and type definitions.
• createimage.c: Tool to create a bootable operating system image on a USB disk.
• interrupt.c: Interrupt handlers.
• interrupt.h: Header file for interrupt.c.
• kernel.c: Kernel code.
• kernel.h: Header file for kernel.c.
• keyboard.c: Keyboard handling code.
• keyboard.h: Header file for keyboard.c.
• mbox.c: The implementation of the mailbox mechanism.
• mbox.h: Header file for mbox.c.
• memory.c: Allocator for physical memory page frame, page-table handling, and virtual memory mapping.
• memory.h: Header file for memory.c.
• 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.
• scheduler.c: Scheduler code.
• scheduler.h: Header file for scheduler.c.
• shell.c: A primitive shell that uses the keyboard input.
• sleep.c: Contains function to allow processes to sleep for some milleseconds.
  
• sleep.h: Header file for sleep.c.
  
• syslib.c: System calls.
• syslib.h: Header file for syslib.c.
• 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.
• thread.c: Synchronization primitives.
• thread.h: Header file for thread.c.
• time.c: Time calibration.
  
• time.h:  Header file for time.c.
  
• usb.c: Code to access the USB disk.
• usb.h: Header file for usb.c.
• usbV86.S: Code for the USB disk driver.
  
• util.c: Library of useful support routines.
• util.h: Header file for util.c.

Since our entire project will be using the USB disk, please do not read/modify the hard disk.

Detailed Requirements and Hints

Before starting this project, you should read carefully Chapters 2-4 of the Intel Architecture Software Developer's Manual, Volume 3: System Programming Guide to understand the address translation mechanism so that you can understand how to set up the page tables. As discussed in class, x86 architectures use a two-level table structure with a directory page that has 1024 entries pointing to the actual page tables. You need to understand this structure very well.

In this project, you can make several assumptions and constraints to simplify your design and implementation:

• The USB disk is smaller than the physical memory on your PC. But we will assume that the total available physical memory is smaller that the total memory needed to run all the processes. This assumption will allow you to trigger demand paging. (So we set the PAGEABLE_PAGES to be 29 in memory.h)
• You can simplify the mapping between a virtual address space and the backing store space on the USB disk to avoid implementing a disk allocator. You can use the area allocated on the disk for the image file as the backing store for each process. You can assume that processes do not use a heap for dynamic memory allocation.
• You need to figure out how to initially map your physical memory page frames to run the kernel threads and how to load the code and data of a process into its address space. When the address space for the process is initialized, all the code and data pages for the process are marked as invalid. This will triggers the page_fault_handler() to run on the first access to any of these pages. At this time you can allocate a physical page frame and read in the page from the disk.
• Finally, you can assume that your virtual memory deals with only the data and code pages. All pages of the stack segments are "pinned," they will never be evicted by your page replacement mechanism. This means that you need to perform pinning when you initialize a process's address space. Also, you can assume that physical pages that are allocated to store the page-tables are pinned in memory and do not get paged. (You would need to implement "pinning" yourself.)

Extra Credits

There are one extra credit you can receive in this project.

You can receive 1/2 extra credit if you implement a FIFO replacement policy described in the class. You may receive another 1/2 extra credit point if you implement a FIFO with second chance replacement policy.

Design review

The best way to present your thoughts during the design review is to give us a brief summary of each of the functions in the templates that are missing and will be filled in by you. There is no need for actual C code here, just a few English sentences should suffice. (Please see the detailed grade split down in the next section.)

Before you come to meet the TA, you should prepare for a brief presentation on a piece of paper or on the screen.

Grading criteria

Design review: (one point for each item)

• how to allocate and pin pages.
• data structure for page_map_entry; Other global data structures needed.
• sketch for init_memory.
• sketch for setup_page_table.
• sketch for page_fault_handler.

Final project:

• init_memory(), initialize the vm for the kernel:  2 pts
• setup_page_table(), setup vm pagetable for application:  2 pts
• page_fault_handler(), handle page fault: 1.5 pts
• swap_in/out code, handle swap page in/out: 1.5 pts
• locking, handle mutual exclusion of operations: .5 pts
• page_replacememnt_policy, handles page replacement: .5 pts
• overall code (overall functioning of vm system): 2 pts