OS2025 上机考试全攻略

Lab 3 Exam

点击查看详细题目

题目描述

课下我们在 MOS 系统中实现了时间片轮转算法（Round-Robin，RR）用于进程调度。在本题中，我们将实现最早截止时间优先算法（Earliest Deadline First，EDF），用于调度周期性进程。

题目要求

在本题中，你需要实现函数 env_create_edf() 用于创建周期性进程，并返回指向被创建进程的进程控制块的指针。该函数声明如下：

struct Env *env_create_edf(const void *binary, size_t size, int runtime, int period);

其中，参数 binary size 与 env_create() 函数中的定义相同，runtime period 为 EDF 调度参数，以时间片为单位：runtime 表示进程在每个周期内需要运行的时间，period 表示进程的运行周期。

在本题中，我们将 MOS 系统两次时钟中断之间的间隔定义为一个时间片，将 MOS 首次调用 schedule() 函数直至下次时钟中断前的间隔作为第 0 个时间片，再次调用 schedule() 函数直至下次时钟中断前的间隔作为第 1 个时间片，以此类推。

对于一个运行周期为 period 的进程来说，其第 t 个周期（从 0 开始计数）的范围为 MOS 的第 [period * t, period * (t + 1)) 个时间片，相应地，进程第 t 个周期的截止时间为 period * (t + 1) 。例如，对于某运行周期为 5 的进程 A，其前三个周期与时间片、时钟中断的对应关系如下图所示：

（这里没有图，请自行脑补）

对于每个使用 env_create_edf() 创建的进程，你需要使用 EDF 算法尽可能保证进程在每个周期内运行 runtime 个时间片，但不一定连续，也不一定运行完（详见调度规则和示例）。

调度规则

新增的 EDF 算法与 MOS 原有的 RR 算法拥有各自独立的调度队列。EDF 调度队列中包含所有使用 env_create_edf() 创建的进程，而 RR 调度队列（MOS 原有的调度队列）中包含所有使用 env_create() 创建的进程。

当时钟中断产生时，若 EDF 调度队列中存在尚未运行完当前周期的时间片的进程，则选取其中截止时间最早的进程调度。如果多个进程的截止时间相同，则选择 env_id 最小的进程调度。

从 EDF 调度队列选取进程后，你仅需使其运行一个时间片，并在下个时钟中断产生时使用第二条规则，重新选择进程调度。本题中要实现的 EDF 调度算法不受 yield 参数和进程优先级的影响，只与进程的截止时间有关。

如果 EDF 调度队列为空，或其中的所有进程均已运行完当前周期的时间片，则使用课下实现的 RR 算法调度 RR 调度队列中的进程。需要注意的是，EDF 调度的进程可以在任何时刻抢占 RR 调度的进程，且 RR 调度的进程运行的时间片在被 EDF 抢占后不发生变化。例如，如果 RR 算法选择调度一个优先级为 5 的进程 A，并已经使其运行了 3 个时间片，此时 EDF 队列中产生了可以被调度的进程 B，则进程 B 会抢占进程 A 的运行，直至进程 B 运行完当前周期的时间片后，进程 A 继续运行剩余的 2 个时间片。

此外，如果在某个周期内，使用 EDF 算法未能保证某进程运行完 runtime 个时间片，则剩余的时间片不会被保留至下一周期，而是直接作废。

示例

进程按照下表的顺序依次加入 RR 调度队列和 EDF 调度队列：

进程名 优先级 每个周期内需要运行的时间片 运行周期
A 1 - -
B 3 - -
C - 1 5
D - 2 7

注：由于课下代码中进程总是插入调度链表的头部，因此 RR 调度队列中的实际顺序为 B、A。

第 0 个时间片，进程 C、D 均位于第 0 个运行周期，未运行完当前周期的时间片，进程 C 截止时间为 5，进程 D 截止时间为 7，选择截止时间最早的进程 C 运行；
第 1 个时间片，进程 C 已运行完当前周期的时间片，而进程 D 未运行完，选择进程 D 运行；
第 2 个时间片，进程 C 已运行完当前周期的时间片，而进程 D 未运行完，选择进程 D 运行；
第 3 个时间片，进程 C、D 已运行完当前周期的时间片，因此选择 RR 调度队列中的进程 B 运行三个时间片；
第 4 个时间片，进程 C、D 已运行完当前周期的时间片，因此继续选择进程 B 运行剩余的两个时间片；
第 5 个时间片，进程 D 已运行完当前周期的时间片，而进程 C 进入第 1 个运行周期，未运行完当前周期的时间片，截止时间为 10，选择进程 C 运行；
第 6 个时间片，进程 C、D 已运行完当前周期的时间片，因此继续选择进程 B 运行剩余的一个时间片；
第 7 个时间片，进程 C 已运行完当前周期的时间片，而进程 D 进入第 1 个运行周期，未运行完当前周期的时间片，截止时间为 14，选择进程 D 运行；
第 8 个时间片，进程 C 已运行完当前周期的时间片，而进程 D 未运行完，选择进程 D 运行；
第 9 个时间片，进程 C、D 已运行完当前周期的时间片，RR 调度队列中的进程 B 已运行完分配的时间片，被移动至调度队列尾部，因此选择进程 A 运行一个时间片；
…

调度流程如下图所示：

（这里没有图，请自行脑补）

参考实现思路

本题参考实现思路如下，你也可以采取其它思路，满足题目要求即可。

在 include/env.h 中添加以下声明：

1
2
3
4
5
LIST_HEAD(Env_edf_sched_list, Env);

extern struct Env_edf_sched_list env_edf_sched_list; // EDF 调度队列

struct Env *env_create_edf(const void *binary, size_t size, int runtime, int period);

注：由于 EDF 算法不需要在队尾插入或取出的操作，因此我们推荐使用 LIST 结构实现 EDF 调度队列。

在 kern/env.c 中添加 env_edf_sched_list 的定义，并在 env_init 函数中初始化 env_edf_sched_list 。

1
struct Env_edf_sched_list env_edf_sched_list; // EDF 调度队列

在 include/env.h 的 Env 结构体中添加以下字段：

1
2
3
4
5
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; // 进程当前周期剩余的时间片

在 kern/env.c 中仿照 env_create() 实现 env_create_edf() 函数，其中需要初始化进程控制块的相关字段，参考如下：

1
2
3
4
5
6
7
8
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; // 初始化为 0，使进程在首次调用 schedule 函数时触发条件判断，进入首个运行周期
    e->env_status = ENV_RUNNABLE;
    ...
}

修改 kern/sched.c 中的 schedule() 函数，实现 EDF 调度算法。参考实现方式如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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; // 请根据提示修改这行代码

    /* 请将 Exercise 3.12 中的代码粘贴至此 */
}

提示

你可以使用 LIST_FOREACH 宏遍历队列，示例如下：

1
2
3
4
5
struct Env *env; // 循环变量

LIST_FOREACH (env, &env_edf_sched_list, env_edf_sched_link) {
    // 在这里对 env 进行操作
}

在课下代码中，我们定义 struct Env *e = curenv ，随后对 e 进行了一系列的判断和操作。在本题中，为了使 RR 算法的调度行为不受 EDF 抢占的影响，你可能需要适当修改这一设计，使 e 的初值为上次使用 RR 算法调度的进程，并在必要时新增全局变量或静态变量。你无需考虑进程退出的情况，详见“评测说明”。如果你在测试样例时遇到 address too low 等访问空指针引发的异常，请检查是否正确实现了这一修改。

评测说明

测试程序的行为仅限于在初始化阶段调用 env_create() 和 env_create_edf() 函数创建一批进程，评测时只评测进程的调度顺序和进程 main() 函数的返回值。

在评测中，我们保证进程运行完 main() 函数后自动进入死循环，而不会主动退出（详见测试目录下的 entry.S 文件）。因此，env_destroy() 、env_free() 函数不会被调用，你无需对它们进行修改。你可以据此结合提示，简化你的实现。

评测中保证不会出现 EDF 调度队列中无可调度进程且 RR 调度队列为空的情况。

点击收起详细题目

点击查看题目解析

题目解析

题目中已经帮我们实现好了全部的定义，将题目中给出的代码复制好后，我们就只需要实现两个内容：一是仿照 env_create() 函数补全 env_create_edf() 函数；二是根据代码中的注释修改 schedule() 函数。

我们首先进行第一步，将 env_create() 函数中为新进程的属性赋值部分替换为题目中给出的内容，再将插入 env_sched_list 队列改为插入 env_edf_sched_list 队列即可（这里需要注意两个队列的类型是不同的，插入时要改用 LIST_INSERT_HEAD ）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// kern/env.c
struct Env *env_create_edf(const void *binary, size_t size, int runtime, int period) {
    struct Env *e;

    env_alloc(&e, 0);

    e->env_edf_runtime = runtime;
    e->env_edf_period = period;
    e->env_period_deadline = 0; // 初始化为 0，使进程在首次调用 schedule 函数时触发条件判断，进入首个运行周期
    e->env_status = ENV_RUNNABLE;

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

    return e; 
}

接下来就是本次 exam 的重难点，即修改 schedule() 函数。在动手操作之前，请一定确保自己完全了解了题目中的调度规则。如果有疑惑的话，可以参考一下题目描述中的“示例”一节，我个人觉得这一节的讲解是最清楚的。

接下来我们跟着注释一步一步完成代码：

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

关于如何更新 env_period_deadline ，从题目描述的示例可以总结出，env_period_deadline 是 env_edf_period 的倍数，每当进程到达截止时间时，将截止时间再加上一倍即可：

1
2
3
4
5
6
7
8
9
10
// kern/sched.c
struct Env *env; // 循环变量

LIST_FOREACH (env, &env_edf_sched_list, env_edf_sched_link) {
    // 这里可以根据提示，使用 LIST_FOREACH 来循环
    if (clock == env->env_period_deadline) {
        env->env_period_deadline += env->env_edf_period;
        env->env_runtime_left = env->env_edf_runtime;
    }
}

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

首先，我们需要通过遍历找出需要调度的 edf 进程。下一步，我们还需要判断进程是否存在。若存在，我们需要调用 env_run() 来运行该进程，同时注意维护 env_runtime_left 变量的值，减去一个时间片：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// kern/sched.c
u_int min = -1; // 截止时间最小的进程的截止时间
struct Env *wheremin = NULL; // 截止时间最小的进程

LIST_FOREACH (env, &env_edf_sched_list, env_edf_sched_link) {
    if (env->env_runtime_left > 0) { // 这里注意判断当前进程是否执行完
        if (min == -1) {
            min = env->env_period_deadline;
            wheremin = env;
        }
        else {
            if (env->env_period_deadline < min || (env->env_period_deadline == min && env->env_id < wheremin->env_id)) {
                min = env->env_period_deadline;
                wheremin = env;
            }
        }
    }
}

if (wheremin != NULL && wheremin->env_status == ENV_RUNNABLE) {
    // 不是很确定是否要判断 status 是否为 ENV_RUNNABLE ，感觉可能不太用
    wheremin->env_runtime_left--;
    env_run(wheremin);
}

(3) 使用课下实现的 RR 算法调度 env_sched_list 中的进程。

到这一步有些同学就看不太懂了，不知道有什么可改的地方，其实有两处是要修改的，当然这就需要我们对本题的调度规则有比较清晰的理解了。

第一处，不知道各位有没有怀疑过注释 (3) 的表述，根据上面的规则和示例，显然只有在 edf 队列中没有找到要调度的 edf 进程时，才会从 RR 队列中选取进程调度，也就是说 (3) 中的调度不是无条件的，这就需要我们将整个 RR 调度的逻辑放在上一步的分支判断中。

第二处，根据代码中的注释和后文的提示都可以看出，我们需要将 RR 调度中的 e 由当前进程 curenv 改为上次执行的 RR 进程。这里我们需要新开一个 static 变量 struct Env *lastRRenv ，每次进行 RR 调度时将当前进程存储进去即可：

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
// kern/sched.c
if (wheremin != NULL && wheremin->env_status == ENV_RUNNABLE) {
    wheremin->env_runtime_left--;
    env_run(wheremin);
}
else {
    static int count = 0;
    static struct Env *lastRRenv = NULL; 
    // 这里必须为静态变量 static ，否则每次调用 schedule() 函数时 lastRRenv 都会被重新定义
    // 仿照 curenv 的定义，初值赋为 NULL
    // struct Env *e = curenv;
    struct Env *e = lastRRenv; // 删去 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);
        lastRRenv = e; // 此时新的 e 已经确定，更新 lastRRenv 的值
        if (e == NULL) {
            panic("schedule: no runnable envs\n");
        }
        count = e->env_pri;
    }
    count--;
    env_run(e);
}

到这里我们就将本次 exam 全部解决了！总的来说，本次 exam 还是非常吃细节的，只有将题目中的调度规则完全搞清楚，并且在做题时不断思考实现细节，时刻记得维护属性值，才能顺利通过测试。

点击收起题目解析

Lab 3 Extra

点击查看详细题目

问题描述

课下实验中，我们主要介绍了异常的分发、异常向量组和 0 号异常（时钟中断）的处理过程。在本次 Extra 中，我们希望大家拓展 4 号异常 AdEL 和 5 号异常 AdES 的异常分发，并在此基础上实现自定义的异常处理。

在 MIPS 指令集中，对这两种异常的描述如下：

ExcCode(异常码) 助记符 描述
4 AdEL 在 load / fetch 指令执行过程中发生的地址错误
5 AdES 在 store 指令执行过程中发生的地址错误

以上错误可能是由于地址不对齐，也可能是由于违反了访问权限。在本次题目中，我们只考虑地址不对齐导致的上述错误，且只考虑 lw 和 sw 指令（即必须四字节对齐）的情况。

且我们要实现自定义的异常处理——通过修改相应的 lw 或 sw 指令，将未 4 字节对齐的地址的低 2 位（二进制格式下）置 0 ，得到符合对齐要求的地址。例如：对于地址0x7f000009 ，需要将其修改为 0x7f000008（即修改后地址 new_addr = old_addr & ~0x3 ），方可得到符合要求的地址。注意，这里我们要求仅修改指令中的立即数部分，不要修改任何寄存器中的值。

在异常处理完成，返回用户态之前，需要输出相应信息：

lw处理完成：

1
printk("AdEL handled, new imm is : %04x\n", new_inst & 0xffff); // 这里的 new_inst 替换为修改后的指令

sw处理完成：

1
printk("AdES handled, new imm is : %04x\n", new_inst & 0xffff); // 这里的 new_inst 替换为修改后的指令

注意上述中的异常处理函数需要完成的输出内容不包含双引号而且应该单独成行，并注意避免其他非必要的输出，否则将影响评测结果。

lw 和 sw 指令的机器码如下：

指令 31…26 25…21 20…16 15…0 行为
lw 100011 base rt imm GPR[rt] <- memory[GPR[base] + (sign-extend)imm]
sw 101011 base rt imm memory[GPR[base] + (sign-extend)imm] <- GPR[rt]

题目要求

建立 AdEL 和 AdES 异常的处理函数，完成异常分发。

在处理函数中，你需要通过修改相应指令以确保重新执行指令时的地址是四字节对齐的。

提示

可以在 kern/genex.S 中，用 BUILD_HANDLER 宏来构建异常处理函数：

1
2
BUILD_HANDLER adel do_adel
BUILD_HANDLER ades do_ades

可以在 kern/traps.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
// 声明 handle 函数
extern void handle_adel(void);
extern void handle_ades(void);

// exception_handlers 请按以下代码实现
void (*exception_handlers[32])(void) = {
    [0 ... 31] = handle_reserved,
    [0] = handle_int,
    [2 ... 3] = handle_tlb,
    [4] = handle_adel,
    [5] = handle_ades,
#if !defined(LAB) || LAB >= 4
    [1] = handle_mod,
    [8] = handle_sys,
#endif
};

void do_adel(struct Trapframe *tf) {
     // 在此实现相应操作以使修改后指令符合要求
}

void do_ades(struct Trapframe *tf) {
     // 在此实现相应操作以使修改后指令符合要求
}

本题涉及对寄存器值的读取。你需要访问保存现场的 Trapframe 结构体（定义在 include/trap.h 中）中对应通用寄存器。

本题涉及对内存的访问，由于我们要修改的指令部分在 kuseg 区间，这一部分的虚拟地址需要通过 TLB 来获取物理地址。我们设置了程序中保存操作指令代码的 .text 节权限为只读，这部分空间在页表中仅被映射为 PTE_V ，而不带有 PTE_D 权限，因此经由页表项无法对物理页进行写操作。可以考虑查询 curenv 的页表获取对应指令的物理地址，再转化为 kseg0 的虚拟地址，从而修改相应内容。

本题要求自定义行为是要修改对应的指令的立即数部分，而不是通过在内核态用四字节对齐的地址直接获得数据，在这种做法下使用 epc + 4 跳过异常将无法通过测试。

题目约束

保证地址出错当且仅当 lw 和 sw 访问的地址未四字节对齐！

保证不会出现取指发生 AdEL 或 AdES 异常！

不保证 lw 和 sw 指令的立即数为正数，但保证异常指令的初始立即数和按要求修改后的立即数都在 signed short (16位) 的取值范围内！

地址不对齐的指令中立即数对应的地址可能是四字节对齐的，即地址不对齐可能是寄存器的值未对齐，但本题要求仅修改指令中的立即数部分！

保证可以仅通过修改立即数部分的方式得到正确结果！

点击收起详细题目

点击查看题目解析

题目解析

点击收起题目解析

Lab 5 Exam

点击查看详细题目

题目背景 & 题目描述

在 Linux 系统中，find 命令是一条很常用的命令，它支持根据多种条件筛选文件，并把文件的路径输出。比如根据路径、名字来匹配相应的文件：

find / -name "motd"

该命令在根目录下查找名为 motd 的文件，并把找到的所有文件的路径输出。

在本次测试中，我们希望同学们实现一个支持以基础路径和文件名为条件查找文件的简易版函数
int find(const char *path, const char *name, struct Find_res *res) 。该函数在 path（都以绝对路径给出）对应的文件及其子目录中递归查找名字为 name 的文件，并把查到的文件的绝对路径和文件总数结果存入 res 指向的预定义结构体，只有文件名和 name 完全一致才视作匹配，无需支持通配符。

struct Find_res 定义在了 user/include/lib.h 中，file_path 用于存查到的路径，count 用于存查到的文件数量。我们保证在本次测试中，该结构体足够装下所满足条件的路径，不会溢出。同时你需要注意我们修改了 MAXPATHLEN ，本题中你需要用宏来表示最大路径长度。

1
2
3
4
5
#define MAXPATHNUM ((PAGE_SIZE - sizeof(int)) / MAXPATHLEN)
struct Find_res {
    char file_path[MAXPATHNUM][MAXPATHLEN];
    int count;
};

函数正常执行则返回 0 ，错误时对应的负错误码，本题保证只会出现两种错误，均已经在 lab5 课下实现，即查找 path 对应文件的时候没找到或者路径太长。如果在 path 对应的文件目录下查找名字为 name 的文件过程中发现路径过长，则跳过该路径继续处理其他路径即可，不视作错误。

需要注意的是，本函数的匹配的规则和标准 find <path> -name "<name>" 实现一致，你可以在跳板机上尝试运行 find 命令，查看一些特殊情况下标准行为（例如 <path> 定位的文件名字恰为 <name> ，提示：在本题中，这种情况下你需要把这个文件包括在查询结果中），为了简化实现，我们保证测试点中 <path> 对应的文件如果能够找到，一定是目录类型，同时，为了简化实现，我们保证所有测试点中，path 均以路径分隔符 / 结尾。

实现思路

在 user/include/lib.h 中我们已经给出了所需的查询结果结构体，你无需再复制：

1
2
3
4
5
#define MAXPATHNUM ((PAGE_SIZE - sizeof(int)) / MAXPATHLEN)
struct Find_res {
    char file_path[MAXPATHNUM][MAXPATHLEN];
    int count;
};

你可以使用文件系统服务进程来完成整个查找过程。可以在用户函数中添加如下请求接口:

在 user/include/lib.h 的 file.c 注释下新增声明：

1
int find(const char *path, const char *name, struct Find_res *res)

将该函数 find() 的实现复制到 user/lib/file.c ：

1
2
3
int find(const char *path, const char *name, struct Find_res *res) {
    return fsipc_find(path, name, res);
}

(请注意，本次 lab5-exam 只需要通过编译，就可以通过第一个测试点并拿到 50 分，如果后续完成确实有困难，你需要根据上面的思路添加 find() 函数的声明和实现，并把 find() 的函数体内部 return fsipc_find(path, name, res); 改成 return 0; ，这样能用最少的行数通过编译，并通过第一个测试点。如果想完整实现本题目要求的所有功能，请忽略这一段话)

在 user/include/fsreq.h 中的枚举类型中增加一个对于文件系统的请求类型 FSREQ_FIND ，请注意要把它放在 MAX_FSREQNO 前。

在同一文件 user/include/fsreq.h 里面加上请求结构体：

1
2
3
4
struct Fsreq_find {
    char req_path[MAXPATHLEN];
    char req_name[MAXNAMELEN];
};

在 user/include/lib.h 的 fsipc.c 的注释下新增声明：

1
int fsipc_find(const char *path, const char *name, struct Find_res *res);

在 user/lib/fsipc.c 中将该函数的实现复制过去：

1
2
3
4
5
6
7
8
9
10
11
int fsipc_find(const char *path, const char *name, struct Find_res *res) {
    if (strlen(path) == 0 || strlen(path) > MAXPATHLEN) {
        return -E_BAD_PATH;
    }
    struct Fsreq_find *req = (struct Fsreq_find *)fsipcbuf;
    strcpy((char *)req->req_path, path);
    strcpy((char *)req->req_name, name);

    int r = fsipc(FSREQ_FIND, req, res, 0);
    return r;
}

然后在文件系统服务函数中实现服务接收和递归查找：

仿照其他项，在 fs/serv.c 的服务函数分发表 serve_table 最后新增一项 [FSREQ_FIND] = serve_find,

在 fs/serve.c 的分发表上方将 serve_find() 函数的实现复制过去：

1
2
3
4
5
6
7
8
9
10
void serve_find(u_int envid, struct Fsreq_find *rq) {
    struct Find_res res __attribute((aligned(PAGE_SIZE))) = {};
    int r = find_files(rq->req_path, rq->req_name, &res);
    if (r) {
        ipc_send(envid, r, 0, 0);
    }
    else {
        ipc_send(envid, 0, (const void*)&res, PTE_D | PTE_LIBRARY);
    }
}

在 fs/serv.h 中添加声明：

1
int find_files(const char *path, const char *name, struct Find_res *res)

然后在 fs/fs.c 中完成 fs/find_files() 函数，实现本服务的核心功能。你可以先使用 walk_path() 函数找到 path 对应的文件夹，然后再文件夹下寻找名字恰为 name 的文件。你可以参照 fs/fs.c 文件里的 dir_lookup() 学会对文件的各个块进行访问，不过需要注意 dir_lookup() 不支持递归查找，你需要用深度优先搜索支持递归查找(下一条提示给出了参考实现)：

1
2
3
4
5
6
7
8
int find_files(const char *path, const char *name, struct Find_res *res) {
    struct File *file;
    // 用 walk_path 来找到 path 对应的文件夹
    // Lab5-Exam: Your code here. (1/2)

    // 在 path 对应的文件夹下面遍历，找到所有名字为 name 的文件，你可以调用下面的参考函数 traverse_file
    // Lab5-Exam: Your code here. (2/2)
}

你可以用任意正确的方式实现 (2/2) 部分，这里用一个提供了一个参考实现函数，你只需要按注释填写四个空：

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
int traverse_file(const char *path, struct File *file, const char *name, struct Find_res *res) {
    u_int nblock;
    nblock = file->f_size / BLOCK_SIZE;

    // 1. 检查路径长度是否符合要求，如不符合，直接返回
    if (/* path 的长度为零或不小于最大路径长度*/) {
        /*返回*/
    }

    // 2. 比较当前文件名是否等于 name，如果相等则更改 res
    if (/*file 的名字等于 name*/) {
        /*增加 res->count*/
        /*添加 res 的路径*/
    }
    if (file->f_type == FTYPE_DIR) {
        for (int i = 0; i < nblock; i++) {
            void *blk;
            try(file_get_block(file, i ,&blk));
            struct File *files = (struct File *)blk;

            for (struct File *f = files; f < files + FILE2BLK; ++f) {
                char curpath[MAXPATHLEN + MAXNAMELEN + 1];
                // 3. 把 path 和 name 拼接起来得到下一层文件路径，注意结尾的 '\0'
                // 提示：我们没有实现 strcat 工具函数，你可以用 strcpy 实现拼接
                // 4. 递归调用 traverse_file 函数
            }
        }
    }
    return 0;
}
点击收起详细题目

题目解析

Lab 5 Extra

点击查看详细题目

本题涉及文件系统诸多细节，若题面表述有不清楚之处，请及时询问助教。

题目背景

当前， MOS 的文件系统将数据以明文的形式保存在磁盘上，这埋下了数据泄漏的隐患，所有用户都可以直接读取任意文件，磁盘意外被他人获取后也可以直接读取数据。

为了消除这些隐患，加密文件系统的概念被提出。通过对文件或文件夹进行加密，可以防止未授权的访问。同时，加密文件系统提供了透明性，只需要正确配置密钥，合法用户可以使用既有方式，且对加密解密过程无感地读写文件。加密解密工作将由文件系统自动完成。

Windows 中的 NTFS 文件系统支持这样的功能。右键一个文件，在菜单中点击“属性”，在属性窗口中的“常规”选项卡中点击“高级”按钮，在高级属性窗口中可以看到“加密内容以便保护数据”​​。

我们可以在 MOS 现有的文件系统的基础上实现简单的加密文件系统。我们实现的加密文件系统需要支持对于普通文件的加密，不需要考虑对于目录的加密，同时需要提供一定的透明性。

加密算法

我们的加密文件系统的加密算法是异或加密。

异或运算 (XOR) 满足 d ^ k = e ， e ^ k = (d ^ k) ^ k = d 。所以异或加密的加密和解密方法是相同的。对于原文，与密钥进行异或运算，即可得到密文；对于密文，与密钥进行异或运算，即可得到原文。

当然，异或加密安全性较低，易被攻破。实际的加密文件系统采用 AES 算法或者更强大的非对称加密算法。

在 MOS 的文件系统中，文件内容被组织为一系列的磁盘块 (block)，每个磁盘块的大小为 4096 字节（由 user/include/fs.h 中的 BLOCK_SIZE 定义）。基于此，我们的加密文件系统的异或加密也是以磁盘块为单位进行的。具体地，规定密钥长度为磁盘块的大小，即 4096 字节。加密时，对于文件内容的一个磁盘块的各个字节，将其与密钥的各个字节进行异或，即可得到密文。由上述异或运算性质，通过同样的方法可以由密文得到原文。

上述过程用 C 语言代码可以如下表示：

1
2
3
4
5
6
unsigned char *blk;
unsigned char encrypt_key[BLOCK_SIZE];

for (int i = 0; i < BLOCK_SIZE; i++) {
    blk[i] ^= encrypt_key[i];
}

密钥以未加密的普通文件在磁盘中存储。合法的密钥文件满足文件内容至少有两个磁盘块并且第一个磁盘块的第一个字为 FS_MAGIC（在 user/include/fs.h 中定义）。文件其余字节可为任意值。规定密钥存储于合法的密钥文件的第二个磁盘块。

系统行为

结合 MOS 现有的文件系统，为了使加密文件系统提供一定的透明性，使用加密文件系统操作文件的整体过程为：加载密钥 > 打开文件 > 读写操作 > 关闭文件 > 卸载密钥。

具体地，我们的加密文件系统的行为分为两部分，一是用户态程序与文件系统进行的交互，二是文件系统服务 fs/serv.c 的加密解密工作。

（一）用户态程序使用声明于 user/include/lib.h 的函数与文件系统进行交互。

已经实现的文件系统功能不应受影响。

通过已有的 open() 函数以加密方式打开一个文件，调用函数时需要额外给 open() 函数的第二个参数 mode 或运算 O_ENCRYPT 。如果当前未加载密钥，应返回 -E_BAD_KEY 。

由 MOS 的文件系统设计，使用 open() 函数打开文件时会将文件的所有磁盘块读取到内存中，故可以利用文件系统服务 fs/serv.c 的文件解密功能实现该异常处理。

通过已有的 close() 函数关闭一个以加密方式打开的文件。如果当前未加载密钥，应返回 -E_BAD_KEY 。

由 MOS 的文件系统设计，所有磁盘块直到使用 close() 函数关闭文件时才会写入磁盘，故可以利用文件系统服务 fs/serv.c 的文件加密功能实现该异常处理。

通过已有的 read() ，write() ，seek() 等函数进行读写和其他操作。调用读取函数时，读出的内容应为解密后的原文。调用写入函数时，传入的是未加密的原文，但应将加密后的密文写入磁盘。

通过新增的 int fskey_set(int fd) 函数加载密钥。参数 fd 为使用 open() 函数以非加密且允许读的方式打开密钥文件返回的文件描述符。如果文件描述符不合法，或以加密方式打开，或打开方式为只写，则返回 -E_INVAL 。函数通过 IPC 调用文件系统服务 fs/serv.c 的密钥加载功能并返回 IPC 的返回值。

通过新增的 int fskey_unset() 函数卸载密钥。函数通过 IPC 调用文件系统服务 fs/serv.c 的密钥卸载功能并返回 IPC 的返回值。

通过新增的 int fskey_isset() 函数判断当前是否加载密钥。函数通过 IPC 调用文件系统服务 fs/serv.c 的状态查询功能并返回 IPC 的返回值。

（二）加密解密工作由文件系统服务 fs/serv.c 完成。

系统状态：记录当前文件系统服务是否已经加载密钥，同时缓存加载的密钥。缓存密钥是为了实现只要加载了密钥，多个读写进程就可以利用文件系统服务使用相同的密钥以加密方式读写文件。同时，即使打开的密钥文件在完成密钥加载操作后被关闭，也不会影响到加密解密工作。

密钥加载：判断当前状态是否已加载密钥，如果已加载密钥，IPC 返回 -E_BAD_KEY ；如果未加载密钥，读取通过 IPC 传入的打开的文件，并判断该文件是否为合法密钥文件。如果不合法，IPC 返回 -E_INVALID_KEY_FILE ；如果未加载密钥且密钥文件合法，读取文件中的密钥并缓存，同时将当前状态标记为已加载密钥。

密钥卸载：判断当前状态是否已加载密钥，如果未加载密钥，IPC 返回 -E_BAD_KEY 。如果已加载密钥，则将当前状态标记为未加载密钥，并且清除密钥缓存。
状态查询：如果当前状态已加载密钥，IPC 返回 1，如果未加载密钥，IPC 返回 0。

文件解密：从磁盘读取以加密方式打开的文件的磁盘块时，判断当前状态是否已加载密钥，如果未加载密钥，IPC 返回 -E_BAD_KEY 。如果已加载密钥，在完成磁盘块读取后对其进行解密。

文件加密：写入以加密方式打开的文件的磁盘块到磁盘时，判断当前状态是否已加载密钥，如果未加载密钥，IPC 返回 -E_BAD_KEY 。如果已加载密钥，对原文进行加密后写入对应磁盘块。

（三）说明：

O_ENCRYPT 需在 user/include/lib.h 中定义。

-E_INVALID_KEY_FILE 和 -E_BAD_KEY 需在 include/error.h 中定义。

fskey_set() 、fskey_unset() 和 fskey_isset() 函数需在 user/include/lib.h 中声明并在 user/lib/file.c 中实现。

若没有发生错误，应当 IPC 返回 0 。

参考实现

只需要满足加密算法和系统行为的要求，各种实现方式都是可以接受的。下面给出一种参考实现方式。

在 include/error.h 中合适位置定义 -E_INVALID_KEY_FILE 和 -E_BAD_KEY 。

1
2
#define E_INVALID_KEY_FILE 14
#define E_BAD_KEY 15

在 user/include/fsreq.h 中增加新的文件系统服务 IPC 请求号，并定义新的请求结构体。

1
2
3
4
5
6
7
8
9
10
11
enum {
    ......
    FSREQ_KEY_SET,
    FSREQ_KEY_UNSET,
    FSREQ_KEY_ISSET,
    MAX_FSREQNO,
};

struct Fsreq_key_set {
    int req_fileid;
};

在 user/include/lib.h 中合适位置声明新增的函数和 IPC 函数，并定义 O_ENCRYPT 。

1
2
3
4
5
6
7
8
9
int fsipc_key_set(u_int fileid);
int fsipc_key_unset();
int fsipc_key_isset();

int fskey_set(int fd);
int fskey_unset();
int fskey_isset();

#define O_ENCRYPT 0x0010

在 fs/serv.c 中定义相关变量用于标记当前状态和缓存密钥，实现相关的服务函数，并且添加到 serve_table 中。密钥文件的要求见“加密算法”一节。

提示：可以参考 fs/fs.c 的 dir_lookup() 和 read_super() 函数。

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
static int encrypt_key_set = 0;
static unsigned char encrypt_key[BLOCK_SIZE];

void serve_key_set(u_int envid, struct Fsreq_key_set *rq) {
    // 判断当前状态是否已加载密钥，如果已加载密钥， IPC 返回 -E_BAD_KEY

    // 利用 open_lookup 找到对应的 Open 结构体，判断文件大小是否至少有两个磁盘块大小
    // 利用 file_get_block 读取文件的第一个磁盘块，判断第一个字是否为 FS_MAGIC
    // 如果密钥文件不合法， IPC 返回 -E_INVALID_KEY_FILE

    // 利用 file_get_block 读取文件的第二个磁盘块，将密钥复制到 encrypt_key 中

    // 将当前状态标记为已加载密钥

    // IPC 返回 0
}

void serve_key_unset(u_int envid) {
    // 判断当前状态是否已加载密钥，如果未加载密钥， IPC 返回 -E_BAD_KEY

    // 将当前状态标记为未加载密钥

    // 将密钥缓存 encrypt_key 清零

    // IPC 返回 0
}

void serve_key_isset(u_int envid) {
    // IPC 返回当前状态
}

void *serve_table[MAX_FSREQNO] = {
    ......
    [FSREQ_KEY_SET] = serve_key_set,
    [FSREQ_KEY_UNSET] = serve_key_unset,
    [FSREQ_KEY_ISSET] = serve_key_isset,
};

查看 user/lib/file.c 中的 open() 函数，确保对 fsipc_map() 函数的调用返回错误代码时，该错误代码将作为 open() 函数的返回值。

提示：可以使用 try() 宏。

修改 fs/serv.c 中的 serve_map() 函数。在读取文件磁盘块之前，判断该文件是否是以加密方式打开的，如果是，判断当前是否已加载密钥，如果未加载密钥， IPC 返回 -E_BAD_KEY ，不将读取到磁盘块内存地址通过 IPC 共享。对于以加密方式打开的文件，读取文件磁盘块之后，对读取到的磁盘块进行解密。解密算法见“加密算法”一节。

修改 fs/serv.c 中的 serve_close() 函数。在调用 file_close() 将磁盘块写入之前，判断这个文件是否是以加密方式打开的，如果是，判断当前是否已加载密钥，如果未加载密钥， IPC 返回 -E_BAD_KEY ，不进行后续的磁盘写入操作。对于以加密方式打开的文件，对文件的所有磁盘块进行加密后再调用 file_close() 进行磁盘写入。加密算法见“加密算法”一节。
提示：可以参考 fs/fs.c 的 file_flush() 函数。

在 user/lib/file.c 中实现 fskey_set() 、 fskey_unset() 和 fsipc_key_isset() 。在 user/lib/fsipc.c 中实现 fsipc_key_set() 、fsipc_key_unset() 和 fsipc_key_isset() 函数，合理调用 user/lib/fsipc.c 与文件系统服务 fs/serv.c 进行 IPC 。

提示：可以参考 user/lib/file.c 中的 ftruncate() 函数。与文件系统服务进行 IPC 的编程方式可以参考 user/lib/file.c 和 user/lib/fsipc.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
/* user/lib/file.c */
int fskey_set(int fdnum) {
    // 使用 fd_lookup 找到对应的 Fd 结构体。判断传入的文件描述符是否合法
    // 如果不合法返回 fd_lookup 函数的返回值（该函数除了0之外，只会返回 -E_INVAL 错误码，符合系统行为要求）

    // 判断文件是否以加密方式打开，判断打开方式是否为只写
    // 密钥文件要求以非加��且允许读的方式打开，不满足则返回 -E_INVAL

    // 通过对 Fd 结构体进行处理获得 fileid ，合理调用相应文件系统 IPC 函数
}

int fskey_unset() {
    // 合理调用相应文件系统 IPC 函数
}

int fskey_isset() {
    // 合理调用相应文件系统 IPC 函数
}

/* user/lib/fsipc.c */
int fsipc_key_set(u_int fileid) {
    // 合理调用 fsipc 函数
}

int fsipc_key_unset(void) {
    // 合理调用 fsipc 函数
}

int fsipc_key_isset(void) {
    // 合理调用 fsipc 函数
}

说明

所有测试点的密钥均与下发样例的密钥不同。硬编码下发的密钥无法通过评测。

MOS 的文件系统可能存在一定的缺陷，保证各评测点均不考察下发代码中非填写部分的已有设计或者潜在缺陷。特别说明以下三种情况：

现有部分函数的实现方式可能导致文件描述符无法被回收。评测保证在文件描述符相关功能实现正确的前提下，打开的文件数量不会耗尽可用的文件描述符。

现有 close() 函数的行为是无论关闭过程是否发生了错误，都会将传入的文件描述符释放。评测保证如果调用 close() 函数关闭文件时发生了错误（如未加载密钥），不会对已被释放的文件描述符再次调用 close() 等文件操作函数。

现有的磁盘块映射到内存机制是在已有映射的情况下不会再次从磁盘读取该磁盘块，然而文件系统服务的全周期并不会解除映射。这会导致未写入磁盘的数据据滞留内存且不会再读取磁盘中对应磁盘块的原始数据。评测保证调用 close() 函数关闭文件时发生了错误（如未加载密钥），不会以加密或非加密方式重新打开该文件进行读写。

在线评测时，所有的 .mk 文件、所有的 Makefile 文件、init/init.c 以及 tests/ 和 tools/ 目录下的所有文件都可能被替换为标准版本，因此请同学们本地开发时，不要在这些文件中编写实际功能所依赖的代码。

可能今天是很多同学最后一次参与 OS 限时测试了。无论是否完成了今天所有的题目，OS 实验课程的学习是顺利还是遗憾，都恭喜你，祝福你！希望之后 OS 和其他课程的学习顺利！

如果你也希望传递 OS 实验课程的学习经验与心得，有热情参与 OS 实验课程的建设中。欢迎加入 OS 实验课程助教团队，敬请留意后续通知。 Let’s be the S.T.A.R. of OS!

点击收起详细题目

题目解析