• 前言

    SWAP 挑战性任务主要关于内存管理、进程调度与外设访问，基本只涉及内核的改动，要求对以上的知识有充足的认识与深刻的理解。代码改动总体上不算多（相较于 SHELL 挑战性任务），但根据自己的感受以及别人的描述是 SWAP 任务的思考量相对来说比较大， SHELL 代码量大但是是挑战性任务中思考量最小的一个。我自己花了大概 3 天的时间实现指导书上的所有操作 + 过编译（仅仅只是过编译，很多实现因为理解不到位都有错误），然后花了 3 天的时间 debug。

    我在实现的过程中，pmap.c 改动的内容是最多的，因为其涉及 swap_out、swap_in 以及 TLB 重填逻辑等有关 SWAP 核心机制的实现。ide.c 和 ide.h 是我新增的文件，因为当前 MOS 中对外设的访问是通过文件系统实现的（Lab5 内容），其属于用户进程，并不方便内核去使用，且关键问题在于：Lab5 实现的文件系统是对主 IDE 控制器进行访问的，而 SWAP 挂载的磁盘 swap_disk 由从 IDE 控制器控制，所以需要进行对应的调整才能访问 swap_disk。

    下图是我的代码改动。注释大概有 100 行，因此实际上代码量只有 400 多行。一定有更好的实现方案，我的实现细节上仍有不足。

    理解修正

    在写 SWAP 挑战性任务的过程中，发现自己之前对 MOS 内核的理解仍有不少小错误，并且为实现 SWAP 造成了很大的困扰，不过居然不影响之前的实验。也是写完 SWAP 之后，对内核机制有了更深和更清晰的理解。现将这些理解错误 or 不全面的点罗列一下，以方便后续的实现。

    • 内核虚拟地址空间的布局：在 kseg0 中，0x8040_0000 之前的均为内核所保留的空间，这一点在 kernel.lds 中的 end = 0x8040_0000 可窥见。pmap.c 的 alloc 函数中，freemem 也是从 end 起开始申请空间的。

      由于 OS 实验中使用的物理内存大小为 64 MB，即 0x400_0000，因此 kseg0 中的有效地址最大为 0x8400_0000（即下面布局中的 Physical Memory Max 处）。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      o     4G ----------->  +----------------------------+------------0x100000000
      o                      |       ...                  |  kseg2
      o      KSEG2    -----> +----------------------------+------------0xc000 0000
      o                      |          Devices           |  kseg1
      o      KSEG1    -----> +----------------------------+------------0xa000 0000
      o                      |      Invalid Memory        |   /|\
      o                      +----------------------------+----|-------Physical Memory Max
      o                      |       ...                  |  kseg0
      o      KSTACKTOP-----> +----------------------------+----|-------0x8040 0000-------end
      o                      |       Kernel Stack         |    | KSTKSIZE            /|\
      o                      +----------------------------+----|------                |
      o                      |       Kernel Text          |    |                    PDMAP
      o      KERNBASE -----> +----------------------------+----|-------0x8002 0000    |
      o                      |      Exception Entry       |   \|/                    \|/
      o      ULIM     -----> +----------------------------+------------0x8000 0000-------

    • 内核空间 kseg0 同时存储所有进程的页表，也即不存在两个进程页表项地址相同的情况。这些页表都存放在虚拟地址 0x8040_0000 ~ 0x8400_0000 处。kseg0 中页表的虚拟地址是按页离散存放的，kuseg 的 UVPT 处的页表的虚拟地址则是连续的 4 MB 空间，不过它们都映射到相同的物理页，在物理内存中按页离散存放。

    • 内核空间 kseg0 不使用页式存储管理，即使在页式存储管理机制建立起后，也依然采用直接映射的方式访问物理内存。

    实现过程

    下面我将按照实现的顺序从零到完成来撰写实现过程（与指导书的操作顺序略有不同，主要依据需求顺序来实现）。基本上覆盖了所有的流程，在一些实现细节上还需要思考并作出相应的代码撰写。

    注意：只有被 syscall_mem_alloc 分配的页面才会被 SWAP 机制管理！！！所有其它地方申请的页面一律不纳入 SWAP 管理的范围（为页表申请的页面、passive_alloc 的页面等等）。这一点指导书中有明确。例如若将内核映射的页面换出，而后续访问不经过 TLB 重填，因此原来的那些数据再也访问不到了，而且内核自己也不知道自己访问的是错误的数据。

    schedule 刷新 TLB

    MIPS R4K 并没有在页表项中提供访问标志位,所以需要在每次 schedule 时刷新对应进程的所有 TLB，通过 TLB 重填来检测页面的访问。

    由于我们实现的 MOS 的页表项权限位中没有访问标志位，因此进程在访问某一页面时，内核无法对该页面对应的页表项留下访问痕迹，因此就无法使用 LRU 算法进行页面管理（内核不知道哪个页面是最近访问的，哪个是最久没访问的）。因此需要通过页面控制块 Page 来跟踪页面的访问，并且在每次 schedule 时刷新所有 TLB，通过不断的 TLB 刷新- TLB 缺页重填来检测页面的访问。

    但可以发现的是，这种设计并不能精准跟踪到页面的每一次访问，因为如果一个时间片内多次访问同一个页面，只会被追踪到 TLB 重填的那一次访问，也就是第一次访问。以下是 DeepSeek 老师给出的解释：

    这种设计虽然看起来不够精确，但这种设计在实际操作系统中是可接受的，因为：

    1. 符合 LRU 精神：（1）LRU 的核心是识别”最近使用过”的页面；（2）只要页面在进程活动期间被访问过，就表明它是活跃的；（3）精确记录每次访问反而会增加不必要的开销。
    2. 与 Linux 实现一致：（1）实际 Linux 内核的 LRU 也是近似实现；（2）不是每次访问都更新状态，而是通过定期扫描；（3）使用 PG_referenced 标志而不是精确计数。
    3. 性能考量：（1）避免每次访问都更新链表带来的开销；（2）减少自旋锁的争用（链表操作需要加锁）；（3）保持 TLB 重填处理的轻量化。

    讨论区助教给出了刷新所有 TLB 的代码实现，在 sche.c 的 schedule 合适处直接调用即可。

    新增 TLB 重填逻辑

    上面已经实现了 TLB 刷新，现在就可以实现 TLB 重填时对页面的跟踪了。

    SWAP 机制有两个队列：active_list 和 inactive_list，分别用于存放访问频繁与不频繁的页面。我们在内核需要新增这两个队列，同时为了能够将 Page 插入到队列中，还要在 Page 结构体中新增一个 field 域，可以参考 Lab2 中 page_free_list 的实现。不过由于队列移动时需要将 Page 插入队尾，因此这里新增的两个队列使用 TAILQ 而不是 LIST。此外，队列的更新需要借助 Page 中新增的访问标志位 PG_referenced 来实现。

    注意这里要在 page_init 中作出新增内容对应的初始化，不然后续会出现 address_too_low 等的报错。

    当前的 Page 结构体：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // pmap.h
    struct Page {
    	Page_LIST_entry_t pp_link; /* free list link */
    	u_short pp_ref;
    	/* Challenge begin */
    	u_int PG_referenced;
        u_int swap_available;	// 只有 swap_available 为真才可被换进换出
        // 以下两个变量标记 Page 所在的队列
    	u_int active;
    	u_int inactive;
    	// field 域
    	TAILQ_ENTRY(Page) swap_link;
    	/* Challenge end */
    };

    完善 Page 结构体后就可以依据指导书实现队列的更新操作，这里没有什么难度，不过要注意可换出页面的范围，遇到不能被 SWAP 管理的页面要及时退出。这里建议在 pmap.c 中实现，然后在 tlbex.c 中 _do_tlb_refill 处调用，实现 TLB 重填时的 SWAP 队列更新。

    至此就实现完了内核对页面的跟踪。

    维护 Page 结构体状态

    新增数据

    由于 SWAP 机制将物理页面换出后，需要对所有映射到该物理页的虚拟页进行无效化，并标记为换出页面（这里需要新增一个页表项权限位 PTE_SWAP），因此每一个参与 SWAP 机制的物理页的 Page 都需要存储所有映射到该 Page 的页表项，以便于对它们一齐修改。

    由于修改页表项时还要及时的冲刷对应的 TLB，因此存储页表项时同时存储该页表项对应的虚拟地址以及进程的 asid。为此我在 pmap.h 中新增了一个页表项结构体 Ptentry 用于存储这些数据。

    关于页表项结构体 Ptentry 在 Page 中的存储，我的做法是直接在 Page 结构体中新增一个数组 struct Ptentry pte_list[MAX_PTE_MAP] 来存放。不过由于映射到 Page 的页表项数目不定，更建议的做法是按照指导书的要求来，用链表存储，在 Page 中存放链表头，在内核保留空间中提前申请节点数组。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // pmap.h
    struct Ptentry {
    	u_int valid;	// valid 为 1 表示该页表项结构体存储的内容有效

    	Pte *pte;
    	u_int asid;
    	u_long va;
    };

    struct Page {
    	// ...已有的数据声明
        struct Ptentry pte_list[MAX_PTE_MAP];
    };

    维护操作

    Page 结构体在映射页面时主要需要维护 swap_available 的值以及 Ptentry 数组（链表）。

    • swap_available 表示物理页是否为 SWAP 机制管理。而指导书及上文明确指出只有 syscall_mem_alloc 的页面才可以被管理，因此只要在 sys_mem_alloc 中对 pp->swap_available 赋值为 1 即可。
    • 无论是内核还是用户的页面映射操作，最终都是在内核的 page_insert 和 page_remove 中进行的。因此在这两个函数中调用新增的页表项指针插入/移除操作，即可实现映射到物理页的页表项列表的维护。

    实现 swap_out 与 swap_in

    实现了所有的前置条件后，就可以实现 SWAP 机制的核心内容了。

    这部分会涉及对 swap_disk 的读写操作、页面替换算法以及页控制块状态保存，因此接下来首先实现这些内容。

    读写 swap_disk

    该任务使用 swap_disk 挂载至 MOS 作为 swap 时存储磁盘，与 swap_disk 有关内容参看 PIIX4 简介一节。

    MOS 基于 Malta 开发板，而 Malta 所使用板载的 PIIX4 芯片组支持 IDE 等设备并且拥有两个独立的 IDE 通道。

    每个 IDE 通道连接着一个 IDE 控制器，每个控制器可以连接两块 IDE 设备，故 MOS 中的 PIIX4 最多支持 4 块 IDE 设备。

    两个 IDE 控制器的偏移地址分别为：

    • 主控制器命令块偏移: 0x1F0
    • 从控制器命令块偏移: 0x170

    以上偏移基于 PIIX4 的 PCIIO 基地址 0x18000000，也即 MOS 中定义的 MALTA_PCIIO_BASE。

    读写 IDE 磁盘的操作可以参考 MOS 原有实现，如对 PIO 感兴趣可以参考PIO 文档，此处不再赘述。

    为了避免与文件系统使用的主 IDE 控制器冲突，我们可以在内核态使用从 IDE 控制器读写磁盘，用于存储交换页面。

    可以修改 Makefile 文件中定义的 QEMU_FLAGS 变量来挂载多块磁盘。

    按照挂载顺序 0, 1 号 IDE 磁盘被主控制器使用，而 2 号 IDE 磁盘 swap_disk 则被从控制器使用，swap_disk 文件的创建可以参考 empty_disk。

    根据指导书的内容，我们只需要知道：

    • Lab5 中实现的文件系统使用的 0 号 IDE 磁盘被主 IDE 控制器使用，而 swap_disk 被从 IDE 控制器使用，其被挂载在从 IDE 控制器的 0 号位。
    • 主控制器和从控制器的地址偏移均基于基地址 MALTA_PCIIO_BASE = 0x1800_0000，从控制器的偏移地址为 0x170。
    • 读写 swap_disk 可以参考 MOS 原有实现。

    Lab5 指导书中给出过 MOS 内核态磁盘驱动实现（wait_ide()、read_sector 和 write_sector），因此我们可以直接搬到内核代码中使用。不过原代码中是对主 IDE 控制器的操作，我们还需要根据以上信息定义从控制器相关的宏并作出对应位置的修改，相关信息见 malta.h。另外原代码是对扇区 sector 进行操作，为了方便我们读写 swap_disk 可以改成对磁盘块进行操作（如下 read_block 与 write_block）。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    // 新增内核文件 kern/ide.c
    uint32_t swap_bitmap[SWAP_BITMAP_SIZE] = {0};
    // 在swap_disk中寻找空闲磁盘块
    int alloc_swap_block() { ... }
    // 释放swap_disk中磁盘块
    void free_swap_block(u_int blockno) { ... }
    // 直接抄指导书，MALTA_IDE_XXX换成SWAP的宏
    u_int wait_ide() { ... }
    void read_block(int diskno, int secno, void* dst, u_int nsecs) { ... }
    void write_block(int diskno, int secno, void* src, u_int nsecs) { ... }
    void write_swap_block(u_int blockno, void *va) {
    	write_block(0, blockno * SWAP_SECT2BLK, va, SWAP_SECT2BLK);
    }
    void read_swap_block(u_int blockno, void *va) {
    	read_block(0, blockno * SWAP_SECT2BLK, va, SWAP_SECT2BLK);
    }

    注意内核中新增的文件要在 kern/include.mk 中添加相应的 .o 文件，不然链接时找不到。

    替换算法与 shrink_active_list

    这部分按照指导书的说明实现即可，注意维护 PG_referenced 和所处队列标志 active 与 inactive 值的更新。

    页面控制块状态保存

    我们需要一个能够保存换出页控制块状态的结构体 PageState，首先需要明确哪些东西需要保存。当页面从 swap_disk 中换进后，是作为一个新的非空闲页被使用的，并且还未被插入 SWAP 的两个队列，因此 field 域都无需保存；只有 PG_referenced 为 false 的页面才会被换出，因此 PG_referenced 也无需保存；而能够被换出的页面一定是 swap_available 为 true 的，因此 swap_available 也无需保存。因此我们只需要保存 pp_ref 和 pte_list 就行了。

    此外为了能够在 PageState 数组中检索到指定换出页，还需要存储换出页在 swap_disk 中的位置。

    1
    2
    3
    4
    5
    6
    7
    8
    // pmap.h
    struct PageState {
    	u_int valid;
    	u_int blockno;	// 物理页换出时所在的磁盘块号，用于查找

    	u_short pp_ref;
    	struct Ptentry pte_list[MAX_PTE_MAP];
    };

    最后要在内核中声明 page_state_set 并为其申请空间（我这里依然采用数组存储），其大小我开到了 swap_disk 的磁盘块个数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // pmap.c
    struct PageState *page_state_set;
    void mips_detect_memory(u_int _memsize) {
        // ...
        /* Challenge begin */
    	npage_swap = SWAP_SIZE >> PGSHIFT;
    	printk("[CHALLENGE] swap_disk size: %lu MB, number of pages for swapping: %lu\n", SWAP_SIZE / (1024 * 1024), npage_swap);
    	/* Challenge end */
    }
    void mips_vm_init() {
        // ...
        /* Challenge begin */
    	page_state_set = (struct PageState*)alloc(npage_swap * sizeof(struct PageState), PAGE_SIZE, 1);
    	printk("[CHALLENGE] to memory %x for struct PageState.\n", freemem);
    	/* Challenge end */
        printk("pmap.c:\t mips vm init success\n");
    }

    swap_out 与 swap_in

    实现了上面的准备工作，我们就可以按照指导书的要求来实现 swap_out 和 swap_in 函数了。有以下几个注意点：

    • 涉及修改页表项内容时，一定要记得刷新对应的 TLB 表项。

    • 保存 Page 状态时数据要齐全，初始化 Page 结构体时要完整清零（但不能像我一开始跟傻子一样用 memset(pp, 0, sizeof(struct Page))），恢复 Page 内容时数据要齐全。

    • 指导书中提供了一个巧妙的用于存放换出物理页向 swap_disk 中磁盘块映射关系的方法：

      事实上只需要维护换出物理页向磁盘块的单向映射关系，一种实现方法是当 swap out 时，将对应磁盘块编号代替该换出页对应的所有页表项中的物理页号部分，并利用页表项标记为换出页以便访问时能够识别出为换出页从而进行 swap in。

    • 这一点我不确定其它人是否遇到，但我是在这里卡了好久。在评测 fork 操作时，会不断地调用 syscall_mem_map 进行父子进程间页面的映射，但是只是映射操作，而没有访存操作（指测试程序中的形如 *(char *)(va + i) 操作）。这就会产生一个问题：

      • 如果此时没有空闲页，且映射过程会不断地将页面换入，那么会不断调用 swap_in 中的 swap_out 操作。
      • 事实上每调用一次 swap_out，SWAP 机制的两个队列中就会少一个可换出页，而可换出页的补充操作只有在 TLB 重填时将 Page 插入到这两个队列之一。
      • 那么 fork 过程中不断 swap_out 但是不会访存，也就意味着不会 TLB 重填，不会有新的可换出页补充。这就会导致可换出页越来越少，最后两个队列为空，fork 操作最终卡在了寻找替换页的过程。

      对此，我的解决办法是在 swap_in 的函数末尾加上 update_lru_list 的操作，即将刚换进的页面立马插入到 SWAP 队列中，作为可换出页的补充。

      其实评测并没有测试我们的换出页过程（即选择哪一个页换出），因此只要能够顺利地运转 SWAP 机制的页面换出-换进过程就可以通过评测。

    定期更新 inactive_list

    可以仿照 schedule 中的 count 来实现。

    注意事项

    • 在 debug 时，可以通过在关键节点或者可能发生 bug 的地方打印信息来检测，例如我我是在替换算法函数中打印关键信息，最终发现 swap_in 函数在 swap_out 新页面时卡在了选取换出页面的过程（持续打印 [DEBUG] 信息）。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      struct Page *algo_swap() {
          // ...
      	while(1) {
      		if (TAILQ_EMPTY(&page_inactive_list)) {
      			printk("[DEBUG] also_swap call shrink_active_list!\n");
      			shrink_active_list();
      		}
      		// ...
      	}
      }

    • 由于新增了 SWAP 机制，当 page_lookup 返回的页面为空时可能是因为是原页面被换出了，所以在一些地方需要新增判断条件（是否为换出页）及相应的操作，而不是直接申请一个新页或异常返回。

    • 关于 fork 的协同，实际上只要考虑到上一点的内容，对进行 duppage 的条件补充上换出页就行了。