Linux超線程感知的調(diào)度算法研究
加入技術(shù)交流群
Linux中通過active_load_balance( )函數(shù)進(jìn)行主動的負(fù)載均衡，active_load_balance( )函數(shù)用于在所有的邏輯CPU中查詢該CPU的忙閑情況。如果發(fā)現(xiàn)由于超線程引起的負(fù)載不平衡(一個物理CPU的兩個邏輯CPU都空閑，另一個物理CPU的兩個邏輯CPU都在運(yùn)行兩個線程)，則喚醒一個需要遷移的線程，將它從一個忙的物理CPU遷移到一個空閑的物理CPU上。
active_load_balance( )通過調(diào)用cpu_rq( )函數(shù)得到每一個邏輯CPU上的運(yùn)行隊(duì)列。如果運(yùn)行隊(duì)列上的當(dāng)前運(yùn)行線程為idle線程，則說明當(dāng)前邏輯CPU為空閑；如果發(fā)現(xiàn)一個物理CPU兩個邏輯CPU都為空閑，而另一個物理CPU中的兩個邏輯CPU的運(yùn)行隊(duì)列為繁忙的情況，則說明存在超線程引起的負(fù)載不均衡。這時當(dāng)前CPU會喚醒遷移服務(wù)線程(migration_thread)來完成負(fù)載均衡的線程遷移。
(4)支持超線程感知的任務(wù)挑選
在超線程處理器中，由于cache資源為兩個邏輯處理器共享，因此調(diào)度器在選取一個新任務(wù)時，必須確保同組的任務(wù)盡量共享一個物理CPU，從而減少cache失效的開銷，提高系統(tǒng)的性能。而傳統(tǒng)的調(diào)度器只是簡單地為邏輯CPU選取一個任務(wù)，沒有考慮物理CPU的影響。
Linux進(jìn)行線程切換時會調(diào)用schedule( )函數(shù)進(jìn)行具體的操作。如果沒有找到合適的任務(wù)schedule()函數(shù)，則會調(diào)度idle線程在當(dāng)前CPU上運(yùn)行。在超線程環(huán)境中Linux調(diào)度idle線程運(yùn)行之前會查詢其同屬CPU的忙閑狀況。如果同屬CPU上有等待運(yùn)行的線程，則會調(diào)用一次load_balance( )函數(shù)在兩個同屬CPU之間作一次負(fù)載均衡，將等待運(yùn)行的線程遷移到當(dāng)前CPU上，保證優(yōu)先運(yùn)行同屬CPU上的任務(wù)。
(5)支持超線程感知的CPU喚醒
傳統(tǒng)的調(diào)度器只知道當(dāng)前CPU，而不知道同屬的邏輯CPU。在超線程環(huán)境下，一個邏輯CPU正在執(zhí)行任務(wù)時，其上的一個線程被喚醒了，此時，如果它的同屬邏輯CPU是空閑的，則應(yīng)該在同屬邏輯CPU上運(yùn)行剛剛喚醒的任務(wù)。
Linux通過wake_up_cpu( )函數(shù)實(shí)現(xiàn)CPU喚醒，在try_o_wakeup、pull_task、move_task_away加入了wake_up_cpu( )函數(shù)的相應(yīng)調(diào)用點(diǎn)。wake_up_cpu()首先查詢當(dāng)前CPU是不是空閑的，如果當(dāng)前CPU為空閑，則調(diào)用resched_cpu( )函數(shù)啟動調(diào)度器，將喚醒的線程調(diào)度到當(dāng)前CPU執(zhí)行；否則查找其同屬邏輯CPU。如果同屬邏輯CPU是空閑的，則將喚醒的線程調(diào)度到同屬邏輯CPU上執(zhí)行；否則比較喚醒的線程和當(dāng)前CPU上運(yùn)行的線程的優(yōu)先級。如果喚醒的線程的優(yōu)先級高，或者優(yōu)先級相等但是時間片多，則進(jìn)行線程切換，在當(dāng)前CPU上調(diào)度執(zhí)行喚醒的線程。如果上述條件都不滿足，最后比較喚醒的線程和當(dāng)前CPU的同屬邏輯CPU上運(yùn)行的線程的優(yōu)先級，如果喚醒的線程的優(yōu)先級高，或者優(yōu)先級相等但是時間片多，則在同屬邏輯CPU上調(diào)度執(zhí)行喚醒的線程。
3 性能測試
Linux-2.6.0 HT-aware scheduler patch實(shí)現(xiàn)了上述超線程調(diào)度優(yōu)化。這里根據(jù)linux-2.6.0 HT-aware scheduler patch對這幾種調(diào)度優(yōu)化進(jìn)行了性能測試。
測試硬件環(huán)境：Xeon 2.2GHz處理器(支持超線程)×4，2GB SDRAM內(nèi)存。
Benchmark：(1)Volanomark是一個純Java的benchmark，專門用于測試系統(tǒng)調(diào)度器和線程環(huán)境的綜合性能。它建立一個模擬Client/Server方式的Java聊天室，通過獲取每秒平均發(fā)送的消息數(shù)來評測宿主機(jī)綜合性能(數(shù)值越大性能越好)。Volanomark測試與Java虛擬機(jī)平臺相關(guān)，本文使用Sun Java SDK 1.4.2作為測試用Java平臺，Volanomark版本2.5.0.9。(2)LMBench是一個用于評價系統(tǒng)綜合性能的多平臺開源benchmark，對其進(jìn)行修改后實(shí)現(xiàn)了lat_thread_ctx接口，用來測試線程的切換開銷。
圖4表明開啟超線程后Volanomark在Linux-2.6.0平臺下平均吞吐量提高了25.5％。由于Linux的O(1)內(nèi)核調(diào)度器比較好地實(shí)現(xiàn)了SMP負(fù)載均衡算法，所以在超線程環(huán)境下整個系統(tǒng)的性能也有了比較好的提升。
圖5顯示出Linux在進(jìn)行了超線程調(diào)度優(yōu)化后，在支持超線程的平臺上所獲得的性能加速比。在Linux-2.6.0加入HT-aware scheduler patch后Volanomark的平均吞吐提高了 8.5％，分別實(shí)現(xiàn)主動負(fù)載均衡、被動的負(fù)載均衡、CPU喚醒和任務(wù)挑選的相關(guān)代碼后，吞吐量分別提高了1.8.%、2.5%、2.3%和2.1％。本文引用地址：http://m.butianyuan.cn/article/202629.htm
使用Lmbench創(chuàng)建10~150個線程，在不同的負(fù)載條件下測試線程的切換開銷。表1的數(shù)據(jù)顯示HT-aware scheduler patch可以將線程的切換開銷減少3%～7%。數(shù)據(jù)顯示：在輕負(fù)載情況下，系統(tǒng)可以獲得更多的加速比。這是因?yàn)楸粍拥呢?fù)載均衡以及主動的負(fù)載均衡只有在系統(tǒng)有CPU空閑時才能發(fā)揮比較好的作用。
4 相關(guān)工作和展望
采用支持超線程技術(shù)的Linux可以獲得較大的性能提升。但是其調(diào)度算法還要根據(jù)實(shí)際的應(yīng)用進(jìn)一步研究。參考文獻(xiàn)[7]中提出了用“Symbiosis”概念來衡量多個線程在SMT環(huán)境中同時執(zhí)行的有效性。參考文獻(xiàn)[8]中提出了線程敏感的調(diào)度算法，用一組硬件性能計數(shù)器計算兩個邏輯CPU上運(yùn)行不同作業(yè)子集的執(zhí)行信息，利用這些信息來預(yù)測不同作業(yè)子集的執(zhí)行性能，并選擇具有最好預(yù)測性能的作業(yè)子集調(diào)度同一個物理CPU執(zhí)行。參考文獻(xiàn)[9]中主要研究了適合SMT 結(jié)構(gòu)并考慮作業(yè)優(yōu)先級的調(diào)度器。研究結(jié)果表明，這些調(diào)度算法能有效地提高超線程系統(tǒng)的性能。
Intel的超線程技術(shù)是其企業(yè)產(chǎn)品線中的重要特征，并將會集成到越來越多的產(chǎn)品中，它標(biāo)志著Intel微處理器一個新的時代：從指令級并行到線程級并行，這樣可使微處理器運(yùn)行模式與多線程應(yīng)用的運(yùn)行模式更加接近，應(yīng)用程序可以充分利用線程級并行和指令級并行進(jìn)行優(yōu)化。隨著超線程處理器的發(fā)展，可能會出現(xiàn)操作系統(tǒng)使用處理器系統(tǒng)中硬件性能監(jiān)視器估算系統(tǒng)在某一時間段的某些性能指標(biāo)，然后利用這些性能指標(biāo)來指導(dǎo)線程的調(diào)度策略。
評論