6.S081 Lab(1) Utilities
2023-08-09 14:53:19 # MIT # 6.S081

课程主页https://pdos.csail.mit.edu/6.828/2021/schedule.html

Lab0 Tools

虚拟机使用VMware Workstation 16 Player,系统采用ubuntu20.04

安装必要工具

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

测试安装

  • 你应当可以编译并运行xv6(按住Ctrl+a x退出)

    # in the xv6 directory
    $ make qemu
    # ... lots of output ...
    init: starting sh
    $

Lab1 Xv6 and Unix utilities

1.1 Boot xv6 (easy)

clone仓库并切换到util分支

$ git clone git://g.csail.mit.edu/xv6-labs-2021
$ cd xv6-labs-2021
$ git checkout util

提交代码, -a 表示不需要git add 直接提交

# -a 表示不需要git add 直接提交
$ git commit -am 'my solution for util lab exercise 1'

查看代码变动

# 展示和上次提交代码不同的地方
$ git diff
# 展示和初始时不同的地方
$ git diff origin/util

启动qemu

$ make qemu

查看可执行程序

$ 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

xv6没有ps命令,但按Ctrl-p,内核会打印每个进程的信息。如果现在尝试,会看到两行

1 sleep  init
2 sleep sh

退出可按住Ctrl-a,再输入x

通过make grade获取成绩,make handin提交lab

1.2 sleep (easy)

user中创建sleep.c

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

int main(int argc, char *argv[]) {
if(argc < 2) {
fprintf(2, "Please enter a number!\n");
exit(1);
}
sleep(atoi(argv[1]));
exit(0);
}

添加到Makefile中

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/_sleep\

测试

$ ./grade-lab-util sleep
make: “kernel/kernel”已是最新。
== Test sleep, no arguments == sleep, no arguments: OK (2.1s)
== Test sleep, returns == sleep, returns: OK (0.6s)
== Test sleep, makes syscall == sleep, makes syscall: OK (0.9s)

1.3 pingpong (easy)

添加到Makefile

user中添加pingpong.c

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

#define READEND 0
#define WRITEEND 1

int main(int argc, char *argv[]) {
int p1[2];
int p2[2];
int pid;
char buf[1];

pipe(p1);
pipe(p2);

pid = fork();

if(pid < 0) {
exit(1);
} else if (pid == 0) {
close(p1[WRITEEND]);
close(p2[READEND]);
read(p1[READEND], buf, 1);
printf("%d: received ping\n", getpid());
write(p2[WRITEEND], buf, 1);
close(p1[READEND]);
close(p2[WRITEEND]);
exit(0);
} else {
close(p1[READEND]);
close(p2[WRITEEND]);
write(p1[WRITEEND], " ", 1);
read(p2[READEND], buf, 1);
printf("%d: received pong\n", getpid());
close(p1[WRITEEND]);
close(p2[READEND]);
exit(0);
}
}

使用两个管道进行双向的数据传输,子进程要先等待父进程写才能读,之后父进程要等子进程写才能读

1.4 primes (moderate)/(hard)

素数筛法:将一组数feed到一个进程里,先print出最小的一个数,这是一个素数,然后用其他剩下的数依次尝试整除这个素数,如果可以整除,则将其drop,不能整除则将其feed到下一个进程中,直到最后打印出所有的素数。

image-20220815203942525

解决思路:采用递归,每次先尝试从左pipe中读取一个数,如果读不到说明已经到达终点,exit,否则再创建一个右pipe并fork一个子进程,将筛选后的数feed进这个右pipe。

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

#define READEND 0
#define WRITEEND 1

void child(int *p);

int main(int argc, char *argv[]) {
int p[2];
pipe(p);

if(fork() == 0) {
child(p);
} else {
close(p[READEND]);
for (int i = 2; i <= 35; i++) {
write(p[WRITEEND], &i, sizeof(int));
}
close(p[WRITEEND]);
wait(0);
}

exit(0);
}

void child(int* p) {
int pr[2];
int n;

close(p[WRITEEND]);
if(read(p[READEND], &n, sizeof(int)) == 0) {
exit(0);
}

pipe(pr);

if(fork() == 0) {
child(pr);
} else {
close(pr[READEND]);
printf("prime %d\n", n);
int prime = n;
while(read(p[READEND], &n, sizeof(int))) {
if(n % prime != 0) {
write(pr[WRITEEND], &n, sizeof(int));
}
}
close(pr[WRITEEND]);
wait(0);
}

exit(0);
}

1.5 find (moderate)

模仿 ls.c 即可

#include "kernel/types.h"
#include "user/user.h"
#include "kernel/fs.h"
#include "kernel/stat.h"
#include "kernel/fcntl.h"

void find(char *path, char* file);

int main(int argc, char *argv[]) {
if(argc != 3) {
fprintf(2, "find: You need pass in only 2 argument");
exit(1);
}

char *target_path = argv[1];
char *target_file = argv[2];
find(target_path, target_file);
exit(0);
}

void find(char *path, char* file) {
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(path + strlen(path) - strlen(file), file) == 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)) {
find(buf, file);
}
}
break;
}
close(fd);
}

1.6 xargs (mederate)

实现将标准输入作为参数一起输入到xargs后面跟的命令中,比如

$ echo hello too | xargs echo bye
bye hello too

如果标准输入有多行,那么也要执行多次命令

使用fork起一个子进程,在子进程中用exec执行相应的命令。父进程wait。对标准输入每次读一个char,若读到\n需要执行命令。

#include "kernel/types.h"
#include "user/user.h"
#include "kernel/param.h"
#define MAX_LEN 100

int main(int argc, char *argv[]) {
char *command = argv[1];
char bf;
char paramv[MAXARG][MAX_LEN]; // arguments
char *m[MAXARG];

while (1) {
int count = argc - 1; // # of current arguments
memset(paramv, 0, MAXARG * MAX_LEN);
// copy the parameter of command
for (int i = 1; i < argc; i++) {
strcpy(paramv[i - 1], argv[i]);
}

int cursor = 0; // cursor pointing the char position in single_arg
int flag = 0; // flag indicating whether thers is argument preceding space
int read_result;

while (((read_result = read(0, &bf, 1))) > 0 && bf != '\n') {
if (bf == ' ' && flag == 1) {
count++;
// reset flag and p
cursor = 0;
flag = 0;
}
else if (bf != ' ') {
paramv[count][cursor++] = bf;
flag = 1;
}
}

if (read_result <= 0) {
// encounters EOF of input
break;
}
for (int i = 0; i < MAXARG - 1; i++) {
m[i] = paramv[i];
}
m[MAXARG - 1] = 0; // 参数最后0结尾
if (fork() == 0) {
exec(command, m);
exit(0);
} else {
wait((int *) 0);
}
}
exit(0);
}

到这里lab1就全部完成了!

image-20221020170416506