HumanCore - CP/M-17 Version 1.0, Date: January 08, 1996
课程安排
| Mon | Tue | Wed | Thur | Fri |
|---|---|---|---|---|
| Binary search trees, BST sort | AVL trees, AVL sort | LEC 2 (ab): PC hardware and x86 programming slides, notes Preparation: Read Bootstrap/PC hardware appendices and the related xv6 source files Assignment: HW: Boot xv6 | ||
| Counting sort, radix sort, lower bounds for sorting and searching | LEC 3 (TAs): C and gdb (pointers example) Homework 1 due: Boot xv6 Preparation: Read 2.9 (Bitwise operators), 5.1 (Pointers and Addresses) through 5.5(Character Pointers and Functions) and 6.4 (pointers to structures) in K&R Assignment: HW: shell Assignment: Lab 2: Memory management | Hashing with chaining | DUE: Lab 1LEC 4 (fk): Shell & OS organization Preparation: Read chapter 0 of the xv6 book. Homework 2 due: shell | |
| Table doubling, Karp-Rabin | LEC 5 (fk): Isolation mechanisms Preparation: Read “Chapter 1: Operating system organization” and the related xv6 source files Assignment: HW: system calls | Open addressing, cryptographic hashing | LEC 6 (ab): Virtual memory (1) (handouts: page table translation and registers) (slides) Preparation: Read “Chapter 2: Page Tables” Homework 3 due: system calls Assignment: HW lazy page allocation | |
| Quiz 1 | LEC 7 (ab): Virtual memory (2) (handout: JOS virtual memory layout) (slides) Homework 4 due: HW lazy page allocation Assignment: HW xv6 CPU alarm Assignment: Lab 3: User-Level Environments | Integer arithmetic, Karatsuba multiplication | DUE: Lab 2 LEC 8 (fk): System calls, interrupts, exceptions (handouts: IDT) Prep aration: Read “Traps, interrupts, and drivers” and the related xv6 source files Homework 5 due: HW xv6 CPU alarm Assignment: HW multithreaded programming | |
| Square roots, Newton’s method | LEC 9 (ab): Multiprocessors and locking (slides) Preparation: Read “Locking” with spinlock.c and skim mp.c Homework 6 due: HW multithreaded programming Assignment: HW xv6 locks | Breadth-first search (BFS) | DUE: Lab 3 (Part A)oct 10 Hacking day Assignment: Lab 4: Preemptive Multitasking | |
| Depth-first search (DFS), topological sorting | LEC 10 (ab): Processes and switching Preparation: Read “Scheduling” up to “Sleep and wakeup” and proc.c, swtch.S Homework 7 due: HW xv6 locks Assignment: HW uthreads | Single-source shortest paths problem | LEC 11 (fk): sleep&wakeup Preparation: Read remainder of “Scheduling”, and corresponding parts of proc.c Homework 8 due: HW uthreads Assignment: HW barrier | |
| Dijkstra | LEC 12 (fk): File systems Preparation: Read bio.c, fs.c, sysfile.c, file.c and “File system” except for the logging sections Homework 9 due: HW barrier Assignment: HW big files | Bellman-Ford | DUE: Lab 4 (Part A)oct 24 LEC 13 (fk): Crash recovery Preparation: Read log.c and the logging sections of “File system” Homework 10 due: HW big files Assignment: HW crash Assignment: Lab 6: Networking Assignment: Lab 7: Final project | |
| Speeding up Dijkstra | Quiz #1 open book and notes scope: Lectures 1 through 13, HW 1 through 10, labs 1 through 3 practice: previous years’ quizzes. | Quiz 2 | DUE: Lab 4 (Part B)oct 31 Hacking day Assignment: Lab 5: File system, spawn, and sh | |
| Memoization, subproblems, guessing, bottom-up; Fibonacci, shortest paths | LEC 14 (fk): File system performance and fast crash recovery Homework 11 due: HW crash Preparation: Read Journaling the Linux ext2fs Filesystem (1998) Assignment: mmap() | Parent pointers; text justification, perfect-information blackjack | DUE: Lab 4 (Part C)nov 7 LEC 15 (ab): Virtual Memory (3) (slides) Preparation: Read Virtual Memory Primitives for User Programs (1991) Homework 12 due: mmap | |
| String subproblems, psuedopolynomial time; parenthesization, edit distance, knapsack | LEC 16 (fk): OS Organization Preparation: Read Exokernel (1995) Homework 13 due: HW exokernel question | Two kinds of guessing; piano/guitar fingering, Tetris training, Super Mario Bros. | DUE: Final project proposal (if doing project)nov 19 LEC 17 (cc): Kernels and HLL Preparation: Read the Biscuit paper (2018) Homework 14 due: [HW Biscuit question | |
| Computational complexity | DROP DATE LEC 18 (ab): Scalable locks (slides) (code) Preparation: Read Non-scalable locks paper (2012) Homework 15 due: ticket lock question | Algorithms research topics | DUE: Lab 5nov 26 LEC 19 (ab): Scaling OSes slides Preparation: Read RCU (2013) Homework 16 due: RCU question DUE: Email us a status update on your final project (a paragraph) | |
| LEC 20 (ab): Virtual Machines (1) (slides) Preparation: Read Software vs Hardware Virtualization (2006) Homework 17 due: VM question | LEC 21 (ab): Virtual Machines (2) (slides) Preparation: Read Dune: Safe User-level Access to Privileged CPU Features (2012) Homework 18 due: Dune question | |||
| LEC 22 (fk): High-performance networking Preparation: Read IX: A Protected Dataplane Operating System for High Throughput and Low Latency (2014) Homework 19 due: IX question | Quiz #2 DUPONT-Gym, 9am-11pm open book, notes, and papers. scope: Lectures 14 through last lecture (dec 12), labs 4 and 5. practice: previous years’ quizzes. |
课程阅读
阅读练习
| 章节 | 内容 | 完成情况 |
|---|---|---|
| Chapter1 | ||
| Chapter2 | ||
| Chapter3 | ||
| Chapter4 | 练习1：触发竞态 | |
| Chapter5 | ||
| Chapter6 |
课程视频
由于本课程视频较为模糊，因此我们以其他的视频进行替代
| 课程 | 内容 | 完成情况 |
|---|---|---|
| 第一讲 | 为何学习操作系统 | 完成 |
| 完成 | ||
| 完成 | ||
| 第三讲 | 操作系统启动流程 | 完成 |
| 中断、异常和系统调用比较 | 完成 | |
| 中断、异常和系统调用题目 | 完成 | |
| 系统调用及题目 | 完成 | |
| 第四讲 | ||
| 第五讲：物理内存管理 | 计算机体系结构和内存层次 | 完成 |
| 地址空间和地址生成 | 完成：笔记记录在内存管理章节 | |
| 连续内存分配 | 完成：笔记记录在内存管理章节 | |
| 碎片整理 | ||
| 第六讲：非连续内存分配 | 非连续分配需求背景 | 完成 |
| 段式管理 | 完成 | |
| 页式管理 | 完成 | |
| 第十一讲：进程和线程 | 进程的概念 | 完成 |
| 进程控制块 | 完成 | |
| 进程状态 | 完成 | |
| 进程三状态模型 | 完成 | |
| 进程挂起 | 完成 | |
| 线程 | 完成 | |
| 第十二讲：进程控制 | 进程切换 | 完成 |
| 进程创建 | 完成 | |
| 进程加载 | 完成 | |
| 第十三讲：内核线程管理 |
作业
| 作业 | 内容 | 完成情况 |
|---|---|---|
| 作业1：boot xv6 (Lecture2) | Boot xv6 | 完成 |
| Finding and breaking at an address | 完成 | |
| Exercise: What is on the stack? | ||
| 作业2：shell (Lecture3) | 完成：6.033: Hands-on Assignment (UNIX) (mit.edu) | |
| 阅读：chapter 0 of the xv6 book | 完成 | |
| 阅读：6.828 shell | 完成 | |
| 完成：实验环境搭建 | 完成 | |
| 完成：执行简单命令 | 完成 | |
| 完成：IO重定向 | 完成 | |
| 完成：实施管道 | 完成 | |
| 完成：挑战练习 | ||
| 作业3：xv6 system calls (Lecture5) | 完成：syscall函数 | 完成 |
| 完成：date函数 | 完成 | |
| 作业4：lazy page allocation(Lecture6) | 完成：修改sbrk函数 | 完成 |
| 完成：lazy allocation | 完成 | |
| 完成：挑战任务 | ||
| 作业5：CPU Alarm(Lecture7) | 阅读：作业内容 | |
| 作业6：Threads and Locking | 完成：对put进行加锁保护 | 完成，但是Hash表原理不太懂，复习了一下，基本懂了 |
实 验
| 实验 | 内容 | 完成情况 |
|---|---|---|
| Lab1 | 完成 | |
| Lab2 | 阅读：Introduction | 完成 |
| 完成：实验环境搭建 | 完成 | |
| 阅读：第一部分，物理页管理 | 完成 | |
| 阅读：第二部分，虚拟内存 | 完成 | |
| 阅读：第三部分，内核地址空间 | 完成 | |
| 编程：编写一个物理内存分配 boot_alloc | 完成 | |
| 第一部分：编写mem_init() | 完成 | |
| 第一部分：编写page_init | 完成 | |
| 第一部分：编写page_alloc和page_free | 完成 | |
| 第二部分：编写pgdir_walk | 完成 | |
| 编写boot_map_region | 完成 | |
| 编写page_lookup | 完成 | |
| 编写page_insert | 完成 | |
| 编写page_delete | 完成 | |
| 第三部分：内核地址空间 | 完成 | |
| Lab3 | 源码阅读 | 完成 |
| 阅读进程状态章节 | 完成 | |
| 进程创建及运行章节代码 | 完成 | |
| 阅读：IA-32 Developer’s Manual 第五章 | 读到了5.10节 | |
| 阅读”Basics of Protected Control Transfer” | 完成 | |
| 练习4，编写trapentry | 完成 | |
| 练习5，编写trap_dispatch | 完成 | |
| 练习6，编写断点异常 | 完成 | |
| Lab 4 | 课程准备 | 完成 |
| 第一部分 | ||
练习1：编写mmio_map_region函数 |
完成 | |
练习2：阅读boot_aps、mp_main以及mpentry.S |
完成 | |
练习2：修改page_init，删除特定内存 |
完成 | |
| 阅读CPU状态 | 完成 | |
| 练习3：初始化每个CPU的内核栈 | 完成 | |
练习4：编写trap_init_percpu |
完成 | |
| 练习5：对内核进行锁保护 | 完成 | |
| 挑战1：使用细颗粒锁 | ||
| 练习6：完成Round-robin调度 | 完成 | |
| 挑战2：添加优先级调度 | ||
| 挑战3：浮点单元支持 | ||
| 完成用于支持进程创建的系统调用 | 完成 | |
练习7：sys_exofork实现 |
完成 | |
| 第二部分 |