lab3 — 虚拟内存管理

前置知识

虚拟存储、页面置换算法、中断机制。

改动点

相比于 lab2 源代码,lab3 主要是添加部分代码以实现虚拟存储功能,仅见的改动点在于页描述结构 pagealloc_pages 函数的具体实现,两者源码如下:

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
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; // 指明此物理页面对应的虚拟地址
};


struct Page * alloc_pages(size_t n) {
struct Page *page=NULL;
bool intr_flag;

while (1)
{
local_intr_save(intr_flag);
{
page = pmm_manager->alloc_pages(n);
}
local_intr_restore(intr_flag);

// 如果因空闲页不够而导致的内存分配失败,且此时已经开启 swap,则其会基于相关替换算法而自动换出某些页面,以满足分配要求(此处要求 n > 1,表明只要请求页面大于 1,分配失败时不会尝试进行页面替换)。
if (page != NULL || n > 1 || swap_init_ok == 0) break;

extern struct mm_struct *check_mm_struct;

swap_out(check_mm_struct, n, 0);
}
return page;
}

练习一

此练习用于了解页面替换算法 FIFO 的具体实现。

对于虚拟内存管理而言,另外涉及两大数据结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct vma_struct {
struct mm_struct *vm_mm; // 指向管理此 vma 的 mm
uintptr_t vm_start; // vma 的起始虚拟地址(包含)
uintptr_t vm_end; // vma 的终止虚拟地址(不包含)
uint32_t vm_flags; // vma 权限标志信息(可读、可写、可执行)
list_entry_t list_link; // 用于将属于同一程序的 vma 链接起来
};

struct mm_struct {
list_entry_t mmap_list; // 指向某程序的 vma 集
struct vma_struct *mmap_cache; // 当前访问的 vma
pde_t *pgdir; // 该程序对应的页目录表
int map_count; // 指明某程序的 vma 总数
void *sm_priv; // swap manager(主要指代页面替换算法的具体实现) 的隐私信息。ucore 之中,使用 pra_list_head 进行填充
};

为实现 FIFO,我们需要使用 list_entry_t pra_list_head 所指链表来有序 (对于 FIFO 而言,指代页面被分配的时间) 保存某程序所分配的物理页面集 (集内页面使用 Page.pra_page_link 进行链接)。

当分配某程序物理页面后,需要将刚分配的页面放置于链首以显式更新 pra_list_head 链表;当需要选择待替换物理页面时,直接选择链尾页面即可。

被替换的物理页面会被存放至 swap 分区内部 (此称为交换技术)。因为此时 PTE 表项无效,因此 ucore 使用此存放该页面所在位置的起始扇区编号。

因为 ucore 将物理页面线性映射至 swap 对应扇区,因此其交换技术的实现十分简单。而实际系统之中,这种映射实现是比较复杂的。

基于 FIFO 实现思想及上述数据结构,很容易写出相关代码,故不再赘述。

练习二

此练习用于了解并实现缺页中断的异常处理程序。

缺页中断的异常处理程序的具体调用流程如下:__alltraps –> trap –> trap_dispatch –> pgfault_handler –>do_pgfault。这里直接基于 do_pgfault 的实现,说明如何处理缺页中断。

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
// mm 指代当前运行程序的虚拟内存管理结构,error_code 指代硬件设置的异常码,addr 指代引发缺页中断的虚拟地址。
int do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
int ret = -E_INVAL;
// 判断 addr 是否属于当前运行程序的合法地址。
struct vma_struct *vma = find_vma(mm, addr);

pgfault_num++;
// 如果该地址不合法,则直接返回即可。
if (vma == NULL || vma->vm_start > addr) {
goto failed;
}

// 详细判断硬件设置的 error_code (其第 0 位指代中断是否由页面不存在而引起,第 1 位指代中断是否由写操作引起,第 2 位指代当前是否处于用户模式),对于因权限不满足的情况,直接返回。
switch (error_code & 3) {
default:

case 2:
if (!(vma->vm_flags & VM_WRITE)) {
goto failed;
}
break;
case 1:
goto failed;
case 0:
if (!(vma->vm_flags & (VM_READ | VM_EXEC))) {
goto failed;
}
}

// 以下情形才能继续运行:1. 写某已存在的地址;2. 写未存在的地址,并且此地址可写;3. 读未存在的地址,并且此地址可读。
// 对于情形 1,基本没有涉及,主要关注后两种情形。

// 获取 vma 对应的访问权限
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;
// 获取该虚拟地址对应的 pte 表项,若获取失败(可能因为空间不足,而分配页表失败),则直接返回。
ptep = get_pte(mm->pgdir, addr, 1);
if (ptep == NULL)
{
goto failed;
}

// 如果其值为空,则只能直接分配页面(对于实际系统而言,直接分配肯定是不行的,因为当前页面可能存在数据)。
if (*ptep == 0) {
// 同样可能因为分配页面而失败,
if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
goto failed;
}
}

// 表明其存在于 swap 分区内部,需要进行获取(如果 swap manager 尚未初始化成功,则直接返回)。
else {
if(swap_init_ok) {
// 获取 swap 内容至所分配的 page。
struct Page *page=NULL;
if ((ret = swap_in(mm, addr, &page)) != 0)
{
goto failed;
}

// 构建页表映射,触发 FIFO 更新,设置 page 对应的 pra_vaddr。
page_insert(mm->pgdir, page, addr, perm);
swap_map_swappable(mm, addr, page, 1);
page->pra_vaddr = addr;
}
else {
goto failed;
}
}

ret = 0;
failed:
return ret;
}

扩展练习一

该练习用于了解并实现 extended clock 页面替换算法。

基于硬件实现以及现有数据结构,该算法比较容易实现。

当分配某程序物理页面后,需要将其放置于 list_entry_t pra_list_head 所示链表的尾部;程序访问过程中,硬件会自动设置 PTE 表项中的相关标志位 (所示页面是否发生修改,所示页面是否访问);当需要选择待替换物理页面时,遍历链表,并动态更新 pra_list_head 指针以及相应页面对应页表项的标志位,如果某页面对应的标志位为 00 (即,自上次至此,尚未被访问,也尚未被修改),则选择此页面进行替换。

扩展练习二

该练习用于了解并实现 LRU 页面替换算法。

当某页面被访问后,似乎无法更新 LRU 所维护的页面链表。