自適應調度是指在滿足不同工作方式相對優先權的條件下，在設計範圍內，同時實時地平衡各種波束請求所要求的時間、能量和計算機資源，為一個調度間隔選擇一個最佳任務序列的一種調度方法。這種調度策略能夠與動態的環境相適應，與規定的不同工作方式優先權相適應，與可用的時間、能量和計算機資源量相適應。針對多任務或者多功能雷達，自適應調度策略被認為是最靈活最有效的調度策略。
基本介紹
- 中文名：自適應調度
- 外文名：adaptive scheduling
- 簡介：選擇一個最佳任務序列的調度方法
- 優點：能夠與動態的環境相適應
- 重要性：最靈活最有效的調度策略
- 套用學科：計算機科學、電器工程、通信工程
簡介,調度原則,影響調度的因素,調度間隔的選擇,相對優先權確定,調度策略的選擇,資源約束條件,自適應調度算法,選擇最優計算模組策略,性能模型,執行時間T的計算,工作負載模型,請求序列,調度性能評估指標,
簡介
自適應調度是指在滿足不同工作方式相對優先權的條件下，在設計範圍內，同時實時地平衡各種波束請求所要求的時間、能量和計算機資源，為一個調度間隔選擇一個最佳任務序列的一種調度方法。這種調度策略能夠與動態的環境相適應，與規定的不同工作方式優先權相適應，與可用的時間、能量和計算機資源量相適應。針對多任務或者多功能雷達，自適應調度策略被認為是最靈活最有效的調度策略。
調度原則
在具體設計一種任務調度算法時應遵循以下三個原則：
( 1 )優先權原則：當申請調度的駐留任務中出現多個任務競爭同一個時間段時，優先調度相對優先權較高的駐留任務。優先權原則保證在雷達資源無法滿足所有請求時，將可用資源分配給相對優先權較高的任務，如果優先權較低的任務不能在某個合理的周期內被調度時，則要延時或是放棄這些任務。
(2) 時間利用原則：
( 3 )期望時間原則：
式中dti為任務期望執行時刻，sti為任務實際執行時刻。期望時間原則要求雷達波束請求的實際執行時刻儘可能靠近其期望執行時刻。一般情況下，調度算法應首先滿足優先權原則，其次是時間利用原則和期望時間原則，也可根據側重點不同而有所調整。
影響調度的因素
在設計自適應調度算法時，調度間隔的選擇、工作方式優先權的劃分、調度策略的選擇和雷達資源約束條件的實現是需要考慮的四個關鍵問題，這四個因素將直接影響調度算法的性能。
調度間隔的選擇
調度間隔(Schedule Interval ，SI)的含義為雷達系統調用調度程式的時間間隔，它是整個雷達電腦程式體系結構的基礎，決定了雷達控制迴路中的主要子程式的執行頻率。雷達控制器與雷達天線每隔一個調度間隔交換一次數據。若是調度間隔選擇過長，則無法滿足雷達系統對某些工作方式時間緊迫性要求；若是調度間隔選擇過短，則會額外增加雷達系統計算機的支援程式和內部處理程式的開銷和負載。因此，調度間隔必須合理設定。
為保證所有任務能夠得到正常執行，調度間隔長度必須小於最小任務執行周期的四分之一。同時，考慮到在一個調度間隔內雷達控制器需要進行雷達回波處理和駐留任務調度處理，因此，調度間隔長度必須大於最惡劣情況下支持調度和數據處理所需要的總時間。實際選取的調度間隔只要在上述範圍內，就認為是合理的。
相對優先權確定
在任務調度過程中，有可能出現多種任務請求競爭同一個執行時間段的情況，此時，調度算法必須決定哪些任務被調度，哪些任務被延遲或是刪除。任務的相對優先權為調度算法提供了決策的依據。
任務的相對優先權由任務重要性和時間緊迫性兩個要素決定。任務重要性通常用任務工作方式優先權表示，而任務的時間緊迫性則是從任務期望發射時間角度對任務進行衡量。Huizing等人提出了時間窗的概念，其具體含義是指雷達任務請求的實際執行時間可以在其期望執行時間前後能夠移動的有效範圍。這使得駐留任務的實際執行時刻不一定與其期望執行時刻相等。一旦雷達任務的時間窗給定後，便可以得到各駐留任務的最早和最晚可執行時刻(截止期)。在所有申請調度執行的任務中，最晚可執行時間與當前調度間隔起始時刻越近，則說明該任務的時間緊迫性越高。此時，時間緊迫性高的任務相對優先權應提高，以便儘快得到調度。
調度策略的選擇
調度策略可進分固定模板、多模板和部分模板法。
固定模板法是最為簡單的一種調度方法。在這種調度方法中，只需要為雷達申請任務預先分配一個固定的調度間隔，用於一組固定組合的雷達任務的調度。固定模板法設計和分析簡單，不需要實時地對雷達任務排序，占用系統資源較少。但是由於模板的固定性，這種調度策略只適用於特定的目標環境，它缺乏靈活性和自適應能力，不利於波形和能量的調整，因此，不可能適用於多樣化的動態環境。這種設計方法只能供單一用途或單一功能的雷達使用。
多模板設計法是固定模板設計方法的一種簡單推廣，相較於前者，它的靈活性和自適應能力有所提高。這種方法中首先需要根據相應的操作環境設計好多個固定的模板，模版的數目是由操作環境的多樣性、期望的操作效率和選擇邏輯的複雜程度決定的。在實時調度時，將根據一定的準則及相應的環境來選擇最適合的模板。多模板方法設計和分析相對簡單，所用系統資源較少，但它也存在著效率低、不利於波形和能量調整等缺點，因此，該方法僅適合於對目標環境和操作環境具有先驗知識的雷達使用。
部分模板法在每個調度間隔內事先安排好一個或多個任務，以維持某個最小程度的操作，該調度間隔內剩餘的時間可用來安排執行緊急任務或是滿足設備約束條件的其它類型的任務。部分模板設計方法較前兩種方法使得雷達的利用效率有所提高，同時，它對環境有著一定程度的靈活性和適應性，可用於多功能和多用途雷達，但是由於其設計和分析的困難，它還是常用於有限功能的雷達。
資源約束條件
雷達每一種工作方式的實現都是通過發射波束駐留實現的，均會消耗一定的雷達資源，而雷達系統所擁有的資源是有限的，因此，設計調度算法時必須綜合考慮各種資源的約束。調度中主要考慮三大資源約束：
( 1 )時間資源約束：一旦調度時間間隔確定之後，在其中可能安排的雷達任務是有限的。任何一個雷達任務的發生，都要求雷達有相應的動作時間，所有安排執行的雷達任務必須在它們的截止期之前完成，同時它們不會出現競爭同一個執行時間段的現象。
( 2 )能量資源約束：如同時間約束一樣，任何一個雷達任務的發生，都要求雷達發射機發射一種或多種信號波形，都要消耗一定數量的能量。特別是對那些距離遠或跟蹤精度較高的目標，為保證足夠的數據質量，可能要消耗更多的發射機能量。
( 3 )計算機資源約束：在每一個雷達任務結束後，雷達回波要經過信號處理機送到雷達系統計算機進行數據處理，因而要占用相應的計算機處理與存儲資源。
三大資源約束中，時間資源約束是最主要的的資源約束，也是調度中主要考慮的因素。
自適應調度算法
計算模組的自適應調度算法，即負載平衡策略，是在包含大量不同計算機中的網路中，選擇最合適給定問題的計算機進行計算。下面給出了選擇最優計算模組的策略。並討論了調度算法涉及到的各個參數，給出了計算(或者估計)這些參數的模型及方法。
選擇最優計算模組策略
假定最合適的計算模組是對給定問題P需要最少執行時間T的計算模組。這樣，就需要估計系統中每個計算模組M需要的執行時間。基本上，可以把執行T分成兩部分Ta和Tc，這裡的Ta是通過網路把數據傳送給M和從M取得結果的時間；Tc是執行計算所需要的時間。
時間Ta可以通過計算下列參數得到:
1．本機與M之間的網路延遲與網路頻寬；
2．傳送數據的規模；
3．返回結果的規模。
計算Tc需要計算下列參數:
1.問題的規模；
2.使用算法的複雜度；
3.M的性能，它取決於M的負載和M的原始性能
性能模型
其中，P為估計的性能指數；P為原始性能指數；ω為M的工作負載。當然，由於未考慮到作業系統的因素，這個模型並不精確。
執行時間T的計算
每當有任何請示時．代理對每個計算服務模組執行一次T的估算。這個計算使用前面所述的所有參數進行計算。可以把這些參數分成三類：
●客戶相關參數
1．傳送數據的規模；
2．接收結果的規模；
3．問題的規模。
●靜態的服務模組相關參數
1．本機與M之間的網路特性，如頻寬、延遲等；
2．M使用的算法的複雜度；
3．M的原始性能指數。
●動態的服務模組相關參數
1．M的工作負載：
客戶端相關參數包含在客戶對調度代理的問題請求中，因此它們的計算是直接的。靜態的服務模組相關參數通過只需要一次存儲。
網路特即性通過多次計算網路特性(頻寬、網路延遲)等，可以得到一個合理的網路延遲和頻寬的平均值。由於在取得它們的平均值後，這些值通常不會有很大改變，因此可以把它們稱為靜態參數。
算法複雜度是當一個新的計算服務模組加入系統中時，它通告了其能解決問題的複雜度。由於算法複雜度只取決於計算服務模組的軟體設計，因此這個複雜度以後不會改變。
原始性能指數原始性能指數，指的是計算機空載時候的性能指數。在計算服務模組啟動時，這個指數就由其本身硬體、作業系統決定。計算時，我們可以使用benchmark程式獲取其值。
工作負載模型
在計算預測執行時間T時，工作負載參數是唯一的動態的服務模組相關參數。每個代理為每個計算模組保存工作負載的緩衝值。通過緩衝，在計算預測執行時間r時就可以直接計算，而此緩衝值只需要周期性更新。這個緩衝值可能過期，從而導致對預測執行時間T的錯誤估計。但是，考慮到不斷獲取精確的工作負載的代價，可以折衷採取這種取平均值的方法。
請求序列
用戶請求的任務組合圖，可用有向無環圖(DAG)來表示。由於用戶的輸入數據可能需要送給多個計算模組，用戶請求的數據可能存在數據冗餘，因此對用戶請求的序列進行最佳化，從而避免數據在網路上重複傳輸，改善數據通信性能。請求序列的目的在於降低網路傳輸量，減少總體請求回響時間。為此，請求序列的調度要做到：
1)不傳輸所有不必要的數據；
2)傳輸所有必要的數據。
同時，通過儘可能地同時執行計算模組，還可以縮短執行時間。為此，需要對請求序列的輸入和輸出參數進行細節分析，產生代表任務及其執行相關性的有向無環圖。此有向無環圖再被送到被選中進行請求序列計算的模組。
調度性能評估指標
在上述調度原則基礎上，定義性能評估指標，用於評估調度算法的性能和有效性。主要包括調度成功率(Schedule Sccess Ratio，SSR)、時間利用率(TimeUtilization Ratio， TUR)、平均時間偏移率(Average Time Shift Ratio，ATSR)。
( 1 )調度成功率(SSR)：
式中N 調度任務個數，Ntotal為相應任務總個數。此指標用以描述各種任務調度情況，並用於評估調度算法對優先權原則的遵循程度。
( 2 )時間利用率( TUR)：
式中T 為總時間，lti為調度成功任務的駐留時間長度。此指標用以描述調度算法對雷達時間的利用情況，並用於評估其對時間利用原則的遵循情況。
( 3 )平均時間偏移率(ATSR)：
其中N 為調度成功任務個數，sti為任務實際執行時刻，dti為任務期望發射時刻，wi為任務時間窗長度。
此指標用以描述任務實際執行時刻與期望執行時刻的偏移程度，並用以評估調度算法對期望時間原則的遵循程度。
