uCore实验 - Lab3

简介

  • 这里是笔者在完成uCore Lab 3时写下的一些笔记
  • 内容涉及虚拟内存存储等
  • 内容较多,建议使用右侧导航栏。

知识点

1. 虚拟内存

  • 虚拟内存是CPU可以看到的“内存”。

    • 虚拟内存所对应的实际物理内存单元可能不存在。
    • 虚拟内存的地址和对应物理内存的地址可能不一致。
    • 通过操作系统所实现的某种内存映射机制,可以达到访问的虚拟内存地址转换为物理内存地址的目的。
  • 当程序访问内存遇上特殊情况时,CPU会执行第十四号中断处理程序——缺页处理程序来处理。

    • 特殊情况有以下两种

      • 写入一个存在物理页的虚拟页——写时复制
      • 读写一个不存在物理页的虚拟页——缺页
      • 不满足访问权限。
    • 当程序触发缺页中断时,CPU会把产生异常的线性地址存储在CR2寄存器中,并且把页访问异常错误码保存在中断栈中。

      其中,页访问异常错误码的位0为1表示对应物理页不存在;位1为1表示写异常;位2为1表示访问权限异常。

  • 由于虚拟内存空间比物理内存空间大得多,所以必须在合适的情况下,将不常用的页面调至外存,或者将待用的页面从外存调入内存中。 这个过程对应用程序无感。 而什么时候调进调出,选择哪个页面调出,这都是值得考究的,这就是使用页面置换算法的目的。

2. 页面置换算法小叙

当物理页面不够用时,需要将某个页面置换到外存中。

那么该置换哪个物理页面呢?这就是页面置换算法的用处。

I. 局部页面置换算法

置换页面的选择范围仅限于当前进程占用的物理页面内.

1) 最近最少用算法(LRU)
a. 简介
  • 思路:选择最长时间没有被引用的页面进行置换。
  • 实现:缺页时,计算内存中每个逻辑页面的上一个访问时间,并选择上一个使用到当前时间最长的页面。
  • 特征:最优置换算法的一种近似。
b. 具体实现
  • 页面链表
    • 系统维护一个按最近一次访问时间排序的页面链表
      • 链表首节点是最近刚刚使用过的页面
      • 链表尾结点是最久未使用的页面
    • 访问内存时,找到相应页面并将其移至链表之首
    • 缺页时,置换链表尾结点的页面
  • 活动页面栈
    • 访问页面时,将此页号压入栈底。并将栈内相同的页号抽出
    • 缺页时,置换栈底的页面。

上述的两种实现都需要维护以及遍历搜索某个数据结构,

同时LRU对于过去的访问情况统计过于细致,所以该方法较为复杂。

2) 改进的时钟页面置换算法(Clock)
a. 简介
  • 思路:
    • 仅对页面的访问情况进行大致统计
    • 减小修改页的缺页处理开销
  • 数据结构:
    • 在页表项中增加访问位,描述页面在过去一段时间的内访问情况。
    • 在页表项中增加修改位,以判断当前页面是否修改过但没有存入外存。
    • 各页面组织成环形链表,同时指针指向最先调入的页面。
  • 算法
    • 访问页面时,在页表项记录页面访问情况
    • 缺页时,从指针处开始顺序查找未被访问与未被修改的页面进行置换。
  • 特征: 时钟算法是LRU与FIFO的折中。
b. 具体实现
  • 页面装入内存时,访问位初始化为0
  • 访问页面(读/写)时,访问位置为1
  • 缺页时,从指针当前位置顺序检查环形链表。
    • 若当前遍历到的页面访问位为0,则置换该页
    • 若当前遍历到的页面访问位为1,则设置该页的访问位为0,并移动指针到下一个页面,直到找到可置换的页面。

II. 全局置换算法

  • 思路:全局置换算法为进程分配可变数目的物理页面。
  • 要解决的问题:
    • 进程在不同阶段的内存需求是有变化的。
    • 分配给进程的内存也需要在不同阶段有所变化。
    • 全局置换算法需要确定分配给进程的物理页面数。
  • CPU利用率与并发进程数存在相互制约的关系。
    • 进程数少时,提高并发进程数,可提高CPU利用效率。
    • 并发进程导致内存访问增加
    • 并发进程的内存访问会降低了访存的局部性特征。
    • 局部性特征的下降会导致缺页率上升和CPU利用率下降。
1) 工作集置换算法
a. 工作集与常驻集
  • 工作集是一个进程当前正在使用的逻辑页面集合,可表示为二元函数$W(t, \Delta)$
    • $t$是当前的执行时刻
    • $\Delta$ 称为工作集窗口(working-set window),即一个定长的页面访问时间的窗口。
    • $W(t, \Delta)$指在当前时刻$t$前的$\Delta$时间窗口中的所有访问页面所组成的集合。
    • $|W(t, \Delta)|$指工作集的大小,即页面数目。
  • 常驻集是当前时刻进程实际驻留在内存中的页面集合。
  • 工作集与常驻集的关系
    • 工作集是进程在运行过程中固有的性质
    • 常驻集取决于系统分配给进程的物理页面数目和页面置换算法。
b. 思路
  • 当前时刻前$\tau$个内存访问的页引用是工作集。其中$\tau$被称为窗口大小

  • 换出不在工作集中的页面

c. 具体实现
  • 访存链表:维护窗口内的访存页面
  • 访存时,换出不在工作集的页面; 更新访存链表。
  • 缺页时,换入页面,更新访存链表。
2) 缺页率置换算法(PPF)
a. 简介

通过调节常驻集大小,使每个进程的缺页率保持在一个合理的范围内。

  • 若进程缺页率过高,则增加常驻集以分配更多的物理内存
  • 若进程缺页率过低,则减小常驻集以减小它的物理页面数。
b. 具体实现
  • 访存时,设置引用位标志
  • 缺页时,计算从上次缺页时间$t_{last}$到现在$t_{current}$的时间间隔
    • 如果$t_{current}-t_{last}>T$,则置换所有在$[t_{last}, t_{current}]$时间内没有被引用的页。
    • 如果$t_{current}-t_{last}<T$,则增加缺失页到常驻集中。

III. Belady现象

  • 现象: 采用FIFO等算法时,可能出现分配的物理页面数增加,缺页次数反而升高的异常情况。
  • 原因:
    • FIFO算法的置换特征与进程访问内存的动态特征矛盾
    • 被置换出去的页面并不一定是进程近期不会访问的。

3. uCore虚拟内存机制的实现

I. 虚拟内存管理

  • 结构体变量check_mm_struct用于管理虚拟内存页面,其结构体如下

    1
    2
    3
    4
    5
    6
    7
    8
    // the control struct for a set of vma using the same PDT
    struct mm_struct {
    list_entry_t mmap_list; // 按照虚拟地址顺序双向连接的虚拟页链表
    struct vma_struct *mmap_cache; // 当前使用的虚拟页地址,该成员加速页索引速度。
    pde_t *pgdir; // 虚拟页对应的PDT
    int map_count; // 虚拟页个数
    void *sm_priv; // 用于指向swap manager的某个链表,在FIFO算法中,该双向链表用于将可交换的已分配物理页串起来
    };
  • 当分配出新的虚拟页时,程序会执行insert_vma_struct函数,此时虚拟页vma_struct就会被插入mm_struct::mmap_list双向链表中。

  • 若程序首次访问该内存而触发缺页中断时,程序会在缺页处理程序中为该虚拟页划分出一块新的物理页。同时,还会更新mm_struct::pgdir上的对应页表条目,之后该页的内存访问即可正常执行。

  • 在FIFO页面置换算法中,初始时,mm_struct中的sm_priv会被设置为pra_list_head。而pra_list_head是一个双向链表的起始结点,该双向链表用于将可交换的已分配物理页串起来。

II. 页面置换

  • swap_managerpmm_manager类似,都设置了一个用于管理某个功能的模块。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    struct swap_manager
    {
    const char *name;
    /* Global initialization for the swap manager */
    int (*init) (void);
    /* Initialize the priv data inside mm_struct */
    int (*init_mm) (struct mm_struct *mm);
    /* Called when tick interrupt occured */
    int (*tick_event) (struct mm_struct *mm);
    /* Called when map a swappable page into the mm_struct */
    int (*map_swappable) (struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in);
    /* When a page is marked as shared, this routine is called to
    * delete the addr entry from the swap manager */
    int (*set_unswappable) (struct mm_struct *mm, uintptr_t addr);
    /* Try to swap out a page, return then victim */
    int (*swap_out_victim) (struct mm_struct *mm, struct Page **ptr_page, int in_tick);
    /* check the page relpacement algorithm */
    int (*check_swap)(void);
    };
  • 若使用FIFO页面置换算法,则在缺页中断程序中,程序只会换入目标物理页,而不会主动换出。

    只有在分配空闲物理页时,若pmm_manager->alloc_pages(n)失败,则程序才会执行一次页面换出,以腾出空闲的物理页,并重新分配。

  • swap_in函数只会将目标物理页加载进内存中,而不会修改页表条目。所以相关的标志位设置必须在swap_in函数的外部手动处理。而swap_out函数会先执行swap_out_victim,找出最适合换出的物理页,并将其换出,最后刷新TLB。需要注意的是swap_out函数会在函数内部设置PTE,当某个页面被换出后,PTE会被设置为所换出物理页在硬盘上的偏移。

    1
    2
    3
    cprintf("swap_out: i %d, store page in vaddr 0x%x to disk swap entry %d\n", i, v, page->pra_vaddr/PGSIZE+1);
    *ptep = (page->pra_vaddr/PGSIZE+1)<<8;
    free_page(page);

    当PTE所对应的物理页存在于内存中,那么该PTE就是正常的页表条目,可被CPU直接寻址用于转换地址。但当所对应的物理页不在内存时,该PTE就成为swap_entry_t,保存该物理页数据在外存的偏移位置。相关代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    /*
    * swap_entry_t
    * --------------------------------------------
    * | offset | reserved | 0 |
    * --------------------------------------------
    * 24 bits 7 bits 1 bit
    * /
    /* *
    * swap_offset - takes a swap_entry (saved in pte), and returns
    * the corresponding offset in swap mem_map.
    * */
    #define swap_offset(entry) ({ \
    size_t __offset = (entry >> 8); \
    if (!(__offset > 0 && __offset < max_swap_offset)) { \
    panic("invalid swap_entry_t = %08x.\n", entry); \
    } \
    __offset; \
    })
  • 同时,不是所有物理页面都可以置换,例如内核关键代码和数据等等,所以在分配物理页时,需要对于那些可被置换的物理页执行swap_map_swappable函数,将该物理页加入到mm_struct::sm_priv指针所指向的双向链表中,换入和换出操作都会操作该链表(插入/移除可交换的已分配物理页)。

  • 数据结构Pagevma_struct分别用于管理物理页和虚拟页,其结构如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    // 用于描述某个虚拟页的结构
    struct vma_struct {
    struct mm_struct *vm_mm; // 管理该虚拟页的mm_struct
    uintptr_t vm_start; // 虚拟页起始地址,包括当前地址
    uintptr_t vm_end; // 虚拟页终止地址,不包括当前地址(地址前闭后开)
    uint32_t vm_flags; // 相关标志位
    list_entry_t list_link; // 用于连接各个虚拟页的双向指针
    };

    // 数据结构Page相关成员的用途已在uCore-2中介绍过,这里只提它新增的两个成员pra_*
    struct Page {
    int ref;
    uint32_t flags;
    unsigned int property;
    list_entry_t page_link;
    list_entry_t pra_page_link; // 用于连接上一个和下一个*可交换已分配*的物理页
    uintptr_t pra_vaddr; // 用于保存该物理页所对应的虚拟地址。
    };
    • 当分配某个虚拟页vma_struct时,程序会在insert_vma_struct函数中设置其vm_mm成员为某个mm_struct,这样便于后续的管理。
    • 在函数pgdir_alloc_page中,程序会设置Pagepra_vaddr成员,将其设置为当前物理页所对应的虚拟地址,之后便可通过Page->pra_vaddr->pte一条链,直接找到当前物理页地址所对应的PTE条目。同时,也可通过pra_vaddr来确定对应外存的相对偏移page->pra_vaddr/PGSIZE+1
    • Page::page_link用于将空闲物理页连接至双向链表中,而page::pra_page_link用于将可交换的已分配物理页连接至另一个双向链表中,注意两者的用途是不同的。

练习解答

1. 练习0

填写已有实验

  • 抄就对了。

2. 练习1

给未被映射的地址映射上物理页

完成do_pgfault(mm/vmm.c)函数,给未被映射的地址映射上物理页。设置访问权限 的时候需要参考页面所在 VMA 的权限,同时需要注意映射物理页时需要操作内存控制 结构所指定的页表,而不是内核的页表。

实验代码如下

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
int do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
int ret = -E_INVAL;
// 获取触发pgfault的虚拟地址所在虚拟页
struct vma_struct *vma = find_vma(mm, addr);

pgfault_num++;
// 如果当前访问的虚拟地址不在已经分配的虚拟页中
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:
// 写,同时存在物理页,则写时复制
// 需要注意的是,default会执行case2的代码,也就是判断是否有写权限。
case 2:
// 读,同时不存在物理页
// 同时如果当前操作是写入,但所在虚拟页不允许写入
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 */
// 读,同时存在物理页。那就不可能会调用page fault,肯定哪里有问题,直接failed
cprintf("do_pgfault failed: error code flag = read AND present\n");
goto failed;
case 0: /* error code flag : (W/R=0, P=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;
if (vma->vm_flags & VM_WRITE) {
perm |= PTE_W;
}
addr = ROUNDDOWN(addr, PGSIZE);
ret = -E_NO_MEM;
pte_t *ptep=NULL;

/* LAB3 EXERCISE 1: YOUR CODE */
// 查找当前虚拟地址所对应的页表项
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 {
/* LAB3 EXERCISE 2: YOUR CODE */
// 如果这个页表项所对应的物理页存在,但不在内存中
// 如果swap已经初始化完成
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。
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;
}
  • 请描述页目录项(Page Directory Entry)和页表项(Page Table Entry)中组成部分对ucore实现页替换算法的潜在用处。
  • 如果ucore的缺页服务例程在执行过程中访问内存,出现了页访问异常,请问硬件要做哪些事情?
    • 将发生错误的线性地址(虚拟地址)保存至CR2寄存器中。
    • 压入EFLAGSCS, EIP,错误码和中断号至当前内核栈中。
    • 保存上下文。
    • 执行新的缺页中断程序。
    • 恢复上下文。
    • 继续执行上一级的缺页服务例程。

3. 练习2

补充完成基于FIFO的页面替换算法

完成vmm.c中的do_pgfault函数,并且在实现FIFO算法的swap_fifo.c中完成map_swappable和swap_out_victim函数。

  • FIFO中,当新加入一个物理页时,我们只需将该物理页加入至链表首部即可。当需要换出某个物理页时,选择链表末尾的物理页即可。

  • 相关实现如下

    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
    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);
    //record the page access situlation
    /*LAB3 EXERCISE 2: YOUR CODE*/
    //(1)link the most recent arrival page at the back of the pra_list_head qeueue.
    list_add(head, entry);
    return 0;
    }

    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
    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;

    return 0;
    }
  • 如果要在ucore上实现"extended clock页替换算法"请给你的设计方案,现有的swap_manager框架是否足以支持在ucore中实现此算法?如果是,请给你的设计方案。如果不是,请给出你的新的扩展和基此扩展的设计方案。并需要回答如下问题

    • 现有的swap_manager框架可以支持在ucore中实现此算法,具体见扩展练习1
    • 需要被换出的页的特征是什么?
      • PTE_P(Present)和PTE_D(Dirty)位均为0。
    • 在ucore中如何判断具有这样特征的页?
      • 获取线性地址所对应的页表项,之后使用位运算判断PTE_PPTE_D
    • 何时进行换入和换出操作?
      • 缺页时换入。
      • 物理页帧满时换出,不过需要注意dirtybit的处理。可以在修改dirty的时候写入外存,或者可以在最终要删除该物理页时再写入外存。后者有利于多个写操作的合并,降低缺页代价,但此时的页替换算法却退化成普通的clock算法,而不是extended clock算法了。

4. 扩展练习

Challenge 1

实现识别dirty bit的 extended clock页替换算法

  • FIFO的基础上,实现swap_out_victim函数即可。

  • 该函数中查找一块可用于换出的物理页,最多只需要遍历三次:

    • 第一次查找 !PTE_A & !PTE_D,同时重置当前页的PTE_A,为第二次遍历的条件打基础
    • 第二次查找 !PTE_A & !PTE_D, 同时重置当前页的PTE_D,为第三次遍历的条件打基础
    • 第三次查找,肯定能找到
  • 这里需要注意对于PTE_D的操作,若第一次、第二次遍历都找不到符合要求的物理页,则必须对PTE_D下手,重置该标志位。还有一点需要注意,在每次修改PTE标志位后,都需要重置TLB缓存。

  • swap_out_victim相关代码如下(偷了个小懒,每次遍历链表都是从头开始,同时其余函数沿用FIFO):

    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
    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,
    };

Challenge 2

实现不考虑实现开销和效率的LRU页替换算法

遇到了一个较为麻烦的问题:如何在正常访问内存时设置swap_manager中相关链表上物理页的LRU,留坑…

  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2020-2021 Kiprey
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~