摘要本章將為大家介紹內核中存在的各種任務調度機理以及它們之間的邏輯關系（這裡將覆蓋進程調度、推後執行、中斷等概念），在此基礎上向大家解釋內核中需要同步保護的根本原因和保護方法。最後提供一個內核共享鏈表同步訪問的例子，幫助大家理解內核編程中的同步問題。內核任務調度與同步關系引言對於從事應用程序開發的朋友來說，用戶空間的任務調度與同步之間的關系相對簡單，無需過多考慮需要同步的原因。這一是因為在用戶空間中各個進程都擁有獨立的運行空間，進程內部的數據對外不可見，所以各個進程即使並發執行也不會產生對數據訪問的競爭。第二是因為用戶空間與內核空間獨立，所以用戶進程不會與內核任務交錯執行，因此用戶進程不存在與內核任務並發的可能。以上兩個原因使得用戶同步僅僅需要在進程間通訊和多線程編程時需要考慮。但是在內核空間中情況要復雜得多，需要考慮同步的原因大大增加了。這是因為內核空間中的共享數據對內核中的所有任務可見，所以當在內核中訪問數據時，就必須考慮是否會有其他內核任務並發訪問的可能、是否會產生競爭條件、是否需要對數據同步。而內核並發的“罪魁禍首”便是內核中復雜多變的任務調度——這裡的任務調度包含所有可能引起內核任務更換的情況。並發，競爭和同步的概念，我們假定大家都有所了解，本文不再重申。下面一段描述了上述幾個概念之間的大致關系，這種關系在內核中同樣適用。對於多線程程序的開發者來說，往往會利用多線程訪問共享數據，避免繁瑣的進程間通訊。但是多線程對共享數據的並發訪問有可能產生競爭，使得數據處於不一致狀態，所以需要一些同步方法來保護共享數據。多線程的並發執行是由於線程被搶占式的調度——一個線程在對共享數據訪問期間（還未完成）被調度程序中斷，將另一個線程投入運行——如果新被調度的線程也要對這個共享數據進行訪問，就將產生競爭。為了避免競爭產生，需要使線程串行地訪問共享數據 ，也就是說訪問需要同步——在一方對數據訪問結束後，另一方才能對同一數據進行訪問。內核任務這裡所定義的內核任務是指內核中執行的一切活動對象，每個內核任務都擁有一個獨立的程序計數器、棧和一組寄存器。更重要的是,它們都屬於內核調度（這裡的調度是廣義上的，不要與進程調度混淆）對象，也就是說它們是可以在內核中交錯執行的。內核任務分類內核任務包含“內核線程”、“系統調用”、“硬件中斷”、“半底任務”等幾類。下來我們就簡要地討論上述幾類內核任務的特點。系統調用系統調用是用戶程序通過門機制來進入內核執行的內核例程，它運行在內核態，處於進程上下文中（進程上下文包括進程的堆棧等等環境），可以認為是代表用戶進程的內核任務，因此具有用戶態任務的特性，比如可以執行進程調度程序（schedule()）、可以睡眠、可以訪問當前進程數據（通過current）。但它屬於內核任務，所以在執行過程中不能被搶占（2.6內核前），只能自己放棄cpu（睡眠）時，系統才能可能重新調度別的任務。（有關系統調用部分請看《系統調用》一章）硬中斷任務硬中斷是指那些由處理器以外的外設產生的中斷，這些中斷被處理器接收後交給內核中的中斷處理程序處理。要注意的是：第一, 硬中斷是異步產生的，中斷發生後立刻得到處理，也就是說中斷操作可以搶占內核中正在運行的代碼。這點非常重要。第二，中斷操作是發生在中斷上下文中的（所謂中斷上下文指的是和任何進程無關的上下文環境）。中斷上下文中不可以使用進程相關的資源，也不能夠進行調度或睡眠。因為調度會引起睡眠，但睡眠必須針對進程而言（睡眠其實是標記進程狀態，然後把當前進程推入睡眠列隊），而異步發生的中斷處理程序根本不知道當前進程的任何信息，也不關心當前哪個進程在運行，它完全是個過客。（有關硬件中斷部分請看《硬件中斷》一章）下半底任務半底的來歷完全出自上面提到的硬中斷的影響。硬件中斷任務（處理程序）是一個快速、異步、簡單地對硬件做出迅速響應並在最短時間內完成必要操作的中斷處理程序。硬中斷處理程序可以搶占內核任務並且執行時還會屏蔽同級中斷或其它中斷，因此中斷處理必須要快、不能阻塞。這樣一來對於一些要求處理過程比較復雜的任務就不合適在中斷任務中一次處理。比如，網卡接收數據的過程中,首先網卡發送中斷信號告訴CPU來取數據，然後系統從網卡中讀取數據存入系統緩沖區中，再下來解析數據然後送入應用層。這些如果都讓中斷處理程序來處理顯然過程太長，造成新來的中斷丟失。因此Linux開發人員將這種任務分割為兩個部分，一個叫上底，即中斷處理程序，短平快地處理與硬件相關的操作（如從網卡讀數據到系統緩存）；而把對時間要求相對寬松的任務（如解析數據的工作）放在另一個部分執行，這個部分就是我們這裡要講的下半底。下半底是一種推後執行任務，它將某些不那麼緊迫的任務推遲到系統更方便的時刻運行。內核中實現下半底的手段經過不斷演化，目前已經從最原始的BH(bottom thalf)演生出BH、任務隊列（Task queues）、軟中斷（Softirq）、Tasklet、工作隊列（Work queues）（2.6內核中新出現的）。下面我們就介紹一下他們各自的特點。軟中斷操作軟中斷（softirq）不象硬中斷那樣是由硬件中斷信號觸發執行的，所以也不同於硬件中斷那樣時隨時都能夠被執行，籠統來講,軟中斷會在內核處理任務完畢後返回用戶級程序前得到處理機會。具體的講,有三個時刻它將被執行(do_softirq())：硬件中斷操作完成後；系統調用返回時；內核調度程序中；（另外,內核線程ksoftirqd周期執行軟中斷）。從中可以看出軟中斷會緊隨硬中斷處理(好象狐假虎威),所以搶占內核任務——至少在時鐘中斷後總有機會運行一次。還要記得軟中斷可以在不同處器上並發執行。在有對稱多處理器的機器上，那麼兩個任務就可以真正的在臨界區中同時執行了，這種類型被稱為真並發。相對而言在,單處理器上並發其實並不是真的同時發生，而是相互交錯執行，是偽並發。但它們都同樣會造成競爭條件，而且也需要同樣的保護。軟中斷是很底層的機制，一般除了在網絡子系統和SCSI子系統這樣對性能要求很高以及要求並發處理的時候，才會選擇使用軟中斷。軟中斷雖然靈活性高和效率高，但是你自己必須處理復雜的同步處理（因為它可在多處理器上並發），所以通常都不直接使用，而是作為支持Tasklet和BH的根本。需要說明的是,軟中斷的執行也處於中斷上下文中，所以中斷上下文對它的限制是和硬中斷一樣的。TaskletTasklet和bottom half都是建立在軟中斷之上的兩種延遲機制，其具體不同之處在於軟中斷是靜態分配的，而且同類軟中斷可以並發地在幾個CPU上運行；Tasklet可以動態分配，並且不同種類的Tasklets可以並發地在幾個CPU上運行，但同類的tasklets 不可以；bottom half只能靜態分配，實質上,下半部分是一個不能與其它下半部分並發執行的高優先級tasklet，即使它們類型不同，而且在不同CPU上運行。Tasklet可以理解為軟中斷的派生，所以它的調度時機與軟中斷一致。對於內核中需要延遲執行的多數任務都可以利用tasklet來完成，由於同類tasklet本身已經進行了同步保護，所以使用tasklet相比軟中斷要簡單得多，而且效率也不錯。bottom half是 BH時最早的內核延遲方法，它原始、簡單且容易控制，因為所有的BH處理程序都被嚴格地順序執行——不允許任何兩個BH處理程序同時並發執行，即使它們的類型不同也不可以，這樣一來BH執行其間減少了許多同步保護。但是BH不得不被淘汰，因為它的“簡便”犧牲了多處理器並發處理的高性能，等於一隊人過獨木橋那樣速度受到牽制。任務隊列任務列隊是BH的替代品，來自BH，所以它的屬性也和BH相同。它的原意在於簡化BH的操作接口，但它的隨意性（數量隨意、執行時機隨意）卻給系統帶來了混亂，所以到今天已經被工作隊列（在2.6內核中）所取代。不過在2.4內核中任務隊列還是被大量應用，尤其是調度隊列、定時器隊列和立即隊列等三種任務隊列（除了這三種系統已接管的特定任務隊列外，你自己也可隨心所欲的建立自己的任務隊列，當然這時你要自己調度它）。調度隊列的任務會在每次進程調度時得到處理，它是在進程上下文中處理的；定時器隊列會在每次時鐘滴答時得到處理；立即隊列會在中斷返回或調度時獲得處理（所以處理最快），他們都是在中斷上下文中處理的。這些任務隊列在內核內由一個統一的內核線程調度，該線程名為keventd，進程號是2（2.4.18）。你可用ps命令查看到該進程。內核線程內核線程可以理解成在內核中運行的特殊進程，它有自己的“進程上下文”（借用調用它的用戶進程的上下文），所以同樣被進程調度程序調度，也可以睡眠——它和用戶進程屬性何其相似，不同之處就在於內核線程運行於內核空間，可訪問內核數據，運行期間不能被搶占。傳統的Unix系統把一些重要的任務委托給周期性執行的進程，這些任務包括刷新磁盤高速緩存，交換出不用的頁面，維護網絡鏈接等等。事實上，以嚴格線性的方式執行這些任務的確效率不高，如果把他們放在後台調度，不管是對它們的函數還是對終端用戶進程都能得到較好地響應。因為一些系統進程只運行在內核態，現代操作系統把它們的函數委托給內核線程（Kernel Thread），內核線程不受不必要的用戶態上下文的拖累。內核中的同步內核只要存在任務交錯執行，就必然會存在對共享數據的並發問題，也就必然存在對數據的保護。而內核中任務交錯執行的原因歸根結底還是由於內核任務調度造成的。我們下面歸納一下內核中同步的原因。同步原因l 中斷——中斷幾乎可以在任何時刻異步發生，也就可能隨時打斷當前正在執行的代碼。l 睡眠及與用戶空間的同步——在內核執行的進程可能會睡眠，這就會喚醒調度程序，從而導致調度一個新的用戶進程執行。l 對稱多處理——兩個或多個處理器可以同時執行代碼。l 內核搶占——因為內核具有搶占性，所以內核中的任務可能會被另一任務搶占（在2.6內核引進的新能力）。後兩種情況大大增加了內核任務並發執行的可能性，使得並發隨時隨刻都有可能發生，而且不可清晰預見，規律難尋。內核任務之間的並發關系上述內核任務很多情況是可以交錯執行的——記住，一個下半部實際上可能在任何時候執行，所以很有可能產生競爭（都要訪問同一個數據結構時，就產生了競爭）。下面分析這些內核任務之間有哪些可能的並發行為。可以抽象出，程序（用戶態和內核態一樣）並發執行的總原因無非是正在運行中的程序被其它程序搶占，所以我們必須看看內核任務之間的搶占關系：n 中斷處理程序可以搶占內核中的所有程序（當沒有鎖保護時），包括軟中斷，tasklet，bottom half和系統的調用、內核線程，甚至也包括硬中斷處理程序。也就是說中斷處理程序可以和這些所有的內核任務並發執行，如果被搶占的程序和中斷處理程序都要訪問同一個資源，就必然有可能產生競爭。n 軟件中斷也可以搶占內核中的所有任務，所以內核代碼（比如，系統調用、內核線程等）中有數據和軟中斷共享，就會有競爭——除此外硬件中斷處理程序也有可能被軟中斷打斷，條件是硬中斷被其它硬中斷打斷，軟中斷隨即便獲得了執行機會，因為軟中斷是跟在硬中斷後執行的。此外要注意的是，軟中斷即使是同種類型的也可以並發地運行在不同處理器上，所以它們之間共享數據都會產生競爭。（如果在同一個處理器上,軟中斷之間是不能相互搶占的）。n 同類的tasklet不可能同時運行，所以對於同類tasklet之間是串行運行的，他們不會產生並發；但兩個不同種類的tasklet有可能在不同處理器上並發運行，如果之間有數據共享就會產生競爭（在同一個處理器上運行的tasklet不發生相互搶占的情況）。n Bottom half 無論是否是同類的，即使在不同處理器上也都不能並發執行，它是絕對串行化的，所以它們之間永遠不能產生競爭。任務列隊屬性基本同BH。n 系統調用和內核線程這種運行在進程上下文中的內核任務可能和各種內核任務並發，除了上面提到的中斷（軟，硬）來搶占它而產生並發外，它也有可能自發性地主動睡眠（比如在一些阻塞性的操作中），放棄處理器，重新調度其它任務，所以系統調用和內核線程除會與軟硬中斷（半底等）發生競爭，也會與其他（包括自己）系統調用與內核線程發生競爭。我們尤其要注意這種情況。注意：tasklet和bottom half是建立在軟中斷之上的，所以它們也都遵從軟中斷的調度規則——都可以打斷進程上下文中的內核代碼（系統調用），都可被硬中斷打斷——這些情況下都可能產生並發。內核同步措施為了避免並發，防止競爭。內核提供了一組同步方法來提供對共享數據的保護。 我們的重點不是介紹這些方法的詳細用法，而是強調為什麼使用這些方法和它們之間的差別。Linux使用的同步機制可以說從2.0到2.6以來不斷發展完善。從最初的原子操作，到後來的信號量，從大內核鎖到今天的自旋鎖。這些同步機制的發展伴隨 Linux從單處理器到對稱多處理器的過度；伴隨著從非搶占內核到搶占內核的過度。鎖機制越來越有效，也越來越復雜。目前來說內核中原子操作多用來做計數使用，其它情況最常用的是兩重鎖以及它們的變種，一個是自旋鎖，另一個是信號量。我們下面就來著重介紹一下這兩種鎖機制。自旋鎖自旋鎖是專為防止多處理器並發而引入的一種鎖，它在內核中大量應用於中斷處理等部分（對於單處理器來說，防止中斷處理中的並發可簡單采用關閉中斷的方式，不需要自旋鎖）。自旋鎖最多只能被一個內核任務持有，如果一個內核任務試圖請求一個已被爭用（已經被持有）的自旋鎖，那麼這個任務就會一直進行忙循環——旋轉——等待鎖重新可用。要是鎖未被爭用，請求它的內核任務便能立刻得到它並且繼續進行。自旋鎖可以在任何時刻防止多於一個的內核任務同時進入臨界區，因此這種鎖可有效地避免多處理器上並發運行的內核任務競爭共享資源。事實上，自旋鎖的初衷就是：在短期間內進行輕量級的鎖定。一個被爭用的自旋鎖使得請求它的線程在等待鎖重新可用的期間進行自旋（特別浪費處理器時間），所以自旋鎖不應該被持有時間過長。如果需要長時間鎖定的話, 最好使用信號量。自旋鎖的基本形式如下：spin_lock(&mr_lock);/*臨界區*/spin_unlock(&mr_lock);因為自旋鎖在同一時刻只能被最多一個內核任務持有，所以一個時刻只有一個線程允許存在於臨界區中。這點很好地滿足了對稱多處理機器需要的鎖定服務。在單處理器上，自旋鎖僅僅當作一個設置內核搶占的開關。如果內核搶占也不存在，那麼自旋鎖會在編譯時被完全剔除出內核。自旋鎖在內核中有許多變種，如對bottom half 而言，可以使用spin_lock_bh()用來獲得特定鎖並且關閉半底執行。相反的操作由spin_unlock_bh()來執行；如果臨界區的訪問邏輯可以被清晰的分為讀和寫這種模式，那麼可以使用讀者/寫者自旋鎖，調用形式為：讀者的代碼路徑：read_lock(&mr_rwlock);/*只讀臨界區*/read_unlock(&mr_rwlock);寫者的代碼路徑：write_lock(&mr_rwlock);/*讀寫臨界區*/write_unlock(&mr_rwlock);簡單的說，自旋鎖在內核中主要用來防止多處理器中並發訪問臨界區，防止內核搶占造成的競爭。另外自旋鎖不允許任務睡眠（持有自旋鎖的任務睡眠會造成自死鎖——因為睡眠有可能造成持有鎖的內核任務被重新調度，而再次申請自己已持有的鎖），它能夠在中斷上下文中使用。死鎖：假設有一個或多個內核任務和一個或多個資源，每個內核都在等待其中的一個資源，但所有的資源都已經被占用了。這便會發生所有內核任務都在相互等待，但它們永遠不會釋放已經占有的資源，於是任何內核任務都無法獲得所需要的資源，無法繼續運行，這便意味著死鎖發生了。自死瑣是說自己占有了某個資源，然後自己又申請自己已占有的資源，顯然不可能再獲得該資源，因此就自縛手腳了。信號量 Linux中的信號量是一種睡眠鎖。如果有一個任務試圖獲得一個已被持有的信號量時，信號量會將其推入等待隊列，然後讓其睡眠。這時處理器獲得自由去執行其它代碼。當持有信號量的進程將信號量釋放後，在等待隊列中的一個任務將被喚醒，從而便可以獲得這個信號量。信號量的睡眠特性，使得信號量適用於鎖會被長時間持有的情況；只能在進程上下文中使用，因為中斷上下文中是不能被調度的；另外當代碼持有信號量時，不可以再持有自旋鎖。信號量基本使用形式為：static DECLARE_MUTEX(mr_sem);//聲明互斥信號量…if(down_interruptible(&mr_sem))/*可被中斷的睡眠，當信號來到，睡眠的任務被喚醒 *//*臨界區…*/up(&mr_sem);同自旋鎖一樣，信號量在內核中也有許多變種，比如讀者－寫者信號量等，這裡不再做介紹了。信號量和自旋鎖區別雖然聽起來兩者之間的使用條件復雜，其實在實際使用中信號量和自旋鎖並不易混淆。注意以下原則。如果代碼需要睡眠——這往往是發生在和用戶空間同步時——使用信號量是唯一的選擇。由於不受睡眠的限制，使用信號量通常來說更加簡單一些。如果需要在自旋鎖和信號量中作選擇，應該取決於鎖被持有的時間長短。理想情況是所有的鎖都應該盡可能短的被持有，但是如果鎖的持有時間較長的話，使用信號量是更好的選擇。另外，信號量不同於自旋鎖，它不會關閉內核搶占，所以持有信號量的代碼可以被搶占。這意味者信號量不會對影響調度反應時間帶來負面影響。自旋鎖對信號量―――――――――――――――――――――――――――――――需求 建議的加鎖方法低開銷加鎖 優先使用自旋鎖短期鎖定 優先使用自旋鎖長期加鎖 優先使用信號量中斷上下文中加鎖 使用自旋鎖持有鎖是需要睡眠、調度 使用信號量―――――――――――――――――――――――――――――――引自 《Linux內核開發》防止並發的方式除了上面提到的外還有很多，我們不詳細介紹了。說了這麼多,希望大家認識到，並發控制在內核編程中是個特別難纏的問題，要駕御它必須清楚地認識到內核中各種任務的調度時機與特點，並且在開發初期就應特別小心保護共享數據（一切共享數據、一切能被別人看到的數據都要注意保護），別等到開發完成才去亡羊補牢。並發控制實例我們下面給出一個多內核任務訪問共享資源的具體例子，其中會用到上面提到的各種同步方法，希望能給大家一個形象的記憶。該例子的具體場景描述如下。我們主要的共享資源是鏈表（mine）,操作它的內核任務有三種：一個是100個內核線程（sharelist），它們負責從表頭將新節點（strUCt my_struct）插入鏈表。二是定時器任務(qt_task)，它負責每個時鐘滴答時從鏈表頭刪除一個節點。三是系統調用（由rmmod命令調用的share_exit），它負責銷毀鏈表並卸載模塊。我們利用模塊（sharelist.o）實現上述場景。加載模塊時會建立定時器任務列隊，並將要執行的任務(task.rounting=qt_task)插入定時器隊列（tq_timer），然後反復調度執行（但別不停地執行）。與此同時利用系統中的keventd內核線程（它的目的是執行任務隊列,由schedule_task激活，PID=2），創建100個內核線程(創建函數kernel_thread)執行插入鏈表的工作（由sharelist完成）——但當鏈表長度超過100時，則從鏈表尾刪除節點。最後當你需要卸載模塊時，調用share_exit函數銷毀整個鏈表，並做一些諸如銷毀我們建立的內核進程的收尾工作。下面我們具體看看在程序中該如何保護我們的鏈表。上述場景中存在的內核並發包括——內核線程之間的並發、內核任務與定時器任務的並發。要知道內核線程執行在進程上下文中，而定時器任務屬於下半部分，執行在中斷上下文中。在這兩部分交錯執行中進行保護則需要采用自旋鎖。我們例子中使用了spin_lock_bh()鎖在內核線程的執行路徑中對鏈表進行保護；在下半部分,由於任務隊列是串行執行並且不能被內核任務或系統調用打斷，所以不必加鎖。另外在卸載模塊時，刪除鏈表中仍然存在系統調用與下半部分的並發可能，因此也需要按上述方式加鎖。除了對共享鏈表訪問使用自旋鎖以外，還有兩個需要同步的地方，一是計數（count），該變量屬於原子類型，用於記錄鏈表接點的id。另外一個是利用信號量同步內核創建線程，調度keventd後執行被堵塞住(down)，等內核線程實際啟動後, 才可繼續執行（up）。結束並發的發生隨處都有，但是由它引起的錯誤可並非每次都有，因為並發過程中引起錯誤的地方往往就一兩步，因此交錯執行這一兩步要靠“運氣”，出錯的幾率有時很小。但是一旦發生後果都是災難性的，比如宕機，破壞數據完整性等。所以我們對並發絕不能掉以輕心，必須拿出“把紙老虎當真老虎的”決心來對待一切內核代碼中可能的並發，即便在單處理器上編程也需要考慮到移植到多處理器的情況，總之一切都要謹慎小心。
