MIT6.s081 2021 Lab Utilities

Boot xv6

按照示例切换到 util 分支后，看到目录下包含 Makefile 文件，执行 make qemu 即可。

sleep

思路

借助系统调用 sleep 实现一个命令行程序，关键是要找到封装了系统调用的 C 函数的位置，根据提示：

… user/user.h for the C definition of sleep callable from a user program …

可知该函数的声明位于 user.h 头文件中，声明方式很简单：

int sleep(int);

将其“拷贝”（include）到需要编写的代码 user/sleep.c 中，调用 sleep(<睡眠时间>) 即可。

最后，按照提示，将编写的 sleep 代码添加到 Makefile 的 UPROGS 中，添加后如下所示：

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\  # here

代码

// user/sleep.c

#include "kernel/types.h" // 注意先包含types.h
#include "user/user.h"    // 再包含user.h（user.h中存在在types.h中定义的别名）


int main(int argc, char* argv[]) {
    if (argc != 2) {
        fprintf(2, "sleep: argument count error\n");
        exit(1);
    }

    int time = atoi(argv[1]);
    sleep(time);

    exit(0);
}

pingpong

思路

本题主要是要理解管道的接口设计，以及借助该接口实现父进程与子进程之间的通信。这是 xv6 文档中对于 pipe 调用的描述：

int pipe(int p[]) // Create a pipe, put read/write file descriptors in p[0] and p[1].

pipe 创建一个管道，并分别将该管道的读、写端文件描述符置为 p[0] 和 p[1]，之后调用 fork 创建一个子进程，由于 fork 的作用是将父进程的数据直接拷贝给子进程，因此子进程同时继承了父进程的管道文件描述符，可以借助该文件描述符进行进程间通信（IPC），相当于借助一个共享文件进行通信，只不过该“文件”存储在内存的内核区域中，而不占用实际的磁盘存储空间。

利用管道解决本题的基本流程如下，首先需要创建两个管道 pa 和 pb，然后：

  1. 父进程向管道 pa 的写端写入 1 字节数据，然后关闭 pa 的写端。
  2. 子进程从管道 pa 的读端读取 1 字节数据，然后关闭 pa 的读端，打印信息，然后向管道 pb 的写端写入 1 字节数据，关闭 pb 的写端。
  3. 父进程从管道 pb 的读端读取 1 字节数据，关闭 pb 的读端，最后打印信息。

这里需要解释一下为什么需要两个管道，由于进程调度策略的影响，父进程和子进程的执行顺序并不确定。可能出现这样一种情况：在 fork 创建子进程后，父进程先被调度，将 1 字节数据写入管道，这时理想的情况是子进程被调度，然后读取父进程发送的数据，但是事实可能并不会如我们所愿，子进程可能一直得不到调度，父进程继续向下执行，从管道中读取自己刚刚发送的 1 字节的数据，这样子进程就无法收到父进程发送的数据，父子进程之间的通信也就失败了。

通过创建两个管道，并分别关闭对应的读端和写端，就能够得到两个单向数据流的管道，也就不会有上述自己写入的数据被被自己读取的情况出现。

代码

// user/pingpong.c

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


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

	int pa[2], pb[2];
	pipe(pa);
	pipe(pb);

	int pid = fork();
	if (pid == 0) {
		close(pa[1]);
		close(pb[0]);

		// phase_2
		read(pa[0], buf, 1);
		close(pa[0]);
		printf("%d: received ping\n", getpid());
		write(pb[1], "a", 1);
		close(pb[1]);
	}
	else if (pid > 0) {
		close(pa[0]);
		close(pb[1]);

		// phase_1
		write(pa[1], "a", 1);
		close(pa[1]);

		// phase_3
		read(pb[0], buf, 1);
		close(pb[0]);
		printf("%d: received pong\n", getpid());
	}
	else {
		fprintf(2, "pingpong: fork failed\n");
		exit(1);
	}

	exit(0);
}

primes

思路

实现一个基于管道的并发埃式筛（The sieve of Eratosthenes），关键是要理解管道的机制，以及仔细阅读题干给出的[文章](Bell Labs and CSP Threads (swtch.com))，该文章有关该埃式筛方法的介绍图片如下所示：

在这里插入图片描述

该算法的个人感觉十分精妙，以下是基本流程：

  1. 进程 0（主进程）发出一系列从 2 开始的整数序列。
  2. 进程 1 首先接收来自进程 0 发出的第一个整数 prime，prime 一定是一个质数，将其打印出来。然后继续按顺序接收来自进程 0 发出的其它整数，若接收到的某个整数能够被 prime 整除，则丢弃它（不做处理），否则将该整数发送给下一个进程。
  3. 后续进程的操作与进程 1 类似，直到没有任何整数发送给下一个进程，程序终止。

算法的思路并不复杂，主要问题在于如何使用管道实现上述流程中进程 i 与进程 i + 1 之间的通信。我这里只使用了一个 int[2] 来轮换地存放管道的文件描述符，并使用一个缓冲区来暂存每次要发送给下一个进程的数，在一个进程完成它所做的工作后，再将缓冲区中的数据批量写入管道，并创建子进程来完成接下来的工作。这里要千万注意管道完成读取或写入后及时关闭，否则可能会出现子进程读取管道时阻塞的情况。

我在写下这篇博客的过程中发现，虽然我使用的这个方法能够达到预期的效果，并成功通过测试用例，但是其实是有一定问题的：本方法的处理过程是串行的。事实上，每个进程都是在将本进程的所有工作全部完成之后，再调用 fork 来创建子进程，完成后续的工作，本质上与放在一个进程中完成所有工作并没有区别，与文章中提到的 “Concurrent” 完全相悖。理想的做法应该是创建一个 int[2] 数组来存放管道的文件描述符，并及时 fork 子进程来工作，以此来实现并发，具体的代码实现有待后续改进。

代码

// user/primes.c

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


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

	int buf;
	int plist[35];

	for (int i = 2; i <= 35; ++i) {
		write(p[1], (char*)&i, 4);
	}
	close(p[1]);

	while (read(p[0], (char*)&buf, 4)) {
		int prime = buf;
		printf("prime %d\n", prime);

		int pcnt = 0;
		while (read(p[0], (char*)&buf, 4)) {
			if (buf % prime) {
				plist[pcnt++] = buf;
			}
		}
		close(p[0]);

		pipe(p); // rotating pipe

		for (int i = 0; i < pcnt; ++i) {
			write(p[1], (char*)(plist + i), 4);
		}
		close(p[1]);

		int pid = fork();
		if (pid == 0) {
			continue;
		}
		else if (pid > 0) {
			wait(0);
			exit(0);
		}
		else {
			fprintf(2, "primes: fork error\n");
			exit(1);
		}

	}

	exit(0);
}

find

思路

本题是这个 Lab 中我花费时间最长的，代码思路虽然不算很复杂，但是有很多的细节问题我在写的时候没有考虑到，感觉 debug 时间差不多是 coding 的几倍了。。。

题目要求实现一个简易的 find 命令，根据提示可以参考 user/ls.c 对目录的读取操作，并使用递归来实现对子目录的查找。基本思路就是打开一个指定路径的文件（目录也算是特殊的文件），并根据文件的类型做不同处理：

  1. 如果文件是常规文件，则判断改文件名是否是目标文件名（find 的第二个参数），如果是，则将其完整路径打印至标准输出。
  2. 如果文件是目录文件，则读取该目录下的所有文件名，并在该目录路径尾部加上 /st.name，依次构造一个新的文件名继续递归调用 find。注意不要递归进入 . 和 ..，否则将导致无限递归。

以上便是基本思路，具体实现可以阅读完整代码，下面讲一下我遇到的一些问题（bug）：

  1. 使用 fstat 获取文件信息时 st.type 始终为 3（T_DEVICE 类型）。

这个问题其实挺难绷的，原因是我把 if ((fd = open(path, 0)) < 0) 写成了 if ((fd = open(path, 0) < 0))，因为 < 的优先级大于 =，所以导致 fd 的值始终为 0 或 1（逻辑表达式的值只能为真或假），那么后续产生意想不到的结果也就不意外了。。。

  1. 出现 find: cannot open file ./sh ，之后所有文件均打开失败

在打印出文件描述符的值后，问题的起因比较明显了。

在这里插入图片描述

文件描述符一直在增大，最终文件打开失败，open 返回 -1。很明显，是因为文件在打开后没有及时关闭，并释放文件描述符，最终文件描述符被全部占用，新的文件无法再被打开。这也解释了既然程序退出后，所有打开的文件会自动关闭，为什么还要建议手动关闭文件的问题。

  1. 读取到空文件名

前面的问题解决之后，我发现程序仍然会出现无限递归搜索的情况（如下图所示），按理说我已经对文件名进行了判断，如果是 . 或者 .. 则不做处理。

在这里插入图片描述

尝试打印文件名之后，我发现目录的最后一个文件名为空，这样的空文件名将导致程序不断往其末尾追加斜杠 / 而并没有递归进入该目录中。

在这里插入图片描述

事实上，使用 read 读取目录时，在读取目录的所有条目之后，会返回一个空的 dirent 结构体，此时 de.name 为空，作为循环结束的标志。其实 user/ls.c 有针对这个特性的判断，不过当时 coding 的时候没有细看。所以正如 Lab guidance 中所说：

Only when you have a firm grasp of the assignment and solution, then start coding.

代码

// user/find.c

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


char* file_name(char* path) {
	char* p;

	for (p = path + strlen(path); p >= path && *p != '/'; --p);
	++p;

	return p;
}

void find(char* path, char* target) {
	int fd;
	struct dirent de;
	struct stat st;
	char buf[512];
	char* name, * p;

	if ((fd = open(path, 0)) < 0) {
		fprintf(2, "find: cannot open file %s\n", path);
		return;
	}

	if (fstat(fd, &st) < 0) {
		fprintf(2, "find: cannot stat file %s\n", path);
		close(fd);
		return;
	}

	switch (st.type) {
	case T_FILE:
		name = file_name(path);
		if (!strcmp(name, target)) {
			printf("%s\n", path);
		}
		break;
	case T_DIR:
		while (read(fd, &de, sizeof(de)) == sizeof(de)) {
			// prevent infinite recursion
			if (!de.inum || !strcmp(de.name, ".") || !strcmp(de.name, "..")) {
				continue;
			}

			// generate path of sub directory
			strcpy(buf, path);
			p = buf + strlen(buf);
			*p++ = '/';
			memmove(p, de.name, DIRSIZ);
			p[DIRSIZ] = 0;

			find(buf, target);
		}
		break;
	default:
		break;
	}

	close(fd);
}

int main(int argc, char* argv[]) {
	if (argc != 3) {
		fprintf(2, "find: argument count error\n");
		exit(1);
	}

	find(argv[1], argv[2]);

	exit(0);
}

xargs

思路

相较于 find，xargs 的实现就简单很多了。由于之前自己实现过一个简单的 shell，因此对于 exec 系统调用还算比较熟悉，本题的主要内容就是根据 argv 和标准输入构造一个新的参数列表，作为指定命令行程序的参数，并使用 exec 来进行调用。

程序的流程比较简单，这里不过多介绍，直接查看完整代码即可。

代码

// user/xargs.c

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


int main(int argc, char* argv[]) {
	int i;
	char buf[512];
	char* nargv[MAXARG];

	while (gets(buf, MAXARG)) {
		buf[strlen(buf) - 1] = 0; // remove last '\n'

		for (i = 1; argv[i]; ++i) {
			nargv[i - 1] = argv[i];
		}

		nargv[i - 1] = buf;
		nargv[i] = 0;

		int pid = fork();
		if (pid == 0) {
			exec(argv[1], nargv);
		}
		else if (pid > 0) {
			wait(0);
		}
		else {
			fprintf(2, "xargs: fork error\n");
			exit(1);
		}
	}

	exit(0);
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/740341.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

物联网系统运维——实验备份与恢复，数据镜像软件DRBD介绍，DRBD的安装和应用，extundelete的安装和应用（重点），环境准备，配置设置

物联网系统运维——实验备份与恢复，数据镜像软件DRBD介绍，DRBD的安装和应用，extundelete的安装和应用（重点），环境准备，配置设置

一.数据备份 1.数据备份的重要性 备份是系统中需要考虑的最重要的事项,虽然这在系统的整个规划,开发和测试过程中甚至占不到1%,看似不太重要且默默无闻的工作只有到恢复的时候才能真正体现出其重要性,任何数据的丢失与数据宕机&#xff0c;都是不可以被接收的。 2.数据备份策…
阅读更多...
oracle 11g rac安装grid 执行root脚本add vip -n 。。。on node= ... failedFailed 错误处理

oracle 11g rac安装grid 执行root脚本add vip -n 。。。on node= ... failedFailed 错误处理

问题&#xff1a; CRS-4402: The CSS daemon was started in exclusive mode but found an active CSS daemon on node racdg1-1, number 1, and is terminating An active cluster was found during exclusive startup, restarting to join the cluster PRCN-2050 : The requ…
阅读更多...
程序员学长 | 快速学会一个算法，Transformer（下）

程序员学长 | 快速学会一个算法，Transformer（下）

本文来源公众号“程序员学长”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;快速学习一个算法&#xff0c;Transformer&#xff08;二&#xff09; 今天我们来继续分享 Transformer 模型的第二部分&#xff0c;解码器部分。 建…
阅读更多...
热虹吸管的传热计算

热虹吸管的传热计算

热对称管和热管通过使用中空管内的两相流体&#xff0c;在特定的距离上传输大量的热量。 更广泛使用的热管使用吸芯结构将液体输送回热端&#xff0c;而热虹吸管是一个简单的空心管&#xff0c;使用重力。 由于缺乏吸芯结构&#xff0c;使得热虹吸管比传统的热管便宜得多。 然…
阅读更多...
自学指南：必备书籍清单--近100本R语言及生物信息相关书籍

自学指南：必备书籍清单--近100本R语言及生物信息相关书籍

R语言是一种功能丰富的编程语言&#xff0c;数据处理、统计分析是大家所熟知的基本功能。开源免费、活跃的全球社区、灵活可扩展等优点促使R语言飞速发展。目前&#xff0c;CRAN 软件包存储库包含 20446 个可用软件包&#xff0c;涵盖了从生物信息到金融分析等广泛的应用领域。…
阅读更多...
vue3.0(十五)内置组件Teleport和Suspense

vue3.0(十五)内置组件Teleport和Suspense

文章目录 一、Teleport1.基本用法2.禁用Teleport3.多个 Teleport 共享目标4.搭配组件 二、 Suspense1.什么是Suspense2.异步依赖3.加载中状态4.事件5.错误处理6.和其他组件结合注意 一、Teleport <Teleport> 是一个内置组件&#xff0c;它可以将一个组件内部的一部分模板…
阅读更多...
第二十八篇——复盘：世界不完美，我们该怎么办？

第二十八篇——复盘：世界不完美，我们该怎么办？

目录 一、背景介绍二、思路&方案三、过程1.思维导图2.文章中经典的句子理解3.学习之后对于投资市场的理解4.通过这篇文章结合我知道的东西我能想到什么&#xff1f; 四、总结五、升华 一、背景介绍 对于信息传递过程中的相关知识的总结&#xff0c;让我又仿佛回到了每一个…
阅读更多...
Python列表比较：判断两个列表是否相等的多种方法

Python列表比较：判断两个列表是否相等的多种方法

&#x1f4d6; 正文 1 通过排序的方式实现判断 list_a [a, b, c, d] list_b [c, d, a, b]if sorted(list_a) sorted(list_b):print(list_a与list_b的元素相等) else:print(list_a与list_b的元素不相等)通过排序&#xff0c;让两组列表中元素一直后进行判断&#xff0c;得到…
阅读更多...
Linux常用基本命令

Linux常用基本命令

linux目录 1.查看linux本机ip ip addr 2.新建文件夹 mkdir 文件夹名 3.新建文件 touch 文件名.后缀 4.删除文件 rm 文件名.后缀 5.删除文件 rm -r 文件名 6.不询问直接删除 rm -rf 文件名/文件名/ 7.显示目录下文件&#xff0c;文件夹 作用&#xff1a;显示指定目…
阅读更多...
人工ai智能写作，分享推荐三款好用软件！

人工ai智能写作，分享推荐三款好用软件！

在数字化时代&#xff0c;人工智能&#xff08;AI&#xff09;已经渗透到我们生活的方方面面&#xff0c;而在内容创作领域&#xff0c;AI智能写作软件更是如雨后春笋般涌现。今天&#xff0c;就为大家分享三款备受好评的AI智能写作软件&#xff0c;让你轻松掌握高效写作的秘密…
阅读更多...
基于matlab的SVR回归预测

基于matlab的SVR回归预测

1 原理 SVR&#xff08;Support Vector Regression&#xff09;回归预测原理&#xff0c;基于支持向量机&#xff08;SVM&#xff09;的回归分支&#xff0c;其核心思想是通过寻找一个最优的超平面来进行回归预测&#xff0c;并处理非线性回归问题。以下是SVR回归预测原理的系统…
阅读更多...
FFmpeg中位操作相关的源码：GetBitContext结构体，init_get_bits函数、get_bits1函数和get_bits函数分析

FFmpeg中位操作相关的源码：GetBitContext结构体，init_get_bits函数、get_bits1函数和get_bits函数分析

一、引言 由《音视频入门基础&#xff1a;H.264专题&#xff08;3&#xff09;——EBSP, RBSP和SODB》可以知道&#xff0c;H.264 码流中的操作单位是位(bit)&#xff0c;而不是字节。因为视频的传输和存贮是十分在乎体积的&#xff0c;对于每一个比特&#xff08;bit&#xf…
阅读更多...
策略模式 + 抽象工厂实现多方式登录验证

策略模式 + 抽象工厂实现多方式登录验证

文章目录 1、需求背景2、常规想法3、工厂模式 配置文件解耦 策略模式4、具体实现5、其他场景6、一点思考 1、需求背景 以gitee为例&#xff0c;登录验证的方式有多种&#xff1a; 用户名密码登录短信验证码登录微信登录 先写一个登录接口&#xff0c;适配所有方式&#xff…
阅读更多...
udp协议 服务器

udp协议 服务器

1 TCP和UDP基本概念 TCP:(Transmission Control Protocol)是一种面向连接、可靠的基于字节流的传输层通信协议。并且提供了全双工通信&#xff0c;允许两个应用之间建立可靠的链接以进行数据交换 udp:(User Datagram Protocol):是一种无链接、不可靠、基于数据报文传输层协议&…
阅读更多...
websocket服务执行playwright测试

websocket服务执行playwright测试

上一篇博客从源码层面分析了playwright vscode插件实现原理&#xff0c;在上一篇博客中提到&#xff0c;backend服务是一个websocket服务。这遍博客将介绍如何封装一个websocket服务&#xff0c;通过发送消息来执行playwright测试。 初始化项目 第一步是初始化项目和安装必要的…
阅读更多...
​【VMware】VMware Workstation的安装

​【VMware】VMware Workstation的安装

目录 &#x1f31e;1. VMware Workstation是什么 &#x1f31e;2. VMware Workstation的安装详情 &#x1f33c;2.1 VMware Workstation的安装 &#x1f33c;2.2 VMware Workstation的无限使用 &#x1f31e;1. VMware Workstation是什么 VMware Workstation是一款由VMwar…
阅读更多...
【K8s】专题六：Kubernetes 资源限制及服务质量等级

【K8s】专题六：Kubernetes 资源限制及服务质量等级

以下内容均来自个人笔记并重新梳理&#xff0c;如有错误欢迎指正&#xff01;如果对您有帮助&#xff0c;烦请点赞、关注、转发&#xff01;欢迎扫码关注个人公众号&#xff01; 目录 一、资源限制 1、基本介绍 2、工作原理 3、限制方法 二、服务质量等级 一、资源限制 1…
阅读更多...
【软件测试入门】测试用例经典设计方法 — 因果图法

【软件测试入门】测试用例经典设计方法 — 因果图法

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 一、因果图设计测试用例的步骤 1、分析需求 阅读需求文档&#xff0c;如果User Case很复杂&am…
阅读更多...
DIY灯光特效：霓虹灯动画制作教程

DIY灯光特效：霓虹灯动画制作教程

下面我们根据这张霓虹灯案例,教大家如何用智能动物霓虹灯闪烁的效果,大家可以根据思路,实现自己想要的动效效果,一起动手来做吧。 即时设计-可实时协作的专业 UI 设计工具 设置背景 新建画板尺寸为:800PX^600PX,设置背景色#120527。 绘制主题 输入自己喜欢文案,轮廓化,具体…
阅读更多...
PHP-CGI的漏洞（CVE-2024-4577）

PHP-CGI的漏洞（CVE-2024-4577）

通过前两篇文章的铺垫&#xff0c;现在我们可以了解 CVE-2024-4577这个漏洞的原理 漏洞原理 CVE-2024-4577是CVE-2012-1823这个老漏洞的绕过&#xff0c;php cgi的老漏洞至今已经12年&#xff0c;具体可以参考我的另一个文档 简单来说&#xff0c;就是使用cgi模式运行的PHP&…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站