MIT6.S081操作系统实验2021——lab1

参考文章

sleep

要求为xv6实现UNIX 程序sleep；其应该暂停用户指定的ticks number。tick是 xv6 内核定义的时间概念，即计时器芯片的两次中断之间的时间（两次时钟中断之间的时间）。您的解决方案应该在文件user/sleep.c中。

• 如果用户忘记传递参数，sleep 应该打印一条错误消息。
• 确保main调用exit()以退出程序。
• 在 Makefile 中将你的sleep程序添加到UPROGS；完成后，make qemu将编译您的程序，您将能够从 xv6 shell 运行它。

Run the program from the xv6 shell:

 $ make qemu...init: starting sh$ sleep 10(nothing happens for a little while)$

提示

• 查看 user/ 中的一些其他程序（ 例如user/echo.c、user/grep.c和user/rm.c），了解如何获取传递给程序的命令行参数。（argc是包括程序名本身的参数个数，argv是包括程序名本身在内的所有参数的字符串指针数组）
• 命令行参数作为字符串传递；您可以使用atoi将其转换为int（请参阅 user/ulib.c）。
• 使用系统调用sleep。

思路
实现首先检查参数个数，然后把参数中给出的ticks number转变为int，之后使用sleep系统调用，输出提示信息即可。

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"int main(int argc,char *argv[])
{if(argc == 1) {printf("sleep need one argument\\n");exit(1);}uint ticks = atoi(argv[1]);sleep(ticks);printf("(nothing happens for a little while)");exit(0);
}

pingpong

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

Run the program from the xv6 shell and it should produce the following output:

$ make qemu...init: starting sh$ pingpong4: received ping3: received pong$

提示

• 使用pipe创建管道。
• 使用fork创建一个子进程。
• 使用read从管道读取，并使用write写入管道。
• 使用getpid查找调用进程的进程 ID。
• 将程序添加到Makefile 中的UPROGS。
• xv6 上的用户程序有一组有限的库函数可供他们使用。您可以在 user/user.h中看到声明；定义（系统调用除外）位于user/ulib.c user/printf.c和user/umalloc.c中。

思路

• 父进程关闭管道1读端，向写端写入ping，关闭管道1写端。关闭管道2写端，从管道2读端读出pong，关闭管道2读端。使用wait让子进程先打印ping,然后打印pong.
• 子进程关闭管道1写端，从管道1读端读出ping，关闭管道1读端。关闭管道2读端，向写端写入pong，关闭管道2写端，然后打印ping。

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"#define READ 0
#define WRITE 1int main(int argc, char *argv[])
{if(argc != 1) printf("dont input arguments\\n");int pipeParToChr[2];int pipeChrToPar[2];char buf[8];pipe(pipeParToChr);pipe(pipeChrToPar);int pid = fork();if( pid == 0 ) // 子进程{close(pipeParToChr[WRITE]);read(pipeParToChr[READ] , buf , sizeof(buf));close(pipeParToChr[READ]);close(pipeChrToPar[READ]);write(pipeChrToPar[WRITE],"pong\\n",5);close(pipeChrToPar[WRITE]);printf("%d: received %s",getpid(),buf);exit(0);}else  // 父进程{close(pipeParToChr[READ]);write(pipeParToChr[WRITE] , "ping\\n" , 5);close(pipeParToChr[WRITE]);close(pipeChrToPar[WRITE]);read(pipeChrToPar[READ],buf,sizeof(buf));close(pipeChrToPar[READ]);wait((int*)0);printf("%d: received %s",getpid(),buf);exit(0);}
}

primes

要求
使用管道编写一个并发版本的初筛。这个想法归功于 Unix 管道的发明者 Doug McIlroy。本页中间的图片和周围的文字说明了如何做到这一点。您的解决方案应该在文件user/primes.c 中。您的目标是使用pipe和fork来设置管道。第一个过程将数字 2 到 35 输入管道。对于每个素数，您将安排创建一个进程，该进程通过管道从其左邻居读取并通过另一管道向其右邻居写入。由于 xv6 的文件描述符和进程数量有限，第一个进程可以在 35 处停止。

Your solution is correct if it implements a pipe-based sieve and produces the following output:

$ make qemu...init: starting sh$ primesprime 2prime 3prime 5prime 7prime 11prime 13prime 17prime 19prime 23prime 29prime 31$

提示

• 尽早关闭进程不需要的文件描述符，否则你的程序将在第一个进程达到 35 之前耗尽 xv6 的资源。
• 一旦第一个进程达到 35，它应该等到整个程序终止，包括所有子孙进程。因此，主进程（产生2~35数字的进程）应该只在所有输出都被打印出来，并且在所有其他子孙进程都退出之后才退出。
• 提示：当管道的写端关闭时，读取该管道的read()立即返回零。
• 将 32 位（4 字节）的int直接写入管道是最简单的，而不是使用格式化的 ASCII I/O。
• 您应该仅在需要时在管道流水线中创建进程。
• 将程序添加到Makefile 中的UPROGS。

实现
并发的素数筛模型：根据该图，我们可以看出需要一个主进程将2~35的int数据输入到第一个子进程。而从子进程的视角看，所有子进程的任务都是从父进程那里读取数据。将读到的第一个数据print出来，并以此为基，将所有读到的不是它的倍数的数据传递给自己的子进程。此外，流水线停止的条件是一个子进程从父进程那里读不到数据，说明所有数据已经筛选完毕。
思路

• 父进程输出一个数组和数组的个数
• 子进程接收数组，接收数组的第一个为最小素数，为基数。输出
• 之后数据分别判断是否为基数的整数倍，如果是抛弃，不是则给下一级子进程
• 最后实现递归，当输入数组的元素个数为1时，输出，结束进程

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"#define READ 0
#define WRITE 1void function(int num[] , int size)
{int pipe1[2];pipe(pipe1);int pid = fork();if(pid > 0){close(pipe1[READ]);for(int i=0; i<size; i++){write(pipe1[WRITE],&num[i],sizeof(num[i]));}close(pipe1[WRITE]);wait((int*)0);}else{close(pipe1[WRITE]);int numchr[34] , indnx = 0;int tmp , min;while(read(pipe1[READ] ,&tmp,sizeof(tmp) )){   if(indnx == 0) {min = tmp;printf("prime %d\\n", min);indnx++;}if(tmp%min != 0) {numchr[indnx-1] = tmp;indnx++;}}close(pipe1[READ]);function(numchr,indnx-1);exit(0);}
}int main(int argc, char *argv[])
{int num[34];int indnx = 0;for(int i = 2; i <= 35 ;i++){num[indnx] = i;indnx++;}function(num,34);exit(0);
}

find

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

Your solution is correct if produces the following output (when the file system contains the files b and a/b):

$ make qemu
...
init: starting sh
$ echo > b
$ mkdir a
$ echo > a/b
$ find . b
./b
./a/b
$ 

即find的功能是在argv[1]所给目录和它的所有子目录(不包括.和…)中查找名为argv[2]的文件。

提示

• 查看 user/ls.c 以了解如何读取操纵目录。
• 使用递归允许 find 进入到子目录。
• 不要递归到 . 和 …
• 对文件系统的更改在 qemu 运行中持续存在；运行干净的文件系统make clean，然后make qemu.
• 用 strcmp()比较字符串。
• 将程序添加到Makefile 中的UPROGS。

为了支持递归，我们需要实现一个在给定目录中查找给定文件的find()函数：

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

提示告诉我们研究ls.c来了解对目录和文件的读取，其中主要是函数void ls(char *path)：

首先以读的方式打开path这个file（unix中一切皆file，包括普通文件、目录、设备），返回一个fd.接着使用fstat()把这个file的一些文件系统相关的信息填充进st结构体中。

对于要实现的函数void find(char *path,char *name)，path必为目录，则直接仿照ls中case T_DIR的情况处理就行。和ls不同的是，我们不需要输出所有文件的所有信息，即在stat(buf, &st)之后，我们不需要printf出文件的信息，而是进行筛选，当这个file类型是文件并且名字与要找的name相同，则输出buf中存储的相对路径即可。如果这个file类型是目录并且不是.和…，就进入此目录递归查找。

#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: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(".", de.name) != 0 && strcmp("..", de.name) != 0){find(buf, target);}}break;}close(fd);}int main(int argc, char *argv[])
{if(argc != 3){printf("input arguments : find <path> <file name>\\n");exit(1);}find(argv[1], argv[2]);exit(0);
}

xargs

要求编写一个简单版本的 UNIX xargs 程序：从标准输入读取行。为每一行将该行作为参数提供给命令，并运行命令。您的解决方案应该在文件user/xargs.c中。
以下示例说明了 xargs 的行为：

$ echo hello too | xargs echo bye
bye hello too
$

注意这里的命令是“echo bye”，附加参数是“hello too”，使得命令“echo bye hello too”输出“bye hello too”。

提示

• 使用fork和exec对每一行输入调用命令。在父进程中使用wait等待子进程完成命令。
• 要读取单行输入，请一次读取一个字符，直到出现换行符 (‘\\n’)。
• kernel/param.h 声明了 MAXARG，如果您需要声明 argv 数组，这可能很有用。
• 将程序添加到Makefile 中的UPROGS。

实现

• 我们已经知道，shell中可以使用管道 | 将’|‘之前的命令的标准输出作为之后的命令的标准输入。而xargs的作用是将’| xargs’之前的命令的标准输出作为之后的命令的附加的命令行参数。标准输入和命令行参数，有很大的不同。
• 以$ echo hello too | xargs echo bye为例，其argc为3。即实际的命令行参数从xargs开始算起。
• 程序的功能应是维护一个新的new_argv数组，先从argv[1]开始把本来的参数复制到new_argv中，然后从stdin（文件描述符0）读取字节，每读取到’\\0’就把这个新参数添加到new_argv末尾，读取到’\\n’就fork出一个子进程以new_argv为基础使用exec来执行命令。然后从本来的参数末尾重新开始添加参数。

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/param.h"int main(int argc, char *argv[]) 
{char *new_argv[MAXARG];int cur_argv = 1;for( cur_argv = 1 ;cur_argv <= argc - 1 ; cur_argv++){new_argv[cur_argv - 1] = argv[cur_argv];}char ch;char buf[128];char *cur_buf = buf;new_argv[cur_argv-1] = buf;while(read(0,&ch,sizeof(char))){if( ch == ' '){*cur_buf = '\\0';cur_buf++;new_argv[cur_argv ] = cur_buf;cur_argv++;}else if( ch == '\\n' ){*cur_buf = '\\0';new_argv[cur_argv] = 0;int pid = fork();if( pid == 0){exec(new_argv[0] , new_argv);exit(0);}else{wait((int*)0);cur_buf = buf;cur_argv = argc;}}else{*cur_buf = ch;cur_buf++;}}exit(0);
}

makefile