Posted on 2007-10-12 11:38
ZelluX 閱讀(874)
評論(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: 穿梭而來]