0.等待隊列

在Linux內(nèi)核中等待隊列有很多用途，可用于中斷處理、進(jìn)程同步及定時。我們在這里只說，進(jìn)程經(jīng)常必須等待某些事件的發(fā)生。等待隊列實現(xiàn)了在事件上的條件等待:?希望等待特定事件的進(jìn)程把自己放進(jìn)合適的等待隊列，并放棄控制全。因此，等待隊列表示一組睡眠的進(jìn)程，當(dāng)某一條件為真時，由內(nèi)核喚醒它們。

等待隊列由循環(huán)鏈表實現(xiàn)，由等待隊列頭（wait_queue_head_t）和等待隊列項（wait_queue）組成，其元素（等待隊列項）包含指向進(jìn)程描述符的指針。每個等待隊列都有一個等待隊列頭(wait?queue?head),等待隊列頭是一個類型為wait_queue_head_t的數(shù)據(jù)結(jié)構(gòu)

定義等待隊列頭（相關(guān)內(nèi)容可以在linux/include/wait.h中找到）

等待隊列頭結(jié)構(gòu)體的定義：

struct?wait_queue_head?{

spinlock_t??lock;??????????//自旋鎖變量，用于在對等待隊列頭??????????

struct?list_head?task_list;??//?指向等待隊列的list_head

};?

typedef?struct?__wait_queue_head??wait_queue_head_t;

使用等待隊列時首先需要定義一個wait_queue_head，這可以通過DECLARE_WAIT_QUEUE_HEAD宏來完成，這是靜態(tài)定義的方法。該宏會定義一個wait_queue_head，并且初始化結(jié)構(gòu)中的鎖以及等待隊列。

Linux中等待隊列的實現(xiàn)思想如下圖所示，當(dāng)一個任務(wù)需要在某個wait_queue_head上睡眠時，將自己的進(jìn)程控制塊信息封裝到wait_queue中，然后掛載到wait_queue的鏈表中，執(zhí)行調(diào)度睡眠。當(dāng)某些事件發(fā)生后，另一個任務(wù)（進(jìn)程）會喚醒wait_queue_head上的某個或者所有任務(wù)，喚醒工作也就是將等待隊列中的任務(wù)設(shè)置為可調(diào)度的狀態(tài)，并且從隊列中刪除。

（2）等待隊列中存放的是在執(zhí)行設(shè)備操作時不能獲得資源而掛起的進(jìn)程

定義等待對列：

struct?wait_queue?{

unsigned?int?flags;??//prepare_to_wait()里有對flags的操作，查看以得出其含義

#define?WQ_FLAG_EXCLUSIVE????????0x01?//一個常數(shù),在prepare_to_wait()用于修改flags的值

void?*?private??????????//通常指向當(dāng)前任務(wù)控制塊

wait_queue_func_t?func;????//喚醒阻塞任務(wù)的函數(shù)?，決定了喚醒的方式

struct?list_head?task_list;????//?阻塞任務(wù)鏈表

};

typedef?struct?__wait_queue??????????wait_queue_t;

poll實現(xiàn)分析

1.select/poll缺點

select/poll的缺點在于：
?????1.每次調(diào)用時要重復(fù)地從用戶態(tài)讀入參數(shù)。
?????2.每次調(diào)用時要重復(fù)地掃描文件描述符。
?????3.每次在調(diào)用開始時，要把當(dāng)前進(jìn)程放入各個文件描述符的等待隊列。在調(diào)用結(jié)束后，又把進(jìn)程從各個等待隊列中刪除。

2.?內(nèi)核實現(xiàn)

2.1?主要數(shù)據(jù)結(jié)構(gòu)：

(1)?struct?poll_table_entry?{

struct?file??filp;

wait_queue_t?wait;//內(nèi)部有一個指針指向一個進(jìn)程

wait_queue_head_t???wait_address;//等待隊列頭部（等待隊列有多個wait_queue_t組成，通過雙鏈表連接）

};

(2)?struct?poll_table_page?{

struct?poll_table_page???next;

struct?poll_table_entry???entry;

struct?poll_table_entry?entries[0];

};

(3)?struct?poll_wqueues?{

poll_table?pt;//一個函數(shù)指針，通常指向__pollwait或null

struct?poll_table_page?*?table;

int?error;

};

(4)?struct?poll_list?{

struct?poll_list?*next;//按內(nèi)存頁連接，因為kmalloc有申請數(shù)據(jù)限制

int?len;//用戶空間傳入fd的數(shù)量

struct?pollfd?entries[0];//存放用戶空間存入的數(shù)據(jù)

};

typedef?void?(*poll_queue_proc)(struct?file?*,?wait_queue_head_t?*,?struct?poll_table_struct?*);
?typedef?struct?poll_table??struct?{
?????poll_queue_proc?qproc;
?}?poll_table;

2.2?poll系統(tǒng)調(diào)用函數(shù)關(guān)系總圖

int?poll(struct?pollfd?*fds,?nfds_t?nfds,?int?timeout);

3.?內(nèi)核2.6.9?poll實現(xiàn)代碼分析

[fs/select.c?-->sys_poll]

asmlinkage?long?sys_poll(struct?pollfd?__user?*?ufds,?unsigned?int?nfds,?long?timeout)
?{
?struct?poll_wqueues?table;
?struct?poll_list?*head;
?struct?poll_list?*walk;
?……

poll_initwait(&table);

……

while(i!=0)?{
struct?poll_list?*pp;
pp?=?kmalloc(sizeof(struct?poll_list)+?sizeof(struct?pollfd)?

*(i>POLLFD_PER_PAGE?POLLFD_PER_PAGE:i),?GFP_KERNEL));
if?(head?==?NULL)
head?=?pp;
else
walk->next?=?pp;
walk?=?pp;
if?(copy_from_user(pp->entries,?ufds?+?nfds-i,
sizeof(struct?pollfd)*pp->len))?{
err?=?-EFAULT;
goto?out_fds;
}

i?-=?pp->len;

}

/*這一大堆代碼就是建立一個鏈表，每個鏈表的節(jié)點是一個page大?。ㄍǔＪ?k），這鏈表節(jié)點由一個指向struct?poll_list的指針掌控每個poll_list的entrys成員指向一個struct?pollfd。上面的循環(huán)就是把用戶態(tài)的struct?pollfd拷進(jìn)這些entries里。通常用戶程序的poll調(diào)用就監(jiān)控幾個fd，所以上面這個鏈表通常也就只需要一個節(jié)點，即操作系統(tǒng)的一頁。但是，當(dāng)用戶傳入的fd很多時，由于poll系統(tǒng)調(diào)用每次都要把所有struct?pollfd拷進(jìn)內(nèi)核，所以參數(shù)傳遞和頁分配此時就成了poll系統(tǒng)調(diào)用的性能瓶頸。*/

fdcount?=?do_poll(nfds,?head,?&table,?timeout);
}
????其中poll_initwait較為關(guān)鍵，從字面上看，應(yīng)該是初始化變量table，注意此處table在整個執(zhí)行poll的過程中是很關(guān)鍵的變量。而struct?poll_table其實就只包含了一個函數(shù)指針。

現(xiàn)在我們來看看poll_initwait到底在做些什么
?void?__pollwait(struct?file?*filp,?wait_queue_head_t?*wait_address,?poll_table?*p);
?void?poll_initwait(struct?poll_wqueues?*pwq)
?{

&(pwq->pt)->qproc?=?__pollwait;?/*設(shè)置回調(diào)函數(shù)*/

……

}
很明顯，poll_initwait的主要動作就是把table變量的成員poll_table對應(yīng)的回調(diào)函數(shù)置為__pollwait。這個__pollwait不僅是poll系統(tǒng)調(diào)用需要，select系統(tǒng)調(diào)用也一樣是用這個__pollwait，說白了，這是個操作系統(tǒng)的異步操作的“御用”回調(diào)函數(shù)。當(dāng)然了，epoll沒有用這個，它另外新增了一個回調(diào)函數(shù)，以達(dá)到其高效運(yùn)轉(zhuǎn)的目的，這是后話，暫且不表。
?????最后一句do_poll，我們跟進(jìn)去：

static?int?do_poll(unsigned?int?nfds,?struct?poll_list?*list,struct?poll_wqueues?*wait,

long?timeout)
{
???int?count?=?0;
???poll_table*?pt?=?&wait->pt;
???for?(;;)?{
???struct?poll_list?*walk;
???set_current_state(TASK_INTERRUPTIBLE);
???walk?=?list;
???while(walk?!=?NULL)?{
???do_pollfd(?walk->len,?walk->entries,?&pt,?&count);
???walk?=?walk->next;
????}
???pt?=?NULL;
???if?(count?||?!timeout?||?signal_pending(current))
????break;
????count?=?wait->error;
????if?(count)
????break;
????timeout?=?schedule_timeout(timeout);?/*?讓current掛起，別的進(jìn)程跑，timeout到了
以后再回來運(yùn)行current*/
????}
????__set_current_state(TASK_RUNNING);
????return?count;
???}

注意set_current_state和signal_pending，它們兩句保障了當(dāng)用戶程序在調(diào)用poll后掛起時，發(fā)信號可以讓程序迅速推出poll調(diào)用，而通常的系統(tǒng)調(diào)用是不會被信號打斷的?？v覽do_poll函數(shù)，主要是在循環(huán)內(nèi)等待，直到count大于0才跳出循環(huán)，而count主要是靠do_pollfd函數(shù)處理。注意標(biāo)紅的while循環(huán)，當(dāng)用戶傳入的fd很多時（比如1000個），對do_pollfd就會調(diào)用很多次，poll效率瓶頸的另一原因就在這里。

do_pollfd就是針對每個傳進(jìn)來的fd，調(diào)用它們各自對應(yīng)的poll函數(shù)，簡化一下調(diào)用過程，如下：

[fs/select.c-->sys_poll()-->do_poll()]
static?void?do_pollfd(unsigned?int?num,?struct?pollfd?*?fdpage,?poll_table?**?pwait,?int?*count)
?{

……

struct?file*?file?=?fget(fd);
file->f_op->poll（file,?&(table->pt));

……
?}

如果fd對應(yīng)的是某個socket，do_pollfd調(diào)用的就是網(wǎng)絡(luò)設(shè)備驅(qū)動實現(xiàn)的poll；如果fd對應(yīng)的是某個ext3文件系統(tǒng)上的一個打開文件，那do_pollfd調(diào)用的就是ext3文件系統(tǒng)驅(qū)動實現(xiàn)的poll。一句話，這個file->f_op->poll是設(shè)備驅(qū)動程序?qū)崿F(xiàn)的，那設(shè)備驅(qū)動程序的poll實現(xiàn)通常又是什么樣子呢？其實，設(shè)備驅(qū)動程序的標(biāo)準(zhǔn)實現(xiàn)是：調(diào)用poll_wait，即以設(shè)備自己的等待隊列為參數(shù)（通常設(shè)備都有自己的等待隊列，不然一個不支持異步操作的設(shè)備會讓人很郁悶）調(diào)用struct?poll_table的回調(diào)函數(shù)。
作為驅(qū)動程序的代表，我們看看socket在使用tcp時的代碼：
[net/ipv4/tcp.c-->tcp_poll]
unsigned?int?tcp_poll(struct?file?*file,?struct?socket?*sock,?poll_table?*wait)
?{

……

poll_wait(file,?sk->sk_sleep,?wait);
tcp_poll的核心實現(xiàn)就是poll_wait，而poll_wait就是調(diào)用struct?poll_table對應(yīng)的回調(diào)函數(shù)，那poll系統(tǒng)調(diào)用對應(yīng)的回調(diào)函數(shù)就是__poll_wait，所以這里幾乎就可以把tcp_poll理解為一個語句：
__poll_wait(file,?sk->sk_sleep,?wait);
由此也可以看出，每個socket自己都帶有一個等待隊列sk_sleep，所以上面我們所說的“設(shè)備的等待隊列”,其實不止一個。
這時候我們再看看__poll_wait的實現(xiàn):
[fs/select.c-->__poll_wait()]
?void?__pollwait(struct?file?*filp,?wait_queue_head_t?*wait_address,?poll_table?*_p)
?{

……

}

__poll_wait的作用就是創(chuàng)建了上圖所示的數(shù)據(jù)結(jié)構(gòu)（一次__poll_wait即一次設(shè)備poll調(diào)用只創(chuàng)建一個poll_table_entry），并通過struct?poll_table_entry的wait成員，把current掛在了設(shè)備的等待隊列上，此處的等待隊列是wait_address，對應(yīng)tcp_poll里的sk->sk_sleep。
現(xiàn)在我們可以回顧一下poll系統(tǒng)調(diào)用的原理了：先注冊回調(diào)函數(shù)__poll_wait，再初始化table變量（類型為struct?poll_wqueues)，接著拷貝用戶傳入的struct?pollfd（其實主要是fd）(瓶頸1)，然后輪流調(diào)用所有fd對應(yīng)的poll（把current掛到各個fd對應(yīng)的設(shè)備等待隊列上）(瓶頸2)。在設(shè)備收到一條消息（網(wǎng)絡(luò)設(shè)備）或填寫完文件數(shù)據(jù)（磁盤設(shè)備）后，會喚醒設(shè)備等待隊列上的進(jìn)程，這時current便被喚醒了。current醒來后離開sys_poll的操作相對簡單，這里就不逐行分析了。

?