摘 要：針對現(xiàn)存任務(wù)調(diào)度算法優(yōu)先級選取過于單一、冗余任務(wù)處理較晚的問題，提出一種基于加權(quán)優(yōu)先級的任務(wù)調(diào)度算法-WPTS算法。該算法綜合考慮任務(wù)3個屬性的加權(quán)值以決定任務(wù)被處理的先后次序，從而克服了任務(wù)選取時的單一性問題。在將任務(wù)分配到處理器的過程中，保證任務(wù)優(yōu)先調(diào)度到完成時間最早的處理器上。同時，引入冗余任務(wù)處理過程，及時消除冗余任務(wù)，達(dá)到對處理器空閑時間段進(jìn)行有效回收、減少處理器調(diào)度長度的效果。性能對比實驗表明，WPTS算法較CPFD算法、HCPFD算法和HDEFT算法能取得更好的性能。

0 引 言

異構(gòu)多核處理器以其芯片面積利用率高、處理器功耗低、應(yīng)用程序的并行化程度高等諸多優(yōu)勢成為處理器體系結(jié)構(gòu)發(fā)展的一個重要方向，同時它的出現(xiàn)給計算機學(xué)科發(fā)展帶來了新的挑戰(zhàn)。研究發(fā)現(xiàn)多核處理器任務(wù)調(diào)度的優(yōu)劣對處理器的執(zhí)行時間、任務(wù)調(diào)度長度、處理器的功耗等諸多性能產(chǎn)生直接影響。因此，多核處理器的任務(wù)調(diào)度作為影響操作系統(tǒng)性能的重要因素成為近年來系統(tǒng)結(jié)構(gòu)方向的熱點研究問題之一。當(dāng)前對異構(gòu)多核處理器上任務(wù)調(diào)度的研究很少考慮任務(wù)優(yōu)先級的選取對調(diào)度結(jié)果的影響以及使用復(fù)制技術(shù)的任務(wù)調(diào)度算法會產(chǎn)生冗余任務(wù)的問題。

本文深入分析了CPFD、HCPFD和HDEFT這3種最具有代表性的任務(wù)調(diào)度算法，并在總結(jié)目前任務(wù)調(diào)度算法存在的缺點基礎(chǔ)上，根據(jù)異構(gòu)多核處理器系統(tǒng)結(jié)構(gòu)的特點，設(shè)計了基于加權(quán)優(yōu)先級的任務(wù)調(diào)度算法（weighted prioritytask scheduling,WPTS），算法以3個參數(shù)構(gòu)成的加權(quán)值作為任務(wù)的優(yōu)先級，將任務(wù)排序構(gòu)成任務(wù)調(diào)度列表，然后依次將任務(wù)映射到處理器上，并在映射過程中對任務(wù)進(jìn)行優(yōu)化處理，最后通過預(yù)先設(shè)定的性能評價參數(shù)對算法進(jìn)行實驗驗證。本研究能有效改善原有任務(wù)調(diào)度算法的不足，提升了多核處理器在實際應(yīng)用中的性能，對異構(gòu)多核處理器上靜態(tài)任務(wù)調(diào)度技術(shù)的發(fā)展具有重大理論和現(xiàn)實意義。

1 WPTS算法設(shè)計

1.1 3種現(xiàn)有高效算法的分析

目前基于異構(gòu)多核處理器取得較好調(diào)度性能的算法有CPFD算法、HCPFD算法和HDEFT算法。CPFD算法使用任務(wù)節(jié)點到入口節(jié)點的最長路徑b-level作為任務(wù)調(diào)度的優(yōu)先級，將任務(wù)調(diào)度到具有最早完成時間的處理器上，其時間復(fù)雜度是O （v4），v是DAG圖中任務(wù)節(jié)點的數(shù)目。

HCPFD算法以關(guān)鍵任務(wù)和任務(wù)的最晚開始時間劃分任務(wù)的優(yōu)先級，將任務(wù)分配到使其完成時間最早的處理器節(jié)點上，在任務(wù)到處理器的映射階段優(yōu)先考慮使用處理器上的空閑時間段來處理任務(wù)，其時間復(fù)雜度為O （pv2），p是任務(wù)調(diào)度中處理器的總個數(shù)。HDEFT算法在任務(wù)分配階段采用sumu （vi）作為任務(wù)優(yōu)先級，在任務(wù)到處理器的映射階段使用任務(wù)插入和復(fù)制技術(shù)，其時間復(fù)雜度為O （pv2）。