BUAA-OS

「BUAA OS Lab3」难点梳理与理解总结

Posted by saltyfishyjk on 2022-05-10
Words 4.4k and Reading Time 19 Minutes
Viewed Times

「BUAA OS Lab3」难点梳理与理解总结

进程创建

进程控制块（Process Control Block）

PCB是用来进程管理的数据结构，在我们的MOS中就是Env结构体，具体内容可以参考源码或Lab 3 名词解释。在后文中，我们可能混用PCB和Env，其实两者基本是一个东西。

对于PCB，我们仿照Lab 2中的思路，为envs开辟空间，通过boot_map_segment将其map到UENVS空间。

之后，我们类比page_init，将空闲进程块连缀成env_free_list，值得注意的是这里guidebook强调了顺序问题，需要稍加注意。

进程创建流程

  1. 从env_free_list获取一个空的PCB
  2. 对PCB进行初始化
  3. 为进程分配资源
  4. 从空闲链表中移出并开始执行

获取空PCB并初始化

第1和第2步是在env_alloc中进行的，其代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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*/
    /* 从env_free_list中取出一个空的PCB */
	if (LIST_EMPTY(&env_free_list)) {
		*new = NULL;
		return -E_NO_FREE_ENV;
	}
	e = LIST_FIRST(&env_free_list);

    /* Step 2: Call a certain function (has been completed just now) to init kernel memory layout for this new Env.
     *The function mainly maps the kernel address to this new Env address. */
    /* 初始化新进程的地址空间，这个函数将在下面具体介绍 */
	env_setup_vm(e);	

    /* Step 3: Initialize every field of new Env with appropriate values.*/
    /* 初始化Env结构体的一些变量，设置env_id, env_status, env_parent_id, env_runs */
	e->env_id = mkenvid(e);
	e->env_status = ENV_RUNNABLE;
	e->env_parent_id = parent_id;
	e->env_runs = 0;

    /* Step 4: Focus on initializing the sp register and cp0_status of env_tf field, located at this new Env. */
    /* e->env_tp.cp0_status的设置保证了可以正常响应中断 
     * 具体而言，0x1000,1004对应的32位二进制数中的第2、12、28位为1（最低位为0位）
     * 根据SR结构可以知道，分别将IEp置高（在进程启动前调用rfe指令会将该值拷贝到IEc从而Interrupt Enable即允许中断）、12位置高表示4号中断可以相应、28位置高表示允许在用户态下使用CP0寄存器 */
    e->env_tf.cp0_status = 0x10001004;
	e->env_tf.regs[29] = USTACKTOP;

    /* Step 5: Remove the new Env from env_free_list. */
    /* 将Env从链表中移出 */
	LIST_REMOVE(e, env_link);
	*new = e;
	return 0;

}

env_setup_vm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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 pp_ref.
     *   pgdir is the page directory of Env e, assign value for it. */
    /* 为pgdir申请一个新的页，并将其pp_ref++ */
	r = page_alloc(&p);
    if (r != 0) { // page_alloc return 0 if success
        panic("env_setup_vm - page alloc error\n");
        return r;
    }
	p->pp_ref++;
	pgdir = (Pde *)page2kva(p);

    /* Step 2: Zero pgdir's field before UTOP. */
	/* 把UTOP下面的pgdir内容全部清零 */
	for (i = 0;i < PDX(UTOP); i++) {
		pgdir[i] = 0;
	}



    /* Step 3: Copy kernel's boot_pgdir to pgdir. */

    /* Hint:
     *  The VA space of all envs is identical above UTOP
     *  (except at 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 < PTE2PT; i++) {
		if (i != PDX(VPT) && i != PDX(UVPT)) {
			pgdir[i] = boot_pgdir[i];
		}
	}
	
	e->env_pgdir = pgdir;
	e->env_cr3 = PADDR(pgdir);
    /* UVPT maps the env's own page table, with read-only permission.*/
    e->env_pgdir[PDX(UVPT)]  = e->env_cr3 | PTE_V;
    return 0;
}

在我们的MOS中支持多进程，多进程彼此互不干扰，因此每个进程有自己的页表。

在env_setup_vm中，我们首先调用page_alloc申请一个页目录页，通过page2kva获取该页的虚拟地址并转型为Pde *并赋给pgdir以便于访问。在这里我们再啰嗦一下，代码中要访问的地址都是虚拟地址。

由于每个进程有自己单独的页表，这个页表会映射完整的4G空间，其中，由于用户态2G加上内核态2G，因此，内核态2G是公用的，因此我们拷贝内核页表。

然后，我们进行一些PCB内容的初始化，具体为设置pgdir，设置env_cr3。

这里，我们再啰嗦一下，每个进程都有自己的视图下的4G空间，不同进程都在同一个虚拟地址有数据是完全可能的。值得注意的是，获取pgdir的具体流程为：申请可用物理页一个，将物理页在kseg0映射的虚拟地址赋给pgdir。由kseg0和物理内存一一映射关系我们可以知道，我们是真正改变了内核虚拟空间的这部分内容，由于对于所有进程内核虚拟空间都是共享的，因此对于其他进程也可以看到。

为进程分配资源并将PCB从空闲链表中移出

首先明确目的：我们需要加载二进制镜像

为了便于理解和对函数的补全，我们需要先从更高的抽象来知道各个函数如何协作完成了这一过程：

  1. loac_icode函数首先申请一个空闲页，并将该进程pgdir对应的两届页表结构中的USTOCK-BY2PG映射刚才申请的空闲页中，并设置好权限。这里的权限为PTE_R，即，writable。然后，调用了load_elf函数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    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.
         */
        struct Page *p = NULL;
        u_long entry_point;
        u_long r;
        u_long perm;

        /* Step 1: alloc a page. */
    	perm = PTE_R;
    	if ((r = page_alloc(&p)) != 0) {
    		return;
    	}
        /* Step 2: Use appropriate perm to set initial stack for new Env. */
        /* Hint: Should the user-stack be writable? */
    	if ((r = page_insert(e->env_pgdir, p, USTACKTOP - BY2PG, perm)) != 0) {
    		return;
    	}
    	if ((r = load_elf(binary, size, &entry_point, e, load_icode_mapper)) != 0) {
    		return;
    	}

        /* Step 3: load the binary using elf loader. */


        /* Step 4: Set CPU's PC register as appropriate value. */
        e->env_tf.pc = entry_point;
    }

  2. load_elf函数解析ELF，并利用函数指针int(*map)调用load_icode_mapper()函数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    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))
    {
    	Elf32_Ehdr *ehdr = (Elf32_Ehdr *)binary;
    	Elf32_Phdr *phdr = NULL;
    	/* As a loader, we just care about segment,
             * so we just parse program headers.
             */
    	u_char *ptr_ph_table = NULL;
            Elf32_Half ph_entry_count;
            Elf32_Half ph_entry_size;
            int r;
    	
    	// check whether `binary` is a ELF file.
    	if (size < 4 || !is_elf_format(binary)) {
                    return -1;
            }

            ptr_ph_table = binary + ehdr->e_phoff; // 程序头表所在处与此文件头的偏移
            ph_entry_count = ehdr->e_phnum; // 程序头表入口数
            ph_entry_size = ehdr->e_phentsize; // 程序头表入口大小

            while (ph_entry_count--) {
                    phdr = (Elf32_Phdr *)ptr_ph_table;

                    if (phdr->p_type == PT_LOAD) {
    	/* Your task here!  */
            /* Real map all section at correct virtual address.Return < 0 if error. */
            /* Hint: Call the callback function you have achieved before. */
    					r = map(phdr->p_vaddr, phdr->p_memsz,  binary + phdr->p_offset, phdr->p_filesz, user_data);
    					if (r != 0) {
    						return r;
    					}	
                    }

                    ptr_ph_table += ph_entry_size;
            }

            *entry_point = ehdr->e_entry;
            return 0;
    }

  3. load_icode_mapper函数根据传入的参数将ELF文件加载进内存。

这个函数非常重要，而且指导书中基本是只抛给了我们一张图，因此我将在下面代码的注释中结合图示仔细讲解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
static int load_icode_mapper(u_long va, u_int32_t sgsize,
                             u_char *bin, u_int32_t bin_size, void *user_data)
{
    struct Env *env = (struct Env *)user_data;
    struct Page *p = NULL;
    u_long i = 0; // 参考图中的i，标记目前已经自va加载了i字节。后面的前一部分可能i=0，这时加不加i本质上一样，但是我们用加i表示概念上的统一
    int r; // 保存返回值，一般是错误码
    u_long offset = va - ROUNDDOWN(va, BY2PG); // va和离其最近的低于其的BY2PG的偏移量，事实上就是图中的offset
	int size; // bcopy或者bzero中的参数
	if (offset != 0) { // offset不等于0，说明va没有页对齐，说明我们首先需要先将va到下一个页起点的这一块加载到内存中
		p = page_lookup(env->env_pgdir, va + i, NULL); // 值得注意的是，这里offset所在的虚拟页前面的内容可能已经被加载到物理内存中过，所以我们需要先查找va是否有对应一个物理页框
		if (p == 0) { // va没有对应的物理页框，说明需要申请一个页框
			if ((r = page_alloc(&p)) != 0) { // 如果物理页申请不到就错误返回
				return r;
			}
			page_insert(env->env_pgdir, p, va + i, PTE_R); // 申请完的新的物理页框需要建立和va+i的映射关系
		}
		size = MIN(bin_size - i, BY2PG - offset); // 计算我们要拷贝多少字节。这里需要注意，当va并非页对齐的时候，不代表bin_size一定比BY2PG-offset大，有可能bin_size连va后面这残缺的半页都填不满。另外特别注意的是，我们不能多加载，不能把bin_size后的内容拷贝过来。
		bcopy((void *)bin,(void *)(page2kva(p) + offset), size); // 这里注意bcopy的三个参数分别是起点、终点和长度。我们将bin开始的MIN(bin_size, BY2PG - offset)这么长的内容拷贝到page2kva(p) + offset对应的地方。这里稍微再罗嗦一下，我们代码中任何访问地址的行为用的都是虚拟地址，所以要将page转为kva。
		i = i + size; // 更新我们已经加载了i字节
	}	
    /* Step 1: load all content of bin into memory. */
        /* Hint: You should alloc a new page. */
    // 在这部分中，我们要将bin_size恰好拷贝完
	while (i < bin_size) { // 循环节有效的标志是我们没有拷贝完bin_size
		size = MIN(BY2PG, bin_size - i); // 每个循环节我们都要考虑：还没有拷贝完的内容（bin_size - i）是否大于等于1页，注意不能多拷贝
		if ((r = page_alloc(&p)) != 0) {
			return r;
		}
		page_insert(env->env_pgdir, p, va + i, PTE_R); // 对新申请的页框建立映射关系
		bcopy((void *)(bin + i), (void *)(page2kva(p)), size); // 拷贝
		i += size; // 更新
    }
    /* Step 2: alloc pages to reach `sgsize` when `bin_size` < `sgsize`.
     * hint: variable `i` has the value of `bin_size` now! */
    // 在这部分中，我们要将binsize->sgsize部分（如果有）填充为0
	u_long bin_size_remain = (va + i) - ROUNDDOWN(va + i, BY2PG); // 这里我没有直接抄login，用了一个新变量bin_size_remain指代如果va+i没有对齐，那么va+i在当前页多出来的那一部分的长度
	if (bin_size_remain != 0) {
		p = page_lookup(env->env_pgdir, va + i, NULL); // 这里和处理offset时候的逻辑类似，都是先寻找va+i是不是已经映射到了页框
		if (p == 0) {
			if ((r = page_alloc(&p)) != 0) {
				return r;
			}
			page_insert(env->env_pgdir, p, va + i, PTE_R);
		}
		size = MIN(sgsize - i, BY2PG - bin_size_remain); // 这里也要继续注意，va+i页当前剩余了BY2PG - bin_size_remain这么多字节，但需要我们继续填充0的字节有sgsize-i，我们需要保证不多写
		bzero((void *)(page2kva(p) + bin_size_remain), size); // 清零
		i += size; // 更新
	}
    while (i < sgsize) { // 如果该条件成立，意味着还需要继续填充0到sgsize
		size = MIN(BY2PG, sgsize - i); // 保证不多填
        // 申请页框+建立映射
		if (r = (page_alloc(&p)) != 0) {
			return r;
		}
		page_insert(env->env_pgdir, p, va + i, PTE_R);
		bzero((void *)(page2kva(p)), size);
		i += size;
	}
    return 0;
}
  1. 返回load_icode函数，设置PC寄存器，使得可以正常进入执行。

上面实现了进程创建，在这之后，我们通过env_create调用env_create_priority进而创建进程。

值得注意的是，我们在真正创建进程的时候，通过了ENV_CREATE这一封装宏。

进程运行和切换

这一部分涉及的函数主要是env_run。这里需要注意，我们说运行一个新进程，但也往往意味着进程切换而非单纯的进程运行，因此我们可以合并来考虑两者，类似共同的循环节，因此我们可以统一考虑进程切换。

进程切换时，需要保存的内容有：

  • 进程本身的信息
  • 进程周围环境的信息

整体流程如下：

  • 保存进程上下文信息，设置当前进程上下文中的pc为epc
  • 切换curenv使其指向新进程
  • 调用lcontext函数，设置全局变量mCONTEXT为当前进程页目录地址，会在TLB重填时用到
  • 调用env_pop_tf保存现场

以下我们以注释的形式解释env_run：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void
env_run(struct Env *e)
{
    /* Step 1: save register state of curenv. */
    /* Hint: if there is an environment running, 
     *   you should switch the context and save the registers. 
     *   You can imitate env_destroy() 's behaviors.*/
    /* 当curenv不为NULL的时候，将当前寄存器状态保存在old中并将old逐字节拷贝到curenv->env_tf中，另外，设置当前进程的pc值为cp0_epc，使其陷入中断 */
    /* 这里有一条规定，即，本实验的寄存器状态保存的地方是TIMESTACK */
	if (curenv) {
		struct Trapframe *old = (struct Trapframe *)(TIMESTACK - sizeof(struct Trapframe));
		bcopy(old, &(curenv->env_tf), sizeof(struct Trapframe));
		curenv->env_tf.pc = curenv->env_tf.cp0_epc;
	}

    /* Step 2: Set 'curenv' to the new environment. */
    /* 使curenve指向新进程 */
	curenv = e;

    /* Step 3: Use lcontext() to switch to its address space. */
    /* 设置全局变量mCONTEXT为当前进程页目录地址 */
	lcontext(curenv->env_pgdir);

    /* Step 4: Use env_pop_tf() to restore the environment's
     *   environment   registers and return to user mode.
     *
     * Hint: You should use GET_ENV_ASID there. Think why?
     *   (read <see mips run linux>, page 135-144)
     */
    /* 保存现场 */
	env_pop_tf(&(curenv->env_tf), GET_ENV_ASID(curenv->env_id));
}

另外有两点强调一下：

  • 在发生时钟中断的时候，操作系统将进程状态的栈顶地址保存进时钟栈TIMESTACK，进入时钟中断后，把TIMESTACK的值赋给寄存器们，再执行中断处理。
  • TIMESTACK是发生时钟中断后进程状态的存储区，而KERNEL_SP是发生系统调用后的进程状态的存储区。
  • env_destroy中，当curenv == e的时候，会将KERNEL_SP的tf拷贝到TIMESTACK中，据学姐说法是调用sched_yield获取下一个要执行的进程之前，要将环境恢复到调用当前进程之前的环境，或者也可能和kill到最后一个进程的时候要恢复到最初状态有关。这部分内容有待将来学习过程中补充或勘误。
  • 我们看到，TIMESTACK所在的页面不应当存在于可被申请的page_free_list中，因此需要在page_init中将其摘出

中断异常

首先明确中断和异常的关系：引起控制流突变的就叫做异常，因此中断是异常的一种，且是仅有的一种异步异常。

相关寄存器

中断和异常用到了CPU中的协处理器（CP0）中的12号（SR），13号（Cause）和14号（EPC）寄存器，介绍如下：

寄存器助记符 CP0寄存器编号 描述
SR 12 Status Reg，状态寄存器，包括中断引脚是能，其他CPU模式等位域
Cause 13 记录导致异常的原因
EPC 14 异常结束后程序恢复执行的位置

处理异常流程

  1. 设置EPC指向异常结束时重新返回的地址
  2. 设置SR位，强制CPU进入内核态（有更高级的特权）并禁止中断
  3. 设置Cause寄存器，记录异常发生的原因
  4. CPU开始从异常入口位置取值，此后交给软件处理（这就是我们要做的工作）

时钟中断

实验中常用的是0号异常，即中断异常的处理函数，对我们来说，会有如下流程：

  1. 跳转到异常分发代码.text.exc_vec3
  2. 跳到对应的异常处理函数（0号异常）处
  3. handle_int中通过指令andi t1, t0, STATUSF_IP4来判断是否是4号中断，如果是的话跳转到timer_irq再跳转到sched_yield，选择下一个进程来执行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
NESTED(except_vec3, 0, sp)
	.set noat 
	.set noreorder
1:
	mfc0	k1, CP0_CAUSE # 将CP0_CAUSE拷贝到k1寄存器
	la	k0, exception_handlers # 将exception_handlers基地址拷贝到k0寄存器
	andi	k1, 0x7c # 获得 CP0_CAUSE 2 - 6位，由Cause寄存器结构知这部分就是异常码ExcCode
	addu	k0, k1 # exception_handlers + ExcCode即对exception_handlers进行ExcCode大小的偏移，找到对应的异常处理函数
	lw	k0, (k0) # 把找到的异常处理函数地址赋值给k0
	nop
	jr	k0 # 跳转到对应的异常处理函数
	nop
END(except_vec3)
	.set at

时钟初始化

值得注意的是，上面的流程概览的前提是完成了时钟的初始化。以下是时钟初始化流程：

  1. init/init.c中调用了kclock_init函数进行初始化
  2. kclock_init直接调用set_timer设置时钟
  3. kclock_asm.S实现了set_timer，具体为在0xb5,000,100位置写入0xc8，其中0xb5,000,000是模拟器gxemul映射实时钟的位置，偏移量0x100表示设置实时钟中断的频率，0xc8表示1秒钟中断200次。也就是说，如果在这里写入0，代表一秒钟中断0次，即关闭实时钟。R3000中实时钟绑定在了4号终端上，也就是说这里是在设置对4号中断的触发，注意是4号中断而非4号异常。

进程调度

进程调度主要在sched_yield中实现，以下将结合代码具体讲解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
void sched_yield(void)
{
    static int count = 0; // remaining time slices of current env
    static int point = 0; // current env_sched_list index
    static struct Env *e = NULL;
    /*  hint:
     *  1. if (count==0), insert `e` into `env_sched_list[1-point]`
     *     using LIST_REMOVE and LIST_INSERT_TAIL.
     *  2. if (env_sched_list[point] is empty), point = 1 - point;
     *     then search through `env_sched_list[point]` for a runnable env `e`, 
     *     and set count = e->env_pri
     *  3. count--
     *  4. env_run()
     *
     *  functions or macros below may be used (not all):
     *  LIST_INSERT_TAIL, LIST_REMOVE, LIST_FIRST, LIST_EMPTY
     */
	/* 当前count为0即当前进程时间片消耗尽；e=NULL即还未开始调度第一个进程；当前进程的状态不是可运行的 */
     if (count == 0 || e == NULL || e->env_status != ENV_RUNNABLE) {
         /* e非NULL即当前有进程正在进行 */
         if (e != NULL) {
             /* 从当前的sched链表中移出 */
             LIST_REMOVE(e, env_sched_link);
             /* 当前进程的状态仍然是可运行的，则需要从sched链表中移出并将其插入另一个sched链表 */
             if (e->env_status != ENV_FREE) {
                 LIST_INSERT_TAIL(&env_sched_list[1 - point], e, env_sched_link);
             }
         }
         while (1) {
             /* 如果当前的sched链表空了，转向另外的链表 */
             while(LIST_EMPTY(&env_sched_list[point])) {
                 point = 1 - point;
             }
             /* 取出链表中的第一个进程 */
             e = LIST_FIRST(&env_sched_list[point]);
             /* 如果这个进程状态是free的，直接删除 */
             if (e->env_status == ENV_FREE) {
                 LIST_REMOVE(e, env_sched_link);
             } else if (e->env_status == ENV_NOT_RUNNABLE) {
                 /* 如果当前进程不可调度，将其转移到对面链表的末尾 */
                 LIST_REMOVE(e, env_sched_link);
                 LIST_INSERT_TAIL(&env_sched_list[1 - point], e, env_sched_link);
             } else {
                 /* 找到了合法的可调度进程，设置count为优先级即该进程要运行的时间片的数量，退出死循环 */
                 count = e->env_pri;
                 break;
             }
         }
     }
	/* 消耗一个时间片 */
     count--;
	/* 新进程被调度1次 */
     e->env_runs++;
	// printf("\n%d\n",e->env_id);
	/* 运行进程 */
     env_run(e);
}

This is copyright.

FEATURED TAGS
BUAA-OS
FRIENDS