北航操作系统实验Lab3进程与异常

实验目的

  1. 创建一个进程并成功运行

    • 进程控制块数据结构(Env)的初始化与管理
    • 进程控制块创建(生成envid、进程地址空间建立)
    • 加载进程代码和数据
  2. 实现时钟中断,通过时钟中断内核可以再次获得执行权
  3. 实现进程调度,创建两个进程,并且通过时钟中断切换进程执行

​ 在本次实验中你将运行一个用户模式的进程。你需要使用数据结构进程控制块 Env来跟踪用户进程。通过建立一个简单的用户进程,加载一个程序镜像到进程控制块中,并让它运行起来。同时,你的 MIPS 内核将拥有处理异常的能力。

进程

进程控制块PCB

env.h 中定义了Env结构体,即是进程控制块PCB

struct Env {
    struct Trapframe env_tf;        // 用于在异常发生时保存上下文环境(一些寄存器的值)
    LIST_ENTRY(Env) env_link;       // 空闲进程链表指针
    u_int env_id;                   // 进程唯一标识符(进程id)
    u_int env_parent_id;            // 父进程id
    u_int env_status;               // 进程的状态
    Pde  *env_pgdir;                // 该进程页目录的内核虚拟地址
    u_int env_cr3;                    // 该进程页目录的物理地址
    LIST_ENTRY(Env) env_sched_link; // 待调度进程链表指针
    u_int env_pri;                    // 进程的优先级
};

进程状态env_status有三种状态:

  • ENV_FREE : 表明该进程是不活动的,即该进程控制块处于进程空闲链表中。
  • ENV_NOT_RUNNABLE : 表明该进程处于阻塞状态,处于该状态的进程往往在等待一定的条件才可以变为就绪状态从而被 CPU 调度。
  • ENV_RUNNABLE : 表明该进程处于就绪状态,正在等待被调度(可能正处于调度队列中),但处于RUNNABLE 状态的进程可以是正在运行的,也可能不在运行中。

Trapframe 结构体

trap.h 中定义了Trapframe 结构体,它是用于发生异常时保存现场的。

struct Trapframe { //lr:need to be modified(reference to linux pt_regs) TODO
    unsigned long regs[32];     // 32 个通用寄存器

    /* 特殊寄存器 */
    unsigned long cp0_status;     // CP0 状态寄存器
    unsigned long hi;            // 乘(除)法高位(模)寄存器
    unsigned long lo;            // 乘(除)法低位(商)寄存器
    unsigned long cp0_badvaddr;    // 异常发生地址
    unsigned long cp0_cause;    // CP0 cause 寄存器
    unsigned long cp0_epc;        // 异常返回地址
    unsigned long pc;            // PC计数器,程序运行的地址
};

Exercise 3.1、3.2

Exercise 3.1

首先要为进程控制块数组envs分配内存, 存放进程控制块的物理内存在系统启动后就要被分配好 。

pmap.c/mips_vm_init 函数用于完成这个任务, 为envs数组分配空间(alloc函数) ,同时建立了映射(boot_map_segment函数), envs数组应该被UENVS区域映射。

envs = (struct Env *)alloc(NENV * sizeof(struct Env), BY2PG, 1);
n = ROUND(NENV * sizeof(struct Env), BY2PG);
boot_map_segment(pgdir, UENVS, n, PADDR(envs), PTE_R);

Exercise 3.2

分配完空间之后,我们还需要对该数组进行管理,就像Lab2实验中对pages数组管理一样,对于处于空闲状态的env控制块按照链表的形式"串"起来。env_free_list 就是用于管理空闲env的链表。

为了实现链表的表头是envs[0], 把env控制块逆序插入链表即可。

  • env_init函数
void env_init(void){
    int i;
    /*Step 1: Initial env_free_list. */
    LIST_INIT(&env_free_list);
    LIST_INIT(env_sched_list); //这里顺便把用于进程调度的链表也初始化一下
    LIST_INIT(env_sched_list + 1);
    /*Step 2: 逆序插入 */
    for(i = NENV - 1; i >= 0; -- i)
    {
        envs[i].env_status = ENV_FREE; // initial status as free
        LIST_INSERT_HEAD((&env_free_list), (envs + i), env_link);
    }
}

进程的创建

Exercise 3.3

struct Env中的env_id这个域,它就是每个进程独一无二的标识符。

env.c/mkenvid函数

该函数为每个进程生成一个新的进程id, 该函数的巧妙之处在于每个进程id都能对应着一个进程。我们在Exercise3.1中申请了1024个env控制块,一个env控制块就是一个进程。mkenvid函数生成的env_id的低11位用于识别是哪一个env控制块(10位应该就够了,多加一位可能是为了保险?反正第11位始终是0)。

env.c/envid2env 函数

该函数就是通过一个env的env_id获取该env_id对应的进程控制块。也即是取出env_id的低10位作为索引(使用了ENVX宏用于取出低10位)。当envid是0时,该函数返回当前进程,这个会在后面的实验中用到。

还有一个就是checkperm选项, 提示中说到,如果checkperm设为1,就要进行检查:如果checkperm为1,e要么是当前进程,要么是当前进程的子进程

int envid2env(u_int envid, struct Env **penv, int checkperm)
{
    struct Env *e;
    /* Hint:
 *      *  If envid is zero, return the current environment.*/
    /*Step 1: Assign value to e using envid. */
    if(envid == 0) {
        *penv = curenv;
        return 0;
    }
    /*取出低10位作为索引,去索引envs数组,得到该envid对应的env*/
    e = &envs[ENVX(envid)]; 
    /*由于会有多个envid对应同一个进程,这里还要进行判断env_id是否相等*/
    if (e->env_status == ENV_FREE || e->env_id != envid) {
            *penv = 0;
            return -E_BAD_ENV;
    }
    /* Hint:
 *      *  Check that the calling environment has legitimate permissions
 *           *  to manipulate the specified environment.
 *                *  If checkperm is set, the specified environment
 *                     *  must be either the current environment.
 *                          *  or an immediate child of the current environment.If not, error! */
    /*Step 2: Make a check according to checkperm. */
    /* 如果checkperm为1,e要么是当前进程,要么是当前进程的子进程 */
    if(checkperm == 1 && e != curenv && curenv->env_id != e->env_parent_id) {
        *penv = 0;
        return -E_BAD_ENV;
    }

    *penv = e;
    return 0;
}

进程创建流程

进程创建的流程如下:

  • 第一步 申请一个空闲的 PCB,从 env_free_list 中索取一个空闲 PCB 块,这时候的 PCB 就像张白纸一样。
  • 第二步 “纯手工打造”打造一个进程。在这种创建方式下,由于没有模板进程, 所以进程拥有的所有信息都是手工设置的。而进程的信息又都存放于进程控制块中,所以我们需要手工初始化进程控制块。
  • 第三步 进程光有 PCB 的信息还没法跑起来,每个进程都有独立的地址空间。所以,我们要为新进程分配资源,为新进程的程序和数据以及用户栈分配必要的内存空间。
  • 第四步 此时 PCB 已经被涂涂画画了很多东西,不再是一张白纸,把它从空闲链表里除名, 就可以投入使用了。

## Exercise 3.4

首先要完成env.c/env_alloc 函数,该函数作用就是分配一个空闲PCB, 并进行初始化。

env_alloc 函数执行的过程中需要调用env_setup_vm函数,该函数功能是初始化新进程地址空间。也即是初始化该进程的页目录

在我们的实验系统中的地址空间中,用户态和内核态各占2G。虚拟地址ULIM以上的2G空间是内核空间,由内核管理。用户态进程可以通过系统调用变成内核态进程。内核态的2G虚拟空间对于所有进程来说都是一样的, 每个进程都会有2G内核态的虚拟地址,以便临时变身为“内核”行使大权 。每个进程所不一样的只是各自用户态的2G空间。因此我们在对进程的的地址空间进行初始化的过程中,ULIM地址以上的页目录项可以完全照搬内核页目录。但是在代码提示中确告诉我们UTOP之前的页目录项清空,UTOP之后的除了UVPT VPT都照搬内核页目录。

这里有必要说明一下UTOPULIM之间的区域,来谈一下我自己的理解。这是在Lab2实验中没理解的地方。

UTOPULIM 的空间分成了3个区域, 分别是UENVSUPAGESUVPT ,分别映射到了进程控制块数组envs、 用于管理物理页的pages数组、当前进程的页表。前两个是在mips_vm_init函数中完成映射的。后一个是在env_setup_vm函数中映射。由于映射,可以认为这三个空间分别存储了其映射的内容。以便用户态进程通过访问这些区域来访问对应的内容。例如, UVPT就是进程的页表区,通过访问UVPT这块地址,就能获得进程的页表项。访问UENVS这块地址就能获得其他进程的信息。用户态进程想要直接访问需要进行系统调用来陷入内核态, 比较麻烦,而用户进程通过读取这几段地址空间就能获得相应的信息,避免了系统调用,可以认为更加方便的提供了一个接口。UTOPULIM这段空间只能读不能写。因此在照搬页目录的时候,除了每个进程各自的页表不同之外,另外两个区域对于每个进程来说都相同,也要照搬过来。

static int
env_setup_vm(struct Env *e)
{
    int i, r;
    struct Page *p = NULL;
    Pde *pgdir;

    /*Step 1: Allocate a page for the page directory using a function you completed in the lab2.
       * and add its reference.
       * pgdir is the page directory of Env e, assign value for it. */
    if ( (r = page_alloc(&p) ) == -E_NO_MEM) {/* Todo here*/ 
        panic("env_setup_vm - page alloc error\n");
        return r;
    }
    p -> pp_ref ++ ; //引用次数加1
    pgdir = (Pde *)page2kva(p);    //将页面p转化为虚拟地址

    /*Step 2: Zero pgdir's field before UTOP. */
    for(i = 0; i < PDX(UTOP); ++ i) pgdir[i] = 0; // UTOP之前的清零

    /*Step 3: Copy kernel's boot_pgdir to pgdir. */
    /* Hint:
     *  The VA space of all envs is identical above UTOP
     *  (except at VPT and UVPT, which we've set below).
     *  See ./include/mmu.h for layout.
     *  Can you use boot_pgdir as a template?
     */
    for(i = PDX(UTOP); i < 1024; ++ i) pgdir[i] = boot_pgdir[i];    //UTOP之后的照搬过来

    /*Step 4: Set e->env_pgdir and e->env_cr3 accordingly. */
    e ->env_pgdir = pgdir;          // 虚拟地址
    e -> env_cr3 = PADDR(pgdir);    //物理地址

    /*VPT and UVPT map the env's own page table, with
 *      *different permissions. */
    e->env_pgdir[PDX(VPT)]   = e->env_cr3;
    e->env_pgdir[PDX(UVPT)]  = e->env_cr3 | PTE_V | PTE_R;
    return 0;
}

应当注意到这段代码: e->env_pgdir[PDX(UVPT)] = e->env_cr3 | PTE_V | PTE_R;

这段代码完成了UVPT区域的映射,将UVPT对应的的页目录项指向了自身。为什么加了这句话UVPT就变成了进程页表区,也就是说我们能通过访问UPVT来获得某个地址的页表项, 再具体一点 *(UVPT + VPN(va))就是虚拟地址va对应的页表项 。Lab4实验中有用到这个, 我会在Lab4实验报告中解释。

Exercise 3.5

再回到env_alloc函数,来梳理以下函数执行过程。

  • 首先,从空闲PCB链表中取出一个空闲PCB。
  • 调用env_setup_vm函数初始化进程的页目录(pgdirenv_cr3)。
  • 为该进程分配一个envid, 设置父进程id, 并且把进程的状态设为ENV_RUNNABLE
  • 设置相应的寄存器的值。

SR(cp0_status)寄存器和中断异常有关, 第12bit设置为1,表示4号中断可以被响应。不是很理解 :)。同时还需要设置栈指针sp,即29号寄存器。设置为用户栈。

  • env控制块相关信息已经初始化完成,将该PCB从空闲链表中移除。

env_alloc函数并没有把所有信息都初始化,其他信息由其他函数来完成。

int env_alloc(struct Env **new, u_int parent_id)
{
    int r;
    struct Env *e;
    
    /*Step 1: Get a new Env from env_free_list*/
    e = LIST_FIRST(&env_free_list) ;
    if(e == NULL) {
        *new = NULL;
        return - E_NO_FREE_ENV;
    }
    
    /*Step 2: Call certain function(has been implemented) to init kernel memory layout for this new Env.
     *The function mainly maps the kernel address to this new Env address. */
    if( env_setup_vm(e) == -E_NO_MEM){
        *new = NULL;
        return - E_NO_FREE_ENV;
    }
    
    /*Step 3: Initialize every field of new Env with appropriate values*/
    e->env_id = mkenvid(e);
    e->env_parent_id = parent_id;
    e->env_status = ENV_RUNNABLE;
    
    /*Step 4: focus on initializing env_tf structure, located at this new Env. 
     * especially the sp register,CPU status. */
    e->env_tf.cp0_status = 0x10001004;
    e->env_tf.regs[29] = USTACKTOP; //设置栈指针

    /*Step 5: Remove the new Env from Env free list*/
    *new = e;
    LIST_REMOVE((e), env_link);
    return 0;
}

Exercise 3.6

刚刚完成了创建进程中的第一小步,现在已经有了空进程。一个进程是一个程序的一次运行,所以现在就要把程序装进给进程分配的内存空间中。这一任务由 load_icode 函数来完成,它的步骤就是分配内存,并将二进制代码(ELF格式)装入分配好的内存中。

void load_icode(struct Env *e, u_char *binary, u_int size) binary 就是我们需要装载的整个文件(ELF文件), size 是文件的大小。

但是一个函数工作量太大,因此该函数把装入内存的任务交给了kernel_elfloader.c/load_elf 函数。

// binary 为整个待加载的 ELF 文件。size 为该 ELF 文件的大小。
// entry_point 是一个 u_long 变量的地址 (相当于引用),解析出的入口地址会被存入到该位置
int load_elf(u_char *binary, int size, u_long *entry_point, void *user_data,
             int (*map)(u_long va, u_int32_t sgsize,
                        u_char *bin, u_int32_t bin_size, void *user_data));

但是load_elf函数的任务还是有点艰巨,因此load_elf函数只完成ELF结构的解析ELF文件有很多段, 把解析出的每个段交给map函数来完成加载到内存的工作, 这个map函数就是load_icode_mapper 函数。 因此最终将各个segment加载到内存中的工作就是由load_icode_mapper函数完成的。接下来首先要完成这个函数。

  • load_icode_mapper函数
static int load_icode_mapper(u_long va, u_int32_t sgsize, u_char *bin, 
                             u_int32_t bin_size, void *user_data)

要想正确加载一个ELF文件到内存,只需将ELF文件中所有需要加载的segment加载到对应的虚地址上即可, 该虚拟地址就是va。

va(该段需要被加载到的虚地址)、sgsize(该段在内存中的大小)、bin(该段在ELF文件中的内容,即是我们需要加载的段的起始地址)、bin_size(该段在文件中的大小)。 user_data就是当前进程。

为什么一个段会有两个大小 bin_size 和 sgsize ?

这个指导书在lab1里面说过了。是由于.bss段的原因。

Note 1.3.5 MemSiz(即sgsize) 永远大于等于 FileSiz(即bin_size)。若 MemSiz 大于 FileSiz,则操作系统在加载程序的时候,会首先将文件中记录的数据加载到对应的 VirtAddr 处。之后,向内存中填 0, 直到该段在内存中的大小达到 MemSiz 为止。那么为什么 MemSiz有时候会大于 FileSiz 呢?这里举这样一个例子:C 语言中未初始化的全局变量,我们需要为其分配内存,但它又不需要被初始化成特定数据。因此,在可执行文件中也只记录它需要占用内存 (MemSiz),但在文件中却没有相应的数据(因为它并不需要初始化成特定数据)。故而在这种情况下,MemSiz 会大于 FileSiz。这也解释了,为什么 C 语言中全局变量会有默认值 0。这是因为操作系统在加载时将所有未初始化的全局变量所占的内存统一填了 0。

接下来就要考虑完成该函数了。在完成这个函数之前我也是一头雾水,尝试着慢慢去分析。

我们需要将起始地址为bin的段加载到虚拟地址va上,如何把对应的段加载到虚拟地址上? 这个加载是指什么? 具体要怎么去操作?

首先bin是我们要加载的内容,加载就是指把它存放的内存中去,并且存放的位置对应着va。 内容肯定要存放在物理页中,因此我们会申请物理页来存储我们需要加载的内容,即是调用bcopy函数把需要加载的内容复制到物理页中。把内容存放好了之后如何去对应虚拟地址呢?还记得lab2实验中有这样一句话吗?

这个函数非常重要!它将在lab3和lab4中被反复用到,这个函数将va虚拟地址和其要对应的物理页pp的映射关系以perm的权限设置加入页目录。我们大概讲一下函数的执行流程与执行要点。

这个函数就是page_insert函数。该函数就是在当前进程的地址空间中,建立虚拟地址和物理页之间的映射关系。

还有一个最重要的地方就是页面映射对应几种情况了。页面分配都是按照一页4KB大小来分配的。由于va并不一定对齐4KB,文件大小也不一定对齐4KB。在一段内存不满一个页(4KB)的情况下,仍然要分配一整个页来存储。因此需要考虑几种情况,我借用了北航lab3释疑解惑里的一张图片来说明这个不对齐的情况。

1589167199035.png

因此我们需要分3种情况来完成这个过程。第一次处理va - ①,第二次处理 ① - ②, 第三次处理② - ③ 。 由于存在不对齐,使用bcopy函数的时候也要注意只能copy一部分过去。

static int load_icode_mapper(u_long va, u_int32_t sgsize,
                             u_char *bin, u_int32_t bin_size, void *user_data)
{
    /* !!!失败就返回小于0的数 */
    //printf("***********--Start load_icode_mapper()--***********\n");
    struct Env *env = (struct Env *)user_data;
    struct Page *p = NULL;
    u_long i;
    int r;
    u_long offset = va - ROUNDDOWN(va, BY2PG);
    if( bin == NULL ) return - 1;
    u_long size = 0;
    /*Step 1: load all content of bin into memory. */

    /* 第一部分, 不对齐要单独处理*/ 
    if(offset > 0) {
        size = BY2PG - offset; // 需要加载的文件大小
        if( page_alloc(&p) == - E_NO_MEM) return - E_NO_MEM;
        p -> pp_ref ++ ;
        /* 将虚拟地址va与刚申请的物理页建立映射 */
        page_insert(env -> env_pgdir, p, va - offset, PTE_R);
        /* 将bin里的内容复制到刚申请的物理页内存中 */
        bcopy((void *)bin, (void *)(page2kva(p) + offset), MIN(bin_size, size) );
    }

    /*第二部分, 已经对齐了, 就正常处理*/
    for (i = size; i < bin_size; i += BY2PG) {
        /* Hint: You should alloc a page and increase the reference count of it. */
        if( page_alloc(&p) == - E_NO_MEM) return - E_NO_MEM;
        p -> pp_ref ++ ;
        /* 将虚拟地址va + i与刚申请的物理页建立映射 */
        page_insert(env -> env_pgdir, p, va + i, PTE_R) ;
        /* 将bin里的内容复制到刚申请的物理页内存中 */
        /* 这里也有个地方要注意, 就是末尾可能不对齐 */
        bcopy((void * )(bin + i), (void *)page2kva(p), MIN(bin_size - i, BY2PG) ); 
    }
    /*Step 2: alloc pages to reach `sgsize` when `bin_size` < `sgsize`.
    * i has the value of `bin_size` now. */
    /*第三部分, 物理页填充0*/
    while (i < sgsize) {
        if( page_alloc(&p) == - E_NO_MEM) return - E_NO_MEM;
        p -> pp_ref ++ ;
        page_insert(env -> env_pgdir, p, va + i, PTE_R) ;
        /*page_alloc 函数已经调用了清0函数, 这里就不再需要了 */
        i += BY2PG;
    }
    //printf("***********--End load_icode_mapper()--***********\n");
    return 0;
}

Exercise 3.7

load_elf

完成单个段的加载函数后,再回到load_elf函数,来完成整个ELF文件的加载。该函数需要解析出每一段,并把相应段的信息传给map函数。这个函数大部分工作已经完成了,我们只需要完成map函数调用的工作。段的信息存放在 Elf32_Phdr结构体中, 前面已经提到了各个参数的意义。我们需要加载的段的地址,即bin 是什么呢?

Elf32_Off    p_offset;        /* Segment file offset */

这就是该段的偏移量,有了偏移量,地址也就知道了。

if (phdr->p_type == PT_LOAD) {
    r = map(phdr->p_vaddr, phdr->p_memsz, binary + phdr->p_offset, phdr->p_filesz, user_data);
    if(r < 0) return r;
}

load_icode

再回到load_icode 函数,这是真正的加载二进制镜像的函数,该函数执行过程如下:

  • 分配进程的运行栈空间,注意这里是用户栈。为栈空间预分配一个页面。

即是分配一个物理页,然后将用户栈的地址该物理页建立映射。注意栈的增长方向是向下的,因此映射的内存空间是 [USTACKTOP - BY2PG, USTACKTOP)

  • 调用load_elf函数把二进制文件加载到内存。
  • 设置pc寄存器

我们要运行的进程的代码段预先被载入到了 entry_ point 为起点的内存中(也就是进程入口地址),当我们运行进程时,CPU 将自动从 pc 所指的位置开始执行二进制码, 因此将pc设为entry_point

static void load_icode(struct Env *e, u_char *binary, u_int size)
{
    /* Hint:
     *  You must figure out which permissions you'll need
     *  for the different mappings you create.
     *  Remember that the binary image is an a.out format image,
     *  which contains both text and data.
     */
    //printf("***********--Start load_icode()--***********\n");
    struct Page *p = NULL;
    u_long entry_point;
    u_long r;
    u_long perm;

    /*Step 1: alloc a page. */
    if(page_alloc(&p) == - E_NO_MEM ) return ;
    
    /*Step 2: Use appropriate perm to set initial stack for new Env. */
    /*Hint: The user-stack should be writable? */
    perm = PTE_R; // 设置权限, page_insert会加上PTE_V位
    r = page_insert(e->env_pgdir, p, USTACKTOP - BY2PG, perm); // 虚拟地址与物理页建立映射
    if(r == - E_NO_MEM) return ;
    
    /*Step 3:load the binary by using elf loader. */
    r = load_elf(binary, size, &entry_point, e, load_icode_mapper); 
    if(r < 0) return ;
    
    /***Your Question Here***/
    /*Step 4:Set CPU's PC register as appropriate value. */
    e->env_tf.pc = entry_point; //设置pc,进程将从这里开始执行
}

Exercise 3.8

上面几个函数完成之后,创建进程很简单了。 分配一个新的空闲进程控制块,然后设置进程控制块,并将二进制代码载入到对应地址空间即可,同时还要设置相应的优先级。

void env_create(u_char *binary, int size){
     /*Step 1: Use env_create_priority to alloc a new env with priority 1 */
    env_create_priority(binary, size, 1) ;
}
void env_create_priority(u_char *binary, int size, int priority)
{
    struct Env *e;
    /*Step 1: Use env_alloc to alloc a new env. */
    env_alloc(&e, 0);
    /*Step 2: assign priority to the new env. */
    e -> env_pri = priority;
    LIST_INSERT_HEAD(env_sched_list, e, env_sched_link) ;    // 这个是后面进程调度使用的,现在可以不用管
    /*Step 3: Use load_icode() to load the named elf binary. */
    load_icode(e, binary, size);
}

Exercise 3.9

在init.c中调用宏函数创建进程,宏函数会调用上面的函数来创建进程。

ENV_CREATE_PRIORITY(user_A,2);
ENV_CREATE_PRIORITY(user_B,1);

到此,进程的创建就结束了,再来看一下进程创建的过程中函数的调用。

进程创建过程中的函数调用

graph TD
A(env.c/env_create_priority) --> B(env.c/env_alloc)
B --> C(env.c/env_setup_vm)
B --> D(env.c/mkenvid)
C --> E(pmap.c/page_alloc)
A --> F(env.c/load_icode)
F --> E
F --> H(kernel_elfloader.c/loadelf)
H --> I(env.c/load_icode_mapper)
I --> E
I --> G
F --> G(pmap.c/page_insert)
tot[进程创建的函数调用]

Exercise 3.10

这一部分就是实现进程切换了env_run函数。这个函数个人感觉也并不容易。进程的切换可分为两部分:

  • 一部分是保存当前进程上下文 (如果当前没有运行的进程就跳过这一步)
  • 另一部分就是恢复要启动的进程的上下文,然后运行该进程。

Note 3.2.4 进程上下文说来就是一个环境,相对于进程而言,就是进程执行时的环境。具体来说就是各个变量和数据,包括所有的寄存器变量、内存信息等。

保存环境需要

  • 保护进程本身的状态

进程本身的状态已经记录在进程控制块里了,我们无需管它。

  • 进程周围的环境状态

我们能看到env_tf里面都是一些通用寄存器和与CPU状态有关的寄存器,env_tf 的作用就是用于保存上下文(所谓的CPU寄存器)。把进程切换时的环境状态保存到env_tf中,下次再次运行该进程的时候就能通过恢复进程周围的环境,继续执行进程。 我们该如何保存呢?

lab3实验中,进程的切换是通过时钟中断来完成的,产生时钟中断时,进程的上下文环境会被保存到TIMESTACK 区,准确来说是TIMESTACK区下一段大小为sizeof(struct Trapframe)的内存中。当我们保存进程的上下文时,自然也就需要访问该内存来得到发生中断时进程的上下文。(下面时钟中断我会继续解释这个TIMESTACK)

struct Trapframe *old;
old = (struct Trapframe *)(TIMESTACK - sizeof(struct Trapframe));

*old 赋值给env_tf 就达到了保存上下文的目的。

同时还需要设置pc值,我们后面可能再次执行该进程,接着中断的地方继续执行,pc值就指出了应该从哪条指令开始执行 。cp0_epc 是保存异常时的,系统正在执行的指令的地址,因此我们需要将pc值设为cp0_epc,以便再次执行该进程时,能从上一次发生中断的地方继续执行。

现在再回来捋一下env_run函数吧!env_run 的执行流程:

  1. 保存当前进程的上下文信息,设置当前进程上下文中的为合适的值。
  2. 把当前进程curenv切换为需要运行的进程。
  3. 调用 lcontext 函数,设置进程的地址空间(即进程的页目录)。
  4. 调用env_pop_tf函数,恢复现场、异常返回。
void
env_run(struct Env *e)
{
    /*Step 1: save register state of curenv. */
    /* Hint: if there is a environment running,you should do
    *  context switch.You can imitate env_destroy() 's behaviors.*/

    /*保存进程上下文*/
    if(curenv != NULL) {
        /* 把现在CPU状态存起来 
         * 这里的TIMESTACK地址0x82000000, 发生中断时储存寄存器内容的栈
         */
        struct Trapframe *old;
        old = (struct Trapframe *)(TIMESTACK-sizeof(struct Trapframe));
        curenv -> env_tf = *old;
        curenv -> env_tf.pc = curenv -> env_tf.cp0_epc;
        //curenv -> env_status = ENV_NOT_RUNNABLE ; //切换进程不需要设置这个
    }
    
    
    /*Step 2: Set 'curenv' to the new environment. */
    curenv = e;
    curenv -> env_status = ENV_RUNNABLE; //这个好像不需要也行
        
    /*Step 3: Use lcontext() to switch to its address space. */
    lcontext((int)curenv->env_pgdir); //修改mCONTEXT
    
    /*Step 4: Use env_pop_tf() to restore the environment's
     * environment   registers and drop into user mode in the
     * the   environment.
     */
    /* Hint: You should use GET_ENV_ASID there.Think why? */
    env_pop_tf(&(e->env_tf) , GET_ENV_ASID(e->env_id)); //把env_tf存到寄存器里去,即是恢复CPU状态
}

这里lcontext函数就是设置mCONTEXT,把mCONTEXT设为当前进程的页目录。 这个mCONTEXT具体的作用我现在也不清楚。网上说是为tlb中断和page_fault服务的 。

中断与异常

这一步需要填写的代码并不多,但是要学的内容却不少。

异常的产生和返回

先来认识一下异常的产生与返回

每当发生异常的时候,一般来说,处理器会进入一个用于分发异常的程序,这个程序的作用就是检测发生了哪种异常,并调用相应的异常处理程序。

Exercise 3.11

将异常分发代码代码填写到 boot/start.S

/* start.S中异常分发代码 */
.section .text.exc_vec3             // 指定这段代码的地址
NESTED(except_vec3, 0, sp)
    .set noat
    .set noreorder
1:
    mfc0 k1,CP0_CAUSE                // 将CP0_CAUSE 寄存器的值存到 k1 寄存器中
    la k0,exception_handlers         // 将异常分发数组的首地址复制给 k0 寄存器
    andi k1,0x7c                    // 取出bit2-bit6,即是取出异常号ExcCode
    addu k0,k1                        // 获得对应的异常处理程序(类似于数组访问)
                // 现在k0是一个内存地址,这个内存地址中储存的数才是异常处理函数入口的位置
    lw k0,(k0)                        // 这里才真正得到异常处理程序的地址
    NOP
    jr k0                            // 跳转到异常处理函数
    nop
END(except_vec3)
    .set at

异常分发代码进行异常处理过程

  1. 取得异常码,这是区别不同异常的重要标志。
  2. 以得到的异常码作为索引去exception_handlers数组中找到对应的中断处理函数,后文中会有涉及。
  3. 跳转到对应的中断处理函数中,从而响应了异常,并将异常交给了对应的异常处理函数去处理 。

traps.c/trap_init函数里,我们能看到异常向量组就是数组,存储了对应的异常处理函数的地址,根据异常号来决定跳转到什么函数取处理。 与本次实验相关的便是 0 号异常 —— 中断,对应的处理函数为handle_int

Cause Register寄存器。其中保存着CPU中哪一些中断或者异常已经发生。bit2 bit6保存着异常码。 bit8 bit15保存着哪一些中断发生了。

前面说的是异常分发代码,那异常发生时如何跳转到异常分发代码处呢?

.text.exec_vec3段将通过链接器放到特定的位置,在R3000中要求是放到0x80000080地址处,这个地址处存放的是异常处理程序的入口地址。一旦CPU异常发生,就会跳转到该地址进行异常处理。

Exercise 3.12

将该代码添加到tools\scse0_3.lds

. = 0x80000080;
.except_vec3 : {
   *(.text.exc_vec3)
}

我的

时钟中断

gxemul是如何模拟时钟中断的 ?时钟中断的产生与中断处理流程如下:

  • kclock_init函数初始化时钟,该函数主要调用set_timer函数,完成如下操作:

首先向0xb5000100位置写入1,1则表示1秒钟中断1次,如果写入0,表示关闭实时钟。同时触发了4号中断。注意这里的中断号异常号是不一样的概念,我们实验的异常包括中断。

  • 一旦实时钟中断产生,就会触发MIPS中断,从而MIPS将PC指向0x80000080,跳转到异常处理程序,最终会调用handle_ int函数来处理实时钟中断(0号异常)。
  • 在handle_ int判断CP0_CAUSE寄存器是不是对应的4号中断位引发的中断,如果是就执行中断服务函数timer_ irq。
  • 在timer_ irq里直接跳转到sched_ yield中执行。而这个函数就是我们将要补充的调度函数。
  • 在时钟中断产生时,最终是调用了sched_ yield函数来进行进程的调度。

Exercise 3.13

kclock_init 直接调用 set_timer 即可。

void kclock_init(void){
    set_timer();
}

KERNEL_SP 和TIME_STACK到底什么关系?

set_timer

我会通过挖掘包含它们的代码来尝试发现一些关系。按时钟中断的顺序来,先看一下set_timer函数

LEAF(set_timer)

    li t0, 0x01
    sb t0, 0xb5000100                // 往0xb5000100位置写1
    sw    sp, KERNEL_SP                // 这个地方设置了KERNEL_SP
setup_c0_status STATUS_CU0|0x1001 0    // 设置允许中断,同时12bit置1,即4号中断可以被响应        
    jr ra                            // 返回

    nop
END(set_timer)

这里我们可以看到KERNEL_SP被赋值成了sp寄存器的值, 由于set_timer是由内核调用的,我们也不难看出,KERNEL_SP是处于内核栈的地址的。

handle_int

异常分发代码上面已经说过了,下面是genex.S/handle_ int函数来处理实时钟中断

NESTED(handle_int, TF_SIZE, sp)
nop

SAVE_ALL
CLI

mfc0 t0, CP0_CAUSE
mfc0 t2, CP0_STATUS
/*这三句用来判断是否可以跳转到timer_irq(判断是否是4号中断)*/
and t0,t2
andi t1, t0, STATUSF_IP4     //取第12位,用于判断4号中断是否可以被响应
bnez t1, timer_irq            //不等于0说明是4号中断,跳转到time_irq
nop
END(handle_int)

timer_irq:
/* sched_yield是进程调度函数 */
1:    j sched_yield            // 跳转到该函数
    nop
    j ret_from_exception    
    nop

这里有两个宏需要解释一下,分别是CLISAVE_ALL (在stackframe.h里)。

/* CLI宏, 这个宏设置SR寄存器,让CPU禁止中断,因为本实验不支持中断嵌套,因此每次只能处理一个中断*/
.macro CLI
mfc0    t0, CP0_STATUS
li    t1, (STATUS_CU0 | 0x1)
or    t0, t1
xor    t0, 0x1
mtc0    t0, CP0_STATUS
.endm
/* SAVE_ALL宏*/
.macro SAVE_ALL
    /*这几条指令不知道意义何在 :) */
    mfc0 k0,CP0_STATUS
    sll k0,3
    bltz k0,1f
    nop
1:
    move    k0,sp
    /*这个get_sp宏设置sp寄存器*/
    get_sp
    /*接下来这些指令就是把各种寄存器的值储存到指定的栈sp里面*/
    move    k1,sp
    ...
    ...
    sw      $31,TF_REG31(sp)
.endm

SAVE_ALL 就是保存现场,把各种寄存器存储到sp寄存器所存储的地址上,这个栈sp是什么地方呢?来看一下get_sp

时钟中断对应的CAUSE寄存器满足 0号异常(条件 1),4号中断(条件2)

.macro get_sp
mfc0    k1, CP0_CAUSE    // 将CP0_CAUSE 寄存器的值存到 k1 寄存器中
andi    k1, 0x107C        // 取出bit2 - bit6(异常码ExcCode 条件1)和 bit12(4号中断 条件2)
xori    k1, 0x1000        // bit12和1做异或运算
bnez    k1, 1f            // k1不等于0,就跳转。也就是说只要上面两个条件有一个不满足就会跳转到分支1
nop
/* 这个地方就是将sp设为TIMESTACK*/
li    sp, 0x82000000
j    2f
nop
1:
bltz    sp, 2f
nop
lw    sp, KERNEL_SP        // 将sp 设为 KERNEL_SP
nop

2:
nop
.endm

至此,KERNEL_SPTIME_STACK 的挖掘结束。相信你们也看出来了这其中的关系了。

总结

最后来总结一下: get_sp宏用于设置sp寄存器,来实现不同的异常发生时的上下文内容存储到不同栈里的效果。

  • 如果是时钟中断,sp就会被设置为TIME_STACK
  • 如果是其他异常,sp就会被设置为KERNEL_SP

再来捋一下,SAVE_ALL宏函数保存现场。SAVE_ALL会调用get_sp来设置sp寄存器(或者说是栈指针),如果发生时钟中断,我们就把sp设置为TIMESTACK,其他异常就是KERNEL_SP 。接着SAVE_ALL函数会把各个寄存器(这个就是进程上下文)的值存入sp中。所以我们就知道了TIMESTACK其实就是我们前面说的发生时钟中断时储存寄存器(上下文环境)内容的栈,KERNEL_SP是其它异常发生时保存上下文的栈!这也就是为什么在切换进程(env_run函数)时,我们保存进程的上下文需要用到了这个TIME_STACK

Exercise 3.14

现在,还剩最后一个内容,也就是进程的调度了: sched_yield 函数。

先在此说明一下,这个函数尽量在lab3就写好,不要留下bug。 我就是lab3的时候留下了一些bug,导致了lab4耽误很长时间。

本实验调度的算法是时间片轮转的算法。所以在时钟中断产生了后,需要进行进程的调度。前面timer_ irq里直接跳转到sched_ yield来完成进程调度,该函数再调用env_run函数来完成进程的切换。

首先我们使用的是两个链表,即env_sched_list,每个链表里存储的都是待调度的进程。为了实现公平的调度,一个进程的时间片用完了,需要插入到另一个链表。一个进程的时间片由它的优先级来决定。时钟中断每产生一次,时间片就需要减一。我们需要使用静态变量来保存当前进程的剩余时间片,当前遍历的链表。写法有很多种,大致流程如下。

  • 判断当前进程的状态和时间片

当前进程的状态如果不是 ENV_RUNNABLE 的话,显然我们就需要停止当前进程的执行,切换另一个进程,不管当前进程的时间片是否为0。如果当前进程的时间片为0,也需要切换另一个进程。

  • 选择将要执行的进程。

如果当前进程的时间片用完,或者状态不对,那么就需要从链表中取出一个状态为RUNNABLE进程,然后切换为该进程执行。进程状态为RUNNABLE的进程肯定处于链表中,状态为NOT_RUNNABLE的进程可以处于链表中,也可以不处于链表中。如果不处于链表中,那么每次进程状态变为NOT_RUNNABLE的时候,就需要将该进程移出链表,状态变为RUNNABLE的时候插入链表。而处于链表中就不需要这么麻烦了。因此相应的代码也有有所不同。lab4会体现出来,lab3好像不用理会。

  • 时间片减一,调用env_run 函数进行进程的切换

注意,要在创建进程的时候,把进程插入调度链表,前面env_create_priority 我已经加了。也可以在load_icode函数中插入,最好不要在env_alloc函数中插入,因为这个时候还没设置优先级!

void sched_yield(void)
{
    //struct Env *e;
    static struct Env *cur = NULL;    // cur也设为了静态变量,表示正在执行的进程
    static int num = 0;// 当前正在遍历的链表
    static int count = 0;// 当前进程剩余执行次数
    /* 这个循环用于选出状态为RUNNABLE的进程, 我的链表也包含了状态为NOT_RUNNABLE的的进程*/
    while(count <= 0 || (cur && cur -> env_status != ENV_RUNNABLE)) {
        count = 0;
        if(cur != NULL) {
            LIST_REMOVE(cur, env_sched_link);// 把这个进程移出当前链表
            /* ENV_FREE的就不能放在链表里了*/
            if(cur -> env_status != ENV_FREE) 
                LIST_INSERT_HEAD(&env_sched_list[num^1], cur, env_sched_link);
        }
        if(LIST_EMPTY(&env_sched_list[num])) num ^= 1; //当前链表为空,就切换链表
        if(LIST_EMPTY(&env_sched_list[num])) { //切换后还为空
            //printf("\nsched.c/sched_yield:NO envs to run\n");
            continue ;
        }
        cur = LIST_FIRST(&env_sched_list[num]); //取出一个进程
        if(cur != NULL) count = cur -> env_pri;    //设置时间片
        //printf("%x %d\n", cur, cur -> env_status);
    }
    -- count;        //时间片减1
    env_run(cur);    //进程切换
}
Last modification:June 28th, 2020 at 11:17 am
如果觉得我的文章对你有用,请随意赞赏