武汉大学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, "}
", 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!
");
}
}
}
下面的代码只有在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, "}
", 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出所有的子进程以实现多任务的执行。