【MIT-OS6.S081作业1.3】Lab1-utilities primes

news/2024/12/12 19:28:38/

本文记录MIT-OS6.S081 Lab1 utilities 的primes函数的实现过程

文章目录

  • 1. 作业要求
    • primes (moderate)/(hard)
  • 2. 实现过程
    • 2.1 代码实现

1. 作业要求

primes (moderate)/(hard)

Write a concurrent version of prime sieve using pipes. This idea is due to Doug McIlroy, inventor of Unix pipes. The picture halfway down this page and the surrounding text explain how to do it. Your solution should be in the file user/primes.c.

Your goal is to use pipe and fork to set up the pipeline. The first process feeds the numbers 2 through 35 into the pipeline. For each prime number, you will arrange to create one process that reads from its left neighbor over a pipe and writes to its right neighbor over another pipe. Since xv6 has limited number of file descriptors and processes, the first process can stop at 35.

Some hints:

Be careful to close file descriptors that a process doesn’t need, because otherwise your program will run xv6 out of resources before the first process reaches 35.
Once the first process reaches 35, it should wait until the entire pipeline terminates, including all children, grandchildren, &c. Thus the main primes process should only exit after all the output has been printed, and after all the other primes processes have exited.
Hint:

  • read returns zero when the write-side of a pipe is closed.
  • It’s simplest to directly write 32-bit (4-byte) ints to the pipes, rather than using formatted ASCII I/O.
  • You should create the processes in the pipeline only as they are needed.
  • Add the program to UPROGS in Makefile.
  • Your solution is correct if it implements a pipe-based sieve and produces the following output:

$ make qemu

init: starting sh
$ primes
prime 2
prime 3
prime 5
prime 7
prime 11
prime 13
prime 17
prime 19
prime 23
prime 29
prime 31
$

2. 实现过程

2.1 代码实现

作业提供了算法的链接:
Bell Labs and CSP Threads
在这里插入图片描述

在这里插入图片描述

先读取左边传来的所有数字,打印出第一个数字p,然后继续循环read左边给到的数字n,如果p不能被n整除,那么就把n继续发送给右边。

为了实现这个功能,我们这里需要使用fork和管道,fork有两个进程:主进程和子进程,我们分析一下它们分别是怎么做的:

  • 第1个fork创建主进程 p 1 p_1 p1和子进程 n p 1 np_1 np1,从前面的ping-pong实验我们知道,主进程和子进程可以一个实现读,一个实现写,这是通过管道来实现的,于是我们创建一个管道 f d 1 fd_1 fd1(分别有 f d 1 [ 0 ] 和 f d 1 [ 1 ] fd_1[0]和fd_1[1] fd1[0]fd1[1])。
  • 主进程 p 1 p_1 p1将2~35写到第1个管道的写描述符 f d 1 [ 1 ] fd_1[1] fd1[1]
  • 子进程 n p 1 np_1 np1从第1个管道的读描述符 f d 1 [ 0 ] fd_1[0] fd1[0]中read第一个数字打印:2,为了将主进程发来的剩余数字继续发送到右边,必然不是写到 f d 1 [ 1 ] fd_1[1] fd1[1],这样和上面图片的数据方向就不一样了。我们需要在子进程创建新的管道 f d 2 fd_2 fd2,同时后面的逻辑还是类似的为主进程和子进程读写,我们依旧使用fork来创建得到主进程 p 2 p_2 p2和子进程 n p 2 np_2 np2(这里的 n p 1 np_1 np1 p 2 p_2 p2是一样的),于是我们可以把主进程 p 1 p_1 p1发来的剩余数字在子进程的主进程 p 2 p_2 p2里写到第2个管道的写描述符 f d 2 [ 1 ] fd_2[1] fd2[1],在子进程 n p 2 np_2 np2来处理同样的读写,后面继续进行这样的读写操作…
  • 我们可以使用递归【这样也就实现了提示说的You should create the processes in the pipeline only as they are needed.】。
  • 递归停止条件:子进程从管道的读描述符读取第一个数字时返回0【read returns zero when the write-side of a pipe is closed.】,那么递归终止,递归过程在递归函数里建立新的管道,但是读取数字需要知道前一个管道,所以递归传参是前一个管道描述符的指针(指针传参)。

注意事项:

  • write可以直接写入int类型的数字【It’s simplest to directly write 32-bit (4-byte) ints to the pipes, rather than using formatted ASCII I/O.】,传入int类型的指针即可。
  • 主要关闭不需要的管道描述符号。
#include "kernel/types.h"
#include "user/user.h"void processPrime(int* p)
{close(p[1]);int num;if (0 == read(p[0], &num, sizeof(num))){close(p[0]);exit(0);}printf("prime %d\n", num);// create new pipeint nPipe[2];pipe(nPipe);int ret = fork();if (ret == 0){processPrime(nPipe);}else{close(nPipe[0]);int nNum;while (read(p[0], &nNum, sizeof(nNum))){if (nNum % num != 0)write(nPipe[1], &nNum, sizeof(nNum));}close(p[0]);close(nPipe[1]);wait(0);}exit(0);
}
int main(int argc, char* argv[])
{int p[2];pipe(p);int ret = fork();if (ret == 0){processPrime(p);}    else{close(p[0]);for (int i = 2; i <= 35; ++i)write(p[1], &i, sizeof(i));close(p[1]);wait(0);}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\ $U/_pingpong\ $U/_primes\ 

重新编译通过,测试primes,如题所述正确打印:

在这里插入图片描述

确实过了一会然后可以继续输入命令,然后我们再使用作业所说的测试命令:

./grade-lab-util primes

在这里插入图片描述

完活!

递归来写还是比较清晰的。


http://www.ppmy.cn/news/1554576.html

相关文章

蓝桥杯我来了

最近蓝桥杯报名快要截止了&#xff0c;我们学校开始收费了&#xff0c;我们学校没有校赛&#xff0c;一旦报名缴费就是省赛&#xff0c;虽然一早就在官网上报名了&#xff0c;但是一直在纠结&#xff0c;和家人沟通&#xff0c;和朋友交流&#xff0c;其实只是想寻求外界的支持…

分布式 CAP理论 总结

前言 相关系列 《分布式 & 目录》《分布式 & CAP理论 & 总结》《分布式 & CAP理论 & 问题》 分布式 分布式的核心是将大型业务拆解成多个子业务以使之在不同的机器上执行。分布式是用于解决单个物理机容量&性能瓶颈问题而采用的优化手段&#xf…

革新医疗器械生产:MR30分布式IO模块引领智能制造新纪元

在当今快速发展的医疗科技领域&#xff0c;高效、精准与安全性是衡量医疗器械生产线的金标准。随着工业4.0时代的到来&#xff0c;分布式IO&#xff08;Input/Output&#xff0c;输入/输出&#xff09;模块以其灵活、高效、可靠的特点&#xff0c;正逐步成为医疗器械生产线智能…

vue element 切换 select 下拉框的 单选多选报错

今天根据项目需求&#xff0c;需要对下拉框进行&#xff0c;单双选判断&#xff0c;当多选切换成多选&#xff0c;没有问题但是单选切换成多选报错如下 页面是要求 选择in或者notin时候 多选 经过好长时间摸索&#xff0c;解决了&#xff0c;最后使用select的失去焦点事件解决…

深入理解Java虚拟机(JVM)

深入理解Java虚拟机&#xff08;JVM&#xff09;&#xff1a;架构、内存模型与性能调优 Java虚拟机&#xff08;JVM&#xff09;是Java程序的运行时环境&#xff0c;作为Java技术的核心之一&#xff0c;它提供了一个抽象的计算平台&#xff0c;使Java程序能够在不同的硬件和操作…

华为HarmonyOS NEXT 原生应用开发: 数据持久化存储(用户首选项)的使用 token令牌存储鉴权!

Preferences 数据持久化存储 用户首选项&#xff08;Preferences&#xff09; 1. 封装 仓库工具类 ● 这里可以选择将 数据字段 key 抽取为一个静态方法&#xff0c;这里选择让用户传参&#xff0c;看起来较容易理解&#xff01; /*** 首选项 preferences - 实现数据持久化…

Leetcode:1812

1&#xff0c;题目 2&#xff0c;思路 先判断字母第一行颜色&#xff1a;白为ture&#xff0c;黑为false在判断根据字母规则判断数字所在的位置颜色ascii码表中&#xff1a;a为奇数&#xff0c;1为奇数&#xff0c;b为偶数&#xff0c;2为偶数&#xff0c;所以可以利用奇偶性对…

孚盟云 MailAjax.ashx SQL漏洞复现

0x01 产品描述: ‌孚盟云‌是由