# ayiman29/xv6-riscv-lottery-scheduling architecture
> Architecture diagram of the GitHub repository ayiman29/xv6-riscv-lottery-scheduling, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-06-27). It is an AI-made overview: check details against the source.
- Interactive diagram: https://gitdiagram.com/ayiman29/xv6-riscv-lottery-scheduling
- Repository: https://github.com/ayiman29/xv6-riscv-lottery-scheduling
## Overview
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: [`kernel/main.c`](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/main.c) (Kernel init), [`kernel/syscall.c`](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/syscall.c) (Syscalls), [`kernel/proc.c`](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/proc.c) (Processes), [`kernel/trap.c`](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/trap.c) (Traps)
## Diagram (Mermaid)
```mermaid
flowchart TD
subgraph group_build["Build & Boot"]
node_makefile["Makefile
build orchestration"]
node_mkfs["mkfs
fs image builder
[mkfs.c]"]
node_qemu(("QEMU
runtime target"))
end
subgraph group_kernel["Kernel"]
node_boot["Boot path
assembly bring-up
[entry.S]"]
node_main["Kernel init
startup init
[main.c]"]
node_proc["Processes
sched/process
[proc.c]"]
node_vm["Virtual memory
mmu/page tables
[vm.c]"]
node_trap["Traps
interrupt/syscall entry
[trap.c]"]
node_syscall["Syscalls
dispatcher
[syscall.c]"]
node_sysproc["Proc syscalls
process syscalls
[sysproc.c]"]
node_sysfile["File syscalls
[sysfile.c]"]
node_fs["File system
on-disk fs
[fs.c]"]
node_blockio["Block I/O
cache+log
[bio.c]"]
node_drivers["Drivers
hardware I/O
[console.c]"]
node_sync["Locks
synchronization
[spinlock.c]"]
node_mem["Alloc & util
allocator/utilities
[kalloc.c]"]
end
subgraph group_user["User Space"]
node_init["init
first user process
[init.c]"]
node_shell["Shell
[sh.c]"]
node_tools["User tools
utilities/tests
[ls.c]"]
end
node_makefile -->|"run"| node_qemu
node_makefile -->|"image"| node_mkfs
node_mkfs -->|"pack"| node_tools
node_qemu -->|"boot"| node_boot
node_boot -->|"enter"| node_main
node_main -->|"init"| node_mem
node_main -->|"init"| node_sync
node_main -->|"init"| node_drivers
node_main -->|"init"| node_proc
node_main -->|"init"| node_vm
node_main -->|"init"| node_trap
node_main -->|"init"| node_fs
node_proc -->|"switch"| node_trap
node_trap -->|"syscall"| node_syscall
node_syscall -->|"proc"| node_sysproc
node_syscall -->|"file"| node_sysfile
node_sysproc -->|"tickets"| node_proc
node_sysfile -->|"io"| node_fs
node_fs -->|"buffered"| node_blockio
node_blockio -->|"disk"| node_drivers
node_drivers -->|"irq"| node_trap
node_vm -->|"pages"| node_mem
node_vm -->|"address space"| node_proc
node_init -->|"start"| node_shell
node_shell -->|"launch"| node_tools
node_tools -->|"requests"| node_syscall
click node_makefile "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/tree/feature/lottery-scheduling/Makefile"
click node_mkfs "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/mkfs/mkfs.c"
click node_boot "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/entry.S"
click node_main "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/main.c"
click node_proc "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/proc.c"
click node_vm "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/vm.c"
click node_trap "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/trap.c"
click node_syscall "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/syscall.c"
click node_sysproc "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/sysproc.c"
click node_sysfile "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/sysfile.c"
click node_fs "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/fs.c"
click node_blockio "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/bio.c"
click node_drivers "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/console.c"
click node_sync "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/spinlock.c"
click node_mem "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/kalloc.c"
click node_init "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/user/init.c"
click node_shell "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/user/sh.c"
click node_tools "https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/user/ls.c"
classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_makefile,node_mkfs,node_qemu toneBlue
class node_boot,node_main,node_proc,node_vm,node_trap,node_syscall,node_sysproc,node_sysfile,node_fs,node_blockio,node_drivers,node_sync,node_mem toneAmber
class node_init,node_shell,node_tools toneMint
```
## Components
### Build & Boot
Top-level build, image creation, and machine bring-up.
- [Makefile](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/tree/feature/lottery-scheduling/Makefile): build orchestration · Compiles kernel and user space, builds the filesystem image, and launches QEMU. · `Makefile`
- [mkfs](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/mkfs/mkfs.c): fs image builder · Creates the xv6 filesystem image populated with user programs. · `mkfs/mkfs.c`
- **QEMU**: runtime target · RISC-V virtual machine used to boot and run the system.
### Kernel
Monolithic RISC-V kernel subsystems.
- [Boot path](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/entry.S): assembly bring-up · Low-level entry, trap vectors, and trampoline code that hand control to the kernel. · `kernel/entry.S`
- [Kernel init](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/main.c): startup init · Early kernel initialization and subsystem bring-up before user processes run. · `kernel/main.c`
- [Processes](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/proc.c): sched/process · Process table, context switching, and lottery scheduling state. · `kernel/proc.c`
- [Virtual memory](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/vm.c): mmu/page tables · Page tables, mappings, and user/kernel memory copying. · `kernel/vm.c`
- [Traps](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/trap.c): interrupt/syscall entry · Handles traps, interrupts, and transitions between user and kernel space. · `kernel/trap.c`
- [Syscalls](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/syscall.c): dispatcher · Dispatches user system calls to kernel handlers. · `kernel/syscall.c`
- [Proc syscalls](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/sysproc.c): process syscalls · Process-related system calls including the lottery tickets interface. · `kernel/sysproc.c`
- [File syscalls](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/sysfile.c): file syscalls · File-related system calls that bridge user requests into the filesystem layer. · `kernel/sysfile.c`
- [File system](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/fs.c): on-disk fs · Core filesystem logic and metadata management. · `kernel/fs.c`
- [Block I/O](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/bio.c): cache+log · Buffer cache and write-ahead logging used by the filesystem. · `kernel/bio.c`
- [Drivers](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/console.c): hardware I/O · Console, UART, interrupt controller, and disk device access. · `kernel/console.c`
- [Locks](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/spinlock.c): synchronization · Spinlocks and sleep locks protecting shared kernel state. · `kernel/spinlock.c`
- [Alloc & util](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/kernel/kalloc.c): allocator/utilities · Physical page allocator and basic kernel utility routines. · `kernel/kalloc.c`
### User Space
Initial process and small Unix-like programs.
- [init](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/user/init.c): first user process · First user-space process that starts the shell. · `user/init.c`
- [Shell](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/user/sh.c): user shell · Command interpreter that launches user programs. · `user/sh.c`
- [User tools](https://github.com/ayiman29/xv6-riscv-lottery-scheduling/blob/feature/lottery-scheduling/user/ls.c): utilities/tests · Small Unix-like programs, stress tests, and scheduler demos. · `user/ls.c`
## Connections
- 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.