Ewance
← All challenges Software Engineer

Build a Multi-Level Feedback Queue Scheduler in xv6

Duration
3 weeks
Level
Intermediate
Type
Code
Team
1 to 5 people

The situation

The teaching-OS group (volunteer maintainers, GitHub-based contribution flow) prioritizes patches that are well-documented and pedagogically clear over patches that are merely clever.

Your task

Implement and benchmark a Multi-Level Feedback Queue scheduler in the xv6 teaching kernel so students see real interactivity tradeoffs.

The brief

What you do

  1. Fork the xv6-riscv repository and implement MLFQ in proc.c with 3 priority queues, per-queue time slices (10ms / 20ms / 40ms), priority demotion on slice exhaustion, and a 100ms priority boost to prevent starvation.
  2. Add a sysinfo-style system call exposing per-process queue + runtime stats.
  3. Write 3 benchmarks: CPU-bound vs I/O-bound mix, interactive-typing simulation, and starvation regression.

You deliver

The git patch, benchmark scripts, and a 6-page report covering design choices, results, and a section honestly listing what your implementation does NOT handle.

What you will practice

  • Implement preemptive, priority-based scheduling in a real kernel
  • Reason about CPU-bound vs I/O-bound workload tradeoffs
  • Use kernel data structures (proc table, run queues) safely under context switches
  • Design benchmarks that isolate the variable you're actually measuring

A suggested way in

  1. Read the original MLFQ chapter in OSTEP before touching code — it covers the gotchas
  2. Priority boosting prevents starvation but breaks if your boost interval is too long
  3. Benchmark on a single-CPU QEMU instance first; multi-CPU adds locking concerns

Skills you will practice

Operating systems, Scheduling, C programming, Kernel development, Benchmarking, Systems programming

How it is assessed

  • Correctness35%

    Patch boots cleanly, survives stress tests, and preserves existing xv6 semantics.

  • Benchmark design25%

    Benchmarks isolate scheduler behavior from I/O and disk effects.

  • Code quality20%

    Follows xv6 conventions; locking is correct and minimal.

  • Report honesty20%

    Report names what the implementation does NOT handle (e.g. multi-core).

Resources

  • GitTool

    Fork xv6-riscv and produce a reviewable patch series.

  • QEMUTool

    Run xv6 under emulation for safe kernel testing.

  • MakeTool

    xv6 build system; required for kernel compilation.

  • PythonTool

    Benchmark harness and result aggregation.

  • NotionTool

    Author the 6-page design report.

  • MarkdownTool

    Patch documentation in the project's contributing style.

Sample Ewance certificate of completion, verified by LearnCoin
Sample certificate
Your proof

Finish it. Earn this.

A verified certificate with your name. Anyone can check it.

Time to practice.

Solve this challenge
Related challenges

More like this.