操作系统大作业——基于OrangeOS的改写（3）

武汉大学21级网安操作系统大作业 任务三

?1. 问题介绍与思路摘要

?1.1 问题介绍

本任务是OS期末实验的第三个基本任务，主要目标是改造任务二的shell，使其能够在同一个shell中支持多任务执行。几点需要注意的地方如下：

? 注意现有内存管理可能不支持多程序支持

? 可执行程序的装入和内存定位问题需要仔细考虑

?1.2 思路摘要

在本次实验中，我们利用"&"符号分割输入的多条命令，拓展 kernel/main.c中的shabby_shell函数使其能够同时执行多条命令。核心思路如下：

? 创建二维字符串数组

char*?multi_argv[MAX_SHELL_PROC][MAX_SHELL_PROC_STACK]

? 在argv中保存输入的所有字符串后，对argv进行扫描，把用&分割得到的命令分别保存在multi_argv中。

? 父进程借助for循环fork出所有的子进程，子进程被fork出来后主动将自己阻塞，等待父进程解除阻塞后，调用execv执行。?

同时我们需要注意，父进程利用for循环进行fork时，得到的子进程同样在该循环中，以及如果子进程抢占了父进程，则父进程可能无法完成fork出所有子进程的过程，导致无法同时运行多条指令。上述问题我们实验具体思路及实现中详细介绍并解决。?

2. 具体思路及其实现?

在本次实验中，我们需要对shell进行改造使之可以同时解析和执行多条命令。这一部分的实现原理较为简单，书本给出的原始代码已经在第十章实现了fork、exit、wait、exec等系统调用函数，并实现了一个简单的shell，也已经具备了将 command文件夹中的指令文件编译链接并装载入操作系统的能力。所以我们要扩展shell，只需要修改shell的函数即可。

任务三基于任务二的代码，shell的代码在kernel/main.c中，由Init()进程fork出来。要完成这部分的改造，我们首先需要了解原始shabby_shell函数、wait函数和execv函数。

?2.1 shabby_shell函数

?shell目前的功能很简单，只实现了读取命令并执行之（如果命令存在的话）。代码如下：

void?shabby_shell(const?char?*?tty_name)??
{??
????int?fd_stdin??=?open(tty_name,?O_RDWR);??
????assert(fd_stdin??==?0);??
????int?fd_stdout?=?open(tty_name,?O_RDWR);??
????assert(fd_stdout?==?1);??
??
????char?rdbuf[128];??
??
????while?(1)?{??
????????write(1,?"$?",?2);??
????????int?r?=?read(0,?rdbuf,?70);??
????????rdbuf[r]?=?0;??
??
????????int?argc?=?0;??
????????char?*?argv[PROC_ORIGIN_STACK];??
????????char?*?p?=?rdbuf;??
????????char?*?s;??
????????int?word?=?0;??
????????char?ch;??
????????do?{??
????????????ch?=?*p;??
????????????if?(*p?!=?'?'?&&?*p?!=?0?&&?!word)?{??
????????????????s?=?p;??
????????????????word?=?1;??
????????????}??
????????????if?((*p?==?'?'?||?*p?==?0)?&&?word)?{??
????????????????word?=?0;??
????????????????argv[argc++]?=?s;??
????????????????*p?=?0;??
????????????}??
????????????p++;??
????????}?while(ch);??
????????argv[argc]?=?0;??
??
????????int?fd?=?open(argv[0],?O_RDWR);??
????????if?(fd?==?-1)?{??
????????????if?(rdbuf[0])?{??
????????????????write(1,?"{",?1);??
????????????????write(1,?rdbuf,?r);??
????????????????write(1,?"}\n",?2);??
????????????}??
????????}??
????????else?{??
????????????close(fd);??
????????????int?pid?=?fork();??
????????????if?(pid?!=?0)?{?/*?parent?*/??
????????????????int?s;??
????????????????wait(&s);??
????????????}??
????????????else?{??/*?child?*/??
????????????????execv(argv[0],?argv);??
????????????}??
????????}??
????}??
??
????close(1);??
????close(0);??
}??

可以分析出，shabby_shell用write()打印一个简单的提示符 $ 到标准输出，之后用read()读取用户输入，然后用open尝试打开与输入命令同名的文件。如果文件存在，即fd!=-1，就认为这是一个可执行文件，然后关闭文件描述符fd，通过fork()创建一个新的进程，在父进程中，使用wait(&s)等待子进程完成；在子进程中，使用execv()执行用户输入的命令。如果文件不存在，就将输入的命令直接输出给用户。跟任务二中的流程图是一样的，这里再放一张：?

?

2.2 wait函数?& exit函数?

?在shabby_shell中有一个wait函数，而wait与exit是一对函数。exit()执行后杀死进程，wait()执行后挂起程序，与fork()相同，这两个函数工作时将会返回EXIT和WAIT消息给MM。在MM中，收到的消息分别由do_exit()和do_wait()来处理。

下面是wait.c中的wait()、exit.c中的exit()、与forkexit.c中的do_wait()和do_exit()的代码，之后我会将其结合起来理解。

PUBLIC?int?wait(int?*?status)??
{??
????MESSAGE?msg;??
????msg.type???=?WAIT;??
??
????send_recv(BOTH,?TASK_MM,?&msg);??
??
????*status?=?msg.STATUS;??
??
????return?(msg.PID?==?NO_TASK???-1?:?msg.PID);??
}??

PUBLIC?void?exit(int?status)??
{??
????MESSAGE?msg;??
????msg.type????=?EXIT;??
????msg.STATUS??=?status;??
??
????send_recv(BOTH,?TASK_MM,?&msg);??
????assert(msg.type?==?SYSCALL_RET);??
}?

PUBLIC?void?do_wait()??
{??
????int?pid?=?mm_msg.source;??
??
????int?i;??
????int?children?=?0;??
????struct?proc*?p_proc?=?proc_table;??
????for?(i?=?0;?i?<?NR_TASKS?+?NR_PROCS;?i++,p_proc++)?{??
????????if?(p_proc->p_parent?==?pid)?{??
????????????children++;??
????????????if?(p_proc->p_flags?&?HANGING)?{??
????????????????cleanup(p_proc);??
????????????????return;??
????????????}??
????????}??
????}??
??
????if?(children)?{??
????????/*?has?children,?but?no?child?is?HANGING?*/??
????????proc_table[pid].p_flags?|=?WAITING;??
????}??
????else?{??
????????/*?no?child?at?all?*/??
????????MESSAGE?msg;??
????????msg.type?=?SYSCALL_RET;??
????????msg.PID?=?NO_TASK;??
????????send_recv(SEND,?pid,?&msg);??
????}??
}??

PUBLIC?void?do_exit(int?status)??
{??
????int?i;??
????int?pid?=?mm_msg.source;?/*?PID?of?caller?*/??
????int?parent_pid?=?proc_table[pid].p_parent;??
????struct?proc?*?p?=?&proc_table[pid];??
??
????/*?tell?FS,?see?fs_exit()?*/??
????MESSAGE?msg2fs;??
????msg2fs.type?=?EXIT;??
????msg2fs.PID?=?pid;??
????send_recv(BOTH,?TASK_FS,?&msg2fs);??
??
????free_mem(pid);??
??
????p->exit_status?=?status;??
??
????if?(proc_table[parent_pid].p_flags?&?WAITING)?{?/*?parent?is?waiting?*/??
????????proc_table[parent_pid].p_flags?&=?~WAITING;??
????????cleanup(&proc_table[pid]);??
????}??
????else?{?/*?parent?is?not?waiting?*/??
????????proc_table[pid].p_flags?|=?HANGING;??
????}??
??
????/*?if?the?proc?has?any?child,?make?INIT?the?new?parent?*/??
????for?(i?=?0;?i?<?NR_TASKS?+?NR_PROCS;?i++)?{??
????????if?(proc_table[i].p_parent?==?pid)?{?/*?is?a?child?*/??
????????????proc_table[i].p_parent?=?INIT;??
????????????if?((proc_table[INIT].p_flags?&?WAITING)?&&??
????????????????(proc_table[i].p_flags?&?HANGING))?{??
????????????????proc_table[INIT].p_flags?&=?~WAITING;??
????????????????cleanup(&proc_table[i]);??
????????????}??
????????}??
????}??
}??

? exit()

这是用户空间的函数，由进程调用以结束自己。它发送一个包含退出状态的消息给内存管理任务（TASK_MM），告知系统进程希望退出。

? do_exit()

当内存管理任务接收到退出请求时，do_exit 函数被调用。它的主要工作包括：

??????????通知文件系统（为了可能的资源释放，如关闭打开的文件）

??????????释放该进程占用的内存

??????????设置进程的退出状态

??????????如果父进程正在等待（即处于 WAITING 状态），则清理退出进程的资源并发送信号给父进程；如果父进程不在等待，则设置该进程为 HANGING（即成为僵尸进程）。

??????????遍历进程表，将所有该进程的子进程的父进程设置为 INIT 进程，这样如果子进程退出，它们将被 INIT 进程清理。

???wait()

这个函数也在用户空间调用，通常由父进程调用以等待其子进程的退出。它向内存管理任务发送等待消息，并阻塞直到有子进程退出。

?? do_wait()

当内存管理任务收到等待请求时，do_wait 函数被调用。它检查是否有任何子进程已经退出（即处于 HANGING 状态）：

??????????如果有，则清理这些子进程，并将它们的退出状态发送给父进程。

??????????如果没有，且该进程确实有子进程，则设置该进程为 WAITING 状态，等待其子进程退出。

??????????如果没有子进程，返回错误。

具体的，举个例子。?

假设进程P有子进程A。而A调用exit()，那么内存管理模块 (MM) 将会：?

1.告诉文件系统 (FS)：A退出，请做相应处理。

2.释放A占用的内存。

3.判断P是否正在等待(WAITING)：

????????（1）如果是：

??????????????????清除P的WAITING位；

??????????????????向P发送消息以解除阻塞（到此P的wait()函数结束）；

??????????????????释放A的进程表项（到此A的exit()函数结束）。

????????（2）如果否：

??????????????????设置A的HANGING位。

4.遍历proc_table[]，寻找A的子进程（如果有的话）：

????????（1）将Init进程设置为A的子进程的父进程（换言之，将A的子进程过继给Init）。

????????（2）判断是否满足Init正在WAITING且A的子进程正在HANGING：

??????????????????如果是：

????????????????????????i.清除Init的WAITING位；

????????????????????????ii.向Init发送消息以解除阻塞（到此Init的wait()函数结束）；

????????????????????????iii.释放A的子进程的进程表项（到此A的子进程的exit()函数结束）。

??????????????????如果否：

????????????????????????i.如果Init正在WAITING但A的子进程没有HANGING，那么“握手”会在将来A的子进程调用exit()时发生；

????????????????????????ii.如果A的子进程正在HANGING但Init没有WAITING，那么“握手”会在将来Init调用wait()时发生。

如果P调用wait()，那么MM将会：

1.遍历proc_table[]，寻找P的子进程A：

????????（1）如果A正在HANGING，那么：

??????????????????向P发送消息以解除阻塞（到此P的wait()函数结束）；

??????????????????释放A的进程表项（到此A的exit()函数结束）。

????????（2）如果A不在HANGING，那么：

??????????????????设P的WAITING位。

2.如果P没有子进程：

向P发送消息，消息携带一个表示出错的返回值（到此P的wait()函数结束）。

?2.3 execv函数

在shabby_shell中还有一个execv函数，而execv()所做的其实只是一件事，即向MM提供最终供调用exec的进程使用的堆栈。?

?下面是exec.c中的execv()和mm/do_exec()的代码。

PUBLIC?int?execv(const?char?*path,?char?*?argv[])??
{??
????char?**p?=?argv;??
????char?arg_stack[PROC_ORIGIN_STACK];??
????int?stack_len?=?0;??
??
????while(*p++)?{??
????????assert(stack_len?+?2?*?sizeof(char*)?<?PROC_ORIGIN_STACK);??
????????stack_len?+=?sizeof(char*);??
????}??
??
????*((int*)(&arg_stack[stack_len]))?=?0;??
????stack_len?+=?sizeof(char*);??
??
????char?**?q?=?(char**)arg_stack;??
????for?(p?=?argv;?*p?!=?0;?p++)?{??
????????*q++?=?&arg_stack[stack_len];??
??
????????assert(stack_len?+?strlen(*p)?+?1?<?PROC_ORIGIN_STACK);??
????????strcpy(&arg_stack[stack_len],?*p);??
????????stack_len?+=?strlen(*p);??
????????arg_stack[stack_len]?=?0;??
????????stack_len++;??
????}??
??
????MESSAGE?msg;??
????msg.type????=?EXEC;??
????msg.PATHNAME????=?(void*)path;??
????msg.NAME_LEN????=?strlen(path);??
????msg.BUF?????=?(void*)arg_stack;??
????msg.BUF_LEN?=?stack_len;??
??
????send_recv(BOTH,?TASK_MM,?&msg);??
????assert(msg.type?==?SYSCALL_RET);??
??
????return?msg.RETVAL;??
}??

PUBLIC?int?do_exec()??
{??
????/*?get?parameters?from?the?message?*/??
????int?name_len?=?mm_msg.NAME_LEN;?/*?length?of?filename?*/??
????int?src?=?mm_msg.source;????/*?caller?proc?nr.?*/??
????assert(name_len?<?MAX_PATH);??
??
????char?pathname[MAX_PATH];??
????phys_copy((void*)va2la(TASK_MM,?pathname),??
??????????(void*)va2la(src,?mm_msg.PATHNAME),??
??????????name_len);??
????pathname[name_len]?=?0;?/*?terminate?the?string?*/??
??
????/*?get?the?file?size?*/??
????struct?stat?s;??
????int?ret?=?stat(pathname,?&s);??
????if?(ret?!=?0)?{??
????????printl("{MM}?MM::do_exec()::stat()?returns?error.?%s",?pathname);??
????????return?-1;??
????}??
??
????/*?read?the?file?*/??
????int?fd?=?open(pathname,?O_RDWR);??
????if?(fd?==?-1)??
????????return?-1;??
????assert(s.st_size?<?MMBUF_SIZE);??
????read(fd,?mmbuf,?s.st_size);??
????close(fd);??
??
????/*?overwrite?the?current?proc?image?with?the?new?one?*/??
????Elf32_Ehdr*?elf_hdr?=?(Elf32_Ehdr*)(mmbuf);??
????int?i;??
????for?(i?=?0;?i?<?elf_hdr->e_phnum;?i++)?{??
????????Elf32_Phdr*?prog_hdr?=?(Elf32_Phdr*)(mmbuf?+?elf_hdr->e_phoff?+??
????????????????????????(i?*?elf_hdr->e_phentsize));??
????????if?(prog_hdr->p_type?==?PT_LOAD)?{??
????????????assert(prog_hdr->p_vaddr?+?prog_hdr->p_memsz?<??
????????????????PROC_IMAGE_SIZE_DEFAULT);??
????????????phys_copy((void*)va2la(src,?(void*)prog_hdr->p_vaddr),??
??????????????????(void*)va2la(TASK_MM,??
?????????????????????????mmbuf?+?prog_hdr->p_offset),??
??????????????????prog_hdr->p_filesz);??
????????}??
????}??
??
????/*?setup?the?arg?stack?*/??
????int?orig_stack_len?=?mm_msg.BUF_LEN;??
????char?stackcopy[PROC_ORIGIN_STACK];??
????phys_copy((void*)va2la(TASK_MM,?stackcopy),??
??????????(void*)va2la(src,?mm_msg.BUF),??
??????????orig_stack_len);??
??
????u8?*?orig_stack?=?(u8*)(PROC_IMAGE_SIZE_DEFAULT?-?PROC_ORIGIN_STACK);??
??
????int?delta?=?(int)orig_stack?-?(int)mm_msg.BUF;??
??
????int?argc?=?0;??
????if?(orig_stack_len)?{???/*?has?args?*/??
????????char?**q?=?(char**)stackcopy;??
????????for?(;?*q?!=?0;?q++,argc++)??
????????????*q?+=?delta;??
????}??
??
????phys_copy((void*)va2la(src,?orig_stack),??
??????????(void*)va2la(TASK_MM,?stackcopy),??
??????????orig_stack_len);??
??
????proc_table[src].regs.ecx?=?argc;?/*?argc?*/??
????proc_table[src].regs.eax?=?(u32)orig_stack;?/*?argv?*/??
??
????/*?setup?eip?&?esp?*/??
????proc_table[src].regs.eip?=?elf_hdr->e_entry;?/*?@see?_start.asm?*/??
????proc_table[src].regs.esp?=?PROC_IMAGE_SIZE_DEFAULT?-?PROC_ORIGIN_STACK;??
??
????strcpy(proc_table[src].name,?pathname);??
??
????return?0;??
}??

???execv()

execv接收两个参数：要执行的文件路径和一个字符串数组，其中包含传递给新程序的参数。在您的代码中，execv 通过以下步骤实现：

1.复制参数到一个栈 (arg_stack):

（1）argv中的每个字符串都被复制到一个临时的栈arg_stack中。

（2）每个字符串的指针（在arg_stack中的位置）也被存储在arg_stack中。

2.构造MESSAGE结构:

（1）这个结构用于与内存管理模块（MM）进行通信，告知它要执行新的程序。

（2）消息包含了程序路径、路径长度、参数栈的地址和参数栈的长度。

3.发送消息给MM:

（1）通过send_recv调用，将消息发送给MM任务。

（2）assert确保调用成功。

??do_exec()

它处理从execv发来的执行请求。步骤如下：

1.获取并验证程序路径:

从消息中复制程序路径，并检查路径的合法性。

2.获取程序文件的大小并读取内容:

（1）使用 stat 系统调用获取文件大小。

（2）读取文件内容到mmbuf，这是一个临时缓冲区。

3.解析 ELF 格式的可执行文件:

（1）ELF (Executable and Linkable Format) 是一种常见的二进制文件格式。

（2）解析ELF头部，加载程序段到目标进程的地址空间。

4.设置参数栈:

将参数从execv发送的消息中复制到目标进程的栈空间。

5.设置新的指令指针 (eip) 和栈指针 (esp):

这些寄存器被设置为新程序的入口点和新栈的顶部。

6.更改进程名:

进程表中的名称被更新为新程序的路径。

总之，execv函数负责准备执行新程序所需的所有信息，并将其发送给内存管理模块。MM任务接收这些信息，加载新程序到内存，并更新进程表以反映这些更改。

需要注意的是，execv将arg_stack[]的首地址以及其中有效内容的长度等通过消息发送给了MM。

2.4 修改shell支持多任务执行?

了解了上述基础知识后，我们就可以开始修改shell以实现支持多任务运行，我们采取的方法是令父进程fork出多个子进程，然后子进程去执行那些命令。?

?我们首先定义两个变量MAX_SHELL_PROC和MAX_SHELL_PROC_STACK，分别表示同时可执行的最多指令条数和一次输入的最大长度。

#define?MAX_SHELL_PROC?5?//最多指令条数?echo?pwd?ls?cat?cp?touch?rm???
#define?MAX_SHELL_PROC_STACK?128?//一次输入的最大长度

shabby_shell函数代码的前半部分不做修改，和源码是一样的，我们用0标志一条命令的结束。我们用&指令分割不同命令后，argv数组的内容可能是这样的：?

argv?=?{test,?&,?ls,?&,?echo,?dp'os,?dp.txt,?&,?ls, &, cat, dp.txt}

?利用 multi_argv 保存二维字符串数组，对命令进行处理后，它的内容可能是这样的：

multi_argv?=?{{test,?0},??
????????????{ls,?0},??
????????????{echo,?dp'os,?dp.txt,?0},??
????????????{ls,?0},??
????????????{cat,?dp.txt,?0}??
????????????}??

定义int类型变量num_proc表示有多少个命令，sec_count的作用与上面argc的作用类似。定义字符串数组multi_argv。error标记命令是否出错，初始值赋为0。?

char*?multi_argv[MAX_SHELL_PROC][MAX_SHELL_PROC_STACK];??//multi_argv保存二维字符串数组??
????????int?num_proc?=?1;?//?表示有多少个命令??
????????int?sec_count?=?0;?//?和上面argc的作用类似??
????????int?error?=?0;?//?标记命令是否出错??

接着使用for循环顺序扫描argv数组。如果argv[i]处遇到的不是&，则把字符串放入multi_argv[num_proc?- 1][sec_count++]，否则，用0标记该命令结束，并将表示任务数量的变量num_proc加一，最后将sec_count重新置为0。?

?如果任务数量大于定义中的最大任务数MAX_SHELL_PROC，我们将error置为1。

int?i;??
for?(i?=?0;?i?<?argc;?i++)??
{??
????if?(strcmp(argv[i],"&"))??
????{??
????????multi_argv[num_proc?-?1][sec_count++]?=?argv[i];??
????}?else?{??
????????multi_argv[num_proc?-?1][sec_count]?=?0;??
????????num_proc++;??
????????sec_count?=?0;??
????????if?(num_proc?>?MAX_SHELL_PROC)??
????????{??
????????????error?=?1;??
????????????printf("Too?many?commands!\n");??
????????}?????
????}??
}??

下面的代码只有在error为0，即没有错误时才会执行，出错则直接跳过。父进程fork出子进程后，父子进程均还在循环中，所以进行判断：如果当前进程是父进程，则执行wait()，是子进程，则调用execv执行。?

if?(!error)??
{??
????for?(i?=?0;?i?<?num_proc;?i++)??
????{??
????????int?fd?=?open(multi_argv[i][0],?O_RDWR);??
????????if?(fd?==?-1)?{??
????????????if?(rdbuf[0])?{??
????????????????write(1,?"{",?1);??
????????????????write(1,?rdbuf,?r);??
????????????????write(1,?"}\n",?2);??
????????????}??
????????}??
????????else?{??
????????????close(fd);??
????????????int?pid?=?fork();??
????????????if?(pid?!=?0)?{?/*?parent?*/??
????????????????int?s;??
????????????????wait(&s);??
????????????}??
????????????else?{??/*?child?*/??
????????????????execv(multi_argv[i][0],?multi_argv[i]);??
????????????}??
????????}??
????}??
}??

至此对shell的一个最基本的改造就完成了。我们首先将这段新修改的代码放入kernel/main.c中，并编译连接，查看一下执行效果。?

?我们用之前在任务二中实现的算法指令进行测试，结果如下图。可以看到，改

造后的shell已经可以实现多任务的执行了。

?3. 本部分小结

?在本部分实验中，我们实现了对shell的改造，使它可以在同一个shell中支持多任务并行。我们首先对同时可执行的指令条数和一次输入的最大长度进行限制，然后修改源码中的shabby_shell函数，用"&"符号分割不同的指令，并定义multi_argv保存二维字符串数组。在for循环中顺序扫描argv数组对输入的指令字符串进行处理，然后父进程fork出所有的子进程以实现多任务的执行。