Lab1
启动xv6(难度：Easy)
https://lmx.gitbook.io/mit-6.s081/
sleep(难度：Easy)
YOUR JOB
实现xv6的UNIX程序
sleep：您的sleep应该暂停到用户指定的计时数。一个滴答(tick)是由xv6内核定义的时间概念，即来自定时器芯片的两个中断之间的时间。您的解决方案应该在文件*user/sleep.c*中
// user/ulib.c
int
atoi(const char *s)
{
int n;
n = 0;
while('0' <= *s && *s <= '9')
n = n*10 + *s++ - '0';
return n;
}
// kernel/sysproc.c
uint64
sys_sleep(void)
{
int n;
uint ticks0;
if(argint(0, &n) < 0)
return -1;
acquire(&tickslock);
ticks0 = ticks;
while(ticks - ticks0 < n){
if(myproc()->killed){
release(&tickslock);
return -1;
}
sleep(&ticks, &tickslock);
}
release(&tickslock);
return 0;
}
// kernel/sysproc.h
#define SYS_sleep 13
// user/user.h提供了sleep的声明以便其他程序调用,用汇编程序编写的user/usys.S可以帮助sleep从用户区跳转到内核区。实现代码：
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
int
main(int args,char *argv[])
{
if (args < 2) {
fprintf(2,"Usage: sleep time\n");
exit(1);
}
int t;
t = atoi(argv[1]);
sleep(t);
exit(0);
}测试：
./grade-lab-util sleep
# output:
== Test sleep, no arguments == sleep, no arguments: OK (3.4s)
== Test sleep, returns == sleep, returns: OK (1.0s)
== Test sleep, makes syscall == sleep, makes syscall: OK (1.1s) pingpong（难度：Easy）
YOUR JOB
编写一个使用UNIX系统调用的程序来在两个进程之间“ping-pong”一个字节，请使用两个管道，每个方向一个。父进程应该向子进程发送一个字节;子进程应该打印“
<pid>: received ping”，其中<pid>是进程ID，并在管道中写入字节发送给父进程，然后退出;父级应该从读取从子进程而来的字节，打印“<pid>: received pong”，然后退出。您的解决方案应该在文件*user/pingpong.c*中。
请使用两个管道
不用两个管道会报莫名其妙的错误(我还是看不透pipe)
p[0] 是管道的读端，p[1]是管道的写端
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
char buf[1024];
int
main(int argc, char const *argv[])
{
if (argc > 1) {
fprintf(2,"Usage: pingpong\n");
exit(1);
}
// cp child pipe，pp parent pipe
int cp[2],pp[2];
// cbuf：child buf
char cbuf[10],pbuf[10];
// Initialize the read(p[0]) and write(p[1]) side of the pipeline
pipe(cp);
pipe(pp);
int rc = fork();
// fork 会让父子复制文件描述符，管道fork之后可以看成连接父子，四个端口，所以你会看到下面重复close
if (rc==0) {
//entry child
// close the write side when reading
close(cp[1]);
// receive parent ping
int r = read(cp[0],cbuf,1);
if (r > 0) {
printf("%d: received ping\n",getpid());
}
close(cp[0]);
// send pong
// Close the read side of parent when writing
close(pp[0]);
write(pp[1],"c",1);
close(pp[1]);
exit(0);
} else if (rc > 0) {
// entry parent
// Close the read side of child pipe when writing
close(cp[0]);
write(cp[1],"p",1);
// close the write side after writing
close(cp[1]);
// receive pong
wait(0);
// close the write side when reading
close(pp[1]);
int r = read(pp[0],pbuf,1);
if (r > 0) {
printf("%d: received pong\n",getpid());
}
// close the read side after reading
close(pp[0]);
} else {
fprintf(2,"fork error\n");
exit(1);
}
exit(0);
}
测试：
root@ubuntu:/home/lmx/Desktop/xv6-labs-2020# ./grade-lab-util pingpong
make: 'kernel/kernel' is up to date.
== Test pingpong == pingpong: OK (0.9s) Primes(素数，难度：Moderate/Hard)
tasks:
YOUR JOB
使用管道编写
prime sieve(筛选素数)的并发版本。这个想法是由Unix管道的发明者Doug McIlroy提出的。请查看这个网站，该网页中间的图片和周围的文字解释了如何做到这一点。您的解决方案应该在*user/primes.c*文件中。
感觉上面那题会了的话，这题比上一题简单
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
int
main(int argc, char const *argv[])
{
int p[2],nums[36];
int index = 0;
for (int i=2;i<36;i++) {
nums[index++] = i;
}
while (index > 0)
{
// p[0] read , p[1] write
pipe(p);
int rc = fork();
if (rc > 0) {
// entry parent
close(p[0]);
for(int i=0;i<index;i++) {
write(p[1],&nums[i],sizeof(int));
}
close(p[1]);
// 主进程一直在这里等着子进程完成，子进程一完成就会进入
wait(0);
// 如果这里不exit的话，当打完所有的素数后就会陷入死循环
exit(0);
} else if (rc == 0) {
close(p[1]);
index = -1;
int val,prime;
prime = -1;
while (read(p[0],&val,sizeof(int)) > 0)
{
if (index < 0) {
prime = val;
index++;
}else if (val%prime!=0) {
nums[index++] = val;
}
}
close(p[0]);
printf("prime %d\n",prime);
}
}
exit(0);
}
测试：
root@ubuntu:/home/lmx/Desktop/xv6-labs-2020# ./grade-lab-util primes
make: 'kernel/kernel' is up to date.
== Test primes == primes: OK (1.5s) 关于上面的主线程为什么要exit，有一个比较坑的地方：
看下面程序:
#include<stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
int main(int argc, char const *argv[])
{
int index = 0;
while (index <= 3)
{
printf("entry while\n");
int rc = fork();
if (rc == 0) {
printf("child pid:%d\n",getpid());
index++;
printf("%d \n",index);
sleep(1);
}else {
printf("parent pid:%d\n",getpid());
wait(0);
exit(0);
}
}
printf("break while\n");
exit(0);
}
// 它会进入死循环，然后一直 输出
/*
entry while
parent pid:24154
child pid:24167
3
*/首先fork出来的是进程，父和子的index是不相通的
当子进程的index超过3，子进程就会结束
这里意思就是在3之前主进程都在wait(),3的时候子进程会exit，这时候index为2的是它的父进程，而这个2的进程同时也是1的子进程，所以那个最初的进程一直都不会退出，然后一直卡在index为2的那个线程那里，一直fork。
当到子进程的index为2时，他成为父进程，fork一个子进程，子进程复制变量，index=2，index++ 变成3，然后该子进程退出。但是此时父进程的index是2，它还会继续进入循环，又fork一个子进程，子进程再复制变量，然后自增，周而复始...这样就一直卡在3这里了
所以必须有个 exit(0),在他完成所有的子任务第一遍时，也就是打印第一遍3的时候就退出程序，这样就完成了任务了
再看上面的通关代码，也是如此，如果没有exit(0),就会一直卡在输出31的地方，因为它也会在那时候一直fork一个子进程，然后退出然后再fork再退出再fork。
反正就是要记得，fork会复制变量，但是父子的变量是不同的，子进程的这个变量改变不会影响父进程的值。也就是fork是变量复制但不共享
find（难度：Moderate）
YOUR JOB
写一个简化版本的UNIX的
find程序：查找目录树中具有特定名称的所有文件，你的解决方案应该放在*user/find.c*
刚开始不知道他要实现啥，写完只通过了第一个test，但是输出显示第二个test我失败是miss了一些输出，那我按它的输入去debug，发现我没有递归进子目录....蠢得可以，又改了一下才ok，所以还是要好好思考...
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
void find(char* path) {
// 这里得代码主要是参照 ls.c 的，lab里面提示的，应该不算作弊(bushi
int fd;
char buf[512];
char *p;
struct dirent de;
struct stat st;
if ((fd=open(path,0))<0)
{
fprintf(2, "find: %s: No such file or directory\n", path);
return;
}
if(fstat(fd, &st) < 0){
fprintf(2, "find: %s:cannot stat\n", path);
close(fd);
return;
}
switch (st.type)
{
case T_FILE:
// 如果是文件直接输出就可了
printf("%s\n",path);
break;
case T_DIR:
// 如果是dir处理起来麻烦点，但是不难，就是要记得如果子目录也是dir的话也要进行递归
if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
printf("find: path too long\n");
return;
}
strcpy(buf, path);
p = buf+strlen(buf);
*p++ = '/';
while (read(fd, &de, sizeof(de)) == sizeof(de))
{
if(de.inum == 0) {
continue;
}
// 因为de.name的定义是 char name[DIRSIZ];
// 这里会直接把p的值设为de.name
// 但是前面已经*p++='/'了，所以de.name会添加在buf的'/'后面
memmove(p, de.name, DIRSIZ);
p[DIRSIZ] = 0;
if(stat(buf, &st) < 0){
printf("find: cannot stat %s\n", buf);
continue;
}
if(st.type==T_FILE){
printf("%s\n",buf);
}else if (st.type==T_DIR&&strcmp(de.name,".")!=0&&strcmp(de.name,"..")!=0){
printf("%s\n",buf);
find(buf);
}else {
printf("%s\n",buf);
}
}
break;
}
close(fd);
}
int main(int argc, char *argv[])
{
// the solution of find
if(argc == 1) {
find(".");
exit(0);
}
// 有几个要查找得参数就查几次
for(int i = 1;i < argc;i++) {
find(argv[i]);
}
exit(0);
}
test:
./grade-lab-util find
make: 'kernel/kernel' is up to date.
== Test find, in current directory == find, in current directory: OK (2.1s)
== Test find, recursive == find, recursive: OK (1.8s) 不知道有没有更快得实现，期待一手
xargs (难度： Moderate)
前面的find实现有坑，我的find理解和出题人的find理解不同
在ubuntu下的 find . b 不是先 find . 再 find b吗，我试了一下就是这样啊，但是这道题目要求find . b 是在 . 路径下寻找 b 的目录，这让我不得不回去改了一下find的代码，先贴上改完的find，被迫无奈：
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
char* filename;
void find(char* path,int bool) {
int fd;
char buf[512];
char *p;
struct dirent de;
struct stat st;
if ((fd=open(path,0))<0)
{
fprintf(2, "find: %s: No such file or directory\n", path);
return;
}
if(fstat(fd, &st) < 0){
fprintf(2, "find: %s:cannot stat\n", path);
close(fd);
return;
}
switch (st.type)
{
case T_FILE:
if(bool == 0) {
printf("%s\n",buf);
}else if (bool == 1 && strcmp(filename,de.name)==0){
printf("%s\n",buf);
}
break;
case T_DIR:
if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
printf("find: path too long\n");
return;
}
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(st.type==T_FILE){
if(bool == 0) {
printf("%s\n",buf);
}else if (bool == 1 && strcmp(filename,de.name)==0){
printf("%s\n",buf);
}
}else if (st.type==T_DIR&&strcmp(de.name,".")!=0&&strcmp(de.name,"..")!=0){
if (bool == 0) {
printf("%s\n",buf);
find(buf,0);
}else if(bool == 1) {
if (strcmp(filename,de.name)==0) {
printf("%s\n",buf);
}
find(buf,1);
}
}
}
break;
}
close(fd);
}
int main(int argc, char *argv[])
{
// the solution of find
if(argc == 1) {
find(".",0);
exit(0);
}
if(argc == 3 && strcmp(argv[1],".")==0) {
filename = (char *)malloc(sizeof(argv[2]));
filename = argv[2];
find(".",1);
exit(0);
}
for(int i = 1;i < argc;i++) {
find(argv[i],0);
}
exit(0);
}通过实现：
#include "kernel/types.h"
#include "kernel/stat.h"
#include "kernel/param.h"
#include "user/user.h"
const int MAXREAD = 1024;
int main(int argc, char *argv[])
{
// stdout 0
char* params[MAXARG];
int index = 0;
for(int i=1;i<argc;i++){
params[index++] = argv[i];
}
char buf[MAXREAD];
int bytes = 0;
while ((bytes=read(0,&buf,MAXREAD))>0)
{
char *arg = (char *)malloc(sizeof(buf));
int argi = 0;
// 因为下面要执行 exec，所以需要fork
int rc = fork();
if(rc==0) {
for(int i=0;i<bytes;i++) {
// 如果碰到 \n or space 说明一个单词结束了，这时候添加进params然后重置初始化工作
if(buf[i]=='\n'||buf[i]==' ') {
// 结束标志,不加也行
arg[argi] = '\0;
argi = 0;
params[index++] = arg;
arg = (char *)malloc(sizeof(arg));
}else {
arg[argi++]=buf[i];
}
}
exec(argv[1],params);
}else {
wait(0);
}
}
exit(0);
}test:
root@ubuntu:/home/lmx/Desktop/xv6-labs-2020# ./grade-lab-util xargs
make: 'kernel/kernel' is up to date.
== Test xargs == xargs: OK (2.0s)
(Old xv6.out.xargs failure log removed)
root@ubuntu:/home/lmx/Desktop/xv6-labs-2020# ./grade-lab-util find
make: 'kernel/kernel' is up to date.
== Test find, in current directory == find, in current directory: OK (1.2s)
== Test find, recursive == find, recursive: OK (1.1s)
Last updated