Lab3

keywords：进程，异常

进程

一个进程就是一个正在执行程序的实例，包括程序计数器、寄存器和变量的当前值。从概念上说，每个进程拥有它自己的虚拟CPU，实际上真正的CPU在各个进程之间来回切换。

由于没有实现线程，本实验中进程既是基本的分配单元，也是基本的执行单元。

进程控制块（PCB）

进程的三种状态

• 运行态（该时刻进程实际占用CPU）
• 就绪态（可运行，但因为其他进程正在运行而暂时停止）
• 阻塞态（除非某种外部事件发生，否则进程不能运行）

进程控制块 (PCB) 是系统专门设置用来管理进程的数据结构，它可以记录进程的外部特征，描述进程的变化过程。

在 MOS 中，PCB 由一个 Env 结构体实现。

struct Env {
	struct Trapframe env_tf;  // Saved registers
	// env_tf: Trapframe 在include/trap.h中定义，在发生进程调度或当陷入内核时，会将当时的进程上下文环境(CP0)保存在env_tf变量中
	LIST_ENTRY(Env) env_link; // Free list
	// env_link：使用其构造空闲进程链表env_free_list
	u_int env_id;		  // Unique environment identifier
	// env_id：进程独一无二的标识符
	u_int env_asid;		  // ASID
	u_int env_parent_id;	  // env_id of this env's parent
	// env_parent_id：进程是可以被其它进程创建的，创建本进程的进程称为父进程。此变量记录父进程的进程id。进程树
	u_int env_status;	  // Status of the environment
	// env_status：ENV_FREE(进程空闲链表)，ENV_NOT_RUNNABLE(阻塞状态)，ENV_RUNNABLE(执行状态或就绪状态)
	Pde *env_pgdir;		  // Kernel virtual address of page dir
	// env_pgdir：该进程页目录的内核虚拟地址
	TAILQ_ENTRY(Env) env_sched_link;
	// env_sched_link：构造调度队列env_sched_list
	u_int env_pri;
	// env_pri：保存了该进程的优先级
};

envs 数组用于存放进程控制块的物理内存。

envs_free_list 按照链表形式保存空闲的进程控制块。

env_sched_list 按照双端队列(TAILQ)形式保存调度队列。

==在 exercise 3.1 中，envs的大小是 NENV .==

段地址映射

base_pgdir 模板页表：

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。

进程的标识

ASID：ASID 是 Address Space ID 的缩写，它是一种处理器（CPU）的硬件机制，用于区分和隔离不同的进程或线程之间的虚拟地址空间。每个进程或线程都有一个唯一的 ASID，用于标识其虚拟地址空间。当处理器执行一个新的进程或线程时，它会切换 ASID，以确保当前运行的进程或线程的虚拟地址空间与先前运行的进程或线程相隔离，这有助于保护系统的安全性和稳定性。

struct Env 进程控制块中的 env_id 域，是每个进程独一无二的标识符，需要在进程创建的时候就被赋予。

mkenvid 函数：生成一个新的进程标识符。

asid_alloc：ASID 部分只占据了 6-11 共 6 个 bit。实验采用了位图法管理 64 个可用的 ASID，如果ASID 耗尽时仍要创建进程，内核会发生崩溃（panic）。

设置进程控制块

4种主要事件会导致进程的创建：

1. 系统初始化。
2. 正在运行的程序执行了创建进程的系统调用。
3. 用户请求创建一个新进程。
4. 一个批处理作业的初始化。

进程创建流程：

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

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

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

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

env_setup_vm ：初始化新进程的地址空间。（我们要暴露 UTOP 往上到 UVPT 之间所有进程共享的只读空间，也就是把这部分内存对应的内核页表 base_pgdir 拷贝到进程页表中。从 UVPT 往上到 ULIM 之间则是进程自己的页表。）

加载二进制镜像

在进程创建之后，父进程和子进程有各自不同的地址空间。如果其中某个进程在其地址空间中修改了一个字，这个修改对其他线程是不可见的。每个进程有自己独立的地址空间，当进程创建后，需要把程序（本节中的程序指可执行文件）加载到新进程的地址空间中。在本实验中，只需要将 ELF 文件中所有需要加载的程序段 （program segment）加载到对应的虚拟地址上即可。

本部分涉及的函数主要为 load_icode_mapper 和 load_icode :

// load_icode 函数负责加载可执行文件 binary 到进程 e 的内存中
static void load_icode(struct Env *e, const void *binary, size_t size) {
	// ① elf_from：解析 ELF 文件头的部分
	const Elf32_Ehdr *ehdr = elf_from(binary, size); 
	if (!ehdr) {
		panic("bad elf at %x", binary);
	}
    
	size_t ph_off;
	ELF_FOREACH_PHDR_OFF (ph_off, ehdr) {
		Elf32_Phdr *ph = (Elf32_Phdr *)(binary + ph_off);
		if (ph->p_type == PT_LOAD) {
            // elf_load_seg: 将 ELF 文件的一个 segment 加载到进程的地址空间中
            // ph: 每个segment的段头; binary+ph->p_offset: 其数据在内存中的起始位置
			panic_on(elf_load_seg(ph, binary + ph->p_offset, load_icode_mapper, e));
		}
	}
	e->env_tf.cp0_epc = ehdr->e_entry;
}

elf_load_seg(ph, bin, map_page, data) ：每当 elf_load_seg 函数解析到一个需要加载到内存中的页面，会将有关的信息作为参数传递给回调函数，并由它完成单个页面的加载过程，而这里 load_icode_mapper 就是 map_page 的具体实现。

elf_load_seg 函数会从 ph 中获取 va（该段需要被加载到的虚地址）、sgsize（该段在内存中的大小）、bin_size（该段在文件中的大小）和 perm（该段被加载时的页面权限），并根据这些信息完成以下两个步骤：

1. 加载该段的所有数据（bin）中的所有内容到内存（va）。
2. 如果该段在文件中的内容的大小达不到为填入这段内容新分配的页面大小，即分配了新的页面但没能填满（如 .bss 区域），那么余下的部分用 0 来填充。

elf_load_seg 会正确处理虚拟地址 va、该段占据的内存长度 sg_size 以及需要拷贝的数据长度 bin_size的页面偏移，对于每个需要加载的页面，用对齐后的地址 va 以及该页的其他信息调用回调函数 map_page，由回调函数完成单页的加载。

load_icode_mapper：单个页面的加载。分配所需的物理页面，并在页表中建立映射。若 src 非空，你还需要将该处的 ELF 数据拷贝到物理页面中。

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;

	/* Step 1: Allocate a page with 'page_alloc'. */
	if (page_alloc(&p) != 0) return -E_NO_MEM;
    
	/* Step 2: If 'src' is not NULL, copy the 'len' bytes started at 'src' into 'offset' at this page. */
	if (src != NULL) {
		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);
}

创建进程

本部分的“创建进程”是指在操作系统内核初始化时直接创建进程，所需做的是分配一个新的 Env 结构体，设置进程控制块，并将程序载入到该进程的地址空间，将新创建的进程放入 env_sched_list。

进程运行与切换

运行一个新进程往往意味着进程切换。进程切换时需要保存进程的上下文信息，包括通用寄存器、HI、LO 和 CP0 中的 SR，EPC，Cause 和 BadVAddr 寄存器。

env_run 的执行流程：

1. 保存当前进程的上下文信息。

2. 切换 curenv 为即将运行的进程。

3. 设置全局变量 cur_pgdir 为当前进程页目录地址，在 TLB 重填时将用到该全局变量。

4. 调用 env_pop_tf 函数，恢复现场、异常返回。

中断与异常

CO中我们已经接触过 CP0 协处理器。

MIPS CPU 处理一个异常时大致要完成四项工作：

1. 设置 EPC 指向从异常返回的地址。
2. 设置 SR 位，强制 CPU 进入内核态（行使更高级的特权）并禁止中断。
3. 设置 Cause 寄存器，用于记录异常发生的原因。
4. CPU 开始从异常入口位置取指，此后一切交给软件处理。

时钟中断

时间片轮转调度是一种进程调度算法，每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则该进程将挂起，切换到另一个进程运行。

进程调度

调用 schedule 函数时，当前正在运行的进程被存储在全局变量 curenv 中（在第一个进程被调度前为 NULL），其剩余的时间片数量被存储在静态变量 count 中。我们考虑是否需要从调度链表头部取出一个新的进程来调度，有这几种应进行进程切换的情况：

• 尚未调度过任何进程。

• 当前进程已经用完了时间片。

• 当前进程不再就绪（如被阻塞或退出）。

• yield 参数指定必须发生切换。

在发生切换的情况下，我们还需要判断当前进程是否仍然就绪，如果是则将其移动到调度链表的尾部。之后，我们从调度链表头部取出一个新的进程来调度，将时间片数量设置为其优先级。

思考题

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

e->env_pgdir 表示一个进程的页目录表，PDX(UVPT) 表示将自身的页目录表映射到虚拟地址空间中的地址，PADDR(e->env_pgdir) 获取 e->env_pgdir 所在的物理页框的地址，PTE_V 表示该页表项是有效的。这行代码是将进程 e 的页目录表自映射到虚拟地址空间的 UVPT 上，以便进程可以通过访问 UVPT 来访问自己的页目录表。

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

int elf_load_seg(Elf32_Phdr ph, const void bin, elf_mapper_t map_page, void data);

在 load_icode 函数中调用 elf_load_seg 时data 传入的是进程控制块 e。观察 load_icode_mapper 发现 创建的新页面插入时需要传入该页面所属进程的页目录基地址和 asid。显然不可以没有这个参数，因为每个进程由独立的地址空间，需要该参数区分页面所属的进程。

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

elf_load_seg 函数会从 ph 中获取 va（该段需要被加载到的虚地址）、sgsize（该段在内存中的大小）、bin_size（该段在文件中的大小）和 perm（该段被加载时的页面权限），并根据这些信息完成以下两个步骤：

1. 加载该段的所有数据（bin）中的所有内容到内存（va）。
2. 如果该段在文件中的内容的大小达不到为填入这段内容新分配的页面大小，即分配了新的页面但没能填满（如 .bss 区域），那么余下的部分用 0 来填充。

elf_load_seg 会正确处理虚拟地址 va、该段占据的内存长度 sg_size 以及需要拷贝的数据长度 bin_size的页面偏移，对于每个需要加载的页面，用对齐后的地址 va 以及该页的其他信息调用回调函数 map_page，由回调函数完成单页的加载。

u_long va: 该段需要被加载到的虚拟地址。

size_t bin_size：该段在文件中的大小。

size_t sgsize：该段在内存中的大小。

u_int perm：该段被加载时的页面权限

elf_mapper_t map_page ： 回调函数

void *data：回调函数所需的参数

需要处理的页面加载情况：

1. 虚拟地址 va 未页对齐，填写offset - min(bin_size, BY2PG - offset) 部分。
2. bin中已页对齐的部分。
3. 若 bin_size < sgsize，分配一些用0补充的页面。

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;
}

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

虚拟地址

在计算机中，CPU处理之灵使用的是虚拟地址，虚拟地址通过地址翻译机制转换为物理地址，然后访问内存。但是，有些情况下需要直接使用物理地址进行访问：

1. 内核态下：当操作系统内核运行在特权级别最高的 CPU 模式下时，它可以访问整个物理地址空间。此时，内核可以直接使用物理地址访问系统中的任何内存区域，包括用户态下不可访问的区域。
2. 设备驱动程序：设备驱动程序通常运行在内核态下，用于控制和管理计算机系统中的外部设备。在这种情况下，驱动程序需要直接使用物理地址来访问设备控制寄存器、DMA 缓冲区等硬件资源。
3. 页表初始化：在计算机系统启动时，操作系统需要初始化页表，以便将虚拟地址映射到正确的物理地址。在这种情况下，操作系统需要直接访问物理地址以初始化页表。

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

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

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

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

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

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

// 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)

BUILD_HANDLER tlb do_tlb_refill

#if !defined(LAB) || LAB >= 4
BUILD_HANDLER mod do_tlb_mod
BUILD_HANDLER sys do_syscall
#endif

BUILD_HANDLER reserved do_reserved

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

# 开启中断
LEAF(enable_irq)
	li      t0, (STATUS_CU0 | STATUS_IM4 | STATUS_IEc) 
	# 将协处理器0(COP0)交给当前进程使用 && 4号中断可响应（即计时器中断） && 启用CP0接收中断
	mtc0    t0, CP0_STATUS
	# 修改 SR 寄存器
	jr      ra
	# 返回
END(enable_irq)

# 中断服务函数
timer_irq:
	sw      zero, (KSEG1 | DEV_RTC_ADDRESS | DEV_RTC_INTERRUPT_ACK)
	# 将零值存入一个地址中，该地址表示时钟中断确认寄存器，表示清除时钟中断
	li      a0, 0
	# 将 a0 寄存器的值清零，以便后续操作使用
	j       schedule
	# 跳转到调度函数

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

每隔一个时间片，调用 schedule 函数，如果 count = 0，说明当前进程时间片已用完，切换进程。

课上实验

exam 是实现多用户调度，花了半小时写出来，不需要debug，总体来说没啥问题。

void schedule(int yield) {
	static int count = 0; // remaining time slices of current env
	struct Env *e = curenv;
	static int user_time[5]; // 创建一个用户累计运行时间片数数组
	int tmp[5], i;
	struct Env *env_tmp;
	for (i = 0; i < 5; i++) 
		tmp[i] = 0;
	TAILQ_FOREACH(env_tmp, &env_sched_list, env_sched_link) {
		tmp[env_tmp->env_user] = 1;
	}
	if (count == 0 || yield || e == NULL || e->env_status != ENV_RUNNABLE) {
		if (e != NULL && e->env_status == ENV_RUNNABLE) {
			TAILQ_REMOVE(&env_sched_list, e, env_sched_link);
			TAILQ_INSERT_TAIL(&env_sched_list, e, env_sched_link);
			user_time[e->env_user] += e->env_pri;
		}
		if (TAILQ_EMPTY(&env_sched_list)) {
			panic("schedule: no runnable envs");
		}
		int usr = -1, t = 999999999;
		for (i = 0; i < 5; i++) {
			if (tmp[i] && user_time[i] < t) {
				usr = i;
				t = user_time[i];
			}
		}
		TAILQ_FOREACH(env_tmp, &env_sched_list, env_sched_link) {
			if (env_tmp->env_user == usr) {
				e = env_tmp;
				break;
			}
		}
		count = e->env_pri;
	}
	if (e != NULL) {
		count --;
		env_run(e);
    }
}

extra 卡住的点主要是没有去看 va2pa 函数的实现，即调用 va2pa 时需要 + 偏移。课上提供了一种把 kuseg 转换为 kseg0 然后直接访存的操作。之所以对虚拟地址赋值就是对物理地址赋值是因为 gxemul 进行了转换。

void do_ov(struct Trapframe *tf) {
	curenv->env_ov_cnt++;
	unsigned long epc = tf->cp0_epc;
	u_long value = *(u_long *)epc;
	Pte *pte;
	struct Page *pp = page_lookup(curenv->env_pgdir, epc, &pte);
	u_long kva = KADDR(PTE_ADDR(*pte)) + (epc & 0xfff);
	if ((value&0x3f) == 32) {
		*(u_long *)kva = (value & ~0x3f) | 0x21;
		printk("add ov handled\n");
	} else if ((value&0x3f) == 0x22) {
		*(u_long *)kva = (value & ~0x3f) | 0x23;
		printk("sub ov handled\n");
	} else if ((value>>26) == 0x8) {
		int s = (value >> 21) & 0x1f;
		int t = (value >> 16) & 0x1f;
		u_int imm = (value & 0xffff);
		tf->regs[t] = (tf->regs[s]>>1) + (imm>>1);
		tf->cp0_epc +=4;
		printk("addi ov handled\n");

	}
}