OS/161 Virtual Memory System Overview

Introduction

The OS/161 virtual-memory system implements demand paging with swapping. It consists of several key components that work together to manage physical memory and provide virtual-memory services to user processes.

In addition to this high-level overview, you can read src/design/vm.txt in the OS/161 source tree for more detailed information (although it may go into depth on topics that are not relevant to the homework in this class).

Key Components

• Coremap: Manages physical memory pages

  • Interface in kern/arch/mips/include/coremap.h
  • Implementation in kern/arch/mips/vm/coremap.c
  • Described further in A Guide to coremap.c

• Logical Pages (lpages): Represents virtual pages and their states

  • Public functions in kern/include/vm.h
  • Most functions/interface in kern/include/vmprivate.h
  • Implementation in lpage.c
  • Described further in Understanding Logical Pages (lpages) in OS/161

• VM Objects: Groups related pages (e.g., for text, data, stack segments)

  • Public functions in kern/include/vm.h
  • Most functions/interface in kern/include/vmprivate.h
  • Implementation in vmobj.c
  • Described further in Understanding VM Objects and vm_object_setsize in OS/161

• Swap System: Manages the swap file for paging

  • Public functions in kern/include/vm.h
  • Most functions/interface in kern/include/vmprivate.h
  • Implementation in swap.c
  • Described further in Understanding the OS/161 Swap System

• Address Spaces: Contains VM objects for a process

  • Interface in kern/include/addrspace.h
  • Implementation in kern/vm/addrspace.c
  • Described further in Understanding Address Spaces in OS/161

• TLB Management: Handles translation lookaside buffer (TLB) operations

  • Interface in kern/arch/mips/include/coremap.h (the mmu_ functions)
  • Implementation in kern/arch/mips/vm/coremap.c

Reading over the header files is a good way to get a sense of the functions and data structures you'll be working with.

Core Data Structures

These are the key data structures used in the virtual memory system:

struct coremap_entry {
        struct lpage *cm_lpage; /* logical page we hold, or NULL */

        volatile
        int cm_tlbix:7;         /* tlb index number, or -1 */
        unsigned cm_cpunum:5;   /* cpu number for cm_tlbix */

        unsigned cm_kernel:1,   /* true if kernel page */
                cm_notlast:1,   /* true not last in sequence of kernel pages */
                cm_allocated:1; /* true if page in use (user or kernel) */
        volatile
        unsigned cm_pinned:1;   /* true if page is busy */

        /* other fields as needed */
};

struct lpage {
        volatile paddr_t lp_paddr;    /* physical addr (& flags in low bits) */
        off_t lp_swapaddr;            /* location in swap file */
        struct spinlock lp_spinlock;  /* synchronization */
}

struct vm_object {
        struct lpage_array *vmo_lpages;     /* array of logical pages */
        vaddr_t vmo_base;                   /* base virtual address */
        size_t vmo_lower_redzone;           /* size of protected area below */
}

The (primitive) array coremap contains num_coremap_entries, each containing a struct coremap_entry corresponding to a physical page.

Notice that the coremap uses bitfields to pack information into a single integer, which saves space since the coremap is a large array.

Key Operations

We'll focus on the operations you need to care about most for Homework 6.

Page-Fault Handling

1. TLB miss triggers fault
2. System locates relevant VM object and lpage
3. If page not in memory,
   • Allocates physical page (may require eviction)
   • Loads page from swap if necessary
4. Updates TLB

Page Replacement

The system implements two page-replacement algorithms:

• Clock algorithm (default)
• Random replacement (alternative)

Students will need to implement both algorithms in the assignment.

Memory Management

• Physical-memory allocation through coremap
• Swap-space management
• Page eviction when memory is full
• TLB management

Common Pitfalls

1. Synchronization
   • Be careful with spinlock ordering
   • Watch for deadlocks in page replacement
2. Memory Management
   • Don't forget to update swap reservations
   • Handle out-of-memory conditions
   • Clean up properly when shrinking objects
3. Error Handling
   • Check return values
   • Handle out-of-memory conditions gracefully
   • Maintain system consistency

(When logged in, completion status appears here.)