lab3
练习0：填写已有实验
需要修改的文件：
default_pmm.c:
static struct Page *default_alloc_pages(size_t n) {
assert(n > 0);
if (n > nr_free) { //如果所有的空闲页的加起来的大小都不够，那直接返回NULL
return NULL;
}
list_entry_t *le, *len;
le = &free_list; //从空闲块链表的头指针开始
while((le=list_next(le)) != &free_list) {//依次往下寻找直到回到头指针处,即已经遍历一次
struct Page *p = le2page(le, page_link);//将地址转换成页的结构
if(p->property >= n){ //由于是first-fit，则遇到的第一个大于N的块就选中即可
int i;
for(i=0;i<n;i++){//递归把选中的空闲块链表中的每一个页结构初始化
len = list_next(le);
struct Page *pp = le2page(le, page_link);
SetPageReserved(pp);
ClearPageProperty(pp);
list_del(le);//从空闲页链表中删除这个双向链表指针
le = len;
}
if(p->property>n){
(le2page(le,page_link))->property = p->property - n;//如果选中的第一个连续的块大于n，只取其中的大小为n的块
}
ClearPageProperty(p);
SetPageReserved(p);
nr_free -= n;//当前空闲页的数目减n
return p;
}
}
return NULL;//没有大于等于n的连续空闲页块，返回空
}
//#################################################################################
static struct Page *default_alloc_pages(size_t n) {
assert(n > 0);
if (n > nr_free) { //如果所有的空闲页的加起来的大小都不够，那直接返回NULL
return NULL;
}
list_entry_t *le, *len;
le = &free_list; //从空闲块链表的头指针开始
while((le=list_next(le)) != &free_list) {//依次往下寻找直到回到头指针处,即已经遍历一次
struct Page *p = le2page(le, page_link);//将地址转换成页的结构
if(p->property >= n){ //由于是first-fit，则遇到的第一个大于N的块就选中即可
int i;
for(i=0;i<n;i++){//递归把选中的空闲块链表中的每一个页结构初始化
len = list_next(le);
struct Page *pp = le2page(le, page_link);
SetPageReserved(pp);
ClearPageProperty(pp);
list_del(le);//从空闲页链表中删除这个双向链表指针
le = len;
}
if(p->property>n){
(le2page(le,page_link))->property = p->property - n;//如果选中的第一个连续的块大于n，只取其中的大小为n的块
}
ClearPageProperty(p);
SetPageReserved(p);
nr_free -= n;//当前空闲页的数目减n
return p;
}
}
return NULL;//没有大于等于n的连续空闲页块，返回空
}
//#############################################################################
static void default_free_pages(struct Page *base, size_t n) {
assert(n > 0);
assert(PageReserved(base));
list_entry_t *le = &free_list;
struct Page *p;
//查找base位置
while((le=list_next(le)) != &free_list){
p = le2page(le, page_link);
if(p>base)
break;
}
//将页插入到空闲页
for(p = base; p<base+n; p++){
p->flags = 0;
set_page_ref(p, 0);
ClearPageReserved(p);
ClearPageProperty(p);
list_add_before(le, &(p->page_link));
}
base->property = n;
SetPageProperty(base);
//高位地址合并
p = le2page(le,page_link) ;
if(base+n == p){
base->property += p->property;
p->property = 0;
}
//低位地址合并
le = list_prev(&(base->page_link));
p = le2page(le, page_link);
if(p==base-1){
while (le != &free_list) {
if (p->property) {
p->property += base->property;
base->property = 0;
break;
}
le = list_prev(le);
p = le2page(le, page_link);
}
}
nr_free += n;
return ;
}
//####################################################################
pmm.c:
static inline void page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep)
{
if (*ptep & PTE_P) { //如果页表项存在
struct Page *page = pte2page(*ptep); //找到页表项
page_ref_dec(page);
if (page->ref == 0) { //如果只有当前进程引用
free_page(page); //释放页
}
*ptep = 0; //设置页目录项为0
tlb_invalidate(pgdir, la); //修改的页表是进程正在使用的页表，使其无效
}
}
kdebug.c:
void print_stackframe(void) {
uint32_t t_ebp = read_ebp();
uint32_t t_eip = read_eip();
int i,j;
for(i = 0;i< STACKFRAME_DEPTH && t_ebp!=0;i++)
{
cprintf("ebp=%08x,eip=%08x,args:",t_ebp,t_eip);
uint32_t *args = (uint32_t *)t_ebp +2;
for(j = 0;j<4;j++)
{
cprintf("0x%08x",args[j]);
}
cprintf("\n");
print_debuginfo(t_eip-1);
t_eip = ((uint32_t *)t_ebp)[1];
t_ebp = ((uint32_t *)t_ebp)[0];
}
}
trap.c:
ticks ++; //每一次时钟信号会使变量ticks加1
if (ticks==TICK_NUM) {//TICK_NUM已经被预定义成了100，每到100便调用print_ticks()函数打印
ticks=0;
print_ticks();
} ticks ++; //每一次时钟信号会使变量ticks加1
if (ticks==TICK_NUM) {//TICK_NUM已经被预定义成了100，每到100便调用print_ticks()函数打印
ticks=0;
print_ticks();
}
}
//###############################################################
void idt_init(void) {
extern uintptr_t __vectors[];
int i;
//初始化idt
for(i=0;i<256;i++)
{
SETGATE(idt[i],0,GD_KTEXT,__vectors[i],DPL_KERNEL);
}
SETGATE(idt[T_SWITCH_TOK],0,GD_KTEXT,__vectors[T_SWITCH_TOK],DPL_USER);
SETGATE(idt[T_SWITCH_TOU],0,GD_KTEXT,__vectors[T_SWITCH_TOU],DPL_KERNEL);
lidt(&idt_pd);
练习1：给未被映射的地址映射上物理页
要求：
完成do_pgfault（mm/vmm.c）函数，给未被映射的地址映射上物理页。设置访问权限 的时候需要参考页面所在 VMA 的权限，同时需要注意映射物理页时需要操作内存控制结构所指定的页表，而不是内核的页表。
1、VMA分析：
struct vma_struct {
// the set of vma using the same PDT
struct mm_struct *vm_mm;
uintptr_t vm_start; // start addr of vma
uintptr_t vm_end; // end addr of vma
uint32_t vm_flags; // flags of vma
//linear list link which sorted by start addr of vma
list_entry_t list_link;
};
/*
vm_start和vm_end描述的是一个合理的地址空间范围（即严格确保 vm_start < vm_end的关系）；
list_link是一个双向链表，按照从小到大的顺序把一系列用vma_struct表示的虚拟内存空间链接起来，并且还要求这些链起来的vma_struct应该是不相交的，即vma之间的地址空间无交集；
vm_flags表示了这个虚拟内存空间的属性，目前的属性包括
*/
#define VM_READ 0x00000001 //只读
#define VM_WRITE 0x00000002 //可读写
#define VM_EXEC 0x00000004 //可执行
/*vm_mm是一个指针，如果说vma描述和管理的是一系列虚拟内存块结构，那么mm则用来描述，究竟是哪个应用程序使用了这些vma，它们是通过vma中的成员mm联系在一起的。mm也有五个成员：*/
struct mm_struct {
// linear list link which sorted by start addr of vma
list_entry_t mmap_list;
// current accessed vma, used for speed purpose
struct vma_struct *mmap_cache;
pde_t *pgdir; // the PDT of these vma
int map_count; // the count of these vma
void *sm_priv; // the private data for swap manager
};
/* mmap_list是双向链表头，链接了所有属于同一页目录表的虚拟内存空间
mmap_cache是指向当前正在使用的虚拟内存空间
pgdir所指向的就是 mm_struct数据结构所维护的页表
map_count记录mmap_list里面链接的vma_struct的个数
sm_priv指向用来链接记录页访问情况的链表头*/
2、函数实现：
实现思路&&函数分析：
三个传入参数分别是：应用程序虚拟存储总管mm、错误码error_code和具体出错的虚拟地址addr。
函数功能是对可能出现页访问错误的情况的处理和报错。
对虚拟地址进行判断，如果虚拟地址的范围超过了限制，或者是虚拟地址无法被查找到，即可以说该地址是不合法的，进行了一次非法访问，那么可以直接报错。
对目标访问页的权限判断，比如对一个只读页进行写操作，或者读了一个不可读的页，那么此时可以直接报错。错误码的低2位分别是：P标志（位0）最低位：表示当前的错误是由于不存在页面（0）引起，还是由于违反访问权限（1）引起。W / R标志（位1）：表示当前错误是由于读操作（0）引起还是还是写操作（1）引起。
如果能够顺利通过上述的合法性判断，那么此次虚拟内存访问就被认为是合法的，此时，页访问异常的原因，是由于该合法虚拟页，没有对应物理页的映射导致，因此下一步要建立起这个映射。通过当前应用程序mm所指向的一级页表，以及虚拟地址，去查询有没有对应的二级页表，get_pte函数会进行搜索，如果没有，那么get_pte函数会新建一个二级页表产生对于，如果创建失败则会返回一个NULL，然后报错。
如果是上述新创建的二级页表，那么*ptep就会是0，代表页表为空，此时调用pgdir_alloc_page，对它进行初始化建立映射关系，如果不为0则表示已有对应的映射，需要进行映射的替换。
int do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
int ret = -E_INVAL;
//#############对虚拟地址进行判断##################
//尝试寻找包括addr的vma
struct vma_struct *vma = find_vma(mm, addr);
pgfault_num++;
//判断addr是否在vma的范围中
if (vma == NULL || vma->vm_start > addr) {
cprintf("not valid addr %x, and can not find it in vma\n", addr);
goto failed;
}
//############对目标访问页的权限判断###############
switch (error_code & 3) {
default:
/* error code flag : default is 3 ( W/R=1, P=1): write, present */
case 2: /* error code flag : (W/R=1, P=0): write, not present */
if (!(vma->vm_flags & VM_WRITE)) {
cprintf("do_pgfault failed: error code flag = write AND not present, but the addr's vma cannot write\n");
goto failed;
}
break;
case 1: /* error code flag : (W/R=0, P=1): read, present */
cprintf("do_pgfault failed: error code flag = read AND present\n");
goto failed;
//如果无法读取直接报错
case 0: /* error code flag : (W/R=0,read, not present */
if (!(vma->vm_flags & (VM_READ | VM_EXEC))) {
cprintf("do_pgfault failed: error code flag = read AND not present, but the addr's vma cannot read or exec\n");
goto failed;
}
}
uint32_t perm = PTE_U;//prem:给物理页赋予权限的中间变量
if (vma->vm_flags & VM_WRITE) {
perm |= PTE_W;
}
addr = ROUNDDOWN(addr, PGSIZE);
ret = -E_NO_MEM;
pte_t *ptep=NULL;
/*##################修改部分#####################*/
//查找页目录，如果不存在则失败
if ((ptep = get_pte(mm->pgdir, addr, 1)) == NULL) {
cprintf("get_pte in do_pgfault failed\n");
goto failed;
}
if (*ptep == 0) { // 如果是新创建的二级页表。
//初始化建立虚拟地址与物理页之间的映射关系
if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
//初始化失败报错并退出。
cprintf("pgdir_alloc_page in do_pgfault failed\n");
goto failed;
}
}
/*#################练习二实现##################*/
//页表项非空，尝试换入页面
else {
if(swap_init_ok) {
struct Page *page=NULL;
//根据mm结构和addr地址，尝试将硬盘中的内容换入至page中
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);
//建立虚拟地址和物理地址之间的对应关系，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;
}
}
/*#################修改部分#######################*/
ret = 0;
failed:
return ret;
}
3、请描述页目录项（Pag Director Entry）和页表（Page Table Entry）中组成部分对ucore实现页替换算法的潜在用处
分页机制的实现确保了虚拟地址和物理地址之间的对应关系。一方面，通过查找虚拟地址是否存在于一二级页表中可知发现该地址是否是合法的；同时可以通过修改映射关系实现页替换操作。另一方面，在实现页替换时涉及到换入换出：换入时需要将某个虚拟地址对应的磁盘的一页内容读入到内存中，换出时需要将某个虚拟页的内容写到磁盘中的某个位置。而页表项可以记录该虚拟页在磁盘中的位置，为换入换出提供磁盘位置信息，页目录项则是用来索引对应的页表。同时，我们可知PDE和PTE均保留了一些位给操作系统使用，具体可以应用在页替换算法时。present位为0时CPU不使用PTE上内容，这时候这些位便会闲置，可以将闲置位用于保存别的信息，例如页替换算法被换出的物理页在交换分区的位置等。同时，需要注意到dirty位，操作系统根据脏位可以判断是否对页数据进行write through。
4、如果ucore的缺页服务例程在执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情？
首先调用中断机制，引起中断
保存现场：将发生错误的线性地址保存在cr2寄存器中;并在中断栈中依次压入
EFLAGS，CS, EIP。并且把访问异常码error code保存到中断栈；
根据中断描述符表查询到对应页访问异常的ISR，跳转到对应的ISR处执行，实 现缺页服务例程
练习二：补充完成基于FIFO的页面替换算法（需要编程）
1、完善do_pgfault函数
swap_init_ok是一个标记位，代表交换初始化成功，可以开始替换的过程了。首先声明了一个页，之后将结构mm、虚拟地址和这个空页，调用了swap_in函数。该函数首先为传入的空页page分配初始化，之后获取了mm一级页表对应的二级页表，通过swapfs_read尝试将硬盘中的内容换入到新的page中，最后，建立起该页的虚拟地址和物理地址之间的对应关系，然后设置为可交换，该页的虚拟地址设置为传入的地址。至此，do_pgfault结束，建立起了新的映射关系，下次访问不会有异常。
2、FIFO替换算法：
先进先出(First In First Out, FIFO)页替换算法：该算法总是淘汰在内存中驻留时间最久的页予以淘汰。只需把一个应用程序在执行过程中已调入内存的页按先后次序链接成一个队列，队列头指向内存中驻留时间最久的页，队列尾指向最近被调入内存的页。这样需要淘汰页时，从队列头很容易查找到需要淘汰的页。
3、_fifo_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);
list_add(head, entry); //将最近用到的页面添加到次序队尾
return 0;
}
4、_fifo_swap_out_victim函数
函数功能：
查询哪个页面需要被换出,并执行换出操作
实现思路：
使用链表操作，删除掉最早进入的那个页，并按照注释将这个页面给到传入参数ptr_page。
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 *le = head->prev; // 取出链表头，即最早进入的物理页面
assert(head!=le); // 确保链表非空
struct Page *p = le2page(le, pra_page_link);
//找到对应的物理页面的Page结构
list_del(le); //将进来最早的页面从队列中删除
assert(p !=NULL);
*ptr_page = p; //将这一页的地址存储在ptr_page中
return 0;
}
结果验证：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Efvr4G2d-1639279481645)(E:\Typore图片\1638683145806.png)]
5、需要被换出的页的特征是什么？
最早被换入，且最近没有再被访问的页
6、在ucore中如何判断具有这样特征的页？
通过判断是否访问过，对未访问过的物理页FIFO即可
7、何时进行换入和换出操作？
当需要调用的页不在页表中时，并且在页表已满的情况下，会引发PageFault，此时需要进行换入和换出操作**。**具体是当保存在磁盘中的内存需要被访问时，需要进行换入操作；当位于物理页框中的内存被页面替换算法选择时，需要进行换出操作。
扩展练习 Challenge：实现识别dirty bit的 extended clock页替换算法（需要编程）
代码实现：
如果状态是(0, 0)，说明当前数据无效且没有被修改，只需将该物理页面从链表上去下，该物理页面记为换出页 面，且不需要将其写入swap分区；如果状态是(1, 0), 将该物理页对应的虚拟页的PTE中的访问位都置成0，然后指针跳转到下一个物理页面；如果状态是(0, 1)，则将该物理页对应的虚拟页的PTE中的dirty位改成0，并且将该物理页写入到外存中，然后指针跳转到下一个物理页；如果状态是(1, 1)，则该物理页的所有对应虚拟页的PTE中的访问为置成0，然后指针跳转到下一个物理页面；
static int
_extend_clock_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);
// 第一次查找 !PTE_A & !PTE_D，同时重置当前页的PTE_A
// 第二次查找 !PTE_A & !PTE_D， 同时重置当前页的PTE_D
// 第三次查找，肯定能找到
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))
{
list_del(le);
assert(p !=NULL);
*ptr_page = p;
return 0;
}
// 如果在第一次查找中，访问到了一个已经使用过的PTE，则标记为未使用。
if(i == 0)
*ptep &= ~PTE_A;
// 如果在第二次查找中，访问到了一个已修改过的PTE，则标记为未修改。
else if(i == 1)
*ptep &= ~PTE_D;
le = le->prev;
// 遍历了一回，肯定修改了标志位，所以要刷新TLB
tlb_invalidate(mm->pgdir, le);
}
}
// 按照前面的assert与if，不可能会执行到此处，所以return -1
return -1;
}
struct swap_manager swap_manager_fifo =
{
.name = "extend_clock swap manager",
.init = &_fifo_init,
.init_mm = &_fifo_init_mm,
.tick_event = &_fifo_tick_event,
.map_swappable = &_fifo_map_swappable,
.set_unswappable = &_fifo_set_unswappable,
.swap_out_victim = &_extend_clock_swap_out_victim,
.check_swap = &_fifo_check_swap,
};
实验总结
1.整个实验下来感觉自己收获很多，通过上网查找资料，自己深刻学习了虚拟内存管理的机制，通过实验更是加深了印象。
2.实验中遇到了很多的问题，比如进程虚拟内存的管理涉及到的一些结构体的关系，由于种类比较多很容易混乱，通过列图梳理了他们之间的关系。
3.操作系统这门课程比较基础，涉及到的内容比较多。有时学起来会比较吃力，但这门课程非常重要，是以后专业课的基石，希望在以后自己留给更多的时间在做实验上，从而更加深入的理解、掌握操作系统。