ucore-lab3

本文最后更新于：2023年6月22日 上午

本实验主要是对页替换算法的实现

woc,有人写了ucore step-by-step,太强了。

知识点

当程序访问内存时，会出现三种情况：

  • 写入一个存在物理页的虚拟页
  • 读一个不存在的页
  • 不满足访问权限

这时就需要缺页处理程序来处理，cpu会把产生异常的线性地址存储到lab2里提到过的cr2寄存器中，并且把页访问异常的错误码存放在中断栈中。

这里只讨论物理页面不够用的时候，应该置换那个物理页面。

需要注意的是，置换页面的选择仅限于当前进程占用的物理页面。

常见的页面置换算法包括课上提到的LRU,近似LRU,在lab3的资料中提到的clock类似于近似LRU。这些置换算法都是局部置换算法。

假如使用全局置换算法，即为进程分配大小可变的物理页面，就需要解决不同的问题：

  • 进程的内存需求的变换
  • 分配给进程的物理页面数

常见的算法有工作集置换算法，通过维护一个固定时间内进程访问的页面（工作集），在访问时换出不在工作集的页面、缺页时换入页面，同时更新访存链表来实现。

另一个算法是缺页率置换算法（PPF），即通过调节常驻集（当前时刻进程实际驻留在内存中的页面集合）的大小来使每一个进程的缺页率保持在一个合理范围内。

上述的局部置换算法以及全局置换算法都可能出现分配物理页面数增加而缺页率上升的异常情况，这被叫做belady现象。

练习

不知道你们怎么知道可以make_grade的

练习0

用meld合并即可

修改的文件：

  • kern/mm/default_pmm.c
  • kern/mm/pmm.c

练习1

完成do_pgfault（kern/mm/vmm.c）函数，给未被映射的地址映射上物理页。

该段代码上方有call graph:

1
CALL GRAPH: trap--> trap_dispatch-->pgfault_handler-->do_pgfault

不得不说，vsc的那个tabnine ai assitant是挂，我还没写完就直接显示出ai分析的代码了，写if的时候直接分析出我想写的代码，纯纯的挂。

exercise1代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
/*LAB3 EXERCISE 1: YOUR CODE*/
//(1) try to find a pte, if pte's PT(Page Table) isn't existed, then create a PT.
if((ptep=get_pte(mm->pgdir,addr,1))==NULL){
    cprintf("get_pte in do_pgfault failed\n");
    goto failed;
}
if (*ptep == 0) {
//(2) if the phy addr isn't exist, then alloc a page & map the phy addr with logical addr
if(pgdir_alloc_page(mm->pgdir,addr,perm)== NULL){
    cprintf("pgdir_alloc_page in do_pgfault failed\n");
    goto failed;
}
}

主要思路就是先查找当前虚拟地址对应的页表项，判断对应的*ptep是不是等于0（不存在），如果不存在就分配一块物理页。

make qemu前记得make clean

结果：

由于实在很难截图，所以这是在练习二完成后截的图

  • 请描述页目录项（Page Directory Entry）和页表项（Page Table Entry）中组成部分对ucore实现页替换算法的潜在用处。

参考hd

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

套娃了属于是

  1. 将发生错误的虚拟地址保存在lab2提到过的cr2寄存器中
  2. 压入EFLAGS,CS,EIP,错误码和中断号至当前的内核栈中
  3. 保存上下文并执行新的缺页中断程序，之后回复上下文
  4. 继续执行当前的缺页处理

练习2

还是在kern/mm/vmm.c里面，不难发现要完成else选项，即物理页面存在的情况；还要完成kern/mm/swap_fifo.c,实现基于fifo的页面替换算法。

kern/mm/vmm.c代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 else { // if this pte is a swap entry, then load data from disk to a page with phy addr
        // and call page_insert to map the phy addr with logical addr
     if(swap_init_ok) {
         struct Page *page=NULL;
         if ((ret = swap_in(mm, addr, &page)) != 0) {
             cprintf("swap_in in do_pgfault failed\n");
             goto failed;
         }    
         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;
     }
}

else代表这个页表项的物理页存在但不在内存中，首先判断是否swap空间初始化完成，如果完成则可以将数据加载到新的在内存的物理页中，将新的物理页与虚拟地址关联，同时将请求的物理页设置为可以swap,即可以被替换。

kern/mm/swap_fifo.c的代码：

1
2
/*LAB3 EXERCISE 2: YOUR CODE*/ 
list_add(head, entry);

只需要加入list的首部即可。

1
2
3
4
5
6
7
8
//(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     
list_entry_t *le = head->prev;
assert(head!=le);
struct Page *p = le2page(le, pra_page_link);
list_del(le);
assert(p !=NULL);
*ptr_page = p;

把list的首个节点删除的操作，学过数据结构应该都熟悉。

结果：

  • 如果要在ucore上实现"extended clock页替换算法"请给你的设计方案，现有的swap_manager框架是否足以支持在ucore中实现此算法？如果是，请给你的设计方案。如果不是，请给出你的新的扩展和基此扩展的设计方案。并需要回答如下问题
    • 需要被换出的页的特征是什么？
    • 在ucore中如何判断具有这样特征的页？
    • 何时进行换入和换出操作？

首先是可以支持的，那么需要被换出的页的特征应该就是PTE_P以及PTE_D均为0的页，也就是换出不存在于内存中且未被其他进程修改的物理页。

其次，根据页结构，显然可以通过位运算查看PTE_P以及PTE_D.

最后，缺页时可以换入，物理页满时换出。根据 的说法，要注意对脏页的处理，

可以在修改dirty的时候写入外存，或者可以在最终要删除该物理页时再写入外存。后者有利于多个写操作的合并，降低缺页代价，但此时的页替换算法却退化成普通的clock算法，而不是extended clock算法了。

challenge1

实现识别dirty bit的 extended clock页替换算法（需要编程）

  • 改进的时钟（Enhanced Clock）页替换算法：在时钟置换算法中，淘汰一个页面时只考虑了页面是否被访问过，但在实际情况中，还应考虑被淘汰的页面是否被修改过。因为淘汰修改过的页面还需要写回硬盘，使得其置换代价大于未修改过的页面，所以优先淘汰没有修改的页，减少磁盘操作次数。改进的时钟置换算法除了考虑页面的访问情况，还需考虑页面的修改情况。即该算法不但希望淘汰的页面是最近未使用的页，而且还希望被淘汰的页是在主存驻留期间其页面内容未被修改过的。这需要为每一页的对应页表项内容中增加一位引用位和一位修改位。当该页被访问时，CPU中的MMU硬件将把访问位置“1”。当该页被“写”时，CPU中的MMU硬件将把修改位置“1”。这样这两位就存在四种可能的组合情况：（0，0）表示最近未被引用也未被修改，首先选择此页淘汰；（0，1）最近未被使用，但被修改，其次选择；（1，0）最近使用而未修改，再次选择；（1，1）最近使用且修改，最后选择。该算法与时钟算法相比，可进一步减少磁盘的I/O操作次数，但为了查找到一个尽可能适合淘汰的页面，可能需要经过多次扫描，增加了算法本身的执行开销。

更改swap_out_victim函数即可。

思路如下：

  • 第一次查找有没有0,0的页，有就换出，同时更改PTE_A为0，重置TLB缓存
  • 第二次查找有没有0,0的页，有就换出，同时更改PTE_D为0，重置TLB缓存
  • 第三次遍历链表必定存在0,0的页，换出即可。

代码及注释：

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
_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
     /* Select the tail */
     for(int i=0;i<3;i++){
         //三次遍历
         list_entry_t *le=head->prev;
         assert(head!=le);
         while(le!=head){
             struct Page *p=le2page(le,pra_page_link);
             pte_t* ptep=get_pte(mm->pgdir,p->pra_vaddr,0);
             if(!(*ptep & PTE_A)&& !(*ptep&PTE_D)){
                 //看是不是0,0
                 list_del(le);
                 assert(p!=NULL);
                 *ptr_page=p;
                 return 0;

             }
             if(i==0)*ptep &= ~PTE_A;
             //第一次查找重置PTE_A
             else if(i==1)*ptep &= ~PTE_D;
             //第二次查找重置PTE_D
             le =le->prev;
             tlb_invalidate(mm->pgdir,le);
             
         }
     }
     return 0;
}

结果：

challenge2没做出来

学长留坑了，我也不想做了打算做一做。

实现不考虑实现开销和效率的LRU页替换算法（需要编程）

既然不考虑开销和效率，那就简单多了，近似LRU都不需要，直接遍历链表。

blog
cs ucore

本文作者: Heeler-Deer
本文链接: https://heeler-deer.top/posts/44602/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！