Operator System Lab 2 上机实验回顾

C/C++ OS
操作系统
发布日期:   2023-04-04
更新日期:   2024-03-18
文章字数:   1.7k
阅读时长:   8 分
阅读次数:  

Exam

题面

实现函数 u_int page_perm_stat(Pde *pgdir, struct Page *pp, u_int perm_mask) 。

函数介绍：遍历以 pgdir 为页目录基地址的整个二级页表，找到指向 pp 的且权限至少为 perm_mask 页表项个数，并输出找到的个数。

我的代码

u_int page_perm_stat(Pde *pgdir, struct Page *pp, u_int perm_mask) {
	u_int count = 0;
	for (u_int i = 0; i < (1u << 10); i++) {
		Pde *pgdir_entryp = pgdir + i;
		if (*pgdir_entryp & PTE_V) {
			Pte *pte = (Pte *) KADDR(PTE_ADDR(*pgdir_entryp));
			for (u_int j = 0; j < (1u << 10); j++) {
				Pte *pte_entryp = pte + j;
				if ((*pte_entryp & PTE_V) && (*pte_entryp & perm_mask) == perm_mask) {
					if (pa2page(PTE_ADDR(*pte_entryp)) == pp)
						count++;
				}
			}
		}
	}
	return count;
}

代码解释

  1. u_int count = 0; 定义了一个用于计数的变量。
  2. for (u_int i = 0; i < (1u << 10); i++) 这层循环遍历页目录下的所有页表项。
  3. Pde *pgdir_entryp = pgdir + i; 这是页目录下的页表项。
  4. if (*pgdir_entryp & PTE_V) 如果这个页表项是有效的。
  5. Pte *pte = (Pte *) KADDR(PTE_ADDR(*pgdir_entryp)); PTE_ADDR 取高 20 位，然后 KADDR 把物理地址转换为虚拟地址，于是得到 (二级) 页表基地址。
  6. for (u_int j = 0; j < (1u << 10); j++) 遍历整个页表。
  7. Pte *pte_entryp = pte + j; 这是一个页表项。
  8. (*pte_entryp & PTE_V) 判断页表项是否有效。
  9. (*pte_entryp & perm_mask) == perm_mask 判断页表项是否包含相应权限。
  10. pa2page(PTE_ADDR(*pte_entryp)) == pp 判断是否指向指定页表，pa2page 把物理地址转换为页表控制结构体。

Extra

题面

实现内存交换机制。不限制策略和效率。

指定位于 $[0x3900000, 0x3910000)$ 的 16 个物理页作为可交换内存。使用 swap_alloc 申请可交换内存，如果可交换内存全部已满，则将一个页面换出到外存。使用 swap_lookup 查找虚拟地址对应物理内存，如果该内存已被换出，则需要换入。

这里课程组使用了一个 u_char 数组模拟外存，总计有 64 个外存页。我们只需要调用 disk_alloc 和 disk_free 就可以申请和释放外存了。

题目为填空题，已有代码如下：

#include <swap.h>

struct Page_list page_free_swapable_list;
static u_char *disk_alloc();
static void disk_free(u_char *pdisk);

void swap_init() {
	LIST_INIT(&page_free_swapable_list);
	for (int i = SWAP_PAGE_BASE; i < SWAP_PAGE_END; i += BY2PG) {
		struct Page *pp = pa2page(i);
		LIST_REMOVE(pp, pp_link);
		LIST_INSERT_HEAD(&page_free_swapable_list, pp, pp_link);
	}
}

// Interface for 'Passive Swap Out'
struct Page *swap_alloc(Pde *pgdir, u_int asid) {
	// Step 1: Ensure free page
	if (LIST_EMPTY(&page_free_swapable_list)) {
		/* Your Code Here (1/3) */
	}
	// Step 2: Get a free page and clear it
	struct Page *pp = LIST_FIRST(&page_free_swapable_list);
	LIST_REMOVE(pp, pp_link);
	memset((void *)page2kva(pp), 0, BY2PG);
	return pp;
}

// Interfaces for 'Active Swap In'
static int is_swapped(Pde *pgdir, u_long va) {
	/* Your Code Here (2/3) */
}

static void swap(Pde *pgdir, u_int asid, u_long va) {
	/* Your Code Here (3/3) */
}

Pte swap_lookup(Pde *pgdir, u_int asid, u_long va) {
	// Step 1: If corresponding page is swapped out, swap it in
	if (is_swapped(pgdir, va)) {
		swap(pgdir, asid, va);
	}
	// Step 2: Look up page table element.
	Pte *ppte;
	page_lookup(pgdir, va, &ppte);
	// Step 3: Return
	return ppte == NULL ? 0 : *ppte;
}

// Disk Simulation (Do not modify)
u_char swap_disk[SWAP_DISK_NPAGE * BY2PG] __attribute__((aligned(BY2PG)));
u_char swap_disk_used[SWAP_DISK_NPAGE];
static u_char *disk_alloc() {
	int alloc = 0;
	for (;alloc < SWAP_DISK_NPAGE && swap_disk_used[alloc]; alloc++) {
		;
	}
	assert(alloc < SWAP_DISK_NPAGE);
	swap_disk_used[alloc] = 1;
	return &swap_disk[alloc * BY2PG];
}

static void disk_free(u_char *pdisk) {
	int offset = pdisk - swap_disk;
	assert(offset % BY2PG == 0);
	swap_disk_used[offset / BY2PG] = 0;
}

内存交换流程：

  1. 换入过程：
    1. 申请一个可交换内存页（使用 swap_alloc）
    2. 将换出到外存的数据全部拷贝到新申请到的页
    3. 将所有指向该外存的页表项全部指向新内存页
    4. 将所有指向该外存的页表项的 PTE_V 置 1，PTE_SWP 置 0
    5. 释放外存页
  2. 换出过程：
    1. 选择一个要换出的内存页（任何策略都可以接受）
    2. 申请一个新的外存页（使用 disk_alloc）
    3. 将所有指向该内存页的页表项全部指向新外存页
    4. 将所有指向该内存页的页表项的 PTE_V 置 0，PTE_SWP 置 1
    5. 复制内存页的全部数据到外存
    6. 释放内存页，并将其插入空闲页表队列

代码实现

Your Code Here (1/3)

struct Page *swap_alloc(Pde *pgdir, u_int asid) {
	// Step 1: Ensure free page
	if (LIST_EMPTY(&page_free_swapable_list)) {
        // random chose one page to swap out
        u_long pa = 0x3900000 + (asid % 16) * BY2PG; // chose page (asid % 16)
        u_long da = (u_long) disk_alloc(); // alloc a disk page
        page_swap_out_lookup(pgdir, asid, pa, da); // update page table entries
        // note: copy memory should use va, thus using KADDR to convert
        memcpy((void *)PTE_ADDR(da), (void *)KADDR(PTE_ADDR(pa)), BY2PG); // copy memory
        struct Page *pp = pa2page(pa); // get page
        pp->pp_ref = 0; // no looger use
        page_free(pp); // free page
        LIST_INSERT_HEAD(&page_free_swapable_list, pp, pp_link); // insert to head
    }
    // Step 2: Get a free page and clear it
	struct Page *pp = LIST_FIRST(&page_free_swapable_list);
	LIST_REMOVE(pp, pp_link);
	memset((void *)page2kva(pp), 0, BY2PG);
	return pp;
}

Your Code Here (2/3)

static int is_swapped(Pde *pgdir, u_long va) {
    // note: you can refer to va2pa in pmap.h
    pgdir = &pgdir[PDX(va)]; // get pgdir entry
    if (!(*pgdir & PTE_V)) return 0; // not valid
    Pte *pte = (Pte *) KADDR(PTE_ADDR(*pgdir)); // get page table entry
    if (!(pte[PTX(va)] & PTE_V) && (pte[PTX(va)] & PTE_SWP)) return 1; // swapped
    return 0; // not swapped
}

Your Code Here (3/3)

static void swap(Pde *pgdir, u_int asid, u_long va) {
    struct Page *pp = swap_alloc(pgdir, asid); // alloc a new page
    Pte *pte = (Pte *) KADDR(PTE_ADDR(pgdir[PDX(va)])); // get pte of va
    u_long da = PTE_ADDR(pte[PTX(va)]); // get da what pte point to
    u_long kva = PTE_ADDR(page2kva(pp)); // get kva of the new page
    memcpy((void *)kva, (void *)da, BY2PG); // copy from disk to the new page
    u_long pa = (u_long) page2pa(pp); // get pa of the new page
    page_swap_in_lookup(pgdir, asid, pa, da); // update page table entries
    disk_free((u_char *)da); // free disk memory
}

Tool Functions

// note: these are similar to page_perm_stat in Lab2-exam.

/* Overview:
 *   Walk through all the page table entries of pgdir
 *   to find all the entries that point to pa
 *   and change these entries to satify swap outs.
 */
void page_swap_out_lookup(Pde *pgdir, u_int asid, u_long pa, u_long da) {
	for (u_int i = 0; i < (1u << 10); i++) {
		Pde *pgdir_entryp = pgdir + i;
		if (*pgdir_entryp & PTE_V) {
			Pte *pte_entryp = (Pte *) KADDR(PTE_ADDR(*pgdir_entryp));
			for (u_int j = 0; j < (1u << 10); j++) {
				Pte *pte = pte_entryp + j;
				if ((*pte & PTE_V) && PTE_ADDR(*pte) == PTE_ADDR(pa)) {
					*pte = (*pte & 0xfff) | PTE_ADDR(da); // point to da
					*pte = (*pte & ~PTE_V) | PTE_SWP; // modify term
					u_long va = ((u_long)i << 22) + ((u_long)j << 12);
					tlb_invalidate(asid, va); // invalidate TLB
				}
			}
		}
	}
}

/* Overview:
 *   Walk through all the page table entries of pgdir
 *   to find all the entries that point to da
 *   and change these entries to satify swap ins.
 */
void page_swap_in_lookup(Pde *pgdir, u_int asid, u_long pa, u_long da) {
	for (u_int i = 0; i < (1u << 10); i++) {
		Pde *pgdir_entryp = pgdir + i;
		if (*pgdir_entryp & PTE_V) {
			Pte *pte_entryp = (Pte *) KADDR(PTE_ADDR(*pgdir_entryp));
			for (u_int j = 0; j < (1u << 10); j++) {
				Pte *pte = pte_entryp + j;
				if ((*pte & PTE_SWP) && PTE_ADDR(*pte) == PTE_ADDR(da)) {
					*pte = (*pte & 0xfff) | PTE_ADDR(pa); // point to pa
					*pte = (*pte & ~PTE_SWP) | PTE_V; // modify term
					u_long va = ((u_long)i << 22) + ((u_long)j << 12);
					tlb_invalidate(asid, va); // invalidate TLB
				}
			}
		}
	}
}

小结

其实整篇写下来也没有什么难度。可是在考场上要一下写那么多内核代码还是很困难的。特别是你不理解每个变量名是什么意思的时候。另外善用 pmap.h 和 mmu.h 中的地址相关宏也是很重要的。

  1. PDX(va) 页目录偏移量，即 ((((u_long)(va)) >> 22) & 0x03FF)
  2. PTX(va) 页表偏移量，即 ((((u_long)(va)) >> 12) & 0x03FF)
  3. PTE_ADDR(pte) 获取页表项中的物理地址，即 ((u_long)(pte) & ~0xFFF)，也就是获取高 20 位
  4. PADDR(kva) kseg0 处虚拟地址 → 物理地址，即 (kva - ULIM)，ULIM 是 0x80000000
  5. KADDR(pa) 物理地址 → kseg0 处虚拟地址，即 (kva + ULIM)，ULIM 是 0x80000000
  6. u_long va2pa(Pde *pgdir, u_long va) 查页表，虚拟地址 → 物理地址
  7. struct Page *pa2page(u_long pa) 物理地址 → 页控制块
  8. u_long page2pa(struct Page *pp) 页控制块 → 物理地址
  9. u_long page2kva(struct Page *pp) 页控制块 → kseg0 处虚拟地址

–ddbdd248d7e5d7618b606ffd008610bd–

C/C++ OS
评论
  目录