CS350 - University of Waterloo

David R. Cheriton School of Computer Science
University of Waterloo

CS 350. Operating Systems

Assignment 3: An Introduction to Virtual Memory
Last Modification: Mon Nov 12 15:02:43 EST 2007

Note: we will create, maintain and modify a web page of hints for this assignment. It will be located at the same location as the hints for Assignment 2. In this case the file name will be a3-hints.html instead of a2-hints.html.

Introduction

You have improved OS/161 to the point that you can now run user processes. However, there are a number of shortcomings in the current system. A process's size is limited by the number of TLB entries (i.e., 64 pages). In this assignment we will adapt OS/161 to take full advantage of the simulated hardware by implementing management of the MIPS software-managed Translation Lookaside Buffer (TLB). You will write the code to manage this TLB. You will also write the code to implement the paging in of user process memory pages (BUT NOT PAGING OUT OR PAGE REPLACEMENT). In this way only the pages that are actually touched by an application will be paged into memory. You will also NOT be required to implement page reclamation when a process finishes and you will NOT be required to fix kfree, etc. to return unused memory back to the kernel heap. Hopefully when you are finished implementing this assignment we should be able to:

Run a program that has a large virtual address space but does not touch all of the pages in that address space (because your OS will implement demand paging). Currently this can not be done if the address space is larger than the amount of free physical memory available.
Run a program that uses/touches more than 64 pages of memory (because your OS will by implementing TLB replacement). Currently the kernel is unable to run programs that use more than 64 pages of memory because it doesn't implement TLB replacement.
Ultimately, be able to run all of the tests in a2-test-scripts that you were able to run after A2 was completed (but this will be an optional part of the assignment).

We will provide you with a testing infrastructure similar to what was provided for A2 via the assignment web page. Your goal will be to be able to run the tests using the infrastructure we provide.

The testing for this assignment will only use one process but your design and implementation for this assignment should cover multiple processes. The A3 hints page will also provide instructions for how to create a kernel that will implement versions of writing to the console and _exit that should allow you to run the A3 test without having all of the system calls from A2 working.

Structure of the TLB entries

In the System/161 machine, each TLB entry includes a 20-bit virtual page number and a 20-bit physical page number as well as the following five fields:

global: 1 bit; if set, ignore the pid bits in the TLB.
valid: 1 bit; set if the TLB entry contains a valid translation.
dirty: 1 bit; enables writing to the page referenced by the entry; if this bit is 0, the page is only accessible for reading.
nocache: 1 bit; unused in System/161. In a real processor, indicates that the hardware cache will be disabled when accessing this page.
pid: 6 bits; a context or address space ID that can be used to allow entries to remain in the TLB after a context switch.

In this assignment the global and pid bits will also be unused. Therefore, all valid entries in the TLB will correspond to only one address space.

All these bits/values are maintained by the operating system. When the valid bit is set, the TLB entry contains a valid translation. This implies that the virtual page is present in physical memory. A TLB miss occurs when no TLB entry can be found with a matching virtual page.

Paging in On Demand

In Assignment 2 OS/161 allocates physical memory for, and properly initializes all of the segments in the virtual address space of the process (using load_elf to copy those parts of the executable file that need to be copied into memory).

In this assignment you will modify OS/161 so that it only allocates memory frames and initializes those pages that are actually referenced during the execution of the user program. When the process issues an access to a page that is on disk, a page fault occurs. The operating system must retrieve the page from disk and bring it into memory. Pages with valid TLB entries are always in physical memory. This means that a reference to a page on disk will always generate a TLB fault. At the time of a TLB fault, the hardware generates a TLB exception, trapping to the operating system. The operating system then checks its own page table to locate the virtual page requested. If that page is currently in memory but wasn't mapped by the TLB, then all we need to do is update the TLB. However, the page might be on disk. If this is the case, a logical description (the details will be slightly more complex) of what the the operating system must do is:

Allocate a place in physical memory to store the page;
Copy the page from disk,
Update the page table entry with the new virtual-to-physical address translation;
Update the TLB to contain the new translation; and
Resume execution of the user program.

Notice that when the operating system selects a location in the TLB in which to place the new translation, it first tries to find an unused TLB entry. However, if all entries are used, the operating system must evict/replace one of the translations in the TLB. You should implement a very simple (but dumb) round robin TLB replacement policy.

// Initialized to NUM_TBL so the first entry evicted will be 0.
int victim = NUM_TLB;

// Just implements a simple round robin replacement
victim = (victim + 1) % NUM_TLB;

You will be tracking and printing several statistics related to the performance of the virtual memory sub-system (including TLB misses and TLB replacements) so be certain to implement this as described so we can easily examine and compare these statistics.

Your Mission

Implement the code that services TLB faults.
Add code to handle the on demand paging in of referenced pages.
Ensure that read-only pages like the .text and .rodata sections can not be written to by user programs.

Setup

Consult the ASST3 config file and notice that the arch/mips/mips/dumbvm.c file will be omitted from your kernel. You will undoubtedly need to add new files to the system for this assignment, e.g., kern/vm/vm.c. This means that your kernel will not be able to run user programs until you fix this (in fact it may not even compile properly?). Be sure to update the file kern/conf/conf.kern to include any new files that you create and to (re)configure your kernel to add them to the Makefile.

Remember to config an ASST3 kernel, run make depend, and build it. Note that until you actually implement the virtual memory sub-system you won't actually be able to run any user programs.

Each time you modify kern/conf/conf.kern you need to reconfigure and recompile the kernel.

cd $HOME/cs350-os161/os-161.1.11/kern/conf
./config ASST3
cd ../compile/ASST3
make depend
make

Note that whenever you add new include files it is useful to run make depend to ensure that all of the dependencies are included and the necessary files will be recompiled if you modify a .h file.

Demand Paging

In this part of the assignment, you will modify OS/161 to handle page faults. When you have completed this problem, your system will generate an exception when a process tries to access an address that is not memory-resident and then handle that exception and continue running the user process.

You will need routines to move a page from disk to memory (because we are not implementing page out you do not have to worry about moving a page from memory to disk).

When the time comes to bring a page into memory, you will need to know which physical pages are currently in use and which are available. One way to manage physical memory is to maintain a core map, a sort of reverse page table. Instead of being indexed by virtual addresses, a core map is indexed by its physical page number and contains information about the virtual page number and address space that is occupying each frame.

Your paging system will also need to support page allocation requests generated by kmalloc(). You should review kmalloc() to understand how these requests are generated, so that your system will respond to them correctly.

Statistic Instrumentation and Reporting

I will make some code available to make it easier to track and print these statistics and to ensure that the output looks the same in all kernels. Watch the newsgroup and the assignment web page for this code.

You should collect and print (as the last thing vm_shutdown() does) the following statistics using the provided headings/names related to the performance of your virtual memory system.

Name = "TLB Faults": The number of TLB faults

Name = "TLB Adds": The number of TLB adds (times an entry was added to the TLB, i.e., calls to TLB_Write)

Name = "TLB Adds with Free": The number of TLB adds where there was a free entry available (i.e., when adding an entry to the TLB no replacement was required)

Name = "TLB Adds with Replace": The number of TLB adds where a TLB replacement was required

Name = "TLB Invalidations": The number of times the TLB was invalidated

Name = "TLB Reloads": The number of TLB reloads (TLB faults that did not require a page fault)

Name = "Page Faults (Zeroed)" : The number of Page Faults that did not require a disk copy.

Name = "Page Faults (Disk)": The number of Page Faults that required a disk copy (e.g., loading a text/code page)

Notes:
(1) Page Faults (Disk) + Page Faults (Zeroed) = the number of actual page faults.
(2) TLB Adds with Free + TLB Adds with Replace = TLB Adds
(3) TLB Reload + Page Faults (Zeroed) + Page Faults (Disk) = TLB Faults

Here is an example of what the output should look like. Note that it is the last thing that OS/161 prints. Please ensure that each line starts with VMSTAT so we can easily search/grep for them (better yet please use the code that will be posted for tracking and printing these stats).

VMSTAT                TLB Faults =       3586
VMSTAT                  TLB Adds =       3586
VMSTAT        TLB Adds with Free =         64
VMSTAT     TLB Adds with Replace =       3522
VMSTAT         TLB Invalidations =          1
VMSTAT               TLB Reloads =       3072
VMSTAT      Page Faults (Zeroed) =        513
VMSTAT        Page Faults (Disk) =          1
The system is halted.
sys161: 139271032 cycles (55872564k, 82003147u, 1395321i)
sys161: 1295 irqs 1965 exns 0r/0w disk 0r/1141w console 10r/0w/2m emufs 0r/0w net
sys161: Elapsed real time: 9.942065 seconds (14.0083 mhz)
sys161: Elapsed virtual time: 5.570841280 seconds (25 mhz)

What to hand in

Design Document Be sure that your design document is named design.pdf and is placed inside of the directory os161-1.11. This document is limited to 4 pages NOTE: That although the non optional test programs for this assignment can be run with only one process, you must ensure that you keep track of the segments and page tables of each address space and that your design assumes that multiple processes can and will be executed. That is, DO NOT create a design and implementation that uses only one global data structure for segments and page tables.

Please organize your design document with the following sections and in each section be sure to include the information requested.

Free Page Frames (Coremap)

In this section you should explain how you keep track of and maintain information about free page frames. Be sure that this section discusses at least the following issues:
- What information do you keep track of?
- Why do you keep track of that information?
- How do you keep track of that information?
- What are the synchronization issues if any?
- How do you mark the initial kernel pages as used and how do you find free frames when they are needed as a result of a kmalloc call.
  What were the tricky issues in solving this problem and how did you resolve them?
Segments:

In this section you should explain how you keep track of and maintain information about the segments of an address space. Be sure that this section discusses at least the following issues:
- What information do you keep track of?
- Why do you keep track of that information?
- How do you keep track of that information?
- What are the synchronization issues if any?
- ALSO: Describe how you determine which segment a virtual address belongs too?
Page Tables:

In this section you should explain how you track and maintain the page tables required by each address space. Be sure that this section discusses at least the following issues:
- What information do you keep track of?
- Why do you keep track of that information?
- How do you keep track of that information?
- What are the synchronization issues if any?
- Describe how you determine which page table entry a virtual address belongs too?
- Which pages are loaded into memory from disk and which are not? How and when?
- Assuming a multiprogrammed environment you must ensure that no process is able to read any data/information from another process. Explain how you ensure this.
TLB Management:

In this section you should explain how you manage the TLB. Be sure that this section discusses at least the following issues:
- When and how are entries added to the TLB?
- When, how, and why is the TLB invalidated?
- When, how, and why does a TLB entry need to be replaced?
- What are the synchronization issues if any?
- How does the kernel know when a TLB replacement must occur?
- In two sentences explain what is wrong with the Round-Robin replacement and in two more sentences describe a better algorithm that could be easily implemented in OS/161.
Write Protecting Pages:

Describe why and how your write protect .text and .rodata pages and how and why all other pages are not write protected. What are the synchronization issues if any?
Address Space Copy:

In order for a fork system call to work, the function as_copy is required. Describe how your virtual memory subsystem accommodates as_copy and describe how you would implement as_copy. What are the synchronization issues if any? Note: that you are not required to implement as_copy unless you are doing the optional parts of the assignment but you do need to describe how you would implement it.
Integration Plan:

Describe an integration plan (how your code fits into the existing framework). Be sure to describe when and how the various data structures above fit in with this plan.
Other Information:

Place any other information about your design that we should know about in this section.

Submitting

cd $HOME/cs350-os161
submit cs350 3 .

If the assignment is being submitted after the due data and before your slip days are used up

cd $HOME/cs350-os161
submit cs350 3 -t .

Strategy
In addition to this information we will provide some information about how to get started on the A3 Hints web page.

Read over the requirements for the design document. The structure, and content should provide many hints for what you will need to do for this assignment.

Start thinking about the data structures described in the design document section and how and where they will fit into the various parts of the existing kernel.

Examine the code in the vm_fault() handler in kern/arch/mips/mips/dumbvm.c. Think about what changes must you add to support TLB and page faults? NOTE that you will not be modifying/using the code in dumbvm.c but you should think about using parts of it as a basis for implementing your fault handler in (a file of your choosing e.g., kern/vm/vm.c).

Examine the code in kern/vm/addrspace.c. Note that the functions are not implemented yet. Study and understand what the equivalent functions in kern/arch/mips/mips/dumbvm.c do and start to plan how and why those functions will be different in kern/vm/addrspace.c.

Examine and understand what the code in kern/userprog/loadelf.c is doing and why. While doing this keep in mind that your kernel needs to be modified to only page in pages that are actually touched during execution. Think about what parts of the various functions in this file you might want to keep, what parts you might want to modify and what additional support you might need.

Be sure that you understand the statistics, how when when they will be tracked, and the differences between them.

See the marking report document so you can determine where to best spend your time to maximize your grade and which test programs you should be able to run when you are finished with this assignment.