李蘭英　溫現(xiàn)杰

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

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

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

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

2.6內(nèi)核包含更好的SMP系統(tǒng)支持，關(guān)鍵在于能在可用CPU之間進(jìn)行負(fù)載平衡，同時(shí)維持親合性以提高緩存效率。對(duì)稱多處理器系統(tǒng)中，每一個(gè)CPU都將維護(hù)一個(gè)自己的就緒隊(duì)列，并且每個(gè)就緒隊(duì)列都有一個(gè)自旋鎖，這樣允許所有的CPU都可以對(duì)任務(wù)進(jìn)行調(diào)度，而不會(huì)與其他CPU產(chǎn)生競(jìng)爭(zhēng)[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)。每個(gè)CPU的就緒隊(duì)列按時(shí)間片是否用完分為兩部分，分別通過(guò)active指針和expired指針訪問(wèn)，前者指向時(shí)間片沒(méi)用完、當(dāng)前可被調(diào)度的就緒進(jìn)程，后者指向時(shí)間片已用完的就緒進(jìn)程。

(2)spinlock_t lock

就緒隊(duì)列的自旋鎖，只影響一個(gè)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í)候會(huì)用到。

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

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

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

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

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

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

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

首先通過(guò)一個(gè)簡(jiǎn)單的聲明創(chuàng)建一個(gè)新的自旋鎖。

spinlock_t my_spinlock = SPIN_LOCK_UNLOCKED;

…

DEFINE_SPINLOCK(my_spinlock);

…

spin_lock_init(&my_spinlock);

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

spin_lock(&my_spinlock);

…

spin_unlock(&my_spinlock);

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

spin_lock_irqsave(&my_spinlock, flags);

…

spin_unlock_irqrestore(&my_spinlock, flags);

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

spin_lock_bh(&my_spinlock);

…

spin_unlock_bh(&my_spinlock);

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

1.3 負(fù)載平衡

在Linux支持的多處理機(jī)系統(tǒng)中，每個(gè)處理器維護(hù)一個(gè)進(jìn)程就緒隊(duì)列runqueue，并獨(dú)立的對(duì)自己的就緒隊(duì)列進(jìn)行調(diào)度操作。由于存在多個(gè)就緒進(jìn)程隊(duì)列runqueue,可能存在多個(gè)隊(duì)列之間負(fù)載的不平衡狀況。函數(shù)rebalance_tick()（單個(gè)CPU時(shí)，此函數(shù)是不起作用的空函數(shù)）當(dāng)有多個(gè)CPU時(shí)，在每個(gè)CPU上的每個(gè)定時(shí)器的tick時(shí)刻得到調(diào)用，檢查每個(gè)調(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)采用相對(duì)集中的負(fù)載均衡方案，有"拉"和"推"兩種操作。在load_balance函數(shù)及idle_balance函數(shù)中調(diào)用pull_task函數(shù)來(lái)實(shí)現(xiàn)"拉"操作，在migration_thread函數(shù)中實(shí)現(xiàn)"推"操作。

(1)“拉”操作

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

(2)“推”操作

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

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

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

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

參考文獻(xiàn)

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

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