[發明專利]一種基于競態條件的任務調度方法

在審

• 申請號: 202010031828.9
• 申請日: 2020-01-13
• 公開（公告）號: CN111258730A
• 公開（公告）日: 2020-06-09
• 發明（設計）人: 李思照;韓新宇;孫建國;鞏建光;閻梓寧;王文衫
• 申請（專利權）人: 哈爾濱工程大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于競態條件的任務調度方法，其特征在于，包括以下步驟：

步驟1：輸入任務調度序列；

步驟2：構造競態條件檢測模型；

某操作事件e作為輸入，識別競態條件和Happened-Before關系；

若輸入的操作事件e為接收消息事件，則其對應于發送消息事件e_s，并且會在相同任務中發現每一個前置的接收消息事件e′；如果e′||e_s，則判定在e_s和e′_s之間存在競態條件，用表示；

若輸入的操作事件e為獲取信號量事件，則其對應于發送信號量事件e_g，并且會在相同任務中發現每一個前置的獲取信號量e′；如果e′||e_g，則在e′和e_g之間存在競態條件，用表示；

如果n個操作事件形成了執行序列且產生的時間序列t₁t₂···t_nt₁，則判定為非災難性的競態條件；

步驟3：確定競態集合；

由于競態條件的不確定性，最大熵模型函數p(y|x)是競態條件可能發生的最大概率，因此可以獲得最大發生概率的競態集合；最大熵模型函數p(y|x)求解方法為：

步驟3.1：確定一個特征空間作為問題域，收集原始訓練數據并將其轉換為訓練樣本；每個訓練樣本由一個實例x和其目標類y組成，一組訓練樣本T＝{(x₁,y₁),(x₂,y₂),…,(x_n,y_n)}對應于一個特定的執行環境；當事件y_i發生時，相應的上下文信息是x_i，經驗概率分布是從這個訓練樣本中獲得，特征f指的是x和y之間的特定關系，特征經驗的期望概率是滿足二元關系中特定要求的所有經驗概率的綜合，二元函數定義如下：

實際概率函數定義如下：

步驟3.2：選擇特征作為優化約束，保持特征的經驗概率和預期概率一致，令步驟3.1中的P是一個滿足約束集C的統計模型，argmax使得熵值最大化；在滿足約束集C所有約束條件時，確定最大熵；約束集C的函數定義如下：

熵值最大化函數定義如下：

步驟3.3：導出模擬最大熵的理論模型，將約束優化問題轉化為非約束優化問題，為每個特征值f_i引入拉格朗日算子λ，由于p(y|x)是一個條件概率，∑_yp(y|x)＝1，因此，通過每個實例x的參數k(x)，拉格朗日函數定義如下：

相應的參數λ_i將會把特征f_i的權重考慮在內，因此，λ_i滿足最大熵的條件p(y|x)，p_λ的最大值函數定義如下：

步驟3.4：應用多重收斂來調整λ_i，具體描述為：

步驟3.4.1：初始化

步驟3.4.2：重復函數直至其收斂，函數定義如下：

真實參數γ和Λ＝{λ₁,λ₂,...,λ_n}都是n+1的約束；為了最大化η(p,Λ,γ)，利用步驟3.3的函數來表示p_λ(y|x)，并結合∑_yp(y|x)＝1可以確定最大熵模型，最大熵模型函數定義如下：

步驟4：劃分子任務并消除競態條件；

如果兩個任務之間存在競態條件，則每個任務將會分為兩個部分即沒有災難性的競態條件的子任務(T_i'，T_j')和一個涉及到災難性競態條件的子任務(T_sub(i)，T_sub(j))；使用Lock函數避免T_sub(i)和T_sub(j)這兩個子任務的同步問題，消除災難性競態條件；T_sub會被允許多次申請Lock函數而不會導致死鎖，同時有必要確定Lock的擁有者和持有者數量LockCounter；當LockCounter為0時，則允許T_sub(i)或T_sub(j)申請Lock，在一個新的申請之后，LockCounter增加1，并在Lock函數后減1；如果T_sub(i)持有一個Lock，則如果T_sub(j)請求Lock，它將會阻塞；如果T_sub(i)重新申請已經存在的Lock，則將會允許此操作；

步驟5：一旦處理器內核處于空閑狀態，所有子任務和任務就會循環分配給處理器內核。