Linux超線程感知的調度算法研究
加入技術交流群
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_o_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上調度執行喚醒的線程。
3 性能測試
Linux-2.6.0 HT-aware scheduler patch實現了上述超線程調度優化。這里根據linux-2.6.0 HT-aware scheduler patch對這幾種調度優化進行了性能測試。
測試硬件環境：Xeon 2.2GHz處理器(支持超線程)×4，2GB 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負載均衡算法，所以在超線程環境下整個系統的性能也有了比較好的提升。
圖5顯示出Linux在進行了超線程調度優化后，在支持超線程的平臺上所獲得的性能加速比。在Linux-2.6.0加入HT-aware scheduler patch后Volanomark的平均吞吐提高了 8.5％，分別實現主動負載均衡、被動的負載均衡、CPU喚醒和任務挑選的相關代碼后，吞吐量分別提高了1.8.%、2.5%、2.3%和2.1％。本文引用地址：http://www.104case.com/article/202629.htm
使用Lmbench創建10~150個線程，在不同的負載條件下測試線程的切換開銷。表1的數據顯示HT-aware scheduler patch可以將線程的切換開銷減少3%～7%。數據顯示：在輕負載情況下，系統可以獲得更多的加速比。這是因為被動的負載均衡以及主動的負載均衡只有在系統有CPU空閑時才能發揮比較好的作用。
4 相關工作和展望
采用支持超線程技術的Linux可以獲得較大的性能提升。但是其調度算法還要根據實際的應用進一步研究。參考文獻[7]中提出了用“Symbiosis”概念來衡量多個線程在SMT環境中同時執行的有效性。參考文獻[8]中提出了線程敏感的調度算法，用一組硬件性能計數器計算兩個邏輯CPU上運行不同作業子集的執行信息，利用這些信息來預測不同作業子集的執行性能，并選擇具有最好預測性能的作業子集調度同一個物理CPU執行。參考文獻[9]中主要研究了適合SMT 結構并考慮作業優先級的調度器。研究結果表明，這些調度算法能有效地提高超線程系統的性能。
Intel的超線程技術是其企業產品線中的重要特征，并將會集成到越來越多的產品中，它標志著Intel微處理器一個新的時代：從指令級并行到線程級并行，這樣可使微處理器運行模式與多線程應用的運行模式更加接近，應用程序可以充分利用線程級并行和指令級并行進行優化。隨著超線程處理器的發展，可能會出現操作系統使用處理器系統中硬件性能監視器估算系統在某一時間段的某些性能指標，然后利用這些性能指標來指導線程的調度策略。
評論