Posted on 2007-10-12 11:38
ZelluX 閱讀(887)
評論(4) 編輯 收藏 所屬分類:
System
發(fā)信人: CJC (藍(lán)色雪狐), 信區(qū): 05SS
標(biāo) 題: OS_Lab3 指南 List
發(fā)信站: 復(fù)旦燕曦BBS (2007年10月11日03:55:12 星期四), 轉(zhuǎn)信
先寫點(diǎn)List的東西吧，這個(gè)其實(shí)在以前并不作為重點(diǎn)講，不過好像大家對它還是有些偏
見，所以這次稍微講下吧。作用是為到時(shí)候建立進(jìn)程關(guān)系列表做準(zhǔn)備。
講的內(nèi)容都在/usr/src/linux.../include/linux/list.h中，大家只要把一些不必要的
ifdef和一些prefetch的東西刪掉就好了。
首先講講歷史。在沒有范型的Java里面我們用的鏈表往往會(huì)這樣（如果轉(zhuǎn)成C的話）：
typedef struct list_head {
struct list_node *prev;
void *data;
struct list_node *next;
} list_t;
通過這個(gè)結(jié)構(gòu)，我們就能完成鏈表的功能了。但是我覺得這個(gè)數(shù)據(jù)結(jié)構(gòu)不好，原因有二
：
第一：這個(gè)結(jié)構(gòu)比較容易引起內(nèi)存碎片。
┌──┬─┬──┐
│prev│ │next│<----多余內(nèi)存消耗
└──┴┼┴──┘
│ ┌───┐
└─>│ data │
└───┘
這種設(shè)計(jì)每一個(gè)節(jié)點(diǎn)都會(huì)引起一塊多余的內(nèi)存消耗。
第二：類型不明確，因?yàn)楝F(xiàn)在沒辦法用范型。如果寫明了類型，那么還要為每種類型的
list自己再做一整套函數(shù)，得不償失。
當(dāng)然，還會(huì)考慮類似于我們希望用別人寫得比較好的代碼之類的原因。
那讓我們來看看我們版本里的list_t是怎么定義的
typedef struct list_head {
struct list_head *next, *prev;
} list_t;
乍一看，這個(gè)list_head里面什么都沒包含，只有一對前后指針，沒有指向數(shù)據(jù)的指針
。那怎么用呢？這里的做法我叫做：反包含。我們來看一個(gè)具體的使用例子：
typedef struct test_struct {
int val1;
int val2;
char vals[4];
list_t all_tests; //千萬注意，這里是list_t，不是list_t *
} test_t;
那么我們聲明了這個(gè)數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中是什么樣的呢？
(test_list) ┌─────┐┬ <--my_test_struct_p(test_t *)
┌──┬──┐ │ val1 ││
│prev│next├┐ ├─────┤│
└──┴──┘│ │ val2 ││h
│ ├─────┤│
│ │ vals ││
表示指向首地址└──>├──┬──┤┴ <--my_list_p(list_t *)
│prev│next│ //這里如果是list_t *就不是這樣畫了！
└──┴──┘
上圖就是一個(gè)test_t的結(jié)構(gòu)圖。小地址在上，大地址在下，val1上面的那條分界線作為
val1的起始地址（請注意我my_test_struct_p及其它指針的畫法，是指向上面那根線，表示
為那個(gè)東西的起始地址，為清楚起見推薦大家以后這樣畫）
然后為了把所有的test_t數(shù)據(jù)結(jié)構(gòu)串起來，我們需要一個(gè)全局變量：test_list，類行
為list_t（如果這里聲明list_t *的話一定要為它分配空間！如果是死的全局變量、全局?jǐn)?shù)
組和一些臨時(shí)數(shù)組，推薦直接聲明成類型而不是指針，因?yàn)榫幾g器會(huì)放在dat/bss和stack段
里。但是如果這個(gè)數(shù)據(jù)結(jié)構(gòu)是返回類型的分配空間，一定要malloc!否則回去就會(huì)錯(cuò)。這里
也提醒一下）
我們可以看到test_list.next是指向my_test_struct_p->all_tests，而不是my_test_s
truct。但是對我有用的應(yīng)該是my_test_struct。所以一般處理方法有二，
第一種比較死板，就是在數(shù)據(jù)結(jié)構(gòu)的一開始就放一個(gè)list_t（命名為list），那么&lis
t=&stru，可以直接(xxx *)list_p。但是問題是如果一個(gè)數(shù)據(jù)結(jié)構(gòu)可以同屬兩個(gè)鏈表，如pc
b，又要是run_list的成員，又要是all_tasks的成員，還要是父進(jìn)程children的成員……這
種方法顯然是不夠的。
第二種方法就相對好些。大家可以看，
((unsigned int)my_list_p)-h=(unsigned int)my_test_struct_p
而怎么得到h呢？是不是需要每個(gè)數(shù)據(jù)結(jié)構(gòu)都定義一個(gè)h呢？不需要，可以這樣看
h=(unsigned int)(&(((test_t *)0)->all_tests))
就是把0地址當(dāng)作是test_t數(shù)據(jù)結(jié)構(gòu)的開始地址，那么這個(gè)數(shù)據(jù)結(jié)構(gòu)的all_tests所在的
地址就是h了。
通過把這兩個(gè)算式結(jié)合，我們可以得到一個(gè)宏：
#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的顯示會(huì)是類似于沒有定義變量，
不用管它，的確是這樣的。最后編譯成功就對了）。
看過了最精妙的list_entry之后我們就可以來看一些簡單的操作了
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
為什么要加while(0)可以參見lab2指南里面的一些define幫助。其大致概念如下：
┌─────────┐
│ │
└->┌──┬──┐ │
┌─┤prev│next├─┘ //這里為了畫清邏輯，不把指針放在首地址
│ └──┴──┘<-┐
│ │
└─────────┘
這是一個(gè)環(huán)狀鏈表。一般這個(gè)作為頭指針，鏈表為空的判斷依據(jù)就是：
static inline int list_empty(struct list_head *head)
{
return head->next == head;
}
然后是添加，先有一個(gè)輔助函數(shù)：
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;
}
這個(gè)是添加在第一個(gè)：
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
┌───────────────────┐
│ ┌─────┐ │
└->┌──┬──┐┌─>├──┬──┤ │
┌─┤prev│next├┘ ┌┤prev│next├-─┘ //這里的數(shù)據(jù)結(jié)構(gòu)就省略畫了
│ └──┴──┘<─┘├──┴──┤ <-┐
│ └─────┘ │
└───────────────────┘
ori_first
┌────────────────────────────┐
│ ┌─────┐ ┌─────┐ │
└->┌──┬──┐┌─>├──┬──┤┌─>├──┬──┤ │
┌─┤prev│next├┘ ┌┤prev│next├┘ ┌┤prev│next├─┘
│ └──┴──┘<─┘├──┴──┤<─┘├──┴──┤<-┐
│ └─────┘ └─────┘ │
└────────────────────────────┘
new ori_first
這個(gè)是添加在head->prev，由于是環(huán)狀的，那么就是添在了最后一個(gè)
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;
}
這個(gè)是用了輔助方法__list_del并且把entry的前后都設(shè)為NULL，是為了安全起見
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = (void *) 0;
entry->prev = (void *) 0;
}
個(gè)人覺得list_del_init, list_move, list_move_tail, list_splice沒啥太大作用…
…不過后面兩個(gè)非常重要：
#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
}
======================================================================
那么這兩個(gè)有什么差別呢？我們可以來看這個(gè)例子：
list_for_each(pos, &test_list) {
list_del(pos);
}
首先，我們得到pos=test_list.next，然后刪除，此時(shí)pos->next=0，如果按照list_fo
r_each的話下一個(gè)循環(huán)的pos就是NULL，再訪問下去就出錯(cuò)了！同樣的，修改位置也是。所
以在需要修改隊(duì)列結(jié)構(gòu)的時(shí)候，一定要使用list_for_each_safe。如果只修改對應(yīng)的數(shù)據(jù)結(jié)
構(gòu)其他字段，可以用list_for_each，因?yàn)檫@個(gè)效率比較高。
有了這些方法基本上就可以使用了。我們可以來看一個(gè)物理內(nèi)存管理的例子：
#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))
//獲取這個(gè)page數(shù)據(jù)結(jié)構(gòu)對應(yīng)的起始地址
#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是用作換出的，最近使用在隊(duì)首，換出隊(duì)尾頁
//如果編譯器不肯讓我們這樣定義的話用lmm_alloc或者out_alloc也可以。
page_t all_pages[PAGE_COUNT];
void init()
{
int i;
INIT_LIST_HEAD(&free_list);
INIT_LIST_HEAD(&lru_list); //初始化兩個(gè)鏈表
for (i = 0; i < PAGE_COUNT; i++) {
all_pages[i] = 0;
list_add_tail(&all_pages[i].mem_list, &free_list); //加入free_list
}
}
//此處返回值作為錯(cuò)誤信息，addr作為所需返回的物理內(nèi)存起始地址
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); //最近使用，放到隊(duì)首
*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隊(duì)列首
}
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隊(duì)列首，下次取時(shí)用
}
物理頁面管理基本上就類似于此。我們接下來來看一個(gè)稍微復(fù)雜些的例子，就是進(jìn)程父
子關(guān)系的例子，去年又同學(xué)跟我反映這是一個(gè)交錯(cuò)鏈接或者說是嵌套鏈接，其實(shí)不然。我們
拆分開來看：
┌─────────-┐
│┌-────────┼───┐
│ ↘ A->children │ │
┌───-┼─>┌──┬──┐ │ │
│ └-─┤prev│next├┐│ │
│ └──┴──┘││ │
│┌────────────┘│ │
││ ┌-───┘ │
││ ┌─────┐ ↘┌─────┐│
│└>├──┬──┤┌─>├──┬──┤│
└-─┤prev│next├┘ ┌┤prev│next├┘
├──┴──┤<─┘├──┴──┤
└─────┘ └─────┘
B C
由圖可知，A有BC兩個(gè)子進(jìn)程，分別連接到A進(jìn)程的children上。此時(shí)，處理A的childre
n又有兩種方法，第一種是增加指針，第二種是作為A進(jìn)程的一部分。利用上面的思考方法，
我們可以知道，如果按照第一種做法，那么勢必會(huì)引起更多的內(nèi)存碎片，不方便。于是我們
把children作為pcb的一個(gè)field。那么B和C里面的prev/next該叫什么呢？因?yàn)锽和C也是pc
b的數(shù)據(jù)結(jié)構(gòu)，已經(jīng)不可能再叫children了（而且他們也應(yīng)該有children節(jié)點(diǎn)，因?yàn)樗麄円?br />
可能有子進(jìn)程）。那么我們就叫它為sibling吧。因?yàn)樵谶@個(gè)鏈表里，除了A是父進(jìn)程，其余
的都是兄弟進(jìn)程。
所以pcb的父子關(guān)系可以這樣寫：
#define TASK_STATE_RUNNING 0
#define TASK_STATE_ZOMBIE 1
//調(diào)用了wait指令，等待子進(jìn)程結(jié)束
#define TASK_STATE_WAIT_CHILD 2
typedef struct pcb_struct{
struct pcb_struct *parent; 父進(jìn)程
unsigned long state;
list_t children;
list_t sibling;
list_t all_tasks;
} pcb_t;
//init是一個(gè)非常特殊的進(jìn)程，一般我們的kernel一起來，就只負(fù)責(zé)兩個(gè)進(jìn)程：init和idle
//init的作用是先fork，子進(jìn)程運(yùn)行shell，它自身while(1) {wait(...);}就是負(fù)責(zé)回收
//孤兒進(jìn)程。
//并且在此，我們可以把所有的進(jìn)程都連接在init的all_tasks上面，這樣又可以節(jié)省一個(gè)
//相當(dāng)于前例test_list的全局變量。找所有進(jìn)程只須遍歷init->all_tasks即可。
//所以在生成init的時(shí)候應(yīng)該是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) //將所有子進(jìn)程交給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放到進(jìn)程列表的尾端
}
}
//然后切換到父進(jìn)程運(yùn)行
}
如果看懂了以上的所有例子，那么鏈表結(jié)構(gòu)應(yīng)該就差不多了。由于篇幅關(guān)系，PCB的構(gòu)
建就單列開來吧。這里專門講LIST好了。:)
如果有代碼覺得看的郁悶的，拿張紙畫畫對應(yīng)的內(nèi)存結(jié)構(gòu)應(yīng)該就會(huì)好些了
--
※ 修改:·CJC 于 Oct 11 03:57:46 修改本文·[FROM: 穿梭而來]
※ 來源:·復(fù)旦燕曦BBS yanxibbs.cn·[FROM: 穿梭而來]