# 华东师范大学数据科学与工程学院学生期末项目报告

# 一、 题目要求

• 作业一：为 xv6 实现 UNIX 程序 sleep ， sleep 应该暂停用户指定的滴答数。时钟周期是 xv6 内核定义的时间概念，即定时器芯片两次中断之间的时间。注意解决方案应该位于文件 user/sleep.c 中。
• 作业二：在 xv6 上实现 pingpong 程序，即两个进程在管道两侧来回通信。父进程将”ping” 写入管道，子进程从管道将其读出并打印：received ping ，其中是子进程的进程 ID。子进程从父进程收到字符串后，将”pong“写入另一个管道，然后由父进程从该管道读取并打印：received pong，其中是父进程的进程 ID。请将代码写在 user/pingpong.c 文件中。
• 作业三：使用 pipe 编写素数筛的并发版本。这个想法源自 Unix pipe 的发明者 Doug McIlroy。解决方案应该位于文件 user/primes.c 中。

# 二、 功能实现情况

# 作业一

# 1. 引入头文件

参考自 user/echo.c

# 2. 编写 main 函数框架

• 模仿 user/echo.c 中 main 函数结构
  • argc 表示参数个数、argv 表示参数列表
  • 对于 sleep 程序，只需要输入 sleep time 即可，故 argc != 2 时提示正确用法并且退出

# 3. 编写 main 函数主体

• argv 内的元素是字符串， argv[0] = "sleep" argv[1] = "{number}"
  • 将 string 转为 int，需要使用 atoi函数 ，把字符串转换成整型数。
  • 随后调用系统调用 sleep(time)
  • 最后 exit(0) 正常退出即可

# 4. 放入 user 文件夹并编写 makefile 文件

# 作业二

# 1. 引入头文件

参考自 user/echo.c

# 2. 编写 main 函数框架

• 题目要求输入 pingpong 即可返回对于操作
  • 因此当 argc != 1 时将提示用法并异常退出

# 3. 编写 main 函数主体

• 创建管道

• 创建 buf 数组用于管道读写

• 创建子进程并实现 pingpong 程序要求

# 创建管道

• 使用两根管道，一个用于父进程向子进程通信 ptcfd ，另一个用于子进程向父进程通信 ctpfd

# 创建 buf 数组

# 创建子进程并实现 pingpong 程序要求

执行过程

• 子进程调用 read 函数读取 ptcfd 管道读端，子进程会被阻塞直到父进程在执行 write 函数在 ptcfd 管道写端写入信息
• 父进程写入信息后，被 wait 函数阻塞，直到子进程完毕
• 父进程执行剩余的部分

# 作业三

# 1. 引入头文件

# 2. 编写 main 函数框架

题目要求输入 primes {num} 即可返回对于操作

• 因此当 argc != 2 时将提示用法并异常退出

# 3. 编写 main 函数主体

• 创建管道
• 创建子进程
• 映射管道
• 写入管道
• 调用 primes 函数

# 创建管道

# 创建子进程

• 由题干

# 映射管道

• 自定义一个 mapping 函数，调用 dup 函数，将管道端口复制到最小的尚未被使用过的文件描述符

  • 因为在程序刚开始运行时，默认文件描述符 1 2 3 都已经打开，故 close(0) 则 0 未被使用， close(1) 则 1 未被使用

  • 调用 mapping(0,pd) 则 pd [0] 映射到文件描述符 0 上
    调用 mapping(1,pd) 则 pd [1] 映射到文件描述符 1 上

• 作用：向被调用的函数传递管道端口

# 写入管道

• 在写入前映射管道写入端给文件描述符 1
• 子进程将 2 到 endNum 的数字写入到管道 fd 内

# 调用 primes 函数

• 父进程等待子进程写入完毕后，将管道读端映射到文件描述符 0
• 调用 primes 函数

# 4. 编写 prime 函数

• 每次调用 primes 函数，管道内第一个数字永远是质数，直接打印
• 随后创建新管道和子进程
• 子进程将原来管道内数字读取，如果不能被管道第一个数字整除，则写入到 primes 函数新创建的管道
• 父进程等待子进程写入完毕后，映射 primes 函数新创建管道的读取端，随后递归调用自己

# 作业四

# 1. 引入头文件与相关结构体

# stat.h

# fs.h

# 2. 编写 main 函数

• 如果参数不是三个，则 exit(1) 异常退出
• 随后调用 find 函数

# 3. 编写 find 函数

# 引入结构体

• 参考 /user/ls.c ，引入结构体 dirent 和 stat
• 结构体定义在 stat.h 和 fs.h 中

# open 函数打开路径

• 通过 open 函数打开对应路径的文件并赋给文件描述符 fd

# fstat 获取文件状态

• 由文件描述符 fd 取得文件的状态，并赋给对应文件结构体 st

# 按不同文件类型处理

# 文件

• 如果是文件，则通过路径获取文件名字，比较是否和目标文件名字相同

• 获取文件名
  • 通过查找最后一个斜杠后的第一个字符，返回对应字符串指针

# 文件夹

• de.inum=0 表示这是一块已经初始化并且可以用来创建文件或者文件夹的位置，因此如果为 0 则跳过

• 读取目录并且将其放入到 buf 中，用一个活动的指针 p 去对 buf 中的内容进行拼接和修饰操作
• 循环体 while，判断条件为是否成功从句柄 fd 中读取 dirent 结构（目录层）
  • 忽略 de.inum==0 的项，以及文件夹的名字为 . 或 .. 的项
  • de.name 的内容移动到 p 指向的指针中，获得 fd 指向的目录下的一个文件完整路径
  • 设置文件名结束符
  • stat 访问完整路径，存入 st
  • 递归调用 find 函数，查找 path 对应文件夹的下一级所有文件

![image-20240314151012443](https://aquaoh.oss-cn-shanghai.aliyuncs.com/post/image-20240314151012443.png

# 作业五

# 1. 引入头文件

# param.h

# 2. 编写 main 函数

# 将 argv 命令参数传递到 params 数组

• 传递参数后，在 params 数组末尾开辟一块足够大空间，给后续填入新字符串做准备

# 读取新写入的命令参数

• 根据提示，文件描述符 0 为管道读端
• 通过循环，一个一个字符读取

# 处理字符

# 换行 \n

• 如果为换行，代表命令输入完毕，则可以执行

• exec 函数执行对应命令

• 执行完后将 params 数组新开辟的空间释放，并让计数变量初始化

# 空格

• 如果为空格，则 params 二维数组第一位下标 + 1，同时开辟新的内存空间（如果参数不多于最大参数数量）

# 默认

• 既非空格，又非换行，则正常写入 params 二维数组，同时第二位下标 + 1

![image-20240317222751358](https://aquaoh.oss-cn-shanghai.aliyuncs.com/post/image-20240317222751358.png

# 三、 性能测试情况

# 作业一

• 使用 make qemu 重新编译并进入虚拟机

• 进入 xv6 系统输入 sleep 1000 后，光标停止，终端不再有 prompt，证明 sleep 程序实现成功

# 作业二

• 使用 make qemu 重新编译并进入虚拟机

• 进入 xv6 系统输入 pingpong 后，正确输出题目要求内容

# 作业三

• 使用 make qemu 重新编译并进入虚拟机
• 进入 xv6 系统输入 primes 100 后，正确输出了全部素数

# 作业四

• 使用 make qemu 重新编译并进入虚拟机
• 使用 mkdir a ， mkdir c 分别创建 a , c 两个文件夹
• 使用 echo test > ./a/b , echo test > b , echo test > ./c/b 保存 test 至指定路径的文件 b 中
• 使用 find . b 查找当前目录下所有 b 文件，正确输出全部 b 的路径

# 作业五

• 使用 make qemu 重新编译并进入虚拟机
• 输入 sh < xragstest.sh 执行测试脚本，正确执行对应命令

# 四、总结

实现几个 unix 实用工具，熟悉 xv6 的开发环境以及系统调用。

# 作业一

• sleep(int time)
  • 为系统调用，time 单位为 ms

# 作业二

• fork()

  • 创建子进程，子进程内 fork 返回 0，父进程内返回子进程 pid

• wait()

  • 父进程内，阻塞当前进程直到子进程执行完毕

• pipe()

  • 创建管道，默认 fd [1] 为写入端，fd [0] 为读取端

使用 fork () 复制本进程创建子进程，创建两个管道，分别用于父子之间两个方向的数据传输

# 作业三

• dup()
  • 将管道端口复制到最小的尚未被使用过的文件描述符
  • 一般为先 close (n) 释放文件描述符后再调用 dup 函数
• 如果管道在子进程未写入数据，而父进程读取数据，则父进程会被阻塞直到子进程写入完毕

使用多进程和管道，每一个进程作为一个 stage，筛掉某个素数的所有倍数（筛法）

每一个 stage 以当前数集中最小的数字作为素数输出（每个 stage 中数集中最小的数一定是一个素数，因为它没有被任何比它小的数筛掉），并筛掉输入中该素数的所有倍数（必然不是素数），然后将剩下的数传递给下一 stage。最后会形成一条子进程链，而由于每一个进程都调用了 wait(0); 等待其子进程，所以会在最末端也就是最后一个 stage 完成的时候，沿着链条向上依次退出各个进程。

# 作业四

• open(path,0)
  • 一切皆文件
  • 返回文件描述符

参考 ls.c

# 作业五

• exec(params[0],params)
  • 执行 params 参数数组对应命令

编写 xargs 工具，从标准输入读入数据，将每一行当作参数，加入到传给 xargs 的程序名和参数后面作为额外参数，然后执行