In The End

个人博客

0%

操作系统：面向对象编程与双向循环链表

发表于 更新于 分类于

用C语言模拟面向对象编程

虽然C语言没有面向对象的概念，但是我们可以通过函数指针灵活地模拟出C++的接口(interface)概念，即是让实现细节不同的某类内核子系统（比如物理内存分配器、调度器，文件系统等）有共同的操作方式，这样虽然内存子系统的实现千差万别，但它的访问接口是不变的。这样不同的内核子系统之间就可以灵活组合在一起，实现风格各异，功能不同的操作系统。接口在 C 语言中，表现为一组函数指针的集合。放在 C++ 中，即为虚表。接口设计的难点是如果找出各种内核子系统的共性访问/操作模式，从而可以根据访问模式提取出函数指针列表。

比如对于uCore内核中的物理内存管理子系统，首先通过分析内核中其他子系统可能对物理内存管理子系统，明确物理内存管理子系统的访问/操作模式，定义了pmm_manager数据结构（位于lab2/kern/mm/pmm.h）如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// pmm_manager是一个物理内存管理类。举个例子，如果要具体实现就可以命名为XXX_pmm_manager
// 只要完成函数指针指向的函数的具体编写，就可以使用
// 通过ucore操作系统来管理整个物理内存空间
struct pmm_manager {
  	//管理器的名字
    const char *name;  
    // 初始化内部描述和管理数据结构，XXX_pmm_manager的空闲块数量和空闲块列表
    void (*init)(void); 
    // 分析空闲物理内存并初始化 
    void (*init_memmap)(struct Page *base, size_t n); 
    // 根据分配算法，分配>=n个页面
    struct Page *(*alloc_pages)(size_t n);  
    // 释放>=n个具有“基本”addr的页面描述符结构的页面(memlayout.h)
    void (*free_pages)(struct Page *base, size_t n);   
    // 返回空闲页面的数量
    size_t (*nr_free_pages)(void);                     
    // 检查XXX_pmm_manager的正确性
    void (*check)(void);                               
};

这样基于此数据结构，我们可以实现不同连续内存分配算法的物理内存管理子系统，而这些物理内存管理子系统需要编写算法，把算法实现在此结构中定义的init（初始化）、init_memmap（分析空闲物理内存并初始化管理）、alloc_pages（分配物理页）、free_pages（释放物理页）函数指针所对应的函数中。而其他内存子系统需要与物理内存管理子系统交互时，只需调用特定物理内存管理子系统所采用的pmm_manager数据结构变量中的函数指针即可

双向循环链表

因为编写操作系统的过程中经常会用到双向循环链表，所以实验指导书中给出了双向循环链表的练习，所以顺便来介绍一下双向循环链表。

在uCore内核（从lab2开始）中使用了大量的双向循环链表结构来组织数据，包括空闲内存块列表、内存页链表、进程列表、设备链表、文件系统列表等的数据组织（在[labX/libs/list.h]实现），但其具体实现借鉴了Linux内核的双向循环链表实现，与“数据结构”课中的链表数据结构不太一样。

首先一个数据结构课上的双向循环链表一般是这样的

1
2
3
4
5
typedef struct foo {
    ElemType data;
    struct foo *prev;
    struct foo *next;
} foo_t;

但是下面来介绍Linux和uCode的双向循环链表

首先将两个指针封装

1
2
3
struct list_entry {
    struct list_entry *prev, *next;
};

先不管真正的数据放在哪，我们先来回顾双向循环链表的基本操作

初始化

首先我们需要一个并不存放真正数据的头节点（所谓的哨兵），在最开始的时候将它的prev和next都指向自己

1
2
3
4
static inline void
list_init(list_entry_t *elm) {
    elm->prev = elm->next = elm;
}

插入

插入有在指定节点前面插入，以及指定节点后面插入，以及头插法尾插法等等。但是究其根源实际上都是基础插入操作的扩展（所谓基础插入，就是在指定节点点的后面插入）。

所以我们封装一个最基本的操作

1
2
3
4
5
6
static inline void
__list_add(list_entry_t *elm, list_entry_t *prev, list_entry_t *next) {
    prev->next = next->prev = elm;
    elm->next = next;
    elm->prev = prev;
}

然后我们从这个基础函数开始扩展

1
2
3
4
static inline void
list_add_after(list_entry_t *listelm, list_entry_t *elm) {
    __list_add(elm, listelm, listelm->next);
}
1
2
3
4
static inline void
list_add_before(list_entry_t *listelm, list_entry_t *elm) {
    __list_add(elm, listelm->prev, listelm);
}

我们可以看到，list_add_after就是__list_add本身的功能，所以直接传参进即可。list_add_before我们可以用个小技巧，找到当前节点的前驱，然后对当前节点的前驱执行__list_add就行

删除

当需要删除空闲块链表中的Page结构的链表节点时，可调用内联函数list_del，而list_del进一步调用了__list_del来完成具体的删除操作。其实现为：

1
2
3
4
5
6
7
8
9
static inline void
list_del(list_entry_t *listelm) {
    __list_del(listelm->prev, listelm->next);
}
static inline void
__list_del(list_entry_t *prev, list_entry_t *next) {
    prev->next = next;
    next->prev = prev;
}

如果要确保被删除的节点listelm不再指向链表中的其他节点，这可以通过调用list_init函数来把listelm的prev、next指针分别自身，即将节点置为空链状态。这可以通过list_del_init函数来完成。

移动

这个很简单了，直接放代码

1
2
3
4
5
6
7
8
9
static inline list_entry_t *
list_next(list_entry_t *listelm) {
    return listelm->next;
}

static inline list_entry_t *
list_prev(list_entry_t *listelm) {
    return listelm->prev;
}

判断是否为空

只要判断自己的next是不是自己就行，如果自己的next都指向自己了那肯定是个空的链表

1
2
3
4
5
static inline int
list_empty(list_entry_t *list) {
    if(list->next == list) return 1;
    else return 0;
}

在这还翻车了一波，忘记了C语言并没有bool变量。。。

访问链表节点所在的宿主数据结构

放一段打印链表的代码来解释

1
2
3
4
5
6
7
8
9
void output(P* p){
    P* k=p;
    k=list_next(p);
    while(k!=p){
        printf("%d ",((Node*)k)->val);
        k=list_next(k);
    }
    puts("");
}

我们一直对一个并没有真正数据的struct来操作，我们在使用的时候得封装一个新的struct，那么我们如何通过struct内部的一个类型来访问宿主类型呢

1
printf("%d ",((Node*)k)->val);

由于C语言的语言特性，我们只需要强制转换类型就行，因为一个结构体的数据在内存中都是放在一起的

下面放一下实验指导书中的实现

1
2
3
4
5
6
7
8
9
10
11
12
/* Return the offset of 'member' relative to the beginning of a struct type */
#define offsetof(type, member)                                      \
((size_t)(&((type *)0)->member))

/* *
 * to_struct - get the struct from a ptr
 * @ptr:    a struct pointer of member
 * @type:   the type of the struct this is embedded in
 * @member: the name of the member within the struct
 * */
#define to_struct(ptr, type, member)                               \
((type *)((char *)(ptr) - offsetof(type, member)))

这里采用了一个利用gcc编译器技术的技巧，即先求得数据结构的成员变量在本宿主数据结构中的偏移量，然后根据成员变量的地址反过来得出属主数据结构的变量的地址。

我们首先来看offsetof宏，size_t最终定义与CPU体系结构相关，本实验都采用Intel X86-32 CPU，顾szie_t等价于 unsigned int。 ((type )0)->member的设计含义是什么？其实这是为了求得数据结构的成员变量在本宿主数据结构中的偏移量。为了达到这个目标，首先将0地址强制”转换”为type数据结构（比如struct Page）的指针，再访问到type数据结构中的member成员（比如page_link）的地址，即是type数据结构中member成员相对于数据结构变量的偏移量。在offsetof宏中，这个member成员的地址（即“&((type )0)->member)”）实际上就是type数据结构中member成员相对于数据结构变量的偏移量。对于给定一个结构，offsetof(type,member)是一个常量，to_struct宏正是利用这个不变的偏移量来求得链表数据项的变量地址。接下来再分析一下to_struct宏，可以发现 to_struct宏中用到的ptr变量是链表节点的地址，把它减去offsetof宏所获得的数据结构内偏移量，即就得到了包含链表节点的属主数据结构的变量的地址。

代码

list.h

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#ifndef __LIBS_LIST_H__
#define __LIBS_LIST_H__

#ifndef __ASSEMBLER__

#include <stdio.h>

struct list_entry {
    struct list_entry *prev, *next;
};

typedef struct list_entry list_entry_t;

static inline void list_init(list_entry_t *elm) __attribute__((always_inline));
static inline void list_add(list_entry_t *listelm, list_entry_t *elm) __attribute__((always_inline));
static inline void list_add_before(list_entry_t *listelm, list_entry_t *elm) __attribute__((always_inline));
static inline void list_add_after(list_entry_t *listelm, list_entry_t *elm) __attribute__((always_inline));
static inline void list_del(list_entry_t *listelm) __attribute__((always_inline));
static inline void list_del_init(list_entry_t *listelm) __attribute__((always_inline));
static inline int list_empty(list_entry_t *list) __attribute__((always_inline));
static inline list_entry_t *list_next(list_entry_t *listelm) __attribute__((always_inline));
static inline list_entry_t *list_prev(list_entry_t *listelm) __attribute__((always_inline));

static inline void __list_add(list_entry_t *elm, list_entry_t *prev, list_entry_t *next) __attribute__((always_inline));
static inline void __list_del(list_entry_t *prev, list_entry_t *next) __attribute__((always_inline));

static inline void
list_init(list_entry_t *elm) {
    elm->prev = elm->next = elm;
}

static inline void
list_add(list_entry_t *listelm, list_entry_t *elm) {
    list_add_after(listelm, elm);
}

static inline void
list_add_before(list_entry_t *listelm, list_entry_t *elm) {
    __list_add(elm, listelm->prev, listelm);
}

static inline void
list_add_after(list_entry_t *listelm, list_entry_t *elm) {
    __list_add(elm, listelm, listelm->next);
}

static inline void
list_del(list_entry_t *listelm) {
    __list_del(listelm->prev, listelm->next);
}

static inline void
list_del_init(list_entry_t *listelm) {
    list_del(listelm);
    list_init(listelm);
}

static inline int
list_empty(list_entry_t *list) {
    if(list->next == list) return 1;
    else return 0;
}

static inline list_entry_t *
list_next(list_entry_t *listelm) {
    return listelm->next;
}

static inline list_entry_t *
list_prev(list_entry_t *listelm) {
    return listelm->prev;
}

static inline void
__list_add(list_entry_t *elm, list_entry_t *prev, list_entry_t *next) {
    prev->next = next->prev = elm;
    elm->next = next;
    elm->prev = prev;
}

static inline void
__list_del(list_entry_t *prev, list_entry_t *next) {
    prev->next = next;
    next->prev = prev;
}

#endif /* !__ASSEMBLER__ */

#endif /* !__LIBS_LIST_H__ */


list.c

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#include "list.h"
#include <stdlib.h>

typedef list_entry_t P;

typedef struct node{
    P point;
    int val;
}Node;

void add(P* p,int pos,int val){
    pos--;
    while(pos){
        p=list_next(p);
        pos--;
    }
    Node* u=(Node*)malloc(sizeof(Node));
    u->val=val;
    list_add(p,&(u->point));
}

void del(P* p,int pos){
    while(pos){
        p=list_next(p);
        pos--;
    }
    list_del(p);
}

void output(P* p){
    P* k=p;
    k=list_next(p);
    while(k!=p){
        printf("%d ",((Node*)k)->val);
        k=list_next(k);
    }
    puts("");
}

int main(){
    Node head;
    P* head_p=&head.point;
    list_init(head_p);
    head.val=0;
    printf("Select the linked list operation:\n");
    printf("1.Insert a new node\n");
    printf("2.remove a node\n");
    printf("3.output all nodes\n");
    int x,pos,val;
    int flag=1;
    while(flag){
        scanf("%d",&x);
        switch(x){
            case 1:{
                       scanf("%d%d",&pos,&val);
                       add(head_p,pos,val);
                       break;
                   }
            case 2:{
                       scanf("%d",&pos);
                       del(head_p,pos);
                       break;
                   }
            case 3:{
                       output(head_p);
                       break;
                   }
            default:{
                        flag=0;
                        break;
                    }
        }
    }
    return 0;
}