mineucore-虚拟内存管理学习笔记

概述

虚拟页式存储技术,在页式存储管理的基础上,增加请求调页和页面置换

有了页式内存管理技术,CPU使用的地址已经不是实际的物理地址了,而是虚拟地址,进而可以通过设置段界限或页表项来设定程序运行时的访问空间,确保程序运行不越界,完成内存访问保护的功能。

但是想最大化利用物理内存,根据程序的局部性原理,即程序在执行过程中的一个较短的时期内,所执行的指令地址和指令操作数地址,分别局限于一定区域。可使程序在没有访问某个虚拟地址时,不分配物理内存,当程序访问某个虚拟地址时,操作系统在动态的分配内存,在页表中建立虚拟地址到物理地址的映射关系,这就是按需分页

但是物理内存总会使用殆尽,操作系统可以将程序内存空间中不经常访问的数据放入外存中,并在页表项中标记,当发生缺页异常时,就把外存中的数据重新加载进内存中,这是页换入换出(page swap in/out)技术。如何选择物理页放入外存中,这就是页面置换算法的工作了。

当两个虚拟页的数据内容相同时,可只分配一个物理页框,这样如果对两个虚拟页的访问方式是只读方式,这两个虚拟页可共享页框,节省内存空间;如果CPU对其中之一的虚拟页进行写操作,则这两个虚拟页的数据内容会不同,需要分配一个新的物理页框,并将物理页框标记为可写,这样两个虚拟页面将映射到不同的物理页帧,确保整个内存空间的正确访问。这种技术称为写时复制(Copy On Write,简称COW)

下面主要在物理内存管理和中断异常的基础上完成上面的三个内容。

按需分页与FIFO页面置换算法

在物理内存方面,使用Page结构体管理所有物理内存,每一个物理帧,都对应一个Page结构体。Page结构体保存在ucore系统的物理内存上方。为了实现页面置换算法,在Page结构体末尾,添加了两个新的成员。

1
2
3
4
5
6
7
8
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; //用来记录此物理页对应的虚拟页起始地址
};

pra_page_link这个双向链表也是有头结点的

1
2
//swap_info.c
list_entry_t pra_list_head;//做为头结点,用双向链表各用到的页框Page结构体,按照时间顺序,使用时当成队列数据结构使用

但是对于用户态的程序来说,需要有相关的数据结构和操作来体现一般应用程序对虚拟内存的“需求”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct mm_struct {
list_entry_t mmap_list; //连接vma_struct的双向链表的头结点
struct vma_struct *mmap_cache; //指向当前正在使用的vma结构,用于提速
pde_t *pgdir; //指向当前mm数据结构所维护的页目录表
int map_count; //其链接的vma_struct的数量
void *sm_priv; //指向用来链接记录页访问情况的链表头
};

struct vma_struct {
struct mm_struct *vm_mm; //指向头mm结构
uintptr_t vm_start; //虚拟地址的起始地址
uintptr_t vm_end; //虚拟地址的结束地址
uint32_t vm_flags; //虚拟空间的标志位
list_entry_t list_link; //双向链表的连接结构(按照地址排序)
};

mm_struct维护一个页表的可用空闲空间,具体来说是一个mm_struct下链接多个vma_struct,vma_struct标记了这个4M空间中可以使用的虚拟空间,各个vma_struct间通过list_link双向链表链接,而mm_struct就是这个双向链表的表头。

当页表映射到物理内存时,页表内容为页帧的地址还有一些标志位,但是当虚拟内存映射到外存时,其页表内容如何设计?即如何区分物理内存的映射和swap区的映射。

一个页大小为4kb,当映射到硬盘中时,需要占用8个扇区(0.5kb/扇区)。可将PTE(页表项)的高24位表示对换到硬盘上的页的起始扇区号,并将bit 0置为0,即当PTE高24位不为0,且bit 0为0,则说明该物理页被映射到了swap区。

1
2
3
4
5
* swap_entry_t
* --------------------------------------------
* | offset | reserved | 0 |
* --------------------------------------------
* 24 bits 7 bits 1 bit

缺页中断的处理函数主要是do_pgfault这个函数,主要包括两个分支:1)当发生缺页中断时,如果页表项的内容为0,则表示发生缺页异常,接下来会请求一个新的物理页,然后更新页表内容,完成映射过程。2)如果不为0,则为是一个映射到swap区的缺页异常。当然不会直接到这两个分支,还需要根据错误号,做进一步判断。

下面完整的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
82
83
//vmm.c
/* do_pgfault - 处理页中断异常的主要函数
* @mm : 管理可用虚拟内存空间的结构体
* @error_code : 处理器抛出的异常码
* @addr : CR2寄存器保存的发生页访问错误的线性地址
*/
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);//在测试中 addr = 100h

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;
}
//判断异常类型,与3,即&11b,取后两位
switch (error_code & 3) {
default:
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: //对应物理页存在,但是读异常,应该是权限问题,直接报错
cprintf("do_pgfault failed: error code flag = read AND present\n");
goto failed;
case 0: //缺页,读异常,下面判断物理页是否可读,若可读,通过下面流程将该物理页映射,若不可写,则报错
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;
}
}
/* 剩下两种情况:
* 1. 写一个不存在的可写物理地址
* 2. 读一个不存在的可读物理地址
*/
uint32_t perm = PTE_U;//perm为PDE(页目录项)/PTE(页项)的权限位
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;
}

//如果该页表内容为0,说明未建立映射,
if (*ptep == 0) { // pgdir_alloc_page申请一个物理页,并建立映射
if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
cprintf("pgdir_alloc_page in do_pgfault failed\n");
goto failed;
}
}
else { // 否则就是映射到swap区,需要将磁盘中的数据加载到物理页
// 调用 page_insert 重新建立映射
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_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;
}

下面是实现FIFO页面置换算法的_fifo_map_swappable函数

1
2
3
4
5
6
7
8
9
10
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);//获取当前使用的维护物理页的Page结构体的地址

assert(entry != NULL && head != NULL);
list_add(head, entry);//所以实现链接效果,只要添加这一句就可以了
return 0;
}

使用一个双向链表维护一个队列,用来保存物理页的使用情况。每次不论重新分配物理页建立映射,还是将磁盘中的数据装入物理内存建立映射,即每次物理页被使用,都会更新Page数据结构的pra_page_link链表,上面说了,这个链表按时间先后连接被使用的物理页,用以FIFO的页面置换算法,每次新使用的物理页都会链接在链表的末尾。

下面是实现的FIFO页面置换算法的_fifo_swap_out_victim函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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->next;
assert(head!=le);
struct Page *p = le2page(le, pra_page_link);//通过Page的成员pra_page_link获取Page的指针
list_del(le);
assert(p !=NULL);
*ptr_page = p;
return 0;
}

上面的队列保存的是正在使用的物理页,如果物理内存满了,就需要将正在使用的物理页置换到外存中,该函数_fifo_swap_out_victim就是删除队列中对首的最早使用的物理页,并用ptr_page保存。

分析测试数据

在测试中,只提供了4个物理页进行分配,首先建立了4个物理页的映射

1
2
3
4
5
6
7
//swap.c
//CHECK_VALID_PHY_PAGE_NUM = 4
for (i=0;i<CHECK_VALID_PHY_PAGE_NUM;i++) {
check_rp[i] = alloc_page();
assert(check_rp[i] != NULL );
assert(!PageProperty(check_rp[i]));
}

然后通过直接写内存数据触发缺页中断,总共发生12次内存写

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
//swap_fifo.c
static int
_fifo_check_swap(void) {
cprintf("write Virt Page c in fifo_check_swap\n");
*(unsigned char *)0x3000 = 0x0c;_
assert(pgfault_num==4);
cprintf("write Virt Page a in fifo_check_swap\n");
*(unsigned char *)0x1000 = 0x0a;
assert(pgfault_num==4);
cprintf("write Virt Page d in fifo_check_swap\n");
*(unsigned char *)0x4000 = 0x0d;
assert(pgfault_num==4);
cprintf("write Virt Page b in fifo_check_swap\n");
*(unsigned char *)0x2000 = 0x0b;
assert(pgfault_num==4);
cprintf("write Virt Page e in fifo_check_swap\n");//页面置换开始
*(unsigned char *)0x5000 = 0x0e;//页面置换开始
assert(pgfault_num==5);
cprintf("write Virt Page b in fifo_check_swap\n");
*(unsigned char *)0x2000 = 0x0b;
assert(pgfault_num==5);
cprintf("write Virt Page a in fifo_check_swap\n");
*(unsigned char *)0x1000 = 0x0a;
assert(pgfault_num==6);
cprintf("write Virt Page b in fifo_check_swap\n");
*(unsigned char *)0x2000 = 0x0b;
assert(pgfault_num==7);
cprintf("write Virt Page c in fifo_check_swap\n");
*(unsigned char *)0x3000 = 0x0c;
assert(pgfault_num==8);
cprintf("write Virt Page d in fifo_check_swap\n");
*(unsigned char *)0x4000 = 0x0d;
assert(pgfault_num==9);
cprintf("write Virt Page e in fifo_check_swap\n");
*(unsigned char *)0x5000 = 0x0e;
assert(pgfault_num==10);
cprintf("write Virt Page a in fifo_check_swap\n");
assert(*(unsigned char *)0x1000 == 0x0a);
*(unsigned char *)0x1000 = 0x0a;
assert(pgfault_num==11);
return 0;
}

下面分析测试结果

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
set up init env for check_swap begin!
page fault at 0x00001000: K/W [no page found].
page fault at 0x00002000: K/W [no page found].
page fault at 0x00003000: K/W [no page found].
page fault at 0x00004000: K/W [no page found].
set up init env for check_swap over!
write Virt Page c in fifo_check_swap
write Virt Page a in fifo_check_swap
write Virt Page d in fifo_check_swap
write Virt Page b in fifo_check_swap
write Virt Page e in fifo_check_swap
page fault at 0x00005000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2
write Virt Page b in fifo_check_swap
write Virt Page a in fifo_check_swap
page fault at 0x00001000: K/W [no page found].
*ptep!=0
swap_out: i 0, store page in vaddr 0x2000 to disk swap entry 3
swap_in: load disk swap entry 2 with swap_page in vadr 0x1000
write Virt Page b in fifo_check_swap
page fault at 0x00002000: K/W [no page found].
*ptep!=0
swap_out: i 0, store page in vaddr 0x3000 to disk swap entry 4
swap_in: load disk swap entry 3 with swap_page in vadr 0x2000
write Virt Page c in fifo_check_swap
page fault at 0x00003000: K/W [no page found].
*ptep!=0
swap_out: i 0, store page in vaddr 0x4000 to disk swap entry 5
swap_in: load disk swap entry 4 with swap_page in vadr 0x3000
write Virt Page d in fifo_check_swap
page fault at 0x00004000: K/W [no page found].
*ptep!=0
swap_out: i 0, store page in vaddr 0x5000 to disk swap entry 6
swap_in: load disk swap entry 5 with swap_page in vadr 0x4000
write Virt Page e in fifo_check_swap
page fault at 0x00005000: K/W [no page found].
*ptep!=0
swap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2
swap_in: load disk swap entry 6 with swap_page in vadr 0x5000
write Virt Page a in fifo_check_swap
page fault at 0x00001000: K/R [no page found].
swap_out: i 0, store page in vaddr 0x2000 to disk swap entry 3
swap_in: load disk swap entry 2 with swap_page in vadr 0x1000
count is 0, total is 7

可以看出程序要对0x00005000进行写时出现缺页中断,但是物理页已经满了,就把0x00001000对应的物理页置换到swap区……

最后12次写中,发生了7次缺页异常。

其他

使用gdb查看mm_struct 和 vma_struct 结构体的内容

查看 mm_struct 和 vma_struct 结构体的内容。可以看到初始时,只有一个页目录表项,维护了一个页表,该页表维护了0~4M的虚拟内存空间

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
gef➤  p check_mm_struct
$3 = (struct mm_struct *) 0xc0303000

gef➤ p *((struct mm_struct *) 0xc0303000)
$12 = {
mmap_list = {
prev = 0xc0304010,
next = 0xc0304010
},
mmap_cache = 0xc0304000,
pgdir = 0xc0120000,
map_count = 0x1,
sm_priv = 0x0
}

gef➤ p *((struct vma_struct *) (0xc0304010-0x10))
$13 = {
vm_mm = 0xc0303000,
vm_start = 0x0,
vm_end = 0x400000,
vm_flags = 0x2,
list_link = {
prev = 0xc0303000,
next = 0xc0303000
}
}
查看页表内容,可以看到页表中没有任何映射
gef➤ x/4xw 0xc0120000
0xc0120000: 0x00000000 0x00000000 0x00000000 0x00000000

页面置换算法分类

局部页面置换算法:1.最优算法 2.FIFO算法 3.最近最久未使用算法 4.时钟置换算法 5.最不常用算法

全局页面置换算法:1.工作集置换算法 2.缺页率置换算法

局部性原理

程序在执行过程中的一个较短的时期内,所执行的指令地址和指令操作数地址,分别局限于一定区域,包括时间局部性、空间局部性、分支局部性