[發明專利]一種面向分布式系統的任務可調度性驗證方法

在審

• 申請號: 202110994159.X
• 申請日: 2021-08-27
• 公開（公告）號: CN113806924A
• 公開（公告）日: 2021-12-17
• 發明（設計）人: 朱國鋒;遲鵬程;于樂
• 申請（專利權）人: 中國航空無線電電子研究所
• 主分類號: G06F30/20
• 分類號: G06F30/20;G06F30/18;G06F111/02
• 代理公司: 上海和躍知識產權代理事務所(普通合伙) 31239
• 代理人: 楊慧

1.一種面向分布式系統的任務可調度性驗證方法，包含以下步驟：

步驟一、采用基于時間自動機模型的處理器模型、任務模型、調度模型以及網絡總線模型四個方面對分布式系統進行仿真；其中，任務模型在任務下達后將任務置于就緒狀態，并根據調度模型的調度以及任務的屬性對任務的狀態進行調整；調度模型根據調度規則將任務調度到處理器模型或者網絡總線模型上；處理器模型在將收到調度模型分配的任務后根據自身模擬的處理器進行空閑和占用狀態的切換，網絡總線模型在將收到調度模型分配的任務后根據自身模擬的總線進行空閑和占用狀態的切換；

步驟二、借助仿真分析工具對任務是否在截至時間完成、總線的占用情況以及處理器的占用情況進行驗證與分析，從而對分布式系統的任務可調度性作出判斷。

2.根據權利要求1所述的一種面向分布式系統的任務可調度性驗證方法，其特征在于：所述任務的屬性包含基礎屬性，任務的基礎屬性包括周期、執行時間、截至時間和優先級；

在基礎型的任務模型中，以任務的就緒、執行、完成和錯誤作為基本狀態，以任務的基礎屬性作為任務模型的狀態轉移的條件。

3.根據權利要求2所述的一種面向分布式系統的任務可調度性驗證方法，其特征在于：所述任務的屬性還包含任務的依賴屬性，任務的依賴屬性包含任務對指定處理器/核的綁定、任務間的依賴關系；任務間的依賴關系包含和其他任務公用某些資源、存在資源的搶占與等待，以及任務執行的先后順序；

根據任務的依賴屬性在基礎型的任務模型中加入若干個與依賴屬性相關的狀態和轉移條件。

4.根據權利要求1所述的一種面向分布式系統的任務可調度性驗證方法，其特征在于：處理器模型的狀態分為空閑和占用，在空閑狀態下接收調度模型對其派分任務并將狀態變為占用，而對應的任務模型則從就緒變為執行狀態；根據模擬的處理器的處理能力判斷處理任務的耗時時間，從而在對應的時間點將占用狀態變為空閑狀態。

5.根據權利要求1所述的一種面向分布式系統的任務可調度性驗證方法，其特征在于：網絡總線模型的狀態均分為空閑和占用，在空閑狀態下接收調度模型對其派分任務并將狀態變為占用；根據模擬的網絡總線的處理能力判斷處理任務的耗時時間，從而在對應的時間點將占用狀態變為空閑狀態。

6.根據權利要求5所述的一種面向分布式系統的任務可調度性驗證方法，其特征在于：網絡總線模型劃分為接收、傳播和發送三類；

其中發送類的網絡總線模型的處理能力與發送端口的信息量和速率有關；

接收類的網絡總線模型的處理能力與接收端口的信息量和速率有關；

傳播類的網絡總線模型的處理能力除了考慮傳輸路徑的固有傳播時延外，還與網絡機理相關。

7.根據權利要求1所述的一種面向分布式系統的任務可調度性驗證方法，其特征在于：當調度模式為搶占式調度時，調度模型在接收到多個任務時，需要對當前將執行的任務進行排序仲裁；

任務排序規則有單調速率排序、輪詢排序、基于固定優先級的排序、基于距離截止時間最近的排序；其中單調速率排序策略將眾多任務按照周期長短分配優先級，處理器資源或總線資源優先分配給高優先級任務；輪詢策略則依照初始序列順序重復遍歷任務隊列。

8.根據權利要求1所述的一種面向分布式系統的任務可調度性驗證方法，其特征在于：對于同構多核處理器的核間任務調度的調度模型需要關注基于負載均衡的任務調度和固定綁定的任務調度策略，基于負載均衡的任務調度需在多核間建立動態調度模型，固定綁定的任務調度則建立固定式的靜態調度模型對于異構多核處理器的任務調度則建立固定式的靜態調度模型。

9.根據權利要求1所述的一種面向分布式系統的任務可調度性驗證方法，其特征在于：步驟二中，通過在UPPAAL中對仿真的分布式系統進行動態模擬仿真，獲得時間片調度情況，每個分區內任務調度的狀態，以及處理器計算資源占用的情況。

10.根據權利要求1所述的一種面向分布式系統的任務可調度性驗證方法，其特征在于：步驟二中，在仿真的分布式系統中加入時間注入模型，給消息傳輸打時間戳，統計系統端到端傳輸耗時，對該分布式系統的傳輸時延作評估。