COS 318 : Operating system
Fall 2004, Princeton University

Project 5: Virtual Memory

Important Dates:

Design review: Monday,  November 22
Due: 11:59 PM, Wednesday, December 1

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 the following :

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:

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.

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. We can decide whether we want to do oral presentation as in project 1,2 or the written design review as in project 3,4 during first precept. If we decide to use written format, you can still arrange time with me for the oral presentation if you  prefer that.

Grading criteria

Design review: (each item one point)

Final project:

Submitting Programming Assignments

Submit your final solution electronically using the following command:

/u/cos318/bin/318submit 5 README otherfiles ...

The submit command copies your files to the directory /u/cs318/submit/user/number and lists all the files that you have submitted for assignment number. user is your user account name. If you execute submit after the project deadline, your files are placed in directory number_late. You can run submit more than once, and you can submit partial lists of files. Note: You just need to submit the files that you have modified. (Eg: memory.h, memory.c, README.)

CS318 Staff