清华大学操作系统课程 —— 样本代码仓库
本仓库基于 Operating Systems: Three Easy Pieces (OSTEP) 体系构建，提供 C++ 版本 (36 文件) + C 版本 (12 文件) = 共 48 个完整可运行实现，涵盖 12 章、4 大知识领域。C 版本使用 POSIX 原生 API (pthread, semaphore, fork, mmap)，更贴近 Linux 内核实际代码风格。适合：
- 清华操作系统课程的学习者
- 408/826 计算机考研复习
- 进程调度/同步/内存/文件系统的实践理解
- 系统编程方向的面试准备
os/
├── Hello.cpp # 仓库入口
│
╔══ Part I: CPU虚拟化 (01-03) — 进程/调度/并发 ═══════════════════════════╗
║ ║
├── 01_processes/ # 进程抽象
│ ├── process_model.cpp # 进程模型 & PCB
│ ├── context_switch.cpp # 上下文切换开销分析
│ └── fork_exec.cpp # fork/exec + COW + Shell重定向
│
├── 02_scheduling/ # CPU调度
│ ├── scheduling_basic.cpp # FCFS/SJF/STCF/Round-Robin
│ ├── mlfq.cpp # 多级反馈队列 (MLFQ) 模拟器
│ └── cfs_simulator.cpp # Linux CFS 完全公平调度模拟
│
├── 03_concurrency/ # 并发与线程
│ ├── threads_intro.cpp # 线程模型 (1:1/N:1/M:N)
│ ├── race_condition.cpp # 竞态条件 & counter++ 分析
│ ├── mutex_impl.cpp # 自旋锁/Ticket锁/Futex性能对比
│ └── condition_variable.cpp # 条件变量 & 生产者-消费者
║ ║
╚══════════════════════════════════════════════════════════════════════════╝
╔══ Part II: 同步机制 (04-06) — 锁/信号量/死锁 ═══════════════════════════╗
║ ║
├── 04_locks/ # 锁的实现
│ ├── spinlock_ticket.cpp # TAS/TTAS/Ticket/MCS 锁对比
│ └── futex.cpp # Linux Futex 快/慢路径
│
├── 05_semaphores/ # 信号量与经典问题
│ ├── semaphore_impl.cpp # 信号量实现 (mutex+condvar)
│ ├── readers_writers.cpp # 读者-写者问题
│ └── dining_philosophers.cpp # 哲学家就餐 (死锁预防)
│
├── 06_deadlock/ # 死锁
│ ├── deadlock_detection.cpp # 等待图 DFS 环检测
│ └── bankers_algorithm.cpp # 银行家算法 (安全状态检查)
║ ║
╚══════════════════════════════════════════════════════════════════════════╝
╔══ Part III: 内存管理 (07-09) — 虚拟内存/分页/分配器 ════════════════════╗
║ ║
├── 07_virtual_memory/ # 虚拟内存
│ ├── address_spaces.cpp # 地址空间布局 & ASLR
│ ├── segmentation.cpp # 分段 (基址+界限)
│ └── page_table_walk.cpp # 页表遍历 (VA→PTE→PA)
│
├── 08_paging/ # 页面管理
│ ├── page_replacement.cpp # OPT/LRU/Clock 替换算法
│ ├── working_set.cpp # 工作集模型 & Thrashing
│ └── swap_system.cpp # Swap/zram/zswap
│
├── 09_allocation/ # 内存分配
│ ├── malloc_free.cpp # malloc 实现 (First Fit)
│ ├── fragmentation.cpp # 碎片分析 (内部/外部)
│ └── buddy_system.cpp # Linux 伙伴系统
║ ║
╚══════════════════════════════════════════════════════════════════════════╝
╔══ Part IV: 存储系统 (10-12) — 文件系统/IO/高级主题 ═════════════════════╗
║ ║
├── 10_file_systems/ # 文件系统
│ ├── file_system_basics.cpp # Inode/目录/硬链接/符号链接
│ ├── fat_inode.cpp # FAT vs Inode 实现对比
│ └── journaling.cpp # 日志文件系统 (ext4 ordered)
│
├── 11_io_disks/ # I/O与磁盘
│ ├── disk_scheduling.cpp # FCFS/SSTF/SCAN 磁盘调度
│ ├── raid.cpp # RAID 0/1/5/6/10 模拟
│ └── io_stack.cpp # Linux I/O Stack (VFS→Block→NVMe)
│
├── 12_advanced/ # 高级主题
│ ├── virtualization.cpp # 虚拟化 & 容器 (VM/Namespace/Cgroups)
│ ├── microkernel.cpp # 微内核 vs 单内核
│ └── linux_syscalls.cpp # 系统调用开销 & vDSO
║ ║
╚══════════════════════════════════════════════════════════════════════════╝
# 注意: 多线程文件需链接 pthread
g++ -std=c++17 03_concurrency/race_condition.cpp -o race -lpthread
./race
# 单线程文件
g++ -std=c++17 01_processes/process_model.cpp -o proc
./proc| Part | 章节 | 核心内容 |
|---|---|---|
| I | 进程 | PCB、上下文切换、fork/exec/COW |
| I | 调度 | FCFS/SJF/RR/MLFQ/Linux CFS |
| I | 并发 | 线程、竞态、自旋锁/mutex/futex、条件变量 |
| II | 锁 | TAS/TTAS/Ticket/MCS、Futex快慢路径 |
| II | 同步 | 信号量、生产者-消费者、读者-写者、哲学家就餐 |
| II | 死锁 | 等待图检测、银行家算法 |
| III | 虚拟内存 | 地址空间/ASLR、分段、页表遍历 |
| III | 分页 | OPT/LRU/Clock、工作集/Thrashing、Swap |
| III | 分配 | malloc实现、碎片、伙伴系统 |
| IV | 文件系统 | Inode/FAT、硬链接/符号链接、日志 |
| IV | I/O磁盘 | 磁盘调度、RAID、Linux I/O栈 |
| IV | 高级 | 虚拟化/容器、微内核、系统调用性能 |
c/ 目录下提供 12 个 C 语言实现，每个对应一章的核心概念，使用原生 POSIX API：
| 章节 | C 文件 | 关键 API |
|---|---|---|
| 进程 | c/01_processes/process_model.c |
fork, waitpid, WIFEXITED |
| 调度 | c/02_scheduling/scheduling.c |
纯算法 (数组+循环) |
| 并发 | c/03_concurrency/race_condition.c |
pthread, _sync*, C11 atomic |
| 锁 | c/04_locks/futex_spinlock.c |
futex syscall, C11 spinlock |
| 信号量 | c/05_semaphores/posix_semaphore.c |
sem_init, sem_wait, sem_post |
| 死锁 | c/06_deadlock/bankers.c |
纯算法 (2D数组) |
| 虚拟内存 | c/07_virtual_memory/page_table.c |
mmap, mprotect, 位操作 |
| 分页 | c/08_paging/page_replace.c |
纯算法 (OPT/LRU/Clock) |
| 分配器 | c/09_allocation/malloc_impl.c |
sbrk, 指针运算 |
| 文件系统 | c/10_file_systems/simple_fs.c |
struct inode, dirent |
| 磁盘 | c/11_io_disks/disk_sched.c |
qsort, 数组操作 |
| 高级 | c/12_advanced/syscall_bench.c |
syscall(), vDSO |
# 编译 C 版本 (部分需要 -lpthread)
gcc -std=c11 -o prog c/01_processes/process_model.c
gcc -std=c11 -o race c/03_concurrency/race_condition.c -lpthread- 教材: Remzi & Andrea Arpaci-Dusseau, Operating Systems: Three Easy Pieces (OSTEP)
- 免费: https://pages.cs.wisc.edu/~remzi/OSTEP/
- 进阶: Robert Love, Linux Kernel Development
本仓库由以下 AI 协作完成：
- 代码架构与实现: Claude (Anthropic)
- 推理引擎: DeepSeek V4 Pro (1M 上下文)
所有代码经人工审查确认，AI 工具仅作为生产力辅助。
MIT License