lab 1 Xv6 and Unix Utilities

2022/09/22

mit 6.828 是 mit 的一个操作系统的公开实验课，立志在十一月之前刷完这个课程！

1. Boot xv6

首先需要安装编译工具链，可以直接参考官方文档来进行，支持Linux与Mac OS，Windows需要在虚拟机里面运行，我使用的是 Debian 可以直接通过 apt 进行安装

sudo apt-get install git build-essential gdb-multiarch qemu-system-misc gcc-riscv64-linux-gnu binutils-riscv64-linux-gnu

在成功安装之后就可以通过 git 下载代码仓库

git clone git://g.csail.mit.edu/xv6-labs-2020

然后切换到本 lab 所用的分支中

git checkout util

然后就可以开始编译运行啦

make qemu

还有两个常用的快捷键，一个是 Ctrl-p 用于显示进程信息，就像 ps 一样，还有一个是Ctrl-a x 用于退出系统，相当于 exit。好啦到这里环境就配置好了，可以开始编写代码完成下面的lab了。

2. sleep

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.

#include "kernel/types.h"
#include "user/user.h"

int main(int argc, char *argv[]){
    if(argc < 2){       // 如果没有传入参数  
        printf("you forget password parameter\n");
        exit(1);
    }
    int value = atoi(argv[1]);  
    sleep(value);           // 调用内核函数
    exit(0);
}

在编写完成之后可以使用

./grade-lab-util sleep

来检测编写是否正确，下面的 lab 都可以使用

3. 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.

这里用到了管道，在Linux中管道的初始化是 pipe 函数，它需要传入一个长度为2的 int 类型数组，在完成初始化之后，这个 int 类型数组的第一个元素被初始化为当前管道的读取文件描述符，第二个元素被初始化为当前管道的写入文件描述符，需要注意的是当管道里面没有数据的时候调用 read 函数是会堵塞的。

这里用到了两个管道，一个是由父进程写给子进程的，一个是子进程写给父进程的，因为如果只使用一个管道的话不能保证读取顺序，可能父进程写入的数据就被父进程直接读取了，然后子进程读取不到数据就杜塞了，导致整个程序杜塞

#include "kernel/types.h"
#include "user/user.h"


int main(int* argc, char *argv[]){
    const uint bufferSize = 10;
    char buffer[bufferSize];  // 缓冲区

    int f2c[2]; // fd[0] is set up for reading, fd[1] is set up for writing
    int c2f[2];
    if(pipe(f2c) < 0){
        printf("can not create ch_a\n");
    }
    if(pipe(c2f) < 0){
        printf("can not create ch_b\n");
    }
    
    if(fork() == 0){                                    // 子进程
        read(f2c[0], buffer, bufferSize);
        printf("%d: received ping\n", getpid());
        write(c2f[1], "world", 6);
    }else{                                              // 父进程
        write(f2c[1], "hello", 6);
        read(c2f[0], buffer, bufferSize);
        printf("%d: received pong\n", getpid());        
    }
    exit(0);
}

这里需要使用两个管道，因为在父进程写入之后通过会有父进程与子进程来读取，如果只有一个管道则不能保证是那个先读取出来，所以需要两个管道，一个专门用来将父进程的数据传输给子进程，另一个则是专门将子进程的数据传输给父进程。

3. 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.

这个的意思就是写一个流水线的质素筛，经过主线程的初始化最后就可以递归调用解题

#include <kernel/types.h>
#include <user/user.h>


void pipeline(int pfd){
    int v, n;
    if(0 == read(pfd, &v, sizeof(int))){            // 读取第一个字符
        close(pfd);
        exit(0);
    }
    printf("prime %d\n", v);                        // 输出第一个字符
    int p[2];
    pipe(p);

    if(fork() == 0){
        close(p[1]);                                // 无法保证写入段已经关闭了，这里再关一次
        pipeline(p[0]);                             // 递归调用
    }else{
        while(1){
            if(read(pfd, &n, sizeof(int)) == 0){
                close(pfd);
                break;
            }
            if(n % v != 0){
                write(p[1], &n, sizeof(int));
            }
        }
        close(p[1]);                                // 关闭写入
        wait((int*)0);
    }
}


int main(int argc, char* argv[]){
    int p[2];
    pipe(p);        // 管道初始化

    if(fork() == 0){            // 第一个子进程
        close(p[1]);
        pipeline(p[0]);         // 调用流水线函数进行处理
    }else{
        for(int i = 2; i <= 35; i++){               // 将数据写入管道
            write(p[1], &i, sizeof(int));
        }
        close(p[1]);                                // 这个管道已经不需要写入了可以直接关闭
        wait((void *)0);
    }
    exit(0);
}

4. 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.

这个可以参考 ls.c 里面的程序来写，在 Linux 中一切皆文件所以文件夹也是文件，首先需要使用 open 函数来获取文件的文件描述符，然后通过 fstat 函数来获取文件状态，如果只是普通文件就可以直接将文件名与目标文件名进行对比，如果是文件夹则需要通过 read 函数来读取文件夹中的所有元素，需要注意的是要忽略 . 与 .. 。

// find.c
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"

void find(char *path, char *target) {
    char buf[512], *p;
    int fd;
    struct dirent de;
    struct stat st;

    if((fd = open(path, 0)) < 0){
        fprintf(2, "find: cannot open %s\n", path);
        return;
    }

    if(fstat(fd, &st) < 0){
        fprintf(2, "find: cannot stat %s\n", path);
        close(fd);
        return;
    }

    switch(st.type){
    case T_FILE:
        // 只对比最后 len(target) 长的字符串
        if(strcmp(path+strlen(path)-strlen(target), target) == 0) {         
            printf("%s\n", path);
        }
        break;
    case T_DIR:
        if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
            printf("find: path too long\n");
            break;
        }
        strcpy(buf, path);
        p = buf+strlen(buf);
        *p++ = '/';
        while(read(fd, &de, sizeof(de)) == sizeof(de)){
            if(de.inum == 0)
                continue;
            memmove(p, de.name, DIRSIZ);
            p[DIRSIZ] = 0;
            if(stat(buf, &st) < 0){
                printf("find: cannot stat %s\n", buf);
                continue;
            }
            if(strcmp(buf+strlen(buf)-2, "/.") != 0 && strcmp(buf+strlen(buf)-3, "/..") != 0) {
                find(buf, target); // 递归查找
            }
        }
        break;
    }
    close(fd);
}

int main(int argc, char *argv[]){
    if(argc < 3){
        exit(0);
    }
    char target[512];
    target[0] = '/'; // 为查找的文件名添加 / 在开头
    strcpy(target+1, argv[2]);
    find(argv[1], target);
    exit(0);
}

5. 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.

大致的思路为，首先保存原有的参数列表，逐个字符的读取标准输入，直到遇到换行符，然后把读取到的数据添加到参数列表中，然后调用exec执行相应的命令并传入参数列表

#include <kernel/types.h>
#include <user/user.h>
#include <kernel/param.h>


/*
1. 读取标准输入
2. 执行指定程序并传入参数
*/
int main(int argc, char* argv[]){
    char* args[MAXARG];         // 参数列表
    int i = 0;                  
    for(; i < argc; i++){       // 将参数写入参数列表
        args[i] = argv[i];
    }
    char buff[256];
    while(1){
        int j = 0;
        for(; (read(0, buff+j, sizeof(char)) != 0) && buff[j] != '\n';){++j;}
        if(j == 0){break;}
        buff[j] = 0;                    // 添加上0作为字符串
        args[i] = buff;
        args[i+1] = 0;                  // 添加上0作为字符串
        if(fork() == 0){                // 子进程
            exec(args[1], args + 1);    // 忽略 xargs 这个参数
        }else{                          // 父进程
            wait((void*)0);
        }
    }
    exit(0);
}