Lab 1: Xv6 and Unix utilities

operating system
MIT 6.S081
发布日期:   2024-05-06
更新日期:   2024-12-07
文章字数:   2.2k
阅读时长:   10 分

Lab 1: Xv6 and Unix utilities

环境配置

  • 机器OS: ubuntu 20.04
  • 安装实验相关包:
    1
    $ sudo apt-get install git build-essential gdb-multiarch qemu-system-misc gcc-riscv64-linux-gnu binutils-riscv64-linux-gnu

一、启动 xv6（难度：easy）

  • 克隆xv6 代码并切换到util 分支

    1
    2
    3
    4
    5
    6
    7
    $ git clone git://g.csail.mit.edu/xv6-labs-2021
    Cloning into 'xv6-labs-2021'...
    ...
    $ cd xv6-labs-2021
    $ git checkout util
    Branch 'util' set up to track remote branch 'util' from 'origin'.
    Switched to a new branch 'util'

  • 构建并运行xv6

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    $ make qemu
    riscv64-unknown-elf-gcc    -c -o kernel/entry.o kernel/entry.S
    riscv64-unknown-elf-gcc -Wall -Werror -O -fno-omit-frame-pointer -ggdb -DSOL_UTIL -MD -mcmodel=medany -ffreestanding -fno-common -nostdlib -mno-relax -I. -fno-stack-protector -fno-pie -no-pie   -c -o kernel/start.o kernel/start.c
    ...  
    riscv64-unknown-elf-ld -z max-page-size=4096 -N -e main -Ttext 0 -o user/_zombie user/zombie.o user/ulib.o user/usys.o user/printf.o user/umalloc.o
    riscv64-unknown-elf-objdump -S user/_zombie > user/zombie.asm
    riscv64-unknown-elf-objdump -t user/_zombie | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$/d' > user/zombie.sym
    mkfs/mkfs fs.img README  user/xargstest.sh 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 
    nmeta 46 (boot, super, log blocks 30 inode blocks 13, bitmap blocks 1) blocks 954 total 1000
    balloc: first 591 blocks have been allocated
    balloc: write bitmap block at sector 45
    qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0

    xv6 kernel is booting

    hart 2 starting
    hart 1 starting
    init: starting sh
    $

  • 使用ls 输出mkfs 在初始文件系统中包含的文件

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    $ ls
    .              1 1 1024
    ..             1 1 1024
    README         2 2 2059
    xargstest.sh   2 3 93
    cat            2 4 24256
    echo           2 5 23080
    forktest       2 6 13272
    grep           2 7 27560
    init           2 8 23816
    kill           2 9 23024
    ln             2 10 22880
    ls             2 11 26448
    mkdir          2 12 23176
    rm             2 13 23160
    sh             2 14 41976
    stressfs       2 15 24016
    usertests      2 16 148456
    grind          2 17 38144
    wc             2 18 25344
    zombie         2 19 22408
    console        3 20 0

  • 使用ctrl-a x 退出qemu ，Ctrl-a 按完松手再按x 退出

二、Sleep实现（难度：easy）

实现xv6的UNIX程序sleep：您的sleep应该暂停到用户指定的计时数。一个滴答(tick)是由xv6内核定义的时间概念，即来自定时器芯片的两个中断之间的时间

学习main 函数的两个参数argc 和argv[] 的含义，将参数传入sleep 系统调用即可实现相关功能。

  • argc 是命令行总的参数个数。
  • argv[] 为保存命令行参数的字符串指针。其中第0个参数是程序的全名，以后的参数为命令行后面跟的用户输入的参数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// "user/sleep.cpp"
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(int argc, char *argv[]) {
    if(argc != 2) {
        char *msg = {"please input sleep time, usage: ./sleep <number>\n"};
        write(1, msg, strlen(msg));
    }
    int t = atoi(argv[1]);
    sleep(t);
    exit(0);
}

在Makefile 中UPROGS 处添加$U/_sleep\

三、pingpong实现（难度：easy）

实现xv6的UNIX程序pingpong：编写一个程序，使用UNIX系统调用在一对管道上的两个进程之间 “ping-pong” 一个字节，每个方向一个。父级应该向子级发送一个字节; 子级应该打印 “<pid>: received ping”，其中 <pid> 是其进程ID，将管道上的字节写入父级，然后退出; 父级应该从子级读取字节，打印 “<pid>: received pong”，然后退出。

学习管道的使用，通过使用pipe 系统调用来实现管道功能，通过fork 系统调用来实现子进程的创建。

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
// "user/pingpong.cpp"
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

#define MSG_SIZE 4
#define READEND 0
#define WRITEEND 1
const char *msg_f = "ping"; 
const char *msg_s = "pong"; 

int main(int argc, char* argv[])
{
    char buf[MSG_SIZE];
    int pf[2], ps[2];   // 创建管道输入端口和输出端口
    int ppf = pipe(pf);   // 创建管道
    int pps = pipe(ps);
    if(ppf < 0 || pps < 0)
        exit(1);
    
    int pid = fork();

    if(pid == 0) {  // 子进程
        // 关闭父进程管道的写端口以及子进程管道的读端口
        close(ps[READEND]);
        close(pf[WRITEEND]);

        read(pf[READEND], buf, MSG_SIZE);
        printf("%d: received %s\n", getpid(), buf);
        write(ps[WRITEEND], msg_s, MSG_SIZE);
        exit(0);
    } else {        // 父进程
        close(ps[WRITEEND]);
        close(pf[READEND]);

        write(pf[WRITEEND], msg_f, MSG_SIZE);
        read(ps[READEND], buf, MSG_SIZE);
        printf("%d: received %s\n", getpid(), buf);
    }
    exit(0);
}

在Makefile 中UPROGS 处添加$U/_pingpong\

四、Primes实现（难度：moderate/hard）

使用管道编写prime sieve(筛选素数)的并发版本。

  • 由于一个数的因数一定比该数本身小，所以可以使用比当前数小的所有素数进行筛选
  • 如果当前数不是已确定的所有素数的倍数，则该数为素数
  • 若该数为素数，则以该数为基创建子进程，并和与该数最接近的素数建立管道
  • 对每个数都使用串联的所有素数进行判断，直到确定其为合数或素数
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
// "user/primes.cpp"
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

#define READEND     0
#define WRITEEND    1
#define MAX_NUM     35

void prime(int p[2]) {
    // ...
    close(p[WRITEEND]);
    int base;
    if(!read(p[READEND], &base, sizeof(int))) {   // 读取传来的数据
        exit(1);
    }
    printf("prime %d\n", base);

    int pr[2];
    int num;
    pipe(pr);
    int pid = fork();
    if(pid == 0) {
        prime(pr);
    } else {
        close(pr[READEND]);
        while(read(p[READEND], &num, sizeof(int))) {
            if(num % base != 0) {
                write(pr[WRITEEND], &num, sizeof(int));
            }
        }
        close(pr[WRITEEND]);
    }

    close(p[READEND]);
}
 
int main(int argc, char *argv[])
{
    int p[2];
    int left;
    
    pipe(p);
    int pid = fork();
    if(pid == 0) {
        prime(p);
    } else {    // 父进程
        close(READEND);
        for(int i = 2; i <= MAX_NUM; i++) {
            left = i;
            write(p[WRITEEND], &left, sizeof(int));
        }
        close(p[WRITEEND]);
    }
    wait(0);
    exit(0);
}

在Makefile 中UPROGS 处添加$U/_primes\

五、find实现（难度：Moderate）

写一个简化版本的UNIX的find程序：查找目录树中具有特定名称的所有文件

学习ls 的实现逻辑，遍历目录树，寻找指定的文件名即可。

  • 注意：处理目录树中的两个特殊文件"." 和".."
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// "user/find.cpp"
#include "kernel/types.h"
#include "kernel/stat.h"
#include "kernel/fs.h"
#include "user/user.h"

char *fmtname(char *path)
{
    static char buf[DIRSIZ + 1];
    char *p;

    // Find first character after last slash.
    for (p = path + strlen(path); p >= path && *p != '/'; p--)
        ;
    p++;

    // Return blank-padded name.
    if (strlen(p) >= DIRSIZ)
        return p;
    memmove(buf, p, strlen(p));
    memset(buf + strlen(p), 0, DIRSIZ - strlen(p));
    return buf;
}

void find(char *path, char *filename)
{
    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:
        if (strcmp(fmtname(path), filename) == 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(de.name, ".") == 0 || strcmp(de.name, "..") == 0)
                continue;
            find(buf, filename);
        }
        break;
    }
    close(fd);
}

int main(int argc, char *argv[])
{
    if (argc < 3)
    {
        printf("usage: find <path> <filename>\n");
        exit(1);
    }
    find(argv[1], argv[2]);
    exit(0);
}

在Makefile 中UPROGS 处添加$U/_find\

六、xargs实现（难度：Moderate）

编写一个简化版UNIX的xargs程序：它从标准输入中按行读取，并且为每一行执行一个命令，将行作为参数提供给命令。

这个题目在第一次做的时候还是很难理解的，主要是参考了这篇文章

1、xargs的作用

我们知道管道(pipe) 是将前一个进程的输出(stdout) 作为下一下进程的输入(stdin) ，但是管道命令仅能处理standard output ，也就是说类似less 、head 、tail 等可以接受标准输入的命令。

而有很多命令不接收管道的传递方式，比如ls 和echo ，它们不能直接接收标准输入，而需要接收命令行参数，这时候就需要使用xargs 命令将管道传输过来的stdin 进行处理然后传递到命令的参数位上。也就是说，xargs 在这里执行了两个行为:

  • 处理管道左侧的标准输入
  • 处理后传递到正确的位置上

例如 echo "one two three" | xargs mkdir 等价于执行 mkdir one two three ，如果不加 xargs 则会提示 mkdir 缺少操作参数。

2、实现思路

事实上，就是从标准输入中读取字符串，直到遇到 \n 或 \r 则完成一次输入， 然后将所有的参数都读进来放在一个字符串数组里，然后将每一行都作为一个参数 fork 出一个子进程来执行 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// user/xargs.cpp
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/param.h"

#define BUFFER_SIZE 512

void mygets(char *buf, int max)
{
    char c;
    int i;
    for (i = 0; i + 1 < max; i++)
    {
        int cc = read(0, &c, 1);
        if (cc < 1)
            break;
        if (c == ' ' || c == '\n' || c == '\r')
            break;
        buf[i] = c;
    }
    buf[i] = '\0';
}

int getcmd(char *buf, int nbuf)
{
    memset(buf, 0, nbuf);
    mygets(buf, nbuf);
    if (buf[0] == 0)
        return -1; // EOF标志位
    return 0;
}

int main(int argc, char *argv[])
{
    if (argc < 2)
    {
        fprintf(2, "Usage: xargs <command>\n");
        exit(1);
    }
    char *_argv[MAXARG];
    int _argc = argc - 1;
    for (int i = 0; i < _argc; i++)
    {
        _argv[i] = argv[i + 1]; // 构造新命令参数，排除 "xargs" 这个字符串
    }
    char buf[BUFFER_SIZE];
    while (getcmd(buf, sizeof(buf)) != -1)  // 读取标准输入中的字符串，即其他命令执行的结果
    {
        if (fork() == 0)
        {
            _argv[_argc] = buf;
            _argc++;
            exec(argv[1], _argv);   // argv[1] 为 xargs 要执行的命令
            fprintf(2, "exec %s failed\n", argv[1]);
            exit(0);
        }
        wait(0);
    }
    exit(0);
}

在Makefile 中UPROGS 处添加$U/_xargs\

实验结果

文章作者: leven
文章链接: https://leven-comeon.github.io/2024/05/06/6.s081/utils/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 leven !
operating system
赏
评论
  目录