OS-lab2

OWPETER Lv3
  2025-04-12 14:52:26 2025-04-12 14:52:26 Created   2025-04-12 14:53:21 2025-04-12 14:53:21 Updated      1.8k Words  6 Mins  

思考题

Thinking 2.1

C程序中的指针存储的地址与mips中lw, sw访存的地址均为虚拟地址

Thinking 2.2

  • 使用宏来实现链表能够很好的实现代码复用，减少代码量同时提高程序可读性。
  • 单向链表在插入与删除时都需要进行遍历操作，因此时间复杂度均为。循环链表依然是单向的，但其维护了一个尾项指针，因此插入尾项的复杂度为，其余操作均为。双向链表的链表项中存储了指向前项的指针与后项的指针，因此插入、删除操作的复杂度为，但如果项在链表尾部插入链表项，依然需要遍历整个链表。

Thinking 2.3

Page_List的正确结构应为C

1
2
3
4
5
6
7
8
9
struct Page_list{
    struct {
        struct {
            struct Page *le_next;
            struct Page **le_prev;
        } pp_link;
        u_short pp_ref;
    }* lh_first;
}

2.4

  • 每个进程都会被分配一块自己的虚拟地址空间，不同虚拟地址在不同地址空间中会映射到不同的物理地址，ASID就是用来区分当前的虚拟地址是被哪个进程所使用，以确定其映射到的物理地址。
  • ASID在4Kc处理器中是8位的，因此8位的ASID可以标识2^8=256个不同的地址空间

2.5

  • tlb_invalid函数中调用了tlb_out
  • tlb_invalid的作用是在页表内容改变后及时更新TLB
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
LEAF(tlb_out)
.set noreorder
	mfc0    t0, CP0_ENTRYHI         # 将EntryHi寄存器中的值写入t0
	mtc0    a0, CP0_ENTRYHI         # 将a0寄存器中的值写入EntryHi
	nop
	/* Step 1: Use 'tlbp' to probe TLB entry */
	/* Exercise 2.8: Your code here. (1/2) */
	tlbp                            # 根据EntryHi中的值查找旧表项，
                                        # 并将表项的索引存入Index

	nop
	/* Step 2: Fetch the probe result from CP0.Index */
	mfc0    t1, CP0_INDEX           # 将Index的值存入t1
.set reorder
	bltz    t1, NO_SUCH_ENTRY       # 如果t1的值小于0，
                                        # 跳转至NO_SUCH_ENTRY标签
.set noreorder
	mtc0    zero, CP0_ENTRYHI       # 将EntryHi, EntryLo0, EntryLo1置0
	mtc0    zero, CP0_ENTRYLO0
	mtc0    zero, CP0_ENTRYLO1
	nop
	/* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index  */
	/* Exercise 2.8: Your code here. (2/2) */
	tlbwi                           # 将EntryHi和EntryLo0寄存器中的值存到Index对应的TLB表项中

.set reorder

NO_SUCH_ENTRY:
	mtc0    t0, CP0_ENTRYHI         # 将t0中的值存入EntryHi，即恢复到tlb_out调用前状态
	j       ra
END(tlb_out)

2.6

根据访存流程和用户函数部分的图示，可以得到函数调用与CPU访存流程的对应关系：

  1. CPU发出访存指令
  2. 查询目标页面是否在TLB中
    • 如果在，直接读取PPN并结合offset完成访存
    • 如果不在TLB中，触发TLB Miss
  3. tlb miss，会导致用户进程暂停，进入一个handler，并调用_do_tlb_refill
  4. 在_do_tlb_refill函数中调用page_lookup，在页目录中查找页表
    • 如果页表项无效，那么调用passive_alloc函数分配新的页表并填写到页目录项
    • 如果有效，从页表中查找
  5. 从页表中查找页表项
    • 如果页表项无效，调用page_alloc函数分配新页面并填写到页表项
    • 如果有效，取出相邻就业，填写到EntryLo，写回TLB，再次访存。

2.7

在内存管理机制上，X86使用分段和分页的结合方式，分段机制复杂但灵活，MIPS主要依赖分页机制，分段支持较弱，管理更简单直接。在TLB方面，X86：虽然也有TLB，但其内存管理机制更复杂，TLB的实现可能有所不同；MIPS依赖TLB来加速地址转换，对于TLB的使用更直接。总体来说，X86 的内存管理机制更复杂，但有着更高的灵活性，而MIPS的内存管理机制更简单，适合对性能和功耗要求较高的场景。

实验难点

本次实验有两个主要难点：物理内存管理机制与二级页表查询机制

Page结构与管理机制

实验中的操作系统利用Page结构体来管理物理页，他的结构类似于双向链表，包含一个指向后一项的指针，和一个指向前一项中“指向后一项的指针”的指针。这个指针的指针存在的意义是，当需要删除当前项时，可以方便的修改前一个元素向后的指针。

在实验中，我们将所有空闲的Page结构体链接在Page_list类型的page_free_list上。对于Page_list结构的定义是这个样子的：

1
2
3
4
5
6
7
8
// pmap.h
LIST_HEAD(Page_list, Page);

// queue.h
#define LIST_HEAD(name, type)                                                                      \
	struct name {                                                                              \
		struct type *lh_first; /* first element */                                         \
	}

所以简化之后其实就是一个Page类型的指针。

1
2
3
struct Page_list {
	struct Page* lh_first;
}

在实验中，使用LIST_INIT宏对其进行初始化，其实就是把lh_first指向null。到此，我们就可以将空闲的Page结构体链接在这个page_free_list的链表头上了，这一过程是通过page_init()完成的。

接下来我们需要了解Page结构体的结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// pmap.h
struct Page {
	Page_LIST_entry_t pp_link; /* free list link */
	u_short pp_ref;
};

typedef LIST_ENTRY(Page) Page_LIST_entry_t;

// queue.h
#define LIST_ENTRY(type)                                                                           \
	struct {                                                                                   \
		struct type *le_next;  /* next element */                                          \
		struct type **le_prev; /* address of previous next element */                      \
	}

经过简化，我们可以得到这样的结构：

1
2
3
4
5
6
7
struct Page {
	struct{
		struct Page* le_next;
		struct Page** le_prev;
	} pp_link;
	u_short pp_ref;
};

也就是说，Page包含了一个short类型的pp_ref，和一个包含两个指针的pp_link域，根据指导书，这两个指针分别指向下一个Page结构体，和上一个Page的le_next指针。

再接下来，我们来研究一下queue.h中的宏应该如何使用。例如LIST_NEXT：

1
#define LIST_NEXT(elm, field) ((elm)->field.le_next)

首先观察到->，说明elm需要一个指针，而field是这个指针指向的一个结构体中的一个元素，并且field是一个包含了名为le_next元素的结构体。因此在lab2中，我们大概率是要这样调用这个宏：

1
2
struct Page* pp, next_pp;
next_pp = LIST_NEXT(pp, pp_link);

还有一种宏包含形参head，例如：

1
#define LIST_FIRST(head) ((head)->lh_first)

在理解了Page_list的结构后，很容易发现这里的head应该为一个Page_list类型的指针。而在pmap.c中只定义了一个Page_list类型的全局变量page_free_list，所以你大概率需要这样调用：

1
2
struct Page* pp;
pp = LIST_FIRST(&page_free_list);

二级页表管理虚拟内存

利用二级页表访问物理页是一个比较复杂的过程，其大致过程为：

  • 将虚拟地址分解为页目录偏移量+页偏移量+页内偏移量
  • 根据页目录基地址与页目录偏移量，找到页目录项，得到其中记录的物理页号
  • 根据页号与页偏移量，找到页表项，得到其中记录的物理页号
  • 根据物理页号和页内偏移量，得到物理地址

pgdir_walk函数的作用事实上就是以上过程的第二步。其根据给定的Pde* pgdir（页目录基地址）与va，获得页表项的地址

体会与感想

Lab2的代码量比Lab1大了不少，而且代码中大量使用了宏和指针，不免让人有些晕头转向，但是当完成之后再进行复盘，能够体会到对于内存管理的理解又加深了一层，整个实验是对理论知识非常充分的实践。

  • Title: OS-lab2
  • Author: OWPETER
  • Created at : 2025-04-12 14:52:26
  • Updated at : 2025-04-12 14:53:21
  • Link: https://owpeter.github.io/2025/04/12/OS-lab2/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
OS-lab2
  1. 思考题
    1. Thinking 2.1
    2. Thinking 2.2
    3. Thinking 2.3
    4. 2.4
    5. 2.5
    6. 2.6
    7. 2.7
  2. 实验难点
    1. Page结构与管理机制
    2. 二级页表管理虚拟内存
  3. 体会与感想