電子發燒友App
0.等待隊列
在Linux內核中等待隊列有很多用途，可用于中斷處理、進程同步及定時。我們在這里只說，進程經常必須等待某些事件的發生。等待隊列實現了在事件上的條件等待:?希望等待特定事件的進程把自己放進合適的等待隊列，并放棄控制全。因此，等待隊列表示一組睡眠的進程，當某一條件為真時，由內核喚醒它們。
等待隊列由循環鏈表實現，由等待隊列頭（wait_queue_head_t）和等待隊列項（wait_queue）組成，其元素（等待隊列項）包含指向進程描述符的指針。每個等待隊列都有一個等待隊列頭(wait?queue?head),等待隊列頭是一個類型為wait_queue_head_t的數據結構
定義等待隊列頭（相關內容可以在linux/include/wait.h中找到）
等待隊列頭結構體的定義：
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宏來完成，這是靜態定義的方法。該宏會定義一個wait_queue_head，并且初始化結構中的鎖以及等待隊列。
Linux中等待隊列的實現思想如下圖所示，當一個任務需要在某個wait_queue_head上睡眠時，將自己的進程控制塊信息封裝到wait_queue中，然后掛載到wait_queue的鏈表中，執行調度睡眠。當某些事件發生后，另一個任務（進程）會喚醒wait_queue_head上的某個或者所有任務，喚醒工作也就是將等待隊列中的任務設置為可調度的狀態，并且從隊列中刪除。
（2）等待隊列中存放的是在執行設備操作時不能獲得資源而掛起的進程
定義等待對列：
struct?wait_queue?{
unsigned?int?flags;??//prepare_to_wait()里有對flags的操作，查看以得出其含義
#define?WQ_FLAG_EXCLUSIVE????????0x01?//一個常數,在prepare_to_wait()用于修改flags的值
void?*?private??????????//通常指向當前任務控制塊
wait_queue_func_t?func;????//喚醒阻塞任務的函數?，決定了喚醒的方式
struct?list_head?task_list;????//?阻塞任務鏈表
};
typedef?struct?__wait_queue??????????wait_queue_t;
poll實現分析
1.select/poll缺點
select/poll的缺點在于：
?????1.每次調用時要重復地從用戶態讀入參數。
?????2.每次調用時要重復地掃描文件描述符。
?????3.每次在調用開始時，要把當前進程放入各個文件描述符的等待隊列。在調用結束后，又把進程從各個等待隊列中刪除。
2.?內核實現
2.1?主要數據結構：
(1)?struct?poll_table_entry?{
struct?file??filp;
wait_queue_t?wait;//內部有一個指針指向一個進程
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;//一個函數指針，通常指向__pollwait或null
struct?poll_table_page?*?table;
int?error;
};
(4)?struct?poll_list?{
struct?poll_list?*next;//按內存頁連接，因為kmalloc有申請數據限制
int?len;//用戶空間傳入fd的數量
struct?pollfd?entries[0];//存放用戶空間存入的數據
};
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系統調用函數關系總圖
int?poll(struct?pollfd?*fds,?nfds_t?nfds,?int?timeout);
3.?內核2.6.9?poll實現代碼分析
[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;
}
/*這一大堆代碼就是建立一個鏈表，每個鏈表的節點是一個page大小（通常是4k），這鏈表節點由一個指向struct?poll_list的指針掌控每個poll_list的entrys成員指向一個struct?pollfd。上面的循環就是把用戶態的struct?pollfd拷進這些entries里。通常用戶程序的poll調用就監控幾個fd，所以上面這個鏈表通常也就只需要一個節點，即操作系統的一頁。但是，當用戶傳入的fd很多時，由于poll系統調用每次都要把所有struct?pollfd拷進內核，所以參數傳遞和頁分配此時就成了poll系統調用的性能瓶頸。*/
fdcount?=?do_poll(nfds,?head,?&table,?timeout);
}
????其中poll_initwait較為關鍵，從字面上看，應該是初始化變量table，注意此處table在整個執行poll的過程中是很關鍵的變量。而struct?poll_table其實就只包含了一個函數指針。
現在我們來看看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;?/*設置回調函數*/
……
}
很明顯，poll_initwait的主要動作就是把table變量的成員poll_table對應的回調函數置為__pollwait。這個__pollwait不僅是poll系統調用需要，select系統調用也一樣是用這個__pollwait，說白了，這是個操作系統的異步操作的“御用”回調函數。當然了，epoll沒有用這個，它另外新增了一個回調函數，以達到其高效運轉的目的，這是后話，暫且不表。
?????最后一句do_poll，我們跟進去：
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掛起，別的進程跑，timeout到了
以后再回來運行current*/
????}
????__set_current_state(TASK_RUNNING);
????return?count;
???}
注意set_current_state和signal_pending，它們兩句保障了當用戶程序在調用poll后掛起時，發信號可以讓程序迅速推出poll調用，而通常的系統調用是不會被信號打斷的。縱覽do_poll函數，主要是在循環內等待，直到count大于0才跳出循環，而count主要是靠do_pollfd函數處理。注意標紅的while循環，當用戶傳入的fd很多時（比如1000個），對do_pollfd就會調用很多次，poll效率瓶頸的另一原因就在這里。
do_pollfd就是針對每個傳進來的fd，調用它們各自對應的poll函數，簡化一下調用過程，如下：
[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對應的是某個socket，do_pollfd調用的就是網絡設備驅動實現的poll；如果fd對應的是某個ext3文件系統上的一個打開文件，那do_pollfd調用的就是ext3文件系統驅動實現的poll。一句話，這個file->f_op->poll是設備驅動程序實現的，那設備驅動程序的poll實現通常又是什么樣子呢？其實，設備驅動程序的標準實現是：調用poll_wait，即以設備自己的等待隊列為參數（通常設備都有自己的等待隊列，不然一個不支持異步操作的設備會讓人很郁悶）調用struct?poll_table的回調函數。
作為驅動程序的代表，我們看看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的核心實現就是poll_wait，而poll_wait就是調用struct?poll_table對應的回調函數，那poll系統調用對應的回調函數就是__poll_wait，所以這里幾乎就可以把tcp_poll理解為一個語句：
__poll_wait(file,?sk->sk_sleep,?wait);
由此也可以看出，每個socket自己都帶有一個等待隊列sk_sleep，所以上面我們所說的“設備的等待隊列”,其實不止一個。
這時候我們再看看__poll_wait的實現:
[fs/select.c-->__poll_wait()]
?void?__pollwait(struct?file?*filp,?wait_queue_head_t?*wait_address,?poll_table?*_p)
?{
……
}
__poll_wait的作用就是創建了上圖所示的數據結構（一次__poll_wait即一次設備poll調用只創建一個poll_table_entry），并通過struct?poll_table_entry的wait成員，把current掛在了設備的等待隊列上，此處的等待隊列是wait_address，對應tcp_poll里的sk->sk_sleep。
現在我們可以回顧一下poll系統調用的原理了：先注冊回調函數__poll_wait，再初始化table變量（類型為struct?poll_wqueues)，接著拷貝用戶傳入的struct?pollfd（其實主要是fd）(瓶頸1)，然后輪流調用所有fd對應的poll（把current掛到各個fd對應的設備等待隊列上）(瓶頸2)。在設備收到一條消息（網絡設備）或填寫完文件數據（磁盤設備）后，會喚醒設備等待隊列上的進程，這時current便被喚醒了。current醒來后離開sys_poll的操作相對簡單，這里就不逐行分析了。
?
工商網監
評論