1

lab3 — 虚拟内存管理

 2 years ago
source link: https://yanglei253.github.io/2021/06/08/ucore/lab3/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

lab3 — 虚拟内存管理

发表于

2021-06-08 分类于 ucore

本文字数: 3.7k 阅读时长 ≈ 3 分钟

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

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

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 的具体实现。

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

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 的实现,说明如何处理缺页中断。

// 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 所维护的页面链表。


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK