实验题目： Lab3
实验目的
- 了解虚拟内存的Page Fault异常处理实现
- 了解页替换算法在操作系统中的实现
实验环境
操作系统： Ubuntu 20.04 LTS
虚拟机： Vmware Player Workstation 16 Player
依赖： build-essential git qemu-system-x86 gdb make diffutils lib32z1实验内容及操作步骤
本次实验是在实验二的基础上，借助于页表机制和实验一中涉及的中断异常处理机制，完成Page Fault异常处理和FIFO页替换算法的实现，结合磁盘提供的缓存空间，从而能够支持虚存管理，提供一个比实际物理内存空间“更大”的虚拟内存空间给系统使用。
这个实验与实际操作系统中的实现比较起来要简单，不过需要了解实验一和实验二的具体实现。
实际操作系统系统中的虚拟内存管理设计与实现是相当复杂的，涉及到与进程管理系统、文件系统等的交叉访问。
练习0：填写已有实验
涉及改动的文件如下,详见 >>这里<<：
- Lab1
kern/debug/kdebug.c- print_stackframe
kern/trap/trap.c- idt_init
- trap_dispatch
- Lab 2
kern/mm/default_pmm.c- default_init_memmap
- default_alloc_pages
- default_free_pages
kern/mm/pmm.c- get_pte
- page_remove_pte
练习1：给未被映射的地址映射上物理页
参考指导书[1]对kern/mm/vmm.c文件下的do_pgfault函数进行分析。
该函数的传入参数总共有三个：
mm_struct变量，保存了所使用的PDT，合法的虚拟地址空间（使用链表组织），以及与后文的swap机制相关的数据- 产生pagefault的时候硬件产生的error code，可以用于帮助判断发生page fault的原因
- 出现page fault的线性地址（保存在cr2寄存器中的线性地址）
函数执行的时候，先查询mm_struct中合法的虚拟地址链表，确定当前出现page fault的线性地址是否合法，合法则继续执行调出物理页
然后使用error code以及查找到的该线性地址的内存页是否允许读写来判断是否出现了读/写不允许读/写的页这种情况，否则继续执行page fault的处理流程
接下来根据合法虚拟地址的标志，来生成对应产生的物理页的权限
#if 0
/*LAB3 EXERCISE 1: YOUR CODE*/
ptep = ??? //(1) try to find a pte, if pte's PT(Page Table) isn't existed, then create a PT.
if (*ptep == 0) {
//(2) if the phy addr isn't exist, then alloc a page & map the phy addr with logical addr
}而练习一需要补全的，是以下两条：
- 获取当前发生缺页的虚拟页对应的PTE
- 分配物理页，并且与对应的虚拟页建立映射关系
参考注释进行补全：
ptep = get_pte(mm->pgdir, addr, 1); // 获取当前发生缺页的虚拟页对应的PTE
if (*ptep == 0) { // 如果需要的物理页是没有分配而不是被换出到外存中
struct Page* page = pgdir_alloc_page(mm->pgdir, addr, perm); // 分配物理页，并且与对应的虚拟页建立映射关系
} else {
// 将物理页从外存换到内存中，练习2中需要实现的内容
}至于后面else的部分，则是练习2需要补充的内容。
请描述页目录项（Page Directory Entry）和页表项（Page Table Entry）中组成部分对ucore实现页替换算法的潜在用处
关于页目录项跟页表项，在之前LAB2的时候已经进行分析过了。
根据之前的分析，可以发现无论是PTE还是TDE，都具有着一些保留的位供操作系统使用，也就是说ucore可以利用这些位来完成一些其他的内存管理相关的算法，比如可以在这些位里保存最近一段时间内该页的被访问的次数（仅能表示0-7次），用于辅助近似地实现虚拟内存管理中的换出策略的LRU之类的算法；也就是说这些保留位有利于OS进行功能的拓展
如果ucore的缺页服务例程在执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情
参考指导书[1:1]给出的资料，我们可以知道，如果缺页ISR在执行过程中遇到页访问异常，则最终硬件需要完成的处理与正常出现页访问异常的处理相一致，均为：
- 将发生错误的线性地址保存在cr2寄存器中;
- 在中断栈中依次压入EFLAGS，CS, EIP，以及页访问异常码error code，由于ISR一定是运行在内核态下的，因此不需要压入ss和esp以及进行栈的切换；
- 根据中断描述符表查询到对应页访问异常的ISR，跳转到对应的ISR处执行，接下来将由软件进行处理；
练习2：补充完成基于FIFO的页面替换算法
先将练习1后面剩余的要补充的部分拿出来：
/*LAB3 EXERCISE 2: YOUR CODE
* Now we think this pte is a swap entry, we should load data from disk to a page with phy addr,
* and map the phy addr with logical addr, trigger swap manager to record the access situation of this page.
*
* Some Useful MACROs and DEFINEs, you can use them in below implementation.
* MACROs or Functions:
* swap_in(mm, addr, &page) : alloc a memory page, then according to the swap entry in PTE for addr,
* find the addr of disk page, read the content of disk page into this memroy page
* page_insert ： build the map of phy addr of an Page with the linear addr la
* swap_map_swappable ： set the page swappable
*/
if(swap_init_ok) {
struct Page *page=NULL;
//(1）According to the mm AND addr, try to load the content of right disk page
// into the memory which page managed.
//(2) According to the mm, addr AND page, setup the map of phy addr <---> logical addr
//(3) make the page swappable.
}
else {
cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
goto failed;
}参考注释，可以知道我们要做的事情就是：
- 判断当前是否对交换机制进行了正确的初始化；
- 将虚拟页对应的物理页从外存中换入内存；
- 给换入的物理页和虚拟页建立映射关系；
- 将换入的物理页设置为允许被换出；
具体实现如下：
if (swap_init_ok) { // 判断是否当前交换机制正确被初始化
struct Page *page = NULL;
swap_in(mm, addr, &page); // 将物理页换入到内存中
page_insert(mm->pgdir, page, addr, perm); // 将物理页与虚拟页建立映射关系
swap_map_swappable(mm, addr, page, 1); // 设置当前的物理页为可交换的
page->pra_vaddr = addr;
} else {
cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
goto failed;
}然后就是swap_fifo.c文件里面的两个函数：map_swappable和swap_out_vistim
首先看map_swappable
static int
_fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in)
{
list_entry_t *head=(list_entry_t*) mm->sm_priv;
list_entry_t *entry=&(page->pra_page_link);
assert(entry != NULL && head != NULL);
//record the page access situlation
/*LAB3 EXERCISE 2: YOUR CODE*/
//(1)link the most recent arrival page at the back of the pra_list_head qeueue.
return 0;
}我们要做的很简单：将最近使用的页加入到 pra_list_head 队列中，即:
list_add(head, entry);该函数完整代码如下：
static int
_fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in)
{
list_entry_t *head=(list_entry_t*) mm->sm_priv;
list_entry_t *entry=&(page->pra_page_link);
assert(entry != NULL && head != NULL);
list_add(head, entry);
return 0;
}然后是swap_out_vistim函数：
static int
_fifo_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page, int in_tick)
{
list_entry_t *head=(list_entry_t*) mm->sm_priv;
assert(head != NULL);
assert(in_tick==0);
/* Select the victim */
/*LAB3 EXERCISE 2: YOUR CODE*/
//(1) unlink the earliest arrival page in front of pra_list_head qeueue
//(2) assign the value of *ptr_page to the addr of this page
return 0;
}要做的则是选择将要被置换的页，因为使用的 FIFO，因此会找到最先进入队列的页，进行置换。
即:
list_entry_t *entry = head -> prev;
struct Page *page = le2page(entry,pra_page_link);
list_del(entry);
*ptr_page = page;
return 0;完整代码如下：
static int
_fifo_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page, int in_tick)
{
list_entry_t *head=(list_entry_t*) mm->sm_priv;
assert(head != NULL);
assert(in_tick==0);
list_entry_t *entry = head -> prev;
struct Page *page = le2page(entry,pra_page_link);
list_del(entry);
*ptr_page = page;
return 0;return 0;
}如果要在ucore上实现"extended clock页替换算法"请给你的设计方案，现有的swap_manager框架是否足以支持在ucore中实现此算法？
在练习 1 中我们看到页表中拥有 access,和 dirty 位，利用这两个功能位就可以检测页表是否被访问过或者被修改过，从而完成 extended clock 页替换算法
需要被换出的页的特征是什么？在ucore中如何判断具有这样特征的页？何时进行换入和换出操作？
- 需要被换出的页的特征是什么？
最早被加入且未被访问过的页表。 - 在 ucore 中如何判断具有这样特征的页？
将页表与 PTE_A 相与，若为 0，则未被访问过 - 何时进行换入和换出操作？
所需的页不在页表中且页表已满
实验结果及分析
运行make qemu，结果如下：
check_vma_struct() succeeded!
page fault at 0x00000100: K/W [no page found].
check_pgfault() succeeded!
check_vmm() succeeded.
ide 0: 10000(sectors), 'QEMU HARDDISK'.
ide 1: 262144(sectors), 'QEMU HARDDISK'.
SWAP: manager = fifo swap manager
BEGIN check_swap: count 1, total 31961
setup Page Table for vaddr 0X1000, so alloc a page
setup Page Table vaddr 0~4MB OVER!
set up init env for check_swap begin!
page fault at 0x00001000: K/W [no page found].
page fault at 0x00002000: K/W [no page found].
page fault at 0x00003000: K/W [no page found].
page fault at 0x00004000: K/W [no page found].
set up init env for check_swap over!
write Virt Page c in fifo_check_swap
write Virt Page a in fifo_check_swap
write Virt Page d in fifo_check_swap
write Virt Page b in fifo_check_swap
write Virt Page e in fifo_check_swap
page fault at 0x00005000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2
write Virt Page b in fifo_check_swap
write Virt Page a in fifo_check_swap
page fault at 0x00001000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x2000 to disk swap entry 3
swap_in: load disk swap entry 2 with swap_page in vadr 0x1000
write Virt Page b in fifo_check_swap
page fault at 0x00002000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x3000 to disk swap entry 4
swap_in: load disk swap entry 3 with swap_page in vadr 0x2000
write Virt Page c in fifo_check_swap
page fault at 0x00003000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x4000 to disk swap entry 5
swap_in: load disk swap entry 4 with swap_page in vadr 0x3000
write Virt Page d in fifo_check_swap
page fault at 0x00004000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x5000 to disk swap entry 6
swap_in: load disk swap entry 5 with swap_page in vadr 0x4000
write Virt Page e in fifo_check_swap
page fault at 0x00005000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2
swap_in: load disk swap entry 6 with swap_page in vadr 0x5000
write Virt Page a in fifo_check_swap
page fault at 0x00001000: K/R [no page found].
swap_out: i 0, store page in vaddr 0x2000 to disk swap entry 3
swap_in: load disk swap entry 2 with swap_page in vadr 0x1000
count is 0, total is 7
check_swap() succeeded!
++ setup timer interrupts
100 ticks
100 ticks收获与体会
经过这次实验，我了解了虚拟内存的Page Fault异常处理实现，以及页替换算法在操作系统中的实现，对于Ucore操作系统的实现有了更加深入的认识。
评论
ValineWaline