OS-Lab3-上机回忆 - 操作系统 | CircleCoder = 碼農書架 = 仰望星空

# 前言

又寄了（悲）。这次体验比上次还差，做 exam 时手欠弄了俩 bug ，等 de 完就只剩 3min 了。据贾爹说 extra 非常非常简单，可惜了，又错过了

这次 exam 的设定是真难，是实现 EDF 调度算法。不过有的老师上课已经明确指出了上机会考这个，而且题目描述也很详尽，按要求一步一步来即可。只能说我的手太欠了

至于 extra ，反正贾爹说简单，我扫了一眼感觉和往年题差不多，应该不是很难。看看会不会开放吧

# exam

# 题目要求

# 简述

实现 最早截止期优先 算法，即 EDF 算法。但课下的 RR 算法也要保留。即我们有两个队列，储存不同的进程。

课下的 env_sched_list ，其中的进程通过 RR 算法调度
本次要实现的 env_edf_sched_list ，其中的进程通过 EDF 算法调度

# EDF 算法

其核心思想是：任务的绝对截止时间越早，优先级越高。

使用 EDF 算法调度的进程规定了固定的周期 period 和每个周期内需要运行的时间片 runtime 。（二者的单位都是一个时间片）
每当进程新的周期开始时，由当前时间 current_time + period 得到进程的截止时间 deadline 。
在调度时，会优先选择截止时间最早的进程，其时间片用完后再切换其他进程

# 保留 RR 算法

我们维护了两个队列，并且使用 EDF 算法的进程优先级更高。

只有当 env_edf_sched_list 中的进程时间片都用完时，才会使用 RR 算法去调度 env_sched_list 中的进程。
如果 env_sched_list 中的进程 A 正在运行，而此时 env_edf_sched_list 中的进程 C 进入新周期、时间片重置，那么进程 C 会立即抢占 CPU 。此时进程 A 剩余的时间片保持不变，无需重置

# 示例

现有四个进程 A 、 B 、 C 、 D 按顺序加入对应的调度队列，具体如下：

进程	调度算法	周期	时间片	优先级
`A`	`RR`			1
`B`	`RR`			3
`C`	`EDF`	5	1
`D`	`EDF`	7	2

由于课下 env_sched_list 中新进程从队头加入，所以 B 进程位于队头。

前 10 个时间单位的时序图如下

# 参考步骤

你可以参考如下操作，也可自行实现，保证结果正确即可

# 添加属性和队列

在 include/env.h 的 env 的结构体定义中加入以下成员变量

	LIST_ENTRY(Env) env_edf_sched_link; // 构造 env_edf_sched_list 的链表项
	u_int env_edf_runtime; // EDF 调度参数：进程在每个周期内需要运行的时间片
	u_int env_edf_period; // EDF 调度参数：进程的运行周期
	u_int env_period_deadline; // 进程当前周期的截止时间
	u_int env_runtime_left; // 进程当前周期剩余的时间片

并在该文件中声明采用 EDF 调度算法的进程队列（因为无需删除和插入队尾，所以推荐使用 Lab2 中的 LIST 结构）

	LIST_HEAD(Env_edf_sched_list, Env);
	extern struct Env_edf_sched_list env_edf_sched_list; // EDF 调度队列

# 创建 EDF 调度的进程块

在 kern/env.c 中声明 EDF 调度队列，然后实现新的进程创建函数，用于创建 EDF 算法调度的进程块，并将其加入 env_edf_sched_list 中。此函数可仿照 env_create 函数实现，这里给出初始化成员变量的部分：

	struct Env env_create_edf(const void binary, size_t size, int runtime, int period) {
	//...

	e->env_edf_runtime = runtime;
	e->env_edf_period = period;
	e->env_period_deadline = 0;
	e->env_status = ENV_RUNNABLE;

	//...
	}

在 include/env.h 中声明此函数

# 修改调度函数

修改 kern/sched.c 中的 schedule 函数，具体如下：

	void schedule(int yield)
	{

	static int clock = -1; // 当前时间片，从 0 开始计数
	clock++;

	/* (1) 遍历 env_edf_sched_list，
	如果进程进入了新的运行周期（可通过 clock == env_period_deadline 判断），
	则更新 env_period_deadline，
	并将 env_runtime_left 设置为 env_edf_runtime。 */


	/* (2) 遍历 env_edf_sched_list，
	选取 env_runtime_left 大于 0
	且 env_period_deadline 最小的进程调度
	（若相同，则选择 env_id 最小的进程）。
	如果不存在这样的进程，则不进行调度。 */


	/* (3) 使用课下实现的 RR 算法调度 env_sched_list 中的进程。 */
	static int count = 0; // remaining time slices of current env
	struct Env *e = curenv; // 请根据提示修改这行代码

	}

# 提示

在 schedule 函数中，使用 RR 算法调度时， Env *e 的初值应修改为上次使用 RR 算法调度的进程

可以通过全局变量实现这一点

# 样例说明

样例文件位于 ./test/lab3_edf 目录下

	void mips_init(u_int argc, char argv, char penv, u_int ram_low_size) {
	printk("init.c:\tmips_init() is called\n");

	mips_detect_memory(ram_low_size);
	mips_vm_init();
	page_init();
	env_init();

	ENV_CREATE_PRIORITY(test_hash1, 1);
	ENV_CREATE_PRIORITY(test_hash2, 3);
	ENV_CREATE_EDF(test_hash3, 1, 5);
	ENV_CREATE_EDF(test_hash4, 2, 7);

	schedule(0);
	panic("init.c:\tend of mips_init() reached!");
	}

运行下方命令

make test lab=3_edf && make run

正确输出的前 30 行如下：

	0: 00001802
	1: 00002003
	2: 00002003
	3: 00001001
	4: 00001001
	5: 00001802
	6: 00001001
	7: 00002003
	8: 00002003
	9: 00000800
	10: 00001802
	11: 00001001
	12: 00001001
	13: 00001001
	14: 00002003
	15: 00001802
	16: 00002003
	17: 00000800
	18: 00001001
	19: 00001001
	20: 00001802
	21: 00002003
	22: 00002003
	23: 00001001
	24: 00000800
	25: 00001802
	26: 00001001
	27: 00001001
	28: 00002003
	29: 00002003
	30: 00001802

并且会有以下四行输出（出现的时机和顺序不定）

	env 00001001 reached end pc: 0x00400180, $v0=0x010c4a21
	env 00002003 reached end pc: 0x00400180, $v0=0x0053b1b3
	env 00000800 reached end pc: 0x00400180, $v0=0x00772068
	env 00001802 reached end pc: 0x00400180, $v0=0x00a3dae8

# 我的实现

# env_create_edf 函数

	struct Env env_create_edf(const void binary, size_t size, int runtime, int period) {
	struct Env *e;
	panic_on(env_alloc(&e, 0));

	e->env_edf_runtime = runtime;
	e->env_edf_period = period;
	e->env_period_deadline = 0;
	e->env_status = ENV_RUNNABLE;

	load_icode(e, binary, size);
	LIST_INSERT_HEAD(&env_edf_sched_list, e, env_edf_sched_link);

	return e;
	}

这个挺简单的，没什么坑点

# schedule 函数

	#include <env.h>
	#include <pmap.h>
	#include <printk.h>
	struct Env* lastRREnv = NULL;

	void schedule(int yield)
	{

	static int clock = -1; // 当前时间片，从 0 开始计数
	clock++;

	// (1)
	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;
	}
	}

	// (2)
	u_int minId = 10000005;
	u_int minDaed = 10000005;
	struct Env *tarEnv = NULL;
	LIST_FOREACH (env, &env_edf_sched_list, env_edf_sched_link) {
	if(env->env_runtime_left > 0){
	if(env->env_period_deadline < minDaed){
	minDaed = env->env_period_deadline;
	tarEnv = env;
	}
	else if(env->env_period_deadline == minDaed){
	if(env->env_id < minId){
	minDaed = env->env_period_deadline;
	minId = env->env_id;
	tarEnv = env;
	}
	}
	}
	}

	if(tarEnv){
	tarEnv->env_runtime_left --;
	env_run(tarEnv);
	}


	// (3) 使用课下实现的 RR 算法调度 env_sched_list 中的进程。
	static int count = 0;
	struct Env *e = lastRREnv;

	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);
	TAILQ_INSERT_TAIL(&env_sched_list, e, env_sched_link);
	}
	e = TAILQ_FIRST(&env_sched_list);
	if (e == NULL)
	{
	panic("schedule: no runnable envs\n");
	}
	count = e->env_pri;
	}
	count--;
	lastRREnv = e;
	env_run(e);
	}

我在这里出现了两个 bug ，差点葬于此函数下

tarEnv->env_runtime_left -- :
EDF 调度前要将时间片减 1，否则 EDF 调度的进程会一直抢占 CPU 。
并且这个语句要放在 env_run(tarEnv); 之前，因为 env_run(tarEnv); 后不再返回 schedule 函数
全局变量 lastRREnv 初值为 NULL
这个保持即可，因为 e 为 NULL 时会自动切换到队头进程。而我忘记了这一点（对课下代码掌握不熟），手欠地写成了：
struct Env *e = (lastRREnv) ? lastRREnv : TAILQ_FIRST(&env_sched_list);
这导致一种情况：初始 count == 0 时，我的 env 已是队头进程，然后切换到了下一个进程。这就 WA 了

# 源码仓库

CircleCoder05

Lab2 上机代码仓库

OS 实验