- 論壇徽章:
- 0
|
Linux 2.4 內(nèi)核說明文檔（進(jìn)程與中斷管理篇）
2.4. Linux執(zhí)行鏈表
在遍歷等待隊(duì)列之前，首先執(zhí)行Linux標(biāo)準(zhǔn)的雙向執(zhí)行鏈表。等待隊(duì)列用起來繁雜，行話稱之為“l(fā)ist.h 實(shí)現(xiàn)”，因?yàn)樗钕嚓P(guān)的文件是include/linux/list.h。
基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)是list_head結(jié)構(gòu)：
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \
(ptr).>;next = (ptr); (ptr).>;prev = (ptr); \
} while (0)
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr).(unsigned long)(&((type *)0).>;member)))
#define list_for_each(pos, head) \
for (pos = (head).>;next; pos != (head); pos = pos.>;next)
前三個(gè)宏用來初始化一個(gè)next和prev指針皆指向自身的空鏈表，宏可以用到的地方明顯受限于c語法約束。例如，LIST_HEAD_INIT()用來初始化結(jié)構(gòu)元素，第二個(gè)宏用來初始化靜態(tài)變量，第三個(gè)用于函數(shù)內(nèi)部。
list_entry()宏提供了對單獨(dú)鏈表元素的操作，例如（fs/file_table.c:fs_may_remount_ro()函數(shù)）：
struct super_block {
...
struct list_head s_files;
...
} *sb = &some_super_block;
struct file {
...
struct list_head f_list;
...
} *file;
struct list_head *p;
for (p = sb.>;s_files.next; p != &sb.>;s_files; p = p.>;next) {
struct file *file = list_entry(p, struct file, f_list);
// do something to 'file'
}
一個(gè)使用list_for_each()宏的最好例子就是任務(wù)調(diào)度函數(shù)中遍歷運(yùn)行隊(duì)列以查找高優(yōu)先級的進(jìn)程部分。
static LIST_HEAD(runqueue_head);
struct list_head *tmp;
struct task_struct *p;
list_for_each(tmp, &runqueue_head) {
p = list_entry(tmp, struct task_struct, run_list);
if (can_schedule(p)) {
int weight = goodness(p, this_cpu, prev.>;active_mm);
if (weight >; c)
c = weight, next = p;
}
}
p.>;run_list 被定義成task_struct結(jié)構(gòu)內(nèi)的list_head結(jié)構(gòu)成員run_list，serves為指向鏈表的指針。向鏈表里面刪除或者添加一個(gè)元素由list_del()/list_add()/list_add_tail()三個(gè)宏完成。下面的例子向運(yùn)行隊(duì)列添加并刪除一個(gè)任務(wù)。
static inline void del_from_runqueue(struct task_struct * p)
{
nr_running..;
list_del(&p.>;run_list);
p.>;run_list.next = NULL;
}
static inline void add_to_runqueue(struct task_struct * p)
{
list_add(&p.>;run_list, &runqueue_head);
nr_running++;
}
static inline void move_last_runqueue(struct task_struct * p)
{
list_del(&p.>;run_list);
list_add_tail(&p.>;run_list, &runqueue_head);
}
static inline void move_first_runqueue(struct task_struct * p)
{
list_del(&p.>;run_list);
list_add(&p.>;run_list, &runqueue_head);
} |
|
免費(fèi)注冊
發(fā)表于 2005-07-04 10:33
^ (x)) & (PIDHASH_SZ . 1)) 
