CSE 451 Assignment 3: Virtual Memory

In-class Design Review: Thursday, November 13, 2014
Design Due: Friday, November 21, 2014 at 9:00PM
Project Due: Monday, December 8, 2014 at 9:00PM
NOTE: At most one slip day may be used; everything is due no later than Tuesday, December 9, 2014
Post-Mortem Due: Tuesday, December 9, 2014 at 9:00PM

Objectives

Design a set of interfaces to implement a collection of functionality.
Become familiar with OS handling of TLB and page faults.
Develop a solid intuition about virtual memory and what it means to support it.

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 addition, while kmalloc() correctly manages sub-page allocations (i.e. memory requests for under 4KB), single and multiple-page requests are not properly returned to the system, meaning that address space pages are discarded after use, severely limiting the lifetime of your system.

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 paging—the mechanism by which memory pages of an active process can be sent to disk when memory is needed, and restored to memory when required by the program. This permits many processes to share limited physical memory while providing each process with the abstraction of a very large virtual memory. Finally, you will correctly handle page reclamation, allowing your system to reclaim memory when processes exit and (in theory, at least) run forever.

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.

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 and address space ID (unless the global bit is set in which case the address space ID is ignored) with the valid bit set.

Paging

The operating system creates the illusion of unlimited memory by using physical memory as a cache of virtual pages. Paging relaxes the requirement that all the pages in a process's virtual address space must be in physical memory. Instead, we allow a process to have pages either on disk or in memory. 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, the operating system must:

Allocate a place in physical memory to store the page;
Read 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 physical memory in which to place the new page, the space may already be occupied. In this case, the operating system must evict that other page from memory. If the page has been modified or does not currently have a copy on disk, then the old page must first be written to disk before the physical page can be reallocated. If the old page has not been modified and already has a copy on disk, then the write to disk can be avoided. The appropriate page table entry must be updated to reflect the fact that the page is no longer in memory.

As with any caching system, performance of your virtual memory system depends on the policy used to decide which things are kept in memory and which are evicted. On a page fault, the kernel must decide which page to replace. Ideally, it will evict a page that will not be needed soon. Many systems (such as UNIX) avoid the delay of synchronously writing memory pages to disk on a page fault by writing modified pages to disk in advance, so that subsequent page faults can be completed more quickly.

Your Mission

Implement the code that services TLB faults (part 1).
Add paging to your operating system (part 2).
Discuss how you can tune your TLB and page replacement algorithms (part 2).
Add the sbrk() system call, so that the malloc() we give you works (part 2).

Setup

Consult the ASST3 config file and notice that the arch/mips/vm/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 or kern/arch/mips/vm/mipsvm.c. Be sure to update the file kern/conf/conf.kern, or, for machine-dependent files, kern/arch/mips/conf/conf.arch, to include any new files that you create. Take care to place files in the "correct" place, separating machine-dependent components from machine-independent components.

You should be prepared to test your system with a range of memory sizes. In particular, you should be able to boot and run simple things using only 512 KB of memory. You should be able to run all the stress tests in 1 MB of memory. Of course, if you can run in 1 MB, you should also be able to run in more than that. So, during developing, you should set memory to 1 MB. Once you believe your system is running, make sure you can boot in 512 KB. Then try a range of memory sizes and workloads to make sure you avoid any odd behavior. In case you've forgotten, you can change memory size by editing sys161.conf file. Look for the line that says: ramsize. (Remember to submit your sys161.conf file with your assignment.)

Now, config an ASST3 kernel, run make depend, and build it. You are now ready to begin assignment 3; tag your repository asst3-start and push it with git push --tags.

Design Questions (graded separately)

Answer the following questions in a section of your design document called TLB Questions. As before, these questions are graded separately from the rest of the assignment.

Problem 1

Assuming that a user program just accessed a piece of data at (virtual) address X, describe the conditions under which each of the following can arise. If the situation cannot happen, answer "impossible" and explain why it cannot occur.

TLB miss, page fault
TLB miss, no page fault
TLB hit, page fault
TLB hit, no page fault

Problem 2

A friend of yours who foolishly decided not to take CSE 451, but who (inexplicably) likes OS/161, implemented a TLB that has room for only one entry, and experienced a bug that caused a user-level instruction to generate a TLB fault infinitely—the instruction never completed executing! Explain how this could happen. (Note that after OS/161 handles an exception, it restarts the instruction that caused the exception.)

Problem 3

How many memory-related exceptions (i.e., hardware exceptions and other software exceptional conditions) can the following MIPS-like instruction raise? Explain the cause of each exception.

  # load word from $0 (zero register), offset 0x120, into register $3
  lw  $3, 0x0120($0)

TLB Handling

In this part of the assignment, you will modify OS/161 to handle TLB faults. Additionally, you need to guarantee that the TLB state is initialized properly on a context switch. One implementation alternative is to invalidate all the TLB entries on a context switch. The entries are then re-loaded by taking TLB faults as pages are referenced. An alternative to invalidating everything is to use the 6-bit address space IDs and maintain separate processes in the TLB simultaneously.

We require that you have a separate implementation of the TLB entry replacement algorithm from the actual piece of code that handles the replacement. This will make it easy to experiment with different replacement algorithms if you wish to do so at some later point. Refer to the kernel config file section of Assignment 2 on how to add configuration options for TLB replacement policies.

Paging

In the main 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. Completing this part will probably require taking care of the following:

To start, you will need routines to move a page from disk to memory and from memory to disk.

You must decide how to implement a backing store (the place on disk where you store virtual pages not currently stored in physical memory). The default sys161.conf includes two disks; you can use one of those disks for swapping. It is simpler to swap to a raw disk and not to a file, but either is ok. Also, be sure not to use that disk for anything else! To help prevent errors or misunderstandings, please have your system print the location of the swap space when it boots.

You will need to store evicted pages and find them when you need them. You should maintain a structure (e.g., a bitmap) that describes the space in your swap area. Think of the swap area as a collection of chunks, where each chunk holds a page. You need to keep track of which chunks are full and which are empty. The empty chunks can be evicted into. You also need to keep track, for each page of a given address space, of which chunk in the swap area it maps onto. When there are too many pages to fit in physical memory, you can write (modified) pages out to swap.

When the time comes to bring a page into memory, you will need to know which physical pages are currently in use. 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 the virtual address and address space identifier for the virtual page currently backed by the page in physical memory. When you need to evict a page, you look up the physical address in the core map, locate the address space whose page you are evicting and modify the corresponding state information to indicate that the page will no longer be in memory. Then you can evict the page.

If the page is dirty, it must first be written to the backing store. In some systems, the writing of dirty pages to backing store is done in the background by a daemon. As a result, when the time comes to evict a page, the page itself usually clean (that is, it has been written to backing store, but not modified since then). You don't have to design and implement this functionality in your system, but if you do it'll be really cool. Should you decide to do this, you will need to create a thread that periodically examines pages in memory and writes them to backing store if they are dirty.

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.

You will need to implement one page replacement policy for ASST3. You may implement others if you choose, making them configurable in the same vein as the TLB replacement algorithm.

Testing malloc() and free()

Now that OS/161 has paging, you can support applications with larger address spaces. The malloc() and free() library functions are provided in the standard C library. Read the code and answer the following questions in a section called Malloc Questions within your design document.

Question 1. Consider the following (useless) program:

/* This is bad code: it doesn't do any error-checking */
#include <stdio.h>
int main (int argc, char **argv) {
    int i;
    void *start, *finish;
    void *res[10];
    start = sbrk(0);
    for (i = 0; i < 10; i++) {
         res[i] = malloc(10);
    }
    finish = sbrk(0);
    /* TWO */
    return 0;
}

How many times does the system call sbrk() get called from within malloc()?
On the i386 platform, what is the numeric value of (finish - start)?

Question 2. Suppose that we now insert the following code at location /* TWO */:
```
{
    void *x;
    free(res[8]); free(res[7]); free(res[6]);
    free(res[1]); free(res[3]); free(res[2]);
    x = malloc(60);  /* MARK */
}
```
Again on the i386, would malloc() call sbrk() when doing that last allocation at the marked line above? What can you say about x?
Question 3. It is conventional for libc internal functions and variables to be prefaced with "__". Why do you think this is so?
Question 4. The man page for malloc requires that "the pointer returned must be suitably aligned for use with any data type." How does our implementation of malloc guarantee this?

Note that the operation of malloc() and free() is a standard job interview question—you should understand this code!

You are responsible for making the malloc() we give you work; this will involve writing an sbrk() system call.

Design and Analysis of Performance Optimizations (Extra Credit)

If you have time, you may add more features to your virtual memory system for extra credit. Please do not spend any time on this until the basic functionality works. For example, you may implement copy-on-write for improving the performance of fork, or fetch-on-demand for improving the performance of exec.

Another extra credit option is to design and evaluate a better policy for TLB replacement and page replacement. These algorithms should be carefully considered, offering robustness against excessive blocking and thrashing across a variety of workloads. Add a section to your design document (which you can update as you implement ASST3), with a description of your algorithms' performance behaviors and characteristics, and how you have guarded against antagonistic memory access patterns. Additionally, give a thorough discussion on how you would perform instrumentation on your design to measure its performance, and from these reported statistics, discuss what parameters you would tune in your policies. Instrumentation will undoubtedly require the use of some additional software counters. As a start, we suggest:

The number of page faults.
The number of TLB faults.
The number of page faults that require a synchronous write of a page.

What other statistics would prove useful in tuning your system?

Selecting proper workloads for testing is critical in order to tune for performance. At a minimum, the matmult and sort programs provided are useful workloads for determining your baseline performance prior to tuning. Predict what will happen as you change parameters in your algorithms on these workloads, and provide a discussion on the likely causes if you were to observe discrepancies when comparing your predicted results to reported measurements. Obtaining a different result from what you expect might indicate a bug in your understanding, a bug in your implementation, or a bug in your testing; list the plausible locations in your design for these bugs.

In your discussion on experiment-based tuning, we suggest that you consider tuning the TLB and paging algorithms separately and then together. You may not consider rewriting the matmult program to improve its performance, but you should provide a plan to add other test programs to your benchmarking suite. Otherwise, your system might perform well at matrix multiplication and sorting, but little else. Try to introduce programs with some variation in their uses of the memory system.

Add to your design document a thorough explanation of the performance benefits of your optimized TLB and paging algorithms. Also, provide a complete summary of the performance analysis you would conduct to tune these algorithms in the future. Finally, answer the following question in a section called TLB and Paging Algorithms.

Question: How will you structure your code (where will you place your TLB and paging algorithms) so that others can be added trivially, and switching between them only requires reconfiguring your kernel?

Design Submission

As with Assignment 2, we will be conducting peer design reviews in section, on November 13. You should have an initial version of your design document complete by then. Bring three hard copies of that design to class and commit that design to your team repository (in the directory os161/submit/asst3). After the peer review, make any changes to your design document and note what you have changed, then push again to your repository.

By Friday, November 21, at 9:00 pm, please submit your design document to catalyst. Your design document submission must include:

Answers to the written problems above in sections called TLB Questions and Malloc Questions. Include the section TLB and Paging Algorithms if you decide to attempt the extra credit.
How you are going to add paging and TLB handling. Include an integration plan (how your code fits into the existing framework) and details on bootstrap. Be sure to include a description of any new data structures you need. Discuss the extensions your design will need to make for address spaces, kmalloc(), swapping, your paging daemon, etc.
A description of the TLB and paging algorithm(s) that you will implement.

As usual, your design document is worth 30% of your assignment grade.

Implementation Submission

Part 1 (TLB) and part 2 (demand paging) are both due 9:00 pm on December 8. For part 2, you will need to run with less memory, so that a process can run even though all of its code and data are not in memory. The turnin should include:

All the code and kernel config files you added or modified to support TLB and page faults.
Your revised design document, named design_document.*, with an extension of pdf, txt, or md.
A script of your operating system running the matmult program, named matmult.script.
Your sys161.conf file.

Any non-code or conf files should be placed in the directory submit/asst3 in your os161/ toplevel directory.

You should submit by tagging your repo with asst3-submit, and then pushing your final working copy of your source along with your tags to your team git repository. Refer to Assignment 2 if you need a refresher on how to submit.

Strategy

The first step is understanding how TLB and page faults occur. To make this task easier, consider having one person in your group study TLB faults and the other study page faults.

The time required to implement page fault handling is longer than the time required to implement TLB fault handling. We have structured the assignment so that you can get the TLB handling done first. Assume that there is enough memory for all processes to fit in memory at the same time, so the only challenge is loading the TLB. Then divide the virtual memory implementation into several small and well-defined modules so that you can work on it together once you have completed the TLB implementation. Get together as early as possible to share what you each have discovered.

Look at the the code exception-mips1.S to see how TLB faults are handled. Then examine the vm_fault() handler in kern/arch/mips/vm/dumbvm.c. What changes must you add to support TLB and page faults?

Some of the key issues are:

What will your page tables look like?
What should you put in each PTE (page table entry)?
What will your core map (or reverse page table) look like?
In what order can TLB faults and page faults occur? For example, can a page fault occur without causing a TLB fault?

When you have completed your initial implementation of the TLB and paging algorithms, begin testing for correctness with matmult and the other provided tests. If you have divided up coding responsibilities, do your best to break your partner's implementation, then help him/her fix it. Think about verifying that your replacement algorithms are working correctly by writing test programs (i.e., "If I run this program it should generate exactly n TLB faults with your algorithm; does it?").

As your system begins to stabilize, consider and discuss opportunities for performance tuning. Continue to test and fix bugs. Take turns testing and tuning.