0.等待隊(duì)列

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

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

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

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

struct?wait_queue_head?{

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

struct?list_head?task_list;??//?指向等待隊(duì)列的list_head

};?

typedef?struct?__wait_queue_head??wait_queue_head_t;

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

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

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

定義等待對(duì)列：

struct?wait_queue?{

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

#define?WQ_FLAG_EXCLUSIVE????????0x01?//一個(gè)常數(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實(shí)現(xiàn)分析

1.select/poll缺點(diǎn)

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

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

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

(1)?struct?poll_table_entry?{

struct?file??filp;

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

wait_queue_head_t???wait_address;//等待隊(duì)列頭部（等待隊(duì)列有多個(gè)wait_queue_t組成，通過(guò)雙鏈表連接）

};

(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;//一個(gè)函數(shù)指針，通常指向__pollwait或null

struct?poll_table_page?*?table;

int?error;

};

(4)?struct?poll_list?{

struct?poll_list?*next;//按內(nèi)存頁(yè)連接，因?yàn)閗malloc有申請(qǐng)數(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實(shí)現(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;

}

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

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

現(xiàn)在我們來(lái)看看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的主要?jiǎng)幼骶褪前裻able變量的成員poll_table對(duì)應(yīng)的回調(diào)函數(shù)置為_(kāi)_pollwait。這個(gè)__pollwait不僅是poll系統(tǒng)調(diào)用需要，select系統(tǒng)調(diào)用也一樣是用這個(gè)__pollwait，說(shuō)白了，這是個(gè)操作系統(tǒng)的異步操作的“御用”回調(diào)函數(shù)。當(dāng)然了，epoll沒(méi)有用這個(gè)，它另外新增了一個(gè)回調(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到了
以后再回來(lái)運(yùn)行current*/
????}
????__set_current_state(TASK_RUNNING);
????return?count;
???}

注意set_current_state和signal_pending，它們兩句保障了當(dāng)用戶程序在調(diào)用poll后掛起時(shí)，發(fā)信號(hào)可以讓程序迅速推出poll調(diào)用，而通常的系統(tǒng)調(diào)用是不會(huì)被信號(hà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很多時(shí)（比如1000個(gè)），對(duì)do_pollfd就會(huì)調(diào)用很多次，poll效率瓶頸的另一原因就在這里。

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

[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對(duì)應(yīng)的是某個(gè)socket，do_pollfd調(diào)用的就是網(wǎng)絡(luò)設(shè)備驅(qū)動(dòng)實(shí)現(xiàn)的poll；如果fd對(duì)應(yīng)的是某個(gè)ext3文件系統(tǒng)上的一個(gè)打開(kāi)文件，那do_pollfd調(diào)用的就是ext3文件系統(tǒng)驅(qū)動(dòng)實(shí)現(xiàn)的poll。一句話，這個(gè)file->f_op->poll是設(shè)備驅(qū)動(dòng)程序?qū)崿F(xiàn)的，那設(shè)備驅(qū)動(dòng)程序的poll實(shí)現(xiàn)通常又是什么樣子呢？其實(shí)，設(shè)備驅(qū)動(dòng)程序的標(biāo)準(zhǔn)實(shí)現(xiàn)是：調(diào)用poll_wait，即以設(shè)備自己的等待隊(duì)列為參數(shù)（通常設(shè)備都有自己的等待隊(duì)列，不然一個(gè)不支持異步操作的設(shè)備會(huì)讓人很郁悶）調(diào)用struct?poll_table的回調(diào)函數(shù)。
作為驅(qū)動(dòng)程序的代表，我們看看socket在使用tcp時(shí)的代碼：
[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的核心實(shí)現(xiàn)就是poll_wait，而poll_wait就是調(diào)用struct?poll_table對(duì)應(yīng)的回調(diào)函數(shù)，那poll系統(tǒng)調(diào)用對(duì)應(yīng)的回調(diào)函數(shù)就是__poll_wait，所以這里幾乎就可以把tcp_poll理解為一個(gè)語(yǔ)句：
__poll_wait(file,?sk->sk_sleep,?wait);
由此也可以看出，每個(gè)socket自己都帶有一個(gè)等待隊(duì)列sk_sleep，所以上面我們所說(shuō)的“設(shè)備的等待隊(duì)列”,其實(shí)不止一個(gè)。
這時(shí)候我們?cè)倏纯確_poll_wait的實(shí)現(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)建一個(gè)poll_table_entry），并通過(guò)struct?poll_table_entry的wait成員，把current掛在了設(shè)備的等待隊(duì)列上，此處的等待隊(duì)列是wait_address，對(duì)應(yīng)tcp_poll里的sk->sk_sleep。
現(xiàn)在我們可以回顧一下poll系統(tǒng)調(diào)用的原理了：先注冊(cè)回調(diào)函數(shù)__poll_wait，再初始化table變量（類型為struct?poll_wqueues)，接著拷貝用戶傳入的struct?pollfd（其實(shí)主要是fd）(瓶頸1)，然后輪流調(diào)用所有fd對(duì)應(yīng)的poll（把current掛到各個(gè)fd對(duì)應(yīng)的設(shè)備等待隊(duì)列上）(瓶頸2)。在設(shè)備收到一條消息（網(wǎng)絡(luò)設(shè)備）或填寫完文件數(shù)據(jù)（磁盤設(shè)備）后，會(huì)喚醒設(shè)備等待隊(duì)列上的進(jìn)程，這時(shí)current便被喚醒了。current醒來(lái)后離開(kāi)sys_poll的操作相對(duì)簡(jiǎn)單，這里就不逐行分析了。

?