本实验主要是对页替换算法的实现
woc,有人写了ucore step-by-step,太强了。
当程序访问内存时,会出现三种情况:
这时就需要缺页处理程序来处理,cpu会把产生异常的线性地址存储到lab2里提到过的cr2寄存器中,并且把页访问异常的错误码存放在中断栈中。
这里只讨论物理页面不够用的时候,应该置换那个物理页面。
需要注意的是,置换页面的选择仅限于当前进程占用的物理页面。
常见的页面置换算法包括课上提到的LRU,近似LRU,在lab3的资料中提到的clock类似于近似LRU。这些置换算法都是局部置换算法。
假如使用全局置换算法,即为进程分配大小可变的物理页面,就需要解决不同的问题:
常见的算法有工作集置换算法
,通过维护一个固定时间内进程访问的页面(工作集),在访问时换出不在工作集的页面、缺页时换入页面,同时更新访存链表来实现。
另一个算法是缺页率置换算法(PPF),即通过调节常驻集(当前时刻进程实际驻留在内存中的页面集合)的大小来使每一个进程的缺页率保持在一个合理范围内。
上述的局部置换算法以及全局置换算法都可能出现分配物理页面数增加而缺页率上升的异常情况,这被叫做belady现象。
不知道你们怎么知道可以make_grade的
用meld合并即可
修改的文件:
完成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代码:
12345678910111213 | /*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 addrif(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
结果:
由于实在很难截图,所以这是在练习二完成后截的图
参考hd
套娃了属于是
还是在kern/mm/vmm.c里面,不难发现要完成else选项,即物理页面存在的情况;还要完成kern/mm/swap_fifo.c,实现基于fifo的页面替换算法。
kern/mm/vmm.c代码如下:
1234567891011121314151617 | 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的代码:
12 | /*LAB3 EXERCISE 2: YOUR CODE*/ list_add(head, entry); |
---|
只需要加入list的首部即可。
12345678 | //(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的首个节点删除的操作,学过数据结构应该都熟悉。
结果:
首先是可以支持的,那么需要被换出的页的特征应该就是PTE_P以及PTE_D均为0的页,也就是换出不存在于内存中且未被其他进程修改的物理页。
其次,根据页结构,显然可以通过位运算查看PTE_P以及PTE_D.
最后,缺页时可以换入,物理页满时换出。根据 的说法,要注意对脏页的处理,
可以在修改dirty的时候写入外存,或者可以在最终要删除该物理页时再写入外存。后者有利于多个写操作的合并,降低缺页代价,但此时的页替换算法却退化成普通的clock算法,而不是extended clock算法了。
实现识别dirty bit的 extended clock页替换算法(需要编程)
更改swap_out_victim函数即可。
思路如下:
代码及注释:
12345678910111213141516171819202122232425262728293031323334353637 | 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;} |
---|
结果:
学长留坑了,我也不想做了打算做一做。
实现不考虑实现开销和效率的LRU页替换算法(需要编程)
既然不考虑开销和效率,那就简单多了,近似LRU都不需要,直接遍历链表。