一種基於約束規劃的綜合化航空電子系統任務分配與調度方法

2024-04-12 19:31:05

1.本發明屬於安全關鍵軟體技術領域，具體涉及一種基於約束規劃的綜合化航空電子系統任務分配與調度方法。


背景技術：

2.對於硬實時系統，軟體運行時執行的可預測延遲與計算結果的正確性同樣重要。特別是對於安全關鍵系統，未能及時提供正確的結果可能會導致系統級功能失調，造成嚴重後果，如嚴重的金錢損失或生命損失。航空航天系統屬於這類系統，必須在設計時分析每個軟體操作，以便在運行時導出其執行持續時間的安全上限，相應地提前配置整個系統的運行時行為，保證系統的實時性。
3.航空電子系統經歷了獨立式、聯邦式、綜合化(integrated modular avionics，ima)以及近期提出來的智能開放式(future airborne capability environment,face)等階段。為了保證各個航電功能安全執行，ima引入分區的概念，每個分區包含獨立的地址空間、上下文數據以及實時任務，一個分區的錯誤行為不能影響到其它分區。綜合化航空電子系統往往採用cots或oem方式，為了方便對不同供應商所提供的航電功能進行集成，綜合模塊化航空電子系統(ima)成為主要的選擇。例如，f22、空客a380、波音787、均採用了ima體系架構。然而，由於功能需求的發展，ima對處理器計算性能的要求日趨提高。相比單核處理器，能夠提供更強計算能力而又能減少了電子設備的體積、重量和功耗(size,weight and power,即swap特性)的多核處理器在ima領域得到廣泛應用。但是，多核處理中多個核心會共享主存、總線等資源，核內任務在執行期間可能存在等待共享資源而導致的時間延遲的問題。根據faa測算，存在一次由於資源共享導致的時間幹擾，可能導致當前分區的最壞執行時間呈8倍增長，而如果存在2-3次時間幹擾，當前分區的最壞執行時間達到13倍的增長。傳統的時序分析僅針對單核處理器，不能準確的預測任務在多核處理器下的最壞執行時間，會導致任務執行可能超出其規定截止時間，造成嚴重的後果。因此，考慮多核處理器中主要共享資源可能帶來的幹擾，計算出延遲的上界，成為航空電子系統安全使用多核處理器的關鍵前提。
4.目前機載航空電子系統，如天脈等，任務的分配主要依靠手工迭代地進行，直到得到符合要求的分配結果，這個過程需要大量的人工和時間成本，效率低下；傳統的調度算法，如edf、fcfs等，在日益複雜的多核ima下，不能滿足所有的任務調度需求。


技術實現要素：

5.發明目的：為解決機載航空電子系統在多核處理器上任務分配和調度方面存在效率低下、需要大量人工和時間成本等問題，本發明提出一種基於約束規劃的綜合化航空電子系統任務分配與調度方法，採用約束規劃手段，自動、安全、優化地得到預期的分配和調度結果，減少手工迭代的過程，提高任務分配和調度生成的效率。
6.技術方案：一種基於約束規劃的綜合化航空電子系統任務分配與調度方法，包括以下步驟：
7.根據多核平臺下的ima系統結構特徵，通過考慮共享主存產生的幹擾，構建多核任務分配場景下的ima體系中任務的wcet和wcrt計算模型；利用多核任務分配場景下的ima體系中任務的wcet和wcrt計算模型，計算多核任務分配場景下的ima體系中任務的wcet和wcrt；
8.將針對ima系統的任務分配問題形式化為第一約束規劃問題，對第一約束規劃問題進行建模，通過考慮多核任務分配場景下的ima體系中任務的wcet和wcrt，設計第一約束規劃問題要滿足的約束條件；所述約束條件包括分配約束和可行性約束；將設計好的約束條件和第一約束規劃問題放入求解器中進行求解，得到預期分配結果；所述預期分配結果包括任務和核心、內存控制器之間的映射關係；
9.依據預期分配結果，將任務與核心、內存控制器之間的映射關係以xml形式的配置文件寫入ima的作業系統中去，作業系統根據配置文件中的映射關係，將系統中任務與相應核心、內存控制器進行綁定。
10.本發明還公開了一種基於約束規劃的綜合化航空電子系統任務分配與調度方法，包括以下步驟：
11.根據多核平臺下的ima系統結構特徵，通過考慮共享主存產生的幹擾和考慮等待開始執行的相應延遲，構建多核調度場景下的ima體系中任務的wcet和wcrt計算模型；利用多核調度場景下的ima體系中任務的wcet和wcrt計算模型，計算多核調度場景下的ima體系中任務的wcet和wcrt；
12.將針對ima體系的調度問題形式化為第二約束規劃問題，對第二約束規劃問題進行建模，通過考慮多核調度場景下的ima體系中任務的wcet和wcrt，設計第二約束規劃問題要滿足的約束條件；該約束條件包括調度約束和可調度性約束；將設計好的約束條件和第二約束規劃問題放入求解器中進行求解，得到預期調度結果，所述預期調度結果包括每個分區在每一幀的開始時間和每個任務實例的開始時間；
13.依據預期調度結果，將每個分區和每個任務實例的執行情況以xml形式的配置文件寫入ima的作業系統中，作業系統根據配置文件中的執行情況靜態地對分區和任務進行調度。
14.有益效果：本發明與現有技術相比，具有以下優點：
15.(1)本發明深入主存內部結構，從硬體角度具體分析任務共享主存時受到幹擾的各種情況，計算出任務執行期間可能受到幹擾延遲的上界，保證航空電子系統的實時性；
16.(2)本發明為航空電子系統提供了一種多核場景下的任務分配和調度方法，用約束規劃的手段代替手工迭代的過程，提高效率和節省大量的人力和時間成本的同時，可以更加安全、優化地得到預期的結果。
附圖說明
17.圖1為本發明的任務分配和調度的總體流程圖；
18.圖2為主存內部結構圖；
19.圖3為內存控制器結構圖；
20.圖4為主時間框架下分區和任務調度示例圖。
具體實施方式
21.下面結合附圖和實施例進一步闡述本發明方法。
22.實施例1：
23.本實施例公開了一種基於約束規劃的綜合化航空電子系統任務分配與調度方法，其主要包括以下步驟：
24.步驟1：從經典的單核場景下任務最壞執行時間(wcet)計算公式入手，根據多核平臺下的ima系統結構特徵，演變成多核ima場景下任務wcet計算方法，並且將主存作為主要考慮的共享資源，深入主存內部結構，具體分析任務在共享主存時可能受到的幹擾延遲，計算出主存幹擾延遲上界，加入到任務最壞執行時間中。上述計算公式作為約束加入後續步驟的約束求解算法中，提供可行性分析。本步驟具體內容如下：
25.針對分配問題，從經典的時序分析入手，它只針對單核場景下任務的wcrt和wcet的計算，並且也不符合ima體系結構，計算公式如下：
[0026][0027]
式中，ri表示任務的wcrt，wi表示任務的wcet，ji表示任務開始執行前的抖動時間，ci表示任務的執行時間，hp(ti)表示優先級高於ti的任務集合。計算任務的最壞執行時間即假設所有優先級高的任務都先執行完的總時間再加上任務自己的執行時間。
[0028]
在ima體系結構中，分區用於分割不同的任務，一個任務只能被同一分區的其他任務搶佔，對wcet計算公式更新如下：
[0029][0030]
式中,pidi表示任務所屬分區的代號，pidi＝pidj就代表任務ti和tj屬於同一分區，c
sw
表示與從剛完成執行的任務到下一個要調度的任務的上下文切換相對應的開銷。ti表示任務ti的周期，tj表示任務tj的周期。
[0031]
經典的wcet計算公式主要針對單核情形，在多核場景下，任務在不同核下的執行時間會有差異，故對公式中ci重新定義如下：
[0032][0033]
式中，表示任務ti在核心p中執行時間；
[0034][0035]
並且在多核場景下，由於資源共享，任務的執行會造成延遲，在時序分析中就必須
把多核幹擾帶來的延遲考慮進去，否則任務wcet會造成較大差距。這裡主要考慮了主要的幹擾：共享主存(同一內存控制器)產生的幹擾dram函數。
[0036]
綜上所述，在多核分配場景下的ima體系中任務的wcet和wcrt計算公式如下：
[0037][0038]
主存儲器的入口點是內存控制器，主存內部結構和內存控制器結構如附圖1和附圖2所示。核心上的任務執行時發出的訪問主存請求都會先經過內存控制器，按照先就緒先來先服務(fr-fcfs)的策略依次調度，即
①
行命中的請求比行衝突的請求優先級更高；
②
先到的請求優先級更高。本發明主要考慮讀寫主存請求的四種命令：precharge(pre)、activate(act)、read(rd)和write(wr)。根據bank的狀態，內存控制器為單個讀寫請求生成一系列命令，當bank內行命中時，生成rd/wr命令；當bank內行衝突時，生成pre、act和rd/wr命令。
[0039]
當核p不與其他核共享bank時，會受到inter-bank幹擾延遲。當核p上的任務生成主存請求時，根據請求類型生成相應命令，在bank調度程序中，由於核p不共享bank，因此沒有來自其他核的幹擾延遲，當請求送入到通道調度程序，它就會被其他bank的命令延遲。考慮任務所受幹擾延遲的最壞情況，即假設
①
核p的請求在其他核的請求之後到達
②
之前的每個請求都產生pre、act、rd/wr命令，計算出幹擾延遲的上界，計算公式如下：
[0040][0041]
式中，表示precharge命令造成的延遲，表示activate命令造成的延遲，表示read和write命令造成的延遲，表示核q和核p不共享bank。
[0042]
當核p與其他核共享bank時，會受到intra-bank幹擾延遲。當核p上的任務生成主存請求時，根據請求類型生成相應命令，由於核p與其他核共享bank，它會受到來自其他核請求的幹擾，當請求為行衝突請求時，根據fr-fcfs策略，bank調度程序會對請求進行重排序。考慮任務所受幹擾延遲的最壞情況，即假設
①
核p的請求都行衝突
②
核q的請求在與其共享bank的核的請求之後到達，且核q的請求也都行衝突，計算出幹擾延遲的上界，計算公式如下：
[0043][0044]
式中，reorder(p)表示調度程序對請求進行重排序的時間，l
conf
表示處理行衝突請求的時間。
[0045]
核p上的請求會同時受到inter-bank和intra-bank幹擾，故幹擾延遲上限為：
[0046][0047]
來自核p上的任務發出訪問主存請求受到的幹擾延遲上限為：
[0048]
dram(ti)＝hi×
dram
p
ꢀꢀ
(8)
[0049]
式中，hi表示任務ti執行過程中訪問主存的最大次數。
[0050]
步驟2：將基於多核平臺的ima系統任務分配問題形式化為約束規劃問題，即將實際場景下的分配問題表達成約束公式，在變量域內搜索滿足每一條約束的結果。任務分配問題主要考慮兩類約束：分配約束和可行性約束。分配約束側重於基本的分配約束；可行性約束可確保所選分配對應於可行系統，在該系統中，在計劃配置階段的後期，可以找到至少一個與所有截止時間相關的計劃。
[0051]
將任務分配問題形式化為約束規劃問題，具體內容如下：
[0052]
約束規劃(constraint programming,cp)是指從一組候選集合中找出可行的解決方案，在這些候選集合中，問題可以用任意約束來建模，許多科學和工程學科中都存在cp問題。cp是基於可行性(尋找一個可行的解決方案)而不是最優化(尋找一個最優的解決方案)，它關注的是約束和變量而不是目標函數。在約束規劃問題中，關鍵點在於問題的建模求解，把實際場景中的問題用變量和約束的形式表現出來，再用求解器對其進行求解以得到預期的結果。
[0053]
約束規劃的主要步驟如下：
[0054]
①
確定要解決的問題和得到已有的輸入信息。
[0055]
②
對問題進行建模：定義所需要的變量，設計問題要滿足的約束條件。在設計約束時，往往是一個更新迭代的過程，從最基本要滿足的頂層約束出發，一步步細化下面的約束，最終達到對問題的全方面覆蓋。
[0056]
③
把設計好的約束和所需的目標函數放入求解器中進行求解。
[0057]
針對ima系統的任務分配問題，可以定義該問題中的cp變量。分別用na
ij
和t2mc
ij
表示任務的分配情況：
[0058][0059][0060]
然後設計約束，該分配問題主要包含兩類主要約束：分配約束和可行性約束。分配約束側重於基本的分配約束，例如確保所有分區和任務只分配給一個核心，至少分配給一個內存控制器；可行性約束可確保所選分配對應於可行系統，在該系統中，在計劃配置階段的後期，可以找到至少一個與所有截止時間相關的計劃。
[0061]
con1：所有任務到核只分配一次：
[0062][0063]
式中，nc表示核的數量。
[0064]
con2：不能過載任何核：
[0065][0066]
式中，n
t
表示任務數量。
[0067]
con3：所有任務到內存控制器至少分配一次：
[0068][0069]
式中，n
mc
表示內存控制器的數量。
[0070]
con4：分配給內存控制器的任務大小總和不能超出內存大小：
[0071][0072]
式中，trami表示任務大小，mcsizek表示內存控制器管理的內存大小。
[0073]
con5：可行性約束：
[0074][0075]
此約束代表了前文面向多核下的任務wcet計算中針對分配問題提出的可行性分析，用於早期時序分析，並通過強制選擇通過可行性測試的分配，以安全的方式指導分配搜索，以保證分配時已滿足多核場景下ima體系的可調度性要求。
[0076]
將設計好的約束放入求解器中進行求解，得到分配結果。預期分配結果為na
ij
和t2mc
ij
兩個分配矩陣，分別表示任務和核心、內存控制器之間的映射關係。本實施例重心在於構建多核ima體系下任務的分配方法，故求解的過程藉助通用的開源求解器進行，不做詳細闡述。
[0077]
實施例2：
[0078]
本實施例公開了一種基於約束規劃的綜合化航空電子系統任務分配與調度方法，其主要包括以下步驟：
[0079]
步驟1：從經典的單核場景下任務最壞執行時間(wcet)計算公式入手，根據多核平臺下的ima系統結構特徵，演變成多核ima場景下任務wcet計算方法，並且將主存作為主要考慮的共享資源，深入主存內部結構，具體分析任務在共享主存時可能受到的幹擾延遲，計算出主存幹擾延遲上界，加入到任務最壞執行時間中。上述計算公式作為約束加入後續步驟的約束求解算法中，提供可調度性分析。
[0080]
針對調度問題：在任務調度問題中，wcet的計算方式與實施例1中的分配任務有所不同，從任務的角度來看，分配問題和調度生成問題之間的主要區別在於，分配驗證關注的是在最壞情況下每個任務在運行時可能具有的最大wcrt，而調度驗證驗證的是，對於給定的調度，每個任務實例都能夠滿足其截止日期和依賴性約束。因此，在非搶佔情況下的分配驗證中，ri的計算就好像ti是在所有高優先級任務之後調度的一樣。然後，生成的wcet wi包含等待開始執行的相應延遲ti。在執行可調度性分析時，計劃已經存在，因此在計算其wcet wi時，將與正在執行的ti以外的任務相對應的延遲包括進來不再有意義。然後可以使用以下方程式代替wi：
[0081][0082]
到每一個任務的調度實例上：
[0083][0084]
式中，表示任務i的第k個實例的開始時間，po
ik
表示分區i在第k幀的開始時
間，表示分區i在第k
′
個窗口的運行長度，表示任務i所在分區運行的窗口數，表示任務i所在分區的周期，當時，表示第k個任務i實例在第k
′
個分區窗口內執行，在同一分區窗口內執行的任務才會互相造成幹擾。ti表示任務ti的周期，tj表示任務tj的周期。
[0085]
對於搶佔任務時，把每一個任務實例都看做一個單獨的任務來處理，它只調度一次，周期為一個maf。
[0086]
任務i的第k個實例的優先級等於任務i的優先級；
[0087]
任務i的第k個實例的截止時間等於k*di；
[0088]
任務i的第k個實例的wcrt為
[0089]
任務i的第k個實例的wcet為
[0090]
加上優先級高的任務延遲：
[0091][0092]
式中，nbactivj表示任務j的執行次數，當(m-1)tj＝(k-1)ti時，表示任務i的第m個實例和任務j的第k個實例在同一窗口內執行，即當任務優先級更高，且在同一個窗口內執行時，才會造成搶佔。
[0093]
綜上所述，在多核調度場景下的ima體系中任務的wcet和wcrt計算公式如下：
[0094][0095]
主存儲器的入口點是內存控制器，主存內部結構和內存控制器結構如附圖1和附圖2所示。核心上的任務執行時發出的訪問主存請求都會先經過內存控制器，按照先就緒先來先服務(fr-fcfs)的策略依次調度，即
①
行命中的請求比行衝突的請求優先級更高；
②
先到的請求優先級更高。本發明主要考慮讀寫主存請求的四種命令：precharge(pre)、activate(act)、read(rd)和write(wr)。根據bank的狀態，內存控制器為單個讀寫請求生成一系列命令，當bank內行命中時，生成rd/wr命令；當bank內行衝突時，生成pre、act和rd/wr命令。
[0096]
當核p不與其他核共享bank時，會受到inter-bank幹擾延遲。當核p上的任務生成主存請求時，根據請求類型生成相應命令，在bank調度程序中，由於核p不共享bank，因此沒有來自其他核的幹擾延遲，當請求送入到通道調度程序，它就會被其他bank的命令延遲。考慮任務所受幹擾延遲的最壞情況，即假設
①
核p的請求在其他核的請求之後到達
②
之前的每個請求都產生pre、act、rd/wr命令，計算出幹擾延遲的上界，計算公式如下：
[0097][0098]
式中，表示precharge命令造成的延遲，表示activate命令造成的延遲，表示read和write命令造成的延遲，表示核q和核p不共享bank。
[0099]
當核p與其他核共享bank時，會受到intra-bank幹擾延遲。當核p上的任務生成主存請求時，根據請求類型生成相應命令，由於核p與其他核共享bank，它會受到來自其他核請求的幹擾，當請求為行衝突請求時，根據fr-fcfs策略，bank調度程序會對請求進行重排序。考慮任務所受幹擾延遲的最壞情況，即假設
①
核p的請求都行衝突
②
核q的請求在與其共享bank的核的請求之後到達，且核q的請求也都行衝突，計算出幹擾延遲的上界，計算公式如下：
[0100][0101]
式中，reorder(p)表示調度程序對請求進行重排序的時間，l
conf
表示處理行衝突請求的時間。
[0102]
核p上的請求會同時受到inter-bank和intra-bank幹擾，故幹擾延遲上限為：
[0103][0104]
來自核p上的任務發出訪問主存請求受到的幹擾延遲上限為：
[0105]
dram(ti)＝hi×
dram
p
ꢀꢀ
(8)
[0106]
式中，hi表示任務ti執行過程中訪問主存的最大次數。
[0107]
步驟2：將基於多核平臺的ima系統任務分配問題形式化為約束規劃問題，即將實際場景下的調度問題表達成約束公式，在變量域內搜索滿足每一條約束的結果。任務調度問題主要考慮兩類約束：調度約束和可調度性約束。調度約束側重於基本的與調度相關的約束；可調度性約束確保生成調度計劃中，所有任務都在其截止時間之前完成。
[0108]
將任務調度問題形式化為約束規劃問題，具體內容如下：
[0109]
針對調度問題，ima體系下任務調度為雙層調度，首先對分區在主時間框架gmaf中進行調度，再對分區內任務在各個分區窗口中進行調度。
[0110]
定義變量表示分區i在第k幀的開始時間，變量表示任務i的第k個實例的開始時間。
[0111]
gmaf為主時間框架，gmif為次時間框架。gmaf被劃分為的等長的frames(幀)，一個gmif即為一幀，gmif的數量即為幀數，nframes。gmaf和gmif的長度都與分區的周期有關，周期的長度總是gmif的整數倍，示例如附圖4所示。
[0112][0113][0114]
然後設計約束，該分配問題主要包含兩類主要約束：調度約束和可調度性約束。調度約束側重於基本的與調度相關的約束，如調度框架的生成；可調度性約束確保生成調度計劃中，所有任務都在其截止時間之前完成。
[0115]
con1：預處理約束如下：
[0116][0117][0118]
分區內被劃分為個分區窗口，周期性的在主時間框架內運行，由於分區窗口的預算會在各個幀重複出現，故對其進行預處理，使得每一幀分配給分區的時間滿足預算。con2：分區調度生成，生成每個分區在每一幀窗口的激活時間，約束如下：
[0119][0120][0121]
由於分區具有周期性，各個分區的周期不同，其都為mif的不同整數倍，故在每一幀內並非所有分區都會運行，需要進行判斷分區在每一幀的運行情況。式中用取模操作判斷分區在每一幀的運行情況，若k-1倍的gmif為該分區周期的整數倍，則該分區在第k幀運行，反之則不運行，將開始時間置0。
[0122]
con3：當兩個分區在同一幀內時，不能同時運行，約束如下：
[0123][0124][0125]
con4：任務調度生成，生成每個任務實例的激活時間，約束如下：
[0126][0127][0128]
con5:分區窗口強制約束：
[0129][0130]
公式(23、24)中表示的關係適用於任何實時環境。然而，在ima軟體中，任務執行只能在其分區時間窗口的邊界內進行，故需要加強任務執行的邊界約束。
[0131]
con6：當相同分區內分配到同一核上的兩個任務不能同時運行：
[0132]
[0133][0134]
式中前提條件前半部分限制兩個任務分配給同一個核，後半部分限制兩個任務在同一個分區窗口內執行。
[0135]
con7：可調度性約束
[0136][0137]
式中每一個任務實例的最壞執行時間，來自前文面向多核ima體系的任務wcet計算中提到的可調度性分析，將主要的共享主存帶來的幹擾延遲考慮進來，保證每個任務實例在運行時都不會超過其截止時間。
[0138]
將設計好的約束和目標函數放入求解器中進行求解，預期輸出兩個數組，數組中元素分別表示每個分區在每一幀的開始時間和每個任務實例的開始時間。