[發(fā)明專利]基于Barrelfish的時間觸發(fā)實時調度方法

有效

• 申請?zhí)枺?/td>: 202110663286.1
• 申請日: 2021-06-15
• 公開（公告）號: CN113407319B
• 公開（公告）日: 2022-06-17
• 發(fā)明（設計）人: 童超;陳遜;楊婷婷
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 北京卓特專利代理事務所(普通合伙) 11572
• 代理人: 田冰;段旺

1.一種基于Barrelfish時間觸發(fā)實時調度方法，其特征在于，所述方法運行于采用TTP/C時間觸發(fā)式通信協(xié)議的分布式實時系統(tǒng)；所述分布式實時系統(tǒng)包括多個節(jié)點；所述分布式實時系統(tǒng)的節(jié)點包括端節(jié)點計算機和時間觸發(fā)以太網交換節(jié)點，實時任務在端節(jié)點計算機上執(zhí)行，并通過時間觸發(fā)以太網傳遞和接收消息；

其中實時任務用四參數(shù)模型來表示，其中τi代表第i個實時任務，φ表示該實時任務在每個周期內被釋放的時刻相對于周期開始時刻的偏移，C表示該實時任務在最壞的情況下需要運行的時間，D表示該實時任務相對于任務釋放時刻的截止期限，T表示該實時任務兩次被釋放的時間間隔；

其中時間觸發(fā)以太網是一個二層的交換網絡，網絡拓撲可以表示成一個有向圖

其中是節(jié)點的集合，包括端節(jié)點和交換節(jié)點，表示網絡中邊的集合，時間觸發(fā)以太網采用雙向的全雙工的物理鏈路，數(shù)學表示如下：

其中[v_a，v_b]表示節(jié)點v_a和節(jié)點v_b之間的一條有向邏輯鏈路，一條物理鏈路(Link)[v_a，v_b]的數(shù)學表示如下：

[v_a，v_b].s，[v_a，v_b].d，[v_a，v_b].mt

其中參數(shù)s表示傳輸速率；參數(shù)d表示鏈路延遲，參數(shù)延遲由傳播和處理延遲構成；

參數(shù)mt表示時間觸發(fā)以太網的宏拍粒度；

一對通信節(jié)點的通信路徑為虛鏈路，端節(jié)點v_a通過交換節(jié)點與端節(jié)點v_b建立通信連接，那么端節(jié)點v_a與端節(jié)點v_b之間的虛鏈路vl[v_a，v_b]表示如下：

vl[v_a，v_b]＝[[v_a，v₁]，[v₁，v₂]，[v₁，v₂]，…，[v_n-1，v_n]，[v_n，v_b]]

消息在虛鏈路上傳輸，在傳輸過程中消息的實例和進行通信調度的基本單位為幀，虛鏈路vl上傳輸?shù)南i在第j條物理鏈路[v_a，v_b]上的幀實例記為虛鏈路vl上所有的幀集合記為整個系統(tǒng)內所有的幀集合記為F，一個幀的表示如下：其中參數(shù)T為發(fā)送周期，φ為發(fā)送偏移，L為發(fā)送占用時長；

所述方法包括以下步驟：

步驟1、在實時任務中添加通信親和性參數(shù)δ：

引入通信親和性參數(shù)δ在所述分布式實時系統(tǒng)中描述實時任務對消息發(fā)送和接收的偏向程度，

依賴于時間觸發(fā)以太網通信的實時任務包括Producer類型，Shaper類型和Consumer類型的任務，F(xiàn)ree類型為與消息無關的任務，則通信依賴的任務模型描述為：其中：①通信依賴任務τi不支持并行以及多關鍵性任務；②任務的通信親和力參數(shù)δ是一個[0，1]之間的數(shù)，描述任務對消息發(fā)送和接收的偏向程度；③僅同周期之間的任務存在優(yōu)先序約束；④不同周期的任務之間是獨立的；⑤Shaper類型任務一個周期內只能發(fā)送或者接受一個消息或者接收并發(fā)送一個消息；Free類型的任務不發(fā)送或者接受任何消息；⑥任務不能被跨核遷移；被分配完成后的任務只能在指定核上運行；

步驟2、拆分任務模型與通信模型的依賴進行分離調度：

對于由描述的Producer類型，Shaper類型和Consumer類型的任務，對于Producer類型或Shaper類型的發(fā)送消息的任務與Shaper類型或者Consumer類型的接收消息的任務若任務與之間存在通信關系，則設置發(fā)送消息任務執(zhí)行完畢后，其發(fā)送的消息m_i才可以被發(fā)送到網絡中，并且消息m_i到接收節(jié)點之前，接收消息的任務不可執(zhí)行；

步驟3、統(tǒng)一三種通信依賴任務的約束表示：

在所有節(jié)點任務可以調度的情況下通過調整參數(shù)τ_i.和參數(shù)τ_i.D使得通信調度的解空間盡量變大以滿足Free類型任務，Producer類型任務，Shaper類型任務和Consumer類型任務的需求，具體如下；

Free類型若Free任務集Γ_free中任務τ_i與任務τ_j具有優(yōu)先序依賴，僅設置約束τ_i.D＜τ_j.D.且

①Producer類型，設Producer類型任務τ_i對應的Consumer類型任務為則使得消息的調度余量盡量大的形式化目標為：其中d_i，c表示任務τi以及任務之間的預期網絡傳輸延遲；

②Consumer類型，設Consumer類型任務τ_i的生產者任務為則消息的調度余量盡量大的形式化目標為：其中d_p，i表示任務τ_i以及任務之間的預期延遲；

③Shaper類型，Shaper類型任務有兩個優(yōu)化目標：和將所述兩個優(yōu)化目標轉化為一個可解的優(yōu)化目標：針對當目標取得最優(yōu)值時該目標可能會導致結果出現(xiàn)極左偏以及極右偏的現(xiàn)象，引入通信親和性參數(shù)δ∈[0，1]來表達左偏或者右偏的程度，此時優(yōu)化目標為需要最小化的目標值：任務的和D參數(shù)需要滿足的約束為τ_i.D≥τ_i.C；τ_i.D≥0；Γ_{Consumer+Producer+Shaper}是可調度的(schedulable)；

步驟4.歸一化調度模型優(yōu)化目標

對于每個Producer類型任務構造一個虛擬的Producer類型任務且該虛擬的Producer類型任務的偏移為截止期限為0，網絡延遲為0；對于每個Consumer類型任務，構造一個虛擬的Consumer類型任務且該虛擬的Consumer類型任務的偏移為截止期限為0，網絡延遲為0：

對于Shaper類型任務，假設該Shaper類型任務由Producer類型任務轉換而來，可得轉換得到該Shaper類型任務的Producer類型任務的虛擬Producer類型任務的參數(shù)令δ＝0時，有：

從而有：該目標與單獨的Producer類型任務優(yōu)化目標等價；

對于Shaper類型任務，假設該Shaper類型任務由Consumer類型任務轉換而來，可得轉換得到該Shaper類型任務的Consumer類型任務的虛擬Consumer類型任務的參數(shù)令δ＝1時，Shape類型任務優(yōu)化目標等價于Consumer類型任務的優(yōu)化目標，

從而將Producer任務和Consumer任務統(tǒng)一歸為Shaper任務；

步驟5.約束求解：

經過目標歸一化后，Producer類型任務和Consumer類型任務的優(yōu)化目標等價于Shaper類型任務的優(yōu)化目標：再考慮可調度性約束：Γ_{Consumer+Producer+Shaper}是可調度的(schedulable)，并采用用于約束任務集Γ_{Consumer+Producer+Shaper}的可調度性，為凸約束，則整個約束優(yōu)化目標為凸優(yōu)化，使用逐步信賴域規(guī)劃方法進行約束求解；

步驟6、任務調度：

經過約束求解后，得到單獨的任務調度模型和通信調度模型在原有任務集的基礎上產生一個新的任務集；新的任務集在各個節(jié)點上獨立地利用EDF調度算法進行模擬調度生成任務調度表，由拆分約束保證其可調度性；根據(jù)新的任務集的參數(shù)和調度依賴拆分方法生成任務相關的消息調度約束，結合消息原有約束，生成消息調度表；在中斷處理接口函數(shù)調用任務調度接口后，任務調度器首先檢索任務調度表的下一個表項，如果已經是最后一個表項，則滾動到下一個周期，讀取需要調度的任務ID和任務結束時刻，如果任務ID為負，則表明本次時間片為空閑時隙，交由非實時任務調度邏輯處理，否則設置下一次時鐘中斷到時間片結束，然后檢索對應需要調度的任務的進程控制塊，返回給中斷處理接口。