OS-Lab2 实验报告
Contents
思考题
Thinking 2.1
请根据上述说明，回答问题：在编写的C 程序中，指针变量中存储的地址被视为虚拟地址，还是物理地址？MIPS 汇编程序中 lw 和 sw 指令使用的地址被视为虚拟地址，还是物理地址？
均为虚拟地址。
Thinking 2.2
请思考下述两个问题：
• 从可重用性的角度，阐述用宏来实现链表的好处。
• 查看实验环境中的/usr/include/sys/queue.h，了解其中单向链表与循环链表的实现，比较它们与本实验中使用的双向链表，分析三者在插入与删除操作上的性能差异。
- 使用宏实现链表，可以方便地支持不同的数据类型，实现类似其他语言当中范型的效果。
- 下附单向链表与循环链表的实现：
/*
* Singly-linked List definitions.
*/
#define SLIST_HEAD(name, type) \
struct name { \
struct type *slh_first; /* first element */ \
}
#define SLIST_HEAD_INITIALIZER(head) \
{ NULL }
#define SLIST_ENTRY(type) \
struct { \
struct type *sle_next; /* next element */ \
}
/*
* Singly-linked List functions.
*/
#define SLIST_INIT(head) do { \
(head)->slh_first = NULL; \
} while (/*CONSTCOND*/0)
#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
(elm)->field.sle_next = (slistelm)->field.sle_next; \
(slistelm)->field.sle_next = (elm); \
} while (/*CONSTCOND*/0)
#define SLIST_INSERT_HEAD(head, elm, field) do { \
(elm)->field.sle_next = (head)->slh_first; \
(head)->slh_first = (elm); \
} while (/*CONSTCOND*/0)
#define SLIST_REMOVE_HEAD(head, field) do { \
(head)->slh_first = (head)->slh_first->field.sle_next; \
} while (/*CONSTCOND*/0)
#define SLIST_REMOVE(head, elm, type, field) do { \
if ((head)->slh_first == (elm)) { \
SLIST_REMOVE_HEAD((head), field); \
} \
else { \
struct type *curelm = (head)->slh_first; \
while(curelm->field.sle_next != (elm)) \
curelm = curelm->field.sle_next; \
curelm->field.sle_next = \
curelm->field.sle_next->field.sle_next; \
} \
} while (/*CONSTCOND*/0)
#define SLIST_FOREACH(var, head, field) \
for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
/*
* Singly-linked List access methods.
*/
#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
#define SLIST_FIRST(head) ((head)->slh_first)
#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)/*
* Circular queue functions.
*/
#define CIRCLEQ_INIT(head) do { \
(head)->cqh_first = (void *)(head); \
(head)->cqh_last = (void *)(head); \
} while (/*CONSTCOND*/0)
#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
(elm)->field.cqe_next = (listelm)->field.cqe_next; \
(elm)->field.cqe_prev = (listelm); \
if ((listelm)->field.cqe_next == (void *)(head)) \
(head)->cqh_last = (elm); \
else \
(listelm)->field.cqe_next->field.cqe_prev = (elm); \
(listelm)->field.cqe_next = (elm); \
} while (/*CONSTCOND*/0)
#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
(elm)->field.cqe_next = (listelm); \
(elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
if ((listelm)->field.cqe_prev == (void *)(head)) \
(head)->cqh_first = (elm); \
else \
(listelm)->field.cqe_prev->field.cqe_next = (elm); \
(listelm)->field.cqe_prev = (elm); \
} while (/*CONSTCOND*/0)
#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
(elm)->field.cqe_next = (head)->cqh_first; \
(elm)->field.cqe_prev = (void *)(head); \
if ((head)->cqh_last == (void *)(head)) \
(head)->cqh_last = (elm); \
else \
(head)->cqh_first->field.cqe_prev = (elm); \
(head)->cqh_first = (elm); \
} while (/*CONSTCOND*/0)
#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
(elm)->field.cqe_next = (void *)(head); \
(elm)->field.cqe_prev = (head)->cqh_last; \
if ((head)->cqh_first == (void *)(head)) \
(head)->cqh_first = (elm); \
else \
(head)->cqh_last->field.cqe_next = (elm); \
(head)->cqh_last = (elm); \
} while (/*CONSTCOND*/0)
#define CIRCLEQ_REMOVE(head, elm, field) do { \
if ((elm)->field.cqe_next == (void *)(head)) \
(head)->cqh_last = (elm)->field.cqe_prev; \
else \
(elm)->field.cqe_next->field.cqe_prev = \
(elm)->field.cqe_prev; \
if ((elm)->field.cqe_prev == (void *)(head)) \
(head)->cqh_first = (elm)->field.cqe_next; \
else \
(elm)->field.cqe_prev->field.cqe_next = \
(elm)->field.cqe_next; \
} while (/*CONSTCOND*/0)
#define CIRCLEQ_FOREACH(var, head, field) \
for ((var) = ((head)->cqh_first); \
(var) != (const void *)(head); \
(var) = ((var)->field.cqe_next))
#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
for ((var) = ((head)->cqh_last); \
(var) != (const void *)(head); \
(var) = ((var)->field.cqe_prev))
/*
* Circular queue access methods.
*/
#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
#define CIRCLEQ_LAST(head) ((head)->cqh_last)
#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
#define CIRCLEQ_LOOP_NEXT(head, elm, field) \
(((elm)->field.cqe_next == (void *)(head)) \
? ((head)->cqh_first) \
: (elm->field.cqe_next))
#define CIRCLEQ_LOOP_PREV(head, elm, field) \
(((elm)->field.cqe_prev == (void *)(head)) \
? ((head)->cqh_last) \
: (elm->field.cqe_prev))可以看到，单向链表的删除需要 O(n) 的时间，而循环链表和本实验的双向链表的插入删除操作均只需要 O(1) 的时间。另外，循环链表提供了更为方便的尾部插入操作。
Thinking 2.3
请阅读include/queue.h 以及include/pmap.h, 将Page_list 的结构梳理清楚，选择正确的展开结构。
//A: struct Page_list{ struct { struct { struct Page *le_next; struct Page *le_prev; } pp_link; u_short pp_ref; }* lh_first; } //B: struct Page_list{ struct { struct { struct Page *le_next; struct Page **le_prev; } pp_link; u_short pp_ref; } lh_first; } //C: struct Page_list{ struct { struct { struct Page *le_next; struct Page **le_prev; } pp_link; u_short pp_ref; }* lh_first; }
C.每一个链表项内部应包括一个指向下一个元素的指针和一个指向上一个元素中的next指针的指针，头节点包括一个指向第一个链表节点的指针。
Thinking 2.4
请思考下面两个问题：
• 请阅读上面有关TLB 的描述，从虚拟内存和多进程操作系统的实现角度，阐述ASID的必要性。
• 请阅读MIPS 4Kc 文档《MIPS32® 4K™ Processor Core Family Software User’sManual》的Section 3.3.1 与Section 3.4，结合ASID 段的位数，说明4Kc 中可容纳不同的地址空间的最大数量。
- 不同进程可能存在相同的虚拟地址，而他们映射的物理地址不同。如果没有ASID，不同进程切换时就需要同步刷新TLB，性能下降。
- ASID共8位，TLB根据不同的ASID判断不同的地址空间，故可容纳2^8=256个不同的地址空间。
Thinking 2.5
请回答下述三个问题：
• tlb_invalidate 和tlb_out 的调用关系？
• 请用一句话概括tlb_invalidate 的作用。
• 逐行解释tlb_out 中的汇编代码。
tlb_invalidate调用tlb_out- tlb_invalidate负责将旧的TLB项清空。
LEAF(tlb_out)
.set noreorder
mfc0 t0, CP0_ENTRYHI //将当前的EntryHi存入t0
mtc0 a0, CP0_ENTRYHI //将传入的虚拟地址写入EntryHi
nop //流水线延迟槽
/* Step 1: Use 'tlbp' to probe TLB entry */
/* Exercise 2.8: Your code here. (1/2) */
tlbp //根据EntryHi查找TLB
nop //流水线延迟槽
/* Step 2: Fetch the probe result from CP0.Index */
mfc0 t1, CP0_INDEX //将查询到的Index写入t1
.set reorder
bltz t1, NO_SUCH_ENTRY //如果Index<0，说明没找到，跳转
.set noreorder
mtc0 zero, CP0_ENTRYHI //EntryHi清零
mtc0 zero, CP0_ENTRYLO0 //EntryLo0清零
mtc0 zero, CP0_ENTRYLO1 //EntyrLo1清零
nop //流水线延迟槽
/* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index */
/* Exercise 2.8: Your code here. (2/2) */
tlbwi //将清零项写入TLB，实现无效化
.set reorder
NO_SUCH_ENTRY:
mtc0 t0, CP0_ENTRYHI //恢复最初的EntryHi
j ra //返回
END(tlb_out)Thinking 2.6
请结合Lab2 开始的CPU 访存流程与下图中的Lab2 用户函数部分，尝试将函数调用与 CPU 访存流程对应起来，思考函数调用与 CPU 访存流程的关系。
函数调用时，底层汇编代码通过虚拟地址访问内存。而虚拟地址向物理地址转换则以来虚拟内存系统和CPU访存机制。
Thinking 2.7
从下述三个问题中任选其一回答：
• 简单了解并叙述 X86 体系结构中的内存管理机制，比较 X86 和 MIPS 在内存管理上的区别。
• 简单了解并叙述 RISC-V 中的内存管理机制，比较 RISC-V 与 MIPS 在内存管理上的区别。
• 简单了解并叙述 LoongArch 中的内存管理机制，比较 LoongArch 与MIPS 在内存管理上的区别。
- x86采用了段页式内存管理，利用分段机制将逻辑地址映射为线性地址，再通过分页机制将线性地址映射为物理地址。这与MIPS中的页式内存不同。
- x86的页表结构由CPU强制规定，而MIPS时设计在软件中。
- TLB Miss时，x86由硬件遍历页表并填充TLB，软件感知不到这一过程，而MIPS中由软件进行Miss异常处理。
- x86的地址空间通过特权级（Ring0-3）结合页表属性控制，而MIPS在硬件上直接划分了kuseg，kseg0， kseg1等区域。
- 总的来说，x86提供了更强的封装性，硬件操作更多，而MIPS直接将底层暴露，具体的行为由开发者实现。
难点分析
链表
在操作系统内核中，我们定义的链表与常规链表不同。常规链表的写法如下：
struct node {
struct node* prev;
struct node* next;
DATATYPE data;
}Node;而在操作系统中，链表结构往往定义成这样：
//Head
struct name {
struct type *lh_first;
}
//Entry
struct {
struct {
struct type *le_next;
struct type **le_prev;
};
DATATYPE data;
}
这样设计的好处在哪里呢？仔细分析，可以发现：
- 链表结构与数据分离。由于C语言本身不支持范型，这样的设计可以很好的在宏里实现一个通用的链表操作，实际使用只需要加上不同类型的数据，便可以使用写好的宏操作很方便的操作链表，无需手写复杂的函数。
- 插入与删除的通用性。我们正常的链表，实现插入删除的时候，要么需要为头节点进行特判，要么需要新增一个永远不会被删除的头节点。但是这样的头节点要求其类型必须与普通节点一样，但是我们实际并不需要储存prev、data信息，会造成浪费。而单独定义的头节点+二级指针(prev为指向前一个节点的next字段的指针)，即可以使用相同的操作进行头节点与非头节点的处理。
两级页表与TLB机制
经过CO的学习，多级页表与TLB从理解层面其实不成问题。难点在于，我们需要时刻记住不同层级虚拟地址的结构，以及在这其中地址是如何转换、并最终得到物理地址的。而在Extra考察的自映射机制，实则一方面是考察理解，同时更重要的也是考察对代码的熟悉度，以及清楚的知道每一个操作需要干什么。这一部分，还是要多结合代码和示意图，才能更好的理解。
实验体会
通过本次试验，我对操作系统底层的内存管理机制有了更深刻的理解，尤其是TLB机制的引入，为写程序时的内存管理提供了优化思路。
原创说明
本篇均为原创，部分问题与AI讨论得出。