前言
最近开始学习 MIT 的 6.S081,由于讲课视频、课件以及作业都比较完善,所以学习体验也比较好。课程链接为:6.S081。由于之前已经上过一次操作系统了,所以这次学习主要是希望能通过完成作业来加深对 Linux 操作系统的理解。目前准备整理一下做作业时候遇到的一些问题和难点,主要是记录一下做作业的思路,不会涉及具体实现代码。如果后面遇到没学过的内容可能会整理听课的笔记。
Lab 1 介绍
Lab 1 主要是熟悉 xv6 以及一些常见的 system calls。实验配置以及源代码框架参考: lab tools page。用 Linux 和 MacOS 都比较简单,这里不再赘述。下面看看这次要的 5 个问题。
sleep (easy)
Implement the UNIX program
sleep
for xv6; yoursleep
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 fileuser/sleep.c
.
题目很简单,只需要了解如何使用 sleep
这个 system call 即可。对于不熟悉的 system call 可以在 https://man7.org/linux/man-pages/index.html 这里查找 linux 的类似 system call 的用法,可以帮助理解。例如 Linux 的 sleep。这样也能熟悉 Linux 常见命令的操作。之后涉及 system call 我都会放一个 linux 上的相关命令用法作为参考。
pingpong
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 “
<pid>: received ping
“, where<pid>
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 “<pid>: received pong
“, and exit. Your solution should be in the file user/pingpong.c.\
这道题主要是让我们了解如何创建进程以及进行进程间通信的其中一种方法(管道):
- 使用
fork()
可以创建进程,参考 fork(2),常见用法如下:
1 | int pid; |
- 使用
pipe()
可以创建一个管道,每个管道有两个整型标识符,分别用于写入和读取,参考 pipe(2),常见的用法如下:
1 | // 存储 *一个* 管道的写入和读取标识符。 |
这道题的具体做法思路是:通过 pipe()
创建两个管道(虽然每个管道都可以写入读取,这道题要求我们将其作为一个单向管道,其中一个管道由主进程写入,子进程读取;另一个管道则相反)。然后通过 fork()
创建子进程,然后通过这两管道进行通信即可,具体顺序是:
假设有管道 p1
p2
,进程 1
和 2
1
向p1
写入一个字节,然后等待并从p2
读取一个字节,然后输出相应信息,退出(可以预先关闭p1
不用的读取端,p2
不用的写入端)2
等待并从p1
读取一个字节,输出相应信息,然后往p2
写入一个字节,退出
由于读取有先后顺序(2
只有在读取了字节后才会往 p2
写入数据,1
才能读取)所以输出顺序是 2
再到 1
primes
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 explain how to do it. Your solution should be in the file
user/primes.c
.Your goal is to use pipe and fork to set up the pipeline. The first process feeds the numbers 2 through 35 into the pipeline. For each prime number, you will arrange to create one process that 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.
首先理解题意,这里我的理解是:
- 假设要从 2 ~ 35 中输出所有质数,操作如下:
- 主进程首先创建子进程 1 以及和 子进程
t1
沟通的管道p1
,并且在p1
中写入2
~35
- 子进程
t1
从p1
中依次读取数字,将第一个读取到的数字2
作为质数,创建子进程t2
以及相应的沟通管道p2
,将2
~35
中不能被2
整除的数字写入p2
,这样就筛掉一部分非质数 - 子进程
t2
从p2
中依次读取数字,将第一个读取到的数字3
作为质数,创建子进程t3
以及相应的沟通管道p3
,接下来如此类推,直到某个被创建的子进程读不到数据为止。
理清了逻辑之后,写代码思路就比较清晰了,对每一个进程,逻辑大概如下:
1 | // 接受与左侧(父进程)沟通的管道 id |
find
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
.
这道题要求我们实现 Unix 中的 find
命令,不需要提供选项,只要求在给定搜索范围以及文件名的情况输出所有符合该文件名的文件路径(相对于搜索路径)即可,主要涉及以下两个问题:
- 给的一个文件(文件路径)怎么判断文件名是要搜索的文件名?
- 怎么(递归地)读取一个路径中的所有文件?
下面一个个来看:
- 给的一个文件(文件路径)怎么判断文件名是要搜索的文件名?
文件路径是以 /
进行分割的,由于这里不考虑后缀,所以给定一个 char*
文件路径只需要从往前遍历找到第一个 /
的位置,返回该位置往后偏置一位的地址即可(char*
类型)。对比两个 char*
使用 strcmp()
;
- 给定一个路径,怎么(递归地)读取一个路径中的所有文件?
首先,通过 kernel/fs.h
中的 fstat
可以读取路径信息,具体包括:
1 |
|
这里我们主要用来判断该路径是文件还是文件夹,用法如下:
1 | int fd = open(path, 0); // fd 作为文件标识符 |
题目中提示有让我们参考 user/ls.c
来进行文件夹信息的读取,user/ls.c
的函数实现如下,其中用到的 struct dirent
如下:
1 | // 见 kernel/fs.h |
user/ls.c
相关函数如下:
1 | void |
xargs
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
.
这一题要求我们实现 UNIX 的 xargs
命令。其基本用法是将标准输入流中按行读取字符串作为 xargs
后命令的参数,如:
echo "1\n2" | xargs -n 1 echo line
echo "1\n2" |
将 echo
的输出重定向至标准输入流中,再通过 xargs
后的命令 echo
执行,这里这里用两行,因此执行两次,每次都将字符串插入到 echo line
后面,因此输出为:
1 | $ echo "1\n2" | xargs -n 1 echo line |
题目中主要涉及:
- 怎么提取要执行的命令以及已有参数
- 怎么从标准输入流中按行逐个读取参数
- 给定命令和参数后怎么执行该命令且不妨碍后续操作
下面分别看一下:
- 第一步提取已有参数很简单,直接从
main()
入口中的argv
从argv[1]
获取至最后即可,可以存在另一个char* []
变量中。 - 我们可以初始化一个
char buf[MAX_SIZE]
数组用来存放输入流读取的数据,执行以下步骤:- 使用
int n = read(0, buf, sizeof(buf) - 1)
函数可以进行读取,第一个0
表示从标准输入流中提取,这里我们由于不知道每个参数有多擦汗那个,所以每次读取都尽可能填满buf
,最后空一位是为了填充'\0'
使其变成一个字符串,这样我们才能用字符串相关函数,并且只有第一次读取才是从buf
起始位置开始填充,之后读取要考虑buf
中剩余已有的数据(read()
返回的n
表示这次实际读取了多少个字节) - 读取完之后使用
int q = strchr(buf, '\n')
可以找到第一个\n
从而获取一行参数(即buf
到q
之间的字符,以空格分隔),同样在该段字符串循环查找' '
即可获取一行中的各个参数,填充进参数列表数组即可。填充完后继续在buf
中继续往后查找\n
进行类似操作 - 当查找不到
\n
时,将剩余的字节复制到buf
起始位置,重新从标准输入流中读取数组填充buf
,直到实际读取字节数为 0 为止 - 这些操作中间要注意的地方是时刻关注要操作的指针位置,具体包括以下几个:
- 从标准输入流中读取数据:假设上一次操作后最后剩下 m 个字节,那么读取数据的起始填充位置位置应该是
buf + m
, 最大读取个数是sizeof(buf) - m - 1
- 查找
\n
的位置:假设上一步中提取到了 n 个字节,那么查找的位置应该按以下规律变化:- 第一次查找:
p = buf
,查找到位置在q
- 第二次查找:
p = q + 1
,以此类推
- 第一次查找:
- 查找
' '
的位置:和前一步类似
- 从标准输入流中读取数据:假设上一次操作后最后剩下 m 个字节,那么读取数据的起始填充位置位置应该是
- 使用
- 获取了每一次参数列表后,可以用
exec()
来进行,exec()
接收两个参数,一个为执行的系统调用,另一个为参数列表,执行exec()
时会覆盖当前进程,因此我们需要使用fork()
来传建子进程调用exec()
,主进程(使用exit(0)
)等待exec()
完后进行执行下一步即可。
其他
fprintf
的用法:
作业代码中经常见到 fprintf(2, "ls: cannot open %s\n", path);
,这里后面两个参数是输出内容,第一个数字表示输出位置的标识符,例如:
1 | // 将 "We are in 2014" 写入 file.txt 中 |
C 中有一些常见的标识符为: 0
- 标准输入流,1
- 标准输出流,2
- 标准错误流
exit
和return
的区别
return
是函数返回,exit()
是结束当前进程,exit()
可以可以返回不同值表示不同结束状态,例如:exit(0)
- 程序正常退出;exit(1)
- 程序非正常退出。
假如有两个进程, p1
和 p2
, p1
为父进程,在父进程中调用 wait(s)
(int* s
),可以等待 p2
退出再进行往之后,p2
退出之后 p1
中的 s
指向的空间会存有 p2
退出的返回值。
在 main()
中 return 0
和 exit(0)
作用一样。