操作系统ucore lab2实验报告

桃扇骨 2022-07-13 02:41 239阅读 0赞

# Lab2 #

## Exercise0：填写已有实验 ##

使用meld将lab1中的代码填入实验中

## Exercise1：**实现 first-fit 连续物理内存分配算法** ##

##### default\_init() #####

static void
    default_init(void) {
        list_init(&free_list);
        nr_free = 0;
    }

这个函数的正确代码已经给出，不需要进行修改。

函数的作用是对free\_list进行初始化，对free\_list 的头结点进行初始化，并且把free\_list 中的nr\_free设置为0，也就是把当前的空闲页中空闲页的数量先初始化为0。

##### default\_init\_memmap(struct Page \*base, size\_t n) #####

static void
    default_init_memmap(struct Page *base, size_t n) {
        assert(n > 0);
        struct Page *p = base;
        for (; p != base + n; p ++) {
            assert(PageReserved(p));//检查是否是保留页
            p->flags = p->property = 0;//设置标志位和property为0
            set_page_ref(p, 0);//将此页的引用计数设为零
        }
        base->property = n;//初始化块首的property为整个free_list的大小
        SetPageProperty(base);//将块首的标志位设置为free
        nr_free += n;//把free_list中的空闲块数量设置为n
        list_add_before(&free_list, &(base->page_link));//最后把整个空闲块加到free_area_t 中
    }

这个函数的代码也已经给出，但其中有一些小的问题

问题出在把以base为头的整个空闲页链表加到free\_list中时，最初给出的代码是把整个块加到头指针的后面，我把这里改成了加在头的前面，由于这是个双向循环链表，并且刚刚初始化，还是个空的链表，所以两个方法的结果是相同的，但是意义却是不同的。

在这几行代码中有些需要注意的地方：

p->flags = p->property = 0;//设置标志位

在这里把标志位直接设置为了0，我们根据指导书可以知道，flag中许多的标志位，其中两个：

#define PG_reserved 0
    #define PG_property 1

*  PG\_reserved ：位于flag的第一位bit0处，表示此页是否被保留，如果是被保留的页，则bit 0会设置为1，且不能放到空闲页链表中，即这样的页不是空闲页，不能动态分配与释放。比如目前内核代码占用的空间就属于这样“被保留”的页。
 *  PG\_property ：位于flag的第二位bit1处，表示此页是否是free的，如果设置为1，表示这页是这个内存块的第一个free的页，并且这个free的块是可以被分配的；如果设置为0，表示这页已经被分配出去了，不能被再二次分配，或者是这个页不是空闲区块的第一个页.

##### 　static struct Page \*default\_alloc\_pages(size\_t n) #####

这个函数的作用是为进程分配大小为n的空闲页

步骤如下：

*  判断空闲页链表中的空闲页的个数是否大于n，如果不大于则直接返回NULL
 *  遍历整个空闲页链表，直到找到大于n的空闲块或者遍历完一遍
 *  如果找到了就把要占用的空闲块从空闲链表中删除，并且重新设置标志位，把这个块没分配完的部分重新加回到空闲链表中，重新计算空闲页的个数，然后返回分配的页地址
 *  如果没找到就返回NULL

static struct Page *
    default_alloc_pages(size_t n) {
        assert(n > 0);
        if (n > nr_free) {
       //如果需要的空闲的个数大于所有的空闲页的个数的总和，直接返回NULL
            return NULL;
        }
        struct Page *page = NULL;//用于存储找到的空闲块的第一个页
        list_entry_t *prev ;//用于存储找到的空闲块的第一个页的前一个页
        list_entry_t *le = &free_list;
        //cprintf("%d******\n", page->property);
        while ((le = list_next(le)) != &free_list) {
       //遍历整个空闲块链表，直到遍历完一遍
            //cprintf("---------------\n");
            struct Page *p = le2page(le, page_link);//得到当前位置的page
            if (p->property >= n) {
       //如果找到符合条件的区块
                page = p;//将找到的这个页存储起来
                //cprintf("%d+++++++\n", page->property);
                prev = list_prev(le);//将这个页的前一个块也存储起来
                break;
            }
        }
        if (page != NULL) {
       //如果找到了符合条件的块
            list_del(&(page->page_link));//把将要占用的空闲块从空闲块链表中删除
            if (page->property > n) {
       //如果用完后这个块还有剩余
                struct Page *p = page + n;
                p->property = page->property - n;
                SetPageProperty(p);
                list_add(prev, &(p->page_link));//就把这个剩下的块加到原来块的位置上去
            }
    
            nr_free -= n;//将整个空闲链表的大小减去n
            ClearPageProperty(page);//把这个空闲块改为已经使用的块
        }
        return page;
    }

##### static void default\_free\_pages(struct Page \*base, size\_t n) #####

这个函数的作用是把用完的页释放掉，并且把这些块合并到空闲链表中去

步骤如下：

*  把这个块中的页都设置为空闲页
 *  在free\_list中遍历查找这个块应该插入的位置
 *  把整合后的块放入free\_list中，并判断是否与free\_list中已有的块相接
 *  如果相接，就把两个块整合在一起，并且把已经整合的块从free\_list中删除

static void default_free_pages(struct Page *base, size_t n) {
        assert(n > 0);
           struct Page * p = NULL;
    
            base->flags = 0;
            base->property = n;       //该空闲页大小为n
            SetPageProperty(base);    //将该页设置为空闲页
            set_page_ref(base,0);
    
            list_entry_t *le = &free_list;
    
            while((le=list_next(le)) != &free_list) {
       //遍历整个空闲链表找到合适的插入位置
                p = le2page(le, page_link);
                if(p> base){
       //第一个大于base的空闲块
                break;
                }
            }
            if(p > base)//如果找到了合适的位置，就把base插入到这个位置前面
                le= &(p->page_link);
            else//如果没有找到，说明这个块应该在整个空闲链表的最後面，所以插入到头的前面
                le = &free_list;
    
            list_add_before(le,&(base->page_link));//将整合后的块添加到空闲列表中
            if (le != &free_list){
                if( base+n == p ){ //待整合的空闲块在原有空闲块的低位地址
                    base->property += p->property; //更新该空闲块大小
                    p->property = 0;
                    list_del(&(p->page_link));  //将已整合的块从空闲列表中删除
                }
            }
            le = list_prev(&(base->page_link));
            if (le!= &free_list){
                p = le2page(le,page_link);
                if (p+p->property == base){ //待整合的空闲块在原有空闲块的高位地址
                    p->property += base->property; //更新该空闲块大小
                    base->property = 0;
                    list_del(&(base->page_link)); //将已整合的块从空闲列表中删除
                }
            }
            nr_free += n;
            return ;
    }

## Exercise2：**实现寻找虚拟地址对应的页表项** ##

通过页目录表的基址和偏移，找到对应的页表，并且返回出去。如果找不到这个页表，也就是这个页表不存在的话，就创建一个页表，并且对页表进行初始化。

pte_t *
    get_pte(pde_t *pgdir, uintptr_t la, bool create) {
        pde_t *pdep = &pgdir[PDX(la)]; //根据页目录表的基址和偏移得到页表的基址
        if (!(*pdep & PTE_P)) {  //如果这个页表不存在就创建此页表 
            struct Page *page;
            if (!create || (page = alloc_page()) == NULL) {
       //如果不允许创建页表或者创建失败就返回NULL
               return NULL;
            }
            set_page_ref(page, 1);//创建成功后对该页的引用次数进行设置 
            uintptr_t pa = page2pa(page);//获取该页的线性地址
            memset(KADDR(pa), 0, PGSIZE);//根据页的地址为页表初始化内存空间
            *pdep = pa | PTE_U | PTE_W | PTE_P;//设置此表的一系列权限
       }
       return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)];  //对pdep进行转化，转化为pte_t 
    }

## Exercise3：**释放某虚地址所在的页并取消对应二级页表项的映射** ##

通过页目录表的基址和偏移释放需要的页。如果这个页只有一个引用，也就是说这个页只有一个进程映射到这个页，那么这个页表就可以直接释放掉。但是如果有多个引用，也就是说有多个进程对应到这个页的话，就只把这个页对应的二级页表中的页表项置为零。

static inline void
    page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {
        if (*ptep & PTE_P) {                    //判断页表中该表项是否存在
            struct Page *page = pte2page(*ptep);
            if (page_ref_dec(page) == 0) {      //判断是否只被引用了一次
                free_page(page);                //如果只被引用了一次，那么可以释放掉此页
            }
            *ptep = 0;                          //如果被多次引用，则不能释放此页，只用释放二级页表的表项
            tlb_invalidate(pgdir, la);          //更新TLB，将TLB中缓存的部分设置为无效
            }
    }