一種基于滑動窗口的多核數(shù)控系統(tǒng)任務調度策略

張麗鵬，于 東，胡 毅

1(中國科學院 沈陽計算技術研究所，沈陽 110168)

2(中國科學院大學，北京 100049)

3(沈陽高精數(shù)控智能技術股份有限公司，沈陽 110168)E-mail:lipzhang_hn@outlook.com

1 引 言

數(shù)控系統(tǒng)技術是機械制造和控制相結合的產(chǎn)物，是當今高端裝備制造業(yè)的核心技術之一.數(shù)控(numerical control，NC)機床特別是高檔數(shù)控機床是國際裝備制造業(yè)競爭的熱點領域[1].隨著計算機信息技術的發(fā)展，多核處理技術成為了新的趨勢，這對數(shù)控技術提出了新的要求.目前，基于嵌入式芯片的數(shù)控系統(tǒng)仍較多采用單核處理器平臺，在這種情況下，通過多核平臺來解決單核遇到的問題具有重要的現(xiàn)實意義.

同構多核處理器是采用多個相同結構的核心組成的芯片，每個核心的功能完全相同，地位完全相等，沒有層級之分[2].各個核心執(zhí)行相同或相似的任務，整個芯片作為一個統(tǒng)一的結構對外提供服務，以滿足提高性能、實現(xiàn)負載均衡的需求.

結合多核處理器系統(tǒng)結構的特征，文獻[3]針對嵌入式多核處理器資源有限特點，采用整數(shù)線性規(guī)劃方法對軟件流水中負載、通信與內(nèi)存開銷建立模型，提出了一種基于軟件流水的任務調度方法以實現(xiàn)負載均衡及通信、內(nèi)存開銷的優(yōu)化.文獻[4]將系統(tǒng)中的所有可用核分組，將共享高速緩存的多個核作為一個簇集，采用簇間獨立調度、簇內(nèi)統(tǒng)一調度的混合調度策略，并利用核間中斷信號來同步任務處理過程.文獻[5]以最小化任務集的執(zhí)行跨度為目標，提出一種基于改進蟻群算法的多核任務分配與調度算法.文獻[6]通過對粒子群算法適應度函數(shù)調整,提出一種基于粒子群算法的多核調度算法.文獻[7]提出一種種群均衡遺傳算法(BPGA)，將任務節(jié)點在處理器核上隨機分配而任務節(jié)點數(shù)均衡分配.上述文獻提出的任務調度策略具有一定的普適性，但算法實現(xiàn)的復雜性相對較高，實用性不強.

本文在以上研究成果的基礎上，以負載均衡性為目標，首先取合適的滑動窗口值，將待執(zhí)行的任務序列以滑動窗口大小進行分批處理.文末對比實驗表明了算法較好的滿足了系統(tǒng)的負載均衡并且有較好的執(zhí)行效率.

2 任務分配模型

2.1 相關理論

多核處理器上的任務分配與調度業(yè)已證明是NP-完全問題[8].通常的做法是使用啟發(fā)式算法或遺傳算法、模擬退火等優(yōu)化求解算法尋其近似解.文獻[9]提出RADG算法來消除迭代內(nèi)的數(shù)據(jù)依賴性，該算法通過重定時技術將周期相關的依賴任務圖轉換為一組獨立的任務.經(jīng)過算法處理后所有的任務在迭代內(nèi)都不存在數(shù)據(jù)依賴關系，這樣就對任務順序的調整提供了可能.本文以此理論研究為基礎，為實驗簡單，假定任務之間不存在數(shù)據(jù)依賴關系，提出基于滑動窗口的多核數(shù)控系統(tǒng)任務調度策略.

cpu負載是指在一段時間內(nèi)正在使用和等待使用cpu的平均任務數(shù),文獻[10]中采用一段時間間隔內(nèi)所有任務的執(zhí)行時間表示.本文引用并改進了這個思想，將cpu的負載表示為:

(1)

按照負載計算公式(1),時間間隔取本次任務分配完成的時間與上一次任務分配完成的時間之差,理想狀態(tài)下每個內(nèi)核的負載為0.7,本文實驗在同構4核心處理器上進行,因此可以認為當系統(tǒng)負載達到3以上時即為負載超標,應考慮適當降低滑動窗口大小提高系統(tǒng)吞吐量.

2.2 任務分配模型

圖1描述了任務分配過程,考慮在某一小段時間內(nèi),設同構多核處理器的核心數(shù)為m,記為C={c1,c2,…,cm}.待分配進程P中有n個線程任務,記為P={tr1,tr2,…,trn}，其中m>0,n>m.

圖1 任務分配模型

由于是同構處理器，同一任務在不同核心上的執(zhí)行時間認為是相同的，則每個任務在各相應核心上的執(zhí)行時間可以表示為T={t1,t2,…,tn}.取滑動窗口值為w，w<=n.則該滑動窗口內(nèi)任務在各相應核心上的執(zhí)行時間可表示為矩陣E，該矩陣有w/m行,m列.

令sum1,sum2,…,summ分別表示矩陣E中每一列的列和,則sum1,sum2,…,summ分別表示分配在核心1,2,…,m上的線程執(zhí)行完成所用時長.為使負載均衡，問題可轉化為尋求在m個核心上分配任務的策略，使得summax與summin差值最小.即:

min(summax-summin)

(2)

3 任務分配算法

3.1 算法思想

在任務執(zhí)行調度之前，首先進行任務序列的預處理，以系統(tǒng)的實時負載為依據(jù)采用大小合適的滑動窗口限制每輪任務的分配量，將滑動窗口中的任務隊列設為多核心訪問的公共資源.對任務隊列依序取滑動窗口大小的前兩份,記為首列和次列.首先對兩個任務隊列進行不同的預處理,過程為鏈式歸并排序過程的改進,排好序的首列基于優(yōu)先級由大到小、運行時間由大到小排列，而次列則基于優(yōu)先級由大到小、運行時間由小到大排列.基于此,在任務分配時分別選擇已排序的首列和次列的當前列表頭部的任務作為復合任務分配給輪到的核心.首次分配任務時的核心得到的復合任務將是優(yōu)先級最高執(zhí)行時間最長的任務與優(yōu)先級最高執(zhí)行時間最短的任務,下一個核心得到的任務將分別是任務隊列剩余任務中優(yōu)先級最高執(zhí)行時間最長的任務與優(yōu)先級最高執(zhí)行時間最短任務的復合,以此類推,直到本輪滑動窗口中的任務分配完畢,計算當前的系統(tǒng)負載,更新滑動窗口值.整體處理流程如圖2所示.

圖2 算法執(zhí)行流程圖

3.2 任務預處理

將任務隊列看作有序的結構，首先依次取任務隊列中前w個任務作為首列Task1,次列Task2.基于鏈式歸并排序過程的改進，分別對兩任務隊列進行排序,算法整體時間復雜度為O(nlogn),空間復雜度為O(1).

主要數(shù)據(jù)結構說明:

struct task_struct{

……

long etm;

long pro;

struct task_struct *next;

……

}

在數(shù)據(jù)結構task_struct中，屬性etm表示該任務執(zhí)行時間計數(shù)或運行時間片，pro表示任務運行優(yōu)先級數(shù),越大優(yōu)先級越高.

過程詳圖如圖3,流程中newHead表示該次迭代中需合并部分的后半部鏈表的頭部,內(nèi)部循環(huán)每次迭代中①處剪斷需要合并的前半段,②處剪斷需要合并的后半段,lastHead在合并前指向后半段開始的位置,合并后指向下一輪將要從哪個位置合并.

圖3 預處理算法執(zhí)行流程圖

過程merge()為合并兩個隊列的核心處理流程，實現(xiàn)對首列及隊列按照不同需求的分割，排序及合并.對原始隊列Task按照任務優(yōu)先級降序，運行時間降序排序.Task.pro、Task.etm分別代表任務的優(yōu)先級與執(zhí)行時長.對于次列Task2的處理流程于此基本一致,所不同的是需將流程merge()中循環(huán)體內(nèi)的條件“>”改為“<=”.如此得到的兩隊列即可進行任務的復合并進一步進行任務分配.過程見圖4.

圖4 歸并過程執(zhí)行流程圖

上述兩個過程完成了按滑動窗口值依次取任務task1，task2并已按照預設要求排序，是后續(xù)步驟的基礎.為使任務隊列在指定核心上分配，并使得分配任務后在滑動窗口內(nèi)所有任務在執(zhí)行期間每個處理器核心的負載相對均衡.需要繼續(xù)對上述得到的任務隊列進行任務的兩兩復合.在這里需要利用Linux系統(tǒng)在多核計算機上對處理器核心的親緣性，即綁定進行/線程到指定處理器核心上執(zhí)行，在本文中使用c語言頭文件sched.h中的sched_setaffinity系統(tǒng)調用的方式.對于復合后任務的執(zhí)行情況，默認情況是先執(zhí)行task.etm較大的.算法流程如圖5所示.

圖5 復合與分配任務算法流程圖

過程adjust_()計算處理器當前負載，據(jù)此動態(tài)調整滑動窗口值w,防止任務的阻塞,提高的系統(tǒng)實時吞吐量.

w值的確定借鑒了TCP中擁塞控制機制[11],采用慢開始和擁塞避免算法,開始時將w值設置為處理器核心數(shù)用以探測,隨之由小到大逐漸增大滑動窗口,即每經(jīng)過一輪處理,w值加倍.當系統(tǒng)的負載達到2時,采用擁塞避免機制,線性增大w值.當系統(tǒng)負載達到3時,重置w值為最小值.流程如圖6所示.

圖6 調整窗口值程序流程圖

4 實驗驗證與結果分析

實驗環(huán)境：飛凌公司研發(fā)的搭載i.MX6處理器的同構4核心ARM開發(fā)板,Linux版本號位3.05.如圖7所示.實驗采取隨機任務圖作為任務調度與分配的測試任務集.

圖7 多核ARM開發(fā)板

各次實驗中隨機生成八百萬任務數(shù)據(jù),進行多次實驗后隨機取5次實驗結果測得各個核心的負載百分比情況如表1所示.結果表明本文提出算法對于系統(tǒng)的負載均衡性測試有較好的實驗結果.

表1 各核心負載情況

對文獻[7]中提出的BPGA算法進行對比，設定處理器數(shù)為1，處理器核心數(shù)固定為4，雜交與變異概率分別仍為0.8、0.4，種群規(guī)模為100，算法最大迭代次數(shù)1000.隨機取10次實驗執(zhí)行時長對比,其結果如圖8所示,計算所取10次實驗結果的平均執(zhí)行效率較前者提高了11.96%.

圖8 執(zhí)行時間對比圖

分析原因可能在于種群規(guī)模與迭代次數(shù)過大的設置使算法收斂時間過長，為增加對比性，更改BPGA算法參數(shù)，設定種群規(guī)模為50，最大迭代次數(shù)800，其實驗對比結果如圖9.

圖9 執(zhí)行時間對比圖

計算所取10次隨機實驗結果的平均執(zhí)行效率,本文算法較前者提高了11.27%.主要原因在于BPGA算法在尋找最優(yōu)解時的頻繁迭代使得任務執(zhí)行時間較長.實驗結果表明，本文算法能夠較好的滿足多核系統(tǒng)處理器的負載均衡性，同時在執(zhí)行效率上有良好的表現(xiàn).

5 結束語

本文在前人研究的基礎上,針對同構多核數(shù)控系統(tǒng),研究并實現(xiàn)了多核任務調度算法,在任務預處理階段,采用滑動窗口動態(tài)調控任務序列大小以避免任務阻塞,在任務分配之前對任務隊列進行復制、排序并復合.最后實驗結果表明本文算法較好的滿足了負載的均衡性,同時又有較好的執(zhí)行效率.

本文存在的問題是任務數(shù)據(jù)為隨機生成,具有正態(tài)分布的特征，對于數(shù)據(jù)類別分布不穩(wěn)定、極端的任務集未能驗證.下一步將在實際生成環(huán)境中進行測試.