Ｌｉｎｕｘ２．６內核對ＳＭＰ系統支持的研究

李蘭英　溫現杰

摘要：首先簡要介紹了SMP系統的體系結構，接著重點分析了SMP系統中進程調度、同步機制和負載平衡三個方面的實現細節，最后給出Cache一致性問題的解決方案。

關鍵詞：同步機制；負載平衡

引言。SMP系統的并行處理技術，不僅提高處理器的運算能力和處理能力，而且對操作系統實時性改進也提供了一個新的途徑。

1Linux內核對SMP系統的支持

2.6內核包含更好的SMP系統支持，關鍵在于能在可用CPU之間進行負載平衡，同時維持親合性以提高緩存效率。對稱多處理器系統中，每一個CPU都將維護一個自己的就緒隊列，并且每個就緒隊列都有一個自旋鎖，這樣允許所有的CPU都可以對任務進行調度，而不會與其他CPU產生競爭[1]。

1.1SMP系統的進程調度

2.6內核中就緒隊列定義為復雜得多的數據結構struct runqueue，首先分析一下其結構中關于SMP系統的定義。

(1) prio_array_t *active, *expired, arrays[2]

runqueue中最關鍵的數據結構。每個CPU的就緒隊列按時間片是否用完分為兩部分，分別通過active指針和expired指針訪問，前者指向時間片沒用完、當前可被調度的就緒進程，后者指向時間片已用完的就緒進程。

(2)spinlock_t lock

就緒隊列的自旋鎖，只影響一個CPU上的就緒隊列。

(3) unsigned long nr_uninterruptible

記錄本CPU尚處于TASK_UNINTERRUPTIBLE狀態的進程數，和負載信息有關。

(4) unsigned long timestamp_last_tick

本就緒隊列最近一次發生調度事件的時間，在負載平衡的時候會用到。

還有幾個數據項，這里不做介紹了。

我們先來總結一下調度器的結構，每個CPU都有一個運行隊列，其中包含了140個優先級列表，它們是按照先進先出的順序進行服務的。被調度執行的任務都會被添加到各自運行隊列優先級列表的末尾。每個任務都有一個時間片，運行隊列的前100個優先級列表保留給實時任務使用，后40個用于用戶任務。除了CPU的運行隊列之外，還有一個過期運行隊列。當活動運行隊列中的一個任務用光自己的時間片之后，它就被移動到過期運行隊列中。在移動過程中，會對其時間片重新進行計算。如果活動運行隊列中已經沒有某個給定優先級的任務了，那么指向活動運行隊列和過期運行隊列的指針就會交換，這樣就可以讓過期優先級列表變成活動優先級的列表。

調度器的工作:在優先級最高的隊列中選擇一個任務來執行。為使這個過程的效率更高，內核使用了一個位圖來定義給定優先級列表上何時存在任務。因此，在大部分體系架構上，會使用一條find-first-bit-set指令在5個32位的字中哪一位的優先級最高。查找一個任務來執行所需要的時間并不依賴于活動任務的個數，而是依賴于優先級的數量，這使得2.6內核的調度器復雜度為O(1)。

1.2 SMP系統中同步機制

只有在MP情況下存在真正的并行，因為線程是同時執行的，其中每個處理器中共享相同數據的線程同時執行。

自旋鎖(spinlock)是使用忙等待鎖來確保互斥鎖的一種特殊方法。如果鎖可用，則獲取鎖，執行互斥鎖動作，然后釋放鎖。如果鎖不可用，線程將忙等待該鎖，直到其可用為止。在可搶占內核和SMP情況下對共享資源的同步問題，一般地一個任務對共享資源的訪問是非常短暫的，如果兩個任務競爭一個共享的資源時，沒有得到資源的任務將自旋以等待另一個任務使用完該共享資源。與原子操作、信號量、讀寫、大內核鎖、讀寫鎖相比，這種鎖機制也是非常高效的。

初始化自旋鎖x是通過宏DEFINE_SPINLOCK(x)實現的，自旋鎖在真正使用前必須先初始化，該宏用于動態初始化。自旋鎖有完全鎖和讀寫鎖兩種形式。在SMP系統中主要用的是完全鎖，這種鎖機制的過程：

首先通過一個簡單的聲明創建一個新的自旋鎖。

spinlock_t my_spinlock = SPIN_LOCK_UNLOCKED;

…

DEFINE_SPINLOCK(my_spinlock);

…

spin_lock_init(&my_spinlock);

定義了自旋鎖之后，就可以使用大量的鎖變量了。每個變量用于不同的上下文。spin_lock和spin_unlock變量。這是一個最簡單的變量，它不會執行中斷禁用，但是包含全部的內存壁壘。這個變量假定中斷處理程序和該鎖之間沒有交互。

spin_lock(&my_spinlock);

…

spin_unlock(&my_spinlock);

接下來是irqsave和irqrestore對，前者需要自旋鎖，并且在本地處理器上禁用中斷。后者釋放自旋鎖，并且(通過flags參數)恢復中斷。

spin_lock_irqsave(&my_spinlock, flags);

…

spin_unlock_irqrestore(&my_spinlock, flags);

最后，如果內核線程通過低半方式共享數據，那么可以使用自旋鎖的另一個變體。

spin_lock_bh(&my_spinlock);

…

spin_unlock_bh(&my_spinlock);

讀寫鎖主要應用在讀取數據比寫入數據更常見情況下。這種模型中允許多個線程同時訪問相同數據，但同一時刻只允許一個線程寫入數據。如果執行寫操作的線程持有此鎖，則臨界段不能由其他線程讀取。如果一個執行讀操作的線程持有此鎖，那么多個讀線程都可以進入臨界段。

1.3 負載平衡

在Linux支持的多處理機系統中，每個處理器維護一個進程就緒隊列runqueue，并獨立的對自己的就緒隊列進行調度操作。由于存在多個就緒進程隊列runqueue,可能存在多個隊列之間負載的不平衡狀況。函數rebalance_tick()（單個CPU時，此函數是不起作用的空函數）當有多個CPU時，在每個CPU上的每個定時器的tick時刻得到調用，檢查每個調度域，在一定的時間間隔時調用函數load_balance()進行負載平衡。該函數在兩種情況下被調用：schedule( )在當前runqueue為空時調用或者在系統空閑時由定時器每1ms調用一次，而在系統忙時則由定時器每200ms調用一次。

Linux 2.6內核調度系統采用相對集中的負載均衡方案，有"拉"和"推"兩種操作。在load_balance函數及idle_balance函數中調用pull_task函數來實現"拉"操作，在migration_thread函數中實現"推"操作。

(1)“拉”操作

“拉”是指系統從重載CPU上“拉”進程過來到輕載CPU上，函數load_balance根據當前CPU是否空閑狀態分為“忙平衡”和“空閑平衡”。每tick時鐘中斷會啟動一次函數rebalance_tick來計算合適的時間間隔，啟動函數load_balance平衡負載。另外，在調度器schedule中，本CPU的就緒隊列為空，就調用idle_balance函數進行“空閑平衡”。函數pull_task實現“拉”進程的具體動作，并更新進程的timestamp屬性，如果被“拉”進程的優先級比本CPU正運行的進程高，則當前進程被搶占。

(2)“推”操作

線程migration_thread執行“推”操作。該進程在系統啟動時自動加載，并將自己設為SCHED_FIFO的實時進程，然后檢查runqueue:migration_queue中是否有請求等待處理，若沒有，則將自己休眠，直至被喚醒后再次檢查。

2SMP 結構中的Cache一致性問題

給SMP系統增加高速緩存能夠利用局部引用特性的優點提高性能，但也會帶來保持高速緩存一致性的問題。當多個處理器存取和修改共享數據時，會出現SMP高速緩存一致性的主要問題。這種問題可以通過使用無高速緩存的操作，以及有選擇的沖洗共享數據來管理共享數據解決。高速緩存與內存一致性問題基本上是由硬件完成的，Intel在Pentum CPU中為已經轉入高速緩存的數據提供了一種自動與內存保持一直的機制，即“窺探”(snooping)機制。這種機制通過監視系統總線對內存的操作，用廢棄緩沖棧方法來重新裝載高速緩存，因而SMP結構中的高速緩存與內存的數據一致性問題是軟件透明的[2]。

3結束語。最新的2.6內核對多處理器體系架構的更好支持，使整個系統更接近于多桌面和實時系統。然而也有一些不進入人意的地方，例如自旋鎖是在保持自旋鎖期間將失效搶占，這意味著搶占延遲將增加，而且搶占延遲也是不確定的。這也成為linux在實時性應用方面的一個障礙。

參考文獻

[1]Daniel P.深入理解LINUX內核[M].陳莉君譯.北京:中國電力出版社,2007.P84-107.

[2]Schinmmel,C.現代體系結構上的UNIX系統:內核程序員的SMP和Caching技術[M].張 輝譯.北京:人民郵電出版社,2003.P217-227.