多核處理器任務(wù)調(diào)度的思考

摘要：本文主要分析了Linux操作系統(tǒng)對(duì)于多核處理器的任務(wù)調(diào)度，探討了目前操作系統(tǒng)在面對(duì)多核處理器時(shí)所要解決的關(guān)鍵問(wèn)題，并在此基礎(chǔ)上進(jìn)一步提出新的多核處理器的任務(wù)調(diào)度算法。

關(guān)鍵詞：多核；處理器；任務(wù)

中圖分類號(hào)：TP332 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2012） 18-0000-02

目前，隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，多核處理器已經(jīng)打面積普及，而在這種多核體系結(jié)構(gòu)下，如何更好的利用好沒(méi)一個(gè)核心，充分發(fā)掘處理器的效率，成為一個(gè)關(guān)鍵問(wèn)題。當(dāng)處理器是單核心的時(shí)候，對(duì)于任務(wù)的處理處理器只需要按照既定的算法依次處理每個(gè)任務(wù)，但是當(dāng)面對(duì)多核處理器時(shí)，這種方式顯然效率低下，造成計(jì)算能力的極大浪費(fèi)。為此我們必須要思考，當(dāng)面對(duì)多核處理器的時(shí)候，我們?nèi)绾伟汛罅咳蝿?wù)更好的分配給處理器的核心，以充分使用處理器，提高資源的利用率。

對(duì)于單核處理器，我們已經(jīng)有大量的成熟算法，諸如先來(lái)先服務(wù)算法，輪轉(zhuǎn)調(diào)度法等，顯然這些算法無(wú)法滿足多核處理器的任務(wù)調(diào)度需求。一個(gè)任務(wù)到來(lái)應(yīng)該分配給哪一個(gè)核心；分配完成后是不是需要調(diào)整整個(gè)處理器的負(fù)載，以達(dá)到每個(gè)核的負(fù)載均衡；一個(gè)任務(wù)完成后，會(huì)不會(huì)出現(xiàn)大面積的核心空閑，而部分核心負(fù)載過(guò)重，有大量任務(wù)唄阻塞，面對(duì)多核處理器由此產(chǎn)生的新問(wèn)題迫使我們不得不重新發(fā)掘新的處理器任務(wù)調(diào)度算法。

鑒于處理器的調(diào)度是由操作系統(tǒng)來(lái)實(shí)施的，當(dāng)前比較成熟的CMP體系操作系統(tǒng)是Linux，Windows，Mac OS。我們通過(guò)分析當(dāng)前已有操作系統(tǒng)的多核任務(wù)調(diào)度，依次來(lái)借鑒，考慮到目前Linux系統(tǒng)的開(kāi)源性，我們著重分析Linux系統(tǒng)，當(dāng)然Linux目前對(duì)于多核的處理也是比較經(jīng)典的，有大量的服務(wù)器采用了Linux。

Linux系統(tǒng)在調(diào)度多個(gè)核心是，給每個(gè)和性能都建立一個(gè)活動(dòng)就緒隊(duì)列，并且把就緒任務(wù)劃分成140個(gè)優(yōu)先級(jí)，其中高100個(gè)優(yōu)先級(jí)用于實(shí)時(shí)任務(wù)，而低40個(gè)優(yōu)先級(jí)分配給普通用戶任務(wù)。每個(gè)就緒任務(wù)都有一個(gè)時(shí)間片，當(dāng)時(shí)間片用完后將該任務(wù)轉(zhuǎn)移到該核心的等待就緒隊(duì)列并重新分配時(shí)間片。如果該核心的活動(dòng)就緒隊(duì)列的所有任務(wù)的時(shí)間片都已運(yùn)行完畢，則該核心的等待就緒隊(duì)就轉(zhuǎn)換為活動(dòng)就緒隊(duì)列。以此保證各個(gè)任務(wù)可以公平使用核心。而Linux的處理器核心的負(fù)載均衡主要通過(guò)以下兩種方式來(lái)實(shí)現(xiàn)，一是當(dāng)一個(gè)核心上的任務(wù)全部結(jié)束后從最繁忙的核心上任意獲取一個(gè)任務(wù)來(lái)執(zhí)行，另一種則是在所有核心都有任務(wù)時(shí)每隔一定時(shí)間檢查以下所有核心，如果不均衡則發(fā)生任務(wù)遷移。

對(duì)于微軟比較經(jīng)典的Windows7來(lái)說(shuō)，主要是采用了一種稱為NUMA的技術(shù)，該技術(shù)是一種分布式的存儲(chǔ)器訪問(wèn)技術(shù)。使用該技術(shù)，處理器可以同時(shí)訪問(wèn)不同的存儲(chǔ)器地址。具體來(lái)說(shuō)就是，處理器的每個(gè)核心都被分配有一個(gè)本地存儲(chǔ)器地址空間，但該核心也可以訪問(wèn)全部的物理存儲(chǔ)器。這樣就在傳統(tǒng)的多核與一個(gè)集中的存儲(chǔ)器的系統(tǒng)結(jié)構(gòu)上，提高了訪問(wèn)效率，便于核間的保護(hù)。

總的來(lái)說(shuō)Linux較好的利用了多核處理器，但在面對(duì)復(fù)雜程序的多個(gè)任務(wù)時(shí)，未考慮讓這些任務(wù)盡量在同一個(gè)核心上運(yùn)行，以避免遷移產(chǎn)生的低效。從以上分析來(lái)看，我們?cè)趯?duì)多核處理器進(jìn)行任務(wù)調(diào)度時(shí)，要盡量保證同一程序的多個(gè)任務(wù)在同一核心上運(yùn)行，以降低cache的缺失率，方便數(shù)據(jù)通信，同時(shí)減少任務(wù)的遷移次數(shù)；與此同時(shí)，還需要盡量的保證每個(gè)核的負(fù)載均衡，以便提高處理器的利用效率，提升系統(tǒng)性能。因此，所要充分發(fā)揮多核處理器的性能，必須完美解決上述兩個(gè)看似矛盾而又統(tǒng)一的問(wèn)題。

2 結(jié)束語(yǔ)

這樣在最壞的情況下，如果一個(gè)程序有多個(gè)長(zhǎng)任務(wù)，此時(shí)會(huì)發(fā)生遷移以提高效率；如果是多個(gè)短任務(wù)，發(fā)生遷移也不會(huì)造成效率下降。

基于以上的調(diào)度策略，經(jīng)初步的實(shí)驗(yàn)表明，可以大幅度提高處理器的使用效率，但是對(duì)于多核系統(tǒng)的研究還需進(jìn)一步的思考。

參考文獻(xiàn)：

[1]（美）拉芙 著，陳莉君，康華 譯. Linux內(nèi)核設(shè)計(jì)與實(shí)現(xiàn)（原書(shū)第3版），2011，6，1

[2]（美）科曼（Cormen，T.H.）等著，潘金貴等譯.算法導(dǎo)論（原書(shū)第2版）.2006.9.1.