OS2025 上机考试全攻略

Lab 0 Exam

点击查看详细题目

题目描述

点击收起详细题目

点击查看题目解析

题目解析

点击收起题目解析

Lab 0 Extra

点击查看详细题目

题目描述

点击收起详细题目

点击查看题目解析

题目解析

点击收起题目解析

Lab 1 Exam

点击查看详细题目

题目描述

点击收起详细题目

点击查看题目解析

题目解析

点击收起题目解析

Lab 1 Extra

点击查看详细题目

题目描述

点击收起详细题目

点击查看题目解析

题目解析

点击收起题目解析

Lab 2 Exam

点击查看详细题目

题目描述

点击收起详细题目

点击查看题目解析

题目解析

点击收起题目解析

Lab 2 Extra

点击查看详细题目

题目背景

在 Lab2 课下实验中，我们实现了粒度为 4KB 的页式内存管理，在这里，我们将要实现简化的 malloc() 和 free() 函数。

malloc() 函数将会在堆区域申请一个指定大小的内存空间，并且搭配 free() 函数可以实现运行中的内存回收。malloc() 在分配内存空间时，将该空间的几个字节作为管理内存块的元数据，元数据后紧挨着分配给用户的内存空间。在我们的程序中，元数据为一个特别设计的结构体 MBlock，用于记录被切割的内存空间。

MBlock 结构体介绍：

1
2
3
4
5
6
7
8
9
struct MBlock { 
    MBlock_LIST_entry_t mb_link; // 链表控制块（该属性占用 8 字节）

    u_int size; // 该元数据所管理的内存空间大小（该属性占用 4 字节）
    void *ptr; // 该元数据管理内存空间的首地址（即 data 位置，仅作为魔数使用）（该属性占用 4 字节）
    u_int free; // 该元数据所管理内存空间是否空闲，1 为空闲，0 为占用（该属性占用 4 字节）
    u_int padding; // 填充，用于将结构体内存大小对齐到 8 字节（该属性占用 4 字节） 
    char data[]; // 该元数据管理的内存空间，仅用于表示内存空间的首地址，不带有实际含义 
};

其中 data[] 在结构体中并不占用内存空间，如果你用 sizeof(struct MBlock) ，会发现，结构体的大小只有 24 字节，正好是前五项参数的大小，这里的 data[] 是 C 语言的柔性数组，表示在结构体后的任意长度空间，可以看作表示所管理的内存空间的数组。

那么 *ptr 又是什么呢，为什么已经存在 data[] 表示内存空间地址的情况下，还需要 *ptr 这一项呢？实际上，*ptr 是作为魔数存在的，通过使 ptr = data 将内存空间地址保存在元数据内部，而 free 时可以再次检查 ptr == data ，确认当前地址是否是由 malloc 分配得到。

当进行一次分配时，程序会在 MBlock 组成的链表中找到合适的空闲 MBlock ，并切割出足够的空间，用于生成记录新空间的元数据 MBlock 和对应分配出的内存空间。换句话说，MBlock 作为分割符，在一段连续的内存空间中，切割出了一系列内存空间。

通过这种方式，可以实现任意粒度的内存分配，以此来减少页中产生的内碎片，注意，元数据和分配给用户的内存空间应当交替紧邻。

题目描述

在本题中，你需要对 MOS 的内核空间 4MB 虚拟内存提供简化的 malloc() 和 free() 函数。

malloc() 函数在收到分配内存的请求时，会将请求值向上对齐到 8 字节的倍数，并且从链表中找到合适的元数据进行分配，在这里，我们选择 First-Fit 方法，即选择遇到的第一个符合要求的元数据。

当遇到一个元数据时，检查其空间大小是否足以分配需要的内存空间:

  • 如果是，则维护元数据，将需要的空间返回给用户，并通过新建元数据的方式维护未被使用的剩余空间

  • 如果不足，继续遍历链表，寻找下一个元数据
    free() 函数通过 MBlock 中的 ptr 属性检查地址是否是当初被 malloc() 分配出去的地址，之后标记为可用，合并相邻空闲空间。

以进行两次分配和一次释放后的内存为示例，其调用顺序和参数为:

1
2
3
4
void *p1 = malloc(32);
void *p2 = malloc(40);
printk("p1:%x p2:%x\n", (int)p1,(int)p2);
free(p1);

题目要求

在本题中，你需要使用对内核空间的 0x80400000 - 0x80800000 实现动态内存分配和回收。

元数据结构将会在 include/malloc.h 给出，其中结构体有效大小为 24 字节，最后 data 指针不需要实际分配内存，仅表示分给用户的空间位置。

初始将在 0x80400000 处声明一个基础元数据，其可用空间大小为 4MB 减去 24B ，之后从这里作为起点。

同时，我们将提供部分代码（请参看实验提供代码部分），你需要将其粘贴至 kern/pmap.c 之后，并补全或者实现如下函数：

内存的分配 ( void* malloc(size_t size) )

本函数的功能为：

  • 使用 First-Fit 分配大小不低于 size 字节的内存空间：
    ○ 分配成功时，将分配的内存区间的首地址返回。
    ○ 分配失败时，返回值为 NULL 。
  • 分配的内存区间需要满足以下条件：
    ○ 内存区间空闲，也即未被分配。
    ○ 区间应当紧凑，区间和元数据之间不存在无意义的空白区域。
    ○ 内存区间大小为不小于 size 的最小的 8 字节倍数。
    ○ 分配地址应当以 8 对齐。

以下是 malloc() 函数的参考实现方案（你也可以自行实现本函数，但必须保证满足函数定义与功能约束）：

  1. 计算需要分配的 8 字节对齐的字节数。
  2. 从 0x80400080 处开始，遍历链表，直到找到剩余空间大于等于 size 的元数据。
  3. 当需要分配的 size 小于等于剩余空间大小时：
    i. 若剩余空间大小，除去分配给用户的内存空间 size ，剩余大小不足分配一个新的的元数据与至少 8 字节的空闲空间，则剩余空间一齐分配给调用者。
    ii. 若剩余空间大小，除去分配给用户的内存空间 size ，仍剩余一个元数据的空间与对应至少 8 字节的空闲空间可以使用，则在分配的数据空间 size 后，再建立新的元数据，并维护元数据。
  4. 若未找到满足条件的元数据，则返回 NULL 。
  5. 将为用户分配空间的首地址返回用户（data 指针位置），而不是 MBlock 的地址。

注意：

  • 本函数返回的内存区间必须从 0x80400008 - 0x80800800 中取得，并且相邻空间不互相覆盖。
  • 保证调用函数时参数 size 不为 0 ，也不超过 1MB 。
  • 不需要考虑清空对应物理页面中的数据。
  • 不应存在不被元数据管理的内存空间，也不应存在管理空间大小为 0 的元数据。
  • 结合 free() 函数，可能会先后申请总和超过 4MB 的内容。

内存的释放 ( void free(void*p) )

本函数的功能为：

  • 释放 p 对应的内存区间，p 应当是 malloc() 分配的区间首地址，如果不是首地址，则无需释放。
  • 如果释放后，相邻有其他空闲空间，则合并相邻内存空间。

以下是 free() 函数的参考实现方案（你也可以自行实现本函数，但必须保证满足函数定义与功能约束）：

  1. 判断当前地址 p 是否在合理的范围内 [HEAP BEGIN + MBLOCK_SIZE, HEAP_BEGIN + HEAP_SIZE]
  2. 通过当前地址 p 减去 MBLOCK_SIZE 得到 MBlock 应在位置。
  3. 判断当前 MBlock 是否合法，可以通过元数据中指向首地址的指针 ptr == data 判断（保证测试中可以使用）。
  4. 当需要释放空闲区间，且相邻存在空闲区间时：
    i. 若后一个区间空闲，将后元数据清除，空间大小加到当前区间元数据中，修改指针位置，设为空闲。
    ii. 若前一个区间空闲，将当前元数据清除，空间大小加到前区间元数据中，修改指针位置。
  5. 当前后区间均占用：
    i. 将当前空间元数据设为空闲。

注意：

  • 当需要释放的内存区间及其相邻空间均空闲时，必须立即将其合并为更大的空闲区间。
  • 参数 p 可能存在并非通过 malloc() 分配得到的地址，此时 p 不应被释放。
  • malloc.h 中定义的 MBLOCK_PREV 是为本道题简化的前向链表方法，通过 MBLOCK_PREV(elm，field) 可以得到 MBlock 链表前一个元素的指针。
  • 可以用 LIST_FIRST 或者 MBLOCK_PREV 是否指向链表头判断是否是头元素。

任务总结

在提交前，你需要完成以下任务：

  • 完成 malloc() 函数。
  • 完成 free() 函数。
  • 修改 kernel.lds 将 end 设置为 0x80800800

实验提供代码

请将本部分提供代码附加在你的 kern/pmap.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
#include <malloc.h>

struct MBlock_list mblock_list;

void malloc_init() {

    printk("malloc init begin\n");

    LIST_INIT(&mblock_list);

    struct MBlock *heap_begin = (struct MBlock*)HEAP_BEGIN;

    printk("heap begin: 0x%X\n", heap_begin);

    heap_begin->size = HEAP_SIZE - MBLOCK_SIZE;
    heap_begin->ptr = (void*) heap_begin->data;
    heap_begin->free = 1;

    LIST_INSERT_HEAD(&mblock_list, heap_begin, mb_link);

    printk("malloc init end\n");

}

void *malloc(size_t size) {
    /*Your Code Here(1/2)*/
}
void free(void *p) {
    /*Your Code Here(2/2)*/
}
点击收起详细题目

点击查看题目解析

题目解析

点击收起题目解析

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 3 extra 的题目虽然总是异常处理，但和 CO P7 的关系真的不是特别大，毕竟还要照顾一下 CO 没学过异常的同学们。其实只要对 MIPS 指令结构和作用有稍微的了解，就足以拿下这道问题了。

异常的注册在提示部分就已经全部给出了，我们只需要实现 do_adel() 和 do_ades() 两个函数即可。其实只要通读一遍题目，稍作思考就可以发现，这两个函数是一模一样的，除了最后的输出以外没有任何区别。

题目中没有给出具体的实现步骤，现在我们就来拆解一下函数的实现流程：首先我们需要取出当前出现异常的指令，然后对指令进行修改，最后将指令写回原来的位置。接下来我们一步一步实现上面的流程：

第一步其实是最难的一步，很多没看过往年博客的同学直接被硬控到死，到最后家门都没出去。而机智如我发现往年总这么考，直接把这段代码抄在纸上，考试时无脑爆抄，直接助我拿下全考场手刹，所以同学们知道该怎么做了吧（笑）
↑以防大家不知道，再次提醒一下，这门课是开卷考试，可以携带纸质资料入场，下回记得带~

题目的提示部分提过，我们从 tf->cp0_epc 中获取到的地址并不是存放当前指令的真实地址，而是它的虚拟地址。我们需要通过一顿猛如虎的操作将其转化为物理地址，才能将当前指令取出。如果你不能理解下面的代码，记住抄下来就对了！祖传代码，屡试不爽：

1
2
3
4
5
6
7
// kern/traps.c
u_int badva = tf->cp0_epc; // 获取虚拟地址
Pde *pgdir = curenv->env_pgdir; // 获取页目录的基地址
struct Page *p = page_lookup(pgdir, badva, NULL); // 查找虚拟地址所在的页
u_int badpa = page2pa(p) + (badva & 0xfff); // 将页转换为物理地址（不含页内偏移），再加上虚拟地址中的页内偏移部分，构成完整物理地址
u_int *badk0va = 0x80000000 | badpa; // 转换为 kseg0 的虚拟地址（kseg0 起始地址为 0x80000000）
u_int code = *badk0va; // code 的值即为 32 位 MIPS 指令的内容

接下来，我们就需要按照题目中的要求来更改指令了。这一步比较简单，但也有几个需要注意的地方：

首先我们需要注意，这里的修改绝不是直接将当前指令的 offset 低 2 位置 0 。回忆 lw 和 sw 指令的用法，我们可以发现，需要能被 4 整除的并不是最后的 offset 值，而是 GPR[base] + offset 的结果。所以我们需要先计算出这个值，然后根据它对 4 取模的结果调整 offset 。

于是就出现了另外一个问题，就是在计算 GPR[base] 的时候，该如何从寄存器中取值。其实只需要用一步 int gpr_base = (int)tf->regs[base]; 即可取到，但这一步或许也难住了许多英雄汉，属实可惜。

最后就是要时刻注意其中不断变化的数据长度和有无符号问题了。整个代码中涉及到 int u_int signed short 类型的反复转换，虽然写法多种多样（比如我就是乱写的，我也不知道哪些有用哪些没用），但还是要尽量避免类型的隐式转换，让整个计算过程都在我们的可控范围之内。同时也一定要格外注意长度转换带来的有无符号拓展问题，确保 offset 在计算时将 signed short 类型转换为 int 类型：

1
2
3
4
5
6
7
8
9
10
11
// kern/traps.c
u_int base = ((code & 0x03e00000) >> 21); // 取出指令的 21 ~ 25 位作为寄存器的编号
u_int u_offset = (code & 0x0000ffff); // 取出指令的 0 ~ 15 位作为偏移值

int gpr_base = (int)tf->regs[base]; // 从寄存器中取出基地址值
signed short offset = (signed short)u_offset; // 我也不知道这步有没有用，但总之这么写是对的
int now_res = gpr_base + (int)offset; // 算出 GPR[base] + offset 的值
int fix_res = (now_res & ~0x3); // 将上述值的低 2 位置 0
int sub = now_res - fix_res; // 算出置 0 前后的差值
offset = offset - (signed short)sub; // 在 offset 上减去上述差值
code = ((code & 0xffff0000) | ((u_int)offset & 0x0000ffff)); // 将 offset 放回原来的位置

最后一步就是把修复好的指令放回原位置了，因为我们刚才已经算出指令在 kseg0 的虚拟地址了，怎么把它取出来就怎么把它放回去即可。最后别忘了按照题目要求输出：

1
2
3
4
5
6
7
8
// kern/tras.c
*badk0va = code;

// in do_adel():
printk("AdEL handled, new imm is : %04x\n", code & 0xffff);

// in do_ades():
printk("AdES handled, new imm is : %04x\n", code & 0xffff);

最后还是总结一下，毕竟是 extra ，难度还是有一些的，我觉得涉及到地址转换的题目都还挺难的。不过把上面那段八股抄下来直接可秒，后面难度就不太大了，可能涉及到一些位运算的知识，不过我相信大家都能 hold 住。总而言之，多看看往年题，多看看往届博客，好处还是大大的有。大家认真准备，千万不要裸考口牙！

点击收起题目解析

Lab 4 Exam

点击查看详细题目

题目描述

点击收起详细题目

点击查看题目解析

题目解析

点击收起题目解析

Lab 4 Extra

点击查看详细题目

题目背景

在 Lab4 课下实验中，我们已经了解了系统调用机制，并且实现了一个简易的进程间通信（IPC）。但是这样的机制基于单页，并且限于双方进程，我们现在想要实现一个简易的共享内存（Shared Memory，简记为 SHM），能够实现多进程间的不定页数通信。

为了实现这一点，我们需要在内核态维护一个数据结构 struct Shm ，用来维护“一块共享内存”，其各个成员如下：

1
2
3
4
5
struct Shm {
    u_int npage;
    struct Page *pages[N_SHM_PAGE];
    u_int open;
};

其中：

  • npage 表示共享内存总共的页数，在我们的测试中被限制为 [1, N_SHM_PAGE] = [1, 8]
  • pages 为用于共享的物理页面，通过将不同进程的虚拟地址映射到相同的物理页面，可以实现内存共享
  • open 用于维护这一块共享内存的状态，open != 0 表示其已经被分配

在我们的测试中，限制共享内存的数量为 N_SHM = 8 个，使用内核数组维护。数组索引即为它们各自的编号。

系统调用约定

你需要实现下列系统调用，它们的定义与功能如下：

1. int sys_shm_new(u_int npage)

申请总大小为 npage 个页面的共享内存。在申请时，首先找到一个编号最小的、未被分配的（open = 0）的共享内存，并使用 page_alloc 函数申请 npage 个页面，进行必要的操作后，记录在 pages 数组中。

如果找不到这样可用的共享内存，返回 -E_SHM_INVALID 而无需申请页面。如果在申请页面时，空闲页面不足，返回 -E_NO_MEM 。在这个过程中，请避免造成内存泄漏（也即，当发现分配失败时，你需要释放已经分配的页面）。

正确执行后，返回共享内存的编号（数组下标）。

2. int sys_shm_bind(int key, u_int va, u_int perm)

将虚拟地址 va（保证按页对齐）作为共享内存的起始地址，映射到编号为 key 的共享内存中。你需要将虚拟地址范围 [va, va + npage * PAGE_SIZE) 依次映射到共享内存的 npage 个物理页面上。

如果对应的共享内存未被分配（open = 0），则返回 -E_SHM_NOT_OPEN。否则，返回 0 即可。

3. int sys_shm_unbind(int key, u_int va)

将虚拟地址范围 [va, va + npage * PAGE_SIZE) 解除映射（va 保证按页对齐）。简单起见，这里的实现不需要关心这些虚拟地址是否真的被映射到共享内存之中，使用 page_remove 函数移除映射即可。

如果 key 对应的共享内存未被分配（open = 0），返回 -E_SHM_NOT_OPEN 。否则，返回 0 即可。

4. int sys_shm_free(int key)

将 key 对应的共享内存注销（将 open 设为 0），并对页面进行必要的操作，将它们释放。

如果该共享内存原本未被分配，返回 -E_SHM_NOT_OPEN 。否则，返回 0 即可。

测试数据保证在调用 sys_shm_free 前，全部的映射都已经被 unbind 了。

注意事项

  1. 测试数据保证，如果一个进程存在一个绑定了共享内存的页面时，则不会进行 fork ，因为此时的行为没有在题面中给出定义。你不需要考虑这种情形。
  2. 你的实现要能够支持同一个进程不同地址间的共享，同一个进程的不同地址也可以被映射到同一个物理页面上，但测试数据保证，同一个进程的某一虚拟地址不会被多次绑定。你不需要维护虚拟地址与共享内存的关系，仅需要实现系统调用的功能即可。
  3. 对于某个共享内存的页面，可能被绑定多个进程，然后被全部解除绑定，此时，你应该保证这些物理页面仍可以进行新的绑定操作。提示：你可以通过在创建共享内存时，增加页面的 pp_ref 记录，并在销毁共享内存时使用 page_decref 函数释放页面。
  4. 测试数据保证，共享页面中的内存仅作为数组进行访问，而不会存放代码段、栈数据等特殊内容。
  5. 测试程序会使用 IPC 机制进行进程间的同步。

题目要求

user/lib/shm.c 与 include/shm.h 的内容已在初始化分支时向仓库中添加，你可以查看它们的具体内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// include/shm.h
#ifndef _SHM_H_
#define _SHM_H_

#include <mmu.h>
#include <types.h>

#define N_SHM_PAGE 8
#define N_SHM 8

struct Shm {
    u_int npage;
    struct Page *pages[N_SHM_PAGE];
    u_int open;
};

#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// user/lib/shm.c
#include <lib.h>
#include <mmu.h>

int shm_new(u_int npage) {
    return syscall_shm_new(npage);
}

int shm_bind(u_int key, void *va) {
    return syscall_shm_bind(key, (u_int)va, PTE_D);
}

int shm_unbind(u_int key, void *va) {
    return syscall_shm_unbind(key, (u_int)va);
}

int shm_free(u_int key) {
    return syscall_shm_free(key);
}

此外，你可以按照下面的步骤进行：

  1. 在 include/error.h 中，添加下列宏：
1
2
#define E_SHM_INVALID 14
#define E_SHM_NOT_OPEN 15
  1. 在 user/include/lib.h 中，添加下列系统调用的用户态封装，以及库函数声明：
1
2
3
4
5
6
7
8
9
10
11
// syscalls
int syscall_shm_new(u_int npage);
int syscall_shm_bind(int key, u_int va, u_int perm);
int syscall_shm_unbind(int key, u_int va);
int syscall_shm_free(int key);

// shm.c
int shm_new(u_int npage);
int shm_bind(u_int key, void *va);
int shm_unbind(u_int key, void *va);
int shm_free(u_int key);
  1. 在 include/syscall.h 中，向 enum 中添加以下系统调用号。请注意新增系统调用号的位置，应当位于 MAX_SYSNO 之前：
1
2
3
4
SYS_shm_new
SYS_shm_bind
SYS_shm_unbind
SYS_shm_free
  1. 在 user/lib/syscall_lib.c 中添加系统调用封装的具体实现，使用 msyscall 函数陷入内核：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int syscall_shm_new(u_int npage) {
    // Lab4-Extra: Your code here. (1/8)
}

int syscall_shm_bind(int key, u_int va, u_int perm) {
    // Lab4-Extra: Your code here. (2/8)
}

int syscall_shm_unbind(int key, u_int va) {
    // Lab4-Extra: Your code here. (3/8)
}

int syscall_shm_free(int key) {
    // Lab4-Extra: Your code here. (4/8)
}
  1. 在 kern/syscall_all.c 中引入相关的头文件，定义表示共享内存的内核数组，并添加系统调用在内核中的实现函数。请保证函数的定义位于系统调用函数表 void *syscall_table[MAX_SYSNO] 之前：
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
#include <shm.h>

// ... ...

struct Shm shm_pool[N_SHM];

int sys_shm_new(u_int npage) {
    if (npage == 0 || npage > N_SHM_PAGE) {
        return -E_SHM_INVALID;
    }

    // Lab4-Extra: Your code here. (5/8)

    return ??;
}

int sys_shm_bind(int key, u_int va, u_int perm) {
    if (key < 0 || key >= N_SHM) {
        return -E_SHM_INVALID;
    }
    
    // Lab4-Extra: Your code here. (6/8)

    return ??;
}

int sys_shm_unbind(int key, u_int va) {
    if (key < 0 || key >= N_SHM) {
        return -E_SHM_INVALID;
    }

    // Lab4-Extra: Your code here. (7/8)

    return ??;
}

int sys_shm_free(int key) {
    if (key < 0 || key >= N_SHM) {
        return -E_SHM_INVALID;
    }

    // Lab4-Extra: Your code here. (8/8)

    return ??;
}
  1. 在 kern/syscall_all.c 中的 void *syscall_table[MAX_SYSNO] 系统调用函数表中，为步骤 3 中添加的系统调用号添加对应的内核函数指针：
1
2
3
4
[SYS_shm_new] = sys_shm_new,
[SYS_shm_bind] = sys_shm_bind,
[SYS_shm_unbind] = sys_shm_unbind,
[SYS_shm_free] = sys_shm_free,
点击收起详细题目

点击查看题目解析

题目解析

点击收起题目解析

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;
}
点击收起详细题目

点击查看题目解析

题目解析

文件系统服务的添加流程还是非常复杂的，虽然 exam 中已经给出了全部流程，将题目中给的代码复制一下即可，但 extra 就不会有这种张嘴就来的事了，建议大家还是对照着题目中“实现思路”一节好好捋顺一下整个流程，对以后写挑战性任务也很有帮助。

将题目中的代码复制完成之后，我们需要完成的就只剩下 fs/fs.c 中的 find_files() 和 traverse_file() 两个函数了。

首先我们来完成 find_files() 函数，需要调用 walk_path() 函数找到路径名 path 对应的文件，这就需要我们充分了解 walk_path() 函数的构成。

walk_path() 函数定义为 int walk_path(char *path, struct File **pdir, struct File **pfile, char *lastelem) ，其中 char *path 为要寻找的文件的路径，其余三个参数用来存储返回值。若成功找到文件，则 struct File **pdir 为该文件所在的文件夹，struct File **pfile 为该文件本身；若未成功找到文件，但找到了该文件所在的文件夹，则 struct File **pdir 为该文件所在的文件夹， char *lastelem 为该文件的名称。除成功找到文件函数返回 0 以外，其它未找到文件的情况函数均返回负值错误码。

我们现在可以发现，在 find_files() 函数中调用 walk_path() 函数时，是完全用不到第二和第四个参数的，只需要保证在 path 对应的文件存在的情况下能够将文件本身取出就可以了。当然，为了防止访问空指针的情况，我们还是在这些参数的位置塞一些东西进去为好，虽然我们拿到这些数据以后也会转手把它们扔掉。

最后按照题目中定义调用 traverse_file() 函数即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// fs/fs.c
int find_files(const char *path, const char *name, struct Find_res *res) {
    struct File *file = NULL;
    // Lab5-Exam: Your code here. (1/2)
    struct File *pdir = NULL; // actually no use
    char nname[MAXNAMELEN]; // actually no use
    int r = walk_path(path, &pdir, &file, nname); // 只需把 file 取出即可
    if (r < 0) {
        return r;
    }
    // Lab5-Exam: Your code here. (2/2)
    traverse_file(path, file, name, res); // 按定义调用 traverse_file() 函数
    return 0;
}

接下来我们来完成 traverse_file() 函数，根据注释一步一步完成：

1. 检查路径长度是否符合要求，如不符合，直接返回

根据注释提示，若 path 的长度为零或不小于最大路径长度，则返回 -E_BAD_PATH 错误码，使用 strlen() 函数即可：

1
2
3
4
5
// fs/fs.c
if (strlen(path) == 0 || strlen(path) >= MAXPATHLEN /* path 的长度为零或不小于最大路径长度*/) {
    /*返回*/
    return -E_BAD_PATH;
}

2. 比较当前文件名是否等于 name，如果相等则更改 res

观察 res 的结构，我们知道 int 型变量 res->count 存储着查找到的文件的总数量，而字符串数组 res->file_path[] 存储着每个查找到的文件的路径。所以只需要更新这两个变量即可：

1
2
3
4
5
6
7
// fs/fs.c
if (!strcmp(file->f_name, name) /*file 的名字等于 name*/) {
    /*增加 res->count*/
    /*添加 res 的路径*/
    strcpy(res->file_path[res->count], path);
    res->count++;
}

3. 把 path 和 name 拼接起来得到下一层文件路径，注意结尾的 '\0'
提示：我们没有实现 strcat 工具函数，你可以用 strcpy 实现拼接

这一步看似十分简单，实则却暗藏玄机。就因为这一步，我在考场上被硬控了 70 分钟，创下 6 次 exam 的 PW（笑哭），甚至有好多同学直接被硬控两个半小时（是的，这次考试延时了半小时，也是这一届唯一一次 OS 上机延时，不过应该是 extra 出太难了的原因），最后连 exam 都没做上。

本质原因其实是：我们在拼接的时候并不知道 path 的结尾到底有没有 / ！

你或许会问，题目中不是已经保证了 path 均以 / 结尾吗？我会告诉你，traverse_file() 是一个递归函数，这里 path 的值不仅可能是最初输入的 path ，还可能是其中任意一个文件夹的路径。

你或许还会问，只要找到哪些文件路径后面有 / ，哪些后面没有，然后特判一下就好了嘛。是啊，你说得对，可是怎么找到呢？经验之谈，任何尝试找到其中规律或者是尝试特判的方法全部都是错的。我也非常奇怪，为什么评测时的测试点会那么强（如果没记错的话，当时有上千个评测点），很多同学在这里钻牛角尖试图找到规律，结果就打出 GG 了。

最后经过我一番冥思苦想，终于找到了破局之法。说来也简单，甚至可能简单到让大家啼笑皆非。如果我找不到什么时候会缺一个 / ，那我不找了还不行吗？！在拼接的时候，我直接检查当前 path 的结尾是不是 / ，如果不是的话，加一个就好了嘛。是的，就是这么简单，也是这道题的唯一解法。如果你在看到这一段之前就已经想到了这个做法，恭喜你，你肯定比我聪明~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// fs/fs.c
// 3. 把 path 和 name 拼接起来得到下一层文件路径，注意结尾的 '\0'
// 提示：我们没有实现 strcat 工具函数，你可以用 strcpy 实现拼接
strcpy(curpath, path);
int curlen = strlen(curpath);
// 如果 path 不以 '/' 结尾，在后面加一个 '/'
if (curpath[curlen - 1] != '/') {
    curpath[curlen] = '/';
    curlen++; // 别忘了 len++
}
int len = strlen(f->f_name);
// 这里人傻了，明明可以用 strcpy(curpath + curlen, f->f_name) 直接拼接的
for (int j = 0; j < len; j++) {
    curpath[curlen + j] = f->f_name[j];
}
curpath[curlen + len] = '\0'; // 别忘了最后加 '\0'

4. 递归调用 traverse_file 函数

最后按照定义递归调用 traverse_file() 函数，这道题就全部做完了：

1
2
3
// fs/fs.c
// 4. 递归调用 traverse_file 函数
traverse_file(curpath, f, name, res);

还是总结一下吧，这场 exam 对我来说实在是一场苦战，导致最后也没有太多时间做 extra 了，即使续费了半个小时也还是没写完，实在是太痛苦了。考场上确实很容易钻牛角尖，在高压状况下大脑很容易宕机，还是祝愿各位能够保持一个稳定平和的心态，以冷静的头脑和灵活的思维面对层出不穷的突发状况。

点击收起题目解析

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!

点击收起详细题目

点击查看题目解析

题目解析

点击收起题目解析