【MIT 6.S081】Lab1: Xv6 and Unix utilities

更新于 分类于 阅读次数： 本文字数： 8.5k 阅读时长 ≈ 8 分钟

MIT 6.S081的Lab1: Xv6 and Unix utilities题解

Boot xv6 (easy)

这个在环境配置里已经做过了，注意退出系统是按ctrl+a后按x，查看进程是ctrl+p，根据后面报错和网上教程在这里先做一些调整：由于我的/usr/bin下有python3，于是把grade-lab-util文件的第一行修改为#!/usr/bin python3

sleep (easy)

要求

实现UNIX的sleep程序，使得系统停止用户指定的时钟数，这里的时钟由xv6内核决定，程序放在user/sleep.c

分析

首先对用户传的参数进行判断，错误的话打印错误信息并退出；之后将参数用提示中说的atoi转成整型再使用系统调用sleep就可以了。

有兴趣的话可以去看内核代码kernal/sysproc.c中的函数sys_sleep

实现

编辑user/sleep.c文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(int agrc, char *agrv[]){
    if(agrc < 2) {
        fprintf(2, "error: sleep time is required!\n");
        exit(1);
    }
    int sleep_time = atoi(agrv[1]);
    sleep(sleep_time);
    exit(0);
}

编辑Makefile文件，在UPROGS=\一栏添加如下内容：

1
$U/_sleep\

测试

输入下面的命令，注意不是官网上的./grade-lab-util sleep：

1
sudo python3 grade-lab-util sleep

pingpong (easy)

要求

使用系统调用实现两个进程使用管道通信，父进程向子进程发送信息，等待子进程结束，从管道读取子进程发的信息，打印进程id: received pong，结束进程；子进程打印进程id: received ping ，将信息发给父进程，结束子进程。程序放在user/pingpong.c

分析

创建两个管道，一个用于父进程到子进程通信，另一个用于子进程到父进程通信。创建子进程，分别对父子进程编程：一个先写后读，一个先读后写。这里没有提示要用close，在官方文档对管道的解说里是有close的，写了下代码，关不关闭这里都是可以通过的。

实现

编辑user/pingpong.c文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(int agrc, char *agrv[]) {
    int p_cp[2], p_pc[2];
    pipe(p_cp);
    pipe(p_pc);
    char buf[2];
    int pid = fork();
    if(pid < 0) {
        fprintf(2, "error: fail to fork!\n");
        exit(1);
    }
    else if(pid > 0) {      // parent
        close(p_pc[0]);     // parent_to_child read
        close(p_cp[1]);     // child_to_parent write
        if(write(p_pc[1], "p", 1) != 1) {
            fprintf(2, "error: parent fail to write!\n");
            exit(1);
        }
        close(p_pc[1]);     // parent_to_child write
        if(read(p_cp[0], buf, 1) != 1) {
            fprintf(2, "error: parent fail to read!\n");
            exit(1);
        }
        close(p_cp[0]);     // child_to_parent read
        if(buf[0] == 'c') {
            printf("%d: received pong\n", getpid());
        }
        else {
            fprintf(2, "error: parent receives wrongly\n");
            exit(1);
        }
        exit(0);
    }
    else {  // child
        close(p_pc[1]);     // parent_to_child write
        close(p_cp[0]);     // child_to_parent read
        if(read(p_pc[0], buf, 1) != 1) {
            fprintf(2, "error: child fail to read!\n");
            exit(1);
        }
        close(p_pc[0]);     // parent_to_child read
        if(buf[0] == 'p') {
            printf("%d: received ping\n", getpid());
        }
        else {
            fprintf(2, "error: child receives wrongly\n");
            exit(1);
        }
        if(write(p_cp[1], "c", 1) != 1) {
            fprintf(2, "error: child fail to write!\n");
            exit(1);
        }
        close(p_cp[1]);     // child_to_parent write
        exit(0);
    }
}

简略版（省去close和错误信息）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(int agrc, char *agrv[]) {
    int p_cp[2], p_pc[2];
    pipe(p_cp);
    pipe(p_pc);
    char buf[2];
    int pid = fork();
    if(pid > 0) {      // parent
        write(p_pc[1], "p", 1);
        read(p_cp[0], buf, 1);
        if(buf[0] == 'c') {
            printf("%d: received pong\n", getpid());
        }
    }
    else {  // child
        read(p_pc[0], buf, 1);
        if(buf[0] == 'p') {
            printf("%d: received ping\n", getpid());
        }
        write(p_cp[1], "c", 1);
    }
    exit(0);
}

编辑Makefile文件，在UPROGS=\一栏添加如下内容：

1
$U/_pingpong\

测试

输入命令：

1
sudo python3 grade-lab-util pingpong

上面是简略版代码的测试结果，下面是完整版代码的测试结果，均通过：

primes (moderate/hard)

要求

利用pipe和fork完成埃式筛素数，输出2-35的所有素数，程序放在user/primes.c

分析

给出了思路提示：

  • 图片的意思是每个进程取出当前最小的素数输出，并利用埃式筛的原理去除该素数的倍数，将剩余的数传给下一个进程，直到 3535

  • 上述思路父子进程不断嵌套，考虑在一个无尽的循环里对父子进程分别操作

  • 有一个数组用于保存当前的素数集，数组的第 00 位存放素数个数 nn，第 11 至 nn 位存放对应的每一个素数

  • 每次循环里，父进程输出素数集的第 11 位即当前的第一个素数，并对剩下的素数进行筛选存入一个临时素数集（存放规则仍同上）中，筛完将其通过管道整体送给子进程，等待子进程完成后中止

  • 每次循环里，子进程读出管道中的第一个整型数据（应为父进程给的素数个数），如果为 00 中止进程，否则将管道中剩余数据全部读入素数集，开新管道，开新进程

  • 注意主进程要等所有进程结束才能结束，且注意关闭文件描述符防止越界

实现

编辑user/primes.c文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(int agrc, char *agrv[]) {
    int p[2];
    int prime[35], newprime[35];    // [1...[0]]: current primes
    pipe(p);
    prime[0] = 34;
    for(int i = 2; i <= 35; i++) {
        prime[i - 1] = i;           // init
    }
    int pid = fork();
    while(1) {
        if(pid < 0) {
            fprintf(2, "error: fail to fork!\n");
            exit(1);
        }
        else if(pid > 0) {          //parent
            printf("prime %d\n", prime[1]);
            close(p[0]);            // read close
            newprime[0] = 0;        // count new primes
            for(int i = 2; i <= prime[0]; i++) {
                if(prime[i] % prime[1] != 0) {
                    newprime[++newprime[0]] = prime[i];
                }
            }
            write(p[1], newprime, sizeof(int) * (newprime[0] + 1));
            close(p[1]);
            wait(0);
            exit(0);
        }
        else {
            close(p[1]);            // close write
            read(p[0], prime, sizeof(int));
            if(prime[0] == 0) {
                exit(0);            // finish: no more primes
            }
            read(p[0], prime + 1, sizeof(int) * prime[0]);
            close(p[0]);
            pipe(p);
            pid = fork();
        }
    }
    exit(0);
}

编辑Makefile文件，在UPROGS=\一栏添加如下内容：

1
$U/_primes\

测试

输入命令：

1
sudo python3 grade-lab-util primes

输入命令：

1
make qemu

find (moderate)

要求

写一个模仿UNIX中find指令的简单程序，指令给出特定查找目录，和特定查找文件名，输出目录树中所有匹配的文件，程序放在user/find.c

分析

  • 看ls.c的源代码可能会用到的东西

    • fstat(路径，文件信息结构体指针)：将路径指向的文件（文件已打开）信息拷贝至后面所给的结构体，stat基本一样但是路径指向的文件不是已打开状态。

    • open函数打开文件成功返回文件描述符，否则返回 −1-1

    • read函数从指定设备/文件中读取指定字节数，成功则返回读取的字节数，否则返回 −1-1

    • strcmp函数比较传进去两个字符串的值，相等返回 00 ，否则返回非 00

    • 其余关于文件的标识什么的看英文大概能猜，问题不大

  • ls.c源代码浅说：

    • ls函数的流程

      • 尝试打开文件，获得文件信息（代码switch之前）

      • （代码switch之后）如果给的路径是文件输出文件信息，如果给的路径是目录，利用while循环读该目录下的所有文件/目录，获得文件信息后输出文件信息

    • fmtname函数：取传入路径字符串的最深文件名，如果是./a/b，返回的是b；如果是./a，返回的是a

  • 思路：对ls.c进行修改，新的ls函数中，如果路径是文件就利用fmtname函数取文件名进行比较；如果路径是目录在获得文件信息后递归这个文件/目录

  • 提示：不要递归到.和..，否则会无限递归

  • 坑点，ls.c打印文件时有用空格对齐（在fmtname函数的倒数第二步），而我们对是否是所需文件的判断在新的ls函数判断出路径是文件之后，使用fmtname函数取文件名，多余空格会影响strcmp的结果

实现

编辑user/find.c文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
char* newfmtname(char *path) {
    static char buf[DIRSIZ+1];
    char *p;
    for(p = path + strlen(path); p >= path && *p != '/'; p--);
    p++;
    if(strlen(p) >= DIRSIZ)
        return p;
    memmove(buf, p, strlen(p));
    buf[strlen(p)] = 0;     // different from fmtname in ls.c
    return buf;
}
void findfile(char *path, char *name) {
    char buf[512], *p;
    int fd;
    struct dirent de;
    struct stat st;
    if((fd = open(path, 0)) < 0) {
        fprintf(2, "ls: cannot open %s\n", path);
        return;
    }
    if(fstat(fd, &st) < 0) {
        fprintf(2, "ls: cannot stat %s\n", path);
        close(fd);
        return;
    }
    switch(st.type) {
    case T_FILE:            // check this filename
        if(strcmp(newfmtname(path), name) == 0)
            printf("%s\n", path);
        break;
    case T_DIR:             
        if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf) {
            printf("ls: 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;
            if(strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0)
                continue;
            memmove(p, de.name, DIRSIZ);    // add file name to path
            p[DIRSIZ] = 0;
            findfile(buf, name);
        }
        break;
    }
    close(fd);
}
int main(int agrc, char *agrv[]) {
    if(agrc != 3) {
        fprintf(2, "wrong path or filename!\n");
        exit(1);
    }
    findfile(agrv[1], agrv[2]);
    exit(0);
}

编辑Makefile文件，在UPROGS=\一栏添加如下内容：

1
$U/_find\

测试

输入命令：

1
sudo python3 grade-lab-util find

xargs (moderate)

要求

写一个模仿UNIX中xargs指令的简单程序，从标准输入读取行并为每一行运行一个命令，将该行作为参数提供给命令，程序放在user/xargs.c

分析

  • 题意：可能因为我没用过UNIX系统中的这个指令，看了半天也没太看明白，先写了个输出传入main函数的参数的程序，发现输出的是xargs后面的部分，那这个指令大概是标准输入读取的是前面部分指令执行的结果（已经执行过了，直接读就可以），标准输入每行添加到原本的参数（argv）后面执行。

  • 将原本的参数放进一个新的字符串数组，标记一下原参数结尾的位置，每从标准输入读一行（\n结尾），将其添加到参数后面，fork() 一个子程序用来执行这个指令

  • kernal/exec.c中可以查到exec指令的代码，第一个参数传名字第二个参数传字符串数组

  • 注意kernel/param.h声明了MAXARG，exec的最大参数量，可以用于开数组

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
#include "kernel/param.h"
int main(int argc, char* argv[]) {
    char* newargv[MAXARG];      // args for exec
    char** lastpos = newargv;   // arg_last_pos
    for (int i = 1; i < argc; i++, lastpos++)
        *lastpos = argv[i];     // point to argv
    char** argv_cur = lastpos;  // fill argv
    char buf[MAXARG][100];      // store args from stdin
    memset(buf, 0, MAXARG * 100);
    int i = 0, j = 0;
    while (read(0, buf[i] + j, 1) > 0) {
        if (buf[i][j] == ' ') { // end of a word
            buf[i][j] = 0;
            *argv_cur = buf[i];
            argv_cur++;
            i++, j = 0;
        }
        else if (buf[i][j] == '\n') {
            buf[i][j] = 0;
            *argv_cur = buf[i];
            i = j = 0;
            int pid = fork();
            if (pid == 0) {     // children
                argv_cur++;
                **argv_cur = 0;
                exec(argv[1], newargv);
                exit(0);
            }
            else {              // parent
                wait(0);
                argv_cur = lastpos;
            }
        }
        else
            j++;                // next char 
    }
    exit(0);
}

编辑Makefile文件，在UPROGS=\一栏添加如下内容：

1
$U/_xargs\

测试

在系统里输入命令：

1
sh < xargstest.sh

以下是文档给的样例和测试的两个结果截图：