How ayiman29/xv6-riscv-lottery-scheduling works
1. What this repo is
- This is xv6 for RISC-V: a small, monolithic teaching OS kernel plus a minimal user-space.
- The kernel is written mostly in ANSI C with a few assembly files for boot, trap entry, and context switching.
2. Boot and bring-up path
- The machine starts in low-level assembly (kernel/entry.S, kernel/start.c, kernel/kernelvec.S, kernel/trampoline.S) and then enters kernel/main.c.
- Early initialization brings up memory allocation, locks, console/UART, interrupt controller, process table, trap handling, file system, and device drivers before user processes run.
- The runtime target is QEMU for riscv64-softmmu; this repo is built and launched through the top-level Makefile.
3. Kernel structure
- The kernel is intentionally compact and layered around a few core subsystems:
- processes/scheduling: proc.c, proc.h
- virtual memory: vm.c, vm.h, memlayout.h
- traps/syscalls: trap.c, syscall.c, syscall.h, sysproc.c, sysfile.c
- file system: fs.c, file.c, bio.c, log.c
- drivers: console.c, uart.c, plic.c, virtio_disk.c
- locking and utilities: spinlock.c, sleeplock.c, kalloc.c, string.c, printf.c
4. Process model and scheduling
- Processes are managed in kernel/proc.c with per-process state in kernel/proc.h.
- The repo includes a lottery scheduler fork: each runnable process has a tickets count and a turns counter, and the scheduler selects a winner proportionally to tickets.
- The new syscall settickets(int n) is wired through sysproc.c, syscall.c, syscall.h, and exposed to user space via user/user.h and user/usys.pl.
- user/test_scheduler.c is the corresponding demo/test workload.
5. Kernel/user boundary
- User programs cannot call kernel code directly; they enter through system calls handled by trap machinery and the syscall dispatcher.
- The boundary is enforced by RISC-V page tables and trap return code in the trampoline path.
- kernel/trap.c and kernel/syscall.c are the main control points where user requests become kernel actions.
6. Virtual memory and execution
- vm.c manages page tables, mappings, and memory copying between user and kernel spaces.
- exec.c loads ELF binaries (kernel/elf.h) into a process address space.
- The memory allocator (kalloc.c) supplies physical pages to the VM and process subsystems.
- This is the main boundary between the CPU-visible kernel state and each process’s private address space.
7. File system and storage path
- File I/O flows from user syscalls into file.c and then into the on-disk file system in fs.c.
- Block I/O is buffered and logged:
- bio.c provides the buffer cache,
- log.c provides write-ahead logging,
- virtio_disk.c talks to the virtual disk device.
- This separation makes the path from read/write syscalls to persistent storage explicit and recoverable.
8. Devices and console
- Console input/output is handled by console.c and uart.c.
- Interrupt delivery is routed through plic.c.
- These are the main hardware-facing interfaces besides the disk driver, and they feed into the trap/interrupt path.
9. Synchronization and multiprocessor support
- The kernel is designed for multiprocessor execution, so shared kernel state is protected with spinlock.c and sleeplock.c.
- Sleeping locks are used where code may block; spinlocks are used for short critical sections and interrupt-safe state.
- This matters for process scheduling, the buffer cache, and file-system metadata updates.
10. User space
- user/ contains small Unix-like programs: shell, core utilities, stress tests, and process tests.
- user/init.c is the first user process and starts the shell (user/sh.c).
- user/usys.pl generates user-space syscall stubs, and user/user.h defines the user API surface.
11. Build and image creation
- mkfs/mkfs.c builds the file-system image that xv6 boots with.
- The top-level Makefile ties together kernel compilation, user program compilation, filesystem image creation, and QEMU execution.
- The repo is therefore split into a kernel image and a user-program filesystem image.
12. End-to-end data flow to diagram
- A typical flow is: QEMU boot → kernel init → start init → shell launches user programs → syscalls enter kernel → kernel performs VM/process/fs/device work → results return to user space.
- For storage-heavy paths, the flow continues through buffer cache + log + virtio disk.
- For the fork-specific feature, process selection is influenced by ticket counts before CPU time is assigned.
Main entry points: main.c Kernel init · syscall.c Syscalls · proc.c Processes · trap.c Traps
Components 19
Build & Boot
Top-level build, image creation, and machine bring-up.
Kernel
Monolithic RISC-V kernel subsystems.
- Boot path · Low-level entry, trap vectors, and trampoline code that hand control to the kernel.
kernel/entry.S - Kernel init · Early kernel initialization and subsystem bring-up before user processes run.
kernel/main.c - Processes · Process table, context switching, and lottery scheduling state.
kernel/proc.c - Virtual memory · Page tables, mappings, and user/kernel memory copying.
kernel/vm.c - Traps · Handles traps, interrupts, and transitions between user and kernel space.
kernel/trap.c - Syscalls · Dispatches user system calls to kernel handlers.
kernel/syscall.c - Proc syscalls · Process-related system calls including the lottery tickets interface.
kernel/sysproc.c - File syscalls · File-related system calls that bridge user requests into the filesystem layer.
kernel/sysfile.c - File system · Core filesystem logic and metadata management.
kernel/fs.c - Block I/O · Buffer cache and write-ahead logging used by the filesystem.
kernel/bio.c - Drivers · Console, UART, interrupt controller, and disk device access.
kernel/console.c - Locks · Spinlocks and sleep locks protecting shared kernel state.
kernel/spinlock.c - Alloc & util · Physical page allocator and basic kernel utility routines.
kernel/kalloc.c
User Space
Initial process and small Unix-like programs.
- init · First user-space process that starts the shell.
user/init.c - Shell · Command interpreter that launches user programs.
user/sh.c - User tools · Small Unix-like programs, stress tests, and scheduler demos.
user/ls.c
Connections 26
- Makefile → QEMU: run · Builds images and starts the virtual machine.
- Makefile → mkfs: image · Creates the filesystem image from user programs.
- mkfs → User tools: pack · Embeds user-space binaries into the filesystem image.
- QEMU → Boot path: boot · Transfers execution into the kernel entry path.
- Boot path → Kernel init: enter · Low-level initialization hands off to kernel main.
- Kernel init → Alloc & util: init · Initializes memory allocation and basic utilities.
- Kernel init → Locks: init · Initializes locking primitives used across the kernel.
- Kernel init → Drivers: init · Brings up console, UART, interrupt controller, and disk support.
- Kernel init → Processes: init · Initializes process state and scheduling structures.
- Kernel init → Virtual memory: init · Sets up virtual memory and page table support.
- Kernel init → Traps: init · Installs trap and interrupt handling paths.
- Kernel init → File system: init · Brings up filesystem state before user processes run.
- Processes → Traps: switch · Uses trap/context machinery for process entry and return.
- Traps → Syscalls: syscall · Routes user-mode system calls to the dispatcher.
- Syscalls → Proc syscalls: proc · Dispatches process-related calls such as settickets.
- Syscalls → File syscalls: file · Dispatches file-related calls into the filesystem path.
- Proc syscalls → Processes: tickets · Updates process scheduling metadata including ticket counts.
- File syscalls → File system: io · Invokes filesystem operations on behalf of user syscalls.
- File system → Block I/O: buffered · Uses buffer cache and logging for coherent disk updates.
- Block I/O → Drivers: disk · Moves blocks to and from the virtual disk device.
- Drivers → Traps: irq · Interrupts and device events re-enter the kernel through traps.
- Virtual memory → Alloc & util: pages · Allocates physical pages for mappings and process memory.
- Virtual memory → Processes: address space · Maintains per-process address spaces and copies between them.
- init → Shell: start · Starts the interactive shell after system bring-up.
- Shell → User tools: launch · Runs user commands and test programs.
- User tools → Syscalls: requests · User programs enter the kernel through system calls.