一、背景
第一个Lab是实现几个shell工具，每个工具都是一个可以独立运行的main函数，会调用系统调用，但其本身并不是系统调用。
实验地址：Lab Xv6 and Unix utilities。
二、sleep
1 问题分析
基于已有的系统调用sleep，实现一个sleep命令，也就是一个main小程序，需要关注以下文件：
- 命令工具属于用户态，只要在user目录下即可，参考user/其他程序，user/ (e.g., user/echo.c, user/grep.c, and user/rm.c)。
- 参数不对需要打印错误信息。
- sleep系统调用已经实现kernel/sysproc.c下的sys_sleep，user/user.h下也已经声明了sleep系统调用，可以触发中断，中断汇编代码在user/usys.S。
- 参考工具函数user/ulib.c。
- 在Makefile文件UPROGS下增加这个程序名，要不然不会编译。
2 代码实现
代码语言：c复制#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
int
main(int argc, char *argv[])
{
if(argc != 2){
fprintf(2, "Usage: sleep param too many...n");
exit(1);
}
int t=atoi(argv[1]);
sleep(t);
exit(0);
}三、pingpong
1 问题分析
实现进程间通信，这涉及到几点：
- 父进程fork子进程，父进程返回子进程pid，子进程返回0，父子进程共享数据。
- pipe，pipe是单向通信，需要两个才能实现双向通信。
- 涉及read、write、getpid、pipe。
2 代码实现
代码语言：c复制#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#define ReadFd 0
#define WriteFd 1
/**
* pipe是一段内核buffer，包含一对fd，一个用来读，一个用来写
*/
int
main(int argc, char *argv[])
{
if(argc != 1){
fprintf(2, "Usage: sleep param too many...n");
exit(1);
}
int f2c[2];
int c2f[2];
pipe(f2c);
pipe(c2f);
char buf[64];
//fork对于父进程返回子进程ID，对于子进程返回0
int pid=fork();
if(pid>0){
close(c2f[WriteFd]);
close(f2c[ReadFd]);
int n;
//子进程先发送ping，父进程接收
while((n=read(c2f[ReadFd],buf,64))<=0);
fprintf(0,"%d: received %sn",getpid(),buf);
strcpy(buf,"pong");
//收到ping后，父进程发送pong
n=0;
while((n=write(f2c[WriteFd],buf,sizeof(buf)))<=0);
close(f2c[WriteFd]);
close(c2f[ReadFd]);
wait(&pid);
exit(0);
}else{
close(c2f[ReadFd]);
close(f2c[WriteFd]);
strcpy(buf,"ping");
int n=0;
while((n=write(c2f[WriteFd],buf,sizeof(buf)))<=0);
n=0;
while ((n=read(f2c[ReadFd],buf,64))<=0);
fprintf(0,"%d: received %sn",getpid(),buf);
close(f2c[WriteFd]);
close(c2f[ReadFd]);
exit(0);
}
}pipe是一段内核buffer，包含一对fd，一个用来读，一个用来写。pingpong需要f2c和c2f两对管道来实现父进程向子进程写数据，子进程读，子进程向父进程写数据，父进程读。
四、primes
1 问题分析
多进程来筛选素数，埃氏筛法，并实现CSP模型。
- fork子进程进行下一步筛选，并且父进程需要等待子进程、子孙进程的结束。
- 文件句柄上限是35，超过会报错。
- 递归。
- 及时释放文件句柄，避免阻塞。
- 一定要并发，不能够串行，父进程向管道写入数据时要先fork子进程，尽量提高并行程度。
这里涉及到对pipe的理解。pipe是一段内核buffer，包含一对fd，一个用来读，一个用来写。如果读到空时则阻塞进程，如果向写满的pipe继续写入时也会阻塞。那么就会有一个问题：子进程读到空时阻塞，无法结束，而父进程需要wait子进程，也就不能够结束，是不是就死锁了？
pipe读到空时虽然会阻塞，但要是 write fd完全被关闭，则读进程就会被唤醒，返回0，所以我们一定要及时关闭对应的文件描述符，避免死锁。
pipe2 代码实现
代码语言：c复制#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#define ReadFd 0
#define WriteFd 1
int prime(int fd);
int
main(int argc, char *argv[])
{
if(argc>2)
{
fprintf(2,"usage: primes [number]");
exit(1);
}
int n=35;
if(argc==2)
{
int t=atoi(argv[1]);
if(t<1)
{
fprintf(2,"parameter is invalid!");
exit(1);
}
if(t>35)
n=t;
}
int pp[2];
pipe(pp);
int pid=fork();
if(pid>0){
close(pp[ReadFd]);
for (int i = 2; i <= n; i ){
write(pp[WriteFd],&i,sizeof(int));
}
close(pp[WriteFd]);
wait(&pid);
}else{
close(pp[WriteFd]);
prime(pp[ReadFd]);
close(pp[ReadFd]);
}
exit(0);
}
int prime(int fd){
int first=2;
int buf;
if(read(fd,&buf,sizeof(int))<=0){
exit(0);
}
first=buf;
fprintf(0,"prime %dn",first);
int pp[2];
pipe(pp);
//传递数据前先fork子进程提高并行程度
int pid=fork();
if(pid>0){
close(pp[ReadFd]);
while (read(fd,&buf,sizeof(int))>0){
if(buf%first!=0){
write(pp[WriteFd],&buf,sizeof(int));
}
}
close(pp[WriteFd]);
}else{
close(pp[WriteFd]);
prime(pp[ReadFd]);
close(pp[ReadFd]);
}
wait(&pid);
exit(0);
}五、find
1 问题分析
从指定目录下寻找目标文件。
- 参考ls.c，读目录。
- 迭代 递归，但是避免对"."、".."进行，否则会死循环。
- make clean可以清除文件系统。
2 涉及的数据结构
代码语言：c复制//目录项
#define DIRSIZ 14
struct dirent {
ushort inum;
char name[DIRSIZ];
};
# 使用read读取目录即可。//文件元信息
#define T_DIR 1 // Directory
#define T_FILE 2 // File
#define T_DEVICE 3 // Device
struct stat {
int dev; // File system's disk device
uint ino; // Inode number
short type; // Type of file
short nlink; // Number of links to file
uint64 size; // Size of file in bytes
};
int fstat(int fd, struct stat*);3 代码实现
代码语言：c复制#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
#include "kernel/fcntl.h"
char*
fmtname(char *path)
{
static char buf[DIRSIZ 1];
char *p;
// Find first character after last slash.
for(p=path strlen(path); p >= path && *p != '/'; p--)
;
p ;
// Return blank-padded name.
if(strlen(p) >= DIRSIZ)
return p;
memmove(buf, p, strlen(p));
memset(buf strlen(p), ' ', DIRSIZ-strlen(p));
if (strlen(buf) == 0) return buf;
for (int i = strlen(buf) - 1; i > 0; i--) {
if (buf[i - 1] != ' ') {
buf[i] = ' ';
return buf;
}
}
return buf;
return buf;
}
void
find(char *path,char *file){
char buf[512], *p;
int fd;
struct dirent de;
struct stat st;
if((fd = open(path, 0)) < 0){
fprintf(2, "find: cannot open %sn", path);
return;
}
if(fstat(fd, &st) < 0){
fprintf(2, "ls: cannot stat %sn", path);
close(fd);
return;
}
switch(st.type){
case T_FILE:
//如果path是普通文件且最后一级是file
if(strcmp(file,fmtname(path))==0){
fprintf(1,"%sn",path);
}
break;
case T_DIR:
//path "/" dirent.name
if(strlen(path) 1 DIRSIZ 1 > sizeof buf){
printf("ls: path too longn");
break;
}
strcpy(buf, path);
p = buf strlen(buf);
*p = '/';
//buf=path "/" 子目录名
while(read(fd, &de, sizeof(de)) == sizeof(de)){
if(de.inum == 0)
continue;
//不要对当前目录和上级目录递归，会死循环
if(strcmp(de.name,".")==0 || strcmp(de.name,"..")==0)
continue;
memmove(p, de.name, DIRSIZ);
p[DIRSIZ] = 0;
if(stat(buf, &st) < 0){
printf("find: cannot stat %sn", buf);
continue;
}
find(buf,file);
}
break;
}
close(fd);
}
int
main(int argc, char *argv[])
{
if(argc != 3){
fprintf(2, "Usage: find param err...n");
exit(1);
}
char *dir=argv[1];
//file必须是文件名，不能是目录
char *file=argv[2];
find(dir,file);
exit(0);
}六、xargs
1 问题分析
这个shell命令的作用是将管道左边的输出作为xargs命令的输入，能够起到连接多条命令的作用。
- 从标准输入中读取所有行数据，然后将每一行作为xargs后面跟着的命令的参数去执行，左边有多少行，右边就执行多少次。要注意换行符“n”
测试用例2 代码实现
代码语言：c复制#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/param.h"
#define BUFSIZE 1024
#define MAXLEN 100
int
main(int argc,char* argv[]){
if(argc<2){
fprintf(2,"Usage: xargs commandn");
exit(1);
}
char *param[MAXARG];
int index=0;
for(int i=1;i<argc;i ){
if(strcmp(argv[i],"-n")==0){
i ;
}else{
param[index]=(char*)malloc(strlen(argv[i]));
strcpy(param[index ],argv[i]);
}
}
char buf[MAXLEN],*p=buf;
while(read(0,p ,1)==1);
int l=0,r=0;
//"n"输入后是两个字符"\" "n"，而不是"n"
while(r<strlen(buf)){
if(buf[r]=='\'&&r<strlen(buf)-1&&buf[r 1]=='n'){
buf[l]='n';
r =2;
l ;
}else{
buf[l ]=buf[r ];
}
}
buf[l]=0;
// fprintf(1,"buf: %s, len: %dn",buf,strlen(buf));
l=0;
while(buf[l]=='"'){
l ;
}
//最后面会有一个换行符
r=strlen(buf)-1-1;
while(buf[r]=='"'){
r--;
}
for(int i=l;i<=r ;i ){
buf[i-l]=buf[i];
}
buf[r 1-l]='n';
buf[r 2-l]=0;
// fprintf(1,"l: %d, r: %d, buf: %s, len: %dn",l,r,buf,strlen(buf));
l=0;r=0;
while(r<strlen(buf)){
if(buf[r]=='n'){
param[index]=(char*)malloc(r-l);
memmove(param[index],buf l,r-l);
// fprintf(1,"index: %d, line: %sn",index,param[index]);
int pid=fork();
if (pid==0){
exec(param[0], param);
exit(0);
}else{
wait(&pid);
}
r ;
l=r;
}else{
r ;
}
}
exit(0);
}主要逻辑就是将=从标准输入中读取数据，并按照'n'进行分行，将每行数据作为xargs后面命令的参数，有多少行就执行多少次。要注意终端输入的"n"并不是'n'，而是'' 'n'两个字符。
