# Lab3实验报告

## 练习1

### 实现过程

本练习代码量不大，主要在于搞清内在逻辑。`do_pgfault`函数在缺页的时候被触发，表明用户访问的虚拟地址在物理内存中没有映射，这种情况可能是非法访存，也有可能是合理访存。因此该函数首先对非法访存进行检查，即查看`vma`结构中是否有对应映射表项。而该练习的代码部分则负责处理合理访存的情况，这种合理访存引发的页缺失异常又可以划分为如下情况：

- 该页置换算法换到了swap分区中；
- 第一次访问该页，仅在`vma_struct`中存在对应，而没有写入页表，分配物理页。

本练习需要处理第二种情况。这个时候仅需要调用`pgdir_alloc_page`函数即可，该函数会自动分配相关对应的物理页，如果内存不够还会调用`swap_out`函数将不需要的页面换出。

这里需要注意到`check_pgfault`的特殊实现，对之后的应用程序虚存管理有参考意义：在启动阶段已经建立好了`pgdir`（即启动阶段的页目录表，并且将`0xC0000000`之后的区域映射到低地址区域），此时如果直接访问或是读取某个C语言程序中声明的变量，则不会引发`page fault`，因此这里通过指针地址`0x100`进行访问试图引发页缺失。如果实现正确的话，会首先引起`page fault`，进而进行异常处理，以`vma_struct`中的信息填充`PTE`，下次访问的时候就能够直接查询多级页表获得物理地址了。

### 请描述页目录项和页表中组成部分对ucore实现页替换算法的潜在用处

如果要实现扩展时钟算法，则需要使用PTE中的`Access`位和`Dirty`位进行记录该页的历史访问情况。
PDE对实现页替换算法目前没有过多用处。

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

这种情况一般不会发生，除非操作系统内核出现故障。对于x86的CPU，会保存现场，并进入`double_fault`异常而非缺页异常供操作系统开发人员捕捉错误并处理。对于Qemu来说三次出现嵌套缺页异常的话，模拟器就会出错退出。

## 练习2

### 实现过程

本练习的实现代码量也比较小，首先是需要处理上一节中列出两种情况的第一种情况，这个时候需要首先调入该缺失的页，并更新页面置换算法结构体中可以被换出的页。

实现FIFO算法的时候，仅仅需要每次有新页到物理内存的时候将页指针连接到FIFO中，每次需要找出换出的`victim`的时候选择链表末端的页换出即可。

### 在ucore上实现"extended clock页替换算法"

#### 现有的swap_manager框架是否足以支持在ucore中实现此算法？

可以，具体的实现方式可以参照我在挑战性练习中给出的相关说明`lab3-challenge-2014011330.md`。但在实现上来说，硬件还需要帮忙将访问过的页的PTE中的`Access`位或`Dirty`位置1，便于软件读取识别。

#### 需要被换出的页的特征是什么？

在clock链表中进行扫描的时候，如果发现某一个页表项的`Access`位和`Dirty`位均为0，则换出该页。

#### 在ucore中如何判断具有这样特征的页？

仅仅需要获取页对应的`PTE`即可，我在挑战性的说明文档中有相关说明。

#### 何时进行换入和换出操作？

- 换入操作：缺页异常发生之后，需要访问的页不在物理内存中。
- 换出操作：物理内存已满而需要新的内存空间时，需要换出未来最不可能使用的物理页。

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

- 练习1：与参考答案相比缺少了`get_pte`调用相关的`assert`检查，这是因为在`create`参数为1的时候不可能返回空指针。
- 练习2：与参考答案基本思路相同，仅仅在于实现FIFO的时候参考答案以链表首作为队尾，而我的实现中链表首作为队头。

## 实验中的重要知识点

本次实验中重要的知识点有：

- 练习1：虚拟存储的交换技术，虚拟页式存储；
- 练习2：页面置换算法的概念，FIFO算法和时钟算法；

而OS原理中很重要，但在实验中没有对应上的知识点有：

- Belady现象、LRU算法；
- 工作集置换算法等全局置换算法的实现。