os-lab2笔记

os-lab2

操作系统

发布日期: 2024-04-24

文章字数: 1.1k

阅读时长: 4 分

阅读次数:

#　lab2

首先我们需要关注include中的一些头文件以及其中定义的一些宏函数和静态内联函数。这些东西是真的难啊，让我觉得自己程设里面学的C语言和这里的不是一个东西。

首先要知道这些宏定义对应的英文全称和中文释义。
1. NASID：Node Abstract System Identifier，节点抽象系统标识符。
2. PAGE_SIZE：Page Size，页面大小。
3. PTMAP：Page Table Mapping，页表映射。
4. PDMAP：Page Directory Mapping，页目录映射。
5. PGSHIFT：Page Shift，页偏移。
6. PDSHIFT：Page Directory Shift，页目录偏移。
7. PDX：Page Directory Index，页目录索引。
8. PTX：Page Table Index，页表索引。
9. PTE_ADDR：Page Table Entry Address，页表条目地址。
10. PTE_FLAGS：Page Table Entry Flags，页表条目标志。
从整体上来理解，首先要知道几个基本的东西是啥。

其中包括Page_list和Page。LIST_HEAD(Page_list, Page);可以知道这几个对应在LIST中的几个基本要素。

typedef LIST_ENTRY(Page) Page_LIST_entry_t;虽然感觉这个类型宏替换意义不大。

LIST又是啥呢？这也好难，让我感觉自己的数据结构又是白学的😢

首先要坚信这个List就是我们学的那个链表，是一个双向链表。

这里的链表是有一个专门的头指针的，在ds中也有地方会这么用。(有一些好像还会有一些头发指针，头指针的前一个元素)这几个都是让链表的处理更加方便，也可以认为是大家认为链表的比较优雅的实现方式。

头指针：

LIST_HEAD(name, type)

也就是

struct name {
    struct type *lh_first;
}

实际上是定义了一个结构体，给这个结构提一个名字比如head，实际上就是LIST_HEAD(name, int) head;

宏替换后实际上就是

struct name {
    struct int *lh_first;
} head;

那么相应的一些与链表头指针的一些操作：

LIST_HEAD_INITIALIZER(head)

具体用法：

LIST_HRAD(name, int) *head;
head = LIST

对于每个结点的指针部分实际上就是

LIST_ENTRY(type)

也就是

struct {
    struct type *le_next;
    struct type **le_prev;
}

这里le_next可以理解，但是这个le_prev呢，这个给的注释也很奇怪，address of previous next element。这么来看，实际上就是将每个next指针作为一个element，那么prev就是前一个元素的这个指针。这样并不是双向链表那种，双向链表是多了一个指向前一个结点的大结点的地址的指针，也就是说可以通过这个指针直接访问前一个结点。而这个le_prev仅仅只是前一个元素的next这个元素的地址。

那么到这里其实就懂了，一个结点分为data和field。filed实际上就是优化版的next，包括next和prev两个元素。data的数据格式为struct type, next是struct type*，prev是struct type**;

那么我们简单总结一下这个链表的结构。首先是head，head是个头指针，里面包含有第一个元素的指针。每个结点包含data和field两个部分。

就可以很好理解LIST_NEXT(elm, field) 这个宏函数了。

(elm) -> field.le_next;

看一下LIST_FOREACH(var, head, field)这个宏定义，这里给出了一种遍历链表的方式。

for ((var) = LIST_FIRST((head)); (var); (var) = LIST_NEXT((var), field)

接下来实现LIST_INSERT_BEFORE(listelm, elm, field)，也即是在listelm前面添加elm。

一般的双向链表有下面这个就够了

LIST_NEXT((elm), field) = listelm;
// listelm->prev = elm; 类似这种的操作

但是由于添加了prev，需要更新elm和listelm的值。

(elm)->field.le_prev = (listelm)->field.le_prev;
(listelm)->field.le_prev = &LIST_NEXT((elm), field);
*(listelm)->field.le_prev = elm;

这里*的运算级是高于->的。

于是完成LIST_INSERT_AFTER(listelm, elm, field)就很简单了。

LIST_NEXT((elm), field) = LIST_NEXT((listelm), field);
if (LIST_NEXT((listelm), field))
    LIST_NEXT((listelm), field)->field.le_prev = &LIST_NEXT((elm), field);
LIST_NEXT((listelm), field) = elm;
elm->field.le_prev = &LIST_NEXT((listelm), field);