OS-lab2

lab2

上机

• lab2-exam 还是比较简单的，认真写肯定能对
• lab2-extra 这是专门给佬出的题，我就只把题面放到这了，造福后人了

lab2-exam

• 对于一个页表项，我们知道其存储的31-12位为物理页号，0-11是标志位，我们的任务是遍历整个页表的页表项，如果是有效页并且检查标志位perm_mask（可能是好几个标志位），如果都包含则计数，最后返回数量

u_int page_perm_stat(Pde *pgdir, struct Page *pp, u_int perm_mask)
{
	Pde *pd_entry;
	int sum = 0;
	int i = 0;
	for (pd_entry = pgdir; i < 1024; pd_entry++)       //一层循环遍历所有的页目录项
	{
		Pte *pt_entry;
		i++;
		int j = 0;
		if ((*pd_entry & PTE_V) != 0) //你的二级页表必须有效才能接着遍历
		{
			for (pt_entry = (Pte *)KADDR(PTE_ADDR(*pd_entry)); j < 1024; pt_entry++) //遍历所有页表项
			{
				j++;
				if ((*pt_entry & PTE_V) != 0)    //有效
				{
					if (((*pt_entry & perm_mask) == perm_mask) && (PTE_ADDR(*pt_entry) == page2pa(pp)))
					{                          //之前因为PTE_V都是一位，所以直接&运算不等于0就行，但是现在标志位可能有很多，必须是(*pt_entry & perm_mask) == perm_mask才能说明包含给定的标志位
						sum++;
					}
				}
			}
		}
	}
	return sum;
}

lab2-extra

真抽象，我觉得extra确实得有区分度，但是你得保证不能让绝大多数同学坐牢没一点收获吧。用机房的CLI是真难受，课下vscode用的是真爽，一个好的idea是优秀程序员的必备工具，CLI难蚌。

题目背景

在理论课程中，我们学习了交换技术。它实现进程在内存与外存之间的交换，因而获得更多的虚拟内存空间。

简单来说，交换空间（swap）是外存上的一块区域，当系统物理内存不足时，内核会将内存中不常访问的数据保存到 swap 上，这样系统就有更多的物理内存为各个进程服务，而当系统需要访问 swap 上存储的内容时，再将 swap 上的数据加载到内存中。这样相当于我们获得了更多的虚拟存储（通过使用一部分外存）。

在本题中，我们会实现一个较为简单的交换机制，使得在没有空闲的物理页面时，可以暂时将正在使用的一页内存换出，同时释放出一页物理页面用于使用。

题目描述
我们建立的交换机制可以分为两部分，“换入”部分，以及“换出”部分。

当我们没有空闲的物理页面时，我们进行“换出”，即申请物理页面时，如果没有可用的页面，我们换出一页正在使用的物理页，供申请者使用。

当我们需要访问某个 kuseg 段的虚拟地址时，我们会检查这个虚拟地址对应的虚拟页是否已被换出到外存，如果是，则我们将其“换入”。

虚拟页被换入的物理页可能与其被换出时不同，但需要保证换入后物理页中的数据以及页表项中的权限位与换出时相同。为此，我们需要在换出时利用外存来保存数据。

题目要求
在本题中，你需要使用物理地址属于 [0x3900000, 0x3910000) 的这 16 个物理页以及外存来实现“交换”。

在本题中我们把这 16 个物理页叫做可交换的物理页。
为了区分这些可交换的物理页，我们建立了一个新的空闲可交换页面链表 page_free_swapable_list。
同时，我们将提供部分代码（请参看实验提供代码部分），你需要将其粘贴至 kern/pmap.c 之后，并补全或者实现如下几个函数：

提示

我们给出一种可行的设计，当然，你也可以略过本节自己进行设计。

当没有空闲的物理页时，我们需要进行换出操作。在本设计中，我们在页表项中增加了一个新的标志位 PTE_SWP（在下发的头文件 swap.h 中已有定义）。

当 PTE_SWP 为 1 且 PTE_V 为 0 时:
对应的虚拟地址映射到的物理内存有效但被换出，实际的内容存在外存上，该页表项的高 20 位为内容在外存上的外存页号。
软件应保证不会出现 PTE_SWP 为 1 且 PTE_V 为 1 的页表项。
当 PTE_SWP 为 0 时，页表项的含义与 Lab2 课下定义的相同。
我们可以通过 da / BY2PG 计算 da 对应的外存页号
当我们希望将某个虚拟地址对应的物理页从外存中换入内存时：

使用 swap_alloc 申请一个物理页 p
将外存中以 da 起始的一页内容拷贝到该物理页 p 上（da 为换出时内容在外存上的地址）
对指定页表中，所有“PTE_SWP 为 1 且 PTE_V 为 0 且高 20 位为 da 对应的外存页号”的页表项，做如下操作：
将 PTE_V 置 1
将 PTE_SWP 置 0
在高 20 位中填入 p 对应的物理页号
维持其它权限位不变
无效化旧 TLB 表项
使用 disk_free 释放 da 起始的一页外存空间
当我们需要换出一个内存中的物理页至外存时：

从 [0x3900000, 0x3910000) 的内存空间中，选择一个物理页 p
使用 disk_alloc 申请一页大小的外存空间，记该外存空间的起始地址为 da
对指定页表中，所有 PTE_V 为 1 且高 20 位为 p 的物理页号的页表项，做如下操作：
将 PTE_V 置 0
将 PTE_SWP 置 1
在高 20 位中填入 da 对应的外存页号
维持其它权限位不变
无效化旧 TLB 表项
将物理页 p 上的内容拷贝到外存中 da 起始的一页空间上
释放物理页 p，也就是将其插回 page_free_swapable_list 链表中
任务总结
在提交前，你需要完成以下任务：

换入部分：
完成 is_swapped 函数。
完成 swap 函数，维护 page_free_swapable_list 链表，适时无效化 TLB 中的旧表项。
换出部分：
完成 swap_alloc 函数，维护 page_free_swapable_list 链表，适时无效化 TLB 中的旧表项。
本题不涉及课下代码的修改。
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);
}

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

---

实验报告

思考题

thinking 2.1

都是虚拟地址

thinking 2.2

• 复用性好，在之后操作系统中，如果需要建立双向链表，可以直接使用宏定义，对链表的一些操作很方便
• 没找见循环链表，除了实验中的双向链表外，还有一个tail queue，其实和双向链表差不多，知识在head维护了链表的首个元素和最后的元素。
  • 将元素插入到链表头部的时候，需要注意如果首个元素为NULL，则插入后的elm既是第一个有时第二个元素
  • 插入链表尾部的时候，维护head中的tqe_last, 但是如果链表为空呢，也得维护tqe_first
  • 插入到某个元素后面的时候，需要判断当前是不是tail，如果是，更新head的tqe_last
  • 删除操作也是，判断是不是链表尾部
• 我们发现这与我们常见的双向链表不一样，因为在filed.le_prev是一个指针的指针，存放的时候上一个元素field.le_next的指针，可能是为了既能做到插入元素，又可以保证访问顺序只能往下而不能往上吧

thinking 2.3

c，我们发现head其实只装了链表的首个元素指针

thinking 2.4

• 我们知道操作系统实现了多进程，让每个进程都认为自己独享“物理空间（实际是虚拟空间）”，但TLB只有一个，不同进程从虚拟空间到物理空间的映射不同，所以使用ASID，只有EntryHi中的虚拟页号和ASID与TLB中的KEY都相同才是对应的物理页号。
• 6位，对应256个不同地址空间

thinking 2.5

• tlb_invalidate 调用 tlb_out

• 当我们建立页表物理映射时，原本的映射可能存在也可能不存在，如果存在且和要映射的物理页面不同|新申请的页，需要更新TLB，下次加载va所在页时，TLB会重新加载，即用时才加载

• LEAF(tlb_out)
  .set noreorder
  	mfc0    t0, CP0_ENTRYHI  //把之前寄存器保存一下
  	mtc0    a0, CP0_ENTRYHI  //将a0即虚拟地址对应的虚拟页号存入到寄存器中
  	nop
  	/* Step 1: Use 'tlbp' to probe TLB entry */
  	/* Exercise 2.8: Your code here. (1/2) */
      tlbp                    //根据寄存器的虚拟页号和ASID，来查找TLB，若没找到，则index为负数
  	nop
  	/* Step 2: Fetch the probe result from CP0.Index */
  	mfc0    t1, CP0_INDEX    //去除索引
  .set reorder
  	bltz    t1, NO_SUCH_ENTRY //如果没找到就直接返回了
  .set noreorder
  	mtc0    zero, CP0_ENTRYHI  //找到的话，那就清空TLB对应项
  	mtc0    zero, CP0_ENTRYLO0
  	nop
  	/* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index  */
  	/* Exercise 2.8: Your code here. (2/2) */
      tlbwi                     //根据索引去请0
  .set reorder
  NO_SUCH_ENTRY:
  	mtc0    t0, CP0_ENTRYHI   
  	j       ra                //返回
  END(tlb_out)                 
  

thinking 2.6

在x86架构中内存被分为三种形式，分别是逻辑地址（Logical Address），线性地址（Linear Address）和物理地址（Physical Address）。如上图所示，通过分段可以将逻辑地址转换为线性地址，而通过分页可以将线性地址转换为物理地址。逻辑地址由两部分构成，一部分是段选择器（Segment Selector），一部分是偏移（Offset）。段选择符存放在段寄存器中，如CS（存放代码段选择符）、SS（存放堆栈段选择符）、DS（存放数据段选择符）和ES、FS、GS（一般也用来存放数据段选择符）等；偏移与对应段描述符（由段选择符决定）中的基地址相加就是线性地址。全局描述符表（Global Descriptor Table）需要OS在初始化时创建（每个CPU都有一张，基本内容大致相同，除了少数几项如TSS），创建好后将表的地址（这是个线性地址）放到全局描述符寄存器中（GDTR），这通过LGDT和SGDT指令来完成。

自映射

为方便区分，记三级页表基地址为PTbase2， 二级页表基地址为PTbase1， 页目录基地址为PDbase

PTbase1 = PTbase2 >> 30 << 21 + PTbase2 = PTbase2 >> 9 + PTbase2

PDbae = PTbase2 >> 9 >>21 << 12 + PTbase1 = PTbase2 >> 18 + PTbase2 >> 9 + PTbase2

PDE = PTbase >> 27 + PTbase >> 18 + PTbase >> 9 + PTbase

---

实验难点

物理地址和虚拟地址

• 在lab2中我们一直都处于内核态，我觉得这个就很抽象，导致2.1 - 2.5 始终对虚拟地址和物理地址搞不清，我们所写的代码都放在内核态，并不会影响我们对0x80400000之后空间的操作。然后我们时刻保持一个原则，所有的指针都是虚拟地址。比如page_init中，我们pages这个变量保存在内核态中，但所指的地址是在80400000，我们只是用pages来管理所对应的物理页。但是pages所指的地址存放了npage个page结构体，也就是说在前面的物理页中其实存放着page结构体。这样的话page_init就很好补充了
• 再如pgdir_walk, 传进来的pgdir是页目录的虚拟地址，我们可以很轻松的找到对应的页表项，如果creat为1，最开始我以为是让页表等于申请到的pp，这个时候就弄错了，页表是虚拟空间中的，所以应该是页目录项地址存储物理页号。先把物理地址转为虚拟地址，并且要按第十二位对齐，再加上二级页号偏移，最终 ppte应该页表项的地址，*ppte = (*Pte)PTE_ADDR(KADDR(*pgdir)) + PTX(va)

双向链表

空闲链表是双向的，但le_prev确实上一个元素le_next的指针，我们并不能通过le_prev访问上一个元素，这样既可以保证单向性又能保证链表的插入删除操作得以进行。例如我们想把elm插入到list_elm的前面

graph LR
prev(prev) -- le_next --> now(list_elm)
now -- le_next --> next(next)
now -- le_prev --> prev
next -- le_pev --> now

elm->le_next(没有写pp_link，问题不大) = list_elm

elm->le_prev = list_elm->le_prev

*(list_elm->prev) = elm

list_elm->prev = &(elm->le_next)

---

实验感受

• 我觉得OS不是一蹴而就的写完，是需要大量仔细看实验指导书，然后看源码，2.6我做了看了三遍，做了三遍，每次看都以为自己会了，写完发现不对，然后再看再写。
• 复用性高的宏是真的方便，能让代码看的整洁并且结构清楚