Skip to main content Link Menu Expand (external link) Document Search Copy Copied

Meeting Summary: CS 326 Lecture/Lab Spring 2025

Date: April 29, 2025, 02:58 PM Pacific Time (US and Canada)
Meeting ID: 813 3845 7711

This summary outlines the key points from the session, including an overview of virtual memory, multi-level page tables, kernel extensions, and the techniques used in the xv6 operating system. It also details the upcoming project and subsequent actions for students.

Quick Recap

  • Overview of Upcoming Classes & Project:
    • The course will soon dive into virtual memory, focusing on implementing a simplified mmap that enables two processes to share a physical memory page.
    • Emphasis was placed on understanding the relationship between virtual and physical memory.
  • Key Topics Covered:
    • Concepts of virtual memory and page tables.
    • Structure and benefits of multi-level sparse page tables.
    • The role of the translation lookaside buffer (TLB) in speeding up memory accesses.
    • Overview of the fork system call and how child process memory is created via copying of the parent’s page table.
    • Introduction of a new kernel extension, “pt”, which allows users to view the page table of the calling process.
  • Additional Topics on the Horizon:
    • File systems and container technology in modern operating systems.
    • Further exploration of memory-mapped files for efficient file I/O in systems with large virtual address spaces.

Next Steps

  • For Students:
    • Read Chapter 3 of the textbook before the next class.
    • Review the Project 4 specification with special attention to the implementation of the mmap system call for sharing memory between parent and child processes.
  • For the Instructor (Greg):
    • Distribute practice problems gradually.
    • Conduct a solution walkthrough for Project 4 on Thursday.
    • Investigate the unexpected behavior of the pt_print function, which is currently showing more pages than anticipated after invoking malloc.

Virtual Memory and Project 4 Overview

The session introduced virtual memory as the final major topic before transitioning to other advanced topics such as file systems and containers. Key points included:

  • Virtual Memory Basics:
    • Virtual memory is a conceptual layer that maps virtual addresses to physical memory.
    • Every memory access—whether for instructions or data—is translated via the page table.
  • Project 4 Focus:
    • Students will implement a system call (mmap) that sets up a shared memory page between a parent and child process.
    • The project aims to connect theoretical concepts with practical implementation using the xv6 operating system.

Virtual Memory and Page Tables

Fundamental Concepts

  • Mapping Virtual to Physical Addresses:
    • The operating system creates the mapping from virtual page numbers to physical page frame numbers using page tables.
    • This translation is performed for each memory access.
  • Page Table Entries (PTEs):
    • Each PTE typically contains a page frame number (e.g., 20 bits) and control flags (e.g., 12 bits for permissions such as read, write, and execute).

  • Code Example: Creating a Page Table in xv6 (Simplified)

    Below is an example of how a new top-level page table might be created in xv6:

    // Allocates and initializes a new page table.
pde_t *
uvm_create(void) {
    pde_t *pagetable = kalloc();
    if(pagetable == 0)
        return 0;
    memset(pagetable, 0, PGSIZE);
    return pagetable;
}

Hierarchical (Multi-Level) Page Tables

  • Why Multi-Level?
    • Single-level page tables can become prohibitively large as virtual address spaces grow.
    • Multi-level, or sparse, page tables efficiently cover large address spaces by allocating additional tables only when needed.
  • Two-Level Page Table Breakdown:
    • Virtual addresses are divided into:
      • L1 Index: Selects an entry in the top-level table.
      • L0 Index: Selects an entry in the second-level table.
      • Offset: Locates the exact byte within a 4KB page.

  • Mermaid Diagram: Two-Level Page Table Structure

    graph TD
    VA[Virtual Address]
    L1[L1 Page Table]
    L0[L0 Page Table]
    P[Physical Page]
      
    VA -->|Extract L1 Index| L1
    L1 -->|Pointer to L0 Table| L0
    VA -->|Extract L0 Index| L0
    L0 -->|Page Mapping| P

Address Translation Process

  • Translation Procedure:
    • The virtual address is segmented into offsets and indices.
    • Each L1 entry points to a corresponding L0 page table.
    • An L0 entry is then used to determine the correct physical page.
  • Memory Consumption Consideration:
    • On 32-bit architectures with 20-bit virtual page numbers, a single-level table might require up to 4 MB of memory.
    • Sparse multi-level page tables reduce this overhead significantly.

Virtual Memory in RISC-V

Sv39 Virtual Memory Model

  • Address Space and Structure:
    • The Sv39 model uses a 39-bit virtual address to support up to 512 GB of RAM.
    • It employs a three-level page table system for mapping.
  • Scaling to Larger Systems:
    • More extensive models like Sv48 and Sv57 exist to cover even larger address spaces.
  • Benefits:
    • Even with limited physical memory, large virtual address spaces allow efficient memory-mapping of large files.

  • Code Example: Walking the Page Table in xv6

    A simplified version of the walk function (which traverses page tables) in xv6 might look as follows:

    // Locates the PTE for a given virtual address.
pte_t *
walk(pde_t *pagetable, uint64 va, int alloc) {
    pte_t *pte;
    // Walk function implementation – details omitted for brevity.
    // If alloc is true, new page tables may be allocated.
    return pte;
}

Kernel Extension: ptprint (Print Page Table)

Overview

  • Purpose:
    • The ptprint extension allows users to view the page table of the calling process.
    • It serves as a practical demonstration of navigating and interpreting page tables.
  • Use Cases:
    • Bridging theoretical concepts with real-world paging mechanisms.
    • Facilitating debugging and validation of memory management.

Exploring Memory Mapping and System Calls in xv6

Memory Allocation and the Fork System Call

  • Dynamic Memory Handling:
    • The discussion demonstrated how allocations via malloc trigger the creation of new page table mappings.
    • An observed discrepancy in the expected number of pages post-allocation will be investigated further.
  • Child Process Creation:
    • The fork system call involves copying a parent’s virtual address space to create a child process.
    • Key functions include:
      • proc_pagetable: Creates the page table for the new process.
      • uvm_create: Allocates and initializes the top-level page table.
      • uvm_copy: Responsible for copying the virtual address space from the parent to the child, page by page.

  • Mermaid Diagram: Fork and Shared Memory Mapping

    graph TD
    Parent[Parent Process]
    Child[Child Process]
    ParentVA[Parent Virtual Address Space]
    ChildVA[Child Virtual Address Space]
    SharedPage[Shared Memory Page]
      
    Parent -->|fork| Child
    ParentVA -- copy --> ChildVA
    ParentVA --> SharedPage
    ChildVA --> SharedPage

  • Code Example: Copying a Parent’s Address Space

    An illustrative snippet for copying memory during a fork:

    int
uvm_copy(pde_t *old, pde_t *new, uint64 sz) {
    uint64 va;
    for(va = 0; va < sz; va += PGSIZE){
        // Allocate and copy one page at a time.
        // Details for copying data and setting up PTEs are omitted.
    }
    return 0;
}

Upcoming Project: Memory Mapping (Project 4)

  • Focus:
    • Implement a new system call, mmap, to enable shared memory between a parent and its child process.
  • Key Reminders:
    • Students should study Chapter 3 of the textbook for foundational knowledge.
    • A comprehensive solution walkthrough will be provided, though no actual code is given during the session.
    • Consider how much assistance to use from coding assistants; full understanding of the code is critical.

Additional Topics on the Horizon

  • Future Subjects:
    • File systems and container technologies, which are increasingly crucial in modern operating systems, particularly in AI systems.
  • Contextual Importance:
    • These topics build on the understanding of virtual memory and provide insight into efficient resource management in complex systems.

This summary preserves the core concepts and detailed discussion points from the meeting while structuring them in a clear, well-organized Markdown format. The inclusion of xv6 C code snippets and Mermaid diagrams provides concrete examples and visual aids to clarify the discussed concepts.