CSC 369S | Assignment 2 | Spring 2007

Assignment 2: Virtual Memory

Due 11:59pm Monday, March 26

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, you are given most of the implementation of a virtual memory system for OS/161. You are given the code that manages the MIPS software-managed Translation Lookaside Buffer (TLB). You are also given most of the code that implements 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.

A2 Starter Code

You have been given a new branch of the initial OS/161 source code from the trunk of your repository. The solutions to A0 and A1, as well as the new starter code for A2 have been added to this branch. You are welcome to replace any of the sample solution code with your own solutions (for example, if you prefer your own version of the dbflags command).

The command to check out your a2 branch is (XX is your group number):

        svn co https://stanley.cs.toronto.edu/svn/csc369-2007-01/<groupXX>/branches/a2-branch

Here is a brief synopsis of the new files:

• kern/vm/vmobj.c - code to manage "virtual memory objects", which define regions of a process's virtual address space
• kern/vm/lpage.c - code to manage "logical pages", the structure that describes each page of the virtual address space
• kern/vm/swap.c - code to manage the swap area, providing functions to move pages between disk and main memory
• kern/vm/addrspace.c - not new, but completely rewritten to set up and manage a process's virtual address space using the new vmobj and lpage structures
• kern/arch/mips/mips/vm.c - machine dependent part of virtual memory management; this is the starting point when a TLB miss exception occurs
• kern/arch/mips/mips/coremap.c - machine dependent part of memory management responsible for the allocation / reclamation of physical pages of memory.
• kern/test/coremaptest.c - test of the existing coremap functions

Assignment Tasks

Your mission is to implement the missing functions in kern/vm/lpage.c and in kern/arch/mips/mips/coremap.c:

• lpage_fault --- this function handles a page fault (note until you implement this function you won't be able to run test programs).
  
• lpage_evict --- this function evicts an lpage from physical memory.
• do_evict -- this function is called when a page is to be evicted from physical memory.
• do_page_replace --- this function does some set up and then calls one of the page_replace methods.
• page_replace --- you will write two versions of this page replacement function, one that uses a random page replacement algorithm, and one that implements some form of LRU.

        #if OPT_RANDPAGE

        /* Random page replacement */
        static
        u_int32_t
        page_replace(void)
        {
            ...
        }

        #else

        /* LRU-style page replacement */
        static 
        u_int32_t
        page_replace(void)
        { 
            ...
        }
        #endif

Your LRU-type algorithm should be based on the clock algorithm covered in lecture. In order to implement the clock algorithm, you will need to add additional fields to some of the VM data structures to track whether a given page has been referenced since the last time the clock hand has passed. Your algorithm should be tunable in some way so that you can experiment to see how varying parameters of the algorithm influences performance.

You need not worry about giving preference to clean pages over dirty ones in your page replacement algorithm.

You will probably spend more time reading the new starter code to figure out the structure of the VM system provided than actually writing the required function implementations. The hardest part of the assignment may be getting the synchronization right.

Information about the structure of the code

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 (this bit is not used in ASST2, you may leave it as 0)
  
• 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 data and instruction caches 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.  For this assignment, you may ignore the pid field; the fields related to it (TLBLO_GLOBAL and TLBHI_PID) can be left as zero values.

All these bits/values are maintained by the operating system (not by the h/w). 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

As covered in the lecture notes, the kernel 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 a process tries to access a page that is on disk (and not in physical memory), a page fault occurs. The kernel must retrieve the page from disk and load it into memory. Pages with valid TLB entries are located in physical memory. This means that a reference to a page on disk (and not in memory) will always generate a TLB fault. At the time of a TLB fault, the hardware generates a TLB exception, trapping to the kernel. The operating system then checks its page table to locate the virtual page requested. If that page is currently in memory but wasn't mapped by the TLB, then the kernel need only update the TLB. However, if the page is on disk, the kernel must:

1. Allocate a frame in physical memory to store the page;
2. Read the page from disk;
3. Update the page table entry with the new virtual-to-physical address translation;
4. Update the TLB to contain the new translation; and
5. Resume execution of the user program (at least put it on the ready queue).
   

Notice that when the operating system selects a location in physical memory in which to place the new page, that location may already be occupied by another page. In this case, the operating system must evict that other page from memory. If the page has been modified or is not present in the swap area on disk, then the page being evicted must be written to disk before the physical page can be reallocated to the new page (the one that generated the page fault above). If the page being evicted has not been modified and is already present in the swap area on disk, then the kernel can avoid writing the page to disk, but the appropriate page table entry still must be updated to reflect the fact that the evicted 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 operating 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.

Setup

Consult the ASST2 config file and notice that the arch/mips/mips/dumbvm.c file will be omitted from your kernel.  Be sure to update the file kern/conf/conf.kern, or, for machine-dependent files, kern/arch/mips/conf/conf.arch, if you create any new files. Take care to place files in the "correct" place, separating machine-dependent components from machine-independent components.

You will notice that if you try to boot your kernel with more memory than is compatible with your swap disk, the kernel will refuse to boot.  There are two ways to deal with this, you can either restrict your physical memory to 512 KB by setting the ramsize line in your sys161.conf file, or you can use a larger ramsize value and also increase the size of your swap disk in your sys161.conf file.
Note that both the cache code from A1 and the new swap code in A2 use lhd0 for disk storage. You should change one or the other to use the second disk device, or simply be careful NOT to run the cache tests during this assignment, since it will trample on anything that has been placed in the swap area.

Now, config an ASST2 kernel, run  make depend, and build it. You are now ready to begin Assignment 2.  Remember to do all your work in the a2-branch of your repository.

TLB Question

The following question will be discussed in tutorial.  As was the case for code review questions in assignment 2, you should make a serious attempt to answer them ahead of time so that you can understand the solutions provided.

Assuming that a user program just tried to access 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

TLB Handling

There are several implementation alternatives to TLB handling. You should read through the code to understand which approach the starter code takes. The system must 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. If this approach were taken, relevant state maintained by the TLB entries would have to be copied back into the page table before invalidating the entries. (For example, in order for the paging algorithm to know which pages must be written to disk before eviction, the information about whether a page is dirty or not must be properly propagated back into the page table.) An alternative to invalidating everything is to use the 6-bit address space IDs and maintain separate processes in the TLB simultaneously.

Note that the implementation of the TLB entry replacement algorithm is separated from the actual piece of code that handles the replacement. This makes it easy to experiment with different replacement algorithms.

Paging

In this part of the assignment, you will write the function that handles page faults (lpage_fault). When you have completed this problem, your system will be able to handle the exception that is generated when a process tries to access an address that is not memory-resident. After handling the exception, the system can continue running the user process.

You are given the functions to move a page from disk to memory and from memory to disk (see kern/vm/swap.c).

How is backing store implemented? (Backing store is the place on disk where you store virtual pages not currently stored in physical memory - i.e. swap space). How are evicted pages stored and how are they found when needed?

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. 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).

The file kern/arch/mips/include/coremap.h defines the coremap data structure which tracks the use of physical memory pages (implemented in kern/arch/mips/mips/coremap.c).

Your paging system must support page allocation requests generated by kmalloc(), as well as from user programs. You should review kmalloc() to understand how these requests are generated, and understand how the code in coremap.c responds to them, so that your system will deal with kernel pages correctly when doing replacement.

You should implement two page-replacement policies: Random (recall from lecture, this is our baseline algorithm), and some form of LRU based on the Clock algorithm.  Kernel configuration options have been added to switch between them (see conf.kern).

Although you we are discarding the dumbvm implementation for this assignment, you may find it worth looking at its code, especially vm_fault(). Although it is simple, it should give you some useful insight into how other parts of the code work.

malloc() and free() behavior

Instrumentation and Performance Evaluation

In this section, we ask you to evaluate the performance of your virtual memory system. Use the file src/asst2/performance.txt as your "lab notebook" for this section. You will undoubtedly want to implement 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.

The starter code already tracks a several performance measures that should help in making your assessment. You should add the necessary infrastructure to maintain these statistics as well as any other statistics that you think you will find useful in tuning your system.

Once you have implemented the page handling functions and added instrumentation, it is time to evaluate your operating system's VM performance.

At a minimum, use the matmult and sort programs provided to determine your baseline performance (the performance of your system using the default TLB and paging algorithms). (Careful: You may need to modify the test programs to use just "printf" for output instead of "warn", "warnx", "err", etc. since we have not implemented the write() system call.) Experiment with the different TLB and paging algorithms and parameters in an attempt to improve your performance. As before, predict what will happen as you change algorithms and parameters. Compare the measured to the predicted results; 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. Figure out where the error is!

You should add at least 2 other test programs to your collection as you test and evaluate the algorithms, otherwise you may discover good parameters for matrix multiplication and sorting, but little else. Try to introduce programs with some variation in their uses of the memory system.

Provide a complete summary of the performance analysis you conduct. Include a thorough explanation of the the parameters you chose and any tuning you did to your algorithms to achieve good performance.

What to hand in

1. Implementation of the required functions. Commit the changes to your repository
2. Your performance.txt file should be added to your repository directly under the src/asst2 directory.

Strategy

You should expect to spend a substantial amount of time reading and learning how the code works. The TLB handling and paging system are reasonably complicated pieces of code. In particular, study the synchronization requirements.

You may need to work more closely with your partner on this assignment. There is not a lot of code to write, so working together to understand the starter code and codesign the required functions may be the most efficient strategy.

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

You should divide the virtual memory implementation into several small and well-defined modules so that you can both work on it as soon as you have a design planned out. Get together as early as possible to share what you each have discovered. DO NOT assign one person to implement the code, and one to run the performance experiments. You can't run any performance tests until the code is working, so you should both concentrate on getting paging working, and then work together on evaluating your implementation.

Look at the code system161/src/mipseb/mips.c to see how TLB faults are generated.

If you wish to see how the simulated machine generates TLB faults, get the source code from ~csc369h/winter/pub/OS161/dist/sys161-1.13.tar.gz), unpack it and look at sys161-1.13/mipseb/mips.c - start with the function translatemem() which shows what the simulated MMU does to translate a virtual address. It is not critical to read this code - you should understand, however, that the hardware generates faults when the TLB does not contain an entry for the requested virtual address, or when an entry exists but is not writable and a store is requested.

Begin by examining the vm_fault() handler in os161/src/kern/arch/mips/mips/vm.c. What changes must you add to support page faults?