lab3_report

OO和OS都在学进程，着实这段时间被进程折磨有点狠

lab_thinkings

Thinking 3.1

question

请结合 MOS 中的页目录自映射应用解释代码中 e->env_pgdir[PDX(UVPT)]= PADDR(e->env_pgdir) | PTE_V的含义。

answer

​ 在MOS 中，将页表和页目录映射到了用户空间中的 0x7fc00000-0x80000000（共 4MB）区域，这意味着 MOS 中允许在用户态下通过 UVPT 访问当前进程的页表和页目录。

#define UVPT 0x7fc0
#define PTE_V 0x0200
#define PDX(va) ((((u_long)(va)) >> 22) & 0x03FF)

从上面三个宏的定义我们不难理解，PTE_V 有效位，若某页表项的有效位为 1，则该页表项中高 20 位就是对应的物理页号。所以这行代码的含义是将页表映射到UVPT所对应的物理地址，从而让用户可以通过UVAT来访问页表，同时用PTE_V置有效位。

env_pgdir[PDX(UVPT)]= PADDR(e->env_pgdir) | PTE_V表示页目录中第PDX(UVPT)项映射到页目录本身的物理地址，实现自映射机制。

Thinking 3.2

question

elf_load_seg 以函数指针的形式，接受外部自定义的回调函数 map_page。请你找到与之相关的 data 这一参数在此处的来源，并思考它的作用。没有这个参数可不可以？为什么？

answer

elf_load_seg定义在lib/elfloader.c中，具体定义如下：

/* Overview:
 *   load an elf format binary file. Map all section
 * at correct virtual address.
 *
 * Pre-Condition:
 *   `binary` can't be NULL and `size` is the size of binary.
 *
 * Post-Condition:
 *   Return 0 if success. Otherwise return < 0.
 *   If success, the entry point of `binary` will be stored in `start`
 */
int elf_load_seg(Elf32_Phdr *ph, const void *bin, elf_mapper_t map_page, void *data) {
	u_long va = ph->p_vaddr;
	size_t bin_size = ph->p_filesz;
	size_t sgsize = ph->p_memsz;
	u_int perm = PTE_V;
	if (ph->p_flags & PF_W) {
		perm |= PTE_D;
	}

	int r;
	size_t i;
	u_long offset = va - ROUNDDOWN(va, BY2PG);
	if (offset != 0) {
		if ((r = map_page(data, va, offset, perm, bin, MIN(bin_size, BY2PG - offset))) !=
		    0) {
			return r;
		}
	}

	/* Step 1: load all content of bin into memory. */
	for (i = offset ? MIN(bin_size, BY2PG - offset) : 0; i < bin_size; i += BY2PG) {
		if ((r = map_page(data, va + i, 0, perm, bin + i, MIN(bin_size - i, BY2PG))) != 0) {
			return r;
		}
	}

	/* Step 2: alloc pages to reach `sgsize` when `bin_size` < `sgsize`. */
	while (i < sgsize) {
		if ((r = map_page(data, va + i, 0, perm, NULL, MIN(bin_size - i, BY2PG))) != 0) {
			return r;
		}
		i += BY2PG;
	}
	return 0;
}

elf_load_seg 的最后两个参数用于接受一个自定义的回调函数 map_page，以及需要传递给回调函数的额外参数 data,这个参数在具体实现中传给了map_page，所以我们再看一下map_page的编写——在kern/env.c中传入map_page指针的函数是load_icode_mapper,data参数为e。load_icode_mapper实现如下：

static int load_icode_mapper(void *data, u_long va, size_t offset, u_int perm, const void *src,
			     size_t len) {
	struct Env *env = (struct Env *)data;
	struct Page *p;
	int r;

	/* Step 1: Allocate a page with 'page_alloc'. */
	/* Exercise 3.5: Your code here. (1/2) */

	page_alloc(&p);
	//
	/* Step 2: If 'src' is not NULL, copy the 'len' bytes started at 'src' into 'offset' at this
	 * page. */
	// Hint: You may want to use 'memcpy'.
	if (src != NULL) {
		/* Exercise 3.5: Your code here. (2/2) */
		memcpy((void*)(page2kva(p)+offset),src,len);
		//
	}

	/* Step 3: Insert 'p' into 'env->env_pgdir' at 'va' with 'perm'. */
	return page_insert(env->env_pgdir, env->env_asid, p, va, perm);
}

这里利用传入的data参数辅助得到了env_pgdir的位置，所以由此可见，data参数不能省略。

Thinking 3.3

question

结合 elf_load_seg 的参数和实现，考虑该函数需要处理哪些页面加载的情况。

answer

elf_load_seg的作用是将ELF二进制文件加载进来，并将整个段映射到正确的虚拟地址。

所以对于页面加载有以下几种情况：

va和va+bin_size的相对位置有以下6种：

va+bin_size和va+sg_size的相对位置有以下6种：

Thinking 3.4

question

思考上面这一段话，并根据自己在 Lab2 中的理解，回答：你认为这里的 env_tf.cp0_epc 存储的是物理地址还是虚拟地址?

answer

env_tf.cp0_epc存储的是虚拟地址，一方面这个值来自于CPU，而CPU提供的均为虚拟地址，另一方面对于每个用户进程来说entry_point都是一样的（如果不手动进行设置的话），这样可使让程序的每次执行都从一个固定的虚拟地址开始，这种统一对CPU是友好的。

Thinking 3.5

question

0 号异常 的处理函数为 handle_int，表示中断，由时钟中断、控制台中断等中断造成

1 号异常 的处理函数为 handle_mod，表示存储异常，进行存储操作时该页被标记为只读

2 号异常 的处理函数为 handle_tlb，表示 TLB load 异常

3 号异常 的处理函数为 handle_tlb，表示 TLB store 异常

8 号异常 的处理函数为 handle_sys，表示系统调用，用户进程通过执行 syscall 指令陷入内核

试找出上述 5 个异常处理函数的具体实现位置。

answer

handle_int在kern/genex.S中，实现如下：

NESTED(handle_int, TF_SIZE, zero)
	mfc0    t0, CP0_CAUSE
	mfc0    t2, CP0_STATUS
	and     t0, t2
	andi    t1, t0, STATUS_IM4
	bnez    t1, timer_irq
	// TODO: handle other irqs
timer_irq:
	sw      zero, (KSEG1 | DEV_RTC_ADDRESS | DEV_RTC_INTERRUPT_ACK)
	li      a0, 0
	j       schedule
END(handle_int)

handle_mod在kern/traps.c中，无具体实现。

handle_tlb在kern/traps.c中，无具体实现。

handle_sys在kern/traps.c中，无具体实现。

Thinking 3.6

question

阅读 init.c、kclock.S、env_asm.S 和 genex.S 这几个文件，并尝试说出enable_irq 和 timer_irq 中每行汇编代码的作用。

answer

//include/asm/cp0regdef.h
#define STATUS_CU0 0x10000000
#define STATUS_IM4 0x1000
#define STATUS_IEc 0x1
#define CP0_STATUS $12
//kern/gemex.S
LEAF(enable_irq)
	li      t0, (STATUS_CU0 | STATUS_IM4 | STATUS_IEc)
	mtc0    t0, CP0_STATUS//设置中断
	jr      ra	//返回
END(enable_irq)

//include/mmu.h
#define KSEG1 0xA0000000U
//include/drivers/dev_rtc.h:
#define DEV_RTC_INTERRUPT_ACK 0x0110
#define DEV_RTC_ADDRESS 0x15000000
//kern/genex.S
timer_irq:
	sw      zero, (KSEG1 | DEV_RTC_ADDRESS | DEV_RTC_INTERRUPT_ACK)//在相应地址写入0，相应时钟中断
	li      a0, 0
	j       schedule

schedule在kern/sched.c中，返回中断并选择一个进程运行。

Thinking 3.7

question

阅读相关代码，思考操作系统是怎么根据时钟中断切换进程的。

answer

env_sched_list有两个链表存放就绪进程。当进程被创建时，我们将其插入第一个进程调度链表的头部。调用 sched_yield 函数时, 先判断当前时间片是否用完。如果用完，则将其插入另一个链表的结尾，之后判断当前就绪状态进程链表是否为空。如果为空, 将指针切换到另一个就绪状态进程链表。最后从指针指向的链表的头部获取一个就绪进程进行切换。

lab_difficulties

lab3的主体是在用户态下进行进程管理，主要分为创建进程、时钟中断和异常处理和进程调度三个部分，由于lab3存在大量计租p7的知识，还是相对比较简单的，我利用上机开始做，刚好九点整就完成提交通过了。

创建进程

由于没有实现线程，本实验中进程既是基本的分配单元，也是基本的执行单元。每个进程都是一个实体，有其自己的地址空间，通常包括代码段、数据段和堆栈。程序是一个没有生命的实体，只有被操作系统赋予生命时，它才能成为一个活动的实体，而执行中的程序，就是进程。

函数	功能
env_init	实现 Env 控制块的空闲队列和调度队列的初始化功能
env_setup_vm	初始化新进程的地址空间
void map_segment(Pde *pgdir, u_long pa, u_long va, u_long size,u_int perm)	在一级页表基地址 pgdir 对应的两级页表结构中做段地址映射，将虚拟地址段 [va,va+size) 映射到物理地址段 [pa,pa+size)，因为是按页映射，要求 size 必须是页面大小的整数倍。同时为相关页表项的权限为设置为 perm。它在这里的作用是将内核中的 Page和 Env 数据结构映射到用户地址，以供用户程序读取。
mkenvid	生成一个新的进程 id
env_create	创建一个新进程
env_run	进程运行使用
schedule	调度函数

PCB

进程控制块 (PCB) 是系统专门设置用来管理进程的数据结构，它可以记录进程的外部特征，描述进程的变化过程。而在lab3实验中，PCB是用一个Env结构体实现的。

struct Env {
	struct Trapframe env_tf;  // Saved registers
	LIST_ENTRY(Env) env_link; // Free list
	u_int env_id;		  // Unique environment identifier
	u_int env_asid;		  // ASID
	u_int env_parent_id;	  // env_id of this env's parent
	u_int env_status;	  // Status of the environment
	Pde *env_pgdir;		  // Kernel virtual address of page dir
	TAILQ_ENTRY(Env) env_sched_link;
	u_int env_pri;
	// Lab 4 IPC
	u_int env_ipc_value;   // data value sent to us
	u_int env_ipc_from;    // envid of the sender
	u_int env_ipc_recving; // env is blocked receiving
	u_int env_ipc_dstva;   // va at which to map received page
	u_int env_ipc_perm;    // perm of page mapping received

	// Lab 4 fault handling
	u_int env_user_tlb_mod_entry; // user tlb mod handler

	// Lab 6 scheduler counts
	u_int env_runs; // number of times been env_run'ed
};

现代计算机系统中经常有很多进程同时存在，每个进程执行不同的任务，它们之间也经常需要相互协作、通信，而这部分在实验中是依靠进程标识符来实现。在 struct Env 进程控制块中的 env_id 这个域，是每个进程独一无二的标识符，需要在进程创建的时候就被赋予。在 env.c 文件中实现了一个叫做 mkenvid 的函数，作用就是生成一个新的进程 id。

设置进程控制块

第一步——申请一个空闲的 PCB（也就是 Env 结构体），从 env_free_list 中索取一个空闲PCB 块，这时候的 PCB 就像张白纸一样。

第二步——“纯手工打造”打造一个进程。在这种创建方式下，由于没有模板进程，所以进程拥有的所有信息都是手工设置。而进程的信息又都存放于进程控制块中，所以需要手工初始化进程控制块。

第三步——进程光有 PCB 的信息还没法跑起来，每个进程都有独立的地址空间。所以，要为新进程初始化页目录。

第四步——此时 PCB 已经被填写了很多东西，不再是一张白纸，把它从空闲链表里摘出，就可以使用。

加载二进制镜像

要想正确加载一个 ELF 文件到内存，只需将 ELF 文件中所有需要加载的程序段（program segment）加载到对应的虚拟地址上即可。

load_icode 函数负责加载可执行文件 binary 到进程 e 的内存中。它调用的 elf_from 函数完成了解析 ELF 文件头的部分，elf_load_seg 负责将 ELF 文件的一个 segment 加载到内存。

创建进程及运行

创建进程的过程很简单，就是实现对上述个别函数的封装，分配一个新的 Env 结构体，设置进程控制块，并将程序载入到该进程的地址空间即可完成。

在创建进程前，需要调用 env_init 初始化进程管理。

进程运行包括两部分——保存当前进程上下文和恢复要启动的进程的上下文，然后运行该进程。

时钟中断和异常处理

异常处理

当发生异常时，处理器会进入一个用于分发异常的程序，这个程序的作用就是检测发生了哪种异常，并调用相应的异常处理程序。一般来说，异常分发程序会被要求放在固定的某个物理地址上（根据处理器的区别有所不同），以保证处理器能在检测到异常时正确地跳转到那里。这个分发程序可以认为是操作系统的一部分。

时钟中断

时钟中断和操作系统的时间片轮转算法是紧密相关的。时间片轮转调度是一种进程调度算法，每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则该进程将挂起，切换到另一个进程运行。那么 CPU 是如何知晓一个进程的时间片结束的呢？就是通过定时器产生的时钟中断。当时钟中断产生时，当前运行的进程被挂起，我们需要在调度队列中选取一个合适的进程运行。如何“选取”，就要涉及到进程的调度了。

kern/kclock.S 中的 kclock_init 函数完成了时钟中断的初始化，该函数向 KSEG1 | DEV_RTC_ADDRESS| DEV_RTC_HZ 位置写入 200，其中 KSEG1 | DEV_RTC_ADDRESS 是模拟器（GXemul）映射实时钟的位置。偏移量为 DEV_RTC_HZ 表示设置实时钟中断的频率，200 表示 1 秒钟中断 200 次；如果写入 0，表示关闭时钟中断。时钟中断对于 GXemul 来说绑定到了 4 号中断上。注意这里的中断号和异常号是不一样的概念，我们实验的异常包括中断，中断本身是 0 号异常。

init/init.c 中的 mips_init 函数在完成初始化并创建进程后，需要调用 kclock_init 函数完成时钟中断的初始化，然后调用 kern/env_asm.S 中的 enable_irq 函数开启中断。

一旦实时钟中断产生，就会触发 MIPS 中断，从而系统将 PC 指向 0x80000080，从而跳转到.text.exc_gen_entry 代码段执行。对于实时钟引起的中断，通过.text.exc_gen_entry 代码段的分发，最终会调用 handle_int 函数来处理实时钟中断。

handle_int 中判断了 Cause 寄存器是不是对应的 4 号中断位引发的中断，如果是，则执行中断服务函数 timer_irq，跳转到 schedule 中执行。而这个函数就是我们将要补充的调度函数。

进程调度

调度的算法很简单，就是时间片轮转的算法。env 中的优先级在这里起到了作用，我们规定其数值表示进程每次运行的时间片数量。不过寻找就绪状态进程不是简单遍历所有进程，而是用一个调度链表存储所有就绪（可运行）的进程，即一个进程在调度链表中当且仅当这个进程是就绪（ENV_RUNNABLE）状态的。当内核创建新进程时，将其插入调度链表的头部；在其不再就绪（被阻塞）或退出时，将其从调度链表中移除。

/* Overview:
 *   Implement a round-robin scheduling to select a runnable env and schedule it using 'env_run'.
 *
 * Post-Condition:
 *   If 'yield' is set (non-zero), 'curenv' should not be scheduled again unless it is the only
 *   runnable env.
 *
 * Hints:
 *   1. The variable 'count' used for counting slices should be defined as 'static'.
 *   2. Use variable 'env_sched_list', which contains and only contains all runnable envs.
 *   3. You shouldn't use any 'return' statement because this function is 'noreturn'.
 */
void schedule(int yield) {
	static int count = 0; // remaining time slices of current env
	struct Env *e = curenv;

	/* We always decrease the 'count' by 1.
	 *
	 * If 'yield' is set, or 'count' has been decreased to 0, or 'e' (previous 'curenv') is
	 * 'NULL', or 'e' is not runnable, then we pick up a new env from 'env_sched_list' (list of
	 * all runnable envs), set 'count' to its priority, and schedule it with 'env_run'. **Panic
	 * if that list is empty**.
	 *
	 * (Note that if 'e' is still a runnable env, we should move it to the tail of
	 * 'env_sched_list' before picking up another env from its head, or we will schedule the
	 * head env repeatedly.)
	 *
	 * Otherwise, we simply schedule 'e' again.
	 *
	 * You may want to use macros below:
	 *   'TAILQ_FIRST', 'TAILQ_REMOVE', 'TAILQ_INSERT_TAIL'
	 */
	/* Exercise 3.12: Your code here. */
	if(yield||count==0||e==NULL||e->env_status!=ENV_RUNNABLE){
		if(e!=NULL&&e->env_status==ENV_RUNNABLE){
			TAILQ_REMOVE(&env_sched_list,e,env_sched_link);
			//e=TAILQ_FIRST(&env_sched_list);
			TAILQ_INSERT_TAIL(&env_sched_list,e,env_sched_link);

		}
		//LIST_REMOVE(e,env_sched_link);
		e=TAILQ_FIRST(&env_sched_list);
		TAILQ_REMOVE(&env_sched_list,e,env_sched_link);
		count=e->env_pri;	
	}
	count--;
	env_run(e);
	//
}

lab_summary

Lab3要求我们实现进程的创建、切换和调度，其中进程的调度主要是通过设置异常处理机制来实现。

本次实验的难度比Lab2稍稍低一些，主要原因是本次lab中各个函数之间的联系比较紧密。虽然某些复杂函数理解起来还是有些困难，但是如果在宏观上把握这些函数的关系，那么对于单个函数的理解就变得相对容易了。

这周刚好冯如杯、蓝桥杯、电梯第二周、学生会和班委会一堆事撞一起，OS的难度不大真的减压不少，期待lab4带来更多精彩。