隨著計算機應用的日益普及，用戶對計算機的處理能力的需求也在成指數級增長。為了滿足用戶的需求，處理器生產廠商也采用了諸如超流水，分支預測，超標量，亂序執行，緩存等技術提高處理器的性能，但是這些技術的采用也增加了微處理器的復雜性，帶來了諸如材料，功耗，光刻，電磁兼容性等一系列問題。因此處理器設計人員開始尋找新的途徑來提高處理器的性能。Intel公司於2002年底推出了超線程技術，通過共享處理器的執行資源，提高CPU的利用率，讓處理單元獲得更高的吞吐量。
2 超線程技術背景
傳統的處理器內部存在著多種並行操作方式。①ILP(Instruction Level Paramllelism,指令級並行)：既同時執行幾條指令，單CPU就能完成。但是傳統的單CPU處理器只能同時執行一個線程，很難保證CPU資源得到100%的利用，性能提高只能通過提升時鐘頻率和改進架構。②TLP（Thread Level Paramllesim，線程級並行）：可以同時執行多個線程，但是需要多處理器系統的支持，通過增加CPU的數量來提高性能。
超線程微處理器將SMT（Simultaneous Multi-Threading,同時多線程技術）引入Intel體系結構，支持超線程技術的操作系統將一個物理處理器視為兩個邏輯處理器，並且為每個邏輯處理器分配一個線程運行。物理處理器在兩個邏輯處理器之間分配高速緩存，執行單元，總線等執行資源，讓暫時閒置的運算單元去執行其它的線程代碼，從而最大限度的提升CPU資源的利用率。
Superscalar粗粒度多線程細粒度，細粒度多線程以及同時多線程的執行時空圖的比較。不同顏色表示不同程序的指令，白色表示空閒，同一橫行中的指令在同一時刻執行。我們可以看出的同時多線程的系統利用率最高,系統的吞吐量也最高。
Intel 超線程技術通過復制、劃分、共享Intel的Netburst微架構的資源讓一個物理CPU中具有兩個邏輯CPU。（1）復制的資源：每個邏輯CPU都維持了一套完整的體系結構狀態，包括通用寄存器，控制寄存器，高級可編程寄存器（APIC），以及一些機器狀態寄存器，體系結構狀態對程序或線程流進行跟蹤，從軟件的角度，一旦體系結構狀態被復制了，就可以將一個物理CPU視為兩個邏輯CPU。（2）劃分的資源：包括重定序（re-order)緩沖，Load/Store緩沖，隊列等 。劃分的資源在多任務模式總分給兩個邏輯CPU使用，在單任務模式時合並起來給一個邏輯CPU使用。（3）共享的資源：包括cache，執行單元等，邏輯CPU共享物理CPU的執行單元進行加，減，取數等操作。
在線程調度時，體系結構狀態對程序或線程流進行跟蹤，各項工作（包括加、乘、加載等）由執行資源（處理器上的單元）負責完成。每個邏輯處理器可以單獨對中斷做出響應。第一個邏輯處理器可以跟蹤一個線程，同時第二個邏輯處理器跟蹤另一個線程。例如，當一個邏輯處理器在執行浮點運算時，另一個邏輯處理器可以執行加法運算和加載操作。
對於擁有超線程技術的CPU可以同時執行處理兩個線程，它可以將來自兩個線程的指令同時發送到處理器內核執行，處理器內核采用亂序指令調度並發執行兩個線程，以確保其執行單元在各時鐘周期均處於運行狀態。傳統的雙處理器系統，每個處理器有一套獨立的體系結構狀態和處理器執行資源。每個處理器上只能同時執行一個線程。支持超線程的雙處理器系統，每個處理器有兩套獨立體系結構狀態，可以獨立的響應中斷。
3 Linux超線程感知調度優化
Linux從2.4.17開始支持超線程技術，傳統的Linux O(1)調度器不能區分物理CPU和邏輯CPU，因此不能充分利用超線程處理器的特性。Ingo Monlar編寫了“HT-aware scheduler patch”，針對超線程技術對O(1)調度器進行了調度算法優化，首先優先安排線程在空閒的物理CPU的邏輯CPU上運行，避免資源競爭帶來的性能下降，並且在線程調度時考慮到了在兩個邏輯CPU之間進行線程遷移的開銷遠遠小於物理CPU之間的遷移開銷以及邏輯CPU共享cache等資源的特性。這些優化的相關算法被Linux的後期版本吸收，具體如下：
（1）共享運行隊列
在SMP (Symmetrical Multi-Processing，對稱多處理)環境中，O(1)調度器為每個CPU分配了一個運行隊列，避免了多CPU共用一個運行隊列帶來的資源競爭。Linux會將超線程CPU中的兩個邏輯CPU視為SMP的兩個獨立CPU,各維持一個運行隊列，但是這兩個邏輯CPU共享cache等資源，沒有體現超線程CPU的特性，因此引入了共享運行隊列的概念。HT-aware scheduler patch在運行隊列struct runqueue結構中增加了nr_cpu和cpu兩個屬性，nr_cpu記錄物理CPU中的邏輯CPU的數目，cpu則指向同屬CPU（同一個物理CPU上的另一個邏輯CPU）的運行隊列。
在Linux中通過調用sched_map_runqueue( )函數實現兩個邏輯CPU的運行隊列的合並，sched_map_runqueue( )首先會查詢系統的CPU隊列，通過phys_proc_id(記錄邏輯CPU所屬的物理CPU的ID)判斷當前CPU的同屬邏輯CPU，如果找到同屬邏輯CPU，則將當前CPU運行隊列的cpu屬性指向同屬邏輯 CPU的運行隊列。
（2）支持“被動的”負載均衡
用中斷驅動的均衡操作必須針對各個物理 CPU，而不是各個邏輯 CPU。否則可能會發生：一個物理 CPU 運行兩個任務，而另一個物理 CPU 不運行任務；現有的調度程序不會將這種情形認為是“失衡的”。在調度程序看來，似乎是第一個物理處理器上的兩個 CPU 運行 1-1 任務，而第二個物理處理器上的兩個 CPU 運行 0-0 任務。
在2.6.0之前，Linux只有通過load_balance( )函數進行CPU之間負載均衡，當某個CPU負載過輕而另一個CPU負載較重時，系統會調用load_balance( )函數從重載CPU上遷移線程到負載較輕的CPU上，只有系統最繁忙的CPU的負載超過當前CPU負載的 25% 時才進行負載平衡。找到最繁忙的CPU（源CPU）之後，確定需要遷移的線程數為源CPU負載與本CPU負載之差的一半,然後按照從 expired 隊列到 active 隊列、從低優先級線程到高優先級線程的順序進行遷移。
在超線程系統中進行負載均衡時，如果也是將邏輯CPU等同於SMP環境中的單個CPU進行調度，這樣可能會出現將線程遷移到同一個物理CPU的兩個邏輯CPU上，從而導致物理CPU的負載過重。
2.6.0之後Linux開始支持NUMA(Non-Uniform Memory Access Architecture)體系結構。進行負載均衡時除了考慮單個CPU的負載 ，還考慮了 NUMA 下各個節點的負載情況。
Linux的超線程調度借鑒NUMA的算法，將物理CPU當作NUMA中的一個節點，並且將物理CPU中的邏輯CPU映射到該節點，通過運行隊列中的node_nr_running屬性記錄當前物理CPU的負載情況。
Linux實現了balance_node( )函數進行物理CPU之間的負載均衡。物理CPU間的負載平衡作為 rebalance_tick() 函數中的一部分在 load_balance( ) 之前啟動，避免出現一個物理CPU 運行 1-1 任務，而第二個物理處理器上的運行 0-0 任務情況。balance_node( ) 先調用 find_busiest_node( ) 找到系統中最繁忙的節點，然後在該節點和當前 CPU 組成的 CPU集合中進行 load_balance( )，把最繁忙的物理CPU中的線程遷移到當前CPU上。然後rebalance_tick( )函數再調用load_balance（工作集為當前的物理CPU中的所有邏輯CPU）進行一次邏輯CPU之間的負載均衡。
（3）支持“主動的”負載均衡
當一個邏輯 CPU 變成空閒，可能造成一個物理 CPU 的負載失衡。例如：系統中有兩個物理CPU，一個物理CPU上運行一個任務並且剛剛結束，另一個物理CPU上正在運行兩個任務，此時出現了一個物理CPU空閒而另一個物理CPU忙的現象。
Linux中通過active_load_balance( )函數進行主動的負載均衡，active_load_balance( )函數用於在所有的邏輯CPU中查詢該CPU的忙閒情況，如果發現由於超線程引起的負載不平衡（一個物理CPU的兩個邏輯CPU都空閒，另一個物理CPU的兩個邏輯CPU都在運行兩個線程），則喚醒一個需要遷移的線程，將它從一個忙的物理CPU遷移到一個空閒的物理CPU上。
active_load_balance( )通過調用cpu_rq( )函數得到每一個邏輯CPU上的運行隊列。如果運行隊列上的當前運行線程為idle線程則說明當前邏輯CPU為空閒，如果發現一個物理CPU兩個邏輯CPU都為空閒，而另一個物理CPU中的兩個邏輯CPU的運行隊列為繁忙的情況，則說明存在超線程引起的負載不均衡。這時當前CPU會喚醒遷移服務線程（migration_thread）來完成負載均衡的線程遷移。
（4）支持超線程感知的任務挑選
在超線程處理器中由於cache資源為兩個邏輯處理器共享，因此調度器在選取一個新任務時，必須確保同組的任務盡量共享一個物理CPU，從而減少cache 失效的開銷，提高系統的性能，而傳統的調度器只是簡單地為邏輯CPU選取一個任務，沒有考慮物理CPU的影響。
Linux進行線程切換時會調用schedule( )函數進行具體的操作，如果沒有找到合適的任務schedule（）函數則會調度idle線程在當前CPU上運行，在超線程環境中Linux調度idle線程運行之前會查詢其同屬CPU的忙閒狀況，如果同屬CPU上有等待運行的線程則會調用一次load_balance( )函數在兩個同屬CPU之間作一次負載均衡，將等待運行的線程遷移到當前CPU上，保證優先運行同屬CPU上的任務。
（5）支持超線程感知的CPU喚醒
傳統的調度器只知道當前CPU，而不知道同屬的邏輯CPU，在超線程環境下，一個邏輯 CPU 正在執行任務，其上的一個線程被喚醒了 ，但它的同屬邏輯CPU是空閒的，則應該在同屬邏輯CPU上運行剛剛喚醒的任務。
Linux通過wake_up_cpu( )函數來實現CPU喚醒，在try_to_wakeup,pull_task,move_task_away加入了wake_up_cpu( )函數的相應調用點。wake_up_cpu（）首先查詢當前CPU是不是空閒的，如果當前CPU為空閒，則調用resched_cpu( )函數啟動調度器，將喚醒的線程調度上當前CPU執行 。如果當前CPU不是空閒，則查找其同屬邏輯CPU，如果同屬邏輯CPU是空閒的，則將喚醒的線程調度上同屬邏輯CPU上執行。如果同屬邏輯CPU也不為空閒，則再比較喚醒的線程和當前CPU上運行的線程的優先級，如果喚醒的線程的優先級高，或者優先級相等但是時間片多，則進行線程切換，在當前CPU上調度執行喚醒的線程。如果上述條件都不滿足，最後比較喚醒的線程和當前CPU的同屬邏輯CPU上運行的線程的優先級，如果喚醒的線程的優先級高，或者優先級相等但是時間片多，則在同屬邏輯CPU上調度喚醒的線程
4 性能測試
Linux-2.6.0 HT-aware scheduler patch實現了上述的超線程調度優化，這裡根據linux-2.6.0 HT-aware scheduler patch對這幾種調度優化進行了性能測試。
測試硬件環境：Xeon 2.2G處理器（支持超線程）×4，2G SDRAM內存。
Benchmark：(1) volanomark是一個純java的benchmark，專門用於測試系統調度器和線程環境的綜合性能，它建立一個模擬Client/Server方式的Java聊天室，通過獲取每秒平均發送的消息數來評測宿主機綜合性能（數值越大性能越好）。Volanomark測試與Java虛擬機平台相關，本文使用Sun Java SDK 1.4.2作為測試用Java平台，Volanomark版本2.5.0.9。(2) LMBench： 是一個用於評價系統綜合性能的多平台開源benchmark，,我們對其進行了修改實現了 lat_thread_ctx接口,用來測試線程的切換開銷。
表4表明開啟超線程後volanomark在Linux-2.6.0平台下平均吞吐量提高了25.5％。由於Linux的O(1)內核調度器實現比較好的SMP負載均衡算法，所以在超線程環境下整個系統的性能也有比較好的提升。
Linux在進行了超線程調度優化後，在支持超線程的平台上的獲得的性能加速比。在Linux-2.6.0加入HT-aware scheduler patch後volanomark的平均吞吐提高了 8.5％，分別實現支持主動負載均衡，被動的負載均衡，CPU喚醒和任務挑選的相關代碼後，吞吐量分別提高了1.8.%,.2.5%,2.3%和2.1％。
我們使用Lmbench創建了10~150個線程,測試在不同的負載條件下線程的切換開銷。表一的數據顯示HT-aware scheduler patch可以將線程的切換開銷減少3%～7%。數據顯示在輕負載情況下，系統可以獲得更多的加速比。因為被動的負載均衡以及主動的負載均衡只有在系統有CPU空閒時才能發揮比較好的作用。
表一：線程切換開銷
5 相關工作和展望
采用支持超線程技術的Linux可以獲得較大的性能提升。但是其調度算法還要根據實際的應用進一步研究。在文獻[7]中，提出“Symbiosis”概念用來衡量多個線程在SMT環境中同時執行的有效性。在文獻[8]中提出了線程敏感的調度算法，用一組硬件性能計數器計算在兩個邏輯CPU上運行不同作業子集的執行信息，利用這些信息來預測不同作業子集的執行性能，並選擇具有最好預測性能的作業子集調度上同一個物理CPU執行。文獻[9]中主要研究適合SMT 結構並考慮作業優先級的調度器。研究結果表明，這些調度算法能有效提高超線程系統的性能。
Intel的超線程技術是其企業產品線中的重要特征，並將會集成到越來越多的產品中，它標志著Intel微處理器一個新的時代：從指令級並行到線程級並行，這樣使微處理器運行模式與多線程應用的運行模式更加接近，應用程序可以充分利用線程級和指令級並行進行優化。隨著超線程處理器的發展可能會出現操作系統使用處理器系統中硬件性能監視器估算系統在某一個時間段的某些性能指標，然後利用這些性能指標來指導線程的調度策略。(T005)
