BUAA OS Lab3 上机

exam

往年题资源约等于无。只能对着学长git仓库的源码疯狂地想象题目…

个人认为lab3的exam相对来说随机性比较大，很有extra的风格。

题面大概率是实现一种新的调度算法。

预备任务

在实现这个任务之前，会有许多复制粘贴的操作。

如Env结构体中新属性的增添，新的宏，新的全局变量，新的初始化等等。

这些内容虽然都需要自己手动去改，但是代码基本都已经在题面中明确给出了。

核心任务

新的调度算法的原理在题面上会十分详尽地讲解，容易出现bug的点与解决方法也都有加粗标志。

题面复杂时甚至会直接给出部分实现框架。但是不能过于依赖，可能有重要的句子是没有在框架里体现出来的。

23级题面摘要

实现RR算法与原来的时间片流转算法的混合使用。

每个进程在建立时已经确定它采用哪种调度算法。

RR算法可抢占时间片流转算法。时间片流转被抢占结束后会默认回到被抢占的进程。

大家可以看一下sched.c的核心代码。

除了我添加注释的几行，其他内容都是题面上已经把代码内容全部用文字描述了。

 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


static struct Env* lastenv = NULL; //这句话有简单引导
void schedule(int yield) {
	static int clock = -1;
	clock++;
	struct Env *env; 
	LIST_FOREACH (env, &env_edf_sched_list, env_edf_sched_link) {
		if (clock == env->env_period_deadline) {
			env->env_period_deadline += env->env_edf_period;
			env->env_runtime_left = env->env_edf_runtime;
		}
	}	
	struct Env *en;
	struct Env *min = NULL;
	if (!LIST_EMPTY(&env_edf_sched_list)) {
		min = LIST_FIRST(&env_edf_sched_list);
	}
	LIST_FOREACH (en, &env_edf_sched_list, env_edf_sched_link) {
		if (en->env_runtime_left > 0) {
			if ((min->env_runtime_left <= 0) || (en->env_period_deadline < min->env_period_deadline) || ((en->env_period_deadline == min->env_period_deadline) && (en->env_id < min->env_id))) {
				min = en;
			}
		}
	}
	if (min != NULL && min->env_runtime_left > 0) {
		//printk("%x\n", min->env_id);
		min->env_runtime_left--;  // 这句话是没有提示的
		env_run(min);
		return;
	}


	static int count = 0;
	struct Env *e = lastenv;  //这句话是有简单引导的
	//printk("%x\n", e->env_id);
	if (e == NULL || count == 0 || e->env_status != ENV_RUNNABLE || yield) {
		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);
		}
		e = TAILQ_FIRST(&env_sched_list);
		lastenv = e; //没有引导，但也不需要引导
		//printk("%x\n", e->env_id);
		if (e == NULL) {
			panic("schedule: no runnable envs\n"); 
		}
		count = e->env_pri;
	}
	count--;
	env_run(e);
}

extra

基本上都是书写异常处理函数，可能要调整epc,或者调整指令本身。

题面

点击查看题面

重要代码

不再多说，送你一段重要代码。

这里以I型指令为例。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


	u_long va = tf->cp0_epc;
	Pte *pte;
	page_lookup(curenv->env_pgdir, va, &pte);
	u_long pa = PTE_ADDR(*pte) | (va & 0xfff);
	u_long kva = KADDR(pa);

	int *instr = (int *)kva;
	int opcode = (*instr) >> 26;
	int _base = ((*instr) >> 21) & 0x1f;
	int _rt = ((*instr) >> 16) & 0x1f;
	int imm = (*instr) & 0xffff;

后记

exam做了110min才过，真的是心惊胆战呢。

刚开始是没有min->env_runtime_left--;导致任务一直做不完死循环，但是这个问题读了题面很快就解决了。

不再死循环后，我交上第一发，居然只有30分。根据测试点的正确情况，矛头指向了不同调度算法的抢占。

我本来写的是struct Env *e = (lastenv == NULL) ? TAILQ_FIRST(&env_sched_list) : lastenv;

事实上完全不应该对NULL特判。反而是你自作主张地先定为TAILQ_FIRST(&env_sched_list)，会被视作这个进程已经被执行过了一次的。更何况此时count == 0，第一个进程直接就被吞了。

这个bug我第一次修复失败了，我修复的方法是： if (e != lastenv || e == NULL || count == 0 || e->env_status != ENV_RUNNABLE || yield)

这更是荒唐可笑的，但是e == lastenv就更不对了。

没想到最终正解却是最简单的： struct Env *e = lastenv;

在考场上啼笑皆非。

毕竟这次extra并不难，但已经没时间了。

事后复盘exam也不难，不容易想到的东西都已经告诉你了。个人的启示是exam往往很简单。所以首先想想最简单的语句。