注

由于最近Diz 项目上线了, 打算二刷MIT的操作系统课, 补上第一次一些没有弄清楚的点, 这一次 我要xv6对我来说没有任何的秘密可言! 由于之前也只剩下一两个lab的时候 草草了事把这门课给刷完了, 这次决定每一个lab所涉及的所有challenge都要写! 不仅自己要学懂, 也要让尽可能多的人看懂! 这是两个不同的境界, 知其然 和知其所以然 以及教会别人知其所以然. 而且主要这一次的目的也是带着大家一起刷, 所以很多时候.要完整刷的经历以及体验.

lab0 Lab guidance - 2023/02/19

关于每个点需要耗费的时长, 我就不过多描述了, 我在第一次写lab的情况下 都会超出Professor 所建议的时长. 我觉得大家也不一定要在意这个时长, 而是说看自己究竟学到了多少东西,这才是最宝贵的, 而不是lab刷完 testcase过了就可以了. 我想教授设计lab的目的 也是让我们加深整体对操作系统的了解, 而不是仅仅通过lab.

guidance里面我觉得关于Debugging Tips 还是很有价值的, 以防没有人看,我还是翻译成中文放在这里吧

• 确保你已经了解C语言中 关于指针的概念, 建议通读K&R的“The C Programming Language”(我读了两遍) 有一些有用的练习在这里https://pdos.csail.mit.edu/6.828/2019/lec/pointers.c 你必须确保已经完全了解链接里面的知识, 不然的话你会在后面的lab遭遇很多不必要的痛苦和灾难, 以至于最后以一种痛苦的方式去明白这些知识. 不要试图跳过这个链接里面关于指针的内容!

• 下面是一些关于指针尤其值得注意的地方

• • 如果 int *p = (int )100, 那么 (int)p + 1 和 (int)(p + 1) 将会得到 不同的结果, 前者的结果是101, 而后者的结果是104,这是因为后者将p当成指针而不是一个int数值, 指针加1会隐式的乘上当前指针所指向的对象的大小, 也即p + 14 = 104。(4指的是在操作系统中,通常情况下一个int类型的指针大小为4个字节)
  • p[i] 和 *(p + i) 是等价的,他们都是指向数组中第i个对象的地址.
  • &p[i] 和 (p+i) 是等价的, 意味着取出当前指针p指向的对象进行加法操作.

• 如果你在写lab的过程中,只通过了部分的testcase或者说只有一部分代码能符合要求, 那么你应该使用git commit 记录当前的快照, 然后进行一步一步的小修改, 直到通过所有的testcase. 如果你对Git不熟悉, 那么请阅读Git的用户手册 ,或许面向CS学生的Git指南 这对你来说十分有用.
• 当你的某一个testcase 没过, 那么你应该确保你知道为什么你的代码导致了错误.尝试使用一些print语句打印一些状态,直到你test case过了为止.
• 你会发现你写了很多的print语句, 你需要从大量打印信息中寻找有价值的信息, 一个好的方法是可以在“script” 中运行“make qemu” (你可以用”man script“来查看script的使用方式) ,script将会重定向所有的控制输出到一个文件中,你可以在文件中找到你想要的信息.
• 很多情况下, print语句 带给我们信息并不充足, 大多数情况下,我们仍然需要进行单步调试, 或者直接阅读汇编代码,或者监控在stack上的变量变化情况.我们可以使用“make qemu-gdb”的命令来对xv6进行调试, 首先我们需要在一个窗口中运行“make qemu-gdb”, 然后在另外一个窗口中运行“gdb” . 通常情况下,我们需要打一个断点在main函数上,然后按’c‘继续当前的执行流直到当xv6运行到main函数 触发断点. (仔细阅读GDB Debugger 获取更多GDB的使用技巧)
• 如果你想看xv6内核的汇编代码 查看在这个地址上的指令是啥, 你可以打开kernel.asm 查出究竟是在哪个函数的那个指令导致了crash 的发生,或者你可以使用“addr2line -e kernel/kernel pc-value”. 如果你想得到更详细的信息,包括crash所对应的调用栈, 那么你可以用上一点所说的方法

在一个窗口中运行“make qemu-gdb”, 然后在另外一个窗口中运行“gdb” , 在panic这个函数上打一个断点(b panic),然后按c 继续运行, 当内核触发断点的时候,使用“bt”来查看当前的调用栈

• 当你的内核卡死 (发生死锁)或者不能继续往下执行的时候(因为缺页中断等), 你可以使用gdb来找到为什么导致卡死的原因, 前面和上一点是同样的步骤,当你遇到卡死的时候,在运行“make qemu-gdb”的窗口中按下ctrl+c 然后输入bt来查看当前的调用栈.
• qemu拥有一个“监控器” 可以让你查看当前虚拟机器的状态,你可以利用 “ctrl-a c”的命令来查看. 一个十分有用的命令是info mem,它会打印当前的页表. 你也许需要使用“cpu”这个命令来指定查看哪个核心的页表, 或者你可以使用“make CPUS=1 qemu”来避免多核的情况.
• 个人强烈推荐使用make CPUS=1 qemu 来进行调试!

lab1 Xv6 and Unix utilities

Boot xv6 并切到util分支

• “ctrl p” 打印当前的进程状态
• “ctrl-a x” 关闭qemu

实现sleep 系统调用 (easy)

Implement the UNIX program sleep for xv6; your sleep should pause for a user-specified number of ticks. A tick is a notion of time defined by the xv6 kernel, namely the time between two interrupts from the timer chip. Your solution should be in the file user/sleep.c.

• 首先通读 xv6 book 的chapter 1
• 查看其他的用户程序 例如user/echo.c user/grep.c 学习如何获取来自命令行的参数
• 如果用户忘记传入参数 ,sleep 函数应该打印错误信息
• 命令行会以string的类型进行传递, 你可以用atoi 函数将它转换成int类型
• 使用sleep系统调用
• 在kernel/sysproc.c 实现sleep 系统调用(寻找sys_sleep), user/user.h 有关于用户层是如何调用sleep, user/usys.S汇编代码 让用户指令跳到内核中
• 确保main函数调用了 exit() 退出你的程序
• 添加你的sleep用户程序 到Makefile的 UPROGS中; 一旦你添加完成, make qemu会自动编译你的程序, 接下来你就可以在xv6 的shell 中去执行它
• 通读K&R的“The C Programming Language” 学习更多关于C的知识·

Pingpong (easy)

Write a program that uses UNIX system calls to ‘‘ping-pong’’ a byte between two processes over a pair of pipes, one for each direction. The parent should send a byte to the child; the child should print “: received ping”, where is its process ID, write the byte on the pipe to the parent, and exit; the parent should read the byte from the child, print “: received pong”, and exit. Your solution should be in the file user/pingpong.c.

• 使用pipe函数 创建一个pipe
• 使用fork函数 创建一个子进程
• 使用read函数 读取来自pipe的内容, 然后通过write函数往pipe里写入
• 使用getpid函数 找到当前进程的Process ID
• 添加pingpong用户程序 到Makefile的 UPROGS中
• 你可以在user/user.h 中找到用户程序中所有可用的库函数, 他们的实现代码在user/lib.c,user/printf.c, user/umalloc.c中

不知道pipe怎么用 ,直接看kernel代码, 看到usertest里面的用法

primes (moderate)

Write a concurrent version of prime sieve (素数筛) using pipes. This idea is due to Doug McIlroy, inventor of Unix pipes. The picture halfway down this page and the surrounding text explains how to do it. Your solution should be in the file user/primes.c.

你的目标是使用pipe和fork建立一个流水线. 往第一个进程输入2 .对于每一个素数, 你需要创建并调度一个进程 reads from its left neighbor over a pipe and writes to its right neighbor over another pipe. Since xv6 has limited number of file descriptors and processes, the first process can stop at 35. (不知道怎么翻译合适 还是放上原文)

• 关闭进程中不需要的文件描述符,不然的话将会提前用尽xv6中所有的文件描述符资源
• 当第一个进程输出35时,它需要等待流水线中所有其他进程终止,包括所有子进程,子子进程等.所以第一个进程将会等待至所有的输出都已经被打印和其他所有进程都终止的时候才会终止.
• read函数会返回0 当 pipe的write侧被关闭
• 直接往pipes 里面写4Bytes的int ,而不是使用 ASCII I/O
• 仅当需要的时候,你才需要创建新的进程
• 添加primes用户程序 到Makefile的 UPROGS中

Find (moderate)

Write a simple version of the UNIX find program: find all the files in a directory tree with a specific name. Your solution should be in the file user/find.c.

• 在user/ls.c中学习如何读取目录
• 使用递归 往下寻找子目录
• 避免递归“.”和“..”
• 当你修改文件系统的时候 你的修改并不会随着qemu的退出而清除; 使用make clean 获得未被修改过的文件系统
• 你需要使用C中的string
• == 并不能比较两个字符串 是否相同 ,你应该使用strcmp()
• 添加find用户程序 到Makefile的 UPROGS中

xargs(moderate)

Write a simple version of the UNIX xargs program: read lines from the standard input and run a command for each line, supplying the line as arguments to the command. Your solution should be in the file user/xargs.c.

很多同学可能对xargs 这个程序不太了解, 其实很简单 就是从标准输入中读取一行, 作为xargs的参数.

• 使用fork 和exec 处理每一行的输入,在父进程中使用wait函数等待子进程先结束.
• 读输入中的每一行, 你可以每次只读一个char 直到遇见’\n’
• kernel/param.h 声明了MAXARG, 这对你如何声明一个argv数组很有帮助
• 添加xargs用户程序 到Makefile的 UPROGS中
• 当你修改文件系统的时候 你的修改并不会随着qemu的退出而清除; 使用make clean 获得未被修改过的文件系统

Extra Challenge for lab 1

Write an uptime program that prints the uptime in terms of ticks using the uptime system call.

• 这个和sleep 一样简单, 关键在于看看sleep是怎么实现的, 了解ticks 这个变量 睡眠唤醒的机制

Support regular expressions in name matching for find. grep.c has some primitive support for regular expressions.

• 了解正则匹配的语法

  • ^{…} 代表括号里面的所有内容都过滤掉
  • . 匹配前面的子表达式一次或多次
  • * 匹配前面的子表达式零次或多次
  • $ 匹配输入字符串的结尾位置

• 了解grep里面的实现 ,strchr 函数返回的是对应字符的index

Modify the shell to not print a $ when processing shell commands from a file

举个例子 sh < xargstest.sh, 会打印出多个$符号

• 详细阅读sh.c 代码, 分析getcmd这个函数的用途
• 如何区分shell command 是否来自文件(也就是 不来自stdin ,文件描述符非0)

Modify the shell to support tab completion

• sh.c 是如何读取用户输入的, 当读到’\t’的时候要做什么处理
• 如何补齐? 往stdin里面写东西

Modify the shell to keep a history of passed shell commands

• 如何保存history? ring buffer FIFO
• 如何支持上下的按键 跳回到上一条commands?

你用getchar可以发现上下左右的编码有三位，分别是十进制27，91和65-68，按顺序对应了上下右左，查阅ascii码可知91是[，65-68是ABCD，27为esc键，可能会输出为^[，所以如果你的shell不支持读取这样的3字节编码，就会输出成^[A，B，C，D这样的乱码了