ucore_lab2实验报告

发表于

ucore lab2实验报告

实验二 主要针对完成Ucore的物理内存管理

练习0

key point:

利用meld工具进行比较与合并

练习1：实现first-fit练习物理内存分配算法

介绍ucore很详细的总结

Note:

连续分配方式，是指为一个用户程序分配一个连续的内存空间。它主要包括单一连续分配、固定分区分配和动态分区分配。

单一连续分配

固定分区分配

动态分区分配

动态分区分配又称为可变分区分配，是一种动态划分内存的分区方法。这种分区方法不预先将内存划分，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统中分区的大小和数目是可变的

动态分区

在进程装入或换入主存时，如果内存中有多个足够大的空闲块，操作系统必须确定分配哪个内存块给进程使用，这就是动态分区的分配策略，考虑以下几种算法：

  • 首次适应(First Fit)算法：空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。
  • 最佳适应(Best Fit)算法：空闲分区按容量递增形成分区链，找到第一个能满足要求的空闲分区。
  • 最坏适应(Worst Fit)算法：又称最大适应(Largest Fit)算法，空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区，也就是挑选出最大的分区。
  • 邻近适应(Next Fit)算法：又称循环首次适应算法，由首次适应算法演变而成。不同之处是分配内存时从上次查找结束的位置开始继续查找。

在这几种方法中，首次适应算法不仅是最简单的，而且通常也是最好和最快的。在UNIX 系统的最初版本中，就是使用首次适应算法为进程分配内存空间，其中使用数组的数据结构 (而非链表）来实现。不过，首次适应算法会使得内存的低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。

邻近适应算法试图解决这个问题，但实际上，它常常会导致在内存的末尾分配空间（因为在一遍扫描中，内存前面部分使用后再释放时，不会参与分配)，分裂成小碎片。它通常比首次适应算法的结果要差。

最佳适应算法虽然称为“最佳”，但是性能通常很差，因为每次最佳的分配会留下很小的难以利用的内存块，它会产生最多的外部碎片。

最坏适应算法与最佳适应算法相反，选择最大的可用块，这看起来最不容易产生碎片，但是却把最大的连续内存划分开，会很快导致没有可用的大的内存块，因此性能也非常差。

Kunth和Shore分别就前三种方法对内存空间的利用情况做了模拟实验，结果表明：

首次适应算法可能比最佳适应法效果好，而它们两者一定比最大适应法效果好。另外注意,在算法实现时,分配操作中最佳适应法和最大适应法需要对可用块进行排序或遍历查找，而首次适应法和邻近适应法只需要简单查找；回收操作中，当回收的块与原来的空闲块相邻时（有三种相邻的情况，比较复杂)，需要将这些块合并。在算法实现时，使用数组或链表进行管理。除了内存的利用率，这里的算法开销也是操作系统设计需要考虑的一个因素。

为了与以后的分页机制配合，首先需要建立对整个计算机的每一个物理页的属性，用结构体Page来表示，它包含了映射此物理页的虚拟页个数，描述物理页属性的flags和双向链接各个Page结构的page_link双向链表。

1
2
3
4
5
6
7
> struct Page{
>     int ref;
>     uint32_t flags;
>     unsigned int property;
>     list_entry_t page_link;
> }123456
>

  • ref

      表示该页被页表的引用记数。如果这个页被页表引用了，即在某页表中有一个页表项设置一个虚拟页到这个Page管理的物理页的映射关系，就会把Page的ref加一。反之，若页表项取消，即映射关系解除，就减一。

  • flags

       表示此物理页的状态标记，有两种属性，bit 0表示是否被保留，如果被保留了则设为1，且不能放到空闲页链表中，即这样的页不是空闲页，不能动态分配与释放。比如内核代码占用的空间。bit 1表示此页是否是空闲的。如果设置为1，表示这页是空闲的，可以被分配；如果设置为0，表示这页已经被分配出去了，不能被再二次分配。

  • property

      用来记录某连续内存空闲块的大小（即地址连续的空闲页的个数）。这里需要注意的是用到此成员变量的这个Page比较特殊，是连续内存空闲地址最小的一夜（即第一页）。

  • page_link

      是便于把多个连续内存空闲块链接在一起的双向链表指针，连续内存空闲块利用这个页的成员变量page_link来链接比它地址小和大的其他连续内存空闲块

  为了有效的管理这些小连续内存空闲块，所有的连续内存空闲块可用一个双向链表来管理，便于分配和释放，为此定义一个free_area_t

1
2
3
4
5
> typedef struct {
>     list_entry_t free_list;         // the list header
>     unsigned int nr_free;           // number of free pages in this free list
> } free_area_t;1234
>
  • free_list是一个list_entry结构的双向链表指针
  • nr_free则记录当前空闲页的个数

有了这两个数据结构，就可以管理起来整个以页尾单位的物理内存空间

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
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;
        SetPageReserved(base);
        // 引用位 置0
        set_page_ref(p, 0);
        list_add_before(&free_list, &(p->page_link));
    }
    base->property = n;
    // SetPageProperty(base);
    nr_free += n;
    // list_add(&free_list, &(base->page_link));
}

static struct Page *
default_alloc_pages(size_t n) {
    assert(n > 0);
    if (n > nr_free) {//当空闲页不够时，返回NULL
        return NULL;
    }
    list_entry_t *le = &free_list;
    while ((le = list_next(le)) != &free_list) {//遍历所有指针
        struct Page *p = le2page(le, page_link);//转换为页结构
        if (p->property >= n) {//如果找到空闲页大小大于等于n时选中
            int i;
            list_entry_t *len;
            for(i = 0; i < n; i++)//初始化分配内存
            {
                len = list_next(le);
                struct Page *p2 = le2page(temp_le, page_link);    //转换页结构
                SetPageReserved(p2);  //初始化标志位
                ClearPageProperty(p2);   
                list_del(le);  //清除双向链表指针
                le = len;  
            }
            if(p->property > n)
            {  
                //若大小>n,只取大小为n的块
                (le2page(le,page_link))->property = p->property - n;  
            }  
            ClearPageProperty(p);  //初始化标志位
            SetPageReserved(p);  
            nr_free -= n;  //空闲页大小-n
            return p;  
        }
    }
    return NULL;//分配失败
}

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++)//在之前插入n个空闲页
    {
        list_add_before(le, &(p->page_link));
        p->flags = 0;//设置标志
        set_page_ref(p, 0);
        ClearPageProperty(p);
        SetPageProperty(p);
    }

    base->property = n;//设置连续大小为n
    //如果是高位，则向高地址合并
    p = le2page(le,page_link);
    if(base + base->property == p )
    {
        base->property += p->property;
        p->property = 0;
    }
    //如果是低位且在范围内，则向低地址合并
    le = list_prev(&(base->page_link));
    p = le2page(le, page_link);
    if(le != &free_list && 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;
}

练习2：实现寻找虚拟地址对应的页表项

页表机制

请求分页系统的页表机制不同于基本分页系统，请求分页系统在一个作业运行之前不要求全部一次性调入内存，因此在作业的运行过程中，必然会出现要访问的页面不在内存的情况，如何发现和处理这种情况是请求分页系统必须解决的两个基本问题。为此，在请求页表项中增加了四个字段，如图

图2

增加的四个字段说明如下：

  • 状态位P：用于指示该页是否已调入内存，供程序访问时参考。
  • 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近己有多长时间未被访问，供置换算法换出页面时参考。
  • 修改位M：标识该页在调入内存后是否被修改过。
  • 外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。

缺页中断机构

在请求分页系统中，每当所要访问的页面不在内存时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。此时应将缺页的进程阻塞（调页完成唤醒)，如果内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应页表项，若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存)。

缺页中断作为中断同样要经历，诸如保护CPU环境、分析中断原因、转入缺页中断处理程序、恢复CPU环境等几个步骤。但与一般的中断相比，它有以下两个明显的区别：

  • 在指令执行期间产生和处理中断信号，而非一条指令执行完后，属于内部中断。
  • 一条指令在执行期间，可能产生多次缺页中断。

地址变换机构

请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，为实现虚拟内存，又增加了某些功能而形成的。

图三

如图3-25所示，在进行地址变换时，先检索快表：

  • 若找到要访问的页，便修改页表项中的访问位（写指令则还须重置修改位)，然后利用页表项中给出的物理块号和页内地址形成物理地址。
  • 若未找到该页的页表项，应到内存中去查找页表，再对比页表项中的状态位P，看该页是否已调入内存，未调入则产生缺页中断，请求从外存把该页调入内存。

注意自己了解高端内存概念

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//typedef uintptr_t pde_t;
    pde_t *pdep = &pgdir[PDX(la)];  // (1)获取页表
    if (!(*pdep & PTE_P))             // (2)假设页目录项不存在
    {      
        struct Page *page;
        if (!create || (page = alloc_page()) == NULL) // (3) check if creating is needed, then alloc page for page table
        {    //假如不需要分配或是分配失败
            return NULL;
        }
        set_page_ref(page, 1);                      // (4)设置被引用1次
        uintptr_t pa = page2pa(page);                  // (5)得到该页物理地址
        memset(KADDR(pa), 0, PGSIZE);                  // (6)物理地址转虚拟地址，并初始化
        *pdep = pa | PTE_U | PTE_W | PTE_P;            // (7)设置可读，可写，存在位
    }
    return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)];     // (8) return page table entry
    //KADDR(PDE_ADDR(*pdep)):这部分是由页目录项地址得到关联的页表物理地址，再转成虚拟地址
    //PTX(la)：返回虚拟地址la的页表项索引
    //最后返回的是虚拟地址la对应的页表项入口地址

练习3: 释放某虚地址所在的页并取消对应二级页表项的映射

释放某虚拟地址所在的页并取消对应的二级页表项的映射（需要编程）

当释放一个包含某虚地址的物理内存页时，需要让对应此物理内存页的管理数据结构Page做相关的清除

处理，使得次物理内存页成为空闲；另外还需把表示虚地址与物理地址对应关系的二级页表项清除

1
2
3
4
5
6
7
8
9
10
if (*ptep & PTE_P)                 //(1) check if this page table entry is present
    {      //假如页表项存在
        struct Page *page = pte2page(*ptep);//(2)找到页表项的那一页信息
        if (page_ref_dec(page) == 0)//(3)如果没有被引用
        { 
            free_page(page);//(4)释放该页
        }
        *ptep = 0;         //(5)该页目录项清零
        tlb_invalidate(pgdir, la); //(6) flush tlb当修改的页表是进程正在使用的那些页表，使之无效
    }