李蘭英　溫現(xiàn)杰

摘要：首先簡要介紹了SMP系統(tǒng)的體系結(jié)構(gòu)，接著重點(diǎn)分析了SMP系統(tǒng)中進(jìn)程調(diào)度、同步機(jī)制和負(fù)載平衡三個方面的實(shí)現(xiàn)細(xì)節(jié)，最后給出Cache一致性問題的解決方案。

關(guān)鍵詞：同步機(jī)制；負(fù)載平衡

引言。SMP系統(tǒng)的并行處理技術(shù)，不僅提高處理器的運(yùn)算能力和處理能力，而且對操作系統(tǒng)實(shí)時(shí)性改進(jìn)也提供了一個新的途徑。

1Linux內(nèi)核對SMP系統(tǒng)的支持

2.6內(nèi)核包含更好的SMP系統(tǒng)支持，關(guān)鍵在于能在可用CPU之間進(jìn)行負(fù)載平衡，同時(shí)維持親合性以提高緩存效率。對稱多處理器系統(tǒng)中，每一個CPU都將維護(hù)一個自己的就緒隊(duì)列，并且每個就緒隊(duì)列都有一個自旋鎖，這樣允許所有的CPU都可以對任務(wù)進(jìn)行調(diào)度，而不會與其他CPU產(chǎn)生競爭[1]。

1.1SMP系統(tǒng)的進(jìn)程調(diào)度

2.6內(nèi)核中就緒隊(duì)列定義為復(fù)雜得多的數(shù)據(jù)結(jié)構(gòu)struct runqueue，首先分析一下其結(jié)構(gòu)中關(guān)于SMP系統(tǒng)的定義。

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

runqueue中最關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)。每個CPU的就緒隊(duì)列按時(shí)間片是否用完分為兩部分，分別通過active指針和expired指針訪問，前者指向時(shí)間片沒用完、當(dāng)前可被調(diào)度的就緒進(jìn)程，后者指向時(shí)間片已用完的就緒進(jìn)程。

(2)spinlock_t lock

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

(3) unsigned long nr_uninterruptible

記錄本CPU尚處于TASK_UNINTERRUPTIBLE狀態(tài)的進(jìn)程數(shù)，和負(fù)載信息有關(guān)。

(4) unsigned long timestamp_last_tick

本就緒隊(duì)列最近一次發(fā)生調(diào)度事件的時(shí)間，在負(fù)載平衡的時(shí)候會用到。

還有幾個數(shù)據(jù)項(xiàng)，這里不做介紹了。

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

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

1.2 SMP系統(tǒng)中同步機(jī)制

只有在MP情況下存在真正的并行，因?yàn)榫€程是同時(shí)執(zhí)行的，其中每個處理器中共享相同數(shù)據(jù)的線程同時(shí)執(zhí)行。

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

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

首先通過一個簡單的聲明創(chuàng)建一個新的自旋鎖。

spinlock_t my_spinlock = SPIN_LOCK_UNLOCKED;

…

DEFINE_SPINLOCK(my_spinlock);

…

spin_lock_init(&my_spinlock);

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

spin_lock(&my_spinlock);

…

spin_unlock(&my_spinlock);

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

spin_lock_irqsave(&my_spinlock, flags);

…

spin_unlock_irqrestore(&my_spinlock, flags);

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

spin_lock_bh(&my_spinlock);

…

spin_unlock_bh(&my_spinlock);

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

1.3 負(fù)載平衡

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

Linux 2.6內(nèi)核調(diào)度系統(tǒng)采用相對集中的負(fù)載均衡方案，有"拉"和"推"兩種操作。在load_balance函數(shù)及idle_balance函數(shù)中調(diào)用pull_task函數(shù)來實(shí)現(xiàn)"拉"操作，在migration_thread函數(shù)中實(shí)現(xiàn)"推"操作。

(1)“拉”操作

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

(2)“推”操作

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

2SMP 結(jié)構(gòu)中的Cache一致性問題

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

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

參考文獻(xiàn)

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

[2]Schinmmel,C.現(xiàn)代體系結(jié)構(gòu)上的UNIX系統(tǒng):內(nèi)核程序員的SMP和Caching技術(shù)[M].張 輝譯.北京:人民郵電出版社,2003.P217-227.