Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

内核中的List结构

Posted on 2007-10-12 11:38 ZelluX 阅读(748) 评论(4)  编辑  收藏 所属分类: System
发信人: CJC (蓝色雪狐), 信区: 05SS
标  题: OS_Lab3 指南 List
发信站: 复旦燕曦BBS (2007年10月11日03:55:12 星期四), 转信

    先写点List的东西吧,这个其实在以前并不作为重点讲,不过好像大家对它还是有些偏
见,所以这次稍微讲下吧。作用是为到时候建立进程关系列表做准备。
    讲的内容都在/usr/src/linux.../include/linux/list.h中,大家只要把一些不必要的
ifdef和一些prefetch的东西删掉就好了。

    首先讲讲历史。在没有范型的Java里面我们用的链表往往会这样(如果转成C的话):
typedef struct list_head {
    struct list_node *prev;
    void *data;
    struct list_node *next;
} list_t;
    通过这个结构,我们就能完成链表的功能了。但是我觉得这个数据结构不好,原因有二

    第一:这个结构比较容易引起内存碎片。
    ┌──┬─┬──┐
    │prev│  │next│<----多余内存消耗
    └──┴┼┴──┘
            │   ┌───┐
            └─>│ data │
                 └───┘

    这种设计每一个节点都会引起一块多余的内存消耗。

    第二:类型不明确,因为现在没办法用范型。如果写明了类型,那么还要为每种类型的
list自己再做一整套函数,得不偿失。

    当然,还会考虑类似于我们希望用别人写得比较好的代码之类的原因。

    那让我们来看看我们版本里的list_t是怎么定义的
typedef struct list_head {
    struct list_head *next, *prev;
} list_t;
    乍一看,这个list_head里面什么都没包含,只有一对前后指针,没有指向数据的指针
。那怎么用呢?这里的做法我叫做:反包含。我们来看一个具体的使用例子:
typedef struct test_struct {
    int val1;
    int val2;
    char vals[4];
    list_t all_tests;   //千万注意,这里是list_t,不是list_t *
} test_t;

    那么我们声明了这个数据结构在内存中是什么样的呢?
 (test_list)         ┌─────┐┬    <--my_test_struct_p(test_t *)
┌──┬──┐       │   val1   ││
│prev│next├┐     ├─────┤│
└──┴──┘│     │   val2   ││h
              │     ├─────┤│
              │     │   vals   ││
表示指向首地址└──>├──┬──┤┴    <--my_list_p(list_t *)
                     │prev│next│      //这里如果是list_t *就不是这样画了!
                     └──┴──┘

    上图就是一个test_t的结构图。小地址在上,大地址在下,val1上面的那条分界线作为
val1的起始地址(请注意我my_test_struct_p及其它指针的画法,是指向上面那根线,表示
为那个东西的起始地址,为清楚起见推荐大家以后这样画)
    然后为了把所有的test_t数据结构串起来,我们需要一个全局变量:test_list,类行
为list_t(如果这里声明list_t *的话一定要为它分配空间!如果是死的全局变量、全局数
组和一些临时数组,推荐直接声明成类型而不是指针,因为编译器会放在dat/bss和stack段
里。但是如果这个数据结构是返回类型的分配空间,一定要malloc!否则回去就会错。这里
也提醒一下)
    我们可以看到test_list.next是指向my_test_struct_p->all_tests,而不是my_test_s
truct。但是对我有用的应该是my_test_struct。所以一般处理方法有二,
    第一种比较死板,就是在数据结构的一开始就放一个list_t(命名为list),那么&lis
t=&stru,可以直接(xxx *)list_p。但是问题是如果一个数据结构可以同属两个链表,如pc
b,又要是run_list的成员,又要是all_tasks的成员,还要是父进程children的成员……这
种方法显然是不够的。
    第二种方法就相对好些。大家可以看,
    ((unsigned int)my_list_p)-h=(unsigned int)my_test_struct_p
    而怎么得到h呢?是不是需要每个数据结构都定义一个h呢?不需要,可以这样看
    h=(unsigned int)(&(((test_t *)0)->all_tests))
    就是把0地址当作是test_t数据结构的开始地址,那么这个数据结构的all_tests所在的
地址就是h了。
    通过把这两个算式结合,我们可以得到一个宏:
#define list_entry(ptr, type, member) \
    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
    在这里的用法就是:
    my_test_struct_p = list_entry(test_list.next, test_t, all_tests);
    (如果使用类似于Simics的编辑器的话,all_tests的显示会是类似于没有定义变量,
不用管它,的确是这样的。最后编译成功就对了)。
    看过了最精妙的list_entry之后我们就可以来看一些简单的操作了
#define INIT_LIST_HEAD(ptr) do { \
    (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
    为什么要加while(0)可以参见lab2指南里面的一些define帮助。其大致概念如下:
┌─────────┐
│                  │
└->┌──┬──┐  │
┌─┤prev│next├─┘     //这里为了画清逻辑,不把指针放在首地址
│  └──┴──┘<-┐
│                  │
└─────────┘

    这是一个环状链表。一般这个作为头指针,链表为空的判断依据就是:
static inline int list_empty(struct list_head *head)
{
    return head->next == head;
}
    然后是添加,先有一个辅助函数:
static inline void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}
    这个是添加在第一个:
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}
┌───────────────────┐
│                     ┌─────┐   │
└->┌──┬──┐┌─>├──┬──┤   │
┌─┤prev│next├┘ ┌┤prev│next├-─┘  //这里的数据结构就省略画了
│  └──┴──┘<─┘├──┴──┤ <-┐
│                     └─────┘   │
└───────────────────┘
                          ori_first
┌────────────────────────────┐
│                     ┌─────┐     ┌─────┐  │
└->┌──┬──┐┌─>├──┬──┤┌─>├──┬──┤  │
┌─┤prev│next├┘ ┌┤prev│next├┘ ┌┤prev│next├─┘
│  └──┴──┘<─┘├──┴──┤<─┘├──┴──┤<-┐
│                     └─────┘     └─────┘  │
└────────────────────────────┘

                            new             ori_first

    这个是添加在head->prev,由于是环状的,那么就是添在了最后一个
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}
┌────────────────────────────┐
│                     ┌─────┐     ┌─────┐  │
└->┌──┬──┐┌─>├──┬──┤┌─>├──┬──┤  │
┌─┤prev│next├┘ ┌┤prev│next├┘ ┌┤prev│next├─┘
│  └──┴──┘<─┘├──┴──┤<─┘├──┴──┤<-┐
│                     └─────┘     └─────┘  │
└────────────────────────────┘
                         ori_first             new


    接下来是删除:
    这是辅助方法
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
    next->prev = prev;
    prev->next = next;
}
    这个是用了辅助方法__list_del并且把entry的前后都设为NULL,是为了安全起见
static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = (void *) 0;
    entry->prev = (void *) 0;
}
    个人觉得list_del_init, list_move, list_move_tail, list_splice没啥太大作用…
…不过后面两个非常重要:
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_prev(pos, head) \
    for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
            pos = pos->prev, prefetch(pos->prev))

使用方法:
list_t *pos;
list_for_each(pos, &test_list) {
    test_t *tmp = list_entry(pos, test_t, all_tests);
    //do something on tmp
}
=======================================================================
list_t *pos, *n;
list_for_each_safe(pos, n, &test_list) {
    test_t *tmp = list_entry(pos, test_t, all_tests);
    //do something on tmp
}
======================================================================
    那么这两个有什么差别呢?我们可以来看这个例子:
list_for_each(pos, &test_list) {
    list_del(pos);
}
    首先,我们得到pos=test_list.next,然后删除,此时pos->next=0,如果按照list_fo
r_each的话下一个循环的pos就是NULL,再访问下去就出错了!同样的,修改位置也是。所
以在需要修改队列结构的时候,一定要使用list_for_each_safe。如果只修改对应的数据结
构其他字段,可以用list_for_each,因为这个效率比较高。

    有了这些方法基本上就可以使用了。我们可以来看一个物理内存管理的例子:
#define USER_MEM_SIZE (256*1024*1024)
#define USER_MEM_START (16*1024*1024)
#define PAGE_SHIFT 12
#define PAGE_SIZE (1<<(PAGE_SHIFT))
#define PAGE_COUNT (((USER_MEM_SIZE)-(USER_MEM_START))>>(PAGE_SHIFT))
#define PAGE_START(ptr) (((ptr)-(all_pages))<<(PAGE_SHIFT)+(USER_MEM_START))
//获取这个page数据结构对应的起始地址
#define PAGE_STRU(addr) (&all_pages[((addr)-(USER_MEM_START))<<(PAGE_SHIFT)])

typedef struct page_struct {
    unsigned long use_count;
    list_t mem_list;
} page_t;

list_t free_list, lru_list; //lru是用作换出的,最近使用在队首,换出队尾页
//如果编译器不肯让我们这样定义的话用lmm_alloc或者out_alloc也可以。
page_t all_pages[PAGE_COUNT];

void init()
{
    int i;
    INIT_LIST_HEAD(&free_list);
    INIT_LIST_HEAD(&lru_list);      //初始化两个链表
    for (i = 0; i < PAGE_COUNT; i++) {
        all_pages[i] = 0;
        list_add_tail(&all_pages[i].mem_list, &free_list);  //加入free_list
    }
}

//此处返回值作为错误信息,addr作为所需返回的物理内存起始地址
int get_page(unsigned int *addr)
{
    if (list_empty(&free_list)) //没有空页
        return -1;
    list_t *lst = free_list.next;
    list_del(lst);
    list_add(lst, &lru_list);   //最近使用,放到队首
    *addr = PAGE_START(list_entry(lst, page_t, mem_list);
    return 0;
}

void use_page(unsigned int addr)
{
    page_t *pg = PAGE_STRU(addr);
    list_del(&pg->mem_list);
    list_add(&pg->mem_list, &lru_list); //将页面放到lru队列首
}

void return_page(unsigned int addr)
{
    page_t *pg = PAGE_STRU(addr);
    list_del(&pg->mem_list);
    list_add(&pg->mem_list, &free_list); //将页面放到free队列首,下次取时用
}

    物理页面管理基本上就类似于此。我们接下来来看一个稍微复杂些的例子,就是进程父
子关系的例子,去年又同学跟我反映这是一个交错链接或者说是嵌套链接,其实不然。我们
拆分开来看:
         ┌─────────-┐
         │┌-────────┼───┐
         │ ↘ A->children    │      │
┌───-┼─>┌──┬──┐  │      │
│       └-─┤prev│next├┐│      │
│            └──┴──┘││      │
│┌────────────┘│      │
││                 ┌-───┘      │
││ ┌─────┐   ↘┌─────┐│
│└>├──┬──┤┌─>├──┬──┤│
└-─┤prev│next├┘ ┌┤prev│next├┘
     ├──┴──┤<─┘├──┴──┤
     └─────┘     └─────┘
           B                  C

    由图可知,A有BC两个子进程,分别连接到A进程的children上。此时,处理A的childre
n又有两种方法,第一种是增加指针,第二种是作为A进程的一部分。利用上面的思考方法,
我们可以知道,如果按照第一种做法,那么势必会引起更多的内存碎片,不方便。于是我们
把children作为pcb的一个field。那么B和C里面的prev/next该叫什么呢?因为B和C也是pc
b的数据结构,已经不可能再叫children了(而且他们也应该有children节点,因为他们也
可能有子进程)。那么我们就叫它为sibling吧。因为在这个链表里,除了A是父进程,其余
的都是兄弟进程。
    所以pcb的父子关系可以这样写:
#define TASK_STATE_RUNNING 0
#define TASK_STATE_ZOMBIE 1
//调用了wait指令,等待子进程结束
#define TASK_STATE_WAIT_CHILD 2

typedef struct pcb_struct{
    struct pcb_struct *parent;  父进程
    unsigned long state;
    list_t children;
    list_t sibling;
    list_t all_tasks;
} pcb_t;

//init是一个非常特殊的进程,一般我们的kernel一起来,就只负责两个进程:init和idle
//init的作用是先fork,子进程运行shell,它自身while(1) {wait(...);}就是负责回收
//孤儿进程。
//并且在此,我们可以把所有的进程都连接在init的all_tasks上面,这样又可以节省一个
//相当于前例test_list的全局变量。找所有进程只须遍历init->all_tasks即可。
//所以在生成init的时候应该是INIT_LIST_HEAD(&task->all_tasks)
void init_pcb(pcb_t *task, pcb_t *init)
{
    INIT_LIST_HEAD(&task->children);
    INIT_LIST_HEAD(&task->sibling);
    task->parent = NULL;
    task->state = TASK_STATE_RUNNING;
    list_add_tail(&task->all_tasks, &init->all_tasks);
}

void add_child(pcb_t *parent, pcb_t *child)
{
    child->parent = parent;
    list_add_tail(&child->sibling, &parent->children);  //想想为什么
}

void do_exit(pcb_t *task, pcb_t *init)
{
    //exit_mem_first_part
    list_t *pos, *n;
    list_for_each_safe(pos, n, &task->children) //将所有子进程交给init
    {           //~~~~
        task_t *child = list_entry(pos, task_t, sibling); //这里是sibling
        child->parent = init;
        list_del(&child->sibling);
        list_add_tail(&child->sibling, &init_children);
        if (child->state == TASK_STATE_ZOMBIE && init->state != TASK_STATE_WAIT_
CHILD)
        {
            //这里激活init,并把init放到进程列表的尾端
        }
    }
    //然后切换到父进程运行
}
    如果看懂了以上的所有例子,那么链表结构应该就差不多了。由于篇幅关系,PCB的构
建就单列开来吧。这里专门讲LIST好了。:)
    如果有代码觉得看的郁闷的,拿张纸画画对应的内存结构应该就会好些了
--

※ 修改:·CJC 于 Oct 11 03:57:46 修改本文·[FROM: 穿梭而来]
※ 来源:·复旦燕曦BBS yanxibbs.cn·[FROM: 穿梭而来]

评论

# re: 内核中的List结构  回复  更多评论   

2007-10-12 13:17 by Damocles
cjc??不是03ss的吗?

# re: 内核中的List结构  回复  更多评论   

2007-10-12 17:00 by ZelluX
@Damocles
恩,他发在yanxi,我转了一篇过来

# re: 内核中的List结构  回复  更多评论   

2007-10-14 00:12 by Damocles
他不是去中科大了吗?

# re: 内核中的List结构  回复  更多评论   

2007-10-14 00:24 by ZelluX
@Damocles
他上学期是我们的Web应用课的TA
这学期怎么样就不清楚了 @,@

只有注册用户登录后才能发表评论。


网站导航: