xv6-adaptive-page-replacement

Modified xv6 Operating System with custom memory printer and adaptive page swapping. Implements per-process memory tracking, page replacement strategies, victim process/page selection, and dynamic swap slot management for advanced memory management.

xv6 Adaptive Page Replacement & Memory Management

📌 Overview

This project extends the MIT xv6 Operating System with advanced memory management features.
It implements a Memory Printer for per-process memory usage and an Adaptive Page Swapping mechanism with dynamic replacement strategies.
The modifications showcase skills in OS kernel programming, process management, virtual memory, and systems design.

---

🚀 Features Implemented

• Memory Printer (Ctrl+I)

  • Displays per-process resident memory pages (in RAM).
  • Provides real-time visibility into memory usage.

• Page Swapping with Adaptive Replacement

  • Swaps pages between RAM and disk swap slots.
  • Maintains a swap slot table in xv6 disk layout.
  • Implements victim page selection and process-level swapping.
  • Adaptive replacement parameters (α, β) dynamically adjust thresholds.
  • Handles page faults and reloads swapped pages efficiently.

• Kernel Enhancements

  • Modified xv6 kernel to integrate swapping logic.
  • System calls for monitoring and debugging.
  • Disk I/O routines extended to support swap slots.

---

⚙️ Implementation Details

1. Memory Printer

   • Keybinding: Ctrl+I
   • Traverses page tables of active processes (PID > 2).
   • Reports resident page count in real time.

2. Page Swapping

   • Swap Slot Allocation: Maintains free/used slots in disk.
   • Victim Selection: Uses adaptive strategy (α, β) to pick pages.
   • Fault Handling: Reloads pages on demand, updates page tables.

3. Adaptive Replacement

   • Parameters (α, β) adjust page residency thresholds dynamically.
   • Balances memory pressure vs. I/O cost.
   • Improves throughput under mixed workloads.

---

🧪 Testing

• Verified correctness on multiple workloads:
  • Single-process memory printer accuracy.
  • Multi-process page swapping under load.
  • Stress tests with limited RAM and frequent swapping.
• Measured performance: reduced page fault rate with adaptive replacement.

---

▶️ How to Run

1. Clone xv6 source with modifications:

   git clone https://github.com/<your-username>/xv6-adaptive-page-replacement.git
   cd xv6-adaptive-page-replacement

Build xv6:

bash Copy Edit make qemu Test features:

Press Ctrl+I → display per-process memory usage.

Run memory-intensive programs to trigger swapping.

Monitor page faults and swap activity in kernel logs.

📊 Results Memory Printer accurately reports per-process page usage.

Adaptive replacement reduced page faults compared to static strategies.

Demonstrates real-world OS concepts: virtual memory, paging, swapping, adaptive replacement algorithms.

🔮 Future Work

This project can be extended further to explore advanced memory management and research directions:

• Multiple Page Replacement Policies

  • Implement and compare LRU, Clock, NRU, and Second-Chance algorithms.
  • Benchmark against the current adaptive strategy.

• Hybrid Swapping Strategy

  • Combine working set model with adaptive replacement to reduce thrashing.

• Page Compression

  • Use in-memory page compression before swapping to reduce I/O cost.

• Swap Space Optimization

  • Extend swap slot management with smarter allocation (e.g., per-process quotas).

• Performance Profiling Tools

  • Build kernel-level metrics for page faults, swap I/O latency, and cache hit/miss ratio.

• NUMA Awareness

  • Modify swapping behavior to account for Non-Uniform Memory Access (NUMA) architectures.

These extensions would align the project more closely with production-grade OS kernels and demonstrate deeper expertise in systems design.