Lab1: Xv6 and Unix utilities
一、Boot xv6
获取实验源码，并切换到指定的分支；（每一个实验都要切换到指定分支）
$ git clone git://g.csail.mit.edu/xv6-labs-2020
Cloning into 'xv6-labs-2020'...
...
$ cd xv6-labs-2020
$ git checkout util
Branch 'util' set up to track remote branch 'util' from 'origin'.
Switched to a new branch 'util
构建并运行xv6
make qemu
二、sleep
1、实验要求
写一个用户程序，调用sleep的系统实现
2、实现过程
在user目录下创建一个sleep.c文件，其源码为：
#include "kernel/types.h"
#include "user/user.h"
int main(int argc, char* argv[]){
if(argc<1||argc>2){
fprintf(2, "usage: sleep time\n ");
exit(1);
}
int time = atoi(argv[1]);
sleep(time);
exit(0);
}
然后在项目的Makefile文件中，UPROGS中按照格式添加sleep。
UPROGS=\
$U/_cat\
$U/_echo\
$U/_forktest\
$U/_grep\
$U/_init\
$U/_kill\
$U/_ln\
$U/_ls\
$U/_mkdir\
$U/_rm\
$U/_sh\
$U/_stressfs\
$U/_usertests\
$U/_grind\
$U/_wc\
$U/_zombie\
$U/_copy\
$U/_sleep\
保存后，退出qemu（ctrl+a,x），重新编译make qemu，并在xv6的命令行中执行sleep 10.
整个编译执行过程，结合gpt给出的答案：
你写的 sleep.c
↓
调用 sleep()
↓
Makefile 把 sleep.c 编译成 sleep.o
↓
Makefile 自动加入 usys.o（含 sleep 实现）
↓
链接 sleep.o + usys.o → sleep
↓
运行成功
3、验证代码是否正确
退出xv6后输入make grade，可能会报错：
xxx@LAPTOP-PSHBU979:~/projects/xv6-labs-2020$ make grade
make clean
make[1]: Entering directory '/home/lyj/projects/xv6-labs-2020'
rm -f *.tex *.dvi *.idx *.aux *.log *.ind *.ilg \
*/*.o */*.d */*.asm */*.sym \
user/initcode user/initcode.out kernel/kernel fs.img \
mkfs/mkfs .gdbinit \
user/usys.S \
user/_cat user/_echo user/_forktest user/_grep user/_init user/_kill user/_ln user/_ls user/_mkdir user/_rm user/_sh user/_stressfs user/_usertests user/_grind user/_wc user/_zombie user/_copy user/_sleep
make[1]: Leaving directory '/home/lyj/projects/xv6-labs-2020'
./grade-lab-util -v
/usr/bin/env: ‘python’: No such file or directory
make: *** [Makefile:234: grade] Error 127
这是因为xv6的grade测试脚本依赖于python脚本执行，由于python默认是python2的别名，但是现在系统大多数都是python3，所以我们可以为python3创建一个软连接
sudo ln -s /usr/bin/python3 /usr/bin/python
然后再执行make grade命令就成功了
然后再执行
./grade-lab-util sleep
二、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 “: 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.
也就是一个字节通过管道在父进程和子进程之间进行传输，就像打乒乓一样。父进程发送一个字节给子进程，子进程接着打印：“: received ping”,子进程把这个字节写入到自己的管道中，传递给父进程，然后子进程退出；父进程读取子进程传输给它的字节，然后打印：“: received pong”, 然后退出。
1、实现过程
在理解了管道的基础上，再写出这个代码就不难，设置两个管道（pipe只支持单向管道，两个管道构成全双工管道），一个管道的写端和父进程连接，读端和子进程连接；另一个管道的写端和子进程连接，读端和父进程连接。其他的看代码注释就能明白；
源码：
#include "kernel/types.h"
#include "user/user.h"
int main(int argc, char* argv[]){
char buf[] = {'6'};
/*
fd1-->parent; fd2->child;
parent往fd1[1]发送数据，child从fd1[0]读取数据
child往fd2[1]发送数据，parent从fd2[0]读取数据
*/
int fd1[2], fd2[2];
pipe(fd1);
pipe(fd2);
if(fork()==0){
// 子进程
// child从fd1[0]读取数据,需要把fd1[1]管道写端关闭；
close(fd1[1]);
read(fd1[0], buf, 1); // 通过fd1读端把fd1管道中的内容读取到buf中。
printf("%d: received ping\n", getpid());
// child往fd2[1]发送数据，需要把fd2[0]给关闭；
close(fd2[0]);
write(fd2[1], buf, 1); // 通过fd2写端把buf中的内容读取到fd2管道的缓冲区中。
exit(0);
}else{
// 父进程
// parent往fd1[1]发送数据，需要把fd1[0]给关闭，因为写入数据的时候，应该停止读取；
close(fd1[0]);
write(fd1[1], buf, 1);
// parent从fd2[0]读取数据，需要把fd2[1]写端关闭
close(fd2[1]);
read(fd2[0], buf, 1);
printf("%d: received pong\n", getpid());
exit(0);
}
}
验证，在xv6-labs-2020目录下输入./grade-lab-util pingpong，显示：
通过测试。
2、感悟
通过这个实验更加理解了管道是什么，我们可以把管道就想象成一个下水道管道，水从管道入口进入管道，就好比把数据写入到管道的缓冲区中，水从管道出口流出管道，就好比把数据从管道的缓冲区中读取处理。
三、primes
1、如何判断一个范围内的数字哪些是质数——埃拉托斯特尼筛法（埃式筛）
我个人的理解就是，用已知质数作为筛子，不断筛出质数的候选数，比如已知质数为2，那么以质数2为筛子，排除范围内所有可以被2整除的数，筛出的质数侯选数为所有奇数，筛出的数中，最小的一定为质数，因此，得到下一个质数为3，然后以质数3为筛子，在前面的基础上继续筛出不是3的倍数的数作为质数候选数，得到的候选数中最小的为5，5也为质数。重复上述过程，直到筛不出数据，则找出了该范围内所有的质数。
2、代码实现
#include "kernel/types.h"
#include "user/user.h"
#define SIZE 35
void recur_sieve(int p[2]){ // 把文件描述符作为参数，该文件描述符指向管道
int prime, num;
int p1[2];
if (close(0) == -1) {
fprintf(2, "error: failed to close p1[1]\n");
exit(1);
}
dup(p[0]); //复用文件描述符0；把p管道的读端绑定文件描述符0；
close(p[0]); //关闭p[0]的文件描述符，还剩文件描述符0可以从p管道中读取数据；
close(p[1]);// 关闭p[1]的文件描述符，无法往p管道中写数据，防止从p中读数时被堵塞
if(read(0, &prime, 4)){
printf("prime: %d\n", prime); // 打印父进程管道的第一个数
pipe(p1);
if(fork()==0){ // child
recur_sieve(p1);
}else{
while(read(0, &num, 4)){ // 父进程继续筛选不能被当前质数整除的数，我称之为质数侯选数
if(num%prime!=0){
write(p1[1], &num, 4); //把质数侯选数写入管道p1中
}
}
if (close(p1[1]) == -1) {// 关闭父进程的写端，不然子进程读取管道的时候，管道读端会堵塞；
fprintf(2, "error: failed to close p1[1]\n");
exit(1);
}
wait(0);
}
}
exit(0);
}
int main(int argc, char* argv[]){
int p[2];
pipe(p);
for(int i=2;i<SIZE+1;i++){
write(p[1], &i, 4);
}
if(fork()==0){
recur_sieve(p); //传递的数组，其实就是传递的地址
}else{
if (close(p[1]) == -1) {
fprintf(2, "error: failed to close p1[1]\n");
exit(1);
}
wait(0);
}
exit(0);
}
注：由于程序并不会主动报告错误，所以需要我们来判断系统调用的返回数是否正确，否则即使整个程序正常运行退出了，也不代表程序没有问题，所以需要加入返回数检查，比如
if (close(p[1]) == -1) {
fprintf(2, "error: failed to close p1[1]\n");
exit(1);
}
3、思考小结
学习了埃式筛筛出一个范围内所有质数的思想，该实现过程递归地创建了多个子进程，每个递归调用可以看作一个筛子，从父进程中读取质数候选数，然后进行筛选，得到新的质数候选数，该质数候选数又会传递该进程创建的子进程。相当于每两个进程之间通过一个管道来进行通信。
加深了fork的理解。fork创建的子进程会复制父进程的文件描述符和内存内容。但是二者又是隔离的，也就是子进程的操作并不会影响到父进程，比如子进程中close文件描述符，并不会close到父进程的文件描述符，因为子进程复制的文件描述符，只是使得指向该文件的引用多了一份，close子进程的文件描述符，只是会导致指向该文件的引用-1，只有指向该文件的所有文件描述符都被关闭了，该文件才会被关闭。所以父进程往管道里面写完以后，要把该父进程指向管道写端的文件描述符给关闭，不然子进程无法关闭父进程的文件描述符，导致该管道的写端一直打开，无法读取数据。
参考：6.S081-Lab1 总结笔记（0基础向）_lab1make grade 出错-CSDN博客
四、find
find(path, filename)就是在指定目录下查找是否有该文件。所以思路就是遍历该路径下的每一个目录，查找是否有该文件，如果有，则打印出该文件的相对路径。
1、实现代码
参考ls的部分代码，因为ls和find之间有类似的地方，ls是列出指定目录下所有文件和目录，而find是递归查找指定目录下是否包含指定的文件。
#include "kernel/types.h"
#include "kernel/fs.h"
#include "kernel/stat.h"
#include "user/user.h"
void find(char* path, char* filename){
// 遍历path下面的所有目录，如果存在名为filename的文件，则打印出其路径
char buf[512], *p;
int fd, fd1;
struct dirent de;
struct stat st, st1;
if((fd=open(path, 0))<0){ // 以只读模式打开path路径
fprintf(2, "find: can't open path\n");
close(fd);
exit(0);
}
// 获取文件元信息
if(fstat(fd, &st)<0){
fprintf(2, "find: can't get fd's state\n");
close(fd);
exit(0);
}
// 对打开的路径的文件类型进行判断，如果为文件，那么则报错退出
// 如果为目录，则判断该目录下所有目录和本身目录是否含有filename，有则打印路径
switch(st.type){
case T_FILE:
fprintf(2, "find: path is a file, but need a directory\n");
exit(0);
case T_DIR: // 为目录，则进行递归查找；
if(strlen(path) + 1 + DIRSIZ + 1 > sizeof(buf)){
printf("ls: path too long\n");
break;
}
strcpy(buf, path); // 复制path到buf
p = buf+strlen(buf);
*p++ = '/';
while((read(fd, &de, sizeof(de))==sizeof(de))){
if(de.inum==0){ // id.inum==0， 说明这个目录里面是空的
continue;
}
// 不遍历.和..，即当前目录和上一级目录
if(!strcmp(de.name, ".") || !strcmp(de.name, "..")){
continue;
}
memmove(p, de.name, DIRSIZ);
p[DIRSIZ]=0;
// 接着对该目录下的所有文件（包含目录进行判断）
if((fd1=open(buf, 0))>0){
if(fstat(fd1, &st1)>=0){
switch(st1.type){
case T_FILE:
if(!strcmp(de.name, filename)){
printf("%s\n", buf);
}
close(fd1);
break;
case T_DIR:
close(fd1);
find(buf, filename);
break;
default:
close(fd1);
break;
}
}else{
close(fd1);
}
}
}
}
close(fd);
}
int main(int argc, char* argv[]){
if(argc!=3){
fprintf(2, "Usage: find path filename\n");
exit(0);
}
find(argv[1], argv[2]);
exit(0);
}
2、反思小结
构建字符串的时候需要手动为字符串末尾指定空字符0， 注意打开的文件描述符，不使用了记得关闭。
五、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 程序：从标准输入中读取行并为每一行运行一个命令，将该行作为命令的参数提供。您的解决方案应该在文件 user/xargs.c 中。
1、理论
Xargs将标准输入转化成命令行参数，执行程序
command1 | xargs command2
先执行command1，然后通过管道把command1的结果输出到xargs中，xargs拆分参数，执行command2;
例如：
$ echo hello too | xargs echo bye
bye hello too
$
$ echo "1\n2" | xargs -n 1 echo line
line 1
line 2
2、代码实现
shell会根据空格把命令行命令划分为字符串数组，所以xargs从标准输入获取的参数，也需要我们手动实现按照空格进行划分，然后把参数凭借在一起，每一行执行一次程序，每次执行程序都要保证传入的参数是字符串数组。
源码：
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/param.h"
#define MAXLINE 512 // 最大输入行数
#define MAXARGS 32 // 每个命令最多接受的参数个数
// 自定义函数：手动分割字符串
int split(char *str, char *args[]) {
int argc = 0;
char *p = str;
while (*p != '\0') {
// 跳过空格
while (*p == ' ' || *p == '\t') p++;
if (*p == '\0') break; // 结束条件，遇到字符串结尾
args[argc++] = p; // 记录当前参数的起始位置
// 找到下一个空格或字符串结尾
while (*p != '\0' && *p != ' ' && *p != '\t') p++;
if (*p != '\0') {
*p = '\0'; // 将空格替换为字符串结束符
p++; // 跳过空格，准备处理下一个参数
}
if (argc >= MAXARGS) break; // 如果参数个数过多，停止处理
}
return argc;
}
int main(int argc, char *argv[]) {
// 从标准输入读取数据
char stdIn[MAXLINE];
int size = read(0, stdIn, sizeof stdIn);
// 计算行数
int line = 0;
for (int k = 0; k < size; ++k) {
if (stdIn[k] == '\n') {
++line;
}
}
// 存储每行数据
char output[line][64];
int i = 0, j = 0;
// 将每行数据存储到 output 数组中
for (int k = 0; k < size; ++k) {
output[i][j++] = stdIn[k];
if (stdIn[k] == '\n') {
output[i][j - 1] = 0; // 用 0 结束字符串，去掉换行符
++i; // 继续保存下一行数据
j = 0;
}
}
// 将数据分行拼接到 argv[2] 后，并运行
char *arguments[MAXARGS];
int k = 0;
// 将原命令（argv[1]）传入
for (j = 0; j < argc - 1; ++j) {
arguments[j] = argv[1 + j];
++k;
}
// 按行处理每个输入
for (i = 0; i < line; ++i) {
// 使用自定义的 split 函数将每行按空格分割
split(output[i], arguments + k); // 传递 arguments[k] 作为存储地址
// 执行命令
if (fork() == 0) {
exec(argv[1], arguments);
exit(0);
}
wait(0); // 等待子进程执行完毕
}
exit(0);
}
3、反思感悟
对于内存的管理的理解上面还存在不足，还是不太习惯C语言的代码风格，很多细节不足，慢慢来吧。
六、总结
第一个实验写得磕磕碰碰，参考了很多大佬的思路和代码，不过也算有收获。