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