Lab: Xv6 and Unix utilities

实验链接

实验准备

实验环境:Ubuntu 22.04.2 LTS
工具链安装:

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

sleep

需求

为 xv6 实现 UNIX 程序 sleep; 您的 sleep 应该暂停用户指定个数的 tick。tick 是由 xv6 内核定义的时间概念，即来自计时器芯片的两次中断之间的时间。您的解决方案应该在 user/sleep.c 文件中。

solution

系统调用 sleep(int) 只接收一个整形参数，故要对通过命令行传入的参数个数进行判断，确认为一个后还要判断其是否能转化为整数。

#include "kernel/types.h"
#include "user/user.h" //该头文件对kernel/types.h头文件有类型依赖，故要放在kernel/types.h之后。
int main(int argc, char *argv[]){
    if(argc < 2)
        printf("no argument\n");
    else if(argc > 2)
    printf("Excessive argument\n");
    else{
        int tag = 1;
        char *p = argv[1];
        while(*p){
            if(*p < '0' || *p > '9'){
                tag=0;
                break;
            }
            p++;
        }
        if(tag)
            sleep(atoi(argv[1]));
        else 
            printf("Illegal argument\n");
    }
    exit(0);
}

pingpong

需求

编写一个程序，使用 UNIX 系统调用通过一对管道(每个方向一个管道)在两个进程之间 “ping-pong” 传递一个字节。父进程应该向子进程发送一个字节; 子进程应该打印<pid>: received ping，其中 <pid> 是它的进程号，将管道上的字节写入父进程，然后退出; 父进程应该从子进程读取字节，打印<pid>: received pong，然后退出。您的解决方案应该在user/pingpong.c.文件中。

solution

依题意可知考察的进程间通信与评测系统可检测到的输出结果无关联关系。
为了利用评测系统来检测进程间通信，可将子进程获取自身进程PID的方式从调用getpid()改为通过管道从父进程获取。

#include "kernel/types.h"
#include "user/user.h"
int main(){
    int p[2];
    pipe(p);
    int pid = fork();
    if(!pid){
        read(p[0],&pid,4);
        printf("%d: received ping\n",pid);
    }
    else{
        write(p[1],&pid,4);
        wait(0);
        printf("%d: received pong\n",getpid());
    }
    exit(0);
}

primes

需求

使用管道编写一个并发版本的 prime sieve(素数筛)。这个想法源于 Unix 管道的发明者 Doug McIlroy。这页中间的图片和周围的文字解释了如何做到这一点。您的解决方案应该在 user/prime.c 文件中。

solution

1. fork()出的子进程与父进程有相同的用户栈、相同的局部变量值、相同的堆、相同的全局变量值、相同的文件描述符、以及相同的代码。但他们是独立的进程，有各自私有地址空间。
2. fork()出的子进程从父进程调用fork()的位置开始往下执行。但子进程在该位置获取的fork返回值为0。
3. 父进程要用wait(0)回收终止的子进程，终止但未被回收的子进程称为僵死进程。

//递归(为了开不同的管道) + fork子进程
#include "kernel/types.h"
#include "user/user.h"
void get_prime(int p1[2]){
    close(p1[1]);
    int n;
    int tag = read(p1[0],&n,4);
    if(!tag){   //管道中无数据
        close(p1[0]);
        exit(0);
    }
    printf("prime %d\n",n);
    int p2[2];
    pipe(p2);   //开新管道
    int pid = fork();
    if(!pid) get_prime(p2);
    else if(pid > 0){
        int m;
        while(read(p1[0],&m,4)){    //筛掉n的倍数
            if(m % n){ 
                write(p2[1],&m,4);
            }
        }
        close(p1[0]);
        close(p2[1]);
        close(p2[0]);
        wait(0);    //回收子进程
    }
    else{
        printf("fork error\n");
        exit(pid);
    }
    exit(0);
}
int main(){
    int p[2];
    pipe(p);
    int i;
    for(i = 2; i <= 35; i++)
        write(p[1],&i,4);
    get_prime(p);
    exit(0);
}

下图可帮助理解上述代码

find

需求

编写一个简单版本的 UNIX 查找程序: 查找目录树中具有特定名称的所有文件。您的解决方案应该在user/find.文件中。

solution

参考user/ls.c可知如何遍历目录中所有文件，由于需要查找范围的是从以输入目录为根的目录树故需要递归处理子目录，需要注意在递归处理时避开”.”(本目录) 和 “..”(父目录)。

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
char* get_name(char* path){//获取当前文件名
    char * p;
    for(p = path+strlen(path); p >= path && *p != '/'; p--);
    p++;
    return p;
}
void find(char *path, char* str){//类Unix系统中，目录被视为一种特殊类型的文件
    char buf[512];//存储路径
    struct dirent de;//目录结构体
    struct stat st;//文件结构体
    int fd = open(path, 0);//0表示以标准模式(读写模式)打开
    if(fd < 0){//打开失败
        fprintf(2, "find: cannot open %s\n", path);
        return;
    }
    if(fstat(fd, &st) < 0){//通过文件描述符将对应的文件信息放入文件结构体stat中,若失败则返回-1
        fprintf(2, "find: cannot stat %s\n", path);
        close(fd);
        return;
    }
    switch(st.type){//判定打开类型
        case T_DEVICE://判定为设备文件
        case T_FILE://判定为普通文件
            if(!strcmp(str, get_name(path)))
                printf("%s\n",path);
            break;
        case T_DIR://判定为目录
            strcpy(buf, path);
            char *p = buf + strlen(buf);
            *p = '/';
            p++;
            while(read(fd, &de, sizeof de) == sizeof de){//使用read从目录文件中读取目录条目，处理目录中文件
                if(de.inum == 0)//该目录条目为空或未使用
                    continue;
                memmove(p, de.name, DIRSIZ);
                p[DIRSIZ] = 0;
                if(stat(buf, &st) < 0){//通过文件路径将对应的文件信息放入文件结构体stat中，若失败则返回-1
                printf("ls: cannot stat %s\n", buf);
                continue;
                }
                if(st.type == T_DEVICE || st.type == T_FILE){//判断为非目录文件
                    if(!strcmp(str, get_name(buf)))
                        printf("%s\n",buf);
                }
                else if(st.type == T_DIR && strcmp(".", get_name(buf)) && strcmp("..", get_name(buf)))//判定为子目录，递归处理，注意不要重复进入本目录以及父目录
                    find(buf, str);
            }
            break;
    }
    close(fd);
    return;
}
int main(int argc, char *argv[]){
    if(argc == 3)
    find(argv[1], argv[2]);
    else
        printf("argument error\n");
    exit(0);
}

xargs

需求

编写一个简单版本的 UNIX xargs 程序:它的参数描述要运行的命令，它从标准输入中读取行，并为每一行运行命令，将该行附加到命令的参数中。您的解决方案应该在 user/xargs.c 文件中。

solution

构造一个char*数组将需要传给exec的数据放入其中即可

#include "kernel/types.h"
#include "user/user.h"
#include "kernel/param.h"
int main(int argc, char *argv[]){
    char *p[MAXARG];
    int i;
    for(i=1; i < argc; i++)
        p[i-1] = argv[i];
    p[argc-1]  = malloc(512);
    p[argc] = 0;
    while(gets(p[argc-1],512)){ //gets函数一次读取一行
        if(p[argc-1][0] == 0)break; //已读完
        if(p[argc-1][strlen(p[argc-1])-1]=='\n') //该函数会将末尾换行保留，故需去掉换行符。
            p[argc-1][strlen(p[argc-1])-1] = 0;
        if(fork()==0)
            exec(argv[1],p);
        else
            wait(0);
    }
    exit(0);
}