XINU Paging System

Introduction

The XINU Paging System extends the base XINU operating system with demand paging, enabling support for virtual memory that exceeds the physical memory limits. By integrating backing store emulation, custom page replacement policies, and private heaps, the project provides robust memory management for multi-process environments.

Goals

1. Enable Demand Paging: Support mapping large address spaces into limited physical memory using backing stores.
2. Custom System Calls: Implement system calls like xmmap(), xmunmap(), vcreate(), vgetmem(), and vfreemem() to provide virtual memory management features.
3. Efficient Page Replacement: Develop and integrate the Second-Chance (SC) page replacement policy for optimal memory utilization.
4. Memory Isolation: Provide processes with private virtual heaps while maintaining global shared memory for inter-process communication.

Features

Virtual Memory

• Supports mapping private memory spaces for processes beyond physical memory limits.
• Implements page directories and page tables for efficient address translation.
• Demand paging ensures that only accessed pages are loaded into memory, optimizing resource usage.

Backing Store Management

• Backing stores emulate swap space using reserved physical memory.
• System calls like get_bs(), release_bs(), read_bs(), and write_bs() manage the backing stores for processes.

Page Replacement Policy

• Implements the Second-Chance (SC) algorithm for page replacement:
  • Uses a circular queue to manage frames.
  • Clears reference bits and swaps out pages with minimal overhead.

Process Virtual Heaps

• Processes created with vcreate() have private virtual heaps.
• System calls like vgetmem() and vfreemem() manage heap allocation and deallocation.

System Architecture

Memory Layout

• Virtual Memory (pages 4096 and beyond)
• 8 Backing Stores (pages 2048 - 4095)
• 1024 Frames (pages 1024 - 2047)
• Kernel Memory (pages 406 - 1023)
• Xinu Text, Data, BSS (pages 0 - 24)

Backing Store Emulation

• 8 backing stores, each capable of storing 256 pages (4MB).
• Mapped to physical memory from 0x00800000 to 0x00FFFFFF.

Page Tables and Directories

• Page tables are created on-demand and destroyed when no longer needed.
• Global page tables map shared memory and are shared by all processes.
• Private page tables are dynamically created for process-specific virtual memory.

Key System Calls

xmmap(int virtpage, bsd_t source, int npages)

Maps npages from a backing store source to a virtual memory region starting at virtpage.

xmunmap(int virtpage)

Unmaps a virtual memory region starting at virtpage.

vcreate(int *procaddr, int ssize, int hsize, int priority, char *name, int nargs, long args)

Creates a process with a private heap of hsize pages.

vgetmem(unsigned int nbytes)

Allocates memory from a process's private heap.

vfreemem(struct mblock *block, unsigned int size_in_bytes)

Frees allocated memory from a process's private heap.

srpolicy(int policy)

Sets the page replacement policy. Default is Second-Chance (SC).

Implementation Details

Inverted Page Table

• Tracks virtual-to-physical page mappings.
• Structure: { frame number, pid, virtual page number }.

Backing Store Map

• Maintains mappings of virtual memory to backing stores.
• Structure: { pid, vpage, npages, store }.

Page Fault Handling

1. Identify the faulted address and validate it.
2. Locate the corresponding backing store and page offset.
3. Allocate a free frame (or replace an existing page using SC).
4. Load the required page into memory and update page tables.

Second-Chance Page Replacement

• Circular queue scans frames, checking reference bits.
• Clears reference bits on the first pass; evicts unreferenced pages on the second pass.

Challenges and Solutions

1. Efficient Page Replacement:

   • Designed an SC algorithm with minimal overhead.
   • Used an inverted page table to optimize frame lookup.

2. Process Isolation:

   • Implemented private heaps using backing store mappings.
   • Ensured memory isolation by dynamically creating and destroying page tables.

3. Backing Store Emulation:

   • Reserved physical memory for backing stores to simulate disk behavior.
   • Provided APIs for backing store management.

Technology Stack

Future Work

1. Additional Page Replacement Policies:
   • Implement FIFO and LRU for comparative analysis.
2. Process Swapping:
   • Support swapping entire processes to and from backing stores.
3. Integration with File Systems:
   • Extend backing store emulation to use disk-based storage.

References

1. Intel System Programming Manual (Vol. 3)
2. Stallings, W. (2020). Operating Systems: Internals and Design Principles.
3. XINU Documentation: Paging and Virtual Memory Extensions