Posted on 2007-10-12 11:38
ZelluX 阅读(869)
评论(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: 穿梭而来]