# Lab2实验报告

## 练习1

### 原有程序的问题分析

在原有的Lab2代码中给出了一个初始的First-Fit实现，但是无法通过`default_check`函数的`assert`检查。经过分析和调试输出，发现原有程序在维护`free_list`的时候没有考虑到顺序性问题：即低地址的Page结构应该被插入在高地址Page的前方。

显然，如果不考虑顺序性问题，First-Fit算法就不能从低地址开始寻找第一个满足需求的空闲空间，而是从一个不可预知的地址开始随机寻找，会造成碎片问题的严重化，需要进行改进。

### 我的First-Fit程序设计

在我的First-Fit设计过程中，采用了和原有程序相似的思路：在分配空间的时候，仅仅对分配的第一个Page进行标记，并加入`free_list`；在释放空间的时候，需要对前方和后方可能出现的连续空闲块进行合并，这个时候就需要从头开始搜索`free_list`链表，找到和释放空间可以拼接的前一块和后一块，此时需要注意依然要保持上一节所提到的顺序性。另外一个有利于提高效率的做法是：在搜索到当前块的前一块和后一块空闲区域时，就停止搜索，而并非一直搜索到链表末端，从而能加快合并的速度。

对于页属性的设计，`property`位仅当该Page处于`free_list`中时有效，代表了该block中闲置页的个数（包括当前页），而`flags`中的`property`位则被主要用作判断页是否已经被占用。对于其他页来说，考虑到Page结构仅用于内存管理器中，所以对于不存在于`free_list`中的Page来说，我的First-Fit程序不对其`property`进行管理，从而提高效率。

### 进一步改进的空间

实际上，本程序仍然有进一步的改进空间，但是实现起来较为复杂，且考虑到First-Fit算法本身对简洁性和易实现性的要求，我没有进行进一步实现。我对程序改进的一些想法如下：

- 建立多个`free_list`，存储不同大小的空闲块。由于First-Fit算法容易造成低地址碎片，而每次分配需要重新开始扫描浪费时间，因此如果有大空闲块的`free_list`，就可以进一步加快算法。
- 由于当前实现的First-Fit算法每次合并都需要扫描链表查找可以合并的前一块或是后一块，造成时间的浪费，所以可以采用如下两种改进方式：
  - 懒惰的合并算法：由于扫描链表耗时长，合并操作耗时短（尤其当碎片足够多时），可以每隔若干次才重新扫描链表修复合并块；
  - 拉链法：对于分配的块设法建立其可能的上一个空闲块和下一个空闲块指针，合并的时候直接操作指针即可，但这种方式实现复杂，且空闲块指针会随着其他块有所变化。


### 和参考答案的对比和优劣分析

Lab2的文件夹中还提供了一份First-Fit的参考代码，这种算法会将所有的空闲页全部加入`free_list`，当进行页分配的时候，需要遍历链表，进行释放的时候，需要向前和向后查找可以合并的区间块。这样以来，算法在任意时刻能够更好地掌握空闲链表的内容，整个代码的逻辑也更加清楚。细粒度的管理能够使得释放任意页的时候更加方便。

但是，相比于我设计的算法而言，参考答案给出的方法显得略微复杂。对于First-Fit算法来说，核心思想在于找到所有空闲的block，而非Page，找到block之后再想办法进行拆分或是合并。显然，我设计的算法无论在分配空间还是释放空间都只需要考虑空闲的块头指针所组成的链表，能够大大加快内存分配的速度，提高整个操作系统的性能。

## 练习2

我的代码实现如下：

```c
pte_t * get_pte(pde_t *pgdir, uintptr_t la, bool create) {
    pde_t *pdep = pgdir + PDX(la);
    if (((*pdep) & PTE_P) != 1) {
        if (!create) return NULL;
        struct Page* ptPage;
        assert(ptPage = alloc_page());
        set_page_ref(ptPage, 1);
        uintptr_t pa = page2pa(ptPage);
        memset(KADDR(pa), 0, PGSIZE);
        *pdep = ((pa & ~0x0FFF) | PTE_U | PTE_W | PTE_P);
    }
    return ((pte_t*)KADDR((*pdep) & ~0xFFF)) + PTX(la);
}
```

当需要获取页表项的时候，首先要找到对应的页目录项`pdep`，并判断该项是否存在，如果不存在，则考虑建立一个新的页表，并填入相关的页表项`((pa & ~0x0FFF) | PTE_U | PTE_W | PTE_P)`，注意需要调用上一个练习中写好的分配页的接口。最后，需要返回页目录项中所指出的页表中页表项的内容，偏移量即为虚拟地址的11-20位`PTX(la)`。

### 请描述pde和页表pte中每个组成部分的含义和以及对ucore而言的潜在用处

pde和pte本身占用的存储空间为32位，可以当做32位整型处理。下面的内容摘自[Osdev](http://wiki.osdev.org/Paging)

pde的各个组成部分为：

```
31 ----------------- 10 11 -- 9 8 7 6 5 4 3 2 1 0
  4KB对齐的页表起始地址      Avai. G S 0 A D W U R P
```

其中`31-10`位地址为必须，avai可以由软件自由修改，不受kernel或硬件的控制。
考虑到uCore的page大小统一，不存在更换情况，所以S位对uCore无用。

其他位可能的潜在用处如下：
- `A, D, W`：这些与高速缓存相关的位，记录该页是否被访问过、不允许高速缓存过或执行了写穿透策略。如果uCore需要与硬件的cache进行交互（即这些位并非由硬件设定），就需要用到这些位。
- `U`：决定了当前页的访问权限（内核or用户）：uCore可以通过这些位进行用户态和内核态程序访问权限的控制。
- `R`：决定了当前页的是否可写属性：当uCore需要对某一页进行保护的时候，需要用到此位。用于权限控制
- `P`：决定当前页是否存在：uCore需要根据这个标志确定页表是否存在，并是否建立新的相关页表，至关重要。

pte的各个组成部分为：

```
31 ----------------- 10 11 -- 9 8 7 6 5 4 3 2 1 0
      物理页的地址         Avai.  G 0 D A C W U R P
```

许多位与pde相同，不同的位有：
- `C`：与上述的`D`位相同。
- `G`：控制TLB地址的更新策略。
- `D`：该页是否被写过。如果uCore需要对高速缓存实现更复杂的控制则可能用到该位。同时，在页换入或是换出的时候可能需要判断是否更新高速缓存。

### 如果ucore执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情？

在x86的MMU模块进行访存的时候需要进行多级页表查找，如果pde或是pte中标志的页不存在，则会产生Page Fault异常（14号），具体来说CPU会进行下面的操作：

- 保存现场，存储当前的寄存器到主存储器中；
- 设置相应的寄存器记录当前出错程序的地址信息；
- 切换特权级（例如从`ring3`切换到`ring0`）；
- 根据异常号读取idt表，确定ISR的地址，判断是否有进入中断门的权限；
- 跳转到ISR起始地址开始执行。

如果当前已经处于页访问异常的处理例程中，又发生了页访问异常，这对CPU来说是不允许的，会产生double fault异常，这种情况往往说明操作系统编码出现问题。

## 练习3

我的代码实现如下

```c
static inline void page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {
    if (((*ptep) & PTE_P) == 1) {
        struct Page *page = pte2page(*ptep);
        page_ref_dec(page);
        if (page->ref == 0) {
        	free_page(page);
        }
        (*ptep) = 0;
        tlb_invalidate(pgdir, la);
    }
}
```

当移除pte表项的时候，第一步是判断相应的页是否存在，如果存在，则减小对应Page的`ref`，由于`ref`代表引用该物理页的虚拟地址数目，当`ref`减小为0的时候系统应该对该页进行回收，并清空pte。最后一步根据题目所给提示，还应该对tlb表项进行更新，确保一致性。

### 数据结构Page的全局变量（其实是一个数组）的每一项与页表中的页目录项和页表项有无对应关系？如果有，其对应关系？

Page数组主要用于管理物理的连续内存，数组中每一个Page**对应**物理内存中的一个页。页目录存在物理内存的页中，其每一项指向的页表也存储在物理内存的页中，页表中每一项存储的是页的**物理内存地址**，通过这个地址能够找到与之**对应**的Page结构。但Page结构本身是存储在单独的内存区域的（具体来说存储在内核段以上的区域）。

在内核态代码连续的内存管理中（例如`PDE(0e0) c0000000-f8000000 38000000 urw`），页表中的连续页表项对应的Page结构体在内存中也是连续的。

### 如果希望虚拟地址与物理地址相等，则需要如何修改Lab2，完成此事？

在Lab2中，由于地址映射的建立分为多个阶段完成，所以针对不同的阶段需要修改不同的代码以使得虚拟地址和物理地址相等。

**第一阶段** 在Bootloader阶段，线性地址与物理地址相等，无需修改；

**第二阶段** 从`kern_entry`到`enable_paging`函数，主要采用段机制进行地址映射，需要修改的地方为`init/entry.S`中的gdt表项，去除`KERNBASE`有关的定义。此外，还需要修改ucore的链接脚本，将ucore起始的虚拟地址由`0xC0100000`改为`0x00100000`。

**第三阶段** 从`enable_paging`函数开始到`gdt_init`函数，虽然启动了页机制但是未更新段映射，这个时候页机制和段机制对于`0xC0000000`的偏移是叠加的。由于上一阶段已经修改过段机制的代码，这里仅需要将`boot_map_segment`函数调用的`KERNBASE`参数改为0，并取消VPT的递归自映射。这种情况下也没有必要专门建立0-4M物理地址映射，因为即使偏移叠加物理地址和虚拟地址还是相等的（最后有更详细的解释）。

**第四阶段** 之后的阶段由于完全启用了页机制，且页机制的相关参数已经在上一步设置完毕，所以无需修改，虚拟地址自会与物理地址相等。

> 实际上，上述四个阶段也可以分为下面的步骤：启用段机制、启用页机制、更换段机制。整个过程中uCore都必须保证正确的地址映射关系。前期uCore主要使用段机制进行地址偏移、后期uCore则使用页机制进行地址偏移。一个tricky的地方就在于二者的切换：uCore首先建立好偏移的页表，然后将第0项的页表偏移取消，考虑到uCore的内核不会超过4MB，因此在启动页机制之后，内核处的偏移关系仍然是由段机制来维护的。这就保证了启用页表之后，接下来读取gdt表的操作的代码能够正常执行，完成gdt表的修改之后，页机制的映射立刻起作用。此时才可以删除pde索引为0的相关页目录项。这也就解释了为何需要先设立0-4M的页目录项再将其清除的原因。

## 与参考答案的实现区别

- 练习1：已经在相应的小节中体现说明；
- 练习2和练习3：由于根据注释编写代码，所以实现逻辑基本相同。

## 本实验中重要的OS知识点

- 练习1：计算机体系结构和内存层次、连续内存地址分配策略（First-Fit算法和Buddy算法）
- 练习2和练习3：页式存储管理和多级页表，pte和pde的结构

## 实验中没有体现的知识点

- 碎片整理：考虑到uCore并没有管理硬盘，所以没有换入换出功能；
- 段式存储管理：虽然uCore建立了段表，但是没有在实验题目中体现；
- 反置页表。