uCoreOs lab4 实验报告

实验目的

• 了解内核线程创建/执行的管理过程
• 了解内核线程的切换和基本调度过程

实验内容

练习0：填写已有实验

本实验依赖实验1/2/3。请把你做的实验1/2/3的代码填入本实验中代码中有“LAB1”,“LAB2”,“LAB3”的注释相应部分。

相对与实验三，实验四中主要改动如下：
kern/process/ （新增进程管理相关文件）
proc.[ch]：新增：实现进程、线程相关功能，包括：创建进程/线程，初始化进程/线程，处理进程/线程退出等功能
entry.S：新增：内核线程入口函数kernel_thread_entry的实现
switch.S：新增：上下文切换，利用堆栈保存、恢复进程上下文
kern/init/
init.c：修改：完成进程系统初始化，并在内核初始化后切入idle进程
kern/mm/ （基本上与本次实验没有太直接的联系，了解kmalloc和kfree如何使用即可）
kmalloc.[ch]：新增：定义和实现了新的kmalloc/kfree函数。具体实现是基于slab分配的简化算法 （只要求会调用这两个函数即可）
memlayout.h：增加slab物理内存分配相关的定义与宏 （可不用理会）。
pmm.[ch]：修改：在pmm.c中添加了调用kmalloc_init函数,取消了老的kmalloc/kfree的实现；在pmm.h中取消了老的kmalloc/kfree的定义
swap.c：修改：取消了用于check的Line 185的执行
vmm.c：修改：调用新的kmalloc/kfree
kern/trap/
trapentry.S：增加了汇编写的函数forkrets，用于do_fork调用的返回处理。
kern/schedule/
sched.[ch]：新增：实现FIFO策略的进程调度
kern/libs
rb_tree.[ch]：新增：实现红黑树，被slab分配的简化算法使用（可不用理会）

将实验3的kdebug.c、trap.c、default_pmm.c、pmm.c、vmm.c、swap_fifo.c进行相应补充即可，并注意并非所有的不同都要替换掉，要根据上述改动考虑是否改动

练习1：分配并初始化一个进程控制块

alloc_proc函数（位于kern/process/proc.c中）负责分配并返回一个新的struct proc_struct结构，用于存储新建立的内核线程的管理信息。ucore需要对这个结构进行最基本的初始化，你需要完成这个初始化过程。

【提示】在alloc_proc函数的实现中，需要初始化的proc_struct结构中的成员变量至少包括: state/pid/runs/kstack/need_resched/parent/mm/context/tf/cr3/flags/name。

请在实验报告中简要说明你的设计实现过程。请回答如下问题：

• 请说明proc_struct中struct context context和struct trapframe *tf成员变量含义和在本实验中的作用是啥？（提示通过看代码和编程调试可以判断出来）

实验过程

所需要填写的代码

// alloc_proc - alloc a proc_struct and init all fields of proc_struct
static struct proc_struct *
alloc_proc(void) {
    struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
    if (proc != NULL) {
    //LAB4:EXERCISE1 YOUR CODE
    /*
     * below fields in proc_struct need to be initialized
     *       enum proc_state state;                      // Process state
     *       int pid;                                    // Process ID
     *       int runs;                                   // the running times of Proces
     *       uintptr_t kstack;                           // Process kernel stack
     *       volatile bool need_resched;                 // bool value: need to be rescheduled to release CPU?
     *       struct proc_struct *parent;                 // the parent process
     *       struct mm_struct *mm;                       // Process's memory management field
     *       struct context context;                     // Switch here to run process
     *       struct trapframe *tf;                       // Trap frame for current interrupt
     *       uintptr_t cr3;                              // CR3 register: the base addr of Page Directroy Table(PDT)
     *       uint32_t flags;                             // Process flag
     *       char name[PROC_NAME_LEN + 1];               // Process name
     */
    }
    return proc;
}

查看proc.h各元素的定义说明

#ifndef __KERN_PROCESS_PROC_H__
#define __KERN_PROCESS_PROC_H__

#include <defs.h>
#include <list.h>
#include <trap.h>
#include <memlayout.h>


// process's state in his life cycle
enum proc_state {
    PROC_UNINIT = 0,  // uninitialized //未初始状态  
    PROC_SLEEPING,    // sleeping //睡眠（阻塞）状态
    PROC_RUNNABLE,    // runnable(maybe running) //运行与就绪态  
    PROC_ZOMBIE,      // almost dead, and wait parent proc to reclaim his resource //僵尸状态 
};

// Saved registers for kernel context switches.
// Don't need to save all the %fs etc. segment registers,
// because they are constant across kernel contexts.
// Save all the regular registers so we don't need to care
// which are caller save, but not the return register %eax.
// (Not saving %eax just simplifies the switching code.)
// The layout of context must match code in switch.S.
struct context {
    uint32_t eip;
    uint32_t esp;
    uint32_t ebx;
    uint32_t ecx;
    uint32_t edx;
    uint32_t esi;
    uint32_t edi;
    uint32_t ebp;
};

#define PROC_NAME_LEN               15
#define MAX_PROCESS                 4096
#define MAX_PID                     (MAX_PROCESS * 2)

extern list_entry_t proc_list;

#define le2proc(le, member)         \
    to_struct((le), struct proc_struct, member)

extern struct proc_struct *idleproc, *initproc, *current;

void proc_init(void);
void proc_run(struct proc_struct *proc);
int kernel_thread(int (*fn)(void *), void *arg, uint32_t clone_flags);

char *set_proc_name(struct proc_struct *proc, const char *name);
char *get_proc_name(struct proc_struct *proc);
void cpu_idle(void) __attribute__((noreturn));

struct proc_struct *find_proc(int pid);
int do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf);
int do_exit(int error_code);

#endif /* !__KERN_PROCESS_PROC_H__ */

根据注释初始化进程结构体proc各元素即可

// alloc_proc - alloc a proc_struct and init all fields of proc_struct
static struct proc_struct *
alloc_proc(void) {
    struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
    if (proc != NULL) {
    //LAB4:EXERCISE1 YOUR CODE
        proc->state = PROC_UNINIT; // 进程状态 设置了进程的状态为“初始”态 这表示进程已经 “出生”了
        proc->pid = -1; // 进程ID 设置进程pid的未初始化值 这表示进程的“身份证号”还没有办好
        proc->runs = 0; // 刚刚初始化的进程 运行时间一定为零 
        proc->kstack = 0; // 为该进程分配的地址为0 因为还没有执行 也没有被重定位 因为默认地址都是从0开始的
        proc->need_resched = NULL; // 刚刚分配出来的进程 还未进入CPU 进程不能被调度
        proc->parent = NULL; // 父进程
        proc->mm = NULL; // 进程所用的虚拟内存
        memset(&(proc->context), 0, sizeof(struct context)); // 进程的上下文
        proc->tf = NULL; // 中断帧指针置空
        proc->cr3 = boot_cr3; // 页目录表地址 设为 内核页目录表基址 由于该内核线程在内核中运行
        proc->flags = 0; // 标志位
        memset(&(proc->name), 0, PROC_NAME_LEN); // 初始化进程名称为空
    }
    return proc;
}

回答问题

请说明proc_struct中struct context context和struct trapframe *tf成员变量含义和在本实验中的作用是啥？（提示通过看代码和编程调试可以判断出来）

context对x86系统而言，进程/线程上下文就是CPU内部的一堆寄存器的信息。
其定义在kern/process/proc.h中：

struct context {
    uint32_t eip;
    uint32_t esp;
    uint32_t ebx;
    uint32_t ecx;
    uint32_t edx;
    uint32_t esi;
    uint32_t edi;
    uint32_t ebp;
};

trapframe *tf 用于保存前一个被（中断或异常）打断的进程的状态信息。
其定义在kern/trap/trap.h中：

struct trapframe {
    struct pushregs tf_regs;
    uint16_t tf_gs;
    uint16_t tf_padding0;
    uint16_t tf_fs;
    uint16_t tf_padding1;
    uint16_t tf_es;
    uint16_t tf_padding2;
    uint16_t tf_ds;
    uint16_t tf_padding3;
    uint32_t tf_trapno;
    /* below here defined by x86 hardware */
    uint32_t tf_err;
    uintptr_t tf_eip;
    uint16_t tf_cs;
    uint16_t tf_padding4;
    uint32_t tf_eflags;
    /* below here only when crossing rings, such as from user to kernel */
    uintptr_t tf_esp;
    uint16_t tf_ss;
    uint16_t tf_padding5;
} __attribute__((packed));

练习2：为新创建的内核线程分配资源

创建一个内核线程需要分配和设置好很多资源。kernel_thread函数通过调用do_fork函数完成具体内核线程的创建工作。do_kernel函数会调用alloc_proc函数来分配并初始化一个进程控制块，但alloc_proc只是找到了一小块内存用以记录进程的必要信息，并没有实际分配这些资源。ucore一般通过do_fork实际创建新的内核线程。do_fork的作用是，创建当前内核线程的一个副本，它们的执行上下文、代码、数据都一样，但是存储位置不同。在这个过程中，需要给新内核线程分配资源，并且复制原进程的状态。你需要完成在kern/process/proc.c中的do_fork函数中的处理过程。它的大致执行步骤包括：

• 调用alloc_proc，首先获得一块用户信息块。
• 为进程分配一个内核栈。
• 复制原进程的内存管理信息到新进程（但内核线程不必做此事）
• 复制原进程上下文到新进程
• 将新进程添加到进程列表
• 唤醒新进程
• 返回新进程号

请在实验报告中简要说明你的设计实现过程。请回答如下问题：

• 请说明ucore是否做到给每个新fork的线程一个唯一的id？请说明你的分析和理由。

实验过程

查看proc.c

/* do_fork -     parent process for a new child process
 * @clone_flags: used to guide how to clone the child process
 * @stack:       the parent's user stack pointer. if stack==0, It means to fork a kernel thread.
 * @tf:          the trapframe info, which will be copied to child process's proc->tf
 */
int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
    int ret = -E_NO_FREE_PROC;
    struct proc_struct *proc;
    if (nr_process >= MAX_PROCESS) {
        goto fork_out;
    }
    ret = -E_NO_MEM;
    //LAB4:EXERCISE2 YOUR CODE
    /*
     * Some Useful MACROs, Functions and DEFINEs, you can use them in below implementation.
     * MACROs or Functions:
     *   alloc_proc:   create a proc struct and init fields (lab4:exercise1)
     *   setup_kstack: alloc pages with size KSTACKPAGE as process kernel stack
     *   copy_mm:      process "proc" duplicate OR share process "current"'s mm according clone_flags
     *                 if clone_flags & CLONE_VM, then "share" ; else "duplicate"
     *   copy_thread:  setup the trapframe on the  process's kernel stack top and
     *                 setup the kernel entry point and stack of process
     *   hash_proc:    add proc into proc hash_list
     *   get_pid:      alloc a unique pid for process
     *   wakup_proc:   set proc->state = PROC_RUNNABLE
     * VARIABLES:
     *   proc_list:    the process set's list
     *   nr_process:   the number of process set
     */

    //    1. call alloc_proc to allocate a proc_struct
    //    2. call setup_kstack to allocate a kernel stack for child process
    //    3. call copy_mm to dup OR share mm according clone_flag
    //    4. call copy_thread to setup tf & context in proc_struct
    //    5. insert proc_struct into hash_list && proc_list
    //    6. call wakup_proc to make the new child process RUNNABLE
    //    7. set ret vaule using child proc's pid
fork_out:
    return ret;

bad_fork_cleanup_kstack:
    put_kstack(proc);
bad_fork_cleanup_proc:
    kfree(proc);
    goto fork_out;
}

根据提示写出代码有

/* do_fork -     parent process for a new child process
 * @clone_flags: used to guide how to clone the child process
 * @stack:       the parent's user stack pointer. if stack==0, It means to fork a kernel thread.
 * @tf:          the trapframe info, which will be copied to child process's proc->tf
 */
int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
    int ret = -E_NO_FREE_PROC; //尝试为进程分配内存
    struct proc_struct *proc;//定义新进程
    if (nr_process >= MAX_PROCESS) {//分配进程数大于4096,返回
        goto fork_out;//返回
    }
    ret = -E_NO_MEM; //因内存不足而分配失败
    
    //    1. call alloc_proc to allocate a proc_struct
    proc = alloc_proc();
    if (!proc) {//申请内存块失败
        goto fork_out;//返回
    }
    proc->parent = current;//设置父进程名字
    //    2. call setup_kstack to allocate a kernel stack for child process
    if (setup_kstack(proc) ! = 0) {//分配内核栈
        goto bad_fork_cleanup_proc;//返回
    }
    //    3. call copy_mm to dup OR share mm according clone_flag
    if (copy_mm(clone_flags, proc) != 0) {//复制父进程的内存信息到子进程
        goto bad_fork_cleanup_kstack;//返回
    }
    //    4. call copy_thread to setup tf & context in proc_struct
    copy_thread(proc, stack, tf);//复制父进程的中断帧和上下文信息
    //    5. insert proc_struct into hash_list && proc_list
    bool intr_flag;
    local_intr_save(intr_flag); //屏蔽中断 intr_flag置为1
    proc->pid = get_pid();//获取当前进程PID
    list_add(&proc_list, &proc->list_link);//加入进程链表
    hash_proc(proc);//将新进程添加到进程的（hash）列表中
    ++nr_process;//进程数加1
    local_intr_restore(intr_flag);//恢复中断
    //    6. call wakeup_proc to make the new child process RUNNABLE
    wakeup_proc(proc);//唤醒子进程
    //    7. set ret vaule using child proc's pid
    ret = proc->pid;//返回子进程的pid
    
fork_out://已分配进程数大于4096
    return ret;

bad_fork_cleanup_kstack://分配内核栈失败
    put_kstack(proc);
bad_fork_cleanup_proc:
    kfree(proc);
    goto fork_out;
}

回答问题

请说明ucore是否做到给每个新fork的线程一个唯一的id？请说明你的分析和理由。

查看get_pid函数，了解PID的生成方法

// get_pid - alloc a unique pid for process
static int
get_pid(void) {
    static_assert(MAX_PID > MAX_PROCESS);
    struct proc_struct *proc;
    list_entry_t *list = &proc_list, *le;
    static int next_safe = MAX_PID, last_pid = MAX_PID;
    if (++ last_pid >= MAX_PID) {
        last_pid = 1;
        goto inside;
    }
    if (last_pid >= next_safe) {
    inside:
        next_safe = MAX_PID;
    repeat:
        le = list;
        while ((le = list_next(le)) != list) {
            proc = le2proc(le, list_link);
            if (proc->pid == last_pid) {
                if (++ last_pid >= next_safe) {
                    if (last_pid >= MAX_PID) {
                        last_pid = 1;
                    }
                    next_safe = MAX_PID;
                    goto repeat;
                }
            }
            else if (proc->pid > last_pid && next_safe > proc->pid) {
                next_safe = proc->pid;
            }
        }
    }
    return last_pid;
}

从上可知

• 在该函数中使用了两个变量next_dafe和last_pid，在初次进入函数时，若next_safe > last_pid + 1，(last_pid，next_safe)的区间取值均是合法pid，如果满足条件，可直接返回last_pid + 1作为新的pid

• 否则，进入循环，在循环之中首先通过if (proc->pid == last_pid)这一分支确保了不存在任何进程的pid与last_pid重合，然后再通过if (proc->pid > last_pid && next_safe > proc->pid)这一判断语句保证了不存在任何已经存在的pid满足：last_pid<pid<next_safe，这样就确保了最后能够找到这么一个满足条件的区间，获得合法的pid；

• 之所以在该函数中使用了如此曲折的方法，维护一个合法的pid的区间，是为了优化时间效率，如果简单的暴力的话，每次需要枚举所有的pid，并且遍历所有的线程，这就使得时间代价过大，并且不同的调用get_pid函数的时候不能利用到先前调用这个函数的中间结果

因此可以给每个新fork的线程一个唯一的id

练习3：阅读代码，理解 proc_run 函数和它调用的函数如何完成进程切换的。

请在实验报告中简要说明你对proc_run函数的分析。并回答如下问题：

• 在本实验的执行过程中，创建且运行了几个内核线程？
• 语句local_intr_save(intr_flag);....local_intr_restore(intr_flag);在这里有何作用?请说明理由

实验过程

查看proc_run函数

// proc_run - make process "proc" running on cpu
// NOTE: before call switch_to, should load  base addr of "proc"'s new PDT
void
proc_run(struct proc_struct *proc) {
    if (proc != current) { // 判断需要运行的线程是否已经运行着了
        bool intr_flag;
        struct proc_struct *prev = current, *next = proc;
        local_intr_save(intr_flag); //屏蔽中断 intr_flag置为1
        {
            current = proc; 
            load_esp0(next->kstack + KSTACKSIZE); // 设置TSS
            lcr3(next->cr3); // 修改当前的cr3寄存器成需要运行线程（进程）的页目录表
            switch_to(&(prev->context), &(next->context)); // 切换到新的线程
        }
        local_intr_restore(intr_flag);//恢复中断
    }
}

1、让 current指向 next内核线程initproc；

2、设置任务状态ts中特权态0下的栈顶指针esp0 为 next 内核线程 initproc 的内核栈的栈顶，即 next->kstack + KSTACKSIZE ；

3、设置 CR3 寄存器的值为 next 内核线程 initproc 的页目录表起始地址 next->cr3，这实际上是完成进程间的页表切换；

4、由 switch_to函数完成具体的两个线程的执行现场切换，即切换各个寄存器，当 switch_to 函数执行完“ret”指令后，就切换到initproc执行了。

运行代码，输入make qemu

回答问题

在本实验的执行过程中，创建且运行了几个内核线程？

查看proc_init函数

// proc_init - set up the first kernel thread idleproc "idle" by itself and
//           - create the second kernel thread init_main
void
proc_init(void) {
    int i;

    list_init(&proc_list);
    for (i = 0; i < HASH_LIST_SIZE; i ++) {
        list_init(hash_list + i);
    }

    if ((idleproc = alloc_proc()) == NULL) {
        panic("cannot alloc idleproc.\n");
    }

    idleproc->pid = 0;
    idleproc->state = PROC_RUNNABLE;
    idleproc->kstack = (uintptr_t)bootstack;
    idleproc->need_resched = 1;
    set_proc_name(idleproc, "idle");
    nr_process ++;

    current = idleproc;

    int pid = kernel_thread(init_main, "Hello world!!", 0);
    if (pid <= 0) {
        panic("create init_main failed.\n");
    }

    initproc = find_proc(pid);
    set_proc_name(initproc, "init");

    assert(idleproc != NULL && idleproc->pid == 0);
    assert(initproc != NULL && initproc->pid == 1);
}

从代码可知，有

• idle_proc，为第 0 个内核线程，在完成新的内核线程的创建以及各种初始化工作之后，进入死循环，用于调度其他进程或线程；
• init_proc，被创建用于打印 “Hello World” 的线程。本次实验的内核线程，只用来打印字符串。

语句local_intr_save(intr_flag);....local_intr_restore(intr_flag);在这里有何作用?请说明理由

在进行进程切换的时候，需要避免出现中断干扰这个过程，所以需要在上下文切换期间清除 IF 位屏蔽中断，并且在进程恢复执行后恢复 IF 位。

• 该语句是屏蔽中断操作，使得在这个语句块内的内容不会被其他中断打断，是一个原子操作
• 这就使得某些关键的代码不会被打断，从而不会一起不必要的错误
• 例如在 proc_run 函数中，将 current 指向了要切换到的线程，但是此时还未真正将控制权转移过去，若此时出现其他中断打断这些操作，便会出现 current 中保存的并不是正在运行的线程的中断控制块，从而出现错误

实验总结

​ 本次实验是关于内核线程的相关实验，实验涉及进程控制块的设计、内核线程分配问题，任务量较小，但是分析代码仍然是一件令人头疼的事情，get_pid函数中用到的多个跳转和循环使得代码难以理解。对于实验中出现的各种错误，还是得耐心debug…