Linux超線程感知的調(diào)度算法研究
加入技術(shù)交流群
1 超線程技術(shù)背景
傳統(tǒng)的處理器內(nèi)部存在著多種并行操作方式。①指令級并行ILP(Instruction Level Paramllelism)：同時執(zhí)行幾條指令，單CPU就能完成。但是，傳統(tǒng)的單CPU處理器只能同時執(zhí)行一個線程，很難保證CPU資源得到100%的利用，性能提高只能通過提升時鐘頻率和改進(jìn)架構(gòu)來實(shí)現(xiàn)。②線程級并行TLP(Thread Level Paramllesim)：可以同時執(zhí)行多個線程，但是需要多處理器系統(tǒng)的支持，通過增加CPU的數(shù)量來提高性能。
超線程微處理器將同時多線程技術(shù)SMT(Simultaneous Multi-Threading)引入Intel體系結(jié)構(gòu)，支持超線程技術(shù)的操作系統(tǒng)將一個物理處理器視為兩個邏輯處理器，并且為每個邏輯處理器分配一個線程運(yùn)行。物理處理器在兩個邏輯處理器之間分配高速緩存、執(zhí)行單元、總線等執(zhí)行資源，讓暫時閑置的運(yùn)算單元去執(zhí)行其他線程代碼，從而最大限度地提升CPU資源的利用率。
Intel 超線程技術(shù)通過復(fù)制、劃分、共享Intel的Netburst微架構(gòu)的資源讓一個物理CPU中具有兩個邏輯CPU。(1)復(fù)制的資源：每個邏輯CPU都維持一套完整的體系結(jié)構(gòu)狀態(tài)，包括通用寄存器、控制寄存器、高級可編程寄存器(APIC)以及一些機(jī)器狀態(tài)寄存器，體系結(jié)構(gòu)狀態(tài)對程序或線程流進(jìn)行跟蹤。從軟件的角度，一旦體系結(jié)構(gòu)狀態(tài)被復(fù)制，就可以將一個物理CPU視為兩個邏輯CPU。(2)劃分的資源：包括重定序(re-order)緩沖、Load/Store緩沖、隊(duì)列等。劃分的資源在多任務(wù)模式時分給兩個邏輯CPU使用，在單任務(wù)模式時合并起來給一個邏輯CPU使用。(3)共享的資源：包括cache及執(zhí)行單元等，邏輯CPU共享物理CPU的執(zhí)行單元進(jìn)行加、減、取數(shù)等操作。
在線程調(diào)度時，體系結(jié)構(gòu)狀態(tài)對程序或線程流進(jìn)行跟蹤，各項(xiàng)工作(包括加、乘、加載等)由執(zhí)行資源(處理器上的單元)負(fù)責(zé)完成。每個邏輯處理器可以單獨(dú)對中斷作出響應(yīng)。第一個邏輯處理器跟蹤一個線程時，第二個邏輯處理器可以同時跟蹤另一個線程。例如，當(dāng)一個邏輯處理器在執(zhí)行浮點(diǎn)運(yùn)算時，另一個邏輯處理器可以執(zhí)行加法運(yùn)算和加載操作。擁有超線程技術(shù)的CPU可以同時執(zhí)行處理兩個線程，它可以將來自兩個線程的指令同時發(fā)送到處理器內(nèi)核執(zhí)行。處理器內(nèi)核采用亂序指令調(diào)度并發(fā)執(zhí)行兩個線程，以確保其執(zhí)行單元在各時鐘周期均處于運(yùn)行狀態(tài)。
圖1和圖2分別為傳統(tǒng)的雙處理器系統(tǒng)和支持超線程的雙處理器系統(tǒng)。傳統(tǒng)的雙處理器系統(tǒng)中，每個處理器有一套獨(dú)立的體系結(jié)構(gòu)狀態(tài)和處理器執(zhí)行資源，每個處理器上只能同時執(zhí)行一個線程。支持超線程的雙處理器系統(tǒng)中，每個處理器有兩套獨(dú)立體系結(jié)構(gòu)狀態(tài)，可以獨(dú)立地響應(yīng)中斷。
2 Linux超線程感知調(diào)度優(yōu)化
Linux從2.4.17版開始支持超線程技術(shù)，傳統(tǒng)的Linux O(1)調(diào)度器不能區(qū)分物理CPU和邏輯CPU，因此不能充分利用超線程處理器的特性。Ingo Monlar編寫了“HT-aware scheduler patch”，針對超線程技術(shù)對O(1)調(diào)度器進(jìn)行了調(diào)度算法優(yōu)化：優(yōu)先安排線程在空閑的物理CPU的邏輯CPU上運(yùn)行，避免資源競爭帶來的性能下降；在線程調(diào)度時考慮了在兩個邏輯CPU之間進(jìn)行線程遷移的開銷遠(yuǎn)遠(yuǎn)小于物理CPU之間的遷移開銷以及邏輯CPU共享cache等資源的特性。這些優(yōu)化的相關(guān)算法被Linux的后期版本所吸收，具體如下：
(1)共享運(yùn)行隊(duì)列
在對稱多處理SMP(Symmetrical Multi-Processing)環(huán)境中，O(1)調(diào)度器為每個CPU分配了一個運(yùn)行隊(duì)列，避免了多CPU共用一個運(yùn)行隊(duì)列帶來的資源競爭。Linux會將超線程CPU中的兩個邏輯CPU視為SMP的兩個獨(dú)立CPU，各維持一個運(yùn)行隊(duì)列。但是這兩個邏輯CPU共享cache等資源，沒有體現(xiàn)超線程CPU的特性。因此引入了共享運(yùn)行隊(duì)列的概念。HT-aware scheduler patch在運(yùn)行隊(duì)列struct runqueue結(jié)構(gòu)中增加了nr_cpu和cpu兩個屬性，nr_cpu記錄物理CPU中的邏輯CPU數(shù)目，CPU則指向同屬CPU(同一個物理CPU上的另一個邏輯CPU)的運(yùn)行隊(duì)列，如圖3所示。
在Linux中通過調(diào)用sched_map_runqueue( )函數(shù)實(shí)現(xiàn)兩個邏輯CPU的運(yùn)行隊(duì)列的合并。sched_map_runqueue( )首先會查詢系統(tǒng)的CPU隊(duì)列，通過phys_proc_id(記錄邏輯CPU所屬的物理CPU的ID)判斷當(dāng)前CPU的同屬邏輯CPU。如果找到同屬邏輯CPU，則將當(dāng)前CPU運(yùn)行隊(duì)列的cpu屬性指向同屬邏輯CPU的運(yùn)行隊(duì)列。
(2)支持“被動的”負(fù)載均衡
用中斷驅(qū)動的均衡操作必須針對各個物理 CPU，而不是各個邏輯 CPU。否則可能會出現(xiàn)兩種情況：一個物理 CPU 運(yùn)行兩個任務(wù)，而另一個物理 CPU 不運(yùn)行任務(wù)；現(xiàn)有的調(diào)度程序不會將這種情形認(rèn)為是“失衡的”。在調(diào)度程序看來，似乎是第一個物理處理器上的兩個 CPU運(yùn)行1-1任務(wù)，而第二個物理處理器上的兩個 CPU運(yùn)行0-0任務(wù)。
在2.6.0版之前，Linux只有通過load_balance( )函數(shù)才能進(jìn)行CPU之間負(fù)載均衡。當(dāng)某個CPU負(fù)載過輕而另一個CPU負(fù)載較重時，系統(tǒng)會調(diào)用load_balance( )函數(shù)從重載CPU上遷移線程到負(fù)載較輕的CPU上。只有系統(tǒng)最繁忙的CPU的負(fù)載超過當(dāng)前CPU負(fù)載的 25% 時才進(jìn)行負(fù)載平衡。找到最繁忙的CPU(源CPU)之后，確定需要遷移的線程數(shù)為源CPU負(fù)載與本CPU負(fù)載之差的一半,然后按照從 expired 隊(duì)列到 active 隊(duì)列、從低優(yōu)先級線程到高優(yōu)先級線程的順序進(jìn)行遷移。
在超線程系統(tǒng)中進(jìn)行負(fù)載均衡時，如果也是將邏輯CPU等同于SMP環(huán)境中的單個CPU進(jìn)行調(diào)度，則可能會將線程遷移到同一個物理CPU的兩個邏輯CPU上，從而導(dǎo)致物理CPU的負(fù)載過重。
在2.6.0版之后，Linux開始支持NUMA(Non-Uniform Memory Access Architecture)體系結(jié)構(gòu)。進(jìn)行負(fù)載均衡時除了要考慮單個CPU的負(fù)載，還要考慮NUMA下各個節(jié)點(diǎn)的負(fù)載情況。
Linux的超線程調(diào)度借鑒NUMA的算法，將物理CPU當(dāng)作NUMA中的一個節(jié)點(diǎn)，并且將物理CPU中的邏輯CPU映射到該節(jié)點(diǎn)，通過運(yùn)行隊(duì)列中的node_nr_running屬性記錄當(dāng)前物理CPU的負(fù)載情況。
Linux通過balance_node( )函數(shù)進(jìn)行物理CPU之間的負(fù)載均衡。物理CPU間的負(fù)載平衡作為rebalance_tick( )函數(shù)中的一部分在 load_balance( )之前啟動，避免了出現(xiàn)一個物理CPU運(yùn)行1-1任務(wù)，而第二個物理CPU運(yùn)行0-0任務(wù)的情況。balance_node( )函數(shù)首先調(diào)用 find_
busiest_node( )找到系統(tǒng)中最繁忙的節(jié)點(diǎn)，然后在該節(jié)點(diǎn)和當(dāng)前CPU組成的CPU集合中進(jìn)行 load_balance( )，把最繁忙的物理CPU中的線程遷移到當(dāng)前CPU上。之后rebalance_tick( )函數(shù)再調(diào)用load_balance(工作集為當(dāng)前的物理CPU中的所有邏輯CPU)進(jìn)行邏輯CPU之間的負(fù)載均衡。
(3)支持“主動的”負(fù)載均衡
當(dāng)一個邏輯 CPU 變成空閑時，可能造成一個物理CPU的負(fù)載失衡。例如：系統(tǒng)中有兩個物理CPU，一個物理CPU上運(yùn)行一個任務(wù)并且剛剛結(jié)束，另一個物理CPU上正在運(yùn)行兩個任務(wù)，此時出現(xiàn)了一個物理CPU空閑而另一個物理CPU忙的現(xiàn)象。
評論