首先我們來定義流的概念,一個流可以是文件,socket,pipe等等可以進行I/O操作的內核對象。
不管是文件,還是套接字,還是管道,我們都可以把他們看作流。
之後我們來討論I/O的操作,通過read,我們可以從流中讀入數據;通過write,我們可以往流寫入數據。現在假定一個情形,我們需要從流中讀數據,但是流中還沒有數據,(典型的例子為,客戶端要從socket讀如數據,但是服務器還沒有把數據傳回來),這時候該怎麼辦?
阻塞:阻塞是個什麼概念呢?比如某個時候你在等快遞,但是你不知道快遞什麼時候過來,而且你沒有別的事可以干(或者說接下來的事要等快遞來了才能做);那麼你可以去睡覺了,因為你知道快遞把貨送來時一定會給你打個電話(假定一定能叫醒你)。
非阻塞忙輪詢:接著上面等快遞的例子,如果用忙輪詢的方法,那麼你需要知道快遞員的手機號,然後每分鐘給他掛個電話:“你到了沒?”
很明顯一般人不會用第二種做法,不僅顯很無腦,浪費話費不說,還占用了快遞員大量的時間。
大部分程序也不會用第二種做法,因為第一種方法經濟而簡單,經濟是指消耗很少的CPU時間,如果線程睡眠了,就掉出了系統的調度隊列,暫時不會去瓜分CPU寶貴的時間片了。
為了了解阻塞是如何進行的,我們來討論緩沖區,以及內核緩沖區,最終把I/O事件解釋清楚。緩沖區的引入是為了減少頻繁I/O操作而引起頻繁的系統調用(你知道它很慢的),當你操作一個流時,更多的是以緩沖區為單位進行操作,這是相對於用戶空間而言。對於內核來說,也需要緩沖區。
假設有一個管道,進程A為管道的寫入方,B為管道的讀出方。
假設一開始內核緩沖區是空的,B作為讀出方,被阻塞著。然後首先A往管道寫入,這時候內核緩沖區由空的狀態變到非空狀態,內核就會產生一個事件告訴B該醒來了,這個事件姑且稱之為“緩沖區非空”。
但是“緩沖區非空”事件通知B後,B卻還沒有讀出數據;且內核許諾了不能把寫入管道中的數據丟掉這個時候,A寫入的數據會滯留在內核緩沖區中,如果內核也緩沖區滿了,B仍未開始讀數據,最終內核緩沖區會被填滿,這個時候會產生一個I/O事件,告訴進程A,你該等等(阻塞)了,我們把這個事件定義為“緩沖區滿”。
假設後來B終於開始讀數據了,於是內核的緩沖區空了出來,這時候內核會告訴A,內核緩沖區有空位了,你可以從長眠中醒來了,繼續寫數據了,我們把這個事件叫做“緩沖區非滿”
也許事件Y1已經通知了A,但是A也沒有數據寫入了,而B繼續讀出數據,知道內核緩沖區空了。這個時候內核就告訴B,你需要阻塞了!,我們把這個時間定為“緩沖區空”。
這四個情形涵蓋了四個I/O事件,緩沖區滿,緩沖區空,緩沖區非空,緩沖區非滿(注都是說的內核緩沖區,且這四個術語都是我生造的,僅為解釋其原理而造)。這四個I/O事件是進行阻塞同步的根本。(如果不能理解“同步”是什麼概念,請學習操作系統的鎖,信號量,條件變量等任務同步方面的相關知識)。
然後我們來說說阻塞I/O的缺點。但是阻塞I/O模式下,一個線程只能處理一個流的I/O事件。如果想要同時處理多個流,要麼多進程(fork),要麼多線程(pthread_create),很不幸這兩種方法效率都不高。
於是再來考慮非阻塞忙輪詢的I/O方式,我們發現我們可以同時處理多個流了(把一個流從阻塞模式切換到非阻塞模式再此不予討論):
while true {
for i in stream[]; {
if i has data
read until unavailable
}
}
我們只要不停的把所有流從頭到尾問一遍,又從頭開始。這樣就可以處理多個流了,但這樣的做法顯然不好,因為如果所有的流都沒有數據,那麼只會白白浪費CPU。這裡要補充一點,阻塞模式下,內核對於I/O事件的處理是阻塞或者喚醒,而非阻塞模式下則把I/O事件交給其他對象(後文介紹的select以及epoll)處理甚至直接忽略。
為了避免CPU空轉,可以引進了一個代理(一開始有一位叫做select的代理,後來又有一位叫做poll的代理,不過兩者的本質是一樣的)。這個代理比較厲害,可以同時觀察許多流的I/O事件,在空閒的時候,會把當前線程阻塞掉,當有一個或多個流有I/O事件時,就從阻塞態中醒來,於是我們的程序就會輪詢一遍所有的流(於是我們可以把“忙”字去掉了)。代碼長這樣:
while true {
select(streams[])
for i in streams[] {
if i has data
read until unavailable
}
}
於是,如果沒有I/O事件產生,我們的程序就會阻塞在select處。但是依然有個問題,我們從select那裡僅僅知道了,有I/O事件發生了,但卻並不知道是那幾個流(可能有一個,多個,甚至全部),我們只能無差別輪詢所有流,找出能讀出數據,或者寫入數據的流,對他們進行操作。
但是使用select,我們有O(n)的無差別輪詢復雜度,同時處理的流越多,沒一次無差別輪詢時間就越長。再次
說了這麼多,終於能好好解釋epoll了
epoll可以理解為event poll,不同於忙輪詢和無差別輪詢,epoll之會把哪個流發生了怎樣的I/O事件通知我們。此時我們對這些流的操作都是有意義的。(復雜度降低到了O(1))
在討論epoll的實現細節之前,先把epoll的相關操作列出:
epoll_create 創建一個epoll對象,一般epollfd = epoll_create()
epoll_ctl (epoll_add/epoll_del的合體),往epoll對象中增加/刪除某一個流的某一個事件
比如
epoll_ctl(epollfd, EPOLL_CTL_ADD, socket, EPOLLIN);//注冊緩沖區非空事件,即有數據流入
epoll_ctl(epollfd, EPOLL_CTL_DEL, socket, EPOLLOUT);//注冊緩沖區非滿事件,即流可以被寫入
epoll_wait(epollfd,...)等待直到注冊的事件發生
(注:當對一個非阻塞流的讀寫發生緩沖區滿或緩沖區空,write/read會返回-1,並設置errno=EAGAIN。而epoll只關心緩沖區非滿和緩沖區非空事件)。
一個epoll模式的代碼大概的樣子是:
while true {
active_stream[] = epoll_wait(epollfd)
for i in active_stream[] {
read or write till
}
}
因為需要了解底層設備訪問的原理,所以慣用高層應用語言的我,需要了解一下Linux的設備訪問機制,尤其是處理一組非阻塞IO的原理方法,標准的術語好像是叫多路復用。以下文章部分句子有引用之處,恕沒有一一指出出處。
對於接觸過Linux內核或設備驅動開發的讀者,一定清楚poll和select系統調用,以及從2.5版本引入的epoll機制(epoll機制包含三個系統調用)。網上關於它們的文章,有說用法的,甚為詳細,更有分析源代碼的,又比較深入,且枝節頗多。經過幾篇文章的閱讀,我把覺得比較核心的東西寫下來吧。我的用意是盡可能以簡單的概念,比對他們三者的異同。
幾經查找我才確定下來,poll和select應該被歸類為這樣的系統調用,它們可以阻塞地同時探測一組支持非阻塞的IO設備,是否有事件發生(如可讀,可寫,有高優先級的錯誤輸出,出現錯誤等等),直至某一個設備觸發了事件或者超過了指定的等待時間——也就是它們的職責不是做IO,而是幫助調用者尋找當前就緒的設備。同類型的產品是Windows的IOCP,它也是處理多路復用,只是把IO和探測封裝在了一起了。
准備的知識有兩點:1、fd;2、op->poll。
在Linux裡面,設備都被抽象為文件,一系列的設備文件就有自己獨立的虛擬文件系統,所以,設備在系統調用參數中的表示就是file description。fd其實就是一個整數(特別地,標准輸入,輸出,錯誤輸出分別對應的fd是0,1,2)。與內核打交道的時候,傳遞整數的fd可以在自己的文件系統中作進一步的檢查是否合法,如果只是返回指針就不能這樣操作了,畢竟指針是無差別無意義的。
通過fd訪問file,通過file可以訪問其fileOperator,這裡面我們要關心的一個fileOp就是poll。因為系統調用poll和select,就是依靠這個文件操作poll實現的。poll文件操作有兩個參數,一個是文件本身,一個可以看做是當設備尚未就緒時調用的回調函數,這個函數是把設備自己特有的等待隊列傳給內核,讓內核把當前的進程掛載到其中(因為當設備就緒時,設備就應該去喚醒在自己特有等待隊列中的所有節點,這樣當前進程就獲取了完成的信號了)。poll文件操作返回的必須是一組標准的掩碼,其中的各個位指示當前的不同的就緒狀態(全0為沒有任何事件觸發)。
再談談早期多路復用的版本poll和select。
本質而言,poll和select的共同點就是,對全部指定設備做一次poll,當然這往往都是還沒有就緒的,那就會通過回調函數把當前進程注冊到設備的等待隊列,如果所有設備返回的掩碼都沒有顯示任何的事件觸發,就去掉回調函數的函數指針,進入有限時的睡眠狀態,再恢復和不斷做poll,再作有限時的睡眠,直到其中一個設備有事件觸發為止。只要有事件觸發,系統調用返回,回到用戶態,用戶就可以對相關的fd作進一步的讀或者寫操作了。當然,這個時候還不是所有的設備都就緒的喔,那就得不斷地poll或者select了,而做一次這樣的系統調用都得輪詢所有的設備,次數是設備數*(睡眠次數-1),也就是時間復雜度是O(n),還得做幾次O(n)呢。可見,對於現在普遍的服務器程序,需要同時並發監聽數千個連接,並且連接需要重復使用的情況,poll和select就存在這樣的性能瓶頸。另外,數千個設備fd在每次調用時,都需要將其從用戶空間復制到內核空間,這裡的開銷不可忽略。
poll和select放在一起,是因為其機制一致,而參數和數據結構就略有不同。select一次性傳入三組作用於不同信道的設備fd,分別是輸入,輸出和錯誤異常。各組的fd期待各組所特有的,由代碼指定的一組事件,如輸入信道期待輸入就緒,輸入掛起和錯誤等事件。 然後,select就挑選調用者關心的fd做poll文件操作,檢測返回的掩碼,看看是否有fd所屬信道感興趣的事件,比如看看這個屬於輸出信道的fd有沒有輸出就緒等一系列的事件發生,一樣地,如果有一個fd發生感興趣事件就返回調用了。select,為了同時處理三組使用不同的事件判斷規則的fd,采用了位圖的方式表示,一組一個位圖,位長度是當中最大的fd值,上限是1024,三組就是3072,而且這還只是傳入的位圖,還有一樣大小的傳出的位圖。當fd數越來越多時,所需的存儲開銷比較大。
既然,一組fd處理起來比較粗放,那就各個fd自己准備好了。poll()系統調用是System V的多元I/O解決方案。它有三個參數,第一個是pollfd結構的數組指針,也就是指向一組fd及其相關信息的指針,因為這個結構包含的除了fd,還有期待的事件掩碼和返回的事件掩碼,實質上就是將select的中的fd,傳入和傳出參數歸到一個結構之下,也不再把fd分為三組,也不再硬性規定fd感興趣的事件,這由調用者自己設定。這樣,不使用位圖來組織數據,也就不需要位圖的全部遍歷了。按照一般隊列地遍歷,每個fd做poll文件操作,檢查返回的掩碼是否有期待的事件,以及做是否有掛起和錯誤的必要性檢查,如果有事件觸發,就可以返回調用了。
回到poll和select的共同點,面對高並發多連接的應用情境,它們顯現出原來沒有考慮到的不足,雖然poll比起select又有所改進了。除了上述的關於每次調用都需要做一次從用戶空間到內核空間的拷貝,還有這樣的問題,就是當處於這樣的應用情境時,poll和select會不得不多次操作,並且每次操作都很有可能需要多次進入睡眠狀態,也就是多次全部輪詢fd,我們應該怎麼處理一些會出現重復而無意義的操作。
這些重復而無意義的操作有:1、從用戶到內核空間拷貝,既然長期監視這幾個fd,甚至連期待的事件也不會改變,那拷貝無疑就是重復而無意義的,我們可以讓內核長期保存所有需要監視的fd甚至期待事件,或者可以再需要時對部分期待事件進行修改;2、將當前線程輪流加入到每個fd對應設備的等待隊列,這樣做無非是哪一個設備就緒時能夠通知進程退出調用,聰明的開發者想到,那就找個“代理”的回調函數,代替當前進程加入fd的等待隊列好了(這也是我後來才總結出來,Linux的等待隊列,實質上是回調函數隊列吧,也可以使用宏來將當前進程“加入”等待隊列,其實就是將喚醒當前進程的回調函數加入隊列)。這樣,像poll系統調用一樣,做poll文件操作發現尚未就緒時,它就調用傳入的一個回調函數,這是epoll指定的回調函數,它不再像以前的poll系統調用指定的回調函數那樣,而是就將那個“代理”的回調函數加入設備的等待隊列就好了,這個代理的回調函數就自己乖乖地等待設備就緒時將它喚醒,然後它就把這個設備fd放到一個指定的地方,同時喚醒可能在等待的進程,到這個指定的地方取fd就好了。我們把1和2結合起來就可以這樣做了,只拷貝一次fd,一旦確定了fd就可以做poll文件操作,如果有事件當然好啦,馬上就把fd放到指定的地方,而通常都是沒有的,那就給這個fd的等待隊列加一個回調函數,有事件就自動把fd放到指定的地方,當前進程不需要再一個個poll和睡眠等待了。
epoll機制就是這樣改進的了。誠然,fd少的時候,當前進程一個個地等問題不大,可是現在和尚多了,方丈就不好管了。以前設備事件觸發時,只負責喚醒當前進程就好了,而當前進程也只能傻傻地在poll裡面等待或者循環,再來一次poll,也不知道這個由設備提供的poll性能如何,能不能檢查出當前進程已經在等待了就立即返回,當然,我也不明白為什麼做了一遍的poll之後,去掉回調函數指針了,還得再做,不是說好了會去喚醒進程的嗎?
現在就讓事件觸發回調函數多做一步。本來設備還沒就緒就調用一個回調函數了,現在再在這個回調函數裡面做一個注冊另一個回調函數的操作,目的就是使得設備事件觸發多走一步,不僅僅是喚醒當前進程,還要把自己的fd放到指定的地方。就像收本子的班長,以前得一個個學生地去問有沒有本子,如果沒有,它還得等待一段時間而後又繼續問,現在好了,只走一次,如果沒有本子,班長就告訴大家去那裡交本子,當班長想起要取本子,就去那裡看看或者等待一定時間後離開,有本子到了就叫醒他,然後取走。這個道理很簡單,就是老師和班干們常說的,大家多做一點工作,我的工作就輕松很多了,尤其是需要管理的東西越來越多時。
這種機制或者說模式,我想在Java的FutureTask裡面應該也會用到的,一堆在線程池裡面跑著的線程(當然這是任務,不是線程,接口是Callable<V>,不是Runnable.run,是Callable.call,它是可以返回結果的),誰先做好就應該先處理呀,可是難道得一個個問嗎?干脆就誰好了,誰就按照既定的操作暴露自己,這樣FutureTask的get方法就可以馬上知道當前最先完成的線程了,就可以取此線程返回結果了。
epoll由三個系統調用組成,分別是epoll_create,epoll_ctl和epoll_wait。epoll_create用於創建和初始化一些內部使用的數據結構;epoll_ctl用於添加,刪除或者修改指定的fd及其期待的事件,epoll_wait就是用於等待任何先前指定的fd事件。
原文http://www.linuxidc.com/Linux/2013-03/80704p4.htm